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

1、 福州大學(xué)數(shù)計學(xué)院主講教師主講教師: : 單單 紅紅計算機(jī)操作系統(tǒng)計算機(jī)操作系統(tǒng)計算機(jī)操作系統(tǒng)計算機(jī)操作系統(tǒng)計算機(jī)操作系統(tǒng)計算機(jī)操作系統(tǒng) 第三章處理機(jī)調(diào)度第三章處理機(jī)調(diào)度 處理機(jī)處理機(jī)調(diào)用調(diào)用調(diào)度策略考慮：周轉(zhuǎn)時間 吞吐率相應(yīng)時間 設(shè)備利用率研究的內(nèi)容有：作業(yè)與進(jìn)程的關(guān)系 作業(yè)調(diào)度策略與算法進(jìn)程調(diào)度策略與算法 幾種調(diào)度策略的評價 本章主要討論處理機(jī)分配問題 處理機(jī)處理機(jī)調(diào)用調(diào)用1.作業(yè)的狀態(tài)及其轉(zhuǎn)換提交狀態(tài)：一個作業(yè)北提交給機(jī)房后或用戶通過終端鍵盤想計算機(jī)鍵入其作業(yè)時所處的狀態(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)時的作業(yè)。 3.1 分級調(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)用高級調(diào)度（作業(yè)調(diào)度、宏觀調(diào)度）按一定原則對外存輸入井上的作業(yè)進(jìn)行調(diào)度，并建立進(jìn)程pcb。它決定允許哪些作業(yè)競爭系統(tǒng)資源。由于這種調(diào)度決定哪些作業(yè)可以進(jìn)入系統(tǒng)，所以也稱收容調(diào)度。作業(yè)一旦被系統(tǒng)收容，就便成進(jìn)程或進(jìn)程組。 中級調(diào)度

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

4、任務(wù)實(shí)體而設(shè)置的執(zhí)行實(shí)體。 顯然，計算機(jī)要完成一個任務(wù)實(shí)體，必須要有一個以上的執(zhí)行實(shí)體，一個作業(yè)總是由一個以上的多個進(jìn)程組成。 3作業(yè)與進(jìn)程的關(guān)系 處理機(jī)處理機(jī)調(diào)用調(diào)用作業(yè)調(diào)度的功能：按某種算法從后備隊(duì)列中挑選一個或一批作業(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)為每個作業(yè)設(shè)置了一個作業(yè)控制塊（jcb）。內(nèi)容：作業(yè)名、作業(yè)狀態(tài)、作業(yè)調(diào)度，以及資源申請和一些控制信息。3.2 作業(yè)的調(diào)度 處理機(jī)處理機(jī)調(diào)用調(diào)用 作業(yè)控制塊jcb 作業(yè)名作業(yè)名 作業(yè)類型作業(yè)類型 資源要求資源要求 資源使用情況資源使用情

5、況 優(yōu)先級優(yōu)先級 當(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)為動態(tài)分配外設(shè)時，作業(yè)所申請的外設(shè)只作為調(diào)度的參考因素）。因此要用到內(nèi)存分配程序和外設(shè)分配程序。為選中的作業(yè)建立相應(yīng)的進(jìn)程。為作業(yè)開始運(yùn)行做好一切準(zhǔn)備工作。如構(gòu)造和讀寫作業(yè)運(yùn)行時所需要的有關(guān)表格及建立負(fù)責(zé)其運(yùn)行控制的作業(yè)運(yùn)行控制程序。在作用運(yùn)行完畢或運(yùn)行

