Round Robin (RR) là một thuật toán lập lịch CPU ưu tiên trong đó mỗi quy trình được phân bổ một lát thời gian cố định gọi là lượng tử. Không giống như Round Robin tiêu chuẩn có thời gian đến bằng 0, biến thể này xử lý các quy trình đến vào các thời điểm khác nhau, khiến việc lập lịch trình trở nên phức tạp hơn khi hàng đợi sẵn sàng thay đổi linh hoạt.
Trong lập lịch ưu tiên, một tiến trình đang chạy có thể bị gián đoạn và chuyển trở lại hàng đợi sẵn sàng. Round Robin đảm bảo tính công bằng bằng cách dành cho mỗi quy trình một phần thời gian CPU bằng nhau, ngăn chặn tình trạng thiếu hụt trong khi vẫn duy trì thời gian phản hồi tốt cho các hệ thống tương tác.
Cách hoạt động của Round Robin với thời gian đến khác nhau
Khi các tiến trình có thời gian đến khác nhau, thuật toán sẽ thực hiện theo các bước sau:
-
Các tiến trình vào hàng đợi sẵn sàng dựa trên thời gian đến của chúng
-
CPU phục vụ quy trình khả dụng đầu tiên trong khoảng thời gian lượng tử
-
Nếu quá trình hoàn tất trong lượng tử thì nó sẽ kết thúc
-
Nếu chưa hoàn thành, nó sẽ di chuyển về cuối hàng đợi sẵn sàng
-
Những người mới đến hãy xếp hàng sẵn sàng và chờ đến lượt của mình
-
Chuyển đổi ngữ cảnh lưu trạng thái của các tiến trình được ưu tiên
Các tính năng chính
-
Ngăn chặn tình trạng đói Mọi tiến trình cuối cùng đều có thời gian CPU
-
Lập kế hoạch hợp lý Lượng thời gian bằng nhau cho tất cả các quy trình
-
Thời gian phản hồi tốt Phù hợp với hệ thống tương tác và thời gian thực
-
Chi phí chuyển đổi bối cảnh Lượng tử nhỏ hơn làm tăng chi phí chuyển đổi
Ví dụ 1 Thời gian lượng tử =2
Hãy xem xét ba quy trình có thời gian đến và thời gian bùng nổ khác nhau:
Biểu đồ Gantt? Vòng tròn (Lượng tử =2) P1 P2 P3 P1 P2 P3 0 2 4 6 8 9 14
Thực hiện từng bước
Tính thời gian trung bình
Thời gian quay vòng trung bình =(8 + 8 + 12) / 3 =9,33 đơn vị
Thời gian chờ trung bình =(4 + 5 + 5) / 3 =4,67 đơn vị
Ví dụ 2 Thời gian lượng tử =4
Với kích thước lượng tử lớn hơn:
Biểu đồ Gantt? Robin tròn (Lượng tử =4) P2 P3 P1 P2 P3 P1 0 4 8 12 15 20 24
Thời gian quay vòng trung bình =(22 + 15 + 19) / 3 =18,67 đơn vị
Thời gian chờ trung bình =(14 + 8 + 10) / 3 =10,67 đơn vị
Kết luận
Lập lịch Round Robin với thời gian đến khác nhau cung cấp sự phân bổ CPU hợp lý trong khi xử lý các lượt đến của quy trình động. Kích thước lượng tử ảnh hưởng đáng kể đến hiệu suất? lượng tử nhỏ hơn cải thiện thời gian phản hồi nhưng tăng chi phí chuyển đổi ngữ cảnh, trong khi lượng tử lớn hơn có thể làm giảm tính công bằng nhưng cải thiện thông lượng.
