04 處理機(jī)調(diào)度.ppt

1、第四章 處理機(jī)調(diào)度,4.1 分級調(diào)度 4.2 作業(yè)調(diào)度 4.3 進(jìn)程調(diào)度 4.4 調(diào)度算法,處理機(jī)調(diào)度的工作是對CPU資源進(jìn)行合理的分配使用，以提高處理機(jī)利用率，并使各用戶公平地得到處理機(jī)資源。所以，本章的主要問題是：,學(xué)習(xí)目標(biāo)： 1.掌握：作業(yè)和進(jìn)程的關(guān)系、作業(yè)的狀態(tài)及其轉(zhuǎn)換；作業(yè)調(diào)度和進(jìn)程調(diào)度的功能；常用的調(diào)度算法。 2.理解：性能評價(jià)標(biāo)準(zhǔn)；調(diào)度算法的評價(jià)。 3.了解：其他調(diào)度算法。 學(xué)習(xí)要點(diǎn)： 本章的重點(diǎn)在于掌握系統(tǒng)中對作業(yè)和進(jìn)程如何實(shí)施調(diào)度，作業(yè)調(diào)度和進(jìn)程調(diào)度的功能；掌握常用調(diào)度算法的實(shí)現(xiàn)思想，并能計(jì)算出各個(gè)算法的性能指標(biāo)；能簡單分析常用調(diào)度算法的性能。,4.1 分級調(diào)度,返回,1.

2、調(diào)度層次 2. 作業(yè)的狀態(tài)及轉(zhuǎn)換 3. 作業(yè)和進(jìn)程的關(guān)系 4. 調(diào)度的性能準(zhǔn)則,調(diào)度：選出待分派的作業(yè)或進(jìn)程。處理機(jī)調(diào)度的目的是分配處理機(jī)。,1. 調(diào)度層次,高級調(diào)度（宏觀調(diào)度、作業(yè)調(diào)度） 把外存上處于后備隊(duì)列中的那些作業(yè)調(diào)入內(nèi)存，并創(chuàng)建進(jìn)程，分配資源，將進(jìn)程加入就緒隊(duì)列。由于這種調(diào)度決定哪些作業(yè)可以進(jìn)入系統(tǒng)，所以也稱收容調(diào)度。作業(yè)一旦被系統(tǒng)收容，就便成進(jìn)程或進(jìn)程組。 中級調(diào)度（交換調(diào)度：內(nèi)外存交換） 從存儲器資源的角度看，將把暫時(shí)不能運(yùn)行的進(jìn)程調(diào)至外存就緒，將當(dāng)前所需部分換入到內(nèi)存，提高內(nèi)存利用率和系統(tǒng)吞吐量。中級調(diào)度實(shí)際上是存儲器之間的對換。,低級調(diào)度（微觀調(diào)度、進(jìn)程調(diào)度） 決定就緒隊(duì)列中

3、的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)（即低級調(diào)度是將處理機(jī)分配給進(jìn)程） ，低級調(diào)度是由每秒可操作許多次的處理機(jī)調(diào)度程序執(zhí)行，處理機(jī)調(diào)度程序應(yīng)常駐內(nèi)存。 兩種調(diào)度方式：非搶占方式：進(jìn)程一直執(zhí)行直到完成或發(fā)生某事件被阻塞。搶占方式：由于優(yōu)先權(quán)、短作業(yè)優(yōu)先或時(shí)間片到等因素，終止現(xiàn)行進(jìn)程。 線程調(diào)度：可有OS內(nèi)核完成，也可由用戶程序進(jìn)行。,調(diào)度隊(duì)列模型,2. 作業(yè)的狀態(tài)及其轉(zhuǎn)換,作業(yè)從提交給系統(tǒng)，直到完成任務(wù)退出系統(tǒng)前，在整個(gè)活動(dòng)過程中它會(huì)處于不同的狀態(tài)。通常，作業(yè)的狀態(tài)分為：提交、后備（收容）、運(yùn)行和完成。,提交狀態(tài)：一個(gè)作業(yè)處于從輸入設(shè)備進(jìn)入外部存儲設(shè)備的過程時(shí)所處的狀態(tài) 后備狀態(tài)：作業(yè)的全部信息都已通過輸入設(shè)

