昆明理工大學(xué) 付湘瓊操作系統(tǒng)第三章處理機(jī)調(diào)度

1、 福州大學(xué)數(shù)計(jì)學(xué)院主講教師主講教師: : 單單 紅紅計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng)計(jì)算機(jī)操作系統(tǒng) 第三章處理機(jī)調(diào)度第三章處理機(jī)調(diào)度 處理機(jī)處理機(jī)調(diào)用調(diào)用調(diào)度策略考慮：周轉(zhuǎn)時(shí)間 吞吐率相應(yīng)時(shí)間 設(shè)備利用率研究的內(nèi)容有：作業(yè)與進(jìn)程的關(guān)系 作業(yè)調(diào)度策略與算法進(jìn)程調(diào)度策略與算法 幾種調(diào)度策略的評(píng)價(jià) 本章主要討論處理機(jī)分配問題 處理機(jī)處理機(jī)調(diào)用調(diào)用1.作業(yè)的狀態(tài)及其轉(zhuǎn)換提交狀態(tài)：一個(gè)作業(yè)北提交給機(jī)房后或用戶通過終端鍵盤想計(jì)算機(jī)鍵入其作業(yè)時(shí)所處的狀態(tài)后備狀態(tài)：作業(yè)的全部信息都已通過輸入機(jī)輸入，并由操作系統(tǒng)將其存在磁盤的某些分區(qū)（存放作業(yè)的輸入井）中等待運(yùn)行。運(yùn)行狀態(tài)

2、：作業(yè)一旦被作用調(diào)度程序選中而被送入主存中投入運(yùn)行。完成狀態(tài)：作業(yè)完成其全部運(yùn)行，釋放出其所占用的全部資源。準(zhǔn)備退出系統(tǒng)時(shí)的作業(yè)。 3.1 分級(jí)調(diào)度 處理機(jī)處理機(jī)調(diào)用調(diào)用 作業(yè)狀態(tài)及其轉(zhuǎn)換圖 spoolingspooling系統(tǒng)系統(tǒng)提交提交收容收容外存外存就緒就緒等待等待運(yùn)行運(yùn)行就緒就緒等待等待交換調(diào)度交換調(diào)度完完成成作業(yè)調(diào)度作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度 處理機(jī)處理機(jī)調(diào)用調(diào)用高級(jí)調(diào)度（作業(yè)調(diào)度、宏觀調(diào)度）按一定原則對(duì)外存輸入井上的作業(yè)進(jìn)行調(diào)度，并建立進(jìn)程pcb。它決定允許哪些作業(yè)競(jìng)爭(zhēng)系統(tǒng)資源。由于這種調(diào)度決定哪些作業(yè)可以進(jìn)入系統(tǒng)，所以也稱收容調(diào)度。作業(yè)一旦被系統(tǒng)收容，就便成進(jìn)程或進(jìn)程組。 中級(jí)調(diào)度

3、（交換調(diào)度）它決定允許哪些進(jìn)程競(jìng)爭(zhēng)處理機(jī)。中級(jí)調(diào)度通過使進(jìn)程臨時(shí)掛起和激活的方法對(duì)系統(tǒng)負(fù)載波動(dòng)作出反映，以便獲得平穩(wěn)的系統(tǒng)操作和實(shí)現(xiàn)較好的系統(tǒng)綜合性能目標(biāo)，中級(jí)調(diào)度的作用使作為作業(yè)進(jìn)入系統(tǒng)和將中央處理機(jī)分配給這些作業(yè)二者之間的一個(gè)緩沖。2 調(diào)度的層次 處理機(jī)處理機(jī)調(diào)用調(diào)用低級(jí)調(diào)度（進(jìn)程調(diào)度）它決定了存在就緒進(jìn)程時(shí)，哪一個(gè)就緒進(jìn)程將分配到中央處理機(jī)，并且把中央處理機(jī)實(shí)際分配給這個(gè)進(jìn)程（即低級(jí)調(diào)度是將處理機(jī)分配給進(jìn)程）。低級(jí)調(diào)度是由每秒可操作許多次的處理機(jī)調(diào)度程序執(zhí)行，處理機(jī)調(diào)度程序應(yīng)常駐內(nèi)存。 2 調(diào)度的層次 處理機(jī)處理機(jī)調(diào)用調(diào)用 作業(yè)是用戶向計(jì)算機(jī)提交任務(wù)的任務(wù)實(shí)體。 進(jìn)程是計(jì)算機(jī)為了完成用戶

