Lập lịch CPU: Scheduling Algorithms

🎯 Mục tiêu bài học

Bạn là người quản lý rạp chiếu phim (CPU) có 1 phòng chiếu. Hàng ngàn khách (Process) đang xếp hàng. Cho ai vào xem trước?

1. Các tiêu chí đánh giá (Metrics)

• CPU Utilization: CPU bận rộn bao nhiêu % (Càng cao càng tốt).
• Throughput: Xử lý được bao nhiêu Process trong 1 giây.
• Turnaround Time (T.Time): Từ lúc xếp hàng đến lúc xem xong phim. (Càng nhỏ càng tốt).
• Waiting Time (W.Time): Thời gian đứng đợi ở hàng chờ.
• Response Time: Từ lúc bấm nút đến lúc thấy phản hồi đầu tiên trên màn hình. (Quan trọng cho UI).

2. Lab 4: Tính toán Lập lịch (Vẽ Gantt Chart)

Đề bài: 3 Process đến lúc t=0.

• P1: Cần 24ms.
• P2: Cần 3ms.
• P3: Cần 3ms.

Kịch bản 1: FCFS (First Come First Serve - Đến trước phục vụ trước)

Thứ tự: P1 -> P2 -> P3.

• P1 chạy: 0 -> 24. (Đợi 0).
• P2 chạy: 24 -> 27. (Đợi 24 - quá lâu cho task nhỏ!).
• P3 chạy: 27 -> 30. (Đợi 27).

Wait Time TB: (0 + 24 + 27) / 3 = 17ms.

👉 Convoy Effect (Hiệu ứng đoàn tàu): Một thằng béo (P1) làm tắc nghẽn cả hệ thống. P2, P3 chỉ cần 3ms nhưng phải đợi mòn mỏi.

Kịch bản 2: SJF (Shortest Job First - Việc ngắn làm trước)

Thứ tự tối ưu: P2 -> P3 -> P1.

• P2 chạy: 0 -> 3. (Đợi 0).
• P3 chạy: 3 -> 6. (Đợi 3).
• P1 chạy: 6 -> 30. (Đợi 6).

Wait Time TB: (0 + 3 + 6) / 3 = 3ms.

👉 Nhanh hơn gấp 5 lần! Nhưng vấn đề là OS không thể biết trước Process cần chạy bao lâu (Tương lai).

Kịch bản 3: Round Robin (Xoay vòng - Lượng tử thời gian = 4ms)

Máy tính hiện đại dùng cái này. Mỗi người chỉ được chạy 4ms rồi cút xuống cuối hàng.

• 0-4: P1 chạy (còn 20).
• 4-7: P2 chạy (Xong).
• 7-10: P3 chạy (Xong).
• 10-30: P1 chạy nốt.

👉 P2, P3 được phản hồi rất nhanh (dưới 10ms). Tốt cho trải nghiệm người dùng.

3. Multi-Level Queue Scheduling

Phân cấp giai cấp:

• Hàng 1 (Ưu tiên cao - System Process): Dùng Round Robin (cần phản hồi nhanh).
• Hàng 2 (Ưu tiên thấp - Batch Job): Dùng FCFS (xử lý nền).

Nếu Hàng 1 còn việc -> Hàng 2 phải nhịn (Starvation). Giải quyết bằng Aging (Càng đợi lâu càng lên chức).