4、備輸入作業(yè)的輸入井中等待進(jìn)入內(nèi)存。 運(yùn)行狀態(tài)：作業(yè)一旦被作業(yè)調(diào)度程序選中，分配所需的資源，為其建立進(jìn)程，而被送入內(nèi)存中投入運(yùn)行。 完成狀態(tài)：作業(yè)完成其全部運(yùn)行，釋放出其所占用的資源，準(zhǔn)備退出系統(tǒng)時(shí)的作業(yè)。,3. 作業(yè)與進(jìn)程的關(guān)系,作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體； 進(jìn)程是計(jì)算機(jī)為了完成用戶任務(wù)實(shí)體而設(shè)置的執(zhí)行實(shí)體。 計(jì)算機(jī)要完成一個(gè)任務(wù)實(shí)體，必須要有一個(gè)以上的執(zhí)行實(shí)體，一個(gè)作業(yè)總是由一個(gè)以上的多個(gè)進(jìn)程組成。 分時(shí)系統(tǒng)中無作業(yè)的概念，進(jìn)程幾乎存在于所有多道程序設(shè)計(jì)系統(tǒng)中。,4. 調(diào)度的性能準(zhǔn)則,我們可從不同的角度來判斷調(diào)度算法的性能，如用戶的角度、處理機(jī)的角度和算法實(shí)現(xiàn)的角度。實(shí)際的調(diào)度算法

5、選擇是一個(gè)綜合的判斷結(jié)果。,面向用戶的調(diào)度性能準(zhǔn)則,周轉(zhuǎn)時(shí)間：作業(yè)從提交到完成（得到結(jié)果）所經(jīng)歷的時(shí)間。包括：在后備隊(duì)列中等待，CPU上執(zhí)行，就緒隊(duì)列和阻塞隊(duì)列中等待，結(jié)果輸出等待批處理系統(tǒng) 平均周轉(zhuǎn)時(shí)間T 平均帶權(quán)周轉(zhuǎn)時(shí)間W （帶權(quán)周轉(zhuǎn)時(shí)間W是 T(周轉(zhuǎn))/T(CPU執(zhí)行) 響應(yīng)時(shí)間：用戶輸入一個(gè)請求（如擊鍵）到系統(tǒng)給出首次響應(yīng)（如屏幕顯示）的時(shí)間分時(shí)系統(tǒng),面向系統(tǒng)的調(diào)度性能準(zhǔn)則,吞吐量：單位時(shí)間內(nèi)所完成的作業(yè)數(shù)，跟作業(yè)本身特性和調(diào)度算法都有關(guān)系批處理系統(tǒng)。 平均周轉(zhuǎn)時(shí)間不是吞吐量的倒數(shù)，因?yàn)椴l(fā)執(zhí)行的作業(yè)在時(shí)間上可以重疊。如：在2小時(shí)內(nèi)完成4個(gè)作業(yè)，而每個(gè)周轉(zhuǎn)時(shí)間是1小時(shí)，則吞吐量是2個(gè)作

6、業(yè)/小時(shí)。 處理機(jī)利用率：大中型主機(jī)。 各種設(shè)備的均衡利用：如CPU繁忙的作業(yè)和I/O繁忙的作業(yè)搭配大中型主機(jī)。 公平性：不因作業(yè)或進(jìn)程本身的特性而使上述指標(biāo)過分惡化。如長作業(yè)等待很長時(shí)間。 優(yōu)先級：可以使關(guān)鍵任務(wù)達(dá)到更好的指標(biāo)。,調(diào)度算法本身的調(diào)度性能準(zhǔn)則,易于實(shí)現(xiàn) 執(zhí)行開銷比,4.2 作業(yè)調(diào)度,返回,1. 作業(yè)控制塊 2. 作業(yè)調(diào)度及功能 3. 作業(yè)調(diào)度目標(biāo)與性能衡量,作業(yè)調(diào)度的任務(wù)：完成作業(yè)從后備狀態(tài)到運(yùn)行狀態(tài)的轉(zhuǎn)變，以及從運(yùn)行態(tài)到完成態(tài)的轉(zhuǎn)變。,1.作業(yè)控制塊,在多道批處理系統(tǒng)中通常有若干作業(yè)被收容在輸入井中，為了管理和調(diào)度作業(yè)，就必須記錄已進(jìn)入系統(tǒng)的各作業(yè)的情況，系統(tǒng)為每個(gè)作業(yè)設(shè)置了

