Thuật toán lập lịch Round Robin là một trong những thuật toán lập lịch phổ biến nhất mà nó thực sự có thể được triển khai trong hầu hết các hệ điều hành. Đây là phiên bản ưu tiên của lập lịch phục vụ đến trước. Thuật toán tập trung vào Chia sẻ thời gian. Trong thuật toán này, mọi quy trình được thực thi theo một cách tuần hoàn.
Các bài viết liên quan:
Một lát thời gian nhất định được xác định trong hệ thống được gọi là lượng tử thời gian . Mỗi tiến trình hiện diện trong hàng đợi sẵn sàng được gán cho CPU lượng tử thời gian đó, nếu quá trình thực thi được hoàn thành trong thời gian đó thì quá trình sẽ kết thúc nếu không quá trình sẽ quay lại hàng đợi sẵn sàng và đợi lượt tiếp theo hoàn thành việc thực hiện.
Ví dụ về lập lịch RR
Trong ví dụ sau, có sáu quy trình được đặt tên là P1, P2, P3, P4, P5 và P6. Arrival Time và Burst Time của chúng được đưa ra dưới đây trong bảng. Lượng tử thời gian của hệ là 4 đơn vị.
| Process ID | Arrival Time | Burst Time |
| 1 | 0 | 5 |
| 2 | 1 | 6 |
| 3 | 2 | 3 |
| 4 | 3 | 1 |
| 5 | 4 | 5 |
| 6 | 6 | 4 |
Theo thuật toán, chúng ta phải duy trì hàng đợi sẵn sàng và biểu đồ Gantt. Cấu trúc của cả hai cấu trúc dữ liệu sẽ được thay đổi sau mỗi lần lập lịch.
Xem thêm Kiểm tra lỗ hổng bảo mật Process Timing
Hàng đợi sẵn sàng:
Ban đầu, tại thời điểm 0, quá trình P1 đến sẽ được lên lịch cho lát thời gian 4 đơn vị. Do đó trong hàng đợi sẵn sàng, sẽ chỉ có một quá trình P1 khi bắt đầu với Burst Time của CPU là 5 đơn vị.
| P1 |
| 5 |
Biểu đồ Gantt
P1 sẽ được thực hiện cho 4 đơn vị đầu tiên.
Hàng đợi sẵn sàng
Trong khi thực thi P1, bốn quy trình nữa P2, P3, P4 và P5 sẽ đến trong hàng đợi sẵn sàng. P1 vẫn chưa hoàn thành, nó cần thêm 1 đơn vị thời gian do đó nó cũng sẽ được thêm trở lại hàng đợi sẵn sàng.
| P2 | P3 | P4 | P5 | P1 |
| 6 | 3 | 1 | 5 | 1 |
Biểu đồ Gantt
Sau P1, P2 sẽ được thực hiện trong 4 đơn vị thời gian được hiển thị trong biểu đồ Gantt.
Hàng đợi sẵn sàng
Trong quá trình thực thi P2, một tiến trình nữa P6 được đưa vào hàng đợi sẵn sàng. Vì P2 vẫn chưa hoàn thành nên P2 cũng sẽ được thêm trở lại hàng đợi sẵn sàng với Burst Time còn lại là 2 đơn vị.
| P3 | P4 | P5 | P1 | P6 | P2 |
| 3 | 1 | 5 | 1 | 4 | 2 |
Biểu đồ Gantt
Sau P1 và P2, P3 sẽ được thực thi trong 3 đơn vị thời gian vì thời gian nổ CPU của nó chỉ là 3 giây.
Xem thêm Time trong Go
Hàng đợi sẵn sàng
Vì P3 đã được hoàn thành, do đó nó sẽ bị kết thúc và không được thêm vào hàng đợi sẵn sàng. Quá trình tiếp theo sẽ được thực hiện là P4.
| P4 | P5 | P1 | P6 | P2 |
| 1 | 5 | 1 | 4 | 2 |
Biểu đồ Gantt
Sau đó, P1, P2 và P3, P4 sẽ được thực thi. Burst Time của nó chỉ là 1 đơn vị nhỏ hơn lượng tử thời gian do đó nó sẽ được hoàn thành.
Xem thêm Complete Graph – đồ thị hoàn chỉnh
Hàng đợi sẵn sàng
Quá trình tiếp theo trong hàng đợi sẵn sàng là P5 với 5 đơn vị Burst Time. Vì P4 đã hoàn thành nên nó sẽ không được thêm trở lại hàng đợi.
| P5 | P1 | P6 | P2 |
| 5 | 1 | 4 | 2 |
Biểu đồ Gantt
P5 sẽ được thực hiện trong toàn bộ lát thời gian vì nó yêu cầu 5 đơn vị thời gian liên tục cao hơn lát thời gian.
Hàng đợi sẵn sàng
P5 vẫn chưa được hoàn thành; nó sẽ được thêm trở lại hàng đợi với Burst Time còn lại là 1 đơn vị.
| P1 | P6 | P2 | P5 |
| 1 | 4 | 2 | 1 |
Biểu đồ Gantt
Quá trình P1 sẽ được đưa ra lượt tiếp theo để hoàn thành quá trình thực thi của nó. Vì nó chỉ yêu cầu 1 đơn vị Burst Time nên nó sẽ được hoàn thành.
Hàng đợi sẵn sàng
P1 đã hoàn thành và sẽ không được thêm trở lại hàng đợi sẵn sàng. Quá trình tiếp theo P6 chỉ yêu cầu 4 đơn vị Burst Time và nó sẽ được thực hiện tiếp theo.
| P6 | P2 | P5 |
| 4 | 2 | 1 |
Biểu đồ Gantt
P6 sẽ được thực hiện trong 4 đơn vị thời gian cho đến khi hoàn thành.
Hàng đợi sẵn sàng
Vì P6 đã hoàn thành, do đó nó sẽ không được thêm lần nữa vào hàng đợi. Chỉ có hai quy trình hiện diện trong hàng đợi sẵn sàng. Quá trình tiếp theo P2 chỉ yêu cầu 2 đơn vị thời gian.
| P2 | P5 |
| 2 | 1 |
Biểu đồ Gantt
P2 sẽ được thực thi lại, vì nó chỉ yêu cầu 2 đơn vị thời gian do đó quá trình này sẽ được hoàn thành.
Hàng đợi sẵn sàng
Bây giờ, quy trình khả dụng duy nhất trong hàng đợi là P5 yêu cầu 1 đơn vị Burst Time. Vì khoảng thời gian là 4 đơn vị nên nó sẽ được hoàn thành trong lần bắn tiếp theo.
| P5 |
| 1 |
Xem thêm Lập kế hoạch Shortest Job First (SJF)
Biểu đồ Gantt
P5 sẽ được thực thi cho đến khi hoàn thành.
Completion Time, Turn Around Time và Waiting Time sẽ được tính như bảng dưới đây.
Như chúng ta biết,
- Turn Around Time = Completion Time – Arrival Time
- Waiting Time = Turn Around Time – Burst Time
| Process ID | Arrival Time | Burst Time | Completion Time | Turn Around Time | Waiting Time |
| 1 | 0 | 5 | 17 | 17 | 12 |
| 2 | 1 | 6 | 23 | 22 | 16 |
| 3 | 2 | 3 | 11 | 9 | 6 |
| 4 | 3 | 1 | 12 | 9 | số 8 |
| 5 | 4 | 5 | 24 | 20 | 15 |
| 6 | 6 | 4 | 21 | 15 | 11 |
Waiting Time trung bình = (12 + 16 + 6 + 8 + 15 + 11) / 6 = 76/6 đơn vị
Thuận lợi
- Nó thực sự có thể thực hiện được trong hệ thống vì nó không phụ thuộc vào Burst Time.
- Nó không bị vấn đề chết đói hay hiệu ứng đoàn xe.
- Tất cả các công việc được phân bổ giá vé của CPU.
Nhược điểm
- Lượng tử thời gian càng cao thì thời gian phản hồi trong hệ thống càng cao.
- Lượng tử thời gian càng thấp, chi phí chuyển đổi ngữ cảnh trong hệ thống càng cao.
- Quyết định một lượng tử thời gian hoàn hảo thực sự là một nhiệm vụ rất khó khăn trong hệ thống.
