Bài tập tham khảo các giải thuật điều phối CPU(RRS-FCFS)

Bài 1 : Thuật giải Round - Robin scheduling

Tiến trình Thời điểm CPU - Burst (ms)
P1 3 37
P2 10 20
P3 24 14
Dùng giải thuật Round - Robin với thời lượng 10ms để điều phối CPU
a. Thể hiện bằng biểu đồ Gantt
b. Tính thời gian chờ trung bình của các tiến trình

Giải
BIỂU ĐỒ GANTT:
- Điểm lưu ý khi vẽ:
+ Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum) là số q ms nào đó.
+ Hết thời gian q, thì tiến trình hiện tại sẽ bị tiến trình khác tiếm quyền nếu tiến trình mới này có thời điểm đến = hoặc < thời điểm đang xét. Đồng thời tiến trình cũ sẽ được đưa vào hàng đợi Ready
+ Tiến trình đầu tiên trong hàng đợi sẽ được chọn để tiếm quyền kế tiếp
- Vẽ biểu đồ:

- Giải thích:
(lưu ý với thuật toán này mình nhớ xem xét thời điểm đề cho là thời điểm đến của các tiến trình)
Theo đề bài này thì CPU bắt đầu cấp phát cho 3 tiến trình P1, P2, P3 là thời điểm 3 và hàng đợi Ready là

P1 P2 P3

+ Tại thời điểm 3, P1 đứng đầu hàng đợi Ready, như vậy P1 được chọn cho vận hành
+ Vì q=10ms nên tại thời điểm 13, P1 tạm dừng vận hành và bị đẩy về cuối hành đợi Ready

P2 P3 P1
Như vậy P2 lúc này đứng đầu hàng đợi và xét lại thì thấy thời điểm đến của P2 là 10 < 13, nên P2 được phép tiếm quyền kế tiếp để vận hành
+ Vì q=10ms nên đến thời điềm 23, P2 phải tạm dừng cho tiến trình khác vận hành và P2 bị đẩy về cuối hàng đợi

P3 P1 P2
Lúc này ta thấy P3 đứng đầu hàng đợi nhưng thời điểm đến của P3 là 24 > 23 (là thời điểm đang xét) nghĩa là tại thời điểm này P3 chưa có nhu cầu để vận hành, nên P3 sẽ hok tiếm quyền P2. P3 sẽ bị đẩy về cuối hàng đợi. Hàng đợi lúc này là

P1 P2 P3
Do P1 được đẩy lên đầu nên P1 được phép tiếm quyền kế tiếp tại thời điểm 23 này.
+ Cứ sau 10ms, ta lại xét để cho vận hành tiến trình kế tiếp là tiến trình nào.

Tại thời điểm 33, P1 tạm dừng và bị đẩy về cuối hàng đợi Ready

P2 P3 P1
P2 đứng đầu hàng đợi sẽ lên tiếm quyền kế tiếp.
+ Tại thời điểm 43, sau khi P2 vận hành 10ms thì lúc này P2 cũng vừa vận hành xong. Vì vậy P2 sẽ không nằm trong hàng đợi Ready. Ta có hàng đợi là

P3 P1
Ta thấy lúc này P3 mới bắt đầu vận hành vì nó đã có nhu cầu vận hành từ lúc thời điểm 24
+ Thời điểm 53, P3 tạm dừng và đưa vào cuối hàng đợi

P1 P3
Đồng thời P1 sẽ được ưu tiên lên tiếm quyền tiếp tục vận hành
+Thời điểm 63, P1 tạm dừng, P3 lên tiếm quyền và nó chỉ cần thêm 4ms nữa là P3 vận hành xong tiến trình của nó. Lúc này nó cũng hok còn nằm trong hàng đợi. Hàng đợi chỉ còn có P1
+ Do đó tại thời điểm 67, P1 được vận hành và nó vận hành hết 7ms nữa là thời gian còn lại cần cho P1
Dựa vào biểu đồ Gantt ta tính thời gian chờ trung bình

THỜI GIAN CHỜ TRUNG BÌNH
Ttb = (T1 + T2 +...+ Tn)/n
(thời gian chờ của mỗi tiến trình = tổng thời gian tiến trình đó bị gián đoạn)

T1 = (3 -3)+ (23 - 13) + (53 - 33) + (67 - 63) = 34
T2 = (13 -10) + (33- 23) = 13
T3 = (43- 24) + (63 - 53) = 29

===> Ttb = (34 + 13 + 29) / 3 = 25.33 ms
Bài 2 : FCFS (First Come First Served): Đến trước có trước
Giả sử một hệ thống có 5 tiến trình đến vào các thời điểm với các tính chất sau:

a) Vẽ 4 biểu đồ Gantt tương ứng với thuật giải điều phối FCFS và RRS (với thời lượng = 1)
b) Tính thời gian chờ trung bình của các tiến trình.

Giải:

Ta có DS các TT:


Biểu đồ Gant như sau:

Để tìm thời gian chờ ta xem hình vẽ điều phối các tiến trình theo FCFS



Vậy:
Thời gian chờ:
W = W1+W2+W3 = 3 + 4 + 13 = 20 ms
Thời gian chờ trung bình = 20/5 = 4ms


Giải thích:
P2: chạy từ giây đầu tiên do đến trước (theo FCFS) nên không phải chờ. Thời gian P2 chạy là 1s (0 ->1)
P5: chạy tiếp theo sau P2, cũng không phải chờ vì P2 đã chạy xong ở giây thứ 1. P5 chạy hết từ 1 -> 5
P3: đến từ giây thứ 2, nhưng lúc đó P5 đang chạy nên phải đứng chờ cho P5 chạy hết ( chờ từ 2->5, W1 = 3). Sau giây thứ 5, P3 mới được chạy và chạy trong 2s ( 5->7)
P1: đến từ giây thứ 3, lúc này P5 cũng đang chạy, sau P5 thì P3 đã được ưu tiên đi trước nên P1 tiếp tục chờ (chờ từ 3->7, W2=4). P3 chạy xong, P1 mới được đi. P1 chạy 10s từ (7 -> 17)
P4 chạy sau cùng do đến chậm nhất (giây thứ 4) và cũng phải chờ cho P3 & P1 chạy xong (chờ từ 4 -> 17, W3=13). Rồi P4 chạy tiếp 17->18.
Finish
Vậy thì Tổng thời gian chờ: W = W1 + W2 + W3 = 3 + 4 + 13 = 20s

2 bài này mình tìm trên mạng,mọi người tham khảo thử nha