7、一個(gè)作業(yè)控制塊（JCB）。 內(nèi)容：作業(yè)名、作業(yè)狀態(tài)、作業(yè)調(diào)度，以及資源申請和一些控制信息。,作業(yè)控制塊JCB,2. 作業(yè)調(diào)度及功能,作業(yè)調(diào)度的任務(wù)：完成作業(yè)從后備狀態(tài)到運(yùn)行狀態(tài)的轉(zhuǎn)變，以及從運(yùn)行態(tài)到完成態(tài)的轉(zhuǎn)變。,作業(yè)調(diào)度的轉(zhuǎn)換過程 (1)作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài) P85(a)框圖 (2)作業(yè)從執(zhí)行狀態(tài)到完成狀態(tài) P85(b)框圖,后備作業(yè)隊(duì)列空,按調(diào)度算法從作 業(yè)中選出一作業(yè),調(diào)用存儲、設(shè)備管理 程序，審核資源要求,資源要求能滿足？,放棄該 作業(yè),否,分配資源,調(diào)用進(jìn)程管理 程序建立進(jìn)程,進(jìn)程調(diào)度,否,是,出 口,作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài),是,調(diào)用存儲管理、設(shè)備管理程序 回收分配該作業(yè)的全部

8、資源要求,撤消該作業(yè)的所有進(jìn)程及作業(yè)的JCB,調(diào)用統(tǒng)計(jì)程序，計(jì)算該作業(yè)的 執(zhí)行費(fèi)用,調(diào)度下一個(gè)作業(yè),作業(yè)從執(zhí)行狀態(tài)到完成狀態(tài),作業(yè)調(diào)度的功能,具體說來，作業(yè)調(diào)度的功能如下：,記錄系統(tǒng)中各個(gè)作業(yè)的情況；（記錄情況） 按照某種調(diào)度算法從后備作業(yè)隊(duì)列中選取作業(yè)；（挑選作業(yè)） 為被選取的作業(yè)分配內(nèi)存和外設(shè)資源；（分配資源） 為選中的作業(yè)建立相應(yīng)的進(jìn)程。（建立進(jìn)程） 在作用運(yùn)行完畢或運(yùn)行過程中因某種原因需要撤離時(shí)，作業(yè)調(diào)度程序還有完成作業(yè)的善后處理工作，如收回分配給他的全部資源，它們將從系統(tǒng)中撤消。（善后處理）,3.作業(yè)調(diào)度的目標(biāo)與性能衡量,調(diào)度的目標(biāo),對所有作業(yè)應(yīng)該是公平合理 應(yīng)使設(shè)備有高的利用率 每

9、天執(zhí)行盡可能多的作業(yè) 有快的響應(yīng)時(shí)間,要設(shè)計(jì)一個(gè)理想的調(diào)度算法是一件十分困難的事,在實(shí)際系統(tǒng)中，調(diào)度算法往往折衷考慮。設(shè)計(jì)調(diào)度算法時(shí)應(yīng)考慮的因素： 調(diào)度算法應(yīng)與系統(tǒng)設(shè)計(jì)目標(biāo)保持一致 注意系統(tǒng)資源均衡使用 保證提交的作業(yè)在截止時(shí)間內(nèi)完成 設(shè)法縮短作業(yè)平均周轉(zhuǎn)時(shí)間 大多數(shù)操作系統(tǒng)都采用比較簡單的調(diào)度算法,假定某一作業(yè)到達(dá)的時(shí)間為Tsi，它被選中執(zhí)行，得到計(jì)算結(jié)果的時(shí)間為Tei 。 作業(yè)的周轉(zhuǎn)時(shí)間為Ti Tei Tsi 作業(yè)平均周轉(zhuǎn)時(shí)間為： T 其中，n為作業(yè)流中的作業(yè)數(shù),作業(yè)平均周轉(zhuǎn)時(shí)間,調(diào)度算法性能的衡量,平均帶權(quán)周轉(zhuǎn)時(shí)間,作業(yè)的帶權(quán)周轉(zhuǎn)時(shí)間為Wi Ti /ri W= 其中，ri 為某作業(yè)i的實(shí)

