Thảo luận Bài 6: Bài tập dùng RRS (Round-Robin)

Giải Bài tập dùng RRS (Round-Robin).

Đề thi I11C

thưa thầy em ko hiểu phần biểu đồ gantt, p1 khi bị tiếm quyền phải bị đưa về cuối vòng chờ, nhưng trên biểu đồ sau khi p2 chạy hết khoản thời gian 10ms đáng lẽ phải đến p3 sau lại là p1

kiến thức còn hạn chế mong thầy chỉ giáo

tranthephuong(i92c) đã viết:thưa thầy em ko hiểu phần biểu đồ gantt, p1 khi bị tiếm quyền phải bị đưa về cuối vòng chờ, nhưng trên biểu đồ sau khi p2 chạy hết khoản thời gian 10ms đáng lẽ phải đến p3 sau lại là p1

kiến thức còn hạn chế mong thầy chỉ giáo

chào bạn,
1-khi p1 chạy từ 5 đến 10, thì có P2 xuất hiện, lúc này trong hàng chờ có P2
nên sau khi p1 chạy xong sẽ đến P2, và khi đó p1 được đưa vào hàng chờ (chỉ có duy nhất p1 trong hàng chờ lúc này, vì mãi đến thời điểm 20 thì p3 mới xuất hiện)
2-khi p2 chạy từ 15 đến 25, thì có p3 xuất hiện,
lúc này trong hàng chờ có P1 và P3
theo thứ tự thì P1 được chạy trước, rồi mới đến P3

mong mọi người cho thêm ý kiến

tranthephuong(i92c) đã viết:thưa thầy em ko hiểu phần biểu đồ gantt, p1 khi bị tiếm quyền phải bị đưa về cuối vòng chờ, nhưng trên biểu đồ sau khi p2 chạy hết khoản thời gian 10ms đáng lẽ phải đến p3 sau lại là p1

kiến thức còn hạn chế mong thầy chỉ giáo

Bạn vui lòng xem kĩ hướng dẫn Thầy đã giảng nhé !

- Ở thời điểm 15, P1 hết thời lượng và được xếp vào cuối Ready Queue, tức là sau P2 (lúc đó P3 chưa đến), P2 ở đầu hàng chờ nên được chọn chuyển sang trang thái Running !


- Ở thời điểm 25 khi P2 hết thời lượng, HĐH sẽ chọn P1 vì P1 ở đầu hàng chờ (khi P3 đến ở thời điểm 20, P1 đã trong đó rồi, nên P3 xếp sau P1) !


- Vậy tiếp theo sẽ là P3 (?!). Thực hiện quantum đầu tiên. Thực hiện xong 10 ms , nhưng do CPU-Burst là 10ms . Nên P3 đã thực hiện xong, và không chuyển xuống cuối queue nữa.


- Vậy vòng Round Robin thứ 2 sẽ tiếp tục với 2 Tiến Trình P1, P2. Và cứ thế quá trình Round-Robin lặp lại đến khi cả P1,P2 đều xử lý xong tiến trình của riêng mình.

Như ở VD câu 4 biểu đồ Gantt thì khi đến hết tiến trình P3 ở 45 thì sao ko tiếp đến P1 mà P2 đến trước,mong mọi người giải đáp giúp.

TranQuangHien40 đã viết:Như ở VD câu 4 biểu đồ Gantt thì khi đến hết tiến trình P3 ở 45 thì sao ko tiếp đến P1 mà P2 đến trước,mong mọi người giải đáp giúp.

Theo mình nghĩ.

Cũng giống tại thời điểm 25. Tại sao P1 lại chạy trước P3:
Tại thời điểm 25:
P1 phải chờ mất 10ms
P3 chỉ chờ 5ms
=>P1 sẽ được chạy trước.
Còn tại thời điểm 45.
P2 phải chờ đến 20ms
P1 chỉ có 10ms
=>P2 sẽ được chạy trước.

