›
›

Bài giảng Hệ điều hành - Chương 5: Định thời CPU - Thoại Nam

Khái niệm cơ bản o Các bộ định thời

- long-term, mid-term, short-term o Các tiêu chuẩn định thời CPU o Các giải thuật định thời

- First-Come, First-Served (FCFS) - Round-Robin (RR)

- Shortest Job First (SJF)

- Shortest Remaining Time First (SRTF)

- Highest Response Ratio Next (HRRN) - Multilevel Queue

- Multilevel Feedback Queue

pdf 14 trang xuanthi 30/12/2022 2540
Download
Bạn đang xem tài liệu "Bài giảng Hệ điều hành - Chương 5: Định thời CPU - Thoại Nam", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pdfbai_giang_he_dieu_hanh_chuong_5_dinh_thoi_cpu_thoai_nam.pdf

Nội dung text: Bài giảng Hệ điều hành - Chương 5: Định thời CPU - Thoại Nam

  1. Khaùi nieäm cô baûn ‰ Trong caùc heä thoáng multi-tasking – 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. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.3- Caùc boä ñònh thôøi new Long-Term Long-Term scheduling scheduling suspended Medium -Term Short-Term ready ready scheduling scheduling running suspended Medium -Term blocked blocked scheduling terminated Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.4- 2
  2. Short-Term Scheduling ‰ Xaùc ñònh process naøo trong ready queue seõ ñöôïc chieám CPU ñeå thöïc thi keá tieáp (do vaäy 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: – clock interrupt – I/O interrupt – operating system call, trap – signal Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.7- Caùc tieâu chuaån ñònh thôøi CPU ‰ User-oriented – 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 – 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 – Waiting Time: toång thôøi gian moät process ñôïi trong ready queue → cöïc tieåu ‰ System-oriented – processor utilization: ñònh thôøi sao cho CPU caøng baän caøng toát → cöïc ñaïi – fairness: taát caû process phaûi ñöôïc ñoái xöû nhö nhau – throughput: soá process hoaøn taát coâng vieäc trong moät ñôn vò thôøi gian → cöïc ñaïi. Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.8- 4
  3. First-Come First-Served (FCFS) ‰ Haøng ñôïi Ready laø moät haøng ñôïi kieåu FIFO ‰ Selection function: process naøo ñôïi laâu nhaát trong ready queue seõ ñöôïc choïn thöïc thi ‰ Decision mode: non-preemptive – Process seõ thöïc thi ñeán khi keát thuùc hoaëc bò blocked do I/O 0 51015 20 P1 P2 P3 P4 P5 ‰Process naøo khoâng coù thöïc hieän I/O seõ ñöôïc ñoäc chieám CPU. ‰Caùc process I/O-bound (ít CPU-burst) khoâng ñöôïc öu tieân baèng caùc process CPU-bound (nhieàu CPU-burst) Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.11- Shortest Job First (SJF) ‰ Selection function: process naøo coù ñoä daøi CPU burst keá tieáp nhoû nhaát seõ ñöôïc choïn thöïc thi. ‰ Decision mode: non-preemptive ‰ I/O-bound process seõ ñöôïc öu tieân hôn so vôùi CPU- bound process ‰ Yeâu caàu: phaûi öôùc tính ñöôïc CPU-burst cuûa process 0510 15 20 P1 P2 P3 P4 P5 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.12- 6
  4. Ví duï öôùc tính ñoä daøi CPU Burst Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.15- Nhaän xeùt veà giaûi thuaät SJF ‰ Coù theå xaûy ra tình traïng “cheát ñ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 (interractive) ‰ 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 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.16- 8
  5. 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 9 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 9 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 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.19- Time Quantum vaø Context Switch C ontext Q uantum Process time = 10 Switch 12 0 010 6 1 0106 1 10 012345678910 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.20- 10
  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 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.23- Multilevel Queue Scheduling Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.24- 12
  7. Multilevel Feedback Queue (t.t) ‰ Ñònh thôøi baè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? Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.27- 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: – 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 Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM -6.28- 14