4、任務(wù)實(shí)體而設(shè)置的執(zhí)行實(shí)體。 顯然，計(jì)算機(jī)要完成一個(gè)任務(wù)實(shí)體，必須要有一個(gè)以上的執(zhí)行實(shí)體，一個(gè)作業(yè)總是由一個(gè)以上的多個(gè)進(jìn)程組成。 3作業(yè)與進(jìn)程的關(guān)系 處理機(jī)處理機(jī)調(diào)用調(diào)用作業(yè)調(diào)度的功能：按某種算法從后備隊(duì)列中挑選一個(gè)或一批作業(yè)調(diào)入內(nèi)存，并創(chuàng)建pcb.1后備作業(yè)隊(duì)列與作業(yè)控制塊 系統(tǒng)中有若干作業(yè)在輸入井中，為了管理和調(diào)度作業(yè)，就必須記錄已進(jìn)入系統(tǒng)的各作業(yè)的情況，系統(tǒng)為每個(gè)作業(yè)設(shè)置了一個(gè)作業(yè)控制塊（jcb）。內(nèi)容：作業(yè)名、作業(yè)狀態(tài)、作業(yè)調(diào)度，以及資源申請(qǐng)和一些控制信息。3.2 作業(yè)的調(diào)度 處理機(jī)處理機(jī)調(diào)用調(diào)用 作業(yè)控制塊jcb 作業(yè)名作業(yè)名 作業(yè)類型作業(yè)類型 資源要求資源要求 資源使用情況資源使用情

5、況 優(yōu)先級(jí)優(yōu)先級(jí) 當(dāng)前狀態(tài)當(dāng)前狀態(tài) 其它其它 處理機(jī)處理機(jī)調(diào)用調(diào)用作業(yè)調(diào)度按照某種調(diào)度算法從后備作業(yè)隊(duì)列中選取作業(yè)，使其進(jìn)入內(nèi)存運(yùn)行。 作業(yè)調(diào)度程序的主要功能是審查系統(tǒng)是否能滿足用戶作業(yè)的資源要求以及按照一定的算法選取作業(yè)。1作業(yè)調(diào)度及其功能 處理機(jī)處理機(jī)調(diào)用調(diào)用按照某種調(diào)度算法從后備作業(yè)隊(duì)列中選取作業(yè)。為被選取的作業(yè)分配內(nèi)存和外設(shè)資源（當(dāng)系統(tǒng)為動(dòng)態(tài)分配外設(shè)時(shí)，作業(yè)所申請(qǐng)的外設(shè)只作為調(diào)度的參考因素）。因此要用到內(nèi)存分配程序和外設(shè)分配程序。為選中的作業(yè)建立相應(yīng)的進(jìn)程。為作業(yè)開始運(yùn)行做好一切準(zhǔn)備工作。如構(gòu)造和讀寫作業(yè)運(yùn)行時(shí)所需要的有關(guān)表格及建立負(fù)責(zé)其運(yùn)行控制的作業(yè)運(yùn)行控制程序。在作用運(yùn)行完畢或運(yùn)行

6、過程中因某種原因需要撤離時(shí)，作業(yè)調(diào)度程序還有完成作業(yè)的善后處理工作，如收回分配給他的全部資源，它們將從系統(tǒng)中抹去2.作業(yè)調(diào)度應(yīng)完成如下幾方面的工作 處理機(jī)處理機(jī)調(diào)用調(diào)用1)調(diào)度目標(biāo) 對(duì)所有作業(yè)應(yīng)該是公平合理 應(yīng)使設(shè)備有高的利用率 每天執(zhí)行盡可能多的作業(yè) 有快的響應(yīng)時(shí)間3.作業(yè)調(diào)度目標(biāo)與性能衡量 處理機(jī)處理機(jī)調(diào)用調(diào)用2）作業(yè)調(diào)度的轉(zhuǎn)換過程 （1）作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài) p85(a)框圖 （2）作業(yè)從執(zhí)行狀態(tài)到完成狀態(tài) p85(b)框圖3.作業(yè)調(diào)度目標(biāo)與性能衡量 處理機(jī)處理機(jī)調(diào)用調(diào)用后備作業(yè)隊(duì)列空按調(diào)度算法從作業(yè)中選出一作業(yè)調(diào)用存儲(chǔ)、設(shè)備管理程序，審核資源要求資源要求能滿足？放棄該作業(yè)否分配資源

7、調(diào)用進(jìn)程管理程序建立進(jìn)程進(jìn)程調(diào)度否是出口作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài) 處理機(jī)處理機(jī)調(diào)用調(diào)用撤銷該作業(yè)的所有進(jìn)程及作業(yè)的jcb調(diào)用存儲(chǔ)管理，設(shè)備管理回收分配給該作業(yè)的全部資源調(diào)用會(huì)計(jì)程序，計(jì)算該作業(yè)的執(zhí)行費(fèi)用調(diào)度下一個(gè)作業(yè)作業(yè)從執(zhí)行狀態(tài)到完成狀態(tài) 處理機(jī)處理機(jī)調(diào)用調(diào)用3）.衡量一個(gè)作業(yè)調(diào)度算法是否滿足系統(tǒng)設(shè)計(jì)的要 求 給出兩個(gè)常用的評(píng)價(jià)在批處理系統(tǒng)中對(duì)作業(yè)調(diào)度算法優(yōu)劣的性能量度1周轉(zhuǎn)時(shí)間：作業(yè)i從提交時(shí)刻tsi到完成時(shí)刻tei稱為作業(yè)的周轉(zhuǎn)時(shí)間。ti=tei-tsi 完成 提交3.作業(yè)調(diào)度目標(biāo)與性能衡量 處理機(jī)處理機(jī)調(diào)用調(diào)用作業(yè)平均周轉(zhuǎn)時(shí)間為（有n個(gè)作業(yè)，n=1) nt=1/n ti i=1一個(gè)作業(yè)

8、的周轉(zhuǎn)時(shí)間說明了該作業(yè)在系統(tǒng)內(nèi)停留的時(shí)間包含兩部分：一是等待時(shí)間；二為執(zhí)行時(shí)間ti = twi - tri(停留時(shí)間)3.作業(yè)調(diào)度目標(biāo)與性能衡量 處理機(jī)處理機(jī)調(diào)用調(diào)用2帶權(quán)周轉(zhuǎn)時(shí)間wi：wi=ti/tri 平均帶權(quán)周轉(zhuǎn)時(shí)間為： nw=1/n wi i=1 3.作業(yè)調(diào)度目標(biāo)與性能衡量 處理機(jī)處理機(jī)調(diào)用調(diào)用（1） 先來先服務(wù)（fcfs）調(diào)度算法 將用戶作業(yè)和就緒進(jìn)程按提交順序或變?yōu)榫途w狀態(tài)的先后排成隊(duì)列，并按照先來先服務(wù)的方式進(jìn)行調(diào)度處理，是一種最普遍和最簡(jiǎn)單的方法。它優(yōu)先考慮在系統(tǒng)中等待時(shí)間最長(zhǎng)的作業(yè)，而不管要求運(yùn)行時(shí)間的長(zhǎng)短。進(jìn)程調(diào)度算法和作業(yè)調(diào)度算法。 處理機(jī)處理機(jī)調(diào)用調(diào)用作業(yè) 進(jìn)入時(shí)刻 開

9、始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間1 8：00 8：00 10：00 2.00 1.002 8：50 10：00 10：50 2.00 4.003 9：00 10：50 11：00 2.00 20.004 9：50 11：00 11：20 1.30 6.50 周轉(zhuǎn)時(shí)間t110.008.002.00 帶權(quán)周轉(zhuǎn)時(shí)間w12/21 周轉(zhuǎn)時(shí)間t210.508.502.00 帶權(quán)周轉(zhuǎn)時(shí)間w22.00/0.504.00先來先服務(wù)算法分析結(jié)果 處理機(jī)處理機(jī)調(diào)用調(diào)用 周轉(zhuǎn)時(shí)間t311.009.002.00 帶權(quán)周轉(zhuǎn)時(shí)間w32.00/0.120.00 周轉(zhuǎn)時(shí)間t411.209.501.30 帶權(quán)周轉(zhuǎn)時(shí)間w4

10、1.30/0.206.50 周轉(zhuǎn)時(shí)間titeitsi 帶權(quán)周轉(zhuǎn)時(shí)間witi/tri 平均周轉(zhuǎn)時(shí)間t1/ntii=1n 處理機(jī)處理機(jī)調(diào)用調(diào)用 該算法總是優(yōu)先調(diào)度要求運(yùn)行時(shí)間最短的作業(yè)。作業(yè) 進(jìn)入時(shí)刻 開始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 帶權(quán)周轉(zhuǎn)時(shí)間 1 8：00 8：00 10：00 2.00 1.00 2 8：50 10：30 11：20 2.30 4.60 3 9：00 10：00 10：10 1.10 11.00 4 9：50 10：10 10：30 0.40 2.00（2）.最短作業(yè)優(yōu)先法（sjf） 處理機(jī)處理機(jī)調(diào)用調(diào)用平均周轉(zhuǎn)時(shí)間t1.55 (t=2.00+2.30+1.10+0.40)/4

