Trong các hệ thống lập trình đơn như MS DOS, khi một tiến trình chờ bất kỳ hoạt động I / O nào được thực hiện, CPU vẫn là thần tượng. Đây là một khoản phí lớn vì nó lãng phí thời gian và gây ra vấn đề starvation. Tuy nhiên, trong hệ thống Đa chương trình, CPU không ở trạng thái nghỉ trong thời gian chờ của process và nó bắt đầu thực hiện các process khác. Hệ điều hành phải xác định quá trình CPU sẽ được cung cấp.
Trong các hệ thống Đa chương trình, Hệ điều hành lập lịch trình cho các quá trình trên CPU để sử dụng nó tối đa và thủ tục này được gọi là lập lịch cho CPU . Hệ điều hành sử dụng các thuật toán lập lịch khác nhau để lập lịch cho các quá trình.
Các bài viết liên quan:
Đây là một nhiệm vụ của bộ lập lịch ngắn hạn để lập lịch cho CPU về số lượng quy trình có trong Nhóm công việc. Bất cứ khi nào quá trình đang chạy yêu cầu một số hoạt động IO thì bộ lập lịch ngắn hạn sẽ lưu bối cảnh hiện tại của quá trình (còn được gọi là PCB) và thay đổi trạng thái của nó từ đang chạy sang chờ. Trong thời gian, tiến trình ở trạng thái chờ đợi; bộ lập lịch ngắn hạn chọn một quá trình khác từ hàng đợi sẵn sàng và chỉ định CPU cho quá trình này. Thủ tục này được gọi là chuyển đổi ngữ cảnh .
Xem thêm Priority Scheduling trong Hệ điều hành
Những gì được lưu trong Khối Kiểm soát Process?
Hệ điều hành duy trì một khối điều khiển quy trình trong suốt thời gian tồn tại của quy trình. Khối điều khiển quá trình bị xóa khi quá trình bị kết thúc hoặc bị giết. Có thông tin sau được lưu trong khối điều khiển quy trình và sẽ thay đổi theo trạng thái của quy trình.
Tại sao chúng ta cần Lập lịch trình?
Trong Đa chương trình, nếu bộ lập lịch dài hạn chọn nhiều quá trình ràng buộc I / O hơn thì phần lớn thời gian, CPU vẫn là thần tượng. Nhiệm vụ của Hệ điều hành là tối ưu hóa việc sử dụng tài nguyên.
Nếu hầu hết các tiến trình đang chạy thay đổi trạng thái của chúng từ đang chạy sang chờ thì có thể luôn có khả năng xảy ra bế tắc trong hệ thống. Do đó, để giảm thiểu chi phí này, HĐH cần lên lịch các công việc để có được việc sử dụng CPU tối ưu và tránh khả năng bị deadlock.
Xem thêm Thuật toán Shortest Remaining Time First (SRTF)
Các thuật toán lập lịch trình
Có nhiều thuật toán khác nhau được Hệ điều hành sử dụng để lập lịch các quá trình trên bộ xử lý một cách hiệu quả.
Mục đích của thuật toán lập lịch trình
- Sử dụng CPU tối đa
- Phân bổ giá vé của CPU
- Thông lượng tối đa
- Thời gian quay vòng tối thiểu
- Thời gian chờ đợi tối thiểu
- Thời gian phản hồi tối thiểu
Có các thuật toán sau đây có thể được sử dụng để lập lịch trình công việc.
Đây là thuật toán đơn giản nhất để thực hiện. Quá trình với thời gian đến tối thiểu sẽ nhận được CPU đầu tiên. Thời gian đến càng ít, quá trình nhận được CPU càng sớm. Đây là kiểu lập kế hoạch không ưu tiên. Xem thêm Lập lịch FCFS trong Operating System
Trong thuật toán lập lịch Round Robin, Hệ điều hành xác định một lượng tử thời gian (lát cắt). Tất cả các quá trình sẽ được thực thi theo cách tuần hoàn. Mỗi tiến trình sẽ lấy CPU trong một khoảng thời gian nhỏ (gọi là lượng tử thời gian) và sau đó quay trở lại hàng đợi sẵn sàng để chờ đến lượt tiếp theo của nó. Đây là một kiểu lập kế hoạch phủ đầu.
Công việc có thời gian bùng nổ ngắn nhất sẽ nhận được CPU đầu tiên. Thời gian bùng nổ càng ít, quá trình lấy CPU càng sớm. Đây là kiểu lập kế hoạch không ưu tiên.
Đó là hình thức phủ đầu của SJF. Trong thuật toán này, Hệ điều hành lên lịch Công việc theo thời gian thực hiện còn lại.
Trong thuật toán này, mức độ ưu tiên sẽ được chỉ định cho mỗi quá trình. Mức độ ưu tiên càng cao thì tiến trình nhận được CPU càng sớm. Nếu mức độ ưu tiên của hai quy trình là như nhau thì chúng sẽ được sắp xếp theo thời gian đến.
Trong Thuật toán lập lịch này, quy trình có tỷ lệ phản hồi cao nhất sẽ được lên lịch tiếp theo. Điều này làm giảm tình trạng đói trong hệ thống.
Xem thêm Lập lịch Highest Response Ratio Next (HRRN) trong hệ điều hành
