Bài giảng Hệ điều hành - Chương 5: Định thời CPU - Thoại Nam
Chöông 5
Ñònh thôøi CPU
-6.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)
– Shortest Job First (SJF)
– Shortest Remaining Time First (SRTF)
– Highest Response Ratio Next (HRRN)
– Multilevel Queue
– Multilevel Feedback Queue
-6.2-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
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.
-6.3-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Caùc boä ñònh thôøi
new
Long-Term
scheduling
Long-Term
scheduling
Medium-Term
scheduling
suspended
ready
Short-Term
scheduling
ready
running
Medium-Term
scheduling
suspended
blocked
blocked
terminated
-6.4-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
2
Caùc haøng ñôïi ñònh thôøi
-6.5-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
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
ï
i
– Ñöôï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ôù.
-6.6-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
3
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
-6.7-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
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
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.
-6.8-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
4
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ä
– Nonpreemptive
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
process ñoäc chieám CPU quaù laâu.
-6.9-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Khaûo saùt giaûi thuaät ñònh thôøi
loadstore
CPU burst
addstore
readfrom file
chu kyø
CPU-I/O
Arrival Service
Process
I/O burst
waitforI/O
Time
Time
incstore
writetofile
1
2
3
5
0
2
4
8
3
6
4
2
CPU burst
waitforI/O
I/O burst
l
a
readfrom file
waitforI/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
-6.10-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
5
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
5
10
15 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)
-6.11-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
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
0
5
10
15
20
P1
P2
P3
P4
P5
-6.12-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
6
Öôùc tính ñoä daøi cuûa CPU Burst
Ñoä daøi cuûa CPU Burst chæ coù theå öôùc tính xaáp xæ
duøng pheùp tính trung bình haøm muõ (exponential
average) döïa treân ñoä daøi cuûa CPU-burst tröôùc.
1. tn = ñoä daøi thöïc söï cuûa CPU burst thöù n
2. τn+1: giaù trò öôùc ñoaùn cuûa CPU burst (n + 1)
3. α, 0 ≤ α ≤ 1
4. Ñoä daøi öôùc tính CPU burst thöù n+1 laø:
τ n+1 = αt +
1− α τ n
)
n
-6.13-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Öôùc tính ñoä daøi cuûa CPU Burst (t.t)
Khai trieån coâng thöùc:
τ n+1 = αt +
1− α
)
τ n
n
= αt +
(
1− α
)
αt +
i
(
1− α
2ατ n−1
)
n
n
n−1
n−1
= α
− α + α τ
∑
i=0
Giaù trò τ1 khoâng öôùc tính maø thöôøng gaùn = 0
α=0 ⇒τn+1 = τn ⇒ khoâng quan taâm ñeán “quaù khöù”
α=1 ⇒τn+1 = tn ⇒ chæ quan taâm ñeán “ngaøy hoâm qua”
α=1/2
-6.14-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
7
Ví duï öôùc tính ñoä daøi CPU Burst
-6.15-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
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
-6.16-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
8
Shortest Remaining Time First
Töông töï nhö SJF nhöng decision mode laø
preemptive
Yeâu caàu: phaûi öôùc tính ñöôïc CPU-burst cuûa process
0
5
10
15
20
P1
P2
P3
P4
P5
-6.17-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
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.
H
– 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û
-6.18-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
9
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
-6.19-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Time Quantum vaø Context Switch
Context
Quantum
Processtime=10
Switch
0
12
0
0
0
10
10
10
6
1
10
1
2
3
4
5
6
7
8
9
-6.20-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
10
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)
-6.21-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Highest Response Ratio Next
0
5
10
15
20
P1
P2
P3
P4
P5
timespentwaiting+ expectedservicetime
expectedservicetime
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û)
-6.22-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
11
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
-6.23-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Multilevel Queue Scheduling
-6.24-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
12
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)
-6.25-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
Multilevel Feedback Queue (t.t)
-6.26-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
13
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?
-6.27-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
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,
– Phöông phaùp ñònh löôïng so saùnh
-6.28-
Khoa Coâng Ngheä Thoâng Tin – Ñaïi Hoïc Baùch Khoa Tp.HCM
14
14 trang
13000
Free
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:
- bai_giang_he_dieu_hanh_chuong_5_dinh_thoi_cpu_thoai_nam.pdf
