Bài giảng Hệ điều hành (Operating Systems) - Chương I: Tổng quan hệ điều hành - Vũ Đức Lung

vaø ñöôïc thaûo luaän ôû phaàn quaûn lyù boä nhôù. 5Khoa 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: – Ngắt thôøi gian (clock interrupt) – Ngaét ngoaïi vi (I/O interrupt) – Lôøi goïi heä thoáng (operating system call) – SignalChöông naøy seõ taäp trung vaøo ñònh thôøi ngaén haïn 6Khoa 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 27Khoa 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. 8Khoa 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”) 9Khoa 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. 10Khoa KTMT Preemptive vaø Non-preemptive
Hàm định thời được thực hiện khi (1) Chuyển từ trạng thái running sang waiting (2) Chuyển từ trạng thái running sang ready (3) Chuyển từ trạng thái waiting, new sang ready (4) Kết thúc thự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
Trường hợp 1, 4 được gọi là định thời nonpreemptive
Trường hợp 2, 3 được gọi là định thời preemptive Thực hiện cơ chế nào khó hơn? Tại sao? 11Khoa 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 285 564 443 622 301 Service Time Arrival Time Process 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 12Khoa 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 addrun 313Khoa 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 14Khoa 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 P1P2 P3 Gantt Chart for Schedule 15Khoa 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. 16Khoa 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 17Khoa 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 P2P3 Gantt Chart for Schedule P4 127 Average waiting time = (0+6+3+7)/4 = 4 18Khoa 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 P2P3 Gantt Chart for Schedule P4 115 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: 419Khoa 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 20Khoa 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? 21Khoa 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. 22Khoa 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 23Khoa 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 24Khoa 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 525Khoa 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: 26Khoa 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û 27Khoa KTMT Ví duï Round Robin
Time Quantum = 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 0 P1 P4P3 Gantt Chart for Schedule P1P2 20 P3 P3 P3P4 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 28Khoa 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 29Khoa KTMT Time quantum vaø context switch Process time = 10 quantum context switch 0 1 2 3 4 5 6 7 8 9 10 0 106 0 10 12 6 1 0 1 9 30Khoa 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 631Khoa 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) 32Khoa 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. 33Khoa 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 34Khoa 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 35Khoa 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) 36Khoa 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 737Khoa 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 vaø 20% cho haøng ñôïi background ñònh thôøi baèng giaûi thuaät FCFS. 38Khoa 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 39Khoa 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). 40Khoa 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 41Khoa 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? 42Khoa 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 843Khoa 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