Thuật giải Round - Robin (Thảo luận bài 4 - Đề thi lần 2 (I83C))

Đề 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.

Giải: (Theo biểu đồ Gantt trên lớp giải)
a. Biểu đồ Gantt. (tạm mô tả như thế này nha các bạn)

--------- P1-------- P1--------P2------P1----P3-------P2
|----|----------|----------|----------|----|--------|-------|
----4---------14--------24---------34---38------46-----53

b. Tính thời gian chờ trung bình của các tiến trình:

P1 bắt đầu chạy từ thời điểm là 4 -> ko phải chờ nên thời gian chờ = 0.
chạy tới 24 thì P1 ngưng đến 34 chạy tiếp -> thời gian chờ = 10.
P2 bắt đầu từ 19 nhưng đến 24 mới được chạy -> thời gian chờ = 5.
Chạy đến 34 thì nhưng đến 46 chạy tiếp -> thời gian chờ = 12.
P3 bắt đầu từ 30 nhưng đến 38 mới được chạy -> thời gian chờ = 8.

=> công thức tính
((0 + 10) + (5+12) + 8 ) / 3 = 11.66667 ms

Admin
Theo thày thì lời giải này đúng (thày kiểm tra lại Đáp án sau).

Giải: theo cách mình nghĩ
a. Biểu đồ Gantt. (tạm mô tả như thế này nha các bạn)

--------- P1-------- P1--------P2------P1----P2-------P3
|----|----------|----------|----------|----|--------|-------|
----4---------14--------24---------34---38------45-----53

Biểu đồ Gantt được mô tả như thế này: P2 sẽ chạy trước P3.
Lý do: Khi P2 chạy xong 1 lần 10s. thỉ lúc này ở giây thứ 34. Tất cả P1, P2, P3 đều đã đang ở hàng chờ Ready. Và ta thấy rằng lúc này khoảng CPU của P1 = 4, P2 = 7, P3 = 8 nên theo thuật giải SJFS có tiếm tuyến thì sẽ ưu tiên tiến trình nào có khoảng CPU nhỏ hơn chạy trước. => P1 chạy xong đến P2 chạy xong rồi đến P3.

Không biết là mình nghĩ như thế có đúng ko ạ? Mong thầy và các bạn cho ý kiến.

Admin
Ở milli giây thứ 34, trước hết P2 bị "tiếm quyền" sử dụng CPU và được đưa vào cuối Ready Queue, tức sau P1-P3, sau đó P1 được chọn, Ready Queue bây giờ có P3-P2 !

b. Tính thời gian chờ trung bình của các tiến trình:
Theo cách của mình thì thời gian chờ trung bình của các tiến trình:
( (0 + 10) + (5 + 4) + 15) /3 = 11.3333 ms

a. Biểu đồ Gantt. (tạm mô tả như thế này nha các bạn)

--------- P1-------- P1--------P2------P1----P3-------P2
|----|----------|----------|----------|----|--------|-------|
0----4---------14--------24---------34---38------46-----53


P1 bắt đầu chạy từ thời điểm là 4 -> ko phải chờ nên thời gian chờ = 0.
chạy tới 24 thì P1 ngưng đến 34 chạy tiếp -> thời gian chờ = 10.
P2 bắt đầu từ 19 nhưng đến 24 mới được chạy -> thời gian chờ = 5.
Chạy đến 34 thì nhưng đến 46 chạy tiếp -> thời gian chờ = 12.
P3 bắt đầu từ 30 nhưng đến 38 mới được chạy -> thời gian chờ = 8.
=> công thức tính
((0 + 10) + (5+12) + 8 ) / 3 = 11.66667 ms

Cách dạy trên trường của thấy là đã đúng rồi đó bạn, k có sai đâu

Thường thì mọi người dều bị tắt ở chổ khi p2 =34 thì thuật toán sẽ chạy như thế nào, đây là cách chạy của nó
thời điểm đến (TTD)
*p1 trước đó đã chạy xong và ngưng tại giây 24 nên đã dc đưa vào ready queue và TTD =24
*Sau đó thời điểm p2=34 chạy xong, p2 ngưng và nhảy vào hàng đợi ,TTD p2 lúc này sẽ dc tính là 34
*Khi p2 xong ta có p1 và p3 . TTD p1=24 , TTD p3=30 nên p1 dc ưu tiên xử lý. P1 dc đưa vào và kết thúc tiến trình tại thời điểm p1=38
* Khi p1 xong thì ta xét p2,p3. p2 TTD= 34 như ở trên đã nói, TTD p3=30 nên p3 dc ưu tiên xử lý
p3 dc xử lý và kết thúc tạo t =46
* P2 cuối cùng dc xử lý và kết thúc 5ai t=53
Kết thúc thuật giải

Time TB= ((0+10) + (5 + 12) + /3=11.66667 ms

Thuât giải RoundRobin là thuật giải vừa xử lý xoay vòng, vừa xét theo thời gian đến (ms) đến. Nên ta fai xét cả thời gian đến của tt khi tt đó đưa vào ready queue, tt nào thời gian đến thấp thì ưu tiên dc xử lý trước

Mình ko có nói là bài thầy sửa trên lớp là ko đúng. Vì mình nghĩ như thế nên mình nói ra thôi. Vì lúc ở trên lớp mình chưa hiểu vì sào P3 lại chạy trước P2. Nhưng bây giờ sau khi bạn nói thế thì mình okie rùi. Cảm ơn bạn nhé. Mình hiểu rồi.

PhamLy_09H1010053 đã viết:Đề 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.

Giải: (Theo biểu đồ Gantt trên lớp giải)
a. Biểu đồ Gantt. (tạm mô tả như thế này nha các bạn)

--------- P1-------- P1--------P2------P1----P3-------P2
|----|----------|----------|----------|----|--------|-------|
----4---------14--------24---------34---38------46-----53

b. Tính thời gian chờ trung bình của các tiến trình:

P1 bắt đầu chạy từ thời điểm là 4 -> ko phải chờ nên thời gian chờ = 0.
chạy tới 24 thì P1 ngưng đến 34 chạy tiếp -> thời gian chờ = 10.
P2 bắt đầu từ 19 nhưng đến 24 mới được chạy -> thời gian chờ = 5.
Chạy đến 34 thì nhưng đến 46 chạy tiếp -> thời gian chờ = 12.
P3 bắt đầu từ 30 nhưng đến 38 mới được chạy -> thời gian chờ = 8.

=> công thức tính
((0 + 10) + (5+12) + 8 ) / 3 = 11.66667 ms



Giải: theo cách mình nghĩ
a. Biểu đồ Gantt. (tạm mô tả như thế này nha các bạn)

--------- P1-------- P1--------P2------P1----P2-------P3
|----|----------|----------|----------|----|--------|-------|
----4---------14--------24---------34---38------45-----53

Biểu đồ Gantt được mô tả như thế này: P2 sẽ chạy trước P3.
Lý do: Khi P2 chạy xong 1 lần 10s. thỉ lúc này ở giây thứ 34. Tất cả P1, P2, P3 đều đã đang ở hàng chờ Ready. Và ta thấy rằng lúc này khoảng CPU của P1 = 4, P2 = 7, P3 = 8 nên theo thuật giải SJFS có tiếm tuyến thì sẽ ưu tiên tiến trình nào có khoảng CPU nhỏ hơn chạy trước. => P1 chạy xong đến P2 chạy xong rồi đến P3.

Không biết là mình nghĩ như thế có đúng ko ạ? Mong thầy và các bạn cho ý kiến.

b. Tính thời gian chờ trung bình của các tiến trình:
Theo cách của mình thì thời gian chờ trung bình của các tiến trình:
( (0 + 10) + (5 + 4) + 15) /3 = 11.3333 ms

1. Về bài giải trên lớp:
Bài giải này không sai !
Nhưng có một vấn đề mình không hiểu tại sao đề bài lại cho thời điểm
bắt đầu cua P1 = 4. Có thể đề cho thêm để khác trong slide bài giảng.
Vậy thực tế có nên tính thêm khoảng thời gian trước khi P1 bắt đầu không ?
Không tính cũng đúng vì hệ thống đề bài cho la chỉ có 3 tiến trinh.

2. Về bài giải của bạn.
Mình nghĩ là bạn bị hiểu nhầm ý nghĩa của "tiếm quyền"
Theo thuật giải SJFS: Nếu tiến trình mới đến có khoảng CPU kế tiếp nhỏ hơn so với thời gian còn lại của tiến trình đang hiện hành thì bị tiếm quyền.
Theo thuật giải RRS: Nếu tiến trình đang chạy bị hết thời lượng (quantum) thì sẽ bi tiếm quyền

Tiếm quyền ở 2 thuật giải là khác nhau.
_____________________________

Software development group: BoB

Nguyen Phuc Bao Chau
Email: baochau183@yahoo.com
Phone: 090 9 581 384
Sky: baochau183
Y!H: baochau183

Nếu như theo lời phân tích của bạn Minh là đúng thì bài toán đó ok rồi,ko biết có ai còn có cách giải khác ko để chúng ta cùng thảo luận.Đừng để tới khi thi rồi phát hiện sai thì chết.Hihi

tri_09h1010091 đã viết:Nếu như theo lời phân tích của bạn Minh là đúng thì bài toán đó ok rồi,ko biết có ai còn có cách giải khác ko để chúng ta cùng thảo luận.Đừng để tới khi thi rồi phát hiện sai thì chết.Hihi

Theo cách thuật giải thì chỉ có 1 đáp án thôi bạn à!Bạn Minh giải thích thế là chi tiết lắm rồi!Mình cũng định post mà vô ăn cơm ra có người đáp án rồi!hết được giải thích buồn ghê! hehhehehe..Dù sao cũng thks Minh nhé

DucDuyI91C đã viết:

tri_09h1010091 đã viết:Nếu như theo lời phân tích của bạn Minh là đúng thì bài toán đó ok rồi,ko biết có ai còn có cách giải khác ko để chúng ta cùng thảo luận.Đừng để tới khi thi rồi phát hiện sai thì chết.Hihi

Theo cách thuật giải thì chỉ có 1 đáp án thôi bạn à!Bạn Minh giải thích thế là chi tiết lắm rồi!Mình cũng định post mà vô ăn cơm ra có người đáp án rồi!hết được giải thích buồn ghê! hehhehehe..Dù sao cũng thks Minh nhé

K có gì, ban đầu trong lớp thấy cách thầy giải thì cũng k hiểu lắm. Về lục lọi, tìm kiếm, nhờ sư phụ chỉ bảo tá lả mới hiểu dc đó

Cám ơn các bạn nha. Ở lớp mình chưa hiểu lắm nghĩa là khi thực hiện vòng chạy này chủ yếu dựa vào thời điểm đến phải không ! Tiến trình nào có thời điểm đến trước sẽ ưu tiên thực hiện trước phải không ? bạn nào giúp mình nha

Thanks Minh nhieu!Ban giai thich kha ro rang

Bài giải tốt quá, thanks bạn nhiều

Thank you !

Ban dau minh cung giai ra dap an la so le ma ko biet dung hay sai ,gio biet ket qua roi cam on ban nhieu :!

Tran Hoang Minh đã viết:

a. Biểu đồ Gantt. (tạm mô tả như thế này nha các bạn)

--------- P1-------- P1--------P2------P1----P3-------P2
|----|----------|----------|----------|----|--------|-------|
0----4---------14--------24---------34---38------46-----53


P1 bắt đầu chạy từ thời điểm là 4 -> ko phải chờ nên thời gian chờ = 0.
chạy tới 24 thì P1 ngưng đến 34 chạy tiếp -> thời gian chờ = 10.
P2 bắt đầu từ 19 nhưng đến 24 mới được chạy -> thời gian chờ = 5.
Chạy đến 34 thì nhưng đến 46 chạy tiếp -> thời gian chờ = 12.
P3 bắt đầu từ 30 nhưng đến 38 mới được chạy -> thời gian chờ = 8.
=> công thức tính
((0 + 10) + (5+12) + 8 ) / 3 = 11.66667 ms

Cách dạy trên trường của thấy là đã đúng rồi đó bạn, k có sai đâu

Thường thì mọi người dều bị tắt ở chổ khi p2 =34 thì thuật toán sẽ chạy như thế nào, đây là cách chạy của nó
thời điểm đến (TTD)
*p1 trước đó đã chạy xong và ngưng tại giây 24 nên đã dc đưa vào ready queue và TTD =24
*Sau đó thời điểm p2=34 chạy xong, p2 ngưng và nhảy vào hàng đợi ,TTD p2 lúc này sẽ dc tính là 34
*Khi p2 xong ta có p1 và p3 . TTD p1=24 , TTD p3=30 nên p1 dc ưu tiên xử lý. P1 dc đưa vào và kết thúc tiến trình tại thời điểm p1=38
* Khi p1 xong thì ta xét p2,p3. p2 TTD= 34 như ở trên đã nói, TTD p3=30 nên p3 dc ưu tiên xử lý
p3 dc xử lý và kết thúc tạo t =46
* P2 cuối cùng dc xử lý và kết thúc 5ai t=53
Kết thúc thuật giải

Time TB= ((0+10) + (5 + 12) + /3=11.66667 ms

Thuât giải RoundRobin là thuật giải vừa xử lý xoay vòng, vừa xét theo thời gian đến (ms) đến. Nên ta fai xét cả thời gian đến của tt khi tt đó đưa vào ready queue, tt nào thời gian đến thấp thì ưu tiên dc xử lý trước

Cảm ơn bạn nhiều, vì ở trên lớp mình cũng không hiểu cách tính P2 và P3, giờ thình mình đã hiểu về thuật toán này rồi.

thanks!

thanks

Mừng quá, mình cũng đang không hiểu lắm chổ này. Giờ thì...hieu hieu chut chut rồi. Cám ơn các bạn nhiều

bai giai cua ban kha chi tiet, thanks

Nhờ bài giải của bạn mình hiểu thêm được nhiều điều. Thanks so much!!