11、=1.55平均帶權(quán)周轉(zhuǎn)時(shí)間t=4.65 (t=1.00+4.60+11.00+2.00)/4=4.65 處理機(jī)處理機(jī)調(diào)用調(diào)用最高響應(yīng)比作業(yè)優(yōu)先算法是對(duì)fcfs方式和sjf方式的一種綜合平衡相應(yīng)比r定義為系統(tǒng)對(duì)作業(yè)的響應(yīng)時(shí)間與作業(yè)要求運(yùn)行時(shí)間的比值r響應(yīng)時(shí)間 / 要求運(yùn)行時(shí)間(作業(yè)等待時(shí)間需運(yùn)行時(shí)間)/ 需運(yùn)行時(shí)間1已等待時(shí)間 / 需運(yùn)行時(shí)間1w/t(3)最高相應(yīng)比作業(yè)優(yōu)先算法（hrn） 處理機(jī)處理機(jī)調(diào)用調(diào)用 響應(yīng)比r不僅是要求運(yùn)行時(shí)間的函數(shù)，而且還是等待時(shí)間的函數(shù)。由于r與要求運(yùn)行時(shí)間成反比，故對(duì)短作業(yè)是有利的，另一方面，因r與等待時(shí)間成正比，故長(zhǎng)作業(yè)隨著其等待時(shí)間的增長(zhǎng)，也可獲的較高的相應(yīng)比

12、。這就克服了短作業(yè)優(yōu)先數(shù)法的缺點(diǎn)，既照顧了先來者，又優(yōu)待了短作業(yè)，是上述兩種算法的一種較好的折中。 處理機(jī)處理機(jī)調(diào)用調(diào)用 作業(yè) 進(jìn)入時(shí)刻 開始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)刻 帶權(quán)周轉(zhuǎn)時(shí)刻 1 8：00 8：00 10：00 2.00 1.00 2 8：50 10：50 11：00 2.10 3.40 3 9：00 10：00 10：10 1.10 11.00 4 9：50 11：00 11：20 1.30 6.50 平均周轉(zhuǎn)時(shí)間t1.625平均帶權(quán)周轉(zhuǎn)時(shí)間w5.575 處理機(jī)處理機(jī)調(diào)用調(diào)用r1（等待時(shí)間執(zhí)行時(shí)間）/ 執(zhí)行時(shí)間2 / 21r2(10.108.50）（11.0010.10) /0.5 （

13、1.200.5）/ 0.50 2.4013.40r3(10.009.00）（10.1010.00) / 0.10 （10.10）/ 0.10 11.00r4(11.009.50）+（11.2011.00)/(11.2011.00) （1.100.20）/ 0.20 1.10/0.201 6.5 處理機(jī)處理機(jī)調(diào)用調(diào)用 時(shí)間片輪轉(zhuǎn)法主要用于進(jìn)程調(diào)度。采用此算法的系統(tǒng)，其程序就緒隊(duì)列往往按進(jìn)程到達(dá)的時(shí)間來排序。進(jìn)程調(diào)度程序總是選擇就緒隊(duì)列中的第一個(gè)進(jìn)程，也就是說按照先來先服務(wù)原則調(diào)度，但一旦進(jìn)程占又處理機(jī)僅使用一個(gè)時(shí)間片。在使用先一個(gè)時(shí)間片后，進(jìn)程還沒又完成其運(yùn)行，它必須釋放出處理機(jī)給下一個(gè)就緒的進(jìn)

14、程，而被搶占的進(jìn)程返回到就緒隊(duì)列的末尾重新排隊(duì)等待在次運(yùn)行。 (4) 輪轉(zhuǎn)法（rr） 處理機(jī)處理機(jī)調(diào)用調(diào)用 時(shí)間片輪轉(zhuǎn)策略特別適合于分時(shí)系統(tǒng)中使用，當(dāng)多個(gè)進(jìn)程駐留在主存中時(shí)，在進(jìn)程間轉(zhuǎn)接處理機(jī)的開銷一般是不大的。 在輪轉(zhuǎn)法中，時(shí)間片長(zhǎng)度的選取非常重要，時(shí)間片長(zhǎng)度的選擇會(huì)直接影響系統(tǒng)開銷和響應(yīng)時(shí)間，如果時(shí)間片長(zhǎng)度過短，則調(diào)度程序剝奪處理機(jī)的次數(shù)增多，這將使進(jìn)程上下文交換次數(shù)也大大增加，加重了系統(tǒng)開銷。如果時(shí)間片長(zhǎng)度選擇過長(zhǎng)（大）。大到一個(gè)進(jìn)程足以完成其全部運(yùn)行工作所需的時(shí)間，那么時(shí)間片輪轉(zhuǎn)法就退化為先來先服務(wù)策略了。最佳的時(shí)間片量值應(yīng)能使分時(shí)用戶得到好的響應(yīng)時(shí)間 處理機(jī)處理機(jī)調(diào)用調(diào)用 響應(yīng)時(shí)間

15、srt/nmax r響應(yīng)時(shí)間 nmax最大進(jìn)程數(shù) 每當(dāng)一輪調(diào)度開始時(shí)，系統(tǒng)便根據(jù)就緒隊(duì)列中已有進(jìn)程數(shù)目計(jì)算一次值。作為新一輪調(diào)度的時(shí)間片。這種方法得到的時(shí)間片是隨就緒隊(duì)列中的進(jìn)程數(shù)變化的。 處理機(jī)處理機(jī)調(diào)用調(diào)用 進(jìn)程調(diào)度的功能：從就緒隊(duì)列中挑選一個(gè)進(jìn)程到處理機(jī)上運(yùn)行。 作業(yè)調(diào)度程序在挑選作業(yè)進(jìn)入主存運(yùn)行時(shí)，要為該作業(yè)建立相應(yīng)的進(jìn)程。在作業(yè)完成后要撤銷該作業(yè)的全部進(jìn)程。 一個(gè)進(jìn)程被建立后，系統(tǒng)為了便于對(duì)進(jìn)程的管理，將系統(tǒng)中的所有進(jìn)程按其狀態(tài)將其組織成不同的進(jìn)程隊(duì)列。3.3 進(jìn)程調(diào)度 處理機(jī)處理機(jī)調(diào)用調(diào)用進(jìn)程調(diào)度程序：負(fù)責(zé)進(jìn)程調(diào)度功能的內(nèi)核程序。作業(yè)調(diào)度與進(jìn)程調(diào)度程序的區(qū)別：前者是挑選作業(yè)進(jìn)主存運(yùn)

16、行、后者是挑選就緒進(jìn)程到處理機(jī)上運(yùn)行。進(jìn)程調(diào)度的核心問題就是，采用什么算法把處理機(jī)分配給進(jìn)程。 處理機(jī)處理機(jī)調(diào)用調(diào)用 進(jìn)程調(diào)度的算法較多，在設(shè)計(jì)進(jìn)程調(diào)度算法時(shí)應(yīng)考慮的因素多，比如：盡量提高資源利用率，減少處理機(jī)的空閑時(shí)間，對(duì)于用戶作業(yè)要較合理的平均響應(yīng)時(shí)間，以及盡可能地增強(qiáng)cpu的處理能力。3. .4 選擇調(diào)度算法時(shí)應(yīng)考慮的問題 處理機(jī)處理機(jī)調(diào)用調(diào)用1. fifo(先來先服務(wù)調(diào)度算法) 最簡(jiǎn)單的調(diào)度原則是先進(jìn)先出(fifo)就緒隊(duì)列abcdcpu完成3.5 調(diào)度算法 處理機(jī)處理機(jī)調(diào)用調(diào)用 根據(jù)進(jìn)程到達(dá)就緒隊(duì)列的時(shí)間來分配中央處理機(jī)，一旦一個(gè)進(jìn)程獲得了中央處理機(jī)，就一直運(yùn)行到結(jié)束，先來先服務(wù)是非

17、剝奪調(diào)度。 這種調(diào)度從形式上講是公平的，但它使短作業(yè)要等待長(zhǎng)作業(yè)的完成，重要的作業(yè)要等待不重要作業(yè)的完成。從這個(gè)意義上講又是不公平的。 先進(jìn)先出調(diào)度使響應(yīng)時(shí)間的變化較小，因此它比其它大多數(shù)調(diào)度都可預(yù)測(cè)。由于這種調(diào)度方法不能保證良好的響應(yīng)時(shí)間，在處理交互式用戶時(shí)很少用這種方法。 處理機(jī)處理機(jī)調(diào)用調(diào)用 在當(dāng)今系統(tǒng)中，先進(jìn)現(xiàn)出很少作為調(diào)度模式，而是常常嵌套在其它的調(diào)度模式中。例如，許多調(diào)度模式根據(jù)優(yōu)先級(jí)將處理機(jī)分配給進(jìn)程，但具有相同優(yōu)先級(jí)的進(jìn)程卻按先進(jìn)先出進(jìn)行分配。 處理機(jī)處理機(jī)調(diào)用調(diào)用根據(jù)作業(yè)要求系統(tǒng)提供的處理機(jī)時(shí)間，內(nèi)存的大小和i/o設(shè)備的數(shù)量，來確定作業(yè)的優(yōu)先數(shù)，如果系統(tǒng)賦予作業(yè)的反比于系統(tǒng)的

18、估計(jì)執(zhí)行時(shí)間，就形成短作業(yè)優(yōu)先的算法。由于作業(yè)需要的執(zhí)行時(shí)間事先難于確定，只是把用戶自保的估計(jì)時(shí)間作為依據(jù)，為防止用戶少報(bào)自己的作業(yè)時(shí)間以獲得優(yōu)先服務(wù)，在采用短作業(yè)優(yōu)先算法時(shí)，應(yīng)采取適當(dāng)?shù)姆纻浯胧?2. 作業(yè)要求的資源 處理機(jī)處理機(jī)調(diào)用調(diào)用 在有的系統(tǒng)中，分配給作業(yè)的優(yōu)先數(shù)還取決于它所占用的內(nèi)存的多少，作業(yè)越大，占用內(nèi)存越多，分配給它的優(yōu)先數(shù)越低。顯然，不論是根據(jù)作業(yè)的執(zhí)行時(shí)間，還是根據(jù)作業(yè)的大小所確定的優(yōu)先數(shù)，都有利于短作業(yè)。 3.動(dòng)態(tài)優(yōu)先數(shù) 雖然基于靜態(tài)優(yōu)先數(shù)的調(diào)度算法比較簡(jiǎn)單，也頗為流利，但畢竟不夠精確。因?yàn)檫M(jìn)程的優(yōu)先數(shù)在它執(zhí)行前就已算好，且在整個(gè)執(zhí)行期間都保持不變，但隨著進(jìn)程的推進(jìn)，

19、計(jì)算優(yōu)先數(shù)所依賴的特征很多都將隨之改變，因此靜態(tài)優(yōu)先數(shù)并非自始至終都能準(zhǔn)確地反映出這些特性，如果能在進(jìn)程運(yùn)行中，不斷的隨著特性的改變而修改其優(yōu)先數(shù)，顯然可以實(shí)現(xiàn)更多精確的調(diào)度，從而獲得更好的調(diào)度性能，這對(duì)分時(shí)系統(tǒng)顯得格外重要. 處理機(jī)處理機(jī)調(diào)用調(diào)用4.時(shí)間片輪轉(zhuǎn)算法 fcb a .cpu完成 a b c當(dāng)時(shí)間片很大時(shí)，每個(gè)進(jìn)程得到比完成該進(jìn)程多的處理機(jī)時(shí)間，此時(shí)輪轉(zhuǎn)調(diào)度模式退化為先進(jìn)先出模式。當(dāng)時(shí)間片非常小時(shí)，上下文轉(zhuǎn)換開銷就成了決定因素，系統(tǒng)性能降低，大多數(shù)時(shí)間都消耗在處理機(jī)的轉(zhuǎn)換上，只有少許用在用戶的計(jì)算上。 處理機(jī)處理機(jī)調(diào)用調(diào)用 這個(gè)最佳的時(shí)間片值是多少呢？顯然，它將隨系統(tǒng)而異。隨負(fù)載而

20、異，同時(shí)也隨進(jìn)程異。 時(shí)間片的選取是實(shí)現(xiàn)各種調(diào)度算法的關(guān)鍵之處，而時(shí)間片的獨(dú)額定通常應(yīng)考慮終端數(shù)目，處理機(jī)能力、各終端任務(wù)的急迫程度、外存?zhèn)鬏斔俣鹊确矫娴囊蛩亍r(shí)間片輪轉(zhuǎn)法亦可應(yīng)用于批處理系統(tǒng)的處理機(jī)調(diào)度。 處理機(jī)處理機(jī)調(diào)用調(diào)用一種常用的進(jìn)程調(diào)度算法是把處理機(jī)分配給具有最高優(yōu)先數(shù)的進(jìn)程（用于實(shí)時(shí)系統(tǒng)） 在這種算法中，首先考慮的問題是如何確定進(jìn)程的優(yōu)先數(shù)。 一種是靜態(tài)優(yōu)先數(shù)，另一種是動(dòng)態(tài)優(yōu)先數(shù)。1)靜態(tài)優(yōu)先數(shù) 靜態(tài)優(yōu)先數(shù)是在系統(tǒng)創(chuàng)建時(shí)確定的，一經(jīng)確定之后在整個(gè)進(jìn)程運(yùn)行期間不再改變，確定靜態(tài)優(yōu)先數(shù)的有關(guān)靜特性是：5.優(yōu)先級(jí)調(diào)度算法 處理機(jī)處理機(jī)調(diào)用調(diào)用 系統(tǒng)中由兩類進(jìn)程，系統(tǒng)進(jìn)程和用戶進(jìn)程。系統(tǒng)進(jìn)