10、際執(zhí)行時(shí)間,4.3 進(jìn)程調(diào)度,要解決的問題： WHAT：按什么原則分配CPU 進(jìn)程調(diào)度算法 WHEN：何時(shí)分配CPU 進(jìn)程調(diào)度的時(shí)機(jī) HOW： 如何分配CPU CPU調(diào)度過程（進(jìn)程的上下文切換）,1. 進(jìn)程調(diào)度的功能 2. 進(jìn)程調(diào)度的時(shí)機(jī) 3. 進(jìn)程調(diào)度的方式 4. 進(jìn)程調(diào)度的過程 5. 進(jìn)程調(diào)度性能衡量,1. 進(jìn)程調(diào)度的功能,進(jìn)程調(diào)度的任務(wù)是控制協(xié)調(diào)進(jìn)程對CPU的競爭，即按一定的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把CPU的使用權(quán)交給被選中的進(jìn)程。,進(jìn)程調(diào)度的功能： 1. 記錄所有進(jìn)程的運(yùn)行狀況（靜態(tài)和動(dòng)態(tài)）； 2. 選擇適當(dāng)?shù)倪M(jìn)程分派CPU ； 3. 完成進(jìn)程上下文切換。,在進(jìn)程（上下文）中

11、切換的步驟 保存處理器的上下文，包括程序計(jì)數(shù)器和其它寄存器 用新狀態(tài)和其它相關(guān)信息更新正在運(yùn)行進(jìn)程的PCB 把原來的進(jìn)程移至合適的隊(duì)列-就緒、阻塞 選擇另一個(gè)要執(zhí)行的進(jìn)程 更新被選中進(jìn)程的PCB 從被選中進(jìn)程中重裝入 CPU 上下文,2. 進(jìn)程調(diào)度的時(shí)機(jī),當(dāng)一個(gè)進(jìn)程運(yùn)行完畢，或由于某種錯(cuò)誤而終止運(yùn)行。(完成任務(wù)) 執(zhí)行完系統(tǒng)調(diào)用，在系統(tǒng)程序返回用戶進(jìn)程時(shí)，可認(rèn)為系統(tǒng)進(jìn)程執(zhí)行完畢，從而可調(diào)度選擇一新的用戶進(jìn)程執(zhí)行。(完成任務(wù)) 執(zhí)行中的進(jìn)程自己調(diào)用的阻塞原語將自己阻塞起來進(jìn)入等待狀態(tài)。(等待資源) 執(zhí)行中的進(jìn)程執(zhí)行了P原語操作，從而因資源不足而被阻塞，或調(diào)用了V原語操作激活了等待資源的進(jìn)程隊(duì)列。

12、 (等待資源) 執(zhí)行中的進(jìn)程提出I/O請求后被阻塞。 (等待資源) 分時(shí)系統(tǒng)中時(shí)間片到。 (時(shí)間片到) 當(dāng)有一個(gè)優(yōu)先級更高的進(jìn)程就緒（可搶占式），例如：新創(chuàng)建一個(gè)進(jìn)程，一個(gè)等待進(jìn)程變成就緒。(發(fā)現(xiàn)重調(diào)標(biāo)志),引起進(jìn)程調(diào)度的原因有以下幾類：,3. 進(jìn)程調(diào)度的方式,可搶占式 Preemptive（可剝奪式）： 當(dāng)有比正在運(yùn)行的進(jìn)程優(yōu)先級更高的進(jìn)程就緒時(shí)，系統(tǒng)可強(qiáng)行剝奪正在運(yùn)行進(jìn)程的CPU，提供給具有更高優(yōu)先級的進(jìn)程使用。 不可搶占式 Non-preemptive（非剝奪式）： 某一進(jìn)程被調(diào)度運(yùn)行后，除非由于它自身的原因不能運(yùn)行，否則一直運(yùn)行下去。,4. 進(jìn)程調(diào)度過程,保存現(xiàn)場 選擇要運(yùn)行的程序 恢

13、復(fù)現(xiàn)場,作業(yè)調(diào)度與進(jìn)程調(diào)度,作業(yè)調(diào)度為進(jìn)程活動(dòng)做準(zhǔn)備，進(jìn)程調(diào)度使進(jìn)程活動(dòng)起來； 作業(yè)調(diào)度次數(shù)少，進(jìn)程調(diào)度頻率高； 有的系統(tǒng)無作業(yè)調(diào)度，但進(jìn)程調(diào)度必不可少。,5. 進(jìn)程調(diào)度性能衡量,具有公平性 資源利用率高（特別是CPU利用率） 在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間（越短越好） 在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量,4.4 調(diào)度算法,1. 先來先服務(wù)算法 2. 時(shí)間片輪轉(zhuǎn)算法 3. 短作業(yè)優(yōu)先算法 4. 最高響應(yīng)比優(yōu)先算法 5. 多級隊(duì)列算法 6. 優(yōu)先級算法 7. 多級反饋隊(duì)列算法,返回,針對不同的系統(tǒng)，往往采用的調(diào)度算法不相同，在操作系統(tǒng)中存在著多種調(diào)度算法， 通常有的算法適用于作業(yè)調(diào)度，有的算法

14、適用于進(jìn)程調(diào)度，有的兩者都適應(yīng)。,先來先服務(wù)調(diào)度算法 （FCFS，F(xiàn)irst Come First Serve）,基本思想：按照作業(yè)提交或進(jìn)程變?yōu)榫途w狀態(tài)的先后次序，調(diào)入系統(tǒng)或分派CPU ，換句話說，調(diào)度程序每次選擇的作業(yè)/進(jìn)程是等待時(shí)間最久的，而不管其運(yùn)行時(shí)間的長短。這種調(diào)度算法突出的優(yōu)點(diǎn)是實(shí)現(xiàn)簡單，效率較低，在一些實(shí)際的系統(tǒng)和一般應(yīng)用程序中采用這種算法的較多。 既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度,先來先服務(wù)（FCFS）調(diào)度算法舉例,2. 時(shí)間片輪轉(zhuǎn)算法(Round Robin),將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列。 每次調(diào)度時(shí)將CPU分派給隊(duì)首進(jìn)程，讓其執(zhí)行一個(gè)時(shí)間片。時(shí)

15、間片的長度從幾個(gè)ms到幾百ms。 在一個(gè)時(shí)間片結(jié)束時(shí)，發(fā)生時(shí)鐘中斷。調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊(duì)列的末尾，并通過上下文切換執(zhí)行當(dāng)前的隊(duì)首進(jìn)程。 進(jìn)程可以未使用完一個(gè)時(shí)間片，就出讓CPU（如阻塞）。,一般用于進(jìn)程調(diào)度（為什么不用于作業(yè)調(diào)度？）,基本思想：,時(shí)間片長度的確定,時(shí)間片長度變化的影響 過長退化為FCFS算法，進(jìn)程在一個(gè)時(shí)間片內(nèi)都執(zhí)行完。 過短用戶的一次請求需要多個(gè)時(shí)間片才能處理完，上下文切換次數(shù)增加。 對響應(yīng)時(shí)間的要求： T(響應(yīng)時(shí)間)=N(進(jìn)程數(shù)目)*q(時(shí)間片) 時(shí)間片長度的影響因素： 系統(tǒng)的響應(yīng)時(shí)間：時(shí)間片越大，響應(yīng)時(shí)間越長（當(dāng)進(jìn)程數(shù)目一定時(shí)）； 就緒進(jìn)程的數(shù)目

