【文章內(nèi)容簡介】 e end of the ready queue （每個(gè)進(jìn)程將得到小單位的 CPU時(shí)間 [時(shí)間片 ]，通常為 10100毫 秒。時(shí)間片用完后，該進(jìn)程將被搶占并插入就緒隊(duì)列末尾） . Round Robin (RR) ? If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n1)q time units（假定就緒隊(duì)列中有 n個(gè)進(jìn)程、時(shí)間量為 q, 則每個(gè)進(jìn)程每次得到 1/n的、不超過 q單位的成塊 CPU時(shí)間，沒有任何一個(gè)進(jìn)程的等待時(shí)間會(huì)超過 (n1) q單位） . ? Performance（特性） ? q large ? FIFO ? q small ? q must be large with respect to context switch, otherwise overhead is too high（ q相對(duì)于切換上下文的時(shí)間而言足夠長，否則將導(dǎo)致系統(tǒng)開銷過大） . Example: RR with Time Quantum = 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 ? The Gantt chart is: ? Typically, higher average turnaround than SJF, but better response（一般來說， RR的平均周轉(zhuǎn)時(shí)間比 SJF長，但響應(yīng)時(shí)間要短一些） . P1 P2 P3 P4 P1 P3 P4 P1 P3 P3 0 20 37 57 77 97 117 121 134 154 162 How a Smaller Time Quantum Increases Context Switches ? Longer quantum yields shorter average turnaround times Turnaround Time Varies With The Time Quantum 一組進(jìn)程的平均周轉(zhuǎn)時(shí)間并不一定隨著時(shí)間片的增大而降低。一般來說，如果大多數(shù)（80%）進(jìn)程能在一個(gè)時(shí)間片內(nèi)完成，就會(huì)改善平均周轉(zhuǎn)時(shí)間 Multilevel Queue ? Ready queue is partitioned into separate queues（就緒隊(duì)列分為） : foreground (interactive)（前臺(tái)） [交互式 ] background (batch) （后臺(tái)） [批處理 ] ? Each queue has its own scheduling algorithm （每個(gè)隊(duì)列有自己的調(diào)度算法） foreground – RR background – FCFS ? Scheduling must be done between the queues（調(diào)度須在隊(duì)列間進(jìn)行） . Multilevel Queue ? Fixed priority scheduling。 ., serve all from foreground then from background. Possibility of starvation（固定優(yōu)先級(jí)調(diào)度，即前臺(tái)運(yùn)行完后再運(yùn)行后臺(tái)。有可能產(chǎn)生饑餓） . ? Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes。 .,80% to foreground in RR 20% to background in FCFS （給定時(shí)間片調(diào)度，即每個(gè)隊(duì)列得到一定的 CPU時(shí)間，進(jìn)程在給定時(shí)間內(nèi)執(zhí)行；如，80%的時(shí)間執(zhí)行前臺(tái)的 RR調(diào)度， 20%的時(shí)間執(zhí)行后臺(tái)的FCFS調(diào)度） Multilevel Queue Scheduling Multilevel Feedback Queue ? 存在多個(gè)就緒隊(duì)列，具有不同的優(yōu)先級(jí)，各自按時(shí)間片輪轉(zhuǎn)法調(diào)度 ? 各個(gè)就緒隊(duì)列中時(shí)間片的大小各不相同，優(yōu)先級(jí)越高的隊(duì)列時(shí)間片越小。 ? 當(dāng)一個(gè)進(jìn)程執(zhí)行完一個(gè)完整的時(shí)間片后被搶占處理器，被搶占的進(jìn)程優(yōu)先級(jí)降低一級(jí)而進(jìn)入下級(jí)就緒隊(duì)列，如此繼續(xù)，直至降到進(jìn)程的基本優(yōu)先級(jí)。 而一個(gè)進(jìn)程從阻塞態(tài)變?yōu)榫途w態(tài)時(shí)要提高優(yōu)先級(jí) ? 終端型作業(yè) ? 短批處理作業(yè) ? 長批處理作業(yè) Multilevel Feedback Queue ? A process can move between the various queues。 aging can be implemented this way（進(jìn)程能在不同的隊(duì)列間移動(dòng)；可實(shí)現(xiàn)老化） . ? Multilevelfeedbackqueue scheduler defined by the following parameters（多級(jí)反饋隊(duì)列調(diào)度程序由以下參數(shù)定義） : ? number of queues（隊(duì)列數(shù)） ? scheduling algorithms for each queue（每一隊(duì)列的調(diào)度算法） ? method used to determine when to upgrade a process（決定進(jìn)程升級(jí)的方法） ? method used to determine when to demote a process（決定進(jìn)程降級(jí)的方法） ? method used to determine which queue a process will enter when that process needs service（決定需要服務(wù)的進(jìn)程將進(jìn)入哪個(gè)隊(duì)列的方法） Multilevel Feedback Queues Example of Multilevel Feedback Queue ? Three queues: ? Q0 – time quantum 8 milliseconds ? Q1 – time quantum 16 milliseconds ? Q2 – FCFS ? Scheduling ? A new job enters queue Q0 which is served FCFS. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1（新的作業(yè)進(jìn)入FCFS的 Q0隊(duì)列，它得到 CPU時(shí)能使用 8毫秒，如果它不能在 8毫秒內(nèi)完成，將移動(dòng)到隊(duì)列 Q1 ） . ? At Q1 job is again served FCFS and receives 16 additional milliseconds. If it still does not plete, it is preempted and moved to queue Q2（作業(yè)在 Q1仍將作為 FCFS調(diào)度，能使用附加的 16毫秒，如果它還不能完成，將被搶占，移至隊(duì)列 Q2 ） . Highest Response Ratio Next (HRRN) 高響應(yīng)比優(yōu)先 (作業(yè) )調(diào)度算法 ? 高響應(yīng)比優(yōu)先調(diào)度算法 —基于優(yōu)先權(quán)算法 在每次選擇作業(yè)投入運(yùn)行時(shí)，先計(jì)算后備作業(yè)隊(duì)列中每個(gè)作業(yè)的響應(yīng)比 RP,然后選擇其值最大的作業(yè)投入運(yùn)行。 ? RP值定義為： RP＝（ 已等待時(shí)間＋要求運(yùn)行時(shí)間）／要求運(yùn)行時(shí)間 ＝ 1＋ 已等待時(shí)間／要求運(yùn)行時(shí)間。 Highest Response Ratio Next (HRRN) 高響應(yīng)比優(yōu)先 (作業(yè) )調(diào)度算法 HRRN算法實(shí)際上是 FCFS算法和 SJF算法的折衷 ? 優(yōu)點(diǎn)： ? 等待時(shí)間相同，則 SJF； ? 要求的服務(wù)時(shí)間相同，則 FCFS； ? 長作業(yè)的優(yōu)先級(jí)隨著等待時(shí)間的增加而提高，不會(huì)出現(xiàn)得不到響應(yīng)的情況。 ? 缺點(diǎn) : ? 作業(yè)調(diào)度程序要統(tǒng)計(jì)作業(yè)的等待時(shí)間 ， 作浮點(diǎn)運(yùn)算（ 這是系統(tǒng)程序最忌諱的 ） 浪費(fèi)大量的計(jì)算時(shí)間 。 例 假定在一個(gè)處理機(jī)上執(zhí)行以下五個(gè)作業(yè)： 作業(yè)號(hào) A B C D E 到達(dá)時(shí)間 0 1 2 3 4 運(yùn)行時(shí)間 4 3 5 2 4 分別采用 FCFS、 SJF、 RR（ 時(shí)間片＝ 1 ） 和HRRN(高響應(yīng)比優(yōu)先 )四種調(diào)度算法時(shí) ， 試做： （ 1） 畫出調(diào)度圖； （ 2） 計(jì)算每個(gè)作業(yè)的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間 ； （ 3）計(jì)算平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間 。 調(diào)度圖： T 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 FCFS A A A A B B B C C C C C D D E E E E SJF A A A A D D B B B E E E E C C C C C RR A B C D E A B C D E A B C E A C E C HRN A A A A B B B D D C C C C C E E E E 作業(yè)號(hào) A B C D E 平均到達(dá)時(shí)間 0 1 2 3 4運(yùn)行時(shí)間 4 3 5 2 4完成時(shí)間 4 ① 7 ② 12 ③ 14 ④ 18 ⑤周轉(zhuǎn)時(shí)間 4 6 10 11 14 9FC FS帶權(quán)周轉(zhuǎn)時(shí)間 1 2 2