Điều phối tiến trình dùng thuật giải Round - Robin

NguyenBacHoi(I22B) đã viết:Ví dụ với bài toán thầy cho.
-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

Tiến trình	Thời điểm đến(ms)	CPU-Burst(ms)
(Vận động viên)	(Cự ly xuất phát)	(Thời gian chạy)
P1	10	30
P2	20	35
P3	25	15

Dùng thuật giải Round-Robin với thời lượng 20ms để điều phối CPU
a) Biểu đồ Gantt.
b) Tính thời gian chờ trung bình.
Giải :
Giả sử P1, P2, P3 là 3 vận động viên trong cuộc chạy tiếp sức. Thời điểm đến ở đây chúng ta hiểu nôm na là cự ly xuất phát của 3 vận động viên, P1 xuất phát ở cự ly 10, P2 xuất phát ở cự ly 20 tương tự đến P3 xuất phát ở cự ly 25. CPU-Burst ở đây chúng ta hiểu là thời gian chạy phù hợp với sức khỏe của 3 vận động viên. Thời lượng ở đây là thời gian tối đa cho phép cho mỗi lần chạy. Ở bài toán trên ta thấy THỜI GIAN CHẠY của vận động viên P1 là 30(ms) nhưng thời gian chạy cho phép là 20(ms) thì chúng ta có thể hiểu vận động viên P1 sẽ chạy 2 lần để hoàn thành hết thời gian chạy 30(ms) của mình.
Áp dụng bảng trợ giúp ta có:
Cự ly xuất phát của P1 ngắn nhất 10 nên P1 sẽ chạy trước với thời lượng T=20. Ta sẽ được:

T = 20ms	P1	P2	P3
	10(30)	20(35)	25(15)
P1	30(10)	20(35)	25(15)

P1 chạy với thời lượng T=20 đạt cự ly là 30 = |10 20| và thời lượng còn lại của P1 là 30 – 20 = 10(ms). Lúc này so sánh giữa P1, P2, P3 thì P2 có khoảng cách nhỏ hơn P1 và P3, ta sẽ hiểu P1 chạy với thời lượng T=20(ms) đã vượt qua P2 và P1 sẽ dừng lại nghỉ để P2 tiếp tục chạy tiếp sức cho P1 ở cự ly mà P1 đã dừng với thời lượng của P2 = 35 sẽ còn lại là 35 – 20 = 15(ms).

T = 20ms	P1	P2	P3
	10(30)	20(35)	25(15)
P1	30(10)	20(35)	25(15)
P2	30(10)	50(15)	25(15)

Tiếp tục so sánh thì P3 sẽ nhỏ hơn so với P1, P2 nên P3 sẽ tiếp tục chạy từ cự ly đã dừng của P2 với thời lượng của P3 là 15(ms)(mỗi lần chạy tối đa là 20ms nhưng có thể hiểu do sức khỏe P3 yếu nên chỉ chạy được 15ms rồi dừng) và thời lượng còn lại của P3 : 0(ms).

T = 20ms	P1	P2	P3
	10(30)	20(35)	25(15)
P1	30(10)	20(35)	25(15)
P2	30(10)	50(15)	25(15)
P3	30(10)	50(15)	65(0)

Vì thời gian còn lại của P3 = 0(ms) nên lúc này ta chỉ so sánh giữa P1 và P2. P1 nhỏ hơn nên P1 sẽ tiếp tục chạy ở cự ly mà P3 đã dừng với thời lượng là 10(ms) và khi kết thúc sẽ còn thời lượng là 0(ms).

T = 20ms	P1	P2	P3
	10(30)	20(35)	25(15)
P1	30(10)	20(35)	25(15)
P2	30(10)	50(15)	25(15)
P3	30(10)	50(15)	65(0)
P1	75(0)	50(15)	65(0)

Cuối cùng là P2 sẽ chạy hết khoảng thời lượng còn lại vì thời lượng P1 và P3 đã hết với cự ly mà P1 đã dừng lại trước đó.

T = 20ms	P1	P2	P3
	10(30)	20(35)	25(15)
P1	30(10)	20(35)	25(15)
P2	30(10)	50(15)	25(15)
P3	30(10)	50(15)	65(0)
P1	75(0)	50(15)	65(0)
P2	75(0)	90(0)	65(0)

Áp dụng bảng trợ giúp này giúp ta vẽ biểu đồ Gantt nhanh hơn so với việc so sánh từng tiến trình rồi vẽ rồi lại tiếp tục so sánh từng tiến trình rồi vẽ tiếp..Nhìn vào bảng trợ giúp ta sẽ biết từ điểm bắt đầu là 10 đi đến 30 là P1(hàng 3), tiếp đến sẽ là P2 nhìn đối chiếu với cột P2 ta được P2 sẽ đi đến 50, rồi đến lượt P3 đi đến 65 rồi đến P1 đi đến 75…
Biểu đồ Gantt :

P1

P2

P3

P1

P2

10--------------------30--------------------50----------------65------------75------------90
Thời gian chờ trung bình : Ti = (Thời điểm kết thúc – Thời điểm đến) – Khoảng CPU
Thời gian chờ trung bình của từng tiến trình:
• P1 = (75 - 10) – 30 = 35(ms)
• P2 = (90 - 20) – 35 = 35(ms)
• P3 = (65 - 25) – 15 = 25(ms)
Thời gian chờ trung bình : (35 + 35 + 25) / 3 = 31,5(ms)
Cách giải thì vẫn vậy không mới mẻ gì nhưng với mình việc ghi ra từng tiến trình như vậy sẽ giúp chúng ta không bị nhầm khi vừa so sánh rồi tính rồi vẽ. Ở đây mình tính toán ở bảng trợ giúp hết rồi nhìn vào đó vẽ biểu đồ Gantt như vậy sẽ tiết kiệm thời gian hơn khi mình vừa vẽ vừa quay ngược lên bảng trợ giúp để tính.
Các bạn tham khảo và cho ý kiến. Cám ơn!!!

Admin
- Thêm Cột 1 với các tiến trình Pi được chọn và Tách bạch việc Xây dựng Bảng trợ giúp với Vẽ Biểu đồ Gantt như trên là Buớc tiến của Công nghệ giải bài tập RRS !
- "Đặt" T=20ms ở Góc trái trên của bảng là rất Khéo và Tinh tế !
- Đồng ý với đề xuất này !

PhamTanKyNam(I22B) đã viết:Đây là bài đóng góp của một bạn lớp trước mình từng học, thiết nghĩ viết lại thì hơi mất thời gian với lại cách trình bài của bạn cũng dễ hiểu nên mình xin mượn tạm để các bạn chưa hiểu thì có chỗ để tham khảo  . Nội dung này khá quan trọng khi thi nên các bạn nên nhuần nhuyễn cách giải bài tập này. Lần trước thi cũng hiểu bài nhưng do trình bày không được rõ ràng nên điểm thấp phải học lại   

NguyenBacHoi(I22B) đã viết:Ví dụ với bài toán thầy cho.
-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

Tiến trình	Thời điểm đến(ms)	CPU-Burst(ms)
(Vận động viên)	(Cự ly xuất phát)	(Thời gian chạy)
P1	10	30
P2	20	35
P3	25	15

Dùng thuật giải Round-Robin với thời lượng 20ms để điều phối CPU
a) Biểu đồ Gantt.
b) Tính thời gian chờ trung bình.
Giải :
Giả sử P1, P2, P3 là 3 vận động viên trong cuộc chạy tiếp sức. Thời điểm đến ở đây chúng ta hiểu nôm na là cự ly xuất phát của 3 vận động viên, P1 xuất phát ở cự ly 10, P2 xuất phát ở cự ly 20 tương tự đến P3 xuất phát ở cự ly 25. CPU-Burst ở đây chúng ta hiểu là thời gian chạy phù hợp với sức khỏe của 3 vận động viên. Thời lượng ở đây là thời gian tối đa cho phép cho mỗi lần chạy. Ở bài toán trên ta thấy THỜI GIAN CHẠY của vận động viên P1 là 30(ms) nhưng thời gian chạy cho phép là 20(ms) thì chúng ta có thể hiểu vận động viên P1 sẽ chạy 2 lần để hoàn thành hết thời gian chạy 30(ms) của mình.
Áp dụng bảng trợ giúp ta có:
Cự ly xuất phát của P1 ngắn nhất 10 nên P1 sẽ chạy trước với thời lượng T=20. Ta sẽ được:

T = 20ms	P1	P2	P3
	10(30)	20(35)	25(15)
P1	30(10)	20(35)	25(15)

P1 chạy với thời lượng T=20 đạt cự ly là 30 = |10 20| và thời lượng còn lại của P1 là 30 – 20 = 10(ms). Lúc này so sánh giữa P1, P2, P3 thì P2 có khoảng cách nhỏ hơn P1 và P3, ta sẽ hiểu P1 chạy với thời lượng T=20(ms) đã vượt qua P2 và P1 sẽ dừng lại nghỉ để P2 tiếp tục chạy tiếp sức cho P1 ở cự ly mà P1 đã dừng với thời lượng của P2 = 35 sẽ còn lại là 35 – 20 = 15(ms).

T = 20ms	P1	P2	P3
	10(30)	20(35)	25(15)
P1	30(10)	20(35)	25(15)
P2	30(10)	50(15)	25(15)

Tiếp tục so sánh thì P3 sẽ nhỏ hơn so với P1, P2 nên P3 sẽ tiếp tục chạy từ cự ly đã dừng của P2 với thời lượng của P3 là 15(ms)(mỗi lần chạy tối đa là 20ms nhưng có thể hiểu do sức khỏe P3 yếu nên chỉ chạy được 15ms rồi dừng) và thời lượng còn lại của P3 : 0(ms).

T = 20ms	P1	P2	P3
	10(30)	20(35)	25(15)
P1	30(10)	20(35)	25(15)
P2	30(10)	50(15)	25(15)
P3	30(10)	50(15)	65(0)

Vì thời gian còn lại của P3 = 0(ms) nên lúc này ta chỉ so sánh giữa P1 và P2. P1 nhỏ hơn nên P1 sẽ tiếp tục chạy ở cự ly mà P3 đã dừng với thời lượng là 10(ms) và khi kết thúc sẽ còn thời lượng là 0(ms).

T = 20ms	P1	P2	P3
	10(30)	20(35)	25(15)
P1	30(10)	20(35)	25(15)
P2	30(10)	50(15)	25(15)
P3	30(10)	50(15)	65(0)
P1	75(0)	50(15)	65(0)

Cuối cùng là P2 sẽ chạy hết khoảng thời lượng còn lại vì thời lượng P1 và P3 đã hết với cự ly mà P1 đã dừng lại trước đó.

T = 20ms	P1	P2	P3
	10(30)	20(35)	25(15)
P1	30(10)	20(35)	25(15)
P2	30(10)	50(15)	25(15)
P3	30(10)	50(15)	65(0)
P1	75(0)	50(15)	65(0)
P2	75(0)	90(0)	65(0)

Áp dụng bảng trợ giúp này giúp ta vẽ biểu đồ Gantt nhanh hơn so với việc so sánh từng tiến trình rồi vẽ rồi lại tiếp tục so sánh từng tiến trình rồi vẽ tiếp..Nhìn vào bảng trợ giúp ta sẽ biết từ điểm bắt đầu là 10 đi đến 30 là P1(hàng 3), tiếp đến sẽ là P2 nhìn đối chiếu với cột P2 ta được P2 sẽ đi đến 50, rồi đến lượt P3 đi đến 65 rồi đến P1 đi đến 75…
Biểu đồ Gantt :

P1

P2

P3

P1

P2

10--------------------30--------------------50----------------65------------75------------90
Thời gian chờ trung bình : Ti = (Thời điểm kết thúc – Thời điểm đến) – Khoảng CPU
Thời gian chờ trung bình của từng tiến trình:
• P1 = (75 - 10) – 30 = 35(ms)
• P2 = (90 - 20) – 35 = 35(ms)
• P3 = (65 - 25) – 15 = 25(ms)
Thời gian chờ trung bình : (35 + 35 + 25) / 3 = 31,5(ms)
Cách giải thì vẫn vậy không mới mẻ gì nhưng với mình việc ghi ra từng tiến trình như vậy sẽ giúp chúng ta không bị nhầm khi vừa so sánh rồi tính rồi vẽ. Ở đây mình tính toán ở bảng trợ giúp hết rồi nhìn vào đó vẽ biểu đồ Gantt như vậy sẽ tiết kiệm thời gian hơn khi mình vừa vẽ vừa quay ngược lên bảng trợ giúp để tính.
Các bạn tham khảo và cho ý kiến. Cám ơn!!!

Admin
- Thêm Cột 1 với các tiến trình Pi được chọn và Tách bạch việc Xây dựng Bảng trợ giúp với Vẽ Biểu đồ Gantt như trên là Buớc tiến của Công nghệ giải bài tập RRS !
- "Đặt" T=20ms ở Góc trái trên của bảng là rất Khéo và Tinh tế !
- Đồng ý với đề xuất này !