16、：數(shù)目越多，時(shí)間片越?。ó?dāng)響應(yīng)時(shí)間一定時(shí)）； 進(jìn)程的轉(zhuǎn)換時(shí)間能力：為保證系統(tǒng)開銷不大于某個(gè)標(biāo)準(zhǔn)，應(yīng)使進(jìn)程的轉(zhuǎn)換時(shí)間/時(shí)間片不大于某一數(shù)值，如1/10； CPU運(yùn)行指令速度：CPU運(yùn)行速度快，則時(shí)間片可以短些，反之，則取長些。,04年考題,簡答題 某系統(tǒng)中，進(jìn)程調(diào)度采用“時(shí)間片輪轉(zhuǎn)”的策略。每個(gè)進(jìn)程得到的時(shí)間片隨進(jìn)程執(zhí)行情況而變化，在過去的時(shí)間里，若進(jìn)程經(jīng)常產(chǎn)生中斷，則給它分配較短的時(shí)間片；若中斷次數(shù)很少，則分給一個(gè)較長的時(shí)間片? 請回答： (1)為什么給經(jīng)常產(chǎn)生中斷的進(jìn)程分配較短的時(shí)間片，而很少產(chǎn)生中斷的進(jìn)程分得較長的時(shí)間片？ (2)如果有兩個(gè)就緒隊(duì)列，一個(gè)是時(shí)間片較短的進(jìn)程就緒隊(duì)列，另一個(gè)時(shí)

17、間片較長的進(jìn)程就緒隊(duì)列，在進(jìn)程調(diào)度時(shí)應(yīng)該優(yōu)先從哪個(gè)隊(duì)列中選取一個(gè)就緒進(jìn)程占有CPU？為什么？,3. 短作業(yè)優(yōu)先調(diào)度算法 (SJF, Shortest Job First),基本思想：對預(yù)計(jì)執(zhí)行時(shí)間短的作業(yè)（進(jìn)程）優(yōu)先處理。通常后來的短作業(yè)不搶先正在執(zhí)行的作業(yè)。 在一般情況下這種調(diào)度算法比先來先服務(wù)調(diào)度算法的效率要高一些。實(shí)現(xiàn)相對先來先服務(wù)調(diào)度算法要困難些，如果作業(yè)的到來順序及運(yùn)行時(shí)間不合適，會(huì)出現(xiàn)餓死現(xiàn)象，例如，系統(tǒng)中有一個(gè)運(yùn)行時(shí)間很長的作業(yè)J，和幾個(gè)運(yùn)行時(shí)間小的作業(yè)，然后，不斷地有運(yùn)行時(shí)間小于J的作業(yè)的到來，這樣，作業(yè)J就得不可調(diào)度而餓死。另外，作業(yè)運(yùn)行的估計(jì)時(shí)間也有問題。,又稱為“短進(jìn)程優(yōu)

18、先”SPN(Shortest Process Next)；這是對FCFS算法的改進(jìn)，其目標(biāo)是減少平均周轉(zhuǎn)時(shí)間。,既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度,SJF的特點(diǎn),優(yōu)點(diǎn)： 縮短作業(yè)的等待時(shí)間； 提高系統(tǒng)的吞吐量； 比FCFS平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間短,缺點(diǎn)： 對長作業(yè)非常不利，可能長時(shí)間得不到執(zhí)行； 未能依據(jù)作業(yè)的緊迫程度來劃分執(zhí)行的優(yōu)先級； 難以準(zhǔn)確估計(jì)作業(yè)（進(jìn)程）的執(zhí)行時(shí)間，從而影響調(diào)度性能。,SJF的變型,最短剩余時(shí)間優(yōu)先SRT(Shortest Remaining Time) 允許比當(dāng)前進(jìn)程剩余時(shí)間更短的進(jìn)程來搶占,先來先服務(wù)調(diào)度算法和短作業(yè)優(yōu)先調(diào)度算法比較舉例,4. 最高響應(yīng)比優(yōu)

19、先調(diào)度算法 HRN(Highest Response_Ratio Next),基本思想： （FCFS和SJF的折衷） 先來先服務(wù)和短作業(yè)優(yōu)先算法都有其片面性，先來先服務(wù)調(diào)度算法只考慮作業(yè)的等待時(shí)間，而忽視了作業(yè)的運(yùn)行時(shí)間，短作業(yè)優(yōu)先算法則相反，只考慮了作業(yè)的運(yùn)行時(shí)間，而忽視了作業(yè)的等待時(shí)間。響應(yīng)比高者優(yōu)先調(diào)度算法是介于這兩種算法之間的一種拆衷的算法。,既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度,5. 多級隊(duì)列算法 (Multiple-level Queue),根據(jù)作業(yè)或進(jìn)程的性質(zhì)或類型的不同，將后備或就緒隊(duì)列再分為若干個(gè)子隊(duì)列。 各隊(duì)列有不同的調(diào)度算法。 既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度,6. 優(yōu)先

20、級算法(Priority cheduling),(1) 靜態(tài)優(yōu)先級 (2) 動(dòng)態(tài)優(yōu)先級 (3) 線性優(yōu)先級調(diào)度算法（SRR, SelfishRound Robin),本算法是對優(yōu)先級高的作業(yè)（進(jìn)程）優(yōu)先處理 。用于作業(yè)調(diào)度和進(jìn)程調(diào)度，可分成搶先式和非搶先式。,(1) 靜態(tài)優(yōu)先級,依據(jù)： 進(jìn)程類型（系統(tǒng)進(jìn)程優(yōu)先級較高） 對資源的需求（對CPU和內(nèi)存需求較少的進(jìn)程，優(yōu)先級較高） 用戶要求（緊迫程度和付費(fèi)多少）,優(yōu)先級在創(chuàng)建進(jìn)程時(shí)就確定，直到進(jìn)程終止前都不改變。通常是一個(gè)整數(shù)。,(2) 動(dòng)態(tài)優(yōu)先級,在就緒隊(duì)列中，等待時(shí)間延長則優(yōu)先級提高，從而使優(yōu)先級較低的進(jìn)程在等待足夠的時(shí)間后，其優(yōu)先級提高到可被調(diào)

21、度執(zhí)行； 進(jìn)程每執(zhí)行一個(gè)時(shí)間片，就降低其優(yōu)先級，從而一個(gè)進(jìn)程持續(xù)執(zhí)行時(shí)，其優(yōu)先級降低到出讓CPU。,在創(chuàng)建進(jìn)程時(shí)賦予的優(yōu)先級，在進(jìn)程運(yùn)行過程中可以自動(dòng)改變，以便獲得更好的調(diào)度性能。如：,(3) 線性優(yōu)先級調(diào)度算法（SRR, Selfish Round Robin）,就緒進(jìn)程隊(duì)列分成兩個(gè)： 新創(chuàng)建進(jìn)程隊(duì)列：按FCFS方式排成；進(jìn)程優(yōu)先級按速率a增加； 享受服務(wù)隊(duì)列：已得到過時(shí)間片服務(wù)的進(jìn)程按FCFS方式排成；進(jìn)程優(yōu)先級按速率b增加；（ab0） 新創(chuàng)建進(jìn)程轉(zhuǎn)入享受服務(wù)隊(duì)列的確定：當(dāng)新創(chuàng)建進(jìn)程優(yōu)先級與享受服務(wù)隊(duì)列中最后一個(gè)進(jìn)程優(yōu)先級相同時(shí)，轉(zhuǎn)入享受服務(wù)隊(duì)列；或當(dāng)享受服務(wù)隊(duì)列為空時(shí)，新創(chuàng)建進(jìn)程隊(duì)列的頭一個(gè)進(jìn)程可以轉(zhuǎn)入享受服務(wù)進(jìn)程隊(duì)列。,SRR算法基本思想：,某時(shí)刻t進(jìn)程的優(yōu)先級為：設(shè)時(shí)刻t1進(jìn)程被創(chuàng)建，t2時(shí)刻轉(zhuǎn)入享受服務(wù)隊(duì)列 p(t)=a*(t2-t1)+b*(t-t2) （ab0）,SRR算法的優(yōu)先級變化,SRR與FCFS和RR算法的關(guān)系,當(dāng)ba0時(shí)，享受服務(wù)隊(duì)列中永遠(yuǎn)只有一個(gè)進(jìn)程；SRR算法退化成FCFS算法； 當(dāng)ab=0時(shí)，SRR算法就是RR算法；,7. 多級反饋隊(duì)列算法(Round Robin with Multiple Feedback),多級反饋隊(duì)列算法是時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級算法的綜合和發(fā)展。,多級反饋隊(duì)列算法思想,設(shè)置多個(gè)就緒隊(duì)列，分別賦