第四章處理機調(diào)度

1、引言： 1、在早期的計算機系統(tǒng)中，對CPU的管理十分簡單，因那時CPU和其他資源一樣，為一個作業(yè)獨占，不存在處理機分配和調(diào)度問題。 2、隨著多道程序設(shè)計技術(shù)和各種不同類型的os的出現(xiàn)，各種不同的CPU管理方法得到啟用，不同的CPU管理方法為用戶提供不同性能的os。 A、在多道批處理系統(tǒng)中，為了提高處理機效 率和作業(yè)的吞吐量，當(dāng)調(diào)度一批作業(yè)組織多 道運行時，要盡可能使作業(yè)搭配合理； B、在分時系統(tǒng)中，由于用戶使用交互會話的工作方式， 系統(tǒng)必須要有較快地響應(yīng)時間，使每個用戶均感到如 同只有他一個人在使用計算機，因此系統(tǒng)在調(diào)度作業(yè) 時，要考慮每個用戶作業(yè)得到處理機的均等性。 3、衡量調(diào)度策略的指標(biāo)：

2、 （1）周轉(zhuǎn)時間：只講一個作業(yè)提交給計算機后到作業(yè)的 結(jié)果返回給用戶所需的時間； （2）吞吐量（率）：在給定時間內(nèi)，一個計算機系統(tǒng)所 完成的總工作量； （3）響應(yīng)時間：從用戶向計算機發(fā)出一條命令開始到計 算機把相應(yīng)結(jié)果返回給用戶所需的時間； （4）設(shè)備利用率：指I/O的使用情況。一、作業(yè)狀態(tài)及其轉(zhuǎn)換： 1、多級調(diào)度：一個作業(yè)從用戶提交開始到真正占有處理機而被執(zhí)行，則要有系統(tǒng)經(jīng)過多級調(diào)度才能實現(xiàn)。 2、作業(yè)狀態(tài)：一個作業(yè)從提交給計算機系統(tǒng)開始到返回執(zhí)行結(jié)果為止，一般要經(jīng)歷提交、收容、執(zhí)行、完成四個狀態(tài)。 （1）提交狀態(tài)：一個作業(yè)在其處于從輸入設(shè)備進入外部存儲設(shè)備的過程。 （2）收容狀態(tài)（后備狀態(tài)

3、）：作業(yè)內(nèi)容全部進入外存輸入井，但該作業(yè)還未被作業(yè)調(diào)度程序 選中時所處的狀態(tài)； （3）執(zhí)行狀態(tài)：作業(yè)調(diào)度程序從后背作業(yè)隊列中選擇若 干個作業(yè)投入運行，它為被選中作業(yè)建立進程并分配 必要資源，這些被選中的作業(yè)處于執(zhí)行態(tài)。 （4） 完成態(tài)：當(dāng)作業(yè)運行完畢，但它所占有的資源還 未全部釋放時所處的狀態(tài)。二、調(diào)度的層次：P82 1、作業(yè)調(diào)度：又稱宏觀調(diào)度（高級調(diào)度），其主要任務(wù) 是按一定的原則對外存輸入井中的大量后備作業(yè)進行 選擇，給選出的作業(yè)分配內(nèi)存、輸入輸出設(shè)備等資源， 并建立相應(yīng)進程，以使該作業(yè)的進程獲得競爭CPU的權(quán) 利，另外，當(dāng)作業(yè)執(zhí)行完畢，還負責(zé)回收系統(tǒng)資源。 2、交換調(diào)度：也叫中級調(diào)度，其

4、主要任務(wù)是按照給定的 原則和策略，將處于外存交換區(qū)中的就緒進程調(diào)入內(nèi)存， 或把處于內(nèi)存就緒狀態(tài)或內(nèi)存等待狀態(tài)的進程交換到外 村交換區(qū)。 3、進程調(diào)度：又叫微觀調(diào)度或低級調(diào)度。其主要任務(wù)是 按照某種策略和方法選取一個處于就緒狀態(tài)的進程占用 處理機。在確定了占用處理機的進程后，系統(tǒng)必須進行 進程上下文的切換以建立與占用處理機進程相應(yīng)的執(zhí)行 環(huán)境。 4、線程調(diào)度：其主要任務(wù)是選擇一個適當(dāng)?shù)木€程到處理 機上去執(zhí)行并進行描述標(biāo)的切換。 （1）線程的調(diào)度狀態(tài)：六個狀態(tài) a、就緒狀態(tài)：已具備執(zhí)行條件以等待CPU執(zhí)行，線 程調(diào)度程序只從線程就緒池中選擇線程進入備用狀 態(tài)。 b、備用狀態(tài)：系統(tǒng)中每個處理機只能有

