4. Các thuật toán điều độ

a. Thuật toán đến trước phục vụ trước (FCFS):

- Tiến trình yêu cầu CPU trước sẽ được cấp trước.

- HDH xếp các tiến trình sẵn sàng vào hàng đợi FIFO.

- Tiến trình mới được xếp vào cuối hàng đợi.

-Đơn giản, đảm bảo tính công bằng.

- Thời gian chờ đợi trung bình lớn.

-=> Ảnh hưởng lớn tới hiệu suất chung của toàn hệ thống.

- Thường là thuật toán điều độ không phân phối lại.

b. Điều độ quay vòng (RR: round robin):

- Sửa đổi FCFS dùng cho các hệ chia sẻ thời gian.

- Có thêm cơ chế phân phối lại bằng cách sử dụng ngắt của đồng hồ.

- Hệ thống xác định những khoảng thời gian nhỏ gọi là lượng tử/ lát cắt thời gian t.

- Khi CPU được giải phóng, HDH đặt thời gian của đồng hồ bằng độ dài lượng tử, lấy tiến trình ở đầu hàng đợi và cấp CPU cho nó.

- Tiến trình kết thúc trước khi hết thời gian t: trả quyền điều khiển cho HDH.

c. Điều độ quay vòng (tt)

- Hết lượng tử thời gian mà tiến trình chưa kết thúc:

+ Đồng hồ sinh ngắt.

+ Tiến trình đang thực hiện bị dừng lại.

+ Quyền điều khiển chuyển cho hàm xử lý ngắt của HDH.

+ HDH chuyển tiến trình về cuối hàng đợi, lấy tiến trình ở đầu và tiếp tục.

- Cải thiện thời gian đáp ứng so với FCFS.

-Thời gian chờ đợi trung bình vẫn dài.

- Lựa chọn độ dài lượng tử thời gian?

d. Điều độ ưu tiên tiến trình ngắn nhất (SPF)

-Chọn trong hàng đợi tiến trình có chu kỳ sử dụng CPU tiếp theo ngắn nhất để phân phối CPU.

-Nếu có nhiều tiến trình với chu kỳ CPU tiếp theo bằng nhau, chọn tiến trình đứng trước.

-Thời gian chờ đợi trung bình nhỏ hơn nhiều so với FCFS.

-Khó thực hiện vì phải biết độ dài chu kỳ CPU tiếp:

+ Trong các hệ thống xử lý theo mẻ: dựa vào thời gian đăng kí tối đa do lập trình viên cung cấp.

+Dự đoán độ dài chu kỳ CPU tiếp theo: dựa trên độ dài TB các chu kỳ CPU trước đó.

-Không có phân phối lại.

e. Điều độ ưu tiên thời gian còn lại ngắn nhất

-SFP có thêm cơ chế phân phối lại (SRTF)

-Khi 1 tiến trình mới xuất hiện trong hàng đợi, HDH so sánh thời gian còn lại của tiến trình đang chạy với thời gian còn lại của tiến trình mới xuất hiện.

-Nếu tiến trình mới xuất hiện có thời gian còn lại ngắn hơn, HDH thu hồi CPU của tiến trình đang chạy, phân phối cho tiến trình mới.

-Thời gian chờ đợi trung bình nhỏ.

-HDH phải dự đoán độ dài chu kỳ CPU của tiến trình.

-Việc chuyển đổi tiến trình ít hơn so với RR.

f. Điều độ có mức ưu tiên

-Mỗi tiến trình có 1 mức ưu tiên.

-Tiến trình có mức ưu tiên cao hơn sẽ được cấp CPU trước.

-Các tiến trình có mức ưu tiên bằng nhau được điều độ theo FCFS.

-Mức ưu tiên được xác định theo nhiều tiêu chí khác nhau.