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

Trang 2 trong tổng số 2 trang Previous  1, 2

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down

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

Bài gửi  NguyenHongAn(I22B) on 16/4/2013, 22:23

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)
P110 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)
P130(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)
P130(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)
P130(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)
P130(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)
P130(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!!! Very Happy

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 !
Bài rất dễ hiểu,tks bạn !

NguyenHongAn(I22B)

Tổng số bài gửi : 20
Join date : 16/03/2013
Age : 26

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  dangvandinhI22A on 17/4/2013, 14:07

Rat ro rang va de hieu.thanks ban nha!

dangvandinhI22A

Tổng số bài gửi : 12
Join date : 12/04/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  HuynhHuuTai(I22A) on 26/4/2013, 10:35

Very Happy cuối cùng cũng có 1 thuật toàn hoàn chỉnh 0 sợ nhầm , thank thầy và mọi người nhiều nhiều Very Happy

HuynhHuuTai(I22A)

Tổng số bài gửi : 31
Join date : 12/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  VANCONGLOI(I22A) on 20/6/2013, 02:39

Cám ơn bạn rất nhiều.

VANCONGLOI(I22A)

Tổng số bài gửi : 22
Join date : 09/03/2013
Age : 26
Đến từ : Bình thuận

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  MaiNguyenThanhLong(I22A) on 20/6/2013, 20:26

Thanks ban nhieu . Cach giai cua ban cu the lam khong so bi nham lan nua Very Happy

MaiNguyenThanhLong(I22A)

Tổng số bài gửi : 16
Join date : 13/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  TranQuocLoc(I22A) on 22/6/2013, 23:15

Ý tưởng quá hay! Nhưng hình như vi phạm quy tắc "Ngắn gọn, Súc tích" của thầy Very Happy

TranQuocLoc(I22A)

Tổng số bài gửi : 10
Join date : 09/03/2013
Age : 26
Đến từ : Bà Rịa- Vũng Tàu

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  NguyenThienChuongI22A on 23/6/2013, 01:03

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)
P110 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)
P130(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)
P130(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)
P130(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)
P130(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)
P130(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!!! Very Happy

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 !
 
Trình bày dài như thế này đi thi liệu có đủ thời gian làm bài không nhỉ

NguyenThienChuongI22A

Tổng số bài gửi : 6
Join date : 22/03/2013

Xem lý lịch thành viên

Về Đầu Trang Go down

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

Bài gửi  Sponsored content Today at 14:48


Sponsored content


Về Đầu Trang Go down

Trang 2 trong tổng số 2 trang Previous  1, 2

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết