Rate this post

Thuật toán lập lịch Round Robin là một trong những thuật toán lập lịch phổ biến nhất mà nó thực sự có thể được triển khai trong hầu hết các hệ điều hành. Đây là phiên bản ưu tiên của lập lịch phục vụ đến trước. Thuật toán tập trung vào Chia sẻ thời gian. Trong thuật toán này, mọi quy trình được thực thi theo một cách tuần hoàn.

Các bài viết liên quan:

Một lát thời gian nhất định được xác định trong hệ thống được gọi là lượng tử thời gian . Mỗi tiến trình hiện diện trong hàng đợi sẵn sàng được gán cho CPU lượng tử thời gian đó, nếu quá trình thực thi được hoàn thành trong thời gian đó thì quá trình sẽ kết thúc nếu không quá trình sẽ quay lại hàng đợi sẵn sàng và đợi lượt tiếp theo hoàn thành việc thực hiện.

Ví dụ về lập lịch RR

Trong ví dụ sau, có sáu quy trình được đặt tên là P1, P2, P3, P4, P5 và P6. Thời gian đến và thời gian bùng nổ của chúng được đưa ra dưới đây trong bảng. Lượng tử thời gian của hệ là 4 đơn vị.

Xử lý IDThời gian đếnThời gian bùng nổ
105
216
323
431
545
664

Theo thuật toán, chúng ta phải duy trì hàng đợi sẵn sàng và biểu đồ Gantt. Cấu trúc của cả hai cấu trúc dữ liệu sẽ được thay đổi sau mỗi lần lập lịch.

Xem thêm Kiểm tra lỗ hổng bảo mật Process Timing

Hàng đợi sẵn sàng:

Ban đầu, tại thời điểm 0, quá trình P1 đến sẽ được lên lịch cho lát thời gian 4 đơn vị. Do đó trong hàng đợi sẵn sàng, sẽ chỉ có một quá trình P1 khi bắt đầu với thời gian bùng nổ của CPU là 5 đơn vị.

P1
5

Biểu đồ Gantt

P1 sẽ được thực hiện cho 4 đơn vị đầu tiên.

Hàng đợi sẵn sàng

Trong khi thực thi P1, bốn quy trình nữa P2, P3, P4 và P5 sẽ đến trong hàng đợi sẵn sàng. P1 vẫn chưa hoàn thành, nó cần thêm 1 đơn vị thời gian do đó nó cũng sẽ được thêm trở lại hàng đợi sẵn sàng.

P2P3P4P5P1
63151

Biểu đồ Gantt

Sau P1, P2 sẽ được thực hiện trong 4 đơn vị thời gian được hiển thị trong biểu đồ Gantt.

Hàng đợi sẵn sàng

Trong quá trình thực thi P2, một tiến trình nữa P6 được đưa vào hàng đợi sẵn sàng. Vì P2 vẫn chưa hoàn thành nên P2 cũng sẽ được thêm trở lại hàng đợi sẵn sàng với thời gian bùng nổ còn lại là 2 đơn vị.

P3P4P5P1P6P2
315142

Biểu đồ Gantt

Sau P1 và P2, P3 sẽ được thực thi trong 3 đơn vị thời gian vì thời gian nổ CPU của nó chỉ là 3 giây.

Hàng đợi sẵn sàng

Vì P3 đã được hoàn thành, do đó nó sẽ bị kết thúc và không được thêm vào hàng đợi sẵn sàng. Quá trình tiếp theo sẽ được thực hiện là P4.

P4P5P1P6P2
15142

Biểu đồ Gantt

Sau đó, P1, P2 và P3, P4 sẽ được thực thi. Thời gian bùng nổ của nó chỉ là 1 đơn vị nhỏ hơn lượng tử thời gian do đó nó sẽ được hoàn thành.

Hàng đợi sẵn sàng

Quá trình tiếp theo trong hàng đợi sẵn sàng là P5 với 5 đơn vị thời gian bùng nổ. Vì P4 đã hoàn thành nên nó sẽ không được thêm trở lại hàng đợi.

P5P1P6P2
5142

Biểu đồ Gantt

P5 sẽ được thực hiện trong toàn bộ lát thời gian vì nó yêu cầu 5 đơn vị thời gian liên tục cao hơn lát thời gian.

Hàng đợi sẵn sàng

P5 vẫn chưa được hoàn thành; nó sẽ được thêm trở lại hàng đợi với thời gian bùng nổ còn lại là 1 đơn vị.

P1P6P2P5
1421

Biểu đồ Gantt

Quá trình P1 sẽ được đưa ra lượt tiếp theo để hoàn thành quá trình thực thi của nó. Vì nó chỉ yêu cầu 1 đơn vị thời gian bùng nổ nên nó sẽ được hoàn thành.

Hàng đợi sẵn sàng

P1 đã hoàn thành và sẽ không được thêm trở lại hàng đợi sẵn sàng. Quá trình tiếp theo P6 chỉ yêu cầu 4 đơn vị thời gian bùng nổ và nó sẽ được thực hiện tiếp theo.

P6P2P5
421

Biểu đồ Gantt

P6 sẽ được thực hiện trong 4 đơn vị thời gian cho đến khi hoàn thành.

Hàng đợi sẵn sàng

Vì P6 đã hoàn thành, do đó nó sẽ không được thêm lần nữa vào hàng đợi. Chỉ có hai quy trình hiện diện trong hàng đợi sẵn sàng. Quá trình tiếp theo P2 chỉ yêu cầu 2 đơn vị thời gian.

P2P5
21

Biểu đồ Gantt

P2 sẽ được thực thi lại, vì nó chỉ yêu cầu 2 đơn vị thời gian do đó quá trình này sẽ được hoàn thành.

Hàng đợi sẵn sàng

Bây giờ, quy trình khả dụng duy nhất trong hàng đợi là P5 yêu cầu 1 đơn vị thời gian bùng nổ. Vì khoảng thời gian là 4 đơn vị nên nó sẽ được hoàn thành trong lần bắn tiếp theo.

P5
1

Biểu đồ Gantt

P5 sẽ được thực thi cho đến khi hoàn thành.

Thời gian hoàn thành, thời gian quay vòng và thời gian chờ sẽ được tính như bảng dưới đây.

Như chúng ta biết,

  1. Thời gian quay vòng   =  Thời gian hoàn thành  – Thời gian đến   
  2. Thời gian chờ   =  Thời gian quay  vòng – Thời gian liên tục   
Xử lý IDThời gian đếnThời gian bùng nổThời gian hoàn thànhThời gian quay vòngThời gian chờ
105171712
216232216
3231196
431129số 8
545242015
664211511

                  Thời gian chờ trung bình = (12 + 16 + 6 + 8 + 15 + 11) / 6 = 76/6 đơn vị

Thuận lợi

  1. Nó thực sự có thể thực hiện được trong hệ thống vì nó không phụ thuộc vào thời gian bùng nổ.
  2. Nó không bị vấn đề chết đói hay hiệu ứng đoàn xe.
  3. Tất cả các công việc được phân bổ giá vé của CPU.

Nhược điểm

  1. Lượng tử thời gian càng cao thì thời gian phản hồi trong hệ thống càng cao.
  2. Lượng tử thời gian càng thấp, chi phí chuyển đổi ngữ cảnh trong hệ thống càng cao.
  3. Quyết định một lượng tử thời gian hoàn hảo thực sự là một nhiệm vụ rất khó khăn trong hệ thống.

Xem thêm Kiểm tra lỗ hổng bảo mật Session Timeout

Leave a Reply

Call now
%d bloggers like this: