Một cách đơn giản để phân phối các yêu cầu của máy khách trên một nhóm máy chủ, các yêu cầu của khách hàng lần lượt chuyển tiếp đến từng máy chủ, đây được gọi là Round Robin.
Round Robin là gì?
Round Robin là một giải thuật định thời CPU. Trong một chu kỳ, mỗi tiến trình được gán một thời gian giữ CPU nhất định.
Round Robin xuất phát từ nguyên tắc vòng tròn, lần lượt mỗi người sẽ nhận được một phần bằng nhau của một thứ gì đó. Giải thuật Round Robin cung cấp khả năng thực thi các quy trình miễn phí.
Những đặc điểm quan trọng của giải thuật Round Robin
Đây là một giải thuật ưu tiên, nằm trong danh mục giải thuật mở đầu. Round Robin được đánh giá là một trong những giải thuật đơn giản nhất, tồn tại lâu đời nhất và tiêu thức tính toán công bằng nhất. Trong giải thuật Round Robin, khoảng thời gian phải đặt ở mức tối thiểu gán cho một tác vụ cụ thể cần được xử lý. Tuy nhiên có thể khác nhau về các hệ điều hành.
Giải thuật được phát triển theo mô hình Hybrid và điều khiển bằng đồng hồ trong tự nhiên. Round Robin cần sử dụng thời gian thực, các khoản hồi sẽ được giới hạn trong một khoản thời gian cụ thể. Hầu hết các hệ điều hành truyền thống điều sử dụng phương pháp lập lịch này.
Các điều kiện quan trọng được sử dụng trong giải thuật Round Robin
- Thời gian hoàn thành: Là thời gian mà bất kỳ quá trình nào cũng cần hoàn thành công việc thực hiện.
- Thời gian quay vòng: Dùng để phân biệt giữa thời gian hoàn thành và thời gian đến. Sử dụng công thức: [Thời gian quay vòng = Thời gian hoàn thành – Thời gian đến].
- Thời gian chờ: Dùng để phân biệt giữa thời gian quay vòng và thời gian liên tục. Sử dụng công thức: [Thời gian chờ = Thời gian quay vòng – Thời gian nổ].
Giải thuật Round Robin
- Đầu tiên có một hàng đợi trong đó các quy trình được sắp xếp theo thứ tự đến trước xử lý trước.
- Mỗi giá trị lượng tử được cấp phát để thực hiện mỗi quá trình.
- Quá trình đầu tiên được thực hiện cho đến khi kết thúc giá trị lượng tử. Sau đó, mỗi ngắt được tạo ra và trạng thái được lưu.
- CPU chuyển sang quy trình tiếp theo, phương pháp cũng tượng tự và được thực hiện theo.
- Các bước tương tự được lặp lại cho đến khi kết thúc quá trình.
Ưu – nhược điểm của giải thuật Round Robin
Ưu điểm
- Với sự hỗ trợ của Round Robin giúp các công việc phân bổ cho CPU được phân bổ hợp lý.
- Tất cả các quy trình đều được xử lý mà không có bất kỳ ưu tiên nào.
- Giải thuật mang lại hiệu suất tốt cho thời gian phản hồi trung bình
- Trong giải thuật không gặp phải các vấn đề thiếu hụt hay hiệu ứng bảo vệ.
- Round Robin không mang tính chu kỳ.
- Thêm các quy trình mới tạo vào cuối hàng đợi.
- Khi thực hiện, một lượng tử thời gian cụ thể được phân bổ cho các công việc khác nhau.
- Mỗi quá trình sẽ có cơ hội lên lịch lại sau một thời gian lượng tử cụ thể.
- Một bộ lập lịch vòng tròn thường sử dụng tính năng chia sẻ thời gian. Điều này có nghĩa là cung cấp cho mỗi công việc một khe thời gian hoặc lượng tử.
Nhược điểm
- Nếu thời gian ngắt của hệ điều hành thấp, đầu ra của bộ xử lý sẽ bị giảm.
- Hiệu suất bị phụ thuộc nhiều vào lượng tử thời gian.
- Không ưu tiên cho những việc quan trọng khi lập lịch vòng tròn.
- Phương pháp này mất nhiều thời gian cho việc chuyển đổi ngữ cảnh.
- Lượng tử thời gian thấp nên dẫn đến quá trình chuyển đổi ngữ cảnh trong hệ thống cao hơn.
- Trở ngại trong việc tìm một lượng tử thời gian chính xác.
- Không đặt được mức độ ưu tiên.
- Khả năng hiểu suy giảm.
Một số điểm cần lưu ý về giải thuật Round Robin
Tăng giá trị của lượng tử thời gian
Với giá trị ngày càng tăng của lượng tử thời gian, khiến cho số lượng chuyển đổi ngữ cảnh giảm, thời gian phản hồi sẽ tăng lên và tỷ lệ thiếu hụt sẽ tăng trong trường hợp này. Đối với giá trị cao hơn của lượng tử thời gian, Round Robin trở nên tốt hơn về số lượng chuyển đổi ngữ cảnh.
Giảm giá trị của lượng tử thời gian
Với giá trị giảm dần của lượng tử thời gian, khiến cho số lượng chuyển đổi ngữ cảnh tăng, thời gian phản hồi sẽ giảm và tỷ lệ thiếu hụt sẽ giảm trong trường hợp này. Đối với giá trị nhỏ hơn của lượng tử thời gian, Round Robin trở nên tốt hơn về thời gian phản hồi.
Hiệu suất của Round Robin
Hiệu suất của lập lịch Round Robin chủ yếu phụ thuộc vào giá trị của lượng tử thời gian. Giá trị lượng tử thời gian phải cân chỉnh để không quá lớn và cũng không quá nhỏ.
Lập lịch FCFS
Nếu giá trị lượng tử thời gian đang tăng lên thì Round Robin có xu hướng trở thành lập lịch FCFS.
Round Robin được đánh giá như thế nào?
Round Robin được đánh giá là một giải thuật cơ bản, sử dụng khá đơn giản, được chứng minh về mặt toán học. Đây là một cách tiếp cận phù hợp.
Khi so sánh với một giải thuật tham lam (Greedy Algorithm), có thể thấy các quy trình có thể không bao giờ hoàn thành với hiệu suất tốt hơn lập tức. Về trường hợp Round Robin, mặc dù hiệu suất tổng thể có thể kém nhưng luôn đảm bảo mọi thứ điều hoàn thành
Đây là một cách tiếp cận quan trọng vì nó cho thấy các giải thuật cơ bản được thiết kế như thế nào. Áp dụng cách tiếp cận này trong những lĩnh vực khác để hiểu biết thêm những khái niệm mới.
Round Robin là một trong những giải thuật được sử dụng phổ biến trong các hệ điều hành để điều phối hoạt động tiến trình. Round Robin nổi trội ở điểm là tạo ra sự công bằng cho các tiến trình khi chạy. Nhưng cũng có mặt hạn chế vì phụ thuộc thời gian xoay vòng của các tiến trình.
Nếu nghiên cứu và có sự hiểu biết sâu về Round Robin, các nhà phát triển sẽ biết cách cải tiến và phát triển nó ngày càng trở nên hữu ích.
Một số câu hỏi thường gặp về Round Robin
Burst Time là gì?
Đây là thời gian cần thiết của CPU để hoàn thành quá trình thực hiện của nó.
Thời gian chờ là gì?
Tổng thời gian mà một quy trình dành cho hàng đợi sẵn.
Thời gian quay vòng là gì?
Khoảng thời gian giữa thời điểm gửi quy trình đến thời điểm hoàn thành
Thời gian lượng tử là gì?
Là lượng thời gian CPU được chỉ định để thực thi được gọi là thời gian lượng tử độc lập với thời gian bùng nổ thực tế, một quá trình sẽ được lên lịch trong các giá trị phần lượng tử hoặc có thể theo khối lượng tử.
