Cách giải bài tập về các thuật giải điều phối CPU (Thuật giải RRS )

3. Thuật giải Round - Robin scheduling
Ví dụ: (Đề thi Hk2 năm 07 - 08 )

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
(mình đã có chỉnh sửa lại đề so với ban đầu mình đã post )
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

bai nay minh thay co van de o o thoi diem den????
p1 co thoi diem den la 3, khi chay voi thoi luong la 10-> chay den thoi diem la13, ma thoi diem den cua p2 la 20, con p3 la 24, vay sao ban lai ho p2 chay tu 13->23 ????, minh thay ky ky, vi chua den thoi diem den cua p2, thi sao p2lai chay dc, ban giai thich gium minh voi
thanks!

canhcam đã viết:bai nay minh thay co van de o o thoi diem den????
p1 co thoi diem den la 3, khi chay voi thoi luong la 10-> chay den thoi diem la13, ma thoi diem den cua p2 la 20, con p3 la 24, vay sao ban lai ho p2 chay tu 13->23 ????, minh thay ky ky, vi chua den thoi diem den cua p2, thi sao p2lai chay dc, ban giai thich gium minh voi
thanks!

_ Ô là la, bạn canhcam quả là có con mắt tinh tường, vấn đề bạn nhận xét rất đúng.
_ Mình đã xem lại đề thi này và phát hiện ra rằng bạn phuong ghi sai đề
_ Đây là đề thi đúng :

Tiến trình	Thời điểm	CPU - Burst
P1	3	37
P2	10	20
P3	24	14

_ Bài giải của bạn Phương hoàn toàn đúng, tuy nhiên chỗ giải thích thì lại sai từ thời điểm 33 trở về sau. Mình xin giải thích lại chỗ sai của bạn phuong như sau:

+ Tại thời điểm 3 : Ready Queue(RQ) -> |rỗng| (ở thời điểm này P1 vừa vào hàng đợi & vì chỉ có mỗi P1 nên nó được chọn cho thi hành ngay, RQ rỗng).
+ Tại thời điểm 10 : RQ -> |P2| (ở thời điểm 10s P2 đến & được đưa vào hàng đợi, P1 vẫn đang vận hành vì chưa hết khoảng Time Quantum).
+ Tại thời điểm 13 : RQ -> |P1| (ở thời điểm 13s P1 đã sử dụng hết Time Quantum của nó nên bị tiếm quyền & bị đẩy xuống cuối hàng đợi, P2 được đưa vào thi hành).
+ Tại thời điểm 23 : RQ -> |P2| (ở thời điểm này P2 đã sử dụng hết Time Quantum của nó nên bị tiếm quyền & bị đẩy xuống cuối hàng đợi, P1 được đưa vào thi hành).
+ Tại thời điểm 24 : RQ -> |P2|P3| (P3 đến & được đưa vào cuối hàng đợi, P1 vẫn đang vận hành).

_ Có gì sai xin các bạn góp ý nhé

hihi, cám ơn asmking nhắc nhở. Đúng là mình ghi sai để thiệt. Mọi người tiếp tục góp ý nha để cùng nhau học tập tốt. Vậy mình sẽ edit lại cho đề đúng heng. Mình cũng hiểu theo cách của mình, chứ hôm thầy dạy bài RRS mình ngồi dưới nghe chưa kịp lắm --> về nhà quên luôn Bạn asmking học kỹ hơn mình nên chắc cách giải thích của bạn asmkng hợp lý hơn đó, nhất là về vấn đề hàng đợi Ready.

asmking đã viết:

canhcam đã viết:bai nay minh thay co van de o o thoi diem den????
p1 co thoi diem den la 3, khi chay voi thoi luong la 10-> chay den thoi diem la13, ma thoi diem den cua p2 la 20, con p3 la 24, vay sao ban lai ho p2 chay tu 13->23 ????, minh thay ky ky, vi chua den thoi diem den cua p2, thi sao p2lai chay dc, ban giai thich gium minh voi
thanks!

_ Ô là la, bạn canhcam quả là có con mắt tinh tường, vấn đề bạn nhận xét rất đúng.
_ Mình đã xem lại đề thi này và phát hiện ra rằng bạn phuong ghi sai đề
_ Đây là đề thi đúng :

Tiến trình	Thời điểm	CPU - Burst
P1	3	37
P2	10	20
P3	24	14

_ Bài giải của bạn Phương hoàn toàn đúng, tuy nhiên chỗ giải thích thì lại sai từ thời điểm 33 trở về sau. Mình xin giải thích lại chỗ sai của bạn phuong như sau:

+ Tại thời điểm 3 : Ready Queue(RQ) -> |rỗng| (ở thời điểm này P1 vừa vào hàng đợi & vì chỉ có mỗi P1 nên nó được chọn cho thi hành ngay, RQ rỗng).
+ Tại thời điểm 10 : RQ -> |P2| (ở thời điểm 10s P2 đến & được đưa vào hàng đợi, P1 vẫn đang vận hành vì chưa hết khoảng Time Quantum).
+ Tại thời điểm 13 : RQ -> |P1| (ở thời điểm 13s P1 đã sử dụng hết Time Quantum của nó nên bị tiếm quyền & bị đẩy xuống cuối hàng đợi, P2 được đưa vào thi hành).
+ Tại thời điểm 23 : RQ -> |P2| (ở thời điểm này P2 đã sử dụng hết Time Quantum của nó nên bị tiếm quyền & bị đẩy xuống cuối hàng đợi, P1 được đưa vào thi hành).
+ Tại thời điểm 24 : RQ -> |P2|P3| (P3 đến & được đưa vào cuối hàng đợi, P1 vẫn đang vận hành).

_ Có gì sai xin các bạn góp ý nhé

Nói về cách giải thuật toán này thì ai cũng thấy nhức đầu hoa mắt cả, nhưng mà chúng ta để ý 1 tí thì chắc cũng kô đến nỗi nào nhỉ. giống như cách trình bày trên đây mình chỉ cần chú ý đến thời gian đến và thời gian tiếm quyền của các tiến trình là ok rồi.