CPU Scheduling

Hai thành phần chịu trách nhiệm điều phối CPU:

• Scheduler: chọn tiến trình từ ready queue để cấp phát CPU dựa trên các thuật toán điều phối CPU (xem thêm CPU Scheduling Algorithms).
• Dispatcher: giúp thực hiện chuyển đổi ngữ cảnh (Context Switch).

Các trường hợp ra quyết định điều phối:

1. Chuyển từ trạng thái running sang blocked.
2. Chuyển từ trạng thái running sang ready.
3. Chuyển từ trạng thái blocked, new sang ready.
4. Kết thúc thực thi.

Types of CPU Scheduling

Có hai loại điều phối:

• Không ưu tiên (non-preemptive): tiến trình sẽ ở trạng thái running cho đến khi nó bị blocked hoặc terminated. Chỉ thực hiện điều phối trong trường hợp 1 và 4.
• Ưu tiên (preemptive): tiến trình có thể bị ngắt và chuyển về trạng thái ready. Ngoài trường hợp 1 và 4 còn có trường hợp 2 và 3 (hoặc cả 2).

Scheduling Criteria

Khi điều phối, ta cần:

Tối đa:

• Thời gian sử dụng CPU. Nói cách khác là giảm thiểu thời gian nhàn rỗi của CPU xuống mức thấp nhất có thể.
• Số lượng tiến trình hoàn tất trong một đơn vị thời gian.

Giảm thiểu:

• Turn around time ($T_{quit}-T_{arrive}$): tổng thời gian mà tiến trình tồn tại ở trong hệ thống.
• Waiting time: là tổng thời gian chờ của tiến trình.
• Response time: là thời gian tính từ lúc tiến trình vào hàng đợi cho đến khi được thực thi lần đầu tiên.

Resources

• CPU Scheduling Algorithms in Operating Systems (guru99.com)