Theo em suy nghĩ như vậy có đúng không thầy.
Mong thầy và các bạn góp ý thêm. Thanks.

Trong lần thi cuối trước mình cũng không để ý đến chỗ này, nên minh giải bài này sai
Kết quả là cũng tại phần này nên mình phải học lại

ngophicamI12A đã viết:

tranthephuong(i92c) đã viết:thưa thầy em ko hiểu phần biểu đồ gantt, p1 khi bị tiếm quyền phải bị đưa về cuối vòng chờ, nhưng trên biểu đồ sau khi p2 chạy hết khoản thời gian 10ms đáng lẽ phải đến p3 sau lại là p1

kiến thức còn hạn chế mong thầy chỉ giáo

Bạn vui lòng xem kĩ hướng dẫn Thầy đã giảng nhé !

- Ở thời điểm 15, P1 hết thời lượng và được xếp vào cuối Ready Queue, tức là sau P2 (lúc đó P3 chưa đến), P2 ở đầu hàng chờ nên được chọn chuyển sang trang thái Running !


- Ở thời điểm 25 khi P2 hết thời lượng, HĐH sẽ chọn P1 vì P1 ở đầu hàng chờ (khi P3 đến ở thời điểm 20, P1 đã trong đó rồi, nên P3 xếp sau P1) !


- Vậy tiếp theo sẽ là P3 (?!). Thực hiện quantum đầu tiên. Thực hiện xong 10 ms , nhưng do CPU-Burst là 10ms . Nên P3 đã thực hiện xong, và không chuyển xuống cuối queue nữa.


- Vậy vòng Round Robin thứ 2 sẽ tiếp tục với 2 Tiến Trình P1, P2. Và cứ thế quá trình Round-Robin lặp lại đến khi cả P1,P2 đều xử lý xong tiến trình của riêng mình.

Ở câu b) Tính thời gian chờ trung bình mình nhìn vào biểu đồ Gantt có thể tính được. Còn vẽ biểu đồ nếu không hiểu kỹ có thể vẽ sai. Mong các bạn giải thích kỹ hơn nữa. Khi nào p1,p2,p3 chạy(theo thứ tự, cái nào chạy trước, cái nào chạy sau)

Bài tập này nếu mình áp dụng vào thực tiễn thì thấy không đúng lắm.

Ví dụ:
Trong nhà ga có 3 ng đến mua vé, và chỉ mua được 10 vé với thời gian đến tương ứng với từng người.

Người A: mua 25 vé và đến ở 5ms và mua được 10 vé, và đứng qua 1 bên cho người kế tiếp mua( còn 15 vé nữa )

Người B: mua 15 vé và đến ở 10ms và mua được 10 vé, và đứng qua 1 bên cho người kế tiếp mua( còn 5 vé nữa)

Người C: mua 10 vé và đến ở 20ms và mua đủ 10 vé nên tiếp tục nhường cho người đứng chờ mà có số vé còn lại ít hơn là người B, và cuối cùng là người A.
Tại vì theo lý thuyết Mỗi tiến trình được cấp 1 thời lượng CPU. Sau khoảng thời gian này nó bị tiếm quyền và được đưa vào cuối hàng chờ Ready.Tiến trình đầu tiên trong hàng chờ Ready được chọn kế tiếp.
Biểu đồ Gantt theo ví dụ:

[img][/img]


Đây là theo cách nghĩ của em vào thực tế nên, có lẽ đã sai em chỉ đưa lên để thầy trò ý kiến thôi.

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.

Mình giải kết quả như sau mong các bạn đóng góp ý kiến.
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)
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.

Admin đã viết:Giải Bài tập dùng RRS (Round-Robin).

Đề thi I11C

- Thưa Thầy, em có sử dụng phần mềm demo thuật toán Robin trong tài liệu của Thầy và thấy kết quả không hợp lý, phần mềm này có vấn đề phải không ạ.
- Nhờ Thầy hướng dẫn giúp em ạ, em cám ơn Thầy rất nhiều.

