Hệ điều hành

Ñònh thôøi CPU Chöông IV: Ñònh thôøi CPU Chöông IV:

 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

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

ﬁ

Caùc boä ñònh thôøi

new

Long-term scheduling Long-term scheduling

ready

suspended ready

Medium-term scheduling

running

Short-term scheduling

blocked

terminated

suspended blocked

Khoa KTMT

Medium-term scheduling

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

 Medium-term scheduling

CPU-bound vaø I/O-bound process

– 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

Khoa KTMT

thaûo luaän ôû phaàn quaûn lyù boä nhôù.

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:

Chöông naøy seõ taäp trung vaøo ñònh thôøi ngaén haïn

– Ngắ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

Khoa KTMT

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

 Coâng vieäc naøy gaây ra phí toån

ñeå khôûi ñoäng laïi chöông trình (chính laø program counter trong PCB)

– Dispatch latency: thôøi gian maø dispatcher döøng moät

Khoa KTMT

process vaø khôûi ñoäng moät process khaùc

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

 System-oriented

ñôïi trong ready queue ﬁ cöïc tieåu

– 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

Khoa KTMT

– Thoâng löôïng (throughput): soá process hoaøn taát coâng vieäc 7

trong moät ñôn vò thôøi gian ﬁ cöïc ñaïi.

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û

Khoa KTMT

“e”)

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

Preemptive vaø Nonpreemptive

ệ

ự

̣ ́

̉ ừ ̉ ừ ̉ ừ ̣ ́

́ ́

ạ ị ờ

c th c hi n khi  Hàm đ nh th i đ ờ ượ ị trang thai running sang waiting (1) Chuyên t trang thai running sang ready (2) Chuyên t trang thai waiting, new sang ready (3) Chuyên t (4) Kêt thuc th 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 h p 1, 4 đ ng h p 2, 3 đ

 Tr  Tr

̣ ̀ ̣

ờ nonpreemptive ờ preemptive

ườ ườ

ợ ợ

Th c hiên c chê nao kho h n? Tai sao?

̣ ơ

́ ơ

ự

ọ ể c goi la đinh th i ượ c goi la đinh th i ượ ̣ ̀ ̣

Khoa KTMT

́ ̀ ̣

Khaûo saùt giaûi thuaät ñònh thôøi

CPU burst

load store add store read from file

moät chu kyø CPU-I/O

Process

I/O burst

wait for I/O

Arrival Time

Service Time

CPU burst

inc store write to file

wait for I/O

I/O burst

CPU burst

load store add store read from file

I/O burst

wait for I/O …

 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 Khoa KTMT

process