6、過程中因某種原因需要撤離時，作業(yè)調(diào)度程序還有完成作業(yè)的善后處理工作，如收回分配給他的全部資源，它們將從系統(tǒng)中抹去2.作業(yè)調(diào)度應(yīng)完成如下幾方面的工作 處理機(jī)處理機(jī)調(diào)用調(diào)用1)調(diào)度目標(biāo) 對所有作業(yè)應(yīng)該是公平合理 應(yīng)使設(shè)備有高的利用率 每天執(zhí)行盡可能多的作業(yè) 有快的響應(yīng)時間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)用存儲、設(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)用存儲管理，設(shè)備管理回收分配給該作業(yè)的全部資源調(diào)用會計程序，計算該作業(yè)的執(zhí)行費(fèi)用調(diào)度下一個作業(yè)作業(yè)從執(zhí)行狀態(tài)到完成狀態(tài) 處理機(jī)處理機(jī)調(diào)用調(diào)用3）.衡量一個作業(yè)調(diào)度算法是否滿足系統(tǒng)設(shè)計的要 求 給出兩個常用的評價在批處理系統(tǒng)中對作業(yè)調(diào)度算法優(yōu)劣的性能量度1周轉(zhuǎn)時間：作業(yè)i從提交時刻tsi到完成時刻tei稱為作業(yè)的周轉(zhuǎn)時間。ti=tei-tsi 完成 提交3.作業(yè)調(diào)度目標(biāo)與性能衡量 處理機(jī)處理機(jī)調(diào)用調(diào)用作業(yè)平均周轉(zhuǎn)時間為（有n個作業(yè)，n=1) nt=1/n ti i=1一個作業(yè)

8、的周轉(zhuǎn)時間說明了該作業(yè)在系統(tǒng)內(nèi)停留的時間包含兩部分：一是等待時間；二為執(zhí)行時間ti = twi - tri(停留時間)3.作業(yè)調(diào)度目標(biāo)與性能衡量 處理機(jī)處理機(jī)調(diào)用調(diào)用2帶權(quán)周轉(zhuǎn)時間wi：wi=ti/tri 平均帶權(quán)周轉(zhuǎn)時間為： 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)度處理，是一種最普遍和最簡單的方法。它優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)，而不管要求運(yùn)行時間的長短。進(jìn)程調(diào)度算法和作業(yè)調(diào)度算法。 處理機(jī)處理機(jī)調(diào)用調(diào)用作業(yè) 進(jìn)入時刻 開

9、始時刻 完成時刻 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間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)時間t110.008.002.00 帶權(quán)周轉(zhuǎn)時間w12/21 周轉(zhuǎn)時間t210.508.502.00 帶權(quán)周轉(zhuǎn)時間w22.00/0.504.00先來先服務(wù)算法分析結(jié)果 處理機(jī)處理機(jī)調(diào)用調(diào)用 周轉(zhuǎn)時間t311.009.002.00 帶權(quán)周轉(zhuǎn)時間w32.00/0.120.00 周轉(zhuǎn)時間t411.209.501.30 帶權(quán)周轉(zhuǎn)時間w4

10、1.30/0.206.50 周轉(zhuǎn)時間titeitsi 帶權(quán)周轉(zhuǎn)時間witi/tri 平均周轉(zhuǎn)時間t1/ntii=1n 處理機(jī)處理機(jī)調(diào)用調(diào)用 該算法總是優(yōu)先調(diào)度要求運(yùn)行時間最短的作業(yè)。作業(yè) 進(jìn)入時刻 開始時刻 完成時刻 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn)時間 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)時間t1.55 (t=2.00+2.30+1.10+0.40)/4

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

12、。這就克服了短作業(yè)優(yōu)先數(shù)法的缺點(diǎn)，既照顧了先來者，又優(yōu)待了短作業(yè)，是上述兩種算法的一種較好的折中。 處理機(jī)處理機(jī)調(diào)用調(diào)用 作業(yè) 進(jìn)入時刻 開始時刻 完成時刻 周轉(zhuǎn)時刻 帶權(quán)周轉(zhuǎn)時刻 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)時間t1.625平均帶權(quán)周轉(zhuǎn)時間w5.575 處理機(jī)處理機(jī)調(diào)用調(diào)用r1（等待時間執(zhí)行時間）/ 執(zhí)行時間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)用 時間片輪轉(zhuǎn)法主要用于進(jìn)程調(diào)度。采用此算法的系統(tǒng)，其程序就緒隊(duì)列往往按進(jìn)程到達(dá)的時間來排序。進(jìn)程調(diào)度程序總是選擇就緒隊(duì)列中的第一個進(jìn)程，也就是說按照先來先服務(wù)原則調(diào)度，但一旦進(jìn)程占又處理機(jī)僅使用一個時間片。在使用先一個時間片后，進(jìn)程還沒又完成其運(yùn)行，它必須釋放出處理機(jī)給下一個就緒的進(jìn)

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