Admin
Đúng rồi. Đã nói trên lớp về vấn đề này !

tranthephuong(i92c) đã viết:thưa thầy em ko hiểu phần biểu đồ gantt, p1 khi bị tiếm quyền phải bị đưa về cuối vòng chờ, nhưng trên biểu đồ sau khi p2 chạy hết khoản thời gian 10ms đáng lẽ phải đến p3 sau lại là p1

kiến thức còn hạn chế mong thầy chỉ giáo

1. Lúc 15ms, P1 đã run 10ms, trong Ready Queue (RQ) chỉ có P2 (lúc này CPU time là 15ms, tại thờ điểm này thì P3 chưa đến). P2 sẽ được run và P1 xếp vào RQ (đang rỗng nên ở vị trí đầu tiên).
2. Đến thời điểm 20ms thi P3 xuất hiện, đươc xếp vào cuối RQ, sau vi trí của P1.
3. Lúc 25ms, P2 run 10ms, được xếp vào cuối RQ, sau P1, P3. P1 được nạp để run tiếp
4. Lúc 35ms, P1 run xong 10ms (P1 đã run hết 20 ms, còn lại 5ms). P1 được xếp vào cuối RQ, sau P3, P2. P3 được nạp để run.
4. Lúc 45ms, P3 run đã xong, lúc này RQ còn lại P2, P1. P2 được nạp run.
5. Lúc 50ms, P2 hoàn tất (chỉ dùng 5ms). Còn lại duy nhất P1 trong RQ.
6. Lúc 55ms, P1 hoàn tất (chỉ dùng 5ms).

TranQuangHien40 đã viết:Như ở VD câu 4 biểu đồ Gantt thì khi đến hết tiến trình P3 ở 45 thì sao ko tiếp đến P1 mà P2 đến trước,mong mọi người giải đáp giúp.

5 - 15 P1 chạy.
ở giây thư 10 thì P2 nhảy vào ngồi chờ. P1 chạy xong về sau P2 đứng, P2 giành cpu định chạy 10s xong lại về sau P1 đứng chờ. Nhưng không ngờ trong lúc P2 chạy từ 15 - 25 thì ở giây 20 P3 nhảy vào sau P1 ngồi chờ, P2 chạy xong về cuối hàng thì đã thấy P3 ngồi trước mình nên phải câm nín chờ đến lượt. Bây giờ trong hàng đợi vị trí đứng của 3 thằng là : P1 - P3 - P2.
Theo đúng vị trí và Quantum, P1 chạy hết 10s về sau P2 đứng, P3 bước lên thế chỗ và chạy hết 10s của mình, do P3 chỉ cần 10s đã làm xong công việc nên kết thúc cuộc chơi, không về cuối hàng chờ nữa.
Lúc này trong hàng chờ chỉ còn P1 và P2. vị trí đứng lúc này là : P2 - P1.
P3 kết thúc, P2 đứng trước nên chạy trước. Theo dự kiến P2 chạy hết 10s và về cuối hàng đứng, nhưng mới chạy 5s thì P2 đã làm xong công việc và kết thúc cuộc chơi. Lúc này chỉ còn một mình P1, do không còn ai giành cpu nên P1 thông thả chạy đến khi kết thúc công viêc thì kết thúc.

ngophicamI12A đã viết:

tranthephuong(i92c) đã viết:thưa thầy em ko hiểu phần biểu đồ gantt, p1 khi bị tiếm quyền phải bị đưa về cuối vòng chờ, nhưng trên biểu đồ sau khi p2 chạy hết khoản thời gian 10ms đáng lẽ phải đến p3 sau lại là p1

kiến thức còn hạn chế mong thầy chỉ giáo

Bạn vui lòng xem kĩ hướng dẫn Thầy đã giảng nhé !

- Ở thời điểm 15, P1 hết thời lượng và được xếp vào cuối Ready Queue, tức là sau P2 (lúc đó P3 chưa đến), P2 ở đầu hàng chờ nên được chọn chuyển sang trang thái Running !



- Ở thời điểm 25 khi P2 hết thời lượng, HĐH sẽ chọn P1 vì P1 ở đầu hàng chờ (khi P3 đến ở thời điểm 20, P1 đã trong đó rồi, nên P3 xếp sau P1) !


- Vậy tiếp theo sẽ là P3 (?!). Thực hiện quantum đầu tiên. Thực hiện xong 10 ms , nhưng do CPU-Burst là 10ms . Nên P3 đã thực hiện xong, và không chuyển xuống cuối queue nữa.


- Vậy vòng Round Robin thứ 2 sẽ tiếp tục với 2 Tiến Trình P1, P2. Và cứ thế quá trình Round-Robin lặp lại đến khi cả P1,P2 đều xử lý xong tiến trình của riêng mình.

Cảm ơn bạn!

1. 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:

Dùng thuật giải Round-Robin với thời lượng bằng 20 ms để đ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
a.Thể hiện bằng biểu đồ Gantt:

b.Thời gian chờ trung bình của các tiến trình:
P1=46-26=20 ms
P2=(26-17)+(52-46)+(92-72)=35 ms
P3=(72-48)+(97-92)=29 ms
==>Thời gian chờ trung bình= (20+35+29)/3=84/3=28 ms


2. 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:

Dùng thuật giải Round-Robin với thời lượng bằng 10 ms để đ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
a.Thể hiện bằng biểu đồ Gantt:

b.Thời gian chờ trung bình của các tiến trình:
P1=(23-13)+(53-33)+(67-63)=34 ms
P2=(13-10)+(33-23)=13 ms
P3=(43-24)+(63-53)=29 ms
==>Thời gian chờ trung bình= (24+13+29)/3=76/3 ms

câu 4. đề thi khóa trước về vòng Robin bài 6
1 hệ thống có 3 tiến trình với thời điểm đến và thời gian sử dụng cpu khác nhau
Tiến trình thời điểm đến cpu-bust(ms)
p1 5 25
p2 10 15
p3 20 10


dùng thuật giải Round-Robin với thời lượng10ms để điều phối cpu
a) thể hiện bằng biểu đồ Gantt
b)tính thời gian chờ trung trình của các tiến trình

giải
a ) thể hiện bằng biểu đồ Gantt



b)tính thời gian chờ của các tiến trình
. p1=(55-5)-25=25
.p2=(50-10)-15=25
.p3=(45-20)-10=15
- thời gian chờ trung bình(25+25+15)/3=65/3=21,6 ms

tranthephuong(i92c) đã viết:thưa thầy em ko hiểu phần biểu đồ gantt, p1 khi bị tiếm quyền phải bị đưa về cuối vòng chờ, nhưng trên biểu đồ sau khi p2 chạy hết khoản thời gian 10ms đáng lẽ phải đến p3 sau lại là p1

kiến thức còn hạn chế mong thầy chỉ giáo

chào bạn lúc vì
khi P1 chạy toi 15s bị tiếm quyền và P2 được chạy và P1 đưa vào cuối hàng chờ.
P2 chạy tới 25s khi này P3 đã nhảy vào hàng chờ (thời điểm đến của P3 là 20s) nhưng P1 đã xếp vào hàng chờ trước lúc nãy được ưu tiên,P3 xếp vào hàng chờ sau P1 nên ko được chọn.

Admin
Giải thích rất rõ ràng !

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:




-Dùng thuật giải Round_robin với thời lượng 20ms để điều phối CPU:
a> Thể hiện bằng biểu đồ Grant
b> Tính thời gian chờ trung bình của các tiến trình

Trả lời:
a> Thể hiện bằng biểu đồ Grant





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

a) Tính hướng xuất / nhập của tiến trình ( I/O-boundedness): Khi một tiến trình nhận được CPU, chủ yếu nó chỉ sử dụng CPU đến khi phát sinh một yêu cầu nhập xuất ? Hoạt động của các tiến trình như thế thường bao gồm nhiều lượt sử dụng CPU , mỗi lượt trong một thời gian khá ngắn.
b) Tính hướng xử lý của tiến trình ( CPU-boundedness): Khi một tiến trình nhận được CPU, nó có huynh hướng sử dụng CPU đến khi hết thời gian dành cho nó ? Hoạt động của các tiến trình như thế thường bao gồm một số ít lượt sử dụng CPU , nhưng mỗi lượt trong một thời gian đủ dài.
c) Tiến trình tương tác hay xử lý theo lô : Người sử dụng theo kiểu tương tác thường yêu cầu được hồi đáp tức thời đối với các yêu cầu của họ, trong khi các tiến trình của tác vụ được xử lý theo lô nói chung có thể trì hoãn trong một thời gian chấp nhận được.
d) Độ ưu tiên của tiến trình : Các tiến trình có thể được phân cấp theo một số tiêu chuẩn đánh giá nào đó, một cách hợp lý, các tiến trình quan trọng hơn ( có độ ưu tiên cao hơn) cần được ưu tiên hơn.
e) Thời gian đã sử dụng CPU của tiến trình : Một số quan điểm ưu tiên chọn những tiến trình đã sử dụng CPU nhiều thời gian nhất vì hy vọng chúng sẽ cần ít thời gian nhất để hoàn tất và rời khỏi hệ thống . Tuy nhiên cũng có quan điểm cho rằng các tiến trình nhận được CPU trong ít thời gian là những tiến trình đã phải chờ lâu nhất, do vậy ưu tiên chọn chúng.
f) Thời gian còn lại tiến trình cần để hoàn tất : Có thể giảm thiểu thời gian chờ đợi trung bình của các tiến trình bằng cách cho các tiến trình cần ít thời gian nhất để hoàn tất được thực hiện trước. Tuy nhiên đáng tiếc là rất hiếm khi biết được tiến trình cần bao nhiêu thời gian nữa để kết thúc xử lý.

Giống nhau: cùng điều phối CPU (chọn tiến trình trong Ready Queue để cấp thời gian CPU (chuyển sang trạng thái Running)).

Khác nhau:
- Preemptive Scheduling thì điều phối CPU có tiếm quyền còn Non-Preemptive Scheduling thì điều phối CPU không tiếm quyền.có nghĩa là khi có 1 tiến trình P1,P2,P3 xuất hiện thì nó sẽ thực hiện 1 phần của tiến trình P1 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P2 , sau đó nó tiếm quyền và thực hiện 1 phần của tiến trình P3. Cứ như vậy nó sẽ thực hiện xong các tiến trình.
- Non-Preemptive Scheduling : Có nghĩa là khi có 1 tiến trình P1,P2 xuất hiện thì nó sẽ thực hiện xong tiến trình P1, sau đó mới thực hiện tiến trình P2 (cách làm trong Windows 3.1 và Macintosh OS).

Đây là công thức tính thời gian chờ của tiến trình thứ i
(Công thức này thầy share trên lớp, đảm bảo độ tin cậy - share lại cho các bạn chưa biết)
Ti = (Thời điểm kết thúc - Thời điểm đến) - CPU Burst

Xét ví dụ sau:

Với biểu đồ Gantt:

Áp dụng công thức trên tính thời gian chờ của các tiến trình:
P1 = (55 - 5) - 25 = 25 ms
P2 = (50 - 10) - 15 = 25 ms
P3 = (45 - 20) - 10 = 15 ms
=> Thời gian trung bình: (25+25+15)/3 = 21.6 ms

việc tiếm quyền trong RRS có sự khác biệt so với Preemptive-SJFS cho nên từ trước tới nay khi nói đến RRS mình rất ít dùng từ "tiếm quyền" mà chỉ quan tâm nhiều nhất đến Ready Queue

_ Vậy tiếm quyền trong RRS & Preemptive-SJFS khác nhau thế nào, chúng ta sẽ so sánh để thấy rõ được vấn đề :

-Round Robin
Khi có 1 tiến trình đến...Tiến trình vừa đến được đưa vào cuối Ready Queue cho dù tiến trình đang thực thi đã hết Time Quantum hay chưa
Xét tiến trình được thực thi kế tiếp, theo... Nội dung của Ready Queue
-Preemptive-SJFS

Khi có 1 tiến trình đến... Nếu tiến trình vừa đến có CPU-Burst nhỏ nhất thì nó được thực thi, ngược lại nó bị đưa vào hàng chờ(Ready Queue)
Xét tiến trình được thực thi kế tiếp, theo... Khoảng CPU-Burst của các tiến trình(kể cả tiến trình đang thực thi)
_ Theo bảng so sánh ta thấy rõ một điều, đối với RRS khi một tiến trình mới đến, nó hiển nhiên được đưa vào cuối hàng chờ (Ready Queue) mà không cần quan tâm CPU-Burst của nó hay tiến trình hiện tại đã thực hiện hết Time Quantum hay chưa. Ngược lại đối với Preemptive-SJFS, khi một tiến trình mới đến nếu CPU-Burst của nó là nhỏ nhất(so với tiến trình hiện tại và tất cả các tiến trình đã đến trước đó) thì nó được phép thực thi ngay lập tức.

Admin
- Đơn giản và Rõ ràng ! Sự thể là như vậy.
- Chú ý: Khi có tiến trình mới đến (được khởi tạo), bao giờ cũng được xếp vào Ready Queue đã. Tiếp theo, trình điều phối (CPU Scheduler) dùng Preemptive SJFS sẽ xét các khoảng CPU (với tiến trình đang Running, tính xem thời gian còn lại của nó là bao nhiêu) để chọn tiến trình phù hợp.
- RRS cũng là thuật giải có tiếm quyền: Tiến trình hiện hành hết thời lượng Time-Quantum, sẽ bị tiếm quyền dùng CPU !

Ví dụ về thuật toán Round Robin:
Đề bài:
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 - 3 - 3
P2 - 10 - 20
P3 - 24 - 14

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

Cách làm:
Bảng Gantt:
| P1 | | P2 | P2 | P3 | P3 |
3 6 10 20 30 40 44

Thời gian chờ Trung Bình:
Ttb = [0 + 0 + (30 - 24)]/3 = 2ms

Các con số trong thời gian chờ trung bình :
t1=0 ms(do tiến trình p1 không chờ, nó chạy đúng thời điểm đến)
t2=0 ms(tương tự p1)
t3= 6 ms(do thời điểm đến của tiến trình này là 24 nhung đến thời điểm 30 p3 mới được thực hiện , lúc này nó phải chờ đến 6 ms :thoi diem thuc hien -thoi diem den =30-24 )
ttb=(t1=t2+t3)/3=(0+0+6)/3=2ms

Thêm một ví dụ về thuật toán Round Robin:
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)
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.

tranthephuong(i92c) đã viết:thưa thầy em ko hiểu phần biểu đồ gantt, p1 khi bị tiếm quyền phải bị đưa về cuối vòng chờ, nhưng trên biểu đồ sau khi p2 chạy hết khoản thời gian 10ms đáng lẽ phải đến p3 sau lại là p1

kiến thức còn hạn chế mong thầy chỉ giáo

---


Theo Hiệp nghĩ P1 chạy trước. Vì P3 thời điểm đến phải tiếm quyền 20ms (sau khi p2 chạy 10ms, p1 chạy 10ms nữa. P3 mới chạy)

giải bài tập ôn tập của thầy, không biết đúng không, thầy và các bạn cho ý kiến nhe