1. FirstCome FirstServed (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

P1 P2 P3 P4 P5

run

add

Khoa KTMT

FCFS Scheduling

 Ví duï :

 Giaû söû thöù töï vaøo cuûa

 Thôøi gian chôø

 P1 = 0;  P2 = 24;  P3 = 27;

Process Burst Time 24 P1 3 P2 3 P3

 Thôøi gian chôø trung bình  (0+24+27)/3 = 17

caùc tieán trình laø  P1, P2, P3

Gantt Chart for Schedule

P1

P2 P3

0

24

27

30

Khoa KTMT

FCFS Scheduling

 Giaû söû thôøi gian vaøo cuûa

 Ví duï:

caùc tieán trình laø  P2, P3, P1

 Thôøi gian chôø :

 P1 = 6; P2 = 0; P3 = 3;  Thôøi gian chôø trung bình

 (6+0+3)/3 = 3 , toát hôn..

Process Burst Time 24 P1 3 P2 3 P3

Gantt Chart for Schedule

P2

P3

P1

0

3

6

30

Khoa KTMT

2. ShortestJobFirst(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

2. ShortestJobFirst(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

Khoa KTMT

thieåu vôùi moät taäp tieán trình cho tröôùc

NonPreemptive SJF Scheduling

 Ví duï :

Process Arrival TimeBurst Time P1 P2 P3 P4

0 2 4 5

7 4 1 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

Preemptive SJF Scheduling(SRTF)

 Ví duï 1:

Process Arrival TimeBurst Time 7 P1 4 P2 1 P3 4 P4

0 2 4 5

VD2:

Gantt Chart for Schedule

P1

P2

P3

P2

P4

P1

0

2

4

5

7

11

16

Process Arrival TimeBurst Time 8 P1 4 P2 9 P3 5 P4

0 1 2 3

Average waiting time = (9+1+0+2)/4 = 3

Khoa KTMT

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

Nhaän xeùt veà giaûi thuaät SJF

 T

ng ng v i m i process c n có đ dài c a CPU burst ti p

ươ ứ

ủ

ế

ầ

ớ

ộ

ỗ

theo

ỏ

ộ

i u trong vi c gi m th i gian đ i trung

 Hàm l a ch n: ch n process có đ dài CPU burst nh nh t ấ ọ ự  Ch ng minh đ ợ ố ư

ọ ượ : SJF t c

ệ

ả

ờ

ứ bình

c đi m

c l

ng th i gian c n CPU ti p theo

ể : C n ph i ầ

ả ướ ượ

ế

ầ

ờ

ượ

 Nh c a process ủ  Gi

ả

i pháp cho v n đ này? ấ

ề

Khoa KTMT

Nhaän xeùt veà giaûi thuaät SJF

(Th i gian s d ng CPU chính là đ dài c a CPU burst)

t c các CPU b

ộ urst đo đ

ứ

ờ  Trung bình t  Nh ng thông th ư

ữ

ả

ng lai

 M t k thu t th

ủ ử ụ c trong quá kh ượ ấ ả urst càng m i càng ph n ng nh ng CPU b ớ ườ ánh đúng hành vi c a process trong t ươ ủ ng dùng là s d ng ườ

ử ụ trung bình hàm mũ

ộ ỹ

a £

c t

ọ

ị

ượ n và tr d đoán

τn

ậ (exponential averaging) – τn+1 = a tn + (1 - a) τn , 0 £ – τ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 xem quan tr ng nh nhau. ọ

ế ượ

Khoa KTMT

(cid:160)

D đoán th i gian s d ng CPU

ử ụ

ự

ờ

dài CPU burst

Độ o đ đượ

dài CPU burst d oán,

Độ v i ớ

ự đ 0 = 10

Khoa KTMT

a = ½ và t

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å:

Khoa KTMT

– Preemptive hoaëc – Nonpreemptive

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

Khoa KTMT

duøng traû khi thöïc thi coâng vieäc

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:

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

FCFS

– Neáu q lôùn: RR (cid:222) – Neáu q nhoû (q khoâng ñöôïc quaù nhoû bôûi vì phaûi toán

 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û

Khoa KTMT

chi phí chuyeån ngöõ caûnh)

Ví duï Round Robin

 Time Quantum = 20

Process Burst Time 53 P1 17 P2 68 P3 24 P4

Gantt Chart for Schedule

P1

P2

P3

P4

P1

P3

P4 P1

P3 P3

0

20

37

57

77 97 117 121 134

154 162

Khoa KTMT

turnaround time trung bình lôùn hôn SJF, nhöng ñaùp öùng toát hôn

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

ñöôïc xeáp tröôùc caùc

 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 (cid:222) process bò blocked

Khoa KTMT

Time quantum vaø context switch

quantum

Process time = 10

context switch

0

10

6

0

10

0

1

2

3

4

5

6

7

8

9

10

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

ờ ắ ẽ ượ ả

ệ

ớ

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)

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

ẽ ử ụ ứ ả ệ

 Performance tùy thu c vào kích th

t c thông tin, n p thông tin c a process s p th c thi ự i dùng ( c a ng ườ ủ – D ng th c thi, l u t ự ừ ạ ắ

OS overhead) ư ấ ả ộ ọ

 Time slice ng n thì đáp ng nhanh

slice), và hàm ph thu c này không đ n gi n ả ộ ụ ự ủ c c a quantum time (còn g i là time ướ ủ ơ

ứ ắ

ấ ề ề ữ ả

t h n (do gi m phí t n OS overhead) – V n đ : có nhi u chuy n ng c nh. Phí t n s cao. ể ổ ổ ẽ ả ố ơ

 Time slice dài h n thì throughput t ơ nh ng th i gian đáp ng l n ớ – N u time slice quá l n, RR tr thành FCFS. ớ

ứ ư ờ

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 ư ờ

ổ ế

» 1%

ế v y phí t n OS overhead chi m 5/25 = 20% ậ – N u quantum = 500 ms, thì phí t n ch còn ế  Nh ng n u có nhi u ng ế ư ạ ộ

interactive thì s th y đáp ng r t ch m ổ ỉ ườ ử ụ ấ ề ẽ ấ i s d ng trên h th ng và thu c lo i ệ ố ứ ậ

– Tùy thu c vào t p công vi c mà l a ch n quantum time ệ ự ậ ọ ộ

– Time slice nên l n trong t ng quan so sánh v i th i gian cho process ớ ươ ớ ờ

switch

Khoa KTMT

– Ví d v i 4.3 BSD UNIX, time slice là 1 giây ụ ớ

Round Robin

n process trong hàng đ i ready, và quantum time là

q, nh ư n th i gian CPU theo t ng kh i có kích

ừ

ố

ợ ờ

thi

t c các process đ u có t m

ế

ả

ộ

ấ ả

ề

ầ

 N u có ế v y m i process s l y 1/ ẽ ấ ậ ỗ q th c l n nh t là ấ ướ ớ – S không có process nào ch lâu h n ( ẽ ờ t ng m là t  RR s d ng m t gi ầ ử ụ ọ

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

ơ n - 1)q đ n v th i gian ơ ị ờ

ể ử ụ ộ ư ế ố

Khoa KTMT

khác nhau

Round Robin: nh

ượ

c đi m ể

 Các process d ng CPU-bound v n còn đ

c “ u tiên” ẫ ạ ượ ư

– Ví d : ụ ộ ử ụ ắ ơ ờ

quantum time và b ị blocked đ đ i I/O. Và

 M t I/O-bound process s d ng CPU trong th i gian ng n h n ể ợ ế ạ ộ i quay tr v hàng ở ề

Khoa KTMT

c các process đã b blocked)  M t CPU-bound process ch y h t time slice và l ị đ i ợ ready queue ( phía tr ạ ướ ở

5. Highest Response Ratio Next

time spent wait

time

=RR

+ ing expected service expected service time

 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û)

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 vaø 20% cho haøng ñôïi background ñònh thôøi baèng giaûi thuaät FCFS.

Khoa KTMT

Multilevel Queue Scheduling*

 Ví d phân nhóm các quá trình

ụ

ộ ư

Đ u tiên cao nh t ấ System Processes

Interactive Processes

Batch Processes

Student Processes

Đ u tiên th p nh t ấ

ộ ư

ấ

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

khaéc phuïc baèng cô cheá

haøng ñôïi khaùc (cid:222) 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.

Khoa KTMT

– 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). 39

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

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?

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

Khoa KTMT

Đ c thêm

ọ

ị

ả

ờ

 Policy và Mechanism  Đ nh th i trên h th ng multiprocessor ệ ố ờ i thu t đ nh th i CPU  Đánh giá gi ậ ị  Đ 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

Khoa KTMT