21、程的優(yōu)先數(shù)比用戶進(jìn)程的優(yōu)先數(shù)高，特別是某些系統(tǒng)進(jìn)程，必須賦予它一種特權(quán)，當(dāng)它需要處理機(jī)時(shí)，應(yīng)盡快的到滿足。 例如，設(shè)備管理器中的i/o進(jìn)程便是如此。這不僅是為了保證i/o設(shè)備盡可能忙碌，一提高設(shè)備利用率，更主要的是為了避免由于響應(yīng)不及時(shí)，將造成信息的丟失。在用戶進(jìn)程中，i/o繁忙的進(jìn)程應(yīng)優(yōu)先與cpu繁忙的進(jìn)程，以保證cpu和i/o設(shè)備之間的并行操作。在分時(shí)系統(tǒng)中，前臺(tái)進(jìn)程應(yīng)優(yōu)先于后臺(tái)進(jìn)程。 進(jìn)程類型 處理機(jī)處理機(jī)調(diào)用調(diào)用 什么是多處理機(jī)系統(tǒng) 多處理機(jī)操作系統(tǒng)的分類 多處理機(jī)系統(tǒng)調(diào)度策略 3.6 多處理機(jī)調(diào)度 處理機(jī)處理機(jī)調(diào)用調(diào)用 多處理機(jī)系統(tǒng)：是一個(gè)具有兩個(gè)或多個(gè)處理機(jī)并能相互進(jìn)行通信以協(xié)同一

22、個(gè)大的給定問題求解的計(jì)算機(jī)系統(tǒng)。特點(diǎn)： 1） 有兩個(gè)或多個(gè)處理機(jī)2） 共享主存或高速通信網(wǎng)絡(luò)3） 共享輸入輸出子系統(tǒng)4） 有單一完整的操作系統(tǒng)5） 各級(jí)硬件和軟件相互作用3.6.1.什么是多處理機(jī)系統(tǒng) 處理機(jī)處理機(jī)調(diào)用調(diào)用主要功能： 進(jìn)程分配 更好的利用多機(jī)硬件 資源在處理機(jī)之間的分配 改善程序的響應(yīng)時(shí)間 處理機(jī)的負(fù)載平衡 處理機(jī)間的協(xié)調(diào)和同步 因處理機(jī)故障引起的系統(tǒng)重組重組 處理機(jī)處理機(jī)調(diào)用調(diào)用 廣意上說，使用多處理機(jī)協(xié)調(diào)工作，來完成用戶所要求任務(wù)的計(jì)算機(jī)系統(tǒng)。這包擴(kuò)了并行處理系統(tǒng)（parallel processing system），例如數(shù)據(jù)流機(jī)(dataflow machine)和細(xì)胞

23、陣列處理機(jī)(celluar array processors)等,也包擴(kuò)了在物理上分散且通過不同的物理傳輸媒體傳輸數(shù)據(jù)的機(jī)算機(jī)網(wǎng)絡(luò)系統(tǒng)和計(jì)算機(jī)網(wǎng)絡(luò)為基礎(chǔ)的,對(duì)用戶透明的分布式系統(tǒng),以及在同一的計(jì)算機(jī)系統(tǒng)里共享內(nèi)存的多處理機(jī)系統(tǒng). 廣義的計(jì)算機(jī)系統(tǒng)的一個(gè)共同的特點(diǎn)是有n個(gè)處理器(n1),能做到真正的并行處理,也就是能同時(shí)執(zhí)行n條指令. 處理機(jī)處理機(jī)調(diào)用調(diào)用 本節(jié)所介紹的多處理機(jī)操作系統(tǒng)是指哪些用來并行執(zhí)行用戶的幾個(gè)程序，以提高系統(tǒng)的吞吐率；或 行 余操作以提高系統(tǒng)可靠性的多處理操作系統(tǒng)。這種系統(tǒng)由共享公共內(nèi)存和外設(shè)的n(n1)個(gè) cpu組成。 從概念上說，在多處理機(jī)系統(tǒng)中的各進(jìn)程的行為與在單機(jī)系

24、統(tǒng)下的行為相同。因此，對(duì)多處理機(jī)操作系統(tǒng)的要求與對(duì)多道程序的批處理系統(tǒng)沒有太多的區(qū)別。但是，多處理環(huán)竟下，進(jìn)程可在各處理機(jī)間進(jìn)行透明遷移，從而，由進(jìn)程上下文切換等帶來的系統(tǒng)開銷將使得多處理機(jī)操作系統(tǒng)的復(fù)雜度大大增加。另外，由于多處理機(jī)系統(tǒng)并行地執(zhí)行用戶的幾個(gè)程序（進(jìn)程），這又帶來了多處理機(jī)條件下的并發(fā)執(zhí)行問題。3.6.2多處理機(jī)操作系統(tǒng)的分類 處理機(jī)處理機(jī)調(diào)用調(diào)用 使用多處理機(jī)系統(tǒng)的主要原因是提高系統(tǒng)的可靠性和在發(fā)生故障時(shí)能將低使用；另一個(gè)原因是提高系統(tǒng)吞吐 。因此，一個(gè)多處理機(jī)操作系統(tǒng)除了提高資原分配和管理，進(jìn)程和處理機(jī)管理，內(nèi)存和數(shù)據(jù)集保護(hù)以及文件系統(tǒng)等功能之外，還能提供系統(tǒng)結(jié)構(gòu)重組的能力

