Bài giảng Hệ điều hành: Chương 4 - ThS. Hà Lê Hoài Thương
lượt xem 21
download
Trong chương 4 Định thời CPU thuộc bài giảng hệ điều hành nhằm trình bày về các kiến thức: khái niệm cơ bản về định thời, các bộ định thời như long-term, mid-term, short-term, các tiêu chuẩn định thời CPU, các giải thuật định thời Shortest Job First (SJF).
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Hệ điều hành: Chương 4 - ThS. Hà Lê Hoài Thương
- 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 Khoa KTMT 1
- 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 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 Long-term Long-term scheduling scheduling Medium-term suspended scheduling Short-term ready ready scheduling running Medium-term suspended scheduling blocked terminated blocked Khoa KTMT 4
- 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ôù. Khoa KTMT 5
- 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 naøy seõ taäp trung vaøo ñònh thôøi Chöông ngaén haïn Khoa KTMT 6
- 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 Khoa KTMT 7
- 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. Khoa KTMT 8
- 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”) Khoa KTMT 9
- 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. Khoa KTMT 10
- 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? Khoa KTMT 11
- Khaûo saùt giaûi thuaät ñònh thôøi load store add store CPU burst moät chu kyø read from file CPU-I/O Arrival Service wait for I/O I/O burst Process Time Time inc store 1 0 3 CPU burst write to file 2 2 6 wait for I/O I/O burst 3 4 4 load store 4 6 5 add store CPU burst 5 8 2 read from file wait for I/O I/O burst … 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 Khoa KTMT 12
- 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 run add Khoa KTMT 13
- FCFS Scheduling Ví duï : Giaû söû thöù töï vaøo cuûa caùc tieán trình laø Process Burst Time P1 24 P1, P2, P3 P2 3 Thôøi gian chôø P3 3 P1 = 0; P2 = 24; Gantt Chart for Schedule P3 = 27; P1 P2 P3 Thôøi gian chôø trung bình 0 24 27 30 (0+24+27)/3 = 17 Khoa KTMT 14
- FCFS Scheduling Ví duï: Giaû söû thôøi gian vaøo cuûa Process Burst Time caùc tieán trình laø P1 24 P2, P3, P1 P2 3 Thôøi gian chôø : P3 3 P1 = 6; P2 = 0; P3 = 3; Thôøi gian chôø trung bình Gantt Chart for Schedule (6+0+3)/3 = 3 , toát P2 P3 P1 hôn.. 0 3 6 30 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? Khoa KTMT Nhận xét 15
- 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. Khoa KTMT 16
- 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 Khoa KTMT 17
- Non-Preemptive SJF Scheduling Ví duï : Process Arrival TimeBurst Time P1 0 7 P2 2 4 P3 4 1 P4 5 4 Gantt Chart for Schedule P1 P3 P2 P4 0 7 8 12 16 Average waiting time = (0+6+3+7)/4 = 4 Khoa KTMT 18
- Preemptive SJF Scheduling (hay Sortest Remaining Time First - SRTF) Ví duï 1: Process Arrival TimeBurst Time Thực hiện ở P1 0 7 chế độ nào? P2 2 4 P3 4 1 P4 5 4 VD2: Gantt Chart for Schedule Process Arrival TimeBurst Time P1 0 8 P1 P2 P3 P2 P4 P1 P2 1 4 0 2 4 5 7 11 16 P3 2 9 P4 3 5 Average waiting time = (9+1+0+2)/4 = 3 Khoa KTMT 19
- 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 Khoa KTMT 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Hệ điều hành: Chương 1 - ThS. Hà Lê Hoài Thương
39 p | 182 | 33
-
Bài giảng Hệ điều hành - Chương 1: Giới thiệu hệ điều hành
32 p | 167 | 16
-
Bài giảng Hệ điều hành: Chương 9 - ĐH Bách khoa TP HCM
56 p | 116 | 13
-
Bài giảng Hệ điều hành: Chương 2 - Trần Công Án (ĐH Cần Thơ)
39 p | 137 | 11
-
Bài giảng Hệ điều hành - Chương 5: Quản lý vào ra
30 p | 166 | 10
-
Bài giảng Hệ điều hành: Chương 1 - Phan Xuân Huy
25 p | 143 | 9
-
Bài giảng Hệ điều hành: Chương 1C - Cấu trúc hệ điều hành
22 p | 133 | 9
-
Bài giảng Hệ điều hành: Chương 2 - Hà Duy An (ĐH Cần Thơ)
45 p | 106 | 9
-
Bài giảng Hệ điều hành: Chương 1 - Nguyễn Phan Trung
43 p | 122 | 9
-
Bài giảng Hệ điều hành: Chương 2 - ThS. Hà Lê Hoài Trung
20 p | 123 | 9
-
Bài giảng Hệ điều hành: Chương 2 - ThS. Phan Đình Duy
36 p | 79 | 7
-
Bài giảng Hệ điều hành: Chương 1 - TS. Ngô Hữu Dũng
60 p | 122 | 7
-
Bài giảng Hệ điều hành: Chương 1 - Đặng Minh Quân
23 p | 75 | 6
-
Bài giảng Hệ điều hành: Chương 1 - ThS. Huỳnh Triệu Vỹ
156 p | 78 | 5
-
Bài giảng Hệ điều hành - Chương 1: Tổng quan hệ điều hành (Lương Minh Huấn)
109 p | 46 | 5
-
Bài giảng Hệ điều hành: Chương 1 - ĐH Bách khoa TP Hồ Chí Minh
26 p | 119 | 5
-
Bài giảng Hệ điều hành: Chương 2 - ĐH Công nghệ thông tin
36 p | 68 | 3
-
Bài giảng Hệ điều hành - Chương 1: Mở đầu
13 p | 86 | 3
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn