Cách giải mới Bài toán Điều phối CPU dùng thuật giải Round-Robin !

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 !

Em vào diễn đàn không thấy bài ở mục bài viết cứ nghĩ viết nhãm bị thầy xóa mất rồi, không ngờ được treo lên phần Chú ý. Em cám ơn Thầy.

Bài giải rất hay, với cách giải này thì không thể nhầm lẫn trước sau giữa các tiến trình.

Không sợ nhầm nữa

Thanks !
Cách giải này rất hay, kết quả rõ ràng. Nều lập bảng như thế này thì chắc chắn sẽ không bao giờ có sự nhầm lẫn giữa các tiến trình.

cách giải của bạn thật hữu ích, dễ hiểu và dễ áp dụng giải bài tập. cám ơn bạn nhiều

hay quá! khỏi sợ tính nhầm nữa.thanks bạn

Cám ơn bạn nhiều. Bài của bạn hay và ý nghĩa nữa

VD rất dễ hiểu, thanks bạn.

Thanks! Bài bạn đăng thật dễ hiểu, ko sợ bị nhầm lẫn nữa.

Cám ơn bạn vì mình sẽ ko sợ nhầm lẫn mất 2 điểm câu bài tập của thầy rồi !!!
Ôi vui quá....

Bài giải rất dễ hiểu và công phu . mình sẽ áp dụng cách giải của bạn vào bài tập . cảm ơn bạn nhiều nha !

Cách giải vẫn vậy nhưng trình bày theo kiểu này dễ hiểu hơn, tránh bị nhầm lẫn

Rất dễ hiểu, thanks bạn!!

Cảm ơn bạn, bài viết rất chi tiết và đầy sáng tạo…một người vì mọi người...

Cám ơn bạn, bài viết thật hữu ích và dễ hiểu.

Thanks bạn !! Cách giải của bạn rất dễ hiểu

Bài viết thật rõ ràng và dễ hiểu
Cảm ơn!

Cam on ban nhieu,

đã ai tìm ra cách giải cho SJFS chưa?

Cảm ơn bạn nhiều lắm vì nhờ bài của bạn mà mình hiểu bài hơn và có cách giải tốt khi làm bài thi.

Giải bài tập kèm theo ví dụ minh họa, rõ ràng, đầy đủ, dễ hiểu, với cách giải này thì lấy trọn 2đ rồi còn gì . Cách giải rất hay, có tính chính xác rất cao !!! Thanks...

Thanks chủ thớt nha! bài giải rất hay

Cách giải hay, cảm ơn bạn đã đưa lên.

Cám ơn bạn, bài viết dễ hiểu