BÀI TẬP : ĐIỀU PHỐI THEO VÒNG ROBIN (ROUND ROBIN SCHEDULING - RRS)

Ở phần bài tập RRS, có 1 bạn trong lớp lên giải nhưng phần tính toán thời gian chờ P2 chưa chính xác, mình viết bài chia sẽ...mong các bạn đóng góp ý kiến cho bài toán chính xác.
Đề bài:
Tiến trình Thời gian Khoảng CPU Time Quantum
P1..................3..................37...................10ms
P2.................10.................20
P3.................24.................14

Biểu Đồ Gantt?
Thời gian chờ trung bình?
Giải:
a. Biểu Đồ Gantt

P1

P2

P1

P2

P3

P1

P3

P1

3....13....23...33....43....53....63....67....74
b.Cách 1: Thời gian chờ:
P1=(74-37-3)=34(ms)
P2=(43-20-10)=13(ms)
P3=(67-14-24)=29(ms)
Thời gian chờ trung bình của tiến trình: (P1+P2+P3)/3=(34+13+29)/3=25,3(ms)
b.Cách 2:Thời gian chờ:
P1=(23-13)+(53-33)+(67-63)=34(ms)
P2=(13-10)+(33-23)=13(ms).// vì thời gian bắt đầu của P2 là 10ms
P3=(43-24)+(63-53)=29(ms)
Thời gian chờ trung bình của tiến trình: (P1+P2+P3)/3=(34+13+29)/3=25,3(ms)

Mình thấy bài này như vầy là hòan chỉnh rồi.Mình mới tìm được 1 (I83C) bài gửi mọi người tham khảo :
Đề bài: Một hệ thống có 3 tiến trình với thời điểm đầu và thời gian sử dung CPU như sau:

Tiến trình-----------Thời điểm đến (ms) ------- CPU Burst (ms)
P1-------------------------- 4 --------------------------24
P2------------------------- 19 ------------------------- 17
P3--------------------------30 -------------------------- 8

Dùng thuật giải Round - Robin với thời lượng 10 giây để đ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.

a. Biểu đồ Gantt.

---------- P1-------- P1--------P2-----P1----P3-----P2
|----|----------|----------|----------|----|--------|-------|
-------4---------14--------24--------34---38-----46-----53
b. P1=38-24-4=10
P2=53-19-17=17
P3=46-30-8=8
Thời gian trung bình = (10+17+/3=11.7 ms

Post thêm BT về Thuật giải Round-Robin các bạn TK

Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:
Tiến trình Thời điểm đến (ms) CPU-Burst (ms)
P1 5 47
P2 23 15
P3 45 28
Dùng thuật giải Round-Robin với thời lượng bằng 20 ms để điều phối CPU:
_ Thể hiện bằng biểu đồ Gantt
_ Tính thời gian chờ trung bình của các tiến trình

*Giải:
_Biểu đồ Gantt

|.....P1........|....P2....|.....P1.........|.....P3........|.P1.....|.P3..|
5...............25.........40...............60..............80.......87...95

_ Thời gian chờ của các tiến trình:
P1 = 87 - 47 - 5 = 35 ms
P2 = 40 - 15 - 23 = 2 ms
P3 = 95 - 28 - 45 = 22 ms
Thời gian chờ trung bình = ( 35 + 2 + 22 ) / 3 = 59 / 3 = 19,66 ms

Mình cũng vừa tìm được 1 ví dụ khác về Round- Robin . Các bạn tham khảo thêm nhé.

Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:
TT Thời điểm đến (ms) CPU-Burst (ms)
P1 4 46
P2 30 28
P3 51 33
Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phương án):
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.

a/

-----+----P1--+---P1----+---P2-----+-P1--+----P3----+--P2--+-- P3----
-----|----------|----------|-----------|------|------------|-------|---------|
0 --- 4 --------24 ------- 44 ------- 64 --- 70 --------- 90 ---- 98 ------111

b/ TG chờ TB = 87/3=29 (ms)
b/ TG chờ TB = 87/3=29 (ms)
Giải thích:
Hình vẽ mô tả các tiến trình đây:

