Bài giảng Hệ điều hành (Operating Systems) - Hà Lê Hoài Trung - Chương 4: Định thời 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 
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 
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?