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.
Xem thêm Kiểm tra lỗ hổng bảo mật Session Timeout
Những câu hỏi phổ biến về thuật toán Round Robin trong Hệ điều hành
- Thuật toán Round Robin là gì?
Thuật toán Round Robin là một trong những thuật toán lập lịch CPU phổ biến nhất trong hệ thống điều khiển lập lịch CPU. Thuật toán này phân chia thời gian CPU thành các đoạn nhỏ, gọi là quantum, và sau đó lập lịch các tiến trình theo trình tự quay vòng, mỗi tiến trình được chạy trong một quantum.
- Round Robin hoạt động như thế nào?
Thuật toán Round Robin hoạt động bằng cách lập lịch các tiến trình trong một danh sách. Mỗi tiến trình được chạy trong một khoảng thời gian được xác định trước gọi là quantum. Khi quantum kết thúc, tiến trình sẽ được đưa lại vào danh sách và tiến trình tiếp theo sẽ được chạy. Quá trình này tiếp tục đến khi tất cả các tiến trình hoàn thành.
- Lợi ích của việc sử dụng Round Robin trong hệ điều hành là gì?
Các lợi ích của việc sử dụng thuật toán Round Robin trong hệ điều hành bao gồm:
- Cải thiện thời gian phản hồi cho người dùng: Do các tiến trình được lập lịch theo trình tự quay vòng, nên thời gian chờ đợi giữa các tiến trình là ngắn, giúp cải thiện thời gian phản hồi cho người dùng.
- Cải thiện độ ưu tiên cho các tiến trình: Vì các tiến trình được chạy theo trình tự quay vòng, nên các tiến trình có thể chạy liên tục mà không bị ưu tiên quá mức so với các tiến trình khác.
- Cải thiện tính công bằng: Các tiến trình được chạy theo trình tự quay vòng, giúp đảm bảo tính công bằng cho các tiến trình và tránh tình trạng một số tiến trình bị đẩy sang sau và không được chạy trong một khoảng thời gian dài.
- Nhược điểm của Round Robin là gì?
Nhược điểm của thuật toán Round Robin bao gồm:
- Chi phí thời gian đáp ứng: Do tiến trình phải chờ đợi cho đến khi quantum của nó đến, nên thời gian đáp ứng của các tiến trình có thể bị giảm.
- Hiệu suất CPU: Nếu quantum được đặt quá lớn, thì một số tiến trình có thể chạy trong một thời gian dài
- Làm thế nào để chọn kích thước quantum phù hợp trong Round Robin?
Việc chọn kích thước quantum phù hợp là rất quan trọng trong Round Robin. Nếu quantum quá nhỏ, thì hệ thống sẽ phải chuyển đổi tiến trình quá thường xuyên, dẫn đến lãng phí tài nguyên CPU. Nếu quantum quá lớn, thì thời gian đáp ứng của tiến trình có thể bị giảm và tính công bằng của hệ thống cũng có thể bị ảnh hưởng. Thông thường, kích thước quantum được chọn khoảng từ 10ms đến 100ms, tùy thuộc vào các yêu cầu của hệ thống cụ thể.
- Round Robin và các thuật toán lập lịch CPU khác có gì khác biệt?
Round Robin là một trong những thuật toán lập lịch CPU phổ biến nhất. So với các thuật toán lập lịch khác, như FCFS (First-Come, First-Served) và SJF (Shortest Job First), Round Robin có thể cải thiện thời gian đáp ứng của hệ thống, đảm bảo tính công bằng và ưu tiên cho các tiến trình. Tuy nhiên, Round Robin cũng có nhược điểm của nó, ví dụ như chi phí thời gian đáp ứng cao và hiệu suất CPU giảm nếu kích thước quantum quá lớn.
- Khi nào nên sử dụng Round Robin?
Round Robin là một thuật toán lập lịch CPU phổ biến và thường được sử dụng trong hệ thống đa nhiệm. Nó phù hợp cho các hệ thống yêu cầu tính công bằng và ưu tiên cho các tiến trình, cũng như cải thiện thời gian đáp ứng cho người dùng. Tuy nhiên, nếu hệ thống yêu cầu thời gian đáp ứng rất nhanh hoặc có các tiến trình ưu tiên đặc biệt, thì Round Robin có thể không phù hợp và cần phải sử dụng các thuật toán lập lịch khác để đáp ứng yêu cầu của hệ thống.
- Làm thế nào để đảm bảo tính công bằng trong Round Robin?
Để đảm bảo tính công bằng trong Round Robin, mỗi tiến trình được cấp một lượng thời gian CPU bằng nhau. Khi tiến trình được lập lịch, nó sẽ được chạy trong một khoảng thời gian nhỏ (quantum) trước khi chuyển sang tiến trình khác. Các tiến trình được lập lịch theo thứ tự đến lượt, vì vậy nếu một tiến trình không thể hoàn thành trong quantum được cấp, nó sẽ được chuyển đến cuối danh sách lập lịch và phải chờ đến khi nó được chạy lại.
- Round Robin có nhược điểm gì?
Mặc dù Round Robin là một thuật toán lập lịch CPU phổ biến và hiệu quả trong nhiều trường hợp, nó cũng có nhược điểm của nó. Đối với các tiến trình yêu cầu sử dụng CPU liên tục trong một khoảng thời gian dài, Round Robin sẽ tốn nhiều thời gian để chuyển đổi giữa các tiến trình, dẫn đến lãng phí tài nguyên CPU. Nếu kích thước quantum được chọn quá lớn, thời gian đáp ứng của hệ thống cũng có thể bị ảnh hưởng.
- Làm thế nào để cải thiện hiệu suất của Round Robin?
Để cải thiện hiệu suất của Round Robin, có thể áp dụng các kỹ thuật như tối ưu hóa kích thước quantum và sử dụng các biến thể của Round Robin, ví dụ như Round Robin với ưu tiên (Priority Round Robin) hoặc Round Robin có thời gian chờ đợi (Wait-Time Round Robin). Ngoài ra, việc tối ưu hóa các tiến trình và ưu tiên các tiến trình quan trọng cũng có thể giúp cải thiện hiệu suất của Round Robin.