15、srt/nmax r響應(yīng)時間 nmax最大進(jìn)程數(shù) 每當(dāng)一輪調(diào)度開始時，系統(tǒng)便根據(jù)就緒隊(duì)列中已有進(jìn)程數(shù)目計算一次值。作為新一輪調(diào)度的時間片。這種方法得到的時間片是隨就緒隊(duì)列中的進(jìn)程數(shù)變化的。 處理機(jī)處理機(jī)調(diào)用調(diào)用 進(jìn)程調(diào)度的功能：從就緒隊(duì)列中挑選一個進(jìn)程到處理機(jī)上運(yùn)行。 作業(yè)調(diào)度程序在挑選作業(yè)進(jìn)入主存運(yùn)行時，要為該作業(yè)建立相應(yīng)的進(jìn)程。在作業(yè)完成后要撤銷該作業(yè)的全部進(jìn)程。 一個進(jìn)程被建立后，系統(tǒng)為了便于對進(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ìn)程調(diào)度算法時應(yīng)考慮的因素多，比如：盡量提高資源利用率，減少處理機(jī)的空閑時間，對于用戶作業(yè)要較合理的平均響應(yīng)時間，以及盡可能地增強(qiáng)cpu的處理能力。3. .4 選擇調(diào)度算法時應(yīng)考慮的問題 處理機(jī)處理機(jī)調(diào)用調(diào)用1. fifo(先來先服務(wù)調(diào)度算法) 最簡單的調(diào)度原則是先進(jìn)先出(fifo)就緒隊(duì)列abcdcpu完成3.5 調(diào)度算法 處理機(jī)處理機(jī)調(diào)用調(diào)用 根據(jù)進(jìn)程到達(dá)就緒隊(duì)列的時間來分配中央處理機(jī)，一旦一個進(jìn)程獲得了中央處理機(jī)，就一直運(yùn)行到結(jié)束，先來先服務(wù)是非

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

18、估計執(zhí)行時間，就形成短作業(yè)優(yōu)先的算法。由于作業(yè)需要的執(zhí)行時間事先難于確定，只是把用戶自保的估計時間作為依據(jù)，為防止用戶少報自己的作業(yè)時間以獲得優(yōu)先服務(wù)，在采用短作業(yè)優(yōu)先算法時，應(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í)行時間，還是根據(jù)作業(yè)的大小所確定的優(yōu)先數(shù)，都有利于短作業(yè)。 3.動態(tài)優(yōu)先數(shù) 雖然基于靜態(tài)優(yōu)先數(shù)的調(diào)度算法比較簡單，也頗為流利，但畢竟不夠精確。因?yàn)檫M(jìn)程的優(yōu)先數(shù)在它執(zhí)行前就已算好，且在整個執(zhí)行期間都保持不變，但隨著進(jìn)程的推進(jìn)，

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

20、異，同時也隨進(jìn)程異。 時間片的選取是實(shí)現(xiàn)各種調(diào)度算法的關(guān)鍵之處，而時間片的獨(dú)額定通常應(yīng)考慮終端數(shù)目，處理機(jī)能力、各終端任務(wù)的急迫程度、外存?zhèn)鬏斔俣鹊确矫娴囊蛩亍r間片輪轉(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í)時系統(tǒng)） 在這種算法中，首先考慮的問題是如何確定進(jìn)程的優(yōu)先數(shù)。 一種是靜態(tài)優(yōu)先數(shù)，另一種是動態(tài)優(yōu)先數(shù)。1)靜態(tài)優(yōu)先數(shù) 靜態(tài)優(yōu)先數(shù)是在系統(tǒng)創(chuàng)建時確定的，一經(jīng)確定之后在整個進(jìn)程運(yùn)行期間不再改變，確定靜態(tài)優(yōu)先數(shù)的有關(guān)靜特性是：5.優(yōu)先級調(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ī)時，應(yīng)盡快的到滿足。 例如，設(shè)備管理器中的i/o進(jìn)程便是如此。這不僅是為了保證i/o設(shè)備盡可能忙碌，一提高設(shè)備利用率，更主要的是為了避免由于響應(yīng)不及時，將造成信息的丟失。在用戶進(jìn)程中，i/o繁忙的進(jìn)程應(yīng)優(yōu)先與cpu繁忙的進(jìn)程，以保證cpu和i/o設(shè)備之間的并行操作。在分時系統(tǒng)中，前臺進(jìn)程應(yīng)優(yōu)先于后臺進(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)：是一個具有兩個或多個處理機(jī)并能相互進(jìn)行通信以協(xié)同一

