Cách giải bài tập định thời CPU

Chia sẻ: Nguyễn Vũ Minh Tâm | Ngày: | Loại File: DOC | Số trang:7

Thêm vào BST

Báo xấu

1.544
lượt xem 133
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu hướng dẫn cách giải bài tập định thời CPU. Tài liệu chỉ mang tính chất tham khảo.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cách giải bài tập định thời CPU

Cách giải bài tập định thời CPU Đề toán : Process__Arrival Time_______Service Time 1___________0________________3 2___________2________________7 3___________4________________3 4___________6________________5 5___________8________________2 *Tiền hành công các móc thời gian lại để bắt đầu tình bước đi AT(Arival Time)=2+4+6+8=20 ST(Service Time)=3+7+3+5+2=20 Biểu đồ: |--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--| 0____________5___________10____________15_________ __20 Cách tìm : FCFS (First Come-First Serve) Cái này không cần phải suy nghĩ nhiều cho mệt.Cái nào đến trước xử lý trước.FCFS này dựa vào khoảng thời gian của Service Time thôi.Như vậy ta có biểu đồ sau : |--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--| 0_______3_________________10______13__________18__ __20 ____P1___________P2___________P3________P4________ P5 Đoạn (0-3) là P1 (3-10) là P2 (10-13) là P3 (13-18) là P4 (18-20) là P5 :smiles (54): Cách tìm : SJF (Sortest Job First) Cái này bắt đầu việc so sánh giữa AT và ST rồi đó .CÁch giải là cái nào thời gian xử lý ngắn hơn được quyền xử lý trước thôi.Dựa vào dâu để biết thời gian ngắn hơn ??? Ta có :
Process__Arrival Time_______Service Time 1___________0________________3 2___________2________________7 Như vậy Process 1 thời gian từ 0-3=3 2 // 2-7=5 ->>Process 1 ngắn hơn nên được quyền xử lý trước, nhưng không ưu tiên Bắt đầu vào cách tính : Ờ đây chúng ta chỉ đi được từng đoạn một trong biểu đồ thời gian thôi : *Process 1 (P1) sẽ đi một bước , sau khi đi xong nó sẽ so sánh với Process kế tiềp là Process 2 (P2) >> vẫn chưa đủ cho P2 vào nên nó đi tiếp bước thứ 2.Lúc này P2 đã được phép vào >Nhưng ở đây nó sẽ so sánh tiếp thời gian nào ngắn hơn giữa P1 và P2 .Ta thấy P1 có thời gian ngắn hơn (giải thích ở trên) nên nó đai tiếp bước thứ 3.Vậy là P1 đã xử lý xong. *Process 2 (P2) : P2 được quyền đi tiếp bước 4 lúc này P3 được vào nhưng do không có quyền ưu tiên nên P2 đi hết các các còn lại cùa nó.Vậy là tiền trình đã đi được 10 bước.Lúc này thì tất cả các Process đều được vào rồi >> nó sẽ so sánh xem thời gian của P nào có thời gian ngắn nhất nó sẽ thực hiện trước .Như vậy các bạn sẽ thấy rằng 2, 3, 5 .Các tiền trình được phép đi tiếp theo là P5, P3 , P4 Biểu đồ : |--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--| 0_______3________________10____12______15_________ __20 (0-3) : P1 (3-10) : P2 (10-12) 5 (12-15) 3 (15-20) 4 Xong !!!:smiles: Cách tìm : SRTF (Sortest Remaining Time First) Cách tìm này cũng giống như tìm SJF nhưng ở đây chúng ta chú ý một chút là thời gian ngắn xử lý trước có ưu tiên.:smiles (148): Process__Arrival Time_______Service Time 1___________0________________3 2___________2________________7 3___________4________________3 4___________6________________5
5___________8________________2 Chúng ta vào cách tính như sau: Ban đầu P1 sẽ đi bước 1, sau khi đi xong P1 sẽ so sánh số bước đi (đồng nghĩa với thời gian đã xử lý) với P2 , ta thấy vẫn chưa đủ số bước đi để P2 vào nên P1 đi tiếp thêm bước 2, nó sẽ quay lại so sánh tiếp số bước của P2.Lúc này P2 đã được phép .Nhưng nó sẽ so sánh tiếp thời gian xử lý của P1 và P2 cái nào ngắn hơn .Ta sẽ thấy rằng P1 chỉ còn xử lý thêm 1 bước trong khi đó P2 còn đến 5 bước .Vậy P1 sẽ được quyền đi thêm bước 3 do quy định thời gian ngắn xử lý trước. Xong P1 . Sau khi P1 đi xong bước 3 thì P2 sẽ quay lại đi một bước .Lúc này đã đi được 4 bước rồi ! P2 sẽ so sánh thời gian chờ của các hành còn lại. Các bạn sẽ thấy P3 được quyền vào xử lý , lúc này nó sẽ so sánh tiếp Service Time .ST nào ngắn hơn sẽ được quyền xử lý trước theo quy luật đã nói ở trên. P2 còn 6 bước P3 có 3 bước , vậy P3 được quyền xử lý hết.Dựa vào quy luật thời gian ngắn xử lý trước có ưu tiên .Xong P3 ! P3 đã đi thêm 3 bước nữa vậy số bước đi hiện giờ là 7 Lúc này P4 được vào xử lý.nó được quyền đi thêm một bước.Khi đi xong nó sẽ so sánh với thời gian chờ kế tiếp lẫn thời gian xử lý, bạn thấy P5 được có 2, còn P4 thì còn 4.Nên P5 được phép vào xử lý hết 2 bước của nó.Xong P5 ! Lúc này tất cả các P đều vào xử lý , nó sẽ dựa vào thời gian xử lý để xác định P nào được vào xử lý tiếp theo.Các bạn quay lại tính sẽ thấy : P2 còn 6 ; P4 còn 4 ; Như vậy quá trình sẽ xử lý P4 rồi đến P2 Ta có biểu đồ sau : |--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--| 0_______3_ 4______ 7__8___10_________14______________20 ____P1___P2___P3___P4__P5______P4___________P5____ __ Giải thuật định thời CPU phần cuối cùng ( RR với Time Quantum=1) Mình sẽ lấy bài mẫu trong slide Thầy đưa để giải thích giải thuật, các bạn có thể lấy ra coi song song 2 cái. Process----- Arrival Time( AT )---------Service Time ( ST ) 1-----------------0------------------------- 3 2----------------- 2----------------- ------- 6
3----------------- 4----------------- ------- 4 4----------------- 6----------------- ------- 5 5----------------- 8----------------- ------- 2 Mình sẽ nói theo giọng văn của mình coi như AT là thời điểm còn ST là số bước. Giải thuật này sẽ theo quy luật đúng thời điểm của ai thì cho phép người đó vào và chỉ đi được 1 bước vì theo đề Time Quantum=1 (nhìn trên hình ta có 5 thời điểm lần lượt cho P1, P2, P3, P4, P5) Đầu tiên thằng P1 bước vào trước. Ta để ý thấy tại thời điểm 2 thằng P2 mới xuất hiện nên P1 được bước 2 bước ( vậy P1 còn 1 bước nữa là kết thúc ) ---0--------------5-------------10-------------15-------------20 __-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.1) P1 >>>>> Tại thời điểm 2: Thằng P2 xuất hiện, ta hình dung vị trí như vầy P2..P1; P2 sẽ bước 1 bước rồi đến P1 bước tiếp một bước ( đến lúc này P1 đi ra vì đã hoàn thành số bước là 3) ---0--------------5-------------10-------------15-------------20 __-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.2) P1 >>>>>--->> P2 ------>> Tại thời điểm 4: Thằng P3 xuất hiện, ta hình dung vị trí là P2 .. P3 ( quan sát (h.2)ta thấy P2 mới chỉ đứng ở thời điểm 3, và P3 ở thời điểm 4 nên mới có vị trí đó; chú ý P1 đã hết số bước nên ko tham gia nữa). Tới lúc này P2 sẽ bước 1 bước và P3 bước một bước. ---0--------------5-------------10-------------15-------------20 __-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.3) P1 >>>>>--->> P2 ------>>---->> P3 --------------->> Tiếp tục tại thời điểm 6: P4 xuất hiện, ta hình dung vị trí là P2 ..P4.. P3 ( Ta có thể quan sát (h.3),P2 lúc đó mới đứng ở thời điểm 5, tại thời điểm 6 P4 mới vào nên có vị trí đó ). Như trentheo trình tự: P2 bước 1, P4 bước 1, P3 bước 1. Chú ý lúc này P4 sẽ đứng ở thời điểm 8. ---0--------------5-------------10-------------15-------------20 __-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.4) P1 >>>>>--->> P2 ------->>--->>--->> P3 --------------->>------->> P4---------------------->> Vào thời điểm 8: P5 xuất hiện nên nó sẽ đứng trước P4 chứ không đứng trước P3 ( vì P3 đang đứng ở thời điểm 9 ). Ta hình dung vị trí là P2..P5..P4.. P3. Như trên P2 bước 1, P5 bước 1, P4 bước 1, P3 bước 1. ---0--------------5-------------10-------------15-------------20 __-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.5) P1 >>>>>--->>
P2 ------->>--->>--->>------->> P3 --------------->>------->>--------->> P4 --------------------->>---------->> P5 ------------------------------>> Vì tất cả thành viên đã tham gia nên ta cứ đọc theo trình tự như trên ( từ -> P2 ->P3 -> [P4-> P5 )để kết thúc số bước của từng thành viên ( cứ >> là 1 bước ta quan sát hình sẽ biết được các thành viên còn bao nhiêu bước). Thôi ghi ra luôn ^_^: Lúc này P2 đã đi được 4 bước ( P2 còn 2 bước ), P3 đi được 3 bước ( P3 còn 1 bước ), P4 đi được 2 bước( P4 còn 3 bước ), P5 đi được 1 bước ( P5 còn 1 bước ). Ta cứ tuân theo trình tự đọc đó là ta có kết quả ---0--------------5-------------10-------------15-------------20 __-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|thời điểm (h.6) P1 >>>>>--->> P2 ------->>--->>--->>------->>--------->>--------->> P3 --------------->>------->>--------->>--------->> P4 --------------------->>---------->>--------->>------>>>>> P5 ------------------------------>>--------->> Chú ý phần cuối cùng ta thấy P4 đi tới 2 bước vì trong quá trình đọc mấy thành viên khác đã hoàn thành số bước của mình (không tham gia nữa). Lúc này P4 còn tới 2 bước lựng nên bước nốt 2 bước còn lại để kết thúc. Bài này các bạn đọc tham khảo, nếu có gì sai sót thì bổ sung để hoàn thiện giải thuật này nhé. Hy vọng có thể giúp các bạn một chút trong giải thuật này. Thân! Blog:http://www.facebook.com/duyduc87 Email:duy.duc87@gmail.com Bài tập tham khảo về Điều phối CPU. KimThao_I83C_08H1012087 on 14/11/2009, 14:47 Mình có một số bì tập tham khảo về Điều phối CPU (Xin Thây và cac ban sửa chữa cac sai ̀ ́ ̣ ́ sot) xin post len mọi người cùng tham khảo. ́ Bài 1 : Giả sử một hệ thống có 5 tiến trình cùng đến vào 1 thời điểm với tính chất sau: Tiến trình Độ ưu tiên Khoảng CPU (số giây) P1 3 10 P2 1 1 P3 3 2 P4 4 1 P5 2 5 a) Vẽ 4 biểu đồ Gantt tương ứng với các thuật giải điều phối SJFS (có tiếm quyền) 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 cho mỗi thuật giải. c) Thuật giải nào tốt nhất về phương diện thời gian chờ trung bình? Giải đáp: Theo đề bài, các tiến trình có độ ưu tiên (Priority Scheduling- PS ), thì tiến trình nào
có độ ưu tiên nhỏ nhất sẽ được chạy trước. Và SJFS là dạng đặc biệt của PS với độ ưu tiên là khoảngCPU kế tiếp.Vậy ta có biểu đồ 1: Điều phối theo độ ưu tiên:Theo độ ưu tiên và chạy hết khoảng CPU P2 P5 P3 P1 P4 0 1 6 8 18 19 *Thời gian chờ trung bình: 8 + 0 + 6 + 18 + 1 = 33/5 = 6.6 biểu đồ 2: Điều phối SJFS không tiếm quyền: đến trước phục vụ trước và khoảng CPU ngắn nhất.P2 và P4 đến cùng thời điểm( đề bài) cùng khoảng CPU nhưng P2 ưu tiên. P3 va P5 cung ̀ độ ưu tiên 3, nhưng P3 chay trước vi khoang CPU ngăn hơn ̣ ̉ ́ P2 P4 P3 P5 P1 01249 *Thời gian chờ trung bình: 9 + 0 + 2 + 1 + 4 = 16/5 = 1.2 biểu đồ 3: Điều phối SJFS có tiếm quyền: giống như biểu đồ 2, chắc tại P2 và P4 có dạng đặc biệt. ( sai?, đúng?) biểu đồ 4: Điều phối RSS: Như điều phối kiểu FCFS nhưng cho phép tiếm quyền khi tiến trình đang chạy bị hết thời lượng. (theo đề bài thời lượng 1 giây) P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 *thời gian chờ trung bình: (0+4+2+1+1+1) + 1 + (2+3) + 3 + (4+2+1+1+1) = 27/5 = 5.4 (a.Tri sua) Như vậy: SJFS ngắn nhất = 1.2 Bài 2 : 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 như sau: Tiến trình Thời điểm đến (ms) CPU-Burst (ms) P1 4 46 P2 30 28 P3 51 33 Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phươn án): a. Thể hiện bằng biểu đồ Gantt (1,0 điểm) b. Tính thời gian chờ trung bình của các tiến trình (1,0 điểm). Bài giải: Nhận xét: p1 chạy hết thời lượng 20ms, nhưng p2 chưa xuất hiện, chạy thêm nửa chừng 10 ( tức thời điểm 30) p2 yêu cầu nhưng vẫn phải chờ p1 chạy hết 20ms, lúc đó p2 mới được chạy.Khi p2 chạy được 11 ms (tức thời điểm 51 ) p3 yêu cầu,nhưng phải chờ p2, nên sắp vào hàng chờ sau p1. p2 xong tới p1 chạy P1 P1 P2 P1 P3 P2 P3 0 4 24 44 64 70 90 98 111 *Thời gian chờ trung bình: (0+20) + (10+6+20) + (19 + 8 ) = 83/3 = 27.7 Bài 3 :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 như sau:
Tiến trình Thời điểm đến (ms) CPU-Burst (ms) P0 6 26 P1 17 45 P2 48 29 Dùng thuật giải RRS với thời lượng bằng 20 ms để điều phối CPU (có thể có 2 phươn án): a. Thể hiện bằng biểu đồ Gantt (1,0 điểm) b. Tính thời gian chờ trung bình của các tiến trình (1,0 điểm) Giải đáp: P0 P1 P1 P2 P1 P2 0 6 26 46 66 86 91 100 Thời gian chờ trung bình: 0 + (9+20) + (18+5) = 52/3 = 17.3 Có ý kiên khac: ́ ́ Tiến trình Độ ưu tiên Khoảng CPU (số giây) P2 1 1 P5 2 5 P1 3 10 P3 3 2 P4 4 1 Biểu đồ 1: Thứ tự thực hiện các tiến trình theo độ ưu tiên: P2 P5 P1 P3 P4 0 1 6 17 18 19 Thời gian: 6 + 0 + 17 + 18 + 1 = 42 / 5 = 8.4