Thuật toán lập kế hoạch Round Robin với ví dụ

Lập kế hoạch Round-Robin là gì?

Tên của thuật toán này xuất phát từ nguyên tắc quay vòng, trong đó mỗi người lần lượt nhận được phần bằng nhau của một thứ gì đó. Đây là thuật toán lập lịch đơn giản nhất, lâu đời nhất, chủ yếu được sử dụng cho đa nhiệm.

Trong lập lịch vòng tròn, mỗi tác vụ sẵn sàng chỉ chạy lần lượt trong hàng đợi tuần hoàn trong một khoảng thời gian giới hạn. Thuật toán này cũng cung cấp khả năng thực thi các quy trình không bị đói.

Đặc điểm của lập kế hoạch Round-Robin

Dưới đây là các đặc điểm quan trọng của Lập kế hoạch vòng tròn:

Round robin là một thuật toán ưu tiên
CPU được chuyển sang quy trình tiếp theo sau khoảng thời gian cố định, được gọi là lượng tử thời gian/lát cắt thời gian.
Quá trình được ưu tiên sẽ được thêm vào cuối hàng đợi.
Round robin là một mô hình kết hợp được điều khiển bằng đồng hồ
Khoảng thời gian phải ở mức tối thiểu, được chỉ định cho một nhiệm vụ cụ thể cần được xử lý. Tuy nhiên, nó có thể khác với hệ điều hành.
Đây là một thuật toán thời gian thực đáp ứng sự kiện trong một giới hạn thời gian cụ thể.
Round robin là một trong những thuật toán lâu đời nhất, công bằng nhất và dễ dàng nhất.
Phương pháp lập lịch được sử dụng rộng rãi trong hệ điều hành truyền thống.

Ví dụ về lập kế hoạch luân phiên

Hãy xem xét ba quá trình sau đây

Hàng đợi xử lý	Thời gian bùng nổ
P1	4
P2	3
P3	5

Bước 1) Quá trình thực thi bắt đầu với quy trình P1, có thời gian bùng nổ là 4. Ở đây, mọi quy trình thực thi trong 2 giây. P2 và P3 vẫn đang trong hàng đợi.

Bước 2) Tại thời điểm =2, P1 được thêm vào cuối Hàng đợi và P2 bắt đầu thực thi

Bước 3) Tại time=4 , P2 được ưu tiên và thêm vào cuối hàng đợi. P3 bắt đầu thực thi.

Bước 4) Tại time=6 , P3 được ưu tiên và thêm vào cuối hàng đợi. P1 bắt đầu thực thi.

Bước 5) Tại time=8 , P1 có thời gian bùng nổ là 4. Nó đã hoàn thành việc thực thi. P2 bắt đầu thực thi

Bước 6) P2 có thời gian bùng nổ là 3. Nó đã thực thi được 2 khoảng thời gian. Tại thời điểm = 9, P2 hoàn thành việc thực thi. Sau đó, P3 bắt đầu thực thi cho đến khi hoàn thành.

Bước 7) Hãy tính thời gian chờ trung bình cho ví dụ trên.

Wait time 
P1= 0+ 4= 4
P2= 2+4= 6
P3= 4+3= 7

Ưu điểm của việc lập kế hoạch luân phiên

Dưới đây là những ưu/lợi ích của phương pháp lập kế hoạch Round-robin:

Nó không phải đối mặt với các vấn đề về nạn đói hoặc hiệu ứng đoàn xe.
Tất cả các công việc đều được phân bổ CPU hợp lý.
Nó xử lý tất cả quá trình mà không có bất kỳ ưu tiên nào
Nếu bạn biết tổng số quy trình trên hàng đợi chạy thì bạn cũng có thể giả sử thời gian phản hồi trong trường hợp xấu nhất cho cùng một quy trình.
Phương pháp lập lịch này không phụ thuộc vào thời gian bùng nổ. Đó là lý do tại sao nó có thể dễ dàng thực hiện trên hệ thống.
Khi một quy trình được thực thi trong một khoảng thời gian cụ thể, quy trình đó sẽ được ưu tiên và một quy trình khác sẽ thực thi trong khoảng thời gian nhất định đó.
Cho phép HĐH sử dụng phương thức Chuyển đổi ngữ cảnh để lưu trạng thái của các quy trình được ưu tiên.
Nó mang lại hiệu suất tốt nhất về thời gian phản hồi trung bình.

Nhược điểm của lập kế hoạch luân phiên

Dưới đây là những hạn chế/nhược điểm của việc sử dụng lập kế hoạch Round-robin:

Nếu thời gian cắt hệ điều hành thấp, hiệu suất xử lý sẽ giảm.
Phương pháp này dành nhiều thời gian hơn cho việc chuyển đổi ngữ cảnh
Hiệu suất của nó phụ thuộc rất nhiều vào lượng tử thời gian.
Không thể đặt mức độ ưu tiên cho các quy trình.
Lập kế hoạch luân phiên không ưu tiên đặc biệt cho những nhiệm vụ quan trọng hơn.
Giảm khả năng hiểu
Lượng tử thời gian thấp hơn dẫn đến chi phí chuyển đổi ngữ cảnh trong hệ thống cao hơn.
Tìm một lượng tử thời gian chính xác là một nhiệm vụ khá khó khăn trong hệ thống này.

Độ trễ trong trường hợp xấu nhất

Thuật ngữ này được sử dụng cho thời gian tối đa cần thiết để thực hiện tất cả các nhiệm vụ.

dt = Biểu thị thời gian phát hiện khi một tác vụ được đưa vào danh sách
st = Biểu thị thời gian chuyển đổi từ nhiệm vụ này sang nhiệm vụ khác
et = Biểu thị thời gian thực hiện nhiệm vụ

Công thức:

^T_worst = {(dt_i+ st_i+ et_i ), + (dt_i+ st_i+ et_i )₂ +...+ (dt_i+ st_i + et_i )_N., + (dt_i+ st_i + et_i  + et_i) N} + t_ISR	
t,_SR = sum of all execution times

Tổng kết

Tên của thuật toán này xuất phát từ nguyên tắc quay vòng, trong đó mỗi người lần lượt nhận được phần bằng nhau của một thứ gì đó.
Round robin là một trong những thuật toán lâu đời nhất, công bằng nhất và dễ dàng nhất và được sử dụng rộng rãi trong các phương pháp lập kế hoạch truyền thống. OS.
Round robin là một thuật toán ưu tiên
Ưu điểm lớn nhất của phương pháp lập lịch vòng tròn là nếu bạn biết tổng số quy trình trên hàng đợi chạy thì bạn cũng có thể giả sử thời gian phản hồi trong trường hợp xấu nhất cho cùng một quy trình.
Phương pháp này dành nhiều thời gian hơn cho việc chuyển đổi ngữ cảnh
Độ trễ trong trường hợp xấu nhất là thuật ngữ được sử dụng để chỉ thời gian tối đa cần thiết để thực hiện tất cả các tác vụ.

Bạn có thể thích: