Bài Tập Tham Khảo Các Giải Thuật điều Phối CPU(RRS-FCFS)

Tin họcBạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.Tin học

Cơ sở lập trình-Công nghệ phần mềm-Hệ điều hành

• Trang Chính
• Latest images
• Tìm kiếm

  Tìm kiếm

  Display results as :Số bàiChủ đề

  Advanced Search

• Đăng ký
• Đăng Nhập

Bài tập tham khảo các giải thuật điều phối CPU(RRS-FCFS)

Tin học :: Your first category :: Lớp I22A-I22B

Trang 1 trong tổng số 1 trang

Bài tập tham khảo các giải thuật điều phối CPU(RRS-FCFS)

NguyenThanhSoai(I22A) 29/3/2013, 00:47

Bài 1 : Thuật giải Round - Robin schedulingTiến trình Thời điểm CPU - Burst (ms)P1 3 37P2 10 20P3 24 14Dùng giải thuật Round - Robin với thời lượng 10ms để điều phối CPUa. Thể hiện bằng biểu đồ Ganttb. Tính thời gian chờ trung bình của các tiến trìnhGiảiBIỂU ĐỒ GANTT:- Điểm lưu ý khi vẽ:+ Mỗi tiến trình được cấp 1 thời lượng CPU (Time Quantum) là số q ms nào đó.+ Hết thời gian q, thì tiến trình hiện tại sẽ bị tiến trình khác tiếm quyền nếu tiến trình mới này có thời điểm đến = hoặc < thời điểm đang xét. Đồng thời tiến trình cũ sẽ được đưa vào hàng đợi Ready+ Tiến trình đầu tiên trong hàng đợi sẽ được chọn để tiếm quyền kế tiếp- Vẽ biểu đồ:- Giải thích:(lưu ý với thuật toán này mình nhớ xem xét thời điểm đề cho là thời điểm đến của các tiến trình)Theo đề bài này thì CPU bắt đầu cấp phát cho 3 tiến trình P1, P2, P3 là thời điểm 3 và hàng đợi Ready làP1 P2 P3+ Tại thời điểm 3, P1 đứng đầu hàng đợi Ready, như vậy P1 được chọn cho vận hành+ Vì q=10ms nên tại thời điểm 13, P1 tạm dừng vận hành và bị đẩy về cuối hành đợi ReadyP2 P3 P1Như vậy P2 lúc này đứng đầu hàng đợi và xét lại thì thấy thời điểm đến của P2 là 10 < 13, nên P2 được phép tiếm quyền kế tiếp để vận hành+ Vì q=10ms nên đến thời điềm 23, P2 phải tạm dừng cho tiến trình khác vận hành và P2 bị đẩy về cuối hàng đợiP3 P1 P2Lúc này ta thấy P3 đứng đầu hàng đợi nhưng thời điểm đến của P3 là 24 > 23 (là thời điểm đang xét) nghĩa là tại thời điểm này P3 chưa có nhu cầu để vận hành, nên P3 sẽ hok tiếm quyền P2. P3 sẽ bị đẩy về cuối hàng đợi. Hàng đợi lúc này làP1 P2 P3Do P1 được đẩy lên đầu nên P1 được phép tiếm quyền kế tiếp tại thời điểm 23 này.+ Cứ sau 10ms, ta lại xét để cho vận hành tiến trình kế tiếp là tiến trình nào.Tại thời điểm 33, P1 tạm dừng và bị đẩy về cuối hàng đợi ReadyP2 P3 P1P2 đứng đầu hàng đợi sẽ lên tiếm quyền kế tiếp.+ Tại thời điểm 43, sau khi P2 vận hành 10ms thì lúc này P2 cũng vừa vận hành xong. Vì vậy P2 sẽ không nằm trong hàng đợi Ready. Ta có hàng đợi làP3 P1Ta thấy lúc này P3 mới bắt đầu vận hành vì nó đã có nhu cầu vận hành từ lúc thời điểm 24+ Thời điểm 53, P3 tạm dừng và đưa vào cuối hàng đợiP1 P3Đồng thời P1 sẽ được ưu tiên lên tiếm quyền tiếp tục vận hành+Thời điểm 63, P1 tạm dừng, P3 lên tiếm quyền và nó chỉ cần thêm 4ms nữa là P3 vận hành xong tiến trình của nó. Lúc này nó cũng hok còn nằm trong hàng đợi. Hàng đợi chỉ còn có P1+ Do đó tại thời điểm 67, P1 được vận hành và nó vận hành hết 7ms nữa là thời gian còn lại cần cho P1Dựa vào biểu đồ Gantt ta tính thời gian chờ trung bìnhTHỜI GIAN CHỜ TRUNG BÌNHTtb = (T1 + T2 +...+ Tn)/n(thời gian chờ của mỗi tiến trình = tổng thời gian tiến trình đó bị gián đoạn)T1 = (3 -3)+ (23 - 13) + (53 - 33) + (67 - 63) = 34T2 = (13 -10) + (33- 23) = 13T3 = (43- 24) + (63 - 53) = 29===> Ttb = (34 + 13 + 29) / 3 = 25.33 msBài 2 : FCFS (First Come First Served): Đến trước có trướcGiả sử một hệ thống có 5 tiến trình đến vào các thời điểm với các tính chất sau:a) Vẽ 4 biểu đồ Gantt tương ứng với thuật giải điều phối FCFS và RRS (với thời lượng = 1)b) Tính thời gian chờ trung bình của các tiến trình.Giải:Ta có DS các TT:Biểu đồ Gant như sau:Để tìm thời gian chờ ta xem hình vẽ điều phối các tiến trình theo FCFSVậy:Thời gian chờ:W = W1+W2+W3 = 3 + 4 + 13 = 20 msThời gian chờ trung bình = 20/5 = 4msGiải thích:P2: chạy từ giây đầu tiên do đến trước (theo FCFS) nên không phải chờ. Thời gian P2 chạy là 1s (0 ->1)P5: chạy tiếp theo sau P2, cũng không phải chờ vì P2 đã chạy xong ở giây thứ 1. P5 chạy hết từ 1 -> 5P3: đến từ giây thứ 2, nhưng lúc đó P5 đang chạy nên phải đứng chờ cho P5 chạy hết ( chờ từ 2->5, W1 = 3). Sau giây thứ 5, P3 mới được chạy và chạy trong 2s ( 5->7)P1: đến từ giây thứ 3, lúc này P5 cũng đang chạy, sau P5 thì P3 đã được ưu tiên đi trước nên P1 tiếp tục chờ (chờ từ 3->7, W2=4). P3 chạy xong, P1 mới được đi. P1 chạy 10s từ (7 -> 17)P4 chạy sau cùng do đến chậm nhất (giây thứ 4) và cũng phải chờ cho P3 & P1 chạy xong (chờ từ 4 -> 17, W3=13). Rồi P4 chạy tiếp 17->18.FinishVậy thì Tổng thời gian chờ: W = W1 + W2 + W3 = 3 + 4 + 13 = 20s 2 bài này mình tìm trên mạng,mọi người tham khảo thử nha NguyenThanhSoai(I22A)Tổng số bài gửi : 5Join date : 15/03/2013 LikeDislike

Similar topics Similar topics» Mời các bạn tham khảo code thuật giải FCFS» Thảo luận Bài 6» Giải thuật điều phối FCFS» Thuật giải điều phối SJF. và FCFS » Thảo luận Bài 6

Tin học :: Your first category :: Lớp I22A-I22B

Trang 1 trong tổng số 1 trangChuyển đến: Chọn Diễn Đàn||--Your first category |--Nhập môn CNPM |--Toán học rời rạc |--Nhập môn lập trình |--Phân tích thiết kế HTTT |--Lớp HLT3 |--Lớp I22A-I22B |--Lớp HC11TH3A |--Hoàn chỉnh kiến thức I12A |--Ôn thi Tốt nghiệp |--Hoàn chỉnh kiến thức I11C |--Hoàn chỉnh kiến thức 102C |--Hoàn chỉnh kiến thức I92C |--CNTT Phan Thiết (K1) |--Hoàn chỉnh kiến thức I91C |--Hoàn chỉnh kiến thức I82C |--Hoàn chỉnh kiến thức I83C Permissions in this forum:Bạn không có quyền trả lời bài viết

• Trang Chính
• Free forum | ©phpBB | Free forum support | Báo cáo lạm dụng | Thảo luận mới nhất