Hệ điều hành 1 - Chương 4: Định thời CPU

Trong các hệ thống multitasking - Thực thi nhiều chương trình đồng thời làm tăng hiệu suất hệ thống. - Tại mỗi thời điểm, chỉ có một process được thực thi. Do đó, cần phải giải quyết vấn đề phân chia, lựa chọn process thực thi sao cho được hiệu quả nhất  chiến lược định thời CPU. Định thời CPU - Chọn một process (từ ready queue) thực thi. - Với một multithreaded kernel, việc định thời CPU là do OS chọn kernel thread được...
Nội dung trích xuất từ tài liệu:
Hệ điều hành 1 - Chương 4: Định thời CPU Chöông 4: Ñònh thôøi CPU Khoa KTMT 1 Noäi dung  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) – Round-Robin (RR) – Shortest Job First (SJF) vaø Shortest Remaining Time First (SRTF) – Priority Scheduling – Highest Response Ratio Next (HRRN) – Multilevel Queue – Multilevel Feedback Queue Khoa KTMT 2 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. Khoa KTMT 3 Caùc boä ñònh thôøi new new Long-term Long-term scheduling scheduling Medium-term suspended suspended scheduling Short-term ready ready ready ready scheduling running running Medium-term suspended suspended scheduling blocked blocked terminated blocked blocked terminated Khoa KTMT 4 Caùc haøng ñôïi ñònh thôøi Khoa KTMT 5 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 – Söï chuyeån ñoåi döïa treân söï caàn thieát ñeå quaûn lyù multiprogramming – Ñöôï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ôù. Khoa KTMT 6 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: – clock interrupt – I/O interrupt – operating system call, trap – signal Khoa KTMT 7 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 veà user mode – 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 Khoa KTMT 8 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 KTMT 9 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”)  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ä – 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 – 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 Khoa KTMT ñoäc chieám CPU quaù laâu.10 process Khaûo saùt giaûi thuaät ñònh thôøi load store add store CPU burst moät chu kyø read from file ...