Round Robin (RR) là thuật toán lập lịch CPU ưu tiên (preemptive) nơi mỗi tiến trình được cấp một đoạn thời gian cố định gọi là quantum. Khác với Round Robin chuẩn với thời gian đến bằng 0, biến thể này xử lý tiến trình đến lúc khác nhau, làm lập lịch phức tạp hơn vì hàng đợi sẵn sàng thay đổi động.
Trong lập lịch ưu tiên, tiến trình đang chạy có thể bị ngắt và chuyển về hàng đợi sẵn sàng. Round Robin đảm bảo công bằng bằng cách cho mỗi tiến trình phần thời gian CPU như nhau, ngăn chặn đói (starvation) trong khi giữ thời gian phản hồi tốt cho hệ thống tương tác.
Cách Round Robin Hoạt Động Với Thời Gian Đến Khác Nhau
Khi tiến trình có thời gian đến khác nhau, thuật toán theo các bước:
- Tiến trình vào hàng đợi sẵn sàng dựa trên thời gian đến
- CPU phục vụ tiến trình sẵn sàng đầu tiên trong thời gian quantum
- Nếu tiến trình hoàn thành trong quantum, nó kết thúc
- Nếu không xong, nó chuyển cuối hàng đợi sẵn sàng
- Tiến trình mới đến tham gia hàng đợi và chờ lượt
- Chuyển ngữ cảnh (context switching) lưu trạng thái tiến trình bị ưu tiên
Đặc Điểm Chính
- Ngăn chặn đói: Mọi tiến trình cuối cùng đều có thời gian CPU
- Lập lịch công bằng: Quantum thời gian bằng nhau cho tất cả tiến trình
- Thời gian phản hồi tốt: Phù hợp hệ thống tương tác và real-time
- Chi phí chuyển ngữ cảnh: Quantum nhỏ tăng chi phí chuyển đổi
Ví Dụ 1 Quantum = 2
Xét ba tiến trình với thời gian đến và burst khác nhau:
| Tiến trình | Thời gian đến | Burst Time |
|---|---|---|
| P1 | 0 | 4 |
| P2 | 1 | 3 |
| P3 | 2 | 7 |
Biểu đồ Gantt — Round Robin (Quantum = 2)
P1 P2 P3 P1 P2 P3
0 2 4 6 8 9 14
Thực Thi Bước Đi Bước
| Thời gian | Tiến trình | Hàng đợi sẵn sàng | Hành động |
|---|---|---|---|
| 0-2 | P1 | P1 | P1 chạy 2 đơn vị, P2 đến t=1 |
| 2-4 | P2 | P2, P1 | P2 chạy 2 đơn vị, P3 đến t=2 |
| 4-6 | P3 | P3, P1 | P3 chạy 2 đơn vị |
| 6-8 | P1 | P1, P2, P3 | P1 hoàn thành 2 đơn vị còn lại |
| 8-9 | P2 | P2, P3 | P2 hoàn thành 1 đơn vị còn lại |
| 9-14 | P3 | P3 | P3 hoàn thành 5 đơn vị còn lại |
Tính Thời Gian Trung Bình
| Tiến trình | Đến | Burst | Hoàn thành | Turnaround | Waiting |
|---|---|---|---|---|---|
| P1 | 0 | 4 | 8 | 8 | 4 |
| P2 | 1 | 3 | 9 | 8 | 5 |
| P3 | 2 | 7 | 14 | 12 | 5 |
Thời gian Turnaround trung bình = (8 + 8 + 12) / 3 = 9,33 đơn vị
Thời gian Waiting trung bình = (4 + 5 + 5) / 3 = 4,67 đơn vị
Ví Dụ 2 Quantum = 4
Với quantum lớn hơn:
| Tiến trình | Thời gian đến | Burst Time |
|---|---|---|
| P1 | 2 | 8 |
| P2 | 0 | 7 |
| P3 | 1 | 9 |
Biểu đồ Gantt — Round Robin (Quantum = 4)
P2 P3 P1 P2 P3 P1
0 4 8 12 15 20 24
| Tiến trình | Đến | Burst | Hoàn thành | Turnaround | Waiting |
|---|---|---|---|---|---|
| P1 | 2 | 8 | 24 | 22 | 14 |
| P2 | 0 | 7 | 15 | 15 | 8 |
| P3 | 1 | 9 | 20 | 19 | 10 |
Thời gian Turnaround trung bình = (22 + 15 + 19) / 3 = 18,67 đơn vị
Thời gian Waiting trung bình = (14 + 8 + 10) / 3 = 10,67 đơn vị
Kết Luận
Round Robin với thời gian đến khác nhau cung cấp phân bổ CPU công bằng trong khi xử lý đến động của tiến trình. Kích thước quantum ảnh hưởng đáng kể hiệu năng — quantum nhỏ cải thiện thời gian phản hồi nhưng tăng chi phí chuyển ngữ cảnh, quantum lớn có thể giảm công bằng nhưng cải thiện throughput.
