Giải thuật điều phối Round Robin (RR)

8
28876

Hôm nay ra tiếp tục với một thuật giải định thời CPU khác, đó là Round Robin (RR).

Đối với thuật giải RR, mỗi tiến trình trước khi bắt đầu được đưa vào CPU xử lý, sẽ được cấp phát cho một đơn vị thời gian chiếm dụng CPU nhất định.

Ta gọi chung giá trị hằng số này với cái tên là quantum. Điểm khác biệt của RR với FCFS đó  là RR tuân thủ theo cơ chế không độc quyền (preemtive).

image001
Như vậy, khi một tiến trình sử dụng hết thời gian quantum mà nó được cấp phát, thì dù vẫn còn phải xử lý tiếp, phần dư của nó cũng sẽ được chuyển về phía sau trong danh sách hàng đợi. Sau đó, căn cứ vào danh sách Ready list đã nạp trước đó, CPU sẽ lấy tiếp tiến trình kế cận để đưa vào xử lý, với mức quantum là như nhau cho tất cả các tiến trình.

Nếu gọi n là số tiến trình có trong Ready list, thời gian quantum là q, như vậy mỗi tiến trình sẽ có một khoảng thời gian là image002 để sử dụng CPU.

Về mặt thời gian thì với RR, thời gian hoàn tất trung bình sẽ cao hơn SJF, bù lại, tính đáp ứng sẽ tốt hơn.

Để hình dung rõ ràng, ta sẽ xét 2 ví dụ sau đây.

Process Arrival Time Burst Time
P1 0 24
P2 1 3
P3 2 3

Với bảng dữ liệu trên, ta biết thêm được quantum time=4. Như vậy, để tính toán thuận tiện, ta cũng tiếp tục sử dụng giản đồ Gantt:

image005

Với giản đồ Gantt này, ta có thể tính được:
– Thời gian xử lý: P1=24, P2=3 và P3= 3.
– Thời gian đợi lần lượt:
+ P1 đợi 0 + (10-4) (ms).
+ P2 đợi 4-1=3 (ms).
+ P3 đợi 7-2=5 (ms).
– Thời gian hoàn tất tiến trình:
+ P1: 30 (ms).
+ P2: 6 (ms).
+ P3: 8 (ms).
– Thời gian trung bình: AvgWT = (6+3+5)/3 = 4.66

Các bạn có thể xem chi tiết ở đây

image006

Nhận xét RR

– Loại bỏ hiện tượng độc chiếm CPU
– Phù hợp với hệ thống tương tác người dùng
– Hiệu quả ? Phụ thuộc vào việc lựa chọn quantum q
+ q quá lớn => FCFS (giảm tính tương tác)
+ q quá nhỏ => chủ yếu thực hiện chuyển đổi ngữ cảnh (context switching)
+ Thường q = 10-100 milliseconds

Điều phối với độ ưu tiên

– Một độ ưu tiên (integer) được gán vào mỗi tiến trình
– Phân biệt tiến trình quan trọng với tiến trình bình thường
– Tiêu chí lựa chọn tiến trình
Tiến trình có độ ưu tiên cao nhất
– Thời điểm lựa chọn tiến trình
+ Độc quyền
+ Không độc quyền (có độ ưu tiên)

Minh họa điều phối với độ ưu  tiên (không độc quyền)

image007

Nhận xét điều phối với độ ưu tiên

Cách tính độ ưu tiên ?
– Hệ thống gán
– Người dùng gán
Tính chất độ ưu tiên
– Tĩnh
+ Vấn đề Starvation: các tiến trình độ ưu tiên thấp có thể không bao giờ thực thi được
+ Giải pháp Aging – tăng độ ưu tiên cho tiến trình chờ lâu trong hệ thống (sống lâu lên lão làng…)
– Động
Võ T. Thương
thuongvt@hotmail.com

Bài tập có hướng dẫn về chiến lược điều phối Round Robin (Xem tiếp trang sau)

8 COMMENTS

  1. cho em hỏi là khi đề yêu cầu vẽ giảng đồ grantt mà có áp dụng độ ưu tiên không độc quyền thì mình sẽ giải quyết nó ra sao ạ, em xin cảm ơn add!

  2. nếu 2 process vào hàng đợi cùng 1 lúc trong chiến lược điều phối Round Robin thì tiêu chí gì để quyết định process nào đc chọn trc
    nếu 1 process trong chiến lược điều phối Round Robin vừa chạy xong 1 chu kỳ tại thời điểm x và tại thời điểm x này xuất hiện 1 process mới vào hàng đợi, vậy process nào sẽ đứng trước process nào

    • 1. “nếu 2 process vào hàng đợi cùng 1 lúc trong chiến lược điều phối Round Robin thì tiêu chí gì để quyết định process nào đc chọn trc” –> HDH sẽ dùng chiến lược SJF (công việc ngắn nhất), tiến trình thời gian use CPU ngắn hơn sẽ được ưu tiên chạy trước.
      2. “nếu 1 process trong chiến lược điều phối Round Robin vừa chạy xong 1 chu kỳ tại thời điểm x và tại thời điểm x này xuất hiện 1 process mới vào hàng đợi, vậy process nào sẽ đứng trước process nào” –> tiến trình cũ được ưu tiên trước, mới xếp hàng sau

  3. giải thuật RR có quantum=2, tại thời điểm x chỉ còn P3 với thời gian xử lý còn lại = 4. Vậy P3
    chạy đến thời điểm x+2 thì quay về hàng đợi rồi chạy tiếp có phải không ạ, nếu phải thì trong biểu đồ gantt P3 chạy từ x đến x+4 hay phải chia thành 2 đoạn x->x+2 và x+2->x+4 ạ

  4. Xét tập các tiến trình sau (với thời gian yêu cầu CPU kèm theo). Giả sử các tiền trình đều vào hệ thống tại thời điểm 0
    Tiến trình | Thời gian CPU | Thời điểm IO | Thời gian IO
    P1 10 0 3
    P2 1 2 1
    P3 5 3 3
    P4 1 2 1
    P5 5 4 2
    a) Hãy biểu đồ Gantt khi xếp lịch theo các thuật toán FCFS, SJF, RR với q = 2
    b) Hãy cho biết trạng thái của các tiến trình tại thời điểm t = 8.8
    ready: tiến trình đang chờ để được xử lý
    running: tiến trình đang được xử lý
    waiting: tiến trình đang chớ IO
    terminated: tiến trình đã kết thúc

    em mới học môn hệ điều hành mà gặp cái bài này em không biết làm như thế nào ạ nhìn nó khác với mấy bài trên quá, chỉ giúp em với ạ em cảm ơn ạ

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.