25、，以支持系統(tǒng)的降級(jí)使用。因此，多處理機(jī)的調(diào)度策略也必須考慮到降級(jí)使用和結(jié)構(gòu)重組問題。 目前為止的多處理機(jī)操作系統(tǒng)可以分為三類： (1) 主從式（master-slave configuration）(2) 獨(dú)立監(jiān)控系統(tǒng)(separate supervisor) (3) 移動(dòng)式監(jiān)控系統(tǒng)(floating supervisor) 處理機(jī)處理機(jī)調(diào)用調(diào)用 主從式中，指定一臺(tái)特定的處理機(jī)為主處理機(jī)，由它負(fù)責(zé)對(duì)全系統(tǒng)的執(zhí)行進(jìn)行控制. 在主從式操作系統(tǒng)中，主處理器上執(zhí)行操作系統(tǒng)程序，以控制其它從處理機(jī)的狀態(tài)，并為從處理機(jī)分配任務(wù)。dec system 10 ,cyber 170 以及多處理機(jī)unix系統(tǒng)mp

26、x都是主從式結(jié)構(gòu).在主從式操作系統(tǒng)中,如果從處理機(jī)需要主處理機(jī)提供服務(wù)時(shí),它們采用硬件中斷方式中斷處理機(jī)上執(zhí)行的進(jìn)程以要求主處理機(jī)提供服務(wù).這種結(jié)構(gòu)的操作系統(tǒng)一般重組功能較差,因?yàn)橹挥兄魈幚頇C(jī)上執(zhí)行操作系統(tǒng)程序.如果主處理機(jī)失敗或發(fā)生不可恢復(fù)的錯(cuò)誤時(shí),整個(gè)系統(tǒng)將會(huì)癱瘓.(1)主從式（master-slave configuration） 處理機(jī)處理機(jī)調(diào)用調(diào)用 獨(dú)立監(jiān)控系統(tǒng)的監(jiān)控程序在每個(gè)處理機(jī)上執(zhí)行, 每個(gè)處理機(jī)為自己的需要提供服務(wù)又互相通報(bào)執(zhí)行情況.一般來說,每個(gè)監(jiān)控程序能重新裝入或在不同的處理機(jī)上復(fù)制獨(dú)立的副本. 獨(dú)立監(jiān)控系統(tǒng)不像主從結(jié)構(gòu)那樣易于崩潰,但其監(jiān)控程序在各處理機(jī)中的副本會(huì)占去大

27、量的內(nèi)存.(2)獨(dú)立監(jiān)控系統(tǒng)(separate supervisor) 處理機(jī)處理機(jī)調(diào)用調(diào)用 移動(dòng)式監(jiān)控系統(tǒng)：移動(dòng)式監(jiān)控系統(tǒng)把監(jiān)控程序根據(jù)需要從一個(gè)處理機(jī)移到另一個(gè)處理機(jī)上.使所有資原有比較均衡的負(fù)載. 移動(dòng)式監(jiān)控系統(tǒng)的處理機(jī)調(diào)度以及服務(wù)請(qǐng)求沖突等大都采用優(yōu)先級(jí)的方式來解決.所以 移動(dòng)式監(jiān)控系統(tǒng)是一種效率最高,實(shí)現(xiàn)也最難的多處理操作系統(tǒng).(3)移動(dòng)式監(jiān)控系統(tǒng)(floating supervisor) 處理機(jī)處理機(jī)調(diào)用調(diào)用（1） 多處理機(jī)系統(tǒng)與單機(jī)調(diào)度的區(qū)別 多處理機(jī)調(diào)度與單機(jī)調(diào)度的主要區(qū)別涉及兩個(gè)資源分配問題：一是存放程序或數(shù)據(jù)的存儲(chǔ)器分配及如何訪問他們的問題。 在多機(jī)系統(tǒng)中，由于各進(jìn)程在物理上也同時(shí)執(zhí)行而不是單機(jī)系統(tǒng)那樣的交叉執(zhí)行，這些在物理上同時(shí)執(zhí)行的進(jìn)程可能同時(shí)訪問物理存儲(chǔ)器的同一地址。處理機(jī)對(duì)同一存儲(chǔ)塊的訪問必須是順序的。各進(jìn)程同時(shí)訪