22、個大的給定問題求解的計算機(jī)系統(tǒng)。特點(diǎn)： 1） 有兩個或多個處理機(jī)2） 共享主存或高速通信網(wǎng)絡(luò)3） 共享輸入輸出子系統(tǒng)4） 有單一完整的操作系統(tǒng)5） 各級硬件和軟件相互作用3.6.1.什么是多處理機(jī)系統(tǒng) 處理機(jī)處理機(jī)調(diào)用調(diào)用主要功能： 進(jìn)程分配 更好的利用多機(jī)硬件 資源在處理機(jī)之間的分配 改善程序的響應(yīng)時間 處理機(jī)的負(fù)載平衡 處理機(jī)間的協(xié)調(diào)和同步 因處理機(jī)故障引起的系統(tǒng)重組重組 處理機(jī)處理機(jī)調(diào)用調(diào)用 廣意上說，使用多處理機(jī)協(xié)調(diào)工作，來完成用戶所要求任務(wù)的計算機(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ī)網(wǎng)絡(luò)為基礎(chǔ)的,對用戶透明的分布式系統(tǒng),以及在同一的計算機(jī)系統(tǒng)里共享內(nèi)存的多處理機(jī)系統(tǒng). 廣義的計算機(jī)系統(tǒng)的一個共同的特點(diǎn)是有n個處理器(n1),能做到真正的并行處理,也就是能同時執(zhí)行n條指令. 處理機(jī)處理機(jī)調(diào)用調(diào)用 本節(jié)所介紹的多處理機(jī)操作系統(tǒng)是指哪些用來并行執(zhí)行用戶的幾個程序，以提高系統(tǒng)的吞吐率；或 行 余操作以提高系統(tǒng)可靠性的多處理操作系統(tǒng)。這種系統(tǒng)由共享公共內(nèi)存和外設(shè)的n(n1)個 cpu組成。 從概念上說，在多處理機(jī)系統(tǒng)中的各進(jìn)程的行為與在單機(jī)系

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

25、，以支持系統(tǒng)的降級使用。因此，多處理機(jī)的調(diào)度策略也必須考慮到降級使用和結(jié)構(gòu)重組問題。 目前為止的多處理機(jī)操作系統(tǒng)可以分為三類： (1) 主從式（master-slave configuration）(2) 獨(dú)立監(jiān)控系統(tǒng)(separate supervisor) (3) 移動式監(jiān)控系統(tǒng)(floating supervisor) 處理機(jī)處理機(jī)調(diào)用調(diào)用 主從式中，指定一臺特定的處理機(jī)為主處理機(jī)，由它負(fù)責(zé)對全系統(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ù)時,它們采用硬件中斷方式中斷處理機(jī)上執(zhí)行的進(jìn)程以要求主處理機(jī)提供服務(wù).這種結(jié)構(gòu)的操作系統(tǒng)一般重組功能較差,因?yàn)橹挥兄魈幚頇C(jī)上執(zhí)行操作系統(tǒng)程序.如果主處理機(jī)失敗或發(fā)生不可恢復(fù)的錯誤時,整個系統(tǒng)將會癱瘓.(1)主從式（master-slave configuration） 處理機(jī)處理機(jī)調(diào)用調(diào)用 獨(dú)立監(jiān)控系統(tǒng)的監(jiān)控程序在每個處理機(jī)上執(zhí)行, 每個處理機(jī)為自己的需要提供服務(wù)又互相通報執(zhí)行情況.一般來說,每個監(jiān)控程序能重新裝入或在不同的處理機(jī)上復(fù)制獨(dú)立的副本. 獨(dú)立監(jiān)控系統(tǒng)不像主從結(jié)構(gòu)那樣易于崩潰,但其監(jiān)控程序在各處理機(jī)中的副本會占去大

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