›
›

Hệ điều hành - Chương 4: Quản lý tiến trình

pdf 58 trang vanle 2750
Download
Bạn đang xem 20 trang mẫu của tài liệu "Hệ điều hành - Chương 4: Quản lý tiến trình", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfhe_dieu_hanh_chuong_4_quan_ly_tien_trinh.pdf

Nội dung text: Hệ điều hành - Chương 4: Quản lý tiến trình

  1. Chöông 4: Quaûn lyù tieán trình Moâ hình Tieán trình Traïng thaùi tieán trình Thoâng tin quaûn lyù tieán trình Quaù trình ñieàu phoái tieán trình Caùc thuaät toaùn ñieàu phoái 10/20/2007 Trần Hạnh Nhi 1
  2. Khaùi nieäm : Ña nhieäm vaø ña chöông ??? Vì sao muoán xöû lyù ñoàng thôøi nhieàu coâng vieäc treân maùy tính ? Job 1 CPU IO CPU IO CPU Job 1 CPU IO CPU IO Job 2 CPU IO CPU CPU Xöû lyù ñoàng thôøi ñeå taêng hieäu suaát söû duïng CPU 10/20/2007 Trần Hạnh Nhi 2
  3. Khaùi nieäm : Ña nhieäm vaø ña chöông ??? Vì sao muoán xöû lyù ñoàng thôøi nhieàu coâng vieäc treân maùy tính ? Job : kq = a*b + c*d; Xöù lyù tuaàn töï Xöûù lyù ñoàng haønh CPU #1 CPU #1 CPU #2 x = a * b 1 x = a * b y = c * d y = c *d 2 kq = x+y kq = x+y 3 Xöû lyù ñoàng thôøi ñeå taêng toác ñoä xöû lyù 10/20/2007 Trần Hạnh Nhi 3
  4. Ña nhieäm vaø ña chöông Multitasking (ña nhieäm) : cho pheùp nhieàu taùc vuï/ coâng vieäc ñöôïc xöû lyù ñoàng thôøi Ngöôøi duøng luoân mong muoán 1 HÑH ña nhieäm Nhöng: Maùy tính thöôøng chæ coù 1 CPU? Multiprogramming (ña chöông) : kyõ thuaät cho pheùp nhieàu chöông trình ñöôïc thöïc hieän ñoàng thôøi (treân 1 CPU) Giaû laäp nhieàu CPU aûo töø 1 CPU thaät ñeå cho pheùp thi haønh nhieàu chöông trình ñoàng thôøi. AÛo hoaù baèng caùch naøo ? Xaây döïng caùc thuaät toaùn ñeå luaân chuyeån CPU giöõa caùc chöông trình öùng duïng. 10/20/2007 Trần Hạnh Nhi 4
  5. Xöû lyù ñoàng haønh, nhöõng khoù khaên ? - Taøi nguyeân giôùi haïn, öùng duïng Excel “voâ haïn” Visual C++ - Nhieàu hoaït ñoäng CDplayer ñan xen Winword ??? Phaân chia taøi nguyeân ? ??? Chia seû taøi nguyeân ? HÑH : “ Giaûi quyeát nhieàu coâng vieäc ñoàng thôøi, ??? Baûo veä? ñaâu coù deã ! “ 10/20/2007 Trần Hạnh Nhi 5
  6. Giaûi phaùp -“Chia ñeå trò”, coâ Winword laäp caùc hoaït ñoäng. - Moãi thôøi ñieåm CDPlayer chæ giaûi quyeát 1 Excel yeâu caàu. - Aûo hoaù taøi Visual C ++ nguyeân : bieán ít thaønh nhieàu HÑH : “ Ai cuõng coù phaàn khi ñeán löôït maø ! ” 10/20/2007 Trần Hạnh Nhi 6
  7. Giaûi phaùp CPU 10/20/2007 Trần Hạnh Nhi 7
  8. Khaùi nieäm tieán trình (Process) Tieán trình laø moät chöông trình ñang trong quaù trình thöïc hieän Moãi tieán trình sôû höõu Moät CPU (aûo) rieâng Moät khoâng gian nhôù rieâng Chieám giöõ 1 soá taøi nguyeân cuûa heä thoáng Vd: Moät chöông trình Word coù theå ñöôïc chaïy 2 laàn seõ taïo ra 2 tieán trình khaùc nhau: Microsoft Word – [Bai tap1.doc] Microsoft Word – [Bai tap2.doc] 10/20/2007 Trần Hạnh Nhi 8
  9. Hai phaàn cuûa tieán trình Doøng xöû lyù P1 P2 int a; int a; Khoâng gian ñòa chæ 10/20/2007 Trần Hạnh Nhi 9
  10. Traïng thaùi tieán trình ? Taïi 1 thôøi ñieåm, tieán trình ôû moät trong caùc traïng thaùi sau: Nhaän CPU ready running ☺ R ☺ R s s Traû CPU ☺ CPU CPU blocked Chôø R Nhaän R Rs CPU 10/20/2007 Trần Hạnh Nhi 10
  11. Khoái quaûn lyù tieán trình - PCB (Process Control Block) Định danh (Process ID) pid Trạng thaùi tiến trình State Ngữ cảnh tiến trình (State, details) Trạng thaùi CPU Bộ xử lyù (cho maùy nhiềuCPU) Context Bộ nhớ chính (IP, Mem, Files ) Taøi nguyeân sử dụng/tạolập Thoâng tin giao tiếp Relatives Tiến trình cha, tiến trình con ( Dad, children) Độ ưu tieâên Scheduling statistic Thoâng tin thống keâ Process control Block PCB 10/20/2007 Trần Hạnh Nhi 11
  12. Ví duï: Khoái quaûn lyù tieán trình cuûa HÑH MachOS typedef struct machpcb { char mpcb_frame[REGOFF]; struct regs mpcb_regs; // user's saved registers struct rwindow mpcb_wbuf[MAXWIN]; //user window save buffer char *mpcb_spbuf[MAXWIN]; //sp's for each wbuf int mpcb_wbcnt; //number of saved windows in pcb_wbuf struct v9_fpu *mpcb_fpu; // fpu state struct fq mpcb_fpu_q[MAXFPQ]; // fpu exception queue int mpcb_flags; // various state flags int mpcb_wocnt; // window overflow count int mpcb_wucnt; // window underflow count kthread_t *mpcb_thread; // associated thread } machpcb_t; 10/20/2007 Trần Hạnh Nhi 12
  13. Caùc thao taùc treân tieán trình Taïo laäp tieán trình Keát thuùc tieán trình Thay ñoåi traïng thaùi tieán trình : Assign() Block() Awake() Suspend() Resume() 10/20/2007 Trần Hạnh Nhi 13
  14. Taïo laäp tieán trình Caùc tình huoáng : Khôûi ñoäng batch job User logs on Kích hoaït 1 service (print ) Process goïi haøm taïo moät tieán trình khaùc Caùc tieán trình coù theå taïo tieán trình con, hình thaønh caây tieán trình trong heä thoáng Caùc tieán trình môùi ñöôïc taïo coù theå thöøa höôûng taøi nguyeân töø cha, hay ñöôïc caáp taøi nguyeân môùi 10/20/2007 Trần Hạnh Nhi 14
  15. Keát thuùc tieán trình Tình huoáng : Tieán trình xöû lyù xong leänh cuoái cuøng hay goïi exit () Keát thuùc Batch job , Halt instruction User logs off Do loãi chöông trình Moät tieán trình coù theå keát thuùc 1 tieán trình khaùc neáu coù ID (ñònh danh) cuûa tieán trình kia. Ví duï: kill –-s SIGKILL 1234: huyû tieán trình coù ID laø 1234 10/20/2007 Trần Hạnh Nhi 15
  16. Moâ hình ña tieán trình (MultiProcesses) Heä thoáng laø moät taäp caùc tieán trình hoaït ñoäng ñoàng thôøi Caùc tieán trình ñoäc laäp vôùi nhau => khoâng coù söï trao ñoåi thoâng tin hieån nhieân Excel winword Visual C CDplayer OS 10/20/2007 Trần Hạnh Nhi 16
  17. Ví duï moâ hình ña tieán trình Giôø thi lyù thuyeát moân Heä Ñieàu haønh Moãi sinh vieân laø moät tieán trình : Cuøng laøm baøi => Hoaït ñoäng ñoàng haønh Coù baøi thi , buùt, giaáy rieâng => Taøi nguyeân rieâng bieät Ñoäc laäp => Khoâng trao ñoåi (veà nguyeân taéc) Thöïc haønh moân Heä Ñieàu haønh 2 sinh vieân/nhoùm Hôïp taùc ñoàng haønh Nhucaàutraoñoåi Duøng taøi nguyeân chung 10/20/2007 Trần Hạnh Nhi 17
  18. Moâ hình ña tieåu trình (MultiThreads) Nhieàu tình huoáng caàn coù nhieàu doøng xöû lyù ñoàng thôøi cuøng hoaït ñoäng trong moät khoâng gian ñòa chæ => cuøng chia seû taøi nguyeân (server, OS, caùc chöông trình tính toaùn song song : nhaân ma traän ) alta vista Khaùi nieäm môùi : tieåu trình (thread) 10/20/2007 Trần Hạnh Nhi 18
  19. Ví duï Moâ hình ña tieåu trình Thöïc haønh moân Heä Ñieàu haønh Moãi nhoùm 2 sinh vieân laø moät tieán trình : Moãi sinh vieân laø moät tieåu trình Cuøng laøm baøi => Hoaït ñoäng ñoàng haønh Coùù baøi thöïc haønh chung => Taøi nguyeân chung Trao ñoåi vôùi nhau 10/20/2007 Trần Hạnh Nhi 19
  20. Khaùc bieät giöõa Tieåu trình & Tieán trình Tieåu trình : 1 doøng xöû lyù Tieán trình : P1 1 khoâng gian ñòa chæ T1 T2 1 hoaëc nhieàu tieåu trình T 3 Caùc tieán trình laø ñoäc laäp Caùc tieåu trình trong cuøng 1 tieán trình khoâng coù söï baûo veä laãn nhau (caàn thieát ? ). int a; 10/20/2007 Trần Hạnh Nhi 20
  21. Tieåu trình haït nhaân (Kernel thread) T1 T2 User mode System call Kernel mode Kernel Thread Khaùi nieäm tieåu trình ñöôïc xaây döïng beân trong haït nhaân Ñônvòxöûlyùlaøtieåutrình Ví duï : Windows 95/98/NT/2000 Solaris, Tru64 UNIX, BeOS, Linux 10/20/2007 Trần Hạnh Nhi 21
  22. Phaân chia CPU ? 1 CPU vaät lyù : laøm theá naøo ñeå taïo aûo giaùc moãi tieán trình sôû höõu CPU rieâng cuûa mình ? Luaân chuyeån CPU giöõa caùc tieán trình 2 thaønh phaàn ñaûm nhieäm vai troø ñieàu phoái: Scheduler choïn 1 tieán trình Dispatcher chuyeån CPU cho tieán trình ñöôïc choïn CPU 10/20/2007 Trần Hạnh Nhi 22
  23. Caùc danh saùch tieán trình Ready List P1 P4 P5 Waiting Lists R1 P2 P7 R2 P3 P10 R3 P6 10/20/2007 Trần Hạnh Nhi 23
  24. Scheduler - Nhieäm vuï Ra quyeát ñònh choïn moät tieán trình ñeå caáp phaùt CPU : ÖÙng cöû vieân = {Caùc tieán trình ready list} 0 tieán trình : CPU raûnh roãi (idle)! 1 tieán trình : khoâng caàn suy nghó nhieàu, ñuùng khoâng ? >1 : choïn ai baây giôø ? Döïa vaøo caùc thuaät toaùn ñieàu phoái Ready List P1 P4 P5 10/20/2007 Trần Hạnh Nhi 24
  25. Dispatcher - Nhieäm vuï Nhieäm vuï cuûa Dispatcher: Chuyeån ñoåi ngöõ caûnh Xeùt ví duï Tieán trình A ñang duøng CPU 1 chuùt thì bò HÑH thu hoài CPU HÑH caáp CPU cho B duøng 1 chuùt, HÑH thu hoài laïi CPU. HÑH caáp CPU trôû laïi cho A. Giaù trò caùc thanh ghi giöõa nhöõng laàn chuyeån ñoåi CPU ? Kòch baûn : Löu ngöõ caûnh tieán trình hieän haønh Naïp ngöõ caûnh tieán trình ñöôïc choïn keá tieáp 10/20/2007 Trần Hạnh Nhi 25
  26. 10/20/2007 Trần Hạnh Nhi 26
  27. Dispatcher - Thaûo luaän Baûn thaân HÑH cuõng laø 1 phaàn meàm, nghóa laø cuõng söû duïng CPU ñeå coùtheåchaïyñöôïc. Caâu hoûi: Khi tieán trình A ñang chieám CPU, laøm theá naøo HÑH coù theå thu hoài CPU laïi ñöôïc ? (vì luùc naøy HÑH khoâng giöõ CPU) EÙp buoäc NSD thænh thoaûng traû CPU laïi cho HÑH ? Coù khaû thi ? Maùy tính phaûi coù 2 CPU, 1 daønh rieâng cho HÑH ? HÑH söû duïng ngaét ñoàng hoà (ngaét ñieàu phoái) ñeå kieåm soaùt heä thoáng Moãi khi coù ngaét ñoàng hoà, HÑH kieåm tra xem coù caàn thu hoài CPU töø 1 tieán trình naøo ñoù laïi hay khoâng ? HÑH chæ thu hoài CPU khi coù ngaét ñoàng hoà phaùt sinh. Khoaûng thôøi gian giöõa 2 laàn ngaét ñieàu phoái goïi laø chu kyø ñoàng hoà (toái thieåu laø 18.2 laàn / giaây) 10/20/2007 Trần Hạnh Nhi 27
  28. Löïa choïn tieán trình ? Taùc vuï cuûa Scheduler Muïc tieâu ? Söû duïng CPU hieäu quaû Ñaûm baûo taát caû caùc tieán trình ñeàu tieán trieån xöû lyù Tieâu chuaån löïa choïn ? Taát caû caùc tieán trình ñeàu nhö nhau ? Ñeà xuaát moät ñoä öu tieân cho moãi tieán trình ? Thôøi ñieåm löïa choïn ? (Thôøi ñieåm kích hoaït Scheduler()) 10/20/2007 Trần Hạnh Nhi 28
  29. Muïc tieâu ñieàu phoái Hieäu quûa (Efficiency) ª Thôøi gian ª Ñaùùp öùng (Response time) ª Hoaøn taát (Turnaround Time = Tquit -Tarrive): ª Chôø (Waiting Time = T in Ready ) : © Thoâng löôïng (Throughput = # jobs/s ) © Hieäu suaát Taøi nguyeân ª Chi phí chuyeån ñoåi Coâng baèng ( Fairness) : Taát caû caùc tieán trình ñeàu coù cô hoäi nhaän CPU 10/20/2007 Trần Hạnh Nhi 29
  30. Thôøi ñieåm ra quyeát ñònh ñieàu phoái Ñieàu phoái ñoäc quyeàn (non-preemptive scheduling): tieán trình ñöôïc choïn coù quyeàn ñoäc chieám CPU Caùc thôøi ñieåm kích hoaït Scheduler P cur keát thuùc P cur : running ->blocked Ñieàu phoái khoâng ñoäc quyeàn (preemptive scheduling): tieán trình ñöôïc choïn coù theå bò cöôùp CPU bôûi tieán trình coù ñoä öu tieân cao hôn Caùc thôøi ñieåm kích hoaït Scheduler P cur keát thuùc P cur : Running -> Blocked Q : Blocked / New -> Ready 10/20/2007 Trần Hạnh Nhi 30
  31. Hai nguyeân taéc ñieàu phoái CPU Ñoäc quyeàn while (true){ save state Pcur Scheduler.NextP() Pnext load state pnext resume Pnext wait for Pnext Khoâng ñoäc quyeàn } while (true){ interrupt Pcur save state Pcur Scheduler.NextP() Pnext load state pnext resume Pnext } 10/20/2007 Trần Hạnh Nhi 31
  32. Ñaùnh giaù chieán löôïc ñieàu phoái Söû duïng 2 ñaïi löôïng ño : Turn- around time = Tquit –Tarrive: töø luùc vaøo HT ñeán khi hoaøn taát Waiting time = T in Ready Xeùt tröôøng hôïp trung bình N tieán trình Avg Turn- around time = (Σ Turn- around time Pi )/N Avg Waiting time = (Σ Waiting time Pi )/N 10/20/2007 Trần Hạnh Nhi 32
  33. Caùc chieán löôïc ñieàu phoái FIFO (FCFS) Xoay vòng (Round Robin) Theo độ ưutiên Công việcngắnnhất(SJF) Nhiềumức độ ưutiên 10/20/2007 Trần Hạnh Nhi 33
  34. FCFS (First comes first served) Tieán trình vaøo RL laâu nhaát ñöôïc choïn tröôùc Ready List Theo thứ tự vaøo RL C B A CPU Độcquyền Ready List C B CPU Ready List C CPU 10/20/2007 Trần Hạnh Nhi 34
  35. Minh hoïa FCFS P TarriveRL CPU burst P TT WT P1 0 24 P1 24 0 P2 1 3 P2 27-1 24-1 P3 2 3 P3 30-2 27-2 AvgWT = (23+25)/3 = 16 P1 P2 P3 02427 0:00 P1 vào RL 0:24 P1 kết thúc P1 dùng CPU P2 dùng CPU 0:01 P2 vào RL 0:27 P2 kết thúc 0:02 P3 vào RL P3 dùng CPU 10/20/2007 Trần Hạnh Nhi 35
  36. Nhaän xeùt FCFS Ñôn giaûn Chòu ñöïng hieän töôïng tích luõy thôøi gian chôø Tieán trình coù thôøi gian xöû lyù ngaén ñôïi tieán trình coù thôøi gian xöû lyù daøi Öu tieân tieán trình cpu-bounded CoùtheåxaûyratìnhtraïngñoäcchieámCPU 10/20/2007 Trần Hạnh Nhi 36
  37. Ñieàu phoái Round Robin (RR) Quantum/ Time slice Ñieàu phoái theo nguyeân taéc FCFS Moãi tieán trình chæ söû duïng moät löôïng q cho moãi laàn söû duïng CPU Ready List C B A CPU A chỉ chiếm CPU trong q ms Ready List A C B B được giao quyềnsử dụng CPU CPU trong q ms kế tiếp Ready List B A C C được giao quyềnsử dụng CPU CPU trong q ms kế tiếp 10/20/2007 Trần Hạnh Nhi 37
  38. Minh hoïa RR, q=4 P TarriveRL CPU burst P TT WT P1 0 24 P1 30 0+(10-4) P2 1 3 P2 7-1 4-1 P3 2 3 P3 10-2 7-2 AvgWT = (6+3+5)/3 = 4.66 P1 P2 P3 P1 P1 P1 P1 P1 0 47101418222630 0:00 P1 vào, P1 dùng CPU 0:07 P2 dừng, P3 dùng CPU 0:01 P2 vào (đợi) 0:10 P3 dừng, P1 dùng CPU 0:02 P3 vào (đợi) 0:14 P1 vẫnchiếmCPU 0:04 P1 hếtlượt, P2 dùng CPU 10/20/2007 Trần Hạnh Nhi 38
  39. Minh hoïa RR, q=4 P TarriveRL CPU burst Tranh chaáp vò trí trong RL : “Chung thuûy” 1. P : running -> ready P1 0 24 2. P : blocked -> ready 3. P: new ->ready P2 4 3 Khoâng phaûi luoân luoân coù thöù töï ñieàu phoái P1 P3 12 3 P2 P3 P4P1 P2 P3 P4 P1 P1 P2 P1 P3 P1 P1 P1 0 48111518222630 RL 0:04 P1 P2 “Chung thuûy” 0:00 P1 0:8 P2 P1 0:04 0:11 P1 0:15 P3 P1 ? 0:04 P2 P1 “Coù môùi nôùi cuõ” 10/20/2007 Trần Hạnh Nhi0:18 P1 39
  40. RR : Khinaøokeátthuùc1 löôïtsöûduïngCPU Heát thôøi löôïng q ms (quantum) cho pheùp Tieán trình keát thuùc Tieán trình bò khoùa Chờ Rs Chờ biếncố 10/20/2007 Trần Hạnh Nhi 40
  41. Nhaän xeùt RR Söû duïng cô cheá khoâng ñoäc quyeàn Bao laâu ? Moãi tieán trình khoâng phaûi ñôïi quaù laâu Loaïi boû hieän töôïng ñoäc chieám CPU Hieäu quaû ? Giaûm tíùnh töông taùc Phuï thuoäc vaøo vieäc choïn löïa quantum q q quaùù lớn ??? q quaù nhỏ ??? Taêng chi phí chuyeån ñoåi ngöõ caûnh Tröôøng hôïp xaáu nhaát cuûa RR ? 10/20/2007 Trần Hạnh Nhi 41
  42. Ñieàu phoái vôùi ñoä öu tieân Phân biệttiếntrìnhquantrọng >< tiến trình bình thường? WinAmp độ ưutiên: cao(-3) ộư Độ WinWord độ ưu tiên: trung bình (0) utiên Outlook độ ưutiên: thấp(3) Tieán trình coù ñoä öu tieân cao nhaát ñöôïc choïn caáp CPU tröôùc 10/20/2007 Trần Hạnh Nhi 42
  43. Ví duï: Ñoä öu tieân cuûa HÑH WinNT WinNT gaùn cho moãi tieán trình ñoä öu tieân coù giaù trò giöõa 0 & 31 0 (ñoä öu tieân nhoû nhaát): daønh rieâng cho traïng thaùi system idle Ñoä öu tieân ñöôïc phaân theo nhoùm: Realtime : (16 - 31) Thích hôïp cho caùc tieán trình thôøi gian thöïc Daønh rieâng cho caùc tieán trình cuûa ngöôøi quaûn trò heä thoáng Dynamic : (0 - 15) Thích hôïp cho caùc tieán trình cuûa ngöôøi duøng thöôøng Chia thaønh 3 möùc : high (11 - 15) normal (6 - 10) idle (2 - 6) 10/20/2007 Trần Hạnh Nhi 43
  44. Bieåu ñoà phaân boá ñoä öu tieân cuûa WinNT realtime time-critical 31 realtime highest (+2) realtime above normal (+1) levels 16-31 24 normal (0) below normal (-1) lowest (-2) realtime idle 16 high dynamic time-critical 15 13 normal dynamic 8 idle levels 1-15 4 dynamic idle 1 system idle 0 10/20/2007 Trần Hạnh Nhi 44
  45. Nguyeân taéc ñieàu phoái Độcquyền Lượtsử dụng CPU kết thuùc khi: tiến trình kếtthuùc, tiến trình bị khoùa Khoâng độcquyền Lượtsử dụng CPU kết thuùc khi: tiến trình kếtthuùc, tiến trình bị khoùa, coùtiếntrìnhvôùiđộ ưutieâncaohơnvaøoRL 10/20/2007 Trần Hạnh Nhi 45
  46. Minh hoïa ñoä öu tieân (khoângñoäc quyeàn) P TRL Priority CPU burst P TT WT P1 0 2 24 P1 30 0+(7-1) P2 1 0 3 P2 4-1 0 P3 2 1 3 P3 7-2 4-2 AvgWT = (6+0+2)/3 = 2.66 P1 P2 P2 P3 P1 030172 4 0:00 P1 vào, P1 dùng CPU 0:4 P2 kết thúc, P3 dùng CPU 0:01 P2 vào (độ ưutiêncaohơnP1) 0:7 P3 dừng, P1 dùng CPU P2 dành quyềndùngCPU 0:30 P1 dừng 0:02 P3 vào (độ ưutiênthấphơnP2) 10/20/2007P3 không dành đượcquyềndùngCPU Trần Hạnh Nhi 46
  47. Nhaän xeùt Caùch tính ñoä öu tieân ? Heä thoáng gaùn : CPU times starvation Ngöôøi duøng gaùn töôøng minh Tính chaát ñoä öu tieân : Tónh Ñoäng Soá phaän tieán trình coù ñoä öu tieân thaáp ? Chôø laâu, laâu, laâu Aging : taêng ñoä öu tieân cho nhöõng tieán trình chôø laâu trong heä thoáng 10/20/2007 Trần Hạnh Nhi 47
  48. Shortest Job First (SJF) Ready List P2 Ng ắn (cần3 chukỳ) nh ất P1 CPU (cần5 chukỳ) P3 (cần7 chukỳ) Là mộtdạng độ ưutiênđặcbiệtvới độ ưutiên pi = thời_gian_còn_lại(Processi) Có thể cài đặt độc quyềnhoặckhôngđộcquyền 10/20/2007 Trần Hạnh Nhi 48
  49. Minh hoïa SJF (ñoäc quyeàn)(1) P TarriveRL CPU burst P TT WT P1 0 24 P1 24 0 P2 1 3 P2 27 24-1 P3 2 3 P3 30 27-2 AvgWT = (23+25)/3 = 16 P1 P2 P3 0242730 0:00 P1 vào, P1 dùng CPU 0:24 P1 kết thúc, P2 dùng CPU 0:01 P2 vào RL 0:27 P2 dừng, P3 dùng CPU 0:02 P3 vào RL 0:30 P3 dừng 10/20/2007 Trần Hạnh Nhi 49
  50. Minh hoïa SJF (ñoäc quyeàn)(2) P TarriveRL CPU burst P TT WT P1 0 24 P1 24 0 P2 1 3 P2 29 26-1 P3 1 2 P3 26 24-2 AvgWT = (24+22)/3 = 15.33 P1 P3 P2 0242629 0:00 P1 vào, P1 dùng CPU 0:24 P1 kết thúc, P3 dùng CPU 0:01 P2 vào 0:26 P3 dừng, P2 dùng CPU 0:01 P3 vào 0:29 P2 dừng 10/20/2007 Trần Hạnh Nhi 50
  51. Minh hoïa SJF (khoângñoäc quyeàn) (1) P TarriveRL CPU burst P TT WT P1 0 24 P1 30 0+(7-1) P2 1 3 P2 4-1 0 P3 2 3 P3 7-2 4-2 AvgWT = (6+0+2)/3 = 2.66 P1 P2 P3 P1 030174 0:00 P1 vào, P1 dùng CPU 0:4 P2 kết thúc, P3 dùng CPU 0:01 P2 vào (độ ưutiêncaohơnP1) 0:7 P3 dừng, P1 dùng CPU P2 dành quyềndùngCPU 0:30 P1 dừng 10/20/2007 Trần Hạnh Nhi 51
  52. Minh hoïa SJF (khoângñoäc quyeàn) (2) P TarriveRL CPU burst P TT WT P1 0 24 P1 33 0+(10-1) P2 1 5 P2 6 0 P3 3 4 P3 10 6-3 AvgWT = (9+0+3)/3 = 4 P1 P2 P2 P3 P1 0331103 6 0:00 P1 vào, P1 dùng CPU 0:6 P2 kết thúc, P3 dùng CPU 0:01 P2 vào (độ ưutiêncaohơnP1) 0:9 P3 dừng, P1 dùng CPU P2 dành quyềndùngCPU 0:33 P1 dừng 0:03 P3 vào (độ ưutiên< P2) 10/20/2007P2 dành quyềndùngCPU Trần Hạnh Nhi 52
  53. Minh hoïa SJF (nhieàu chu kyø CPU) P TarriveRL CPU1 IO1 IO1 CPU2 IO2 IO2 burst R T burst R T P1 0 5 R1 2 2 R2 2 P2 2 1 R1 10 1 R1 4 P3 10 8 R2 1 0 Null 0 CPU P1 P2 P1 P3 P2 P3 P1 P3 0212103 6 13 14 15 17 R1 P2 P1 P2 3 13 15 19 R2 P1 P3 1719 21 22 10/20/2007 Trần Hạnh Nhi 53
  54. Nhaän xeùt SJF Toái öu thôøi gian chôø P1 P2 P3 Chöùng minh ? a b c AvgWT = (3a+2b+c) Min AvgWT ? Khoâng khaû thi a<b<c Laøm sao bieát CPU burst ? τ n+1 = α tn + (1−α )τ n length of the nth predicted value for 0<= α <=1 th CPU burst the n CPU burst most recent relative weight past history information 10/20/2007 Trần Hạnh Nhi 54
  55. Ñieàu phoái vôùi nhieàu möùc öu tieân Toå chöùc N RL öùng vôùi Độưutiên nhieàu möùc öu tieân 1 Moãi RLi aùp duïng moät chieán löôïc ñieàu phoái CPU thích hôïp 2 Giöõa caùc RL aùp duïng ñieàu phoái theo ñoä öu tieân : n RLi roãng môùi ñieàu phoái RLi+1 Kếthợp nhiềuchiếnlược 10/20/2007 Trần Hạnh Nhi 55
  56. Ñieàu phoái vôùi nhieàu möùc öu tieân – Thöïc teá Toå chöùc N RL öùng vôùi Độưutiên nhieàu möùc öu tieân 1 Moãi RLi aùp duïng RR Giöõa caùc RL aùp duïng CPU ñieàu phoái theo ñoä öu 2 tieân : RLi roãng môùi ñieàu phoái RLi+1 n Kếthợp nhiềuchiếnlược 10/20/2007 Trần Hạnh Nhi 56
  57. Khuyeát ñieåm 1 ☺ ☺ ☺ CPU 2 Starvation !!! Giaûi phaùp Aging : Chờ lâu quá Chôø laâu quaù : chuyeån leân RL vôùi ñoä öu tieân cao hôn Chieám CPU laâu quaù : chuyeån xuoáng RL vôùi ñoä öu tieân thaáp hôn Khi naøo thöïc hieän aging ? Aging tieán trình naøo ? 10/20/2007 Trần Hạnh Nhi 57
  58. Bài tập: Hãy điềuphối CPU: SJF không độc quyền. R1,R2: FIFO Tieán Thôøi ñieåm IO laàn 1 IO laàn 2 trình vaøo Ready CPU1 CPU2 list Thôøi Thieát Thôøi Thieát gian bò gian bò P1 0 8 5 R1 1 0 Null P2 2 1 8 R2 2 5 R1 P3 10 6 5 R1 2 3 R2 P4 11 3 20 R2 0 0 Null 10/20/2007 Trần Hạnh Nhi 58