1. Thời điểm 4: P1 bắt đầu chạy 20 ms
2. Thời điểm 24: do P2,P3 chưa đến nên P1 chạy tiếp 20 ms
3. Thời điểm 44: P2 được tiếm quyền P1 (vì P2 đang chờ ở thời điểm 30)
4. Thời điểm 64: P1 được tiếm quyền P2 (vì P1 đang chờ ở thời điểm 44 )
5. Thời điểm 70: P3 được chạy trước P2 (vì P3 đang chờ trước ở thời điểm 51 còn P2 là 64 )
6. Thời điểm 90: P2 được tiếm quyền P3 (vì P2 đang chờ ở thời điểm 64 )
7. Cuối cùng chỉ còn P3 sẽ chạy hết thời gian còn lại.

Chú ý thời điểm đến của P2=30 và P3=51
Bạn cộng các số màu đỏ trong hình lại rồi chia cho 3.
Kết quả : 87/3=29.

MaiTranHoangTri65(102C) đã viết:Post thêm BT về Thuật giải Round-Robin các bạn TK

Một hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng CPU như sau:
Tiến trình Thời điểm đến (ms) CPU-Burst (ms)
P1 5 47
P2 23 15
P3 45 28
Dùng thuật giải Round-Robin với thời lượng bằng 20 ms để điều phối CPU:
_ Thể hiện bằng biểu đồ Gantt
_ Tính thời gian chờ trung bình của các tiến trình

*Giải:
_Biểu đồ Gantt

|.....P1........|....P2....|.....P1.........|.....P3........|.P1.....|.P3..|
5...............25.........40...............60..............80.......87...95

_ Thời gian chờ của các tiến trình:
P1 = 87 - 47 - 5 = 35 ms
P2 = 40 - 15 - 23 = 2 ms
P3 = 95 - 28 - 45 = 22 ms
Thời gian chờ trung bình = ( 35 + 2 + 22 ) / 3 = 59 / 3 = 19,66 ms

- Sau khi P1 hết thời lượng thực thi 20ms sẽ đưa P1 ra hàng đợi.
- P2 đến ở thời điểm 23 ms nhưng phải chờ đến thời điểm 25 ms mới được thực thi do P1 vẫn còn thời lượng thực thi.
- Sau khi P2 thực thi xong do P1 lúc này còn ở hàng đợi nên P1 được thực thi
- P3 đến ở thời điểm 45 ms nhưng phải chờ P1 thực thi hết thời lượng mới được thực thi.
P1= (40-25)+(80-60) = 35ms
P2=(25-23) = 2 ms
P3=(60-45)+(87-80) = 22 ms
Thời gian chờ trung bình = ( 35 + 2 + 22 ) / 3 = 59 / 3 = 19,66 ms
Theo mình bạn nên giải câu b theo cách giải của Thầy trên lớp. Phương pháp giải câu b của bạn chỉ nên áp dụng để kiểm tra lại xem Biểu đồ Gantt và tính thời gian chờ trung bình đã đúng chưa. Vì theo mình thấy cách tính câu b như vậy mà không sử dụng biểu đồ Gantt nếu như bạn vẽ biểu đồ Gantt sai thì câu b bạn vẫn tính đúng như vậy sẽ mất câu a. ý kiến của mình như vậy không biết có đúng không?

nguyenvandung(i91C) đã viết:Theo mình bạn nên giải câu b theo cách giải của Thầy trên lớp. Phương pháp giải câu b của bạn chỉ nên áp dụng để kiểm tra lại xem Biểu đồ Gantt và tính thời gian chờ trung bình đã đúng chưa. Vì theo mình thấy cách tính câu b như vậy mà không sử dụng biểu đồ Gantt nếu như bạn vẽ biểu đồ Gantt sai thì câu b bạn vẫn tính đúng như vậy sẽ mất câu a. ý kiến của mình như vậy không biết có đúng không?

Lúc ra thi bạn sẽ không biết trước kết quả, do vậy khi giải câu a sai, nếu theo cách dựa trên sơ đồ Gantt để tính thời gian chờ thì kết quả câu b cũng sai theo, bạn không cách nào kiểm tra được. Ngược lại, nếu giải câu b theo cách mà bạn MaiTranHoangTri65(102C) đã dùng thì có khả năng sẽ cho kết quả đúng (hên xui), vì nó không dựa hoàn toàn vào sơ đồ Gantt, mà chỉ lấy thời gian kết thúc của tiến trình đó thôi

cách tính của bạn MaiTranHoangTri65 không phải hên xui đâu mà đúng đó, vì đây là cách của các bạn khóa trước làm và thầy cũng đã áp dụng vì thấy đúng mà. đúng là cách này khó hiểu hơn vì không trực quan = cách cổ điển của thầy, nhưng mà đó cũng là 1 cách để mình kiểm tra lại kết quả mình làm có đúng không

Hix, hên xui ở đây có nghĩa là với trường hợp câu a giải sai, dẫn theo câu b có thể sai (hoặc đúng nếu hên). Chứ cách của thầy giải trong đáp án dĩ nhiên là đúng rồi, ai dám nói cách giải của thầy là hên xui, bạn đọc bài của mình không kỹ đã nói vậy rồi

Vả lại, theo bản thân mình nhận thấy thì cách giải trong đáp án của thầy dễ hiểu và trực quan hơn cách cổ điển của thầy hướng dẫn khi sửa trên bảng

thời gian chờ = thời gian kết thúc - thời gian thực thi - thời gian bắt đầu

quá dễ hiểu và trực quan còn gì.

Admin
Chính xác hơn là:
Thời gian chờ = Thời điểm kết thúc - Thời điểm bắt đầu - Thời gian thực thi

Các 1 hơi khó hiểu bạn có thể giải thích rõ không,mình chỉ hiểu cách 2 thôi^^

Các bạn vào đâyhttps://hedieuhanh.forumvi.com/t2658-topic để tham khảo thảo luận Đề thi và Lời giải đề thi cuối kỳ ngày 27-12-2010 của lớp I92C trong đó có bài tập về Round-Robin.

Cám ơn bạn đã chia sẽ bài tập thật hữu ích

LeVanHung(102C) đã viết: Ở phần bài tập RRS, có 1 bạn trong lớp lên giải nhưng phần tính toán thời gian chờ P2 chưa chính xác, mình viết bài chia sẽ...mong các bạn đóng góp ý kiến cho bài toán chính xác.
Đề bài:
Tiến trình Thời gian Khoảng CPU Time Quantum
P1..................3..................37...................10ms
P2.................10.................20
P3.................24.................14

Biểu Đồ Gantt?
Thời gian chờ trung bình?
Giải:
a. Biểu Đồ Gantt

P1

P2

P1

P2

P3

P1

P3

P1

3....13....23...33....43....53....63....67....74
b.Cách 1: Thời gian chờ:
P1=(74-37-3)=34(ms)
P2=(43-20-10)=13(ms)
P3=(67-14-24)=29(ms)
Thời gian chờ trung bình của tiến trình: (P1+P2+P3)/3=(34+13+29)/3=25,3(ms)
b.Cách 2:Thời gian chờ:
P1=(23-13)+(53-33)+(67-63)=34(ms)
P2=(13-10)+(33-23)=13(ms).// vì thời gian bắt đầu của P2 là 10ms
P3=(43-24)+(63-53)=29(ms)
Thời gian chờ trung bình của tiến trình: (P1+P2+P3)/3=(34+13+29)/3=25,3(ms)

Thật đáng chúc mừng bạn "LeVanHung(102C)" bạn giải chính xác đề thi Môn HĐH Câu 4 (2đ) khoá I92C ngày 27/12/2010.
Hy vọng nếu Thầy có ra đề chương 5 chúc cả lớp (cả I102C và các bạn khoá trước) đều làm tốt câu này. Kỳ thi sắp đến rồi mình Chúc Thầy và tất cả các bạn nhiểu sức khoẻ, tinh thần tốt cho kỳ thi sắp đến

Một bài khác về SJFS

Giải
Thời điểm Tiến trình Khoảng CPU kế tiếp
-- 0 -------- P1 -------- 7 ms
-- 2 -------- P2 -------- 4 ms
-- 4 -------- P3 -------- 2 ms

CPU Burst = 2ms

Sơ đồ Gantt



Thời gian chờ trung bình:(8 + 0 + 2)/3 =2,67 ms

Thời gian chờ của các tiến trình

P1 = 8 - 2 = 6
P2 = 0
P3 = 6 - 2 = 4

Admin
Cần tính lại thời gian chờ cho đúng !

Nguyen_Cao_Tri_(I92C) đã viết:Một bài khác về SJFS

Giải
Thời điểm Tiến trình Khoảng CPU kế tiếp
-- 0 -------- P1 -------- 7 ms
-- 2 -------- P2 -------- 4 ms
-- 4 -------- P3 -------- 2 ms

CPU Burst = 2ms

Sơ đồ Gantt



Thời gian chờ trung bình:(8 + 0 + 2)/3 =2,67 ms

Thời gian chờ của các tiến trình

P1 = 8 - 2 = 6
P2 = 0
P3 = 6 - 2 = 4

Admin
Cần tính lại thời gian chờ cho đúng !

