Round Robin là gì? Đặc điểm của thuật toán lập lịch

Với những tính năng tuyệt vời thuật toán lập lịch Round-Robin có thể được triển khai ở tất cả các hệ điều hành. Trong bài viết dưới đây, BKHOST sẽ thông tin tổng quan về khái niệm, đặc điểm của Round-Robin và những ví dụ điển hình.

Round-Robin là gì?

Tên gọi của thuật toán Round-Robin có nguồn gốc từ chính nguyên tắc quay vòng. Round-Robin được đánh giá là một trong những thuật toán lập lịch đơn giản và có tuổi đời cao nhất. Với thuật toán này lần lượt mỗi tác vụ sẽ được chạy trong một hàng đợi với giới hạn thời gian cụ thể. Khả năng thực thi của thuật toán liên tục, tuần hoàn.

Đặc điểm của thuật toán Round-Robin

Thuật toán lập lịch Round-Robin sở hữu những đặc điểm quan trọng như:

• Round-Robin là giải thuật ưu tiên.
• Sau khoảng thời gian cố định CPU sẽ được chuyển sang quy trình tiếp theo.
• Ở cuối hàng đợi thêm các quy trình mới tạo.
• Round-Robin được điều khiển bằng đồng hồ tự nhiên.
• Thời gian để xử lý một tác vụ cụ thể phải đặt ở mức tối thiểu. Và điều này có thể khác nhau ở mỗi hệ điều hành.
• Các sự kiện ở thuật toán này đều được giới hạn trong một khoảng thời gian cụ thể.
• Công bằng, dễ dàng, lâu đời và được sử dụng rộng rãi ở các hệ điều hành truyền thống là những điểm nổi bật của Round-robin.

Ví dụ về lập kế hoạch Round-robin

Lập kế hoạch Round –robin được diễn ra theo các bước sau:

Bước 1: Quy trình P1 bắt đầu được thực thi với thời gian bắt đầu là 4 trong khi đó P2 và P3 đang ở hàng đợi. Mỗi quy trình này đều diễn ra trong khoảng thời gian là 2s.

Bước 2: P1 sẽ được thêm vào cuối hàng đợi khi at time = 2 và lúc này P2 được thực thi.

Bước 3: P3 được thực thi và P2 được thêm vào cuối hàng đợi khi at time = 4.

Bước 4: P1 được thực thi khi at time = 6 và P3 lại thêm vào cuối hàng đợi.

Bước 5: Thời gian nổ của P1 là 4 vì thế khi at time = 8 thì P1 hoàn thành việc thực thi, kế tiếp sẽ là P2.

Bước 6: Thời gian nổ của P2 là 3 như vậy khi at time = 9 P2 sẽ thực thi xong, quá trình thực thi P3 bắt đầu cho đến khi hoàn thành.

Bước 7: Thời gian chờ trung bình của ví dụ trên được tính như dưới đây:

Thời gian chờ đợi:

• P1= 0+ 4= 4
• P2= 2+4= 6
• P3= 4+3= 7

Ưu và nhược điểm của lập kế hoạch Round-Robin

Ưu điểm

• Phân bổ công việc cho CPU hợp lý, không xảy ra vấn đề ùn tắc hoặc thời gian chết.
• Tất cả các quy trình đều được xử lý mà không có bất cứ ưu tiên nào.
• Round-robin được thực hiện dễ dàng trên hệ thống vì không phụ thuộc vào thời gian nổ.
• Bạn sẽ giả định được thời gian phản hồi của quy trình khi biết tổng số quy trình đang ở trên hàng đợi.
• Trong một khoảng thời gian cụ thể nếu một quy trình được thực thi thì quy trình đó sẽ được ưu tiên. Và trong khoảng thời gian nhất định đó một quy trình khác sẽ được thực thi.
• Trạng thái của các quy trình được ưu tiên sẽ được hệ điều hành sử dụng phương thức Chuyển đổi ngữ cảnh để lưu lại.
• Thời gian phản hồi trùng bình nhanh, kịp thời.

Nhược điểm

• Đầu ra của bộ xử lý giảm khi thời gian cắt của hệ điều hành thấp.
• Việc chuyển đổi ngữ cảnh ở Round-robin tốn khá nhiều thời gian.
• Lượng tử thời gian ảnh hưởng lớn đến hiệu suất của thuật toán Round-robin.
• Các quy trình và những nhiệm vụ quan trọng không được ưu tiên.
• Trong hệ thống này vấn đề tìm một lượng tử thời gian chính xác là nhiệm vụ nan giải.
• Chi phí chuyển ngữ cảnh cao và suy giảm khả năng hiểu.

Độ trễ trường hợp xấu nhất (Worst Case Latency)

Thời gian tối đa để thực hiện xong xuôi mọi nhiệm vụ được biểu thị bằng thuật ngữ Worst Case Latency, trong đó:

• dt = thời gian phát hiện ra tác vụ.
• st = thời gian chuyển đổi giữa các nhiệm vụ.
• et = thời gian để thực hiện trọn vẹn tác vụ.

Công thức:

{{EJS0}}

Tổng kết về Round-Robin