Thuật toán lập lịch Round Robin với ví dụ

Lập lịch Round-Robin là gì?

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

Trong lập lịch Round-robin, mỗi tác vụ đã sẵn sàng chạy lần lượt chỉ trong một 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 miễn phí.

Trong hướng dẫn về Hệ điều hành này, bạn sẽ học:

• Lập lịch Round-Robin là gì?
• Đặc điểm của lập lịch vòng tròn
• Ví dụ về Lập lịch vòng tròn
• Lợi thế của việc lên lịch vòng tròn
• Nhược điểm của lập lịch vòng tròn
• Độ trễ trong trường hợp tồi tệ nhất

Đặc điểm của lập lịch vòng tròn

Dưới đây là các đặc điểm quan trọng của Lập lịch Vòng quanh:

• 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 thời gian.
• Quá trình được ưu tiên trước được thêm vào cuối hàng đợi.
• Round robin là một mô hình hybrid được điều khiển bằng đồng hồ
• Phần thời gian phải là 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 hệ điều hành với hệ điều hành.
• Nó là một thuật toán thời gian thực phản hồi 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 lịch vòng tròn

Hãy xem xét ba quy trình sau

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

Bước 1) Quá trình bắt đầu với quá trình P1, có thời gian bùng nổ là 4. Ở đây, mọi quá trình thực hiện 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 thời điểm = 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 thời điểm = 6, P3 được đặt trước và thêm vào cuối hàng đợi. P1 bắt đầu thực thi.

Bước 5) Tại thời điểm = 8, P1 có thời gian bùng nổ là 4. Nó đã hoàn tất quá trình thực thi. P2 bắt đầu thực hiện

Bước 6) P2 có thời gian bùng nổ là 3. Nó đã được thực thi trong 2 khoảng thời gian. Tại thời điểm = 9, P2 hoàn thành việc thực hiện. 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 timeP1= 0+ 4= 4P2= 2+4= 6P3= 4+3= 7

Lợi thế của việc lên lịch vòng tròn

Dưới đây là ưu / lợi ích của phương pháp lập lị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 của đoàn xe.
• Tất cả các công việc đều được phân bổ CPU hợp lý.
• Nó giải quyết tất cả cá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ố quá trình trên hàng đợi chạy, thì bạn cũng có thể giả định thời gian phản hồi trong trường hợp xấu nhất cho cùng một quá 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 trước 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 pháp Chuyển đổi ngữ cảnh để lưu trạng thái của các quy trình được ưu tiên trước.
• 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 lịch vòng tròn

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

• Nếu thời gian cắt của hệ điều hành thấp, đầu ra của bộ xử lý sẽ bị 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 nhiều vào lượng tử thời gian.
• Không thể đặt ưu tiên cho các quy trình.
• Lập lịch vòng tròn không ưu tiên đặc biệt cho các 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 tồi tệ 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 nhiệm 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 tác vụ

Công thức:

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +… + (dti+ sti + eti )N., + (dti+ sti + eti + eti) N} + tISRt,SR = sum of all execution times

Tóm lược:

• Tên của thuật toán này xuất phát từ nguyên tắc vòng tròn, trong đó mỗi người lần lượt nhận được một 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 cũng như các 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.
• 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 lặp là Nếu bạn biết tổng số quá trình trên hàng đợi chạy, thì bạn cũng có thể giả định thời gian phản hồi trong trường hợp xấu nhất cho cùng một quá 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à một thuật ngữ được sử dụng cho khoảng thời gian tối đa cần thiết để thực hiện tất cả các tác vụ.