Vâng, cám ơn Thầy đã giúp em phát hiện bài giải mình sai
Thầy thật tuyệt vời vì ngày nghỉ Thầy vẫn dành thời gian xem bài và đánh giá cho chúng em.
Em xin phép cập nhật lại bài như sau




Thời gian chờ trung bình:(6 + 0 + 2)/3 =2,67 ms

Thời gian chờ của các tiến trình

P1 = 8 - 2 = 6
P2 = 0
P3 = 6 - 4 = 2

Cảm ơn Trí nhiều nha.

Khi nào rảnh tụi mình ngồi học cùng với nhau nhé.

Tìm được một bài về Round-Robin mọi người cùng tham khảo

Tiến trình	Thời điểm	Thực thi
P1	0	24
P2	1	3
P3	2	3

Với time quantum = 4 ms

a.Biểu đồ Gantt :

|...P1...|...P2...|...P3...|.............P1.............|
0........4.........7........10...........................30

b.Thời gian chờ trung bình:

- Cách 1:

P1 = 30 - 24 - 0 = 6 ms
P2 = 7 - 3 - 1 = 3 ms
P3 = 10 - 3 - 2 = 5 ms
t = (6 + 3 + 5)/3= 14/3 = 4,66 ms

-Cách 2 :

P1 = 10 - 4 = 6 ms
P2 = 4 - 1 = 3 ms
P3 = 7- 2 = 5 ms
t = (6 + 3 + 5)/3= 14/3 = 4,66 ms

Các bạn xem có gì sai sót thì sửa lại dùm mình

Thanks. Chúc cả lớp học bài thi tốt nhé!

LeVanHung(102C) đã viết: Ở phần bài tập RRS, có 1 bạn trong lớp lên giải nhưng phần tính toán thời gian chờ P2 chưa chính xác, mình viết bài chia sẽ...mong các bạn đóng góp ý kiến cho bài toán chính xác.
Đề bài:
Tiến trình Thời gian Khoảng CPU Time Quantum
P1..................3..................37...................10ms
P2.................10.................20
P3.................24.................14

Biểu Đồ Gantt?
Thời gian chờ trung bình?
Giải:
a. Biểu Đồ Gantt

P1

P2

P1

P2

P3

P1

P3

P1

3....13....23...33....43....53....63....67....74
b.Cách 1: Thời gian chờ:
P1=(74-37-3)=34(ms)
P2=(43-20-10)=13(ms)
P3=(67-14-24)=29(ms)
Thời gian chờ trung bình của tiến trình: (P1+P2+P3)/3=(34+13+29)/3=25,3(ms)
b.Cách 2:Thời gian chờ:
P1=(23-13)+(53-33)+(67-63)=34(ms)
P2=(13-10)+(33-23)=13(ms).// vì thời gian bắt đầu của P2 là 10ms
P3=(43-24)+(63-53)=29(ms)
Thời gian chờ trung bình của tiến trình: (P1+P2+P3)/3=(34+13+29)/3=25,3(ms)

Theo cach nghi cua minh :
- P1 chay tu 3 toi thoi diem 13 thi vao hang doi ready va con khoang CPU la 27
- P2 chay den 23 thi lai vao hang doi hang doi ready sau P1 do thoi diem P3 chua toi va con khoang CPU la 10
- P1 chay tiep den thoi diem 33 va lai vao hang doi ready nhu sau:P2,P3,P1 va con khoang CPU la 17
- P2 chay tiep den thoi diem 43 va lai vao hang doi ready nhu sau:P3,P1 ,P2va con khoang CPU la 0
- P3 chay den thoi diem 53 va lai vao hang doi ready nhu sau:P1,P2,P3, va con khoang CPU la 4
- P1 chay tiep den thoi diem 63 va lai vao hang doi ready nhu sau:P2,P3,P1 va con khoang CPU la 7
- Do P2 da het khoang CPU nen P3 chay tiep den thoi diem 67 va lai vao hang doi ready nhu sau:P1,P3 va con khoang CPU la 0
- P1 chay tiep den thoi diem 74 .

maivietthanh (i92c) đã viết:Cảm ơn Trí nhiều nha.

Khi nào rảnh tụi mình ngồi học cùng với nhau nhé.

Học chung thì cho mình 1 vé nha. Mình cũng đang cần học để hiểu rõ hơn đây.

vongocminhhoang (102C) đã viết:cách tính của bạn MaiTranHoangTri65 không phải hên xui đâu mà đúng đó, vì đây là cách của các bạn khóa trước làm và thầy cũng đã áp dụng vì thấy đúng mà. đúng là cách này khó hiểu hơn vì không trực quan = cách cổ điển của thầy, nhưng mà đó cũng là 1 cách để mình kiểm tra lại kết quả mình làm có đúng không

Mình đồng ý với bạn này, giải bài tập sao mà hên xui được, phương pháp đã qua kiểm chứng thì người ta mới dám áp dụng chứ. Nên biết 2 cách luôn, khi thi, làm nháp 2 cách luôn, hơi mất thời gian chút nhưng có kết quả chính xác.

TranThaiHuan(102C) đã viết:Mình thấy bài này như vầy là hòan chỉnh rồi.Mình mới tìm được 1 (I83C) bài gửi mọi người tham khảo :
Đề bài: Một hệ thống có 3 tiến trình với thời điểm đầu và thời gian sử dung CPU như sau:

Tiến trình-----------Thời điểm đến (ms) ------- CPU Burst (ms)
P1-------------------------- 4 --------------------------24
P2------------------------- 19 ------------------------- 17
P3--------------------------30 -------------------------- 8

Dùng thuật giải Round - Robin với thời lượng 10 giây để đ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.

a. Biểu đồ Gantt.

---------- P1-------- P1--------P2-----P1----P3-----P2
|----|----------|----------|----------|----|--------|-------|
-------4---------14--------24--------34---38-----46-----53
b. P1=38-24-4=10
P2=53-19-17=17
P3=46-30-8=8
Thời gian trung bình = (10+17+/3=11.7 ms

Có 1 cách giải khác của bài này, nhờ thầy và các bạn kiểm tra dùm, cách nào là đúng? Cảm ơn Thầy và các bạn.

a. bieu do Gantt:
| P1 | P1 | P2 | P3 | P1 | P2 |
4 14 24 34 42 46 53

b. Thoi gian cho TB:
P1 = 46 - 24 - 4 = 18
P2 = 53 - 17 - 19 = 27
P3 = 42 - 8 - 30 = 4
thoi gian cho TB la: (18 + 27 + 4 )/3 = 16,3 (ms)

ng_minhthoa đã viết:

TranThaiHuan(102C) đã viết:Mình thấy bài này như vầy là hòan chỉnh rồi.Mình mới tìm được 1 (I83C) bài gửi mọi người tham khảo :
Đề bài: Một hệ thống có 3 tiến trình với thời điểm đầu và thời gian sử dung CPU như sau:

Tiến trình-----------Thời điểm đến (ms) ------- CPU Burst (ms)
P1-------------------------- 4 --------------------------24
P2------------------------- 19 ------------------------- 17
P3--------------------------30 -------------------------- 8

Dùng thuật giải Round - Robin với thời lượng 10 giây để đ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.

a. Biểu đồ Gantt.

---------- P1-------- P1--------P2-----P1----P3-----P2
|----|----------|----------|----------|----|--------|-------|
-------4---------14--------24--------34---38-----46-----53
b. P1=38-24-4=10
P2=53-19-17=17
P3=46-30-8=8
Thời gian trung bình = (10+17+/3=11.7 ms

Có 1 cách giải khác của bài này, nhờ thầy và các bạn kiểm tra dùm, cách nào là đúng? Cảm ơn Thầy và các bạn.

a. bieu do Gantt:
| P1 | P1 | P2 | P3 | P1 | P2 |
4 14 24 34 42 46 53

b. Thoi gian cho TB:
P1 = 46 - 24 - 4 = 18
P2 = 53 - 17 - 19 = 27
P3 = 42 - 8 - 30 = 4
thoi gian cho TB la: (18 + 27 + 4 )/3 = 16,3 (ms)

Mình thấy bài giải của bạn TranThaiHuan là đúng đó. Bạn nên xem lại khái niệm thuật toán Round Robin Scheduling bạn sẽ hiểu cách làm. Ở đây sai ở P3 thay vào đó là P1 được thực thi. Bởi vì tại thời điểm trước đó P1 đã được đưa vào hàng đợi trong khi P3 chưa tới.
| P1 | P1 | P2 | P3 | P1 | P2 |
==> | P1 | P1 | P2 | P1 | P3 | P2 |

bai cac ban rat hay,
cam on cac ban nhieu nhe!

Bài giải của bạn đúng, nhưng bạn vẽ biểu đồ Grantt như zậy thì ko biết có bị trừ diểm ko

thansk bạn