5、一個線程處 于備用狀態(tài)，處于備用狀態(tài)的線程被選定為某一特 定處理機的下一個執(zhí)行對象。當(dāng)條件合適時，調(diào)度 程序為該線程進行描述表切換。 c、運行狀態(tài)：一旦調(diào)度程序?qū)€程執(zhí)行完描述表切 換，線程便進入運行狀態(tài)。 d、等待狀態(tài)：以下情況便可使線程進入等待狀態(tài)： 線程等待一對象，同步他的執(zhí)行；因等待I/O設(shè)備； 環(huán)境子系統(tǒng)導(dǎo)致線程自己掛起。當(dāng)線程等待結(jié)束， 就回到就緒狀態(tài)。 e、轉(zhuǎn)化狀態(tài)：如果線程已準(zhǔn)備好執(zhí)行，但由于資源 為不可用，從而成為轉(zhuǎn)化狀態(tài)。當(dāng)資源為可用時， 線程便由轉(zhuǎn)化狀態(tài)進入就緒狀態(tài)； f、終止?fàn)顟B(tài)：線程完成了他的執(zhí)行。 （2）引起線程調(diào)度的時機： a、當(dāng)線程進入就緒狀態(tài)時； b、當(dāng)線程的

6、時間片用完或線程終止時； c、當(dāng)調(diào)度程序或執(zhí)行體改變線程優(yōu)先級時； d 、當(dāng)執(zhí)行體或應(yīng)用程序改變正在運行的處理機族時。 （3）線程描述表：是用于描述現(xiàn)行線程的現(xiàn)場，包括： 程序計數(shù)器、處理機狀態(tài)寄存器、其他寄存器內(nèi)容、 用戶棧和核心棧指針、線程運行的地址空間的指針。三、作業(yè)與進程的關(guān)系（P83） 1、作業(yè)可被看作用戶向計算機提交任務(wù)的任務(wù)實體，而 進程則是計算機為了完成用戶任務(wù)實體而攝制的執(zhí)行實 體，是系統(tǒng)分配資源的基本單位。 2、一個作業(yè)由一個或多個進程組成： 第一步：系統(tǒng)為一個作業(yè)創(chuàng)建一個根進程； 第二步：在執(zhí)行作業(yè)控制語句時，根據(jù)任務(wù)要求，系統(tǒng) 或根進程為其建立相應(yīng)的子進程； 第三步：系

7、統(tǒng)為子進程分配資源和調(diào)度各子進程完成作 業(yè)要求的任務(wù)。一、作業(yè)調(diào)度的功能： 1、記錄系統(tǒng)中各作業(yè)的狀態(tài)。 系統(tǒng)為每個作業(yè)建立一個作業(yè)控制塊(JCB)來對作業(yè)進行控制管理并記錄作業(yè)在運行過程中的狀態(tài)。 （1）JCB的建立：作業(yè)進入后備狀態(tài)時為該作業(yè) 建立相應(yīng)的JCB，從而使該作業(yè)能被系統(tǒng)感 知； （2）JCB的撤銷：當(dāng)作業(yè)執(zhí)行完畢進入完成狀態(tài)后，系 統(tǒng)撤銷其JCB而釋放有關(guān)資源并撤銷該作業(yè)； （3）JCB內(nèi)容：作業(yè)名，作業(yè)類型，資源要求，資源使 用情況等 2、從后備作業(yè)隊列中選出一部分作業(yè)投入運行。 3、為被調(diào)度選中的作業(yè)做好執(zhí)行前的準(zhǔn)備工作。 4、在作業(yè)執(zhí)行結(jié)束時作善后處理工作。主要是輸出作業(yè)

