Giáo trình môn Hệ điều hành - Chương IV: Định thời CPU

1 Khoa KTMT Chöông IV: Ñònh thôøi CPU  Khaùi nieäm cô baûn  Caùc boä ñònh thôøi ‟ long-term, mid-term, short-term  Caùc tieâu chuaån ñònh thôøi CPU  Caùc giaûi thuaät ñònh thôøi ‟ First-Come, First-Served (FCFS) ‟ Shortest Job First (SJF) vaø Shortest Remaining Time First (SRTF) ‟ Priority Scheduling ‟ Round-Robin (RR) ‟ Highest Response Ratio Next (HRRN) ‟ Multilevel Queue ‟ Multilevel Feedback Queue 2 Khoa KTMT Mục tiêu  Hiểu được: – Tại sao phải định thời. – Các tiêu chí định thời – Một số giải thuật định thời 3 Khoa KTMT Khaùi nieäm cô baûn  Trong caùc heä thoáng multitasking ‟ Thöïc thi nhieàu chöông trình ñoàng thôøi laøm taêng hieäu suaát heä thoáng. ‟ Taïi moãi thôøi ñieåm, chæ coù moät process ñöôïc thöïc thi. Do ñoù, caàn phaûi giaûi quyeát vaán ñeà phaân chia, löïa choïn process thöïc thi sao cho ñöôïc hieäu quaû nhaát chieán löôïc ñònh thôøi CPU.  Ñònh thôøi CPU ‟ Choïn moät process (töø ready queue) thöïc thi. ‟ Vôùi moät multithreaded kernel, vieäc ñònh thôøi CPU laø do OS choïn kernel thread ñöôïc chieám CPU. 4 Khoa KTMT Caùc boä ñònh thôøi ready running suspended ready suspended blocked new terminated blocked Long-term scheduling Long-term scheduling Medium-term scheduling Medium-term scheduling Short-term scheduling 5 Khoa KTMT Caùc boä ñònh thôøi  Long-term scheduling ‟ Xaùc ñònh chöông trình naøo ñöôïc chaáp nhaän naïp vaøo heä thoáng ñeå thöïc thi ‟ Ñieàu khieån möùc ñoä multiprogramming cuûa heä thoáng ‟ Long term scheduler thöôøng coá gaéng duy trì xen laãn CPU-bound vaø I/O-bound process  Medium-term scheduling ‟ Process naøo ñöôïc ñöa vaøo (swap in), ñöa ra khoûi (swap out) boä nhôù chính ‟ Ñöôïc thöïc hieän bôûi phaàn quaûn lyù boä nhôù vaø ñöôïc thaûo luaän ôû phaàn quaûn lyù boä nhôù. 6 Khoa KTMT Caùc boä ñònh thôøi (tt) „ Short term scheduling  Xaùc ñònh process naøo trong ready queue seõ ñöôïc chieám CPU ñeå thöïc thi keá tieáp (coøn ñöôïc goïi laø ñònh thôøi CPU, CPU scheduling)  Short term scheduler coøn ñöôïc goïi vôùi teân khaùc laø dispatcher  Boä ñònh thôøi short-term ñöôïc goïi moãi khi coù moät trong caùc söï kieän/interrupt sau xaûy ra: ‟ t thôøi gian (clock interrupt) ‟ Ngaét ngoaïi vi (I/O interrupt) ‟ Lôøi goïi heä thoáng (operating system call) ‟ Signal Chöông naøy seõ taäp trung vaøo ñònh thôøi ngaén haïn 7 Khoa KTMT Dispatcher  Dispatcher seõ chuyeån quyeàn ñieàu khieån CPU veà cho process ñöôïc choïn bôûi boä ñònh thôøi ngaén haïn  Bao goàm: ‟ Chuyeån ngöõ caûnh (söû duïng thoâng tin ngöõ caûnh trong PCB) ‟ Chuyeån cheá ñoä ngöôøi duøng ‟ Nhaûy ñeán vò trí thích hôïp trong chöông trình öùng duïng ñeå khôûi ñoäng laïi chöông trình (chính laø program counter trong PCB)  Coâng vieäc naøy gaây ra phí toån ‟ Dispatch latency: thôøi gian maø dispatcher döøng moät process vaø khôûi ñoäng moät process khaùc 8 Khoa KTMT Caùc tieâu chuaån ñònh thôøi CPU  User-oriented ‟ Thôøi gian ñaùp öùng (Response time): khoaûng thôøi gian process nhaän yeâu caàu ñeán khi yeâu caàu ñaàu tieân ñöôïc ñaùp öùng (time- sharing, interactive system) cöïc tieåu ‟ Thôøi gian quay voøng (hoaøn thaønh) (Turnaround time): khoaûng thôøi gian töø luùc moät process ñöôïc naïp vaøo heä thoáng ñeán khi process ñoù keát thuùc cöïc tieåu ‟ Thôøi gian chôø (Waiting time): toång thôøi gian moät process ñôïi trong ready queue cöïc tieåu  System-oriented ‟ Söû duïng CPU (processor utilization): ñònh thôøi sao cho CPU caøng baän caøng toát cöïc ñaïi ‟ Coâng baèng (fairness): taát caû process phaûi ñöôïc ñoái xöû nhö nhau ‟ Thoâng löôïng (throughput): soá process hoaøn taát coâng vieäc trong moät ñôn vò thôøi gian cöïc ñaïi. 9 Khoa KTMT Hai yeáu toá cuûa giaûi thuaät ñònh thôøi  Haøm choïn löïa (selection function): duøng ñeå choïn process naøo trong ready queue ñöôïc thöïc thi (thöôøng döïa treân ñoä öu tieân, yeâu caàu veà taøi nguyeân, ñaëc ñieåm thöïc thi cuûa process,), ví duï „ w = toång thôøi gian ñôïi trong heä thoáng „ e = thôøi gian ñaõ ñöôïc phuïc vuï „ s = toång thôøi gian thöïc thi cuûa process (bao goàm caû “e”) 10 Khoa KTMT Hai yeáu toá cuûa giaûi thuaät ñònh thôøi (tt)  Cheá ñoä quyeát ñònh (decision mode): choïn thôøi ñieåm thöïc hieän haøm choïn löïa ñeå ñònh thôøi. Coù hai cheá ñoä ‟ Khoâng tröng duïng (Non-preemptive)  Khi ôû traïng thaùi running, process seõ thöïc thi cho ñeán khi keát thuùc hoaëc bò blocked do yeâu caàu I/O ‟ Tröng duïng (Preemptive)  Process ñang thöïc thi (traïng thaùi running) coù theå bò ngaét nöûa chöøng vaø chuyeån veà traïng thaùi ready bôûi heä ñieàu haønh  Chi phí cao hôn non-preemptive nhöng ñaùnh ñoåi laïi baèng thôøi gian ñaùp öùng toát hôn vì khoâng coù tröôøng hôïp moät process ñoäc chieám CPU quaù laâu. 11 Khoa KTMT Preemptive vaø Non-preemptive  Hàm định thời được thực hiện khi ( ) n từ ng i running sang waiting ( ) n từ ng i running sang ready ( ) n từ ng i waiting, new sang ready ( ) t c c thi 1 và 4 không cần lựa chọn loại định thời biểu, 2 và 3 cần  ng p , c i nh i nonpreemptive  ng p , c i nh i preemptive c n cơ o hơn? i sao? 12 Khoa KTMT Khaûo saùt giaûi thuaät ñònh thôøi  Service time = thôøi gian process caàn CPU trong moät chu kyø CPU-I/O  Process coù service time lôùn laø caùc CPU-bound process Process Arrival Time Service Time 1 0 3 2 2 6 3 4 4 4 6 5 5 8 2 load store add store read from file wait for I/O inc store write to file load store add store read from file wait for I/O wait for I/O I/O burst CPU burst CPU burst CPU burst I/O burst I/O burst moät chu kyø CPU-I/O 13 Khoa KTMT 1. First-Come First-Served (FCFS)  Haøm löïa choïn: Tieán trình naøo yeâu caàu CPU tröôùc seõ ñöôïc caáp phaùt CPU tröôùc; Process seõ thöïc thi ñeán khi keát thuùc hoaëc bò blocked do I/O  Cheá ñoä quyeát ñònh: non-preemptive algorithm  Hieän thöïc : söû duïng haøng ñôïi FIFO (FIFO queues) ‟ Tieán trình ñi vaøo ñöôïc theâm vaøo cuoái haøng ñôïi ‟ Tieán trình ñöôïc löïa choïn ñeå xöû lyù ñöôïc laáy töø ñaàu cuûa queues 0 5 10 15 20 P1 P2 P3 P4 P5 add run 14 Khoa KTMT FCFS Scheduling  Ví duï : Process Burst Time P1 24 P2 3 P3 3  Giaû söû thöù töï vaøo cuûa caùc tieán trình laø  P1, P2, P3  Thôøi gian chôø  P1 = 0;  P2 = 24;  P3 = 27;  Thôøi gian chôø trung bình  (0+24+27)/3 = 17 0 24 27 30 P1 P2 P3 Gantt Chart for Schedule 15 Khoa KTMT FCFS Scheduling  Ví duï: Process Burst Time P1 24 P2 3 P3 3  Giaû söû thôøi gian vaøo cuûa caùc tieán trình laø  P2, P3, P1  Thôøi gian chôø :  P1 = 6; P2 = 0; P3 = 3;  Thôøi gian chôø trung bình  (6+0+3)/3 = 3 , toát hôn.. 0 3 6 30 P1 P2 P3 Gantt Chart for Schedule Liệu có xảy ra trường hợp trì hoãn vô hạn định (starvation hay indefinte blocking) với giải thuật FCFS? Nhận xét 16 Khoa KTMT 2. Shortest-Job-First(SJF) Scheduling  Ñònh thôøi bieåu coâng vieäc ngaén nhaát tröôùc  Khi CPU ñöôïc töï do, noù seõ caáp phaùt cho tieán trình yeâu caàu ít thôøi gian nhaát ñeå keát thuùc ( tieán trình ngaén nhaát)  Lieân quan ñeán chieàu daøi thôøi gian söû duïng CPU cho laàn tieáp theo cuûa moãi tieán trình. Söû duïng nhöõng chieàu daøi naøy ñeå laäp lòch cho tieán trình vôùi thôøi gian ngaén nhaát. 17 Khoa KTMT 2. Shortest-Job-First(SJF) Scheduling  Hai hình thöùc (Schemes): ‟ Scheme 1: Non-preemptive( tieán trình ñoäc quyeàn CPU)  Khi CPU ñöôïc trao cho quaù trình noù khoâng nhöôøng cho ñeán khi noù keát thuùc chu kyø xöû lyù cuûa noù ‟ Scheme 2: Preemptive( tieán trình khoâng ñoäc quyeàn)  Neáu moät tieán trình CPU môùi ñöôïc ñöa vaøo danh saùch vôùi chieàu daøi söû duïng CPU cho laàn tieáp theo nhoû hôn thôøi gian coøn laïi cuûa tieán trình ñang xöû lyù noù seõ döøng hoaït ñoäng tieán trình hieän haønh (hình thöùc naøy coøn goïi laø Shortest- Remaining-Time-First (SRTF).) ‟ SJF laø toái öu ‟ cho thôøi gian chôø ñôïi trung bình toái thieåu vôùi moät taäp tieán trình cho tröôùc 18 Khoa KTMT Non-Preemptive SJF Scheduling  Ví duï : Process Arrival TimeBurst Time P1 0 7 P2 2 4 P3 4 1 P4 5 4 0 8 16 P1 P2 P3 Gantt Chart for Schedule P4 12 7 Average waiting time = (0+6+3+7)/4 = 4 19 Khoa KTMT Preemptive SJF Scheduling (hay Sortest Remaining Time First - SRTF)  Ví duï 1: Process Arrival TimeBurst Time P1 0 7 P2 2 4 P3 4 1 P4 5 4 0 7 16 P1 P2 P3 Gantt Chart for Schedule P4 11 5 Average waiting time = (9+1+0+2)/4 = 3 P2 P1 2 4 Process Arrival TimeBurst Time P1 0 8 P2 1 4 P3 2 9 P4 3 5 VD2: Thực hiện ở chế độ nào? 20 Khoa KTMT Nhaän xeùt veà giaûi thuaät SJF  Coù theå xaûy ra tình traïng “ñoùi” (starvation) ñoái vôùi caùc process coù CPU-burst lôùn khi coù nhieàu process vôùi CPU- burst nhoû ñeán heä thoáng.  Cô cheá non-preemptive khoâng phuø hôïp cho heä thoáng time sharing (interactive)  Giaûi thuaät SJF ngaàm ñònh ra ñoä öu tieân theo burst time  Caùc CPU-bound process coù ñoä öu tieân thaáp hôn so vôùi I/O-bound process, nhöng khi moät process khoâng thöïc hieän I/O ñöôïc thöïc thi thì noù ñoäc chieám CPU cho ñeán khi keát thuùc 21 Khoa KTMT Nhaän xeùt veà giaûi thuaät SJF  Tương ứng với mỗi process cần có độ dài của CPU burst tiếp theo  Hàm lựa chọn: chọn process có độ dài CPU burst nhỏ nhất  Chứng minh được: SJF tối ưu trong việc giảm thời gian đợi trung bình  Nhược điểm: Cần phải ước lượng thời gian cần CPU tiếp theo của process  Giải pháp cho vấn đề này? 22 Khoa KTMT Nhaän xeùt veà giaûi thuaät SJF (Thời gian sử dụng CPU chính là độ dài của CPU burst)  Trung bình tất cả các CPU burst đo được trong quá khứ  Nhưng thông thường những CPU burst càng mới càng phản ánh đúng hành vi của process trong tương lai  Một kỹ thuật thường dùng là sử dụng trung bình hàm mũ (exponential averaging) – τn+1 = a tn + (1 - a) τn , 0 a 1 – τn+1 = a tn + (1- a) a tn-1 ++ (1- a) jaτn-j ++ (1- a) n+1aτ0 – Nếu chọn a = ½ thì có nghĩa là trị đo được tn và trị dự đoán τn được xem quan trọng như nhau. 23 Khoa KTMT Dự đoán thời gian sử dụng CPU Độ dài CPU burst đo được Độ dài CPU burst dự đoán, với a = ½ và 0 = 10 24 Khoa KTMT 3. Priority Scheduling  Moãi process seõ ñöôïc gaùn moät ñoä öu tieân  CPU seõ ñöôïc caáp cho process coù ñoä öu tieân cao nhaát  Ñònh thôøi söû duïng ñoä öu tieân coù theå: ‟ Preemptive hoaëc ‟ Nonpreemptive 25 Khoa KTMT Gaùn ñoä öu tieân  SJF laø moät giaûi thuaät ñònh thôøi söû duïng ñoä öu tieân vôùi ñoä öu tieân laø thôøi-gian-söû-duïng- CPU-döï-ñoaùn.  Gaùn ñoä öu tieân coøn döïa vaøo: ‟ Yeâu caàu veà boä nhôù ‟ Soá löôïng file ñöôïc môû ‟ Tæ leä thôøi gian duøng cho I/O treân thôøi gian söû duïng CPU ‟ Caùc yeâu caàu beân ngoaøi ví duï nhö: soá tieàn ngöôøi duøng traû khi thöïc thi coâng vieäc 26 Khoa KTMT 3. Priority Scheduling  Vaán ñeà: trì hoaõn voâ haïn ñònh ‟ process coù ñoä öu tieân thaáp coù theå khoâng bao giôø ñöôïc thöïc thi  Giaûi phaùp: laøm môùi (aging) ‟ ñoä öu tieân cuûa process seõ taêng theo thôøi gian  Vd: ‟ IBM, MIT 1973 ‟ process 1967. – 0 – 127. Sau 15’ tăng độ ưu tiên 1 lần  khoãng bao lâu thì process được thực thi. 27 Khoa KTMT 4. Ñònh thôøi luaân phieân (Round Robin -RR)  Moãi process nhaän ñöôïc moät ñôn vò nhoû thôøi gian CPU (time slice, quantum time), thoâng thöôøng töø 10-100 msec ñeå thöïc thi. Sau khoaûng thôøi gian ñoù, process bò ñoaït quyeàn vaø trôû veà cuoái haøng ñôïi ready.  Neáu coù n process trong haøng ñôïi ready vaø quantum time = q thì khoâng coù process naøo phaûi chôø ñôïi quaù (n 1)q ñôn vò thôøi gian.  Hieäu suaát ‟ Neáu q lôùn: RR FCFS ‟ Neáu q nhoû (q khoâng ñöôïc quaù nhoû bôûi vì phaûi toán chi phí chuyeån ngöõ caûnh)  Thôøi gian chôø ñôïi trung bình cuûa giaûi thuaät RR thöôøng khaù lôùn nhöng thôøi gian ñaùp öùng nhoû 28 Khoa KTMT Ví duï Round Robin  Time Quantum = 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 0 P1 P4 P3 Gantt Chart for Schedule P1 P2 20 P3 P3 P3 P4 P1 37 57 77 97 117 121 134 154 162 turnaround time trung bình lôùn hôn SJF, nhöng ñaùp öùng toát hôn 29 Khoa KTMT RR vôùi time quantum = 1  Thôøi gian turn-around trung bình cao hôn so vôùi SJF nhöng coù thôøi gian ñaùp öùng trung bình toát hôn.  Öu tieân CPU-bound process  I/O-bound process thöôøng söû duïng raát ít thôøi gian cuûa CPU, sau ñoù phaûi blocked ñôïi I/O  CPU-bound process taän duïng heát quantum time, sau ñoù quay veà ready queue ñöôïc xeáp tröôùc caùc process bò blocked 30 Khoa KTMT Time quantum vaø context switch Process time = 10 quantum context switch 0 1 2 3 4 5 6 7 8 9 10 0 10 6 0 10 12 6 1 0 1 9 31 Khoa KTMT Thời gian hoàn thành và quantum time  Thời gian hoàn thành trung bình (average turnaround time) không chắc sẽ được cải thiện khi quantum lớn 32 Khoa KTMT Quantum vaø response time  Quantum time phaûi lôùn hôn thôøi gian duøng ñeå xöû lyù clock interrupt (timer) vaø thôøi gian dispatching  Neân lôùn hôn thôøi gian töông taùc trung bình (typical interaction) 33 Khoa KTMT Quantum time cho Round Robin*  Khi thực hiện process switch thì OS sẽ sử dụng CPU chứ không phải process của người dùng (OS overhead) – Dừng thực thi, lưu tất cả thông tin, nạp thông tin của process sắp thực thi  Performance tùy thuộc vào kích thước của quantum time (còn gọi là time slice), và hàm phụ thuộc này không đơn giản  Time slice ngắn thì đáp ứng nhanh – Vấn đề: có nhiều chuyển ngữ cảnh. Phí tổn sẽ cao.  Time slice dài hơn thì throughput tốt hơn (do giảm phí tổn OS overhead) nhưng thời gian đáp ứng lớn – Nếu time slice quá lớn, RR trở thành FCFS. 34 Khoa KTMT Quantum time cho Round Robin  Quantum time và thời gian cho process switch: – Nếu quantum time = 20 ms và thời gian cho process switch = 5 ms, như vậy phí tổn OS overhead chiếm 5/25 = 20% – Nếu quantum = 500 ms, thì phí tổn chỉ còn 1%  Nhưng nếu có nhiều người sử dụng trên hệ thống và thuộc loại interactive thì sẽ thấy đáp ứng rất chậm – Tùy thuộc vào tập công việc mà lựa chọn quantum time – Quantum time nên lớn trong tương quan so sánh với thời gian cho process switch – Ví dụ với 4.3 BSD UNIX, quantum time là 1 giây 35 Khoa KTMT Round Robin  Nếu có n process trong hàng đợi ready, và quantum time là q, như vậy mỗi process sẽ lấy 1/n thời gian CPU theo từng khối có kích thước lớn nhất là q – Sẽ không có process nào chờ lâu hơn (n - 1)q đơn vị thời gian  RR sử dụng một giả thiết ngầm là tất cả các process đều có tầm quan trọng ngang nhau – Không thể sử dụng RR nếu muốn các process khác nhau có độ ưu tiên khác nhau 36 Khoa KTMT Round Robin: nhược điểm  Các process dạng CPU-bound vẫn còn được “ưu tiên” – Ví dụ: Một I/O-bound process sử dụng CPU trong thời gian ngắn hơn quantum time và bị blocked để đợi I/O. Và Một CPU-bound process chạy hết time slice và lại quay trở về hàng đợi ready queue (ở phía trước các process đã bị blocked) 37 Khoa KTMT 5. Highest Response Ratio Next  Choïn process keá tieáp coù giaù trò RR (Response ratio) lôùn nhaát  Caùc process ngaén ñöôïc öu tieân hôn (vì service time nhoû) timeservice expected timeservice expected ingspent wait time RR 38 Khoa KTMT Highest Response Ratio Next Process Arrival Time Service Time 1 0 3 2 2 6 3 4 4 4 6 5 5 8 2 Quantumn time = 3 39 Khoa KTMT 6. Multilevel Queue Scheduling  Haøng ñôïi ready ñöôïc chia thaønh nhieàu haøng ñôïi rieâng bieät theo moät soá tieâu chuaån nhö ‟ Ñaëc ñieåm vaø yeâu caàu ñònh thôøi cuûa process ‟ Foreground (interactive) vaø background process,  Process ñöôïc gaùn coá ñònh vaøo moät haøng ñôïi, moãi haøng ñôïi söû duïng giaûi thuaät ñònh thôøi rieâng  Heä ñieàu haønh caàn phaûi ñònh thôøi cho caùc haøng ñôïi. ‟ Fixed priority scheduling: phuïc vuï töø haøng ñôïi coù ñoä öu tieân cao ñeán thaâp. Vaán ñeà: coù theå coù starvation. ‟ Time slice: moãi haøng ñôïi ñöôïc nhaän moät khoaûng thôøi gian chieám CPU vaø phaân phoái cho caùc process trong haøng ñôïi khoaûng thôøi gian ñoù. Ví duï:  80% cho haøng ñôïi foreground ñònh thôøi baèng RR.  20% cho haøng ñôïi background ñònh thôøi baèng giaûi thuaät FCFS. 40 Khoa KTMT Multilevel Queue Scheduling*  Ví dụ phân nhóm các quá trình System Processes Interactive Processes Batch Processes Student Processes Độ ưu tiên thấp nhất Độ ưu tiên cao nhất 41 Khoa KTMT 7. Haøng ñôïi phaûn hoài ña caáp Multilevel Feedback Queue  Vaán ñeà cuûa multilevel queue ‟ process khoâng theå chuyeån töø haøng ñôïi naøy sang haøng ñôïi khaùc khaéc phuïc baèng cô cheá feedback: cho pheùp process di chuyeån moät caùch thích hôïp giöõa caùc haøng ñôïi khaùc nhau.  Multilevel Feedback Queue ‟ Phaân loaïi processes döïa treân caùc ñaëc tính veà CPU-burst ‟ Söû duïng decision mode preemptive ‟ Sau moät khoaûng thôøi gian naøo ñoù, caùc I/O-bound process vaø interactive process seõ ôû caùc haøng ñôïi coù ñoä öu tieân cao hôn coøn CPU-bound process seõ ôû caùc queue coù ñoä öu tieân thaáp hôn. ‟ Moät process ñaõ chôø quaù laâu ôû moät haøng ñôïi coù ñoä öu tieân thaáp coù theå ñöôïc chuyeån ñeán haøng ñôïi coù ñoä öu tieân cao hôn (cô cheá nieân haïn, aging). 42 Khoa KTMT 7. Multilevel Feedback Queue  Ví duï: Coù 3 haøng ñôïi ‟ Q0 , duøng RR vôùi quantum 8 ms ‟ Q1 , duøng RR vôùi quantum 16 ms ‟ Q2 , duøng FCFS 43 Khoa KTMT 7. Multilevel Feedback Queue (tt)  Ñònh thôøi duøng multilevel feedback queue ñoøi hoûi phaûi giaûi quyeát caùc vaán ñeà sau ‟ Soá löôïng haøng ñôïi bao nhieâu laø thích hôïp? ‟ Duøng giaûi thuaät ñònh thôøi naøo ôû moãi haøng ñôïi? ‟ Laøm sao ñeå xaùc ñònh thôøi ñieåm caàn chuyeån moät process ñeán haøng ñôïi cao hôn hoaëc thaáp hôn? ‟ Khi process yeâu caàu ñöôïc xöû lyù thì ñöa vaøo haøng ñôïi naøo laø hôïp lyù nhaát? 44 Khoa KTMT So saùnh caùc giaûi thuaät  Giaûi thuaät ñònh thôøi naøo laø toát nhaát?  Caâu traû lôøi phuï thuoäc caùc yeáu toá sau: ‟ Taàn xuaát taûi vieäc (System workload) ‟ Söï hoã trôï cuûa phaàn cöùng ñoái vôùi dispatcher ‟ Söï töông quan veà troïng soá cuûa caùc tieâu chuaån ñònh thôøi nhö response time, hieäu suaát CPU, throughput, ‟ Phöông phaùp ñònh löôïng so saùnh 45 Khoa KTMT Đọc thêm  Policy và Mechanism  Định thời trên hệ thống multiprocessor  Đánh giá giải thuật định thời CPU  Định thời trong một số hệ điều hành thông dụng  Nguồn: Operating System Concepts. Sixth Edition. John Wiley & Sons, Inc. 2002. Silberschatz, Galvin, Gagne 46 Khoa KTMT Bài tập Xét 1 tập các process sau có thời gian thực thi CPU tính bằng mili giây: Giả sử thứ tự đến để thực thi của các process là P1, P2, P3, P4, P5. (tất cả process này đều đến tại thời điểm bằng 0). 1. Vẽ sơ đồ Gautt thực thi của các process theo giải thuật định thời: FCFS, SJF, RR (quantumn = 1). Ở cả 2 chế độ preemptive và nonpreemptive. 2. Thời gian đợi của các process trong từng giải thuật định thời? Process Burst - time Priority P1 10 3 P2 1 1 P3 2 3 P4 1 4 p5 5 2 47 Khoa KTMT Bài tập 3. Tính thời gian hoàn thành(turnaround time) của từng process cho từng giải thuật? Trong các giải thuật sau, giải thuật nào có thể gây ra trường hợp 1 process có thể không bao giờ được thực thi: 1. First come, first serve 2. Shortest job first 3. Round robin 4. Priority. Giải thích lý do tại sao xảy ra trường hợp trên? 48 Khoa KTMT Bài tập 1. RR với q = 2 2. Preemptive Priority với số càng lớn càng ưu tiên 3. Điều phối ưu tiên nhiều cấp xoay vòng, sử dụng 2 cấp: Cấp 1 sử dụng giải thuật robin round với quantumn = 3ms. Cấp 2 sử dụng giải thuật SRTF. Một process nếu đã ở cấp I 5ms sẽ được chuyển xuống cấp II nếu đang ở trạng thái waiting còn nếu đang ở trạng thái running thì sau khi ra khỏi sẽ chuyển. Ngược lại một process đang ở cấp II sau khoãng thời gian 10ms sẽ được chuyển lên I. Khi các process vào bộ nhớ chính thì điều vào hàng đợi cấp I. 49 Khoa KTMT Bài tập  Cho 4 tiến trình A, B, C, D với thời gian vào ready list và thời gian cần CPU cho các lần thứ 1, thứ 2, thứ 3 và thời gian thực hiện I/O tương ứng như bản sau:  Vẽ giản Gantt, Tính thời gian đợi trung bình, Thời gian đáp ứng trung bình, Thời gian lưu lại trong hệ thống trung bình cho các giải thuật (câu 1, 2 chỉ dùng thời gian thực thi 1st execution time như là burst time) 1. FCFS 2. RR với q = 3 3. SRFT cho cả 3 lần exec