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.
Tóm tắt nội dung
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. Thời gian đến và thời gian bùng nổ 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ị.
| Xử lý ID | Thời gian đến | Thời gian bùng nổ |
| 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 thời gian bùng nổ 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 thời gian bùng nổ 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.
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. Thời gian bùng nổ 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.
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ị thời gian bùng nổ. 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 thời gian bùng nổ 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ị thời gian bùng nổ 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ị thời gian bùng nổ 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ị thời gian bùng nổ. 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 |
Biểu đồ Gantt
P5 sẽ được thực thi cho đến khi hoàn thành.
Thời gian hoàn thành, thời gian quay vòng và thời gian chờ sẽ được tính như bảng dưới đây.
Như chúng ta biết,
- Thời gian quay vòng = Thời gian hoàn thành – Thời gian đến
- Thời gian chờ = Thời gian quay vòng – Thời gian liên tục
| Xử lý ID | Thời gian đến | Thời gian bùng nổ | Thời gian hoàn thành | Thời gian quay vòng | Thời gian chờ |
| 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 |
Thời gian chờ 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 thời gian bùng nổ.
- 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.