8、 管理信息，例如執(zhí)行時間；回收該作業(yè)所占用的資源； 撤銷與該作業(yè)有關(guān)的進程和JCB。 P85圖4.3二、作業(yè)調(diào)度目標(biāo)與性能衡量： 1、調(diào)度目標(biāo) （1）對所有作業(yè)應(yīng)是公平的； （2）應(yīng)使設(shè)備有高的利用率； （3）每天執(zhí)行盡可能多的任務(wù)； （4）有快的相應(yīng)時間。 2、調(diào)度算法優(yōu)劣的衡量： 批處理系統(tǒng)-用作業(yè)的平均周轉(zhuǎn)時間或平均帶權(quán)周轉(zhuǎn) 時間衡量； 分時系統(tǒng)、實時系統(tǒng)-用作業(yè)周轉(zhuǎn)時間或平均帶權(quán)周 轉(zhuǎn)時間及平均相應(yīng)時間衡量。 （1）周轉(zhuǎn)時間：指作業(yè)從提交時刻開始到完成時刻為止 所經(jīng)歷時間。即：Ti=Tei-Tsi 平均周轉(zhuǎn)時間：T=(T1+Tn)/n （2）帶權(quán)周轉(zhuǎn)時間：指作業(yè)周轉(zhuǎn)時間和作業(yè)執(zhí)行時間的

9、 比值，即 Wi=Ti/Tri 平均帶權(quán)周轉(zhuǎn)時間： W=(W1+Wn)/n 在計算機系統(tǒng)運行過程中，進程數(shù)一般多于處理機樹目，從而導(dǎo)致進程對處理機的競爭，進程調(diào)度即按一定策略，動態(tài)地把處理機分配給處于就緒狀態(tài)的進程，使之能被執(zhí)行。一、進程調(diào)度的功能： 指操作系統(tǒng)中的進程調(diào)度程序按照某種調(diào) 度算法，從就緒進程隊列中選擇一個進程將他 移出就緒隊列并置為運行態(tài)， 同時啟動CPU立即執(zhí)行 該進程。具體描述為： （1）記錄系統(tǒng)中所有進程的執(zhí)行情況； a、進程管理模塊將系統(tǒng)中各進程狀態(tài)和狀態(tài)特征記 錄在PCB中； b、根據(jù)進程的狀態(tài)特征和資源需求，將系統(tǒng)中所 有進程PCB組織成多個隊列。 （2）選擇占有處

10、理機的進程； 根據(jù)不同的系統(tǒng)設(shè)計目標(biāo)，有各種各樣的選 擇策略，如：靜態(tài)優(yōu)先數(shù)調(diào)度法、輪轉(zhuǎn)法等。 （3）進行進程上下文切換： a、進程上下文：包括進程的狀態(tài)、有關(guān)變量、數(shù)據(jù) 結(jié)構(gòu)的值，硬件寄存器的值及PCB和有關(guān)程序； b、一個進程的執(zhí)行實質(zhì)上是在其上下文中執(zhí)行； c、當(dāng)出現(xiàn)進程調(diào)度時系統(tǒng)要做上下文的切換。二、進程調(diào)度的時機 1、引起進程調(diào)度的原因 a、正在執(zhí)行的進程執(zhí)行完畢； b、進行中的進程自己調(diào)用阻塞原語將自己阻塞起來， 進入睡眠等待狀態(tài)； c、執(zhí)行中進程調(diào)用了P原語操作，從而因資源不足而 被阻塞，或調(diào)用了V原語激活了等待資源的進程隊 列； d、執(zhí)行中進程提出了I/O請求后被阻塞； e、在

11、分時系統(tǒng)中時間片已經(jīng)用完； f、在執(zhí)行完系統(tǒng)調(diào)用后，在系統(tǒng)程序返回用戶程序時， 可認為系統(tǒng)進程執(zhí)行完畢，從而調(diào)度選擇一新的進 程執(zhí)行； g、就緒隊列中進程的優(yōu)先級變得高于當(dāng)前執(zhí)行進程的 優(yōu)先級，從而引起進程調(diào)度。 2、處理機調(diào)度的時機： 當(dāng)系統(tǒng)出現(xiàn)提上七種情況之一時，即發(fā)生處理機 調(diào)度。 3、處理機調(diào)度的方式： （1）可剝奪式：即就緒隊列中一旦有優(yōu)先級高于當(dāng)前進 程的優(yōu)先級時，便立即發(fā)生進程調(diào)度，轉(zhuǎn)讓處理機； （2）非剝奪方式：即使在就緒進程隊列存在優(yōu)先級高于 當(dāng)前當(dāng)前正在執(zhí)行的進程的優(yōu)先級時，當(dāng)前進程仍 將繼續(xù)占用處理機，直到該進程因自己調(diào)用某原語 或等待I/O而進入阻塞狀態(tài)、或時間片用完時

12、才發(fā) 生調(diào)度出讓處理機。三、進程上下文切換（P88） 1、進程上下文的內(nèi)容： 2、進程上下文切換的步驟： （1）決定是否做上下文切換及其是否允許做上下文切換； （2）保存當(dāng)前執(zhí)行進程的上下文； （3）選擇一個就緒狀態(tài)進程； （4）恢復(fù)或裝配所選進程上下文，將CPU控制權(quán)交給所 選進程。四、進程調(diào)度性能評價： 1、定性評價：進程調(diào)度性能的衡量可分為定性和定量兩 種。在定性衡量方面，首先考慮調(diào)度的可能性包括一 次進程調(diào)度是否引起數(shù)據(jù)結(jié)構(gòu)的破壞，這要求對調(diào)度 時機的選擇和保存CPU現(xiàn)場十分謹慎；其次，簡潔性 也是衡量進程調(diào)度的一個重要指標(biāo)，由于調(diào)度程序的 執(zhí)行涉及到多個進程和必須進行上下文的切換，

13、如 果調(diào)度過于頻繁，將會耗去較大的系統(tǒng)開銷。 2、定量評價：包括CPU利用率，進城在就緒隊列中的等 待時間與執(zhí)行時間之比。1、先來先服務(wù)調(diào)度算法(FCFS) （1）方法思想：按照進程進入就緒隊列的先后次序選擇 進程投入 運行。該法也可以用于作業(yè)調(diào)度。 （2）特點： 優(yōu)點：實現(xiàn)簡單、公平。 缺點： a、計算機效率可能不高，如系統(tǒng)中的進程偏向于需求某 一類資源，導(dǎo)致有的資源高度繁忙，有的資源可能長 期不用； b、對短進程可能不利，不能很好地滿足用戶的需求。 （3）例：設(shè)P1,P2,P3為三個進程，他們的本次CPU周期 時值分別是21ms,6ms,3ms，且以P1,P2,P3的次序 進入就緒隊列中，

14、則在（1）不剝奪方式下執(zhí)行 序列為：P1P2P3,且 平均周轉(zhuǎn)時間T=(21+27+30)/3=26ms 平均等待時間W=(0+21+27)/3=16ms 平均帶權(quán)周轉(zhuǎn)時間T1=(21/21+27/6+30/3) （2）在分時系統(tǒng)中，若時間片為6ms，分析 這三個進程的執(zhí)行情況。 2、最短者優(yōu)先(SJF,SPF) （1）思想：以進程的本次CPU時間長短作為調(diào)度的依據(jù) 來選擇進程投入運行。 （2）例：設(shè)P1,P2,P3為三個進程，他們的本次CPU周期 時值分別是21ms,6ms,3ms，分析他們的執(zhí)行情 況及有關(guān)指標(biāo)的計算。 （3）性能分析： a、采用最短進程優(yōu)先調(diào)度算法，可以降低平均周轉(zhuǎn) 時間

15、，平均帶權(quán)周轉(zhuǎn)時間、平均等待時間。 b 、該算法實現(xiàn)簡單。 缺點：一般情況具有公平性，但是當(dāng)系統(tǒng)中長進程 較少而短進程較多時，對長進程失去公平性。 3、最高相應(yīng)比者優(yōu)先(HRN=highest reponse ration next） （1）當(dāng)需要從就緒隊列中選擇進程投入運行時，先計算 個進程的相應(yīng)比，選擇相應(yīng)比最高的進程運行。（2）例：設(shè)有四個作業(yè)：J1,J2,J3,J4，他們的進入時間 分別為8:00,8:50,9:00,9:50，運行時間分別為 2:00,0.50,0.10,0.20，分析執(zhí)行情況。 (略) （3）性能： a、該算法較復(fù)雜，系統(tǒng)開銷大； b、性能評價參數(shù)有升高趨勢； c、

16、克服了FCFS、 SPF各自的缺點。4、輪轉(zhuǎn)法（RR=round robin） （1）思想：系統(tǒng)將所有就緒進程按先進先出原則組織成 隊列，調(diào)度程序每次選擇隊首進程投入運行，并 按規(guī)定的時間片S值設(shè)置時鐘，以便S到限時產(chǎn)生 中斷。若現(xiàn)行進程的CPU周期時值小于S值，則當(dāng) 該進程完成時就進入重新調(diào)度，S的剩余量交還給 系統(tǒng)；如果當(dāng)前CPU周期時值大于或等于S值，則 當(dāng)時間片中斷發(fā)生時便進入剝奪態(tài)，將現(xiàn)行進程 送至就緒隊列尾部，而當(dāng)前CPU周期剩余量放到下 一輪再執(zhí)行，同時選擇隊首進程投入運行。 2）例：針對前面提到的P1,P2,P3三個進程，利用輪轉(zhuǎn)法， 分析他們的執(zhí)行情況。 （略） （3）關(guān)于時

17、間片： a、長短適中，如太長，則使每一個進程均能在一個 時間片內(nèi)完成，RR算法褪化成了FCFS；若太短， 導(dǎo)致頻繁的時間片中斷和調(diào)度，CPU額外開銷大。 b、時間片S可以采用基本時間片法和變長時間片法。 c、S的選取公式： S=RT/N 其中RT為系統(tǒng)響應(yīng)時間上限，N為系統(tǒng)中進程 數(shù)目上限。 （4）性能： a、具有公平性； b、易于實現(xiàn)，算法簡單； c、CPU存在較大的額外開銷，用于進程切換和 調(diào)度。 5、最高優(yōu)先級法： （HPF=highest priority first） （1）思想：在進行進程調(diào)度時，選擇優(yōu)先級最高者頭投 入運行，而忽略等待時間、運行時間等因素。 a、優(yōu)先級的表示方法：

18、用一個整數(shù)表示，該數(shù)稱為 優(yōu)先數(shù)，有的系統(tǒng)規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越高。 b、優(yōu)先級的設(shè)置方法： 靜態(tài)優(yōu)先級法：由系統(tǒng)在建立進程時確定一個優(yōu)先 數(shù)，它在整個生命期內(nèi)保持不變：進程的優(yōu)先 數(shù)可以根據(jù)其類型、功能、資源需求等確定； 動態(tài)優(yōu)先數(shù)：在創(chuàng)建一個進程時，根據(jù)該進程的基 本特性設(shè)置一個初始優(yōu)先數(shù)，而后在進程運行 過程中，隨著時間推移和運行環(huán)境的變化而動 態(tài)地改變優(yōu)先級， P=Po-at。 （2）例：設(shè)有5個進程P1,P2,P3,P4,P5它們各自的本次 CPU時值、初始化優(yōu)先級及進入就緒隊列相對時 刻如下： 進程 CPU時值 優(yōu)先數(shù) 進入時刻 P1 32 5 0 P2 4 3 0 P3 8 5

19、 0 P4 2 6 0 P5 16 4 16 （1）分析在靜態(tài)優(yōu)先級調(diào)度算法下的有關(guān)指標(biāo)：平 均等待時間、平均周轉(zhuǎn)時間、平均帶權(quán)周轉(zhuǎn)時間。 （2）在剝奪式的動態(tài)優(yōu)先級方法中，設(shè)現(xiàn)行進程每 連續(xù)運行10毫秒以上后，優(yōu)先數(shù)加1，而就緒進程每 40毫秒后進程優(yōu)先數(shù)減1，分析執(zhí)行情況。（3）性能： a、靜態(tài)優(yōu)先級法簡單，但缺點是公平性差，可能會 造成優(yōu)先級低的長期等待； b、動態(tài)優(yōu)先級法資源利用率高，公平性好，缺點是 系統(tǒng)開銷較大，實現(xiàn)復(fù)雜。 6、多級反饋隊列： （1）思想： a、系統(tǒng)按優(yōu)先級別設(shè)置若干n個就緒進程隊 列，第一 級隊列的優(yōu)先級最高，以下逐級降低，第n級隊列的 優(yōu)先級最低； b、每個就緒

20、隊列對應(yīng)一個時間片Si(i=1,2,n)，且 有S1S2Sn，一般有Si+1=2Si c、除對第n級隊列按RR調(diào)度外，對其余各級均按 FCFS調(diào)度； d、當(dāng)現(xiàn)行進程正在運行它的CPU周期時，如果有時 間片中斷或有進程進入更高級的就緒隊列時將引起 剝奪，對前一種情況，先行進程將進入下一級隊列， 對后一種情況，先行進程進入本級隊列尾部，當(dāng)一 進程被喚醒時，它進入原來離開時的隊列。 （2）特點： a、復(fù)雜，實現(xiàn)困難； b 、是FCFS，RR，HPF的綜合應(yīng)用。 進程調(diào)度室內(nèi)核原語，當(dāng)發(fā)生了引起調(diào)度的某種事件時，由有關(guān)的內(nèi)核程序轉(zhuǎn)入。 采用HPF算法的進程調(diào)度程序大致描述如下： procedure s

21、cheduler; begin if RQ=nil then start(idler); outqueue(RQ,I,HPF); if EXENIL then begin if I.priorityEXE.priority then begin save(EXE); EXE.start:=ready; EXE.queue:=RQ; insert(RQ.EXE); end; else begin insert(RQ,i); return end; end; start(i); end;一、實時系統(tǒng)的特點及功能 （一）特點 1、有限等待時間（確定性）：與分時系統(tǒng) 的多個進程的并發(fā)執(zhí)行特性相比，分時

22、系 統(tǒng)中并發(fā)執(zhí)行的進程具有不確定性，其執(zhí) 行順序與執(zhí)行環(huán)境有關(guān)。而實時系統(tǒng)則不 然，他要求所有進程在處理事件時，都必 須在有限時間內(nèi)開始處理。 2、有限響應(yīng)時間： 指從系統(tǒng)響應(yīng)外部事件 開始，必須在有限時間內(nèi)處理完畢。 3、用戶控制：指用戶可以控制進程的優(yōu)先級并選擇 相應(yīng)的調(diào)度算法，從而達到對進程執(zhí)行先后順序 的控制。 4、可靠性：要求很高 5、系統(tǒng)出錯處理能力： 要求系統(tǒng)在出錯時，既能處理發(fā)生的錯誤， 又不影響當(dāng)前正在執(zhí)行的用戶進程。 （二）實時系統(tǒng)的功能： 1、很快的進程或線程切換速度 與分時系統(tǒng)不同，公平性和最小平均響應(yīng)時 間指標(biāo)在實時系統(tǒng)中并不重要，實時系統(tǒng)中調(diào)度 算法的設(shè)計原則是滿足所有硬實施任務(wù)的處理時 限和盡可能多地滿足軟實時任 務(wù)的處理時限。 2、快速的外部中斷響應(yīng)能力 3、基于優(yōu)先級的隨機搶先式調(diào)度策略，有四種： （1）優(yōu)先級+時間片輪轉(zhuǎn)調(diào)度策略 （2）基于優(yōu)先級的非搶占式調(diào)度策略 （3）基于優(yōu)先級的固定點搶先式調(diào)度策略 （4）基于優(yōu)先級的隨時搶先式調(diào)度策略二、實時調(diào)度算法的分類： （1）靜態(tài)表格驅(qū)動類 （2）靜態(tài)優(yōu)先級驅(qū)動搶先式調(diào)度算法類 （3）動態(tài)計劃調(diào)度算法類