第三章處理機調(diào)度與死鎖1.ppt

1、第三章,處理機調(diào)度與死鎖 （一）,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,2,本章主要內(nèi)容,調(diào)度的基本概念 基本調(diào)度算法 死鎖的基本概念 解決死鎖的幾種方法,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,3,調(diào)度主要討論處理機分配問題,在多道單處理機系統(tǒng)環(huán)境下，內(nèi)存就緒隊列往往有多個進程等待處理機，而分配處理機的任務(wù)通常是由調(diào)度程序完成的。 由于處理機是計算機系統(tǒng)中最重要的資源，故提高處理機的利用率、改善系統(tǒng)性能很大程度取決于處理機調(diào)度性能的優(yōu)劣。 處理機調(diào)度的主要目標(biāo) 對CPU資源進行合理的分配使用，以提高CPU利用率 使各用戶公平地得到處理機資源 減少用戶的響應(yīng)時間。 處理機調(diào)度管理問題是操作系統(tǒng)設(shè)計的

2、核心問題之一。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,4,3.1 處理機調(diào)度的層次,多道批處理系統(tǒng)的一個作業(yè)被提交后，若想得到處理機運行，須經(jīng)歷作業(yè)調(diào)度、進程調(diào)度； 而一個終端型作業(yè)，則只需經(jīng)歷進程調(diào)度，即可獲得處理機運行； 在作業(yè)執(zhí)行過程，由于某種原因，可通過中級調(diào)度，將作業(yè)換出內(nèi)存，將其掛起暫停執(zhí)行，當(dāng)條件允許，中級調(diào)度又可將其調(diào)入內(nèi)存繼續(xù)執(zhí)行。 由上可看出，處理機調(diào)度是分層次的。 對于每一層次的調(diào)度，都可選擇不同的調(diào)度方式和調(diào)度算法。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,5,1處理機調(diào)度的層次 處理機是計算機系統(tǒng)中的重要資源，處理機調(diào)度算法對整個計算機系統(tǒng)的綜合性能指標(biāo)有重要影響?？砂烟幚?/p>

3、機調(diào)度分成三個層次：高級調(diào)度，中級調(diào)度，低級調(diào)度 高級調(diào)度（作業(yè)調(diào)度/宏觀調(diào)度/長程調(diào)度/接納調(diào)度/收容調(diào)度） 按一定原則選擇外存輸入井上后備作業(yè)隊列中的一個或多個作業(yè)進入內(nèi)存，并為其建立相應(yīng)的進程。 它決定允許哪些作業(yè)有資格競爭系統(tǒng)資源。 它只涉及虛擬處理機分配 分時與實時系統(tǒng)無須此層調(diào)度,3.1 處理機調(diào)度的層次,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,6,低級調(diào)度（進程調(diào)度/微觀調(diào)度/短程調(diào)度） 當(dāng)內(nèi)存就緒隊列不為空時，它決定哪一個就緒進程可分配到中央處理機（即低級調(diào)度是將處理機實際地分配給某進程）。 低級調(diào)度是由每秒可操作許多次的處理機調(diào)度程序執(zhí)行，處理機調(diào)度程序應(yīng)常駐內(nèi)存。 進程調(diào)度的方

4、式：非搶占方式（非剝奪）：實時性差 搶占方式（剝奪） 搶占的方式有：1 時間片原則； 2 優(yōu)先級原則； 3 短進程優(yōu)先原則。,3.1 處理機調(diào)度的層次,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,7,中級調(diào)度（交換調(diào)度） 它決定允許哪些進程競爭處理機。 中級調(diào)度通過使進程臨時掛起和激活的方法對系統(tǒng)負(fù)載波動作出反映，以便獲得平穩(wěn)的系統(tǒng)操作和實現(xiàn)較好的系統(tǒng)綜合性能目標(biāo)。 中級調(diào)度的作用是作為作業(yè)進入系統(tǒng)和將中央處理機分配給這些作業(yè)二者之間的一個緩沖 引入中級調(diào)度的目的是為提高內(nèi)存的利用率和系統(tǒng)吞吐量,3.1 處理機調(diào)度的層次,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,8,3.1 處理機調(diào)度的層次,中級調(diào)度屬內(nèi)存

5、管理部分。涉及進程在內(nèi)外存間的交換； 從存儲器資源管理的角度來看，把進程的部分或全部換出到外存上，可為當(dāng)前運行進程的執(zhí)行提供所需內(nèi)存空間，將當(dāng)前進程所需部分換入到內(nèi)存。（指令和數(shù)據(jù)必須在內(nèi)存里才能被處理機直接訪問）。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,9,作業(yè)狀態(tài)及其轉(zhuǎn)換圖,spooling 系統(tǒng),提交,外存,就緒,等待,運行,就緒,等待,交換調(diào)度,完 成,作業(yè)調(diào)度,進程調(diào)度,后備,收容,執(zhí)行,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,10,2、調(diào)度隊列模型,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,11,2、調(diào)度隊列模型,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,12,同時具有三級調(diào)度的調(diào)度隊列模型,中級調(diào)

6、度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,13,1作業(yè)調(diào)度及其功能 作業(yè)調(diào)度:按照某種調(diào)度算法，從后備作業(yè)隊列中選取 一個或一批作業(yè)，使其進入內(nèi)存運行。完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)變。 主要功能:是審查系統(tǒng)是否能滿足用戶作業(yè)的資源要求以及按照一定的算法選取作業(yè)。 記錄已進入系統(tǒng)的各作業(yè)的情況（JCB：Job Control Block）； 按一定的調(diào)度算法，從后備作業(yè)中選擇一個或幾個作 業(yè)進入系統(tǒng)內(nèi)存； 為被選中的作業(yè)創(chuàng)建進程，并且為其申請系統(tǒng)資源； 作業(yè)結(jié)束后作善后處理工作。,3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,14,后備作業(yè)隊列空,按調(diào)度算法從后備

7、作 業(yè)隊列中選出一作業(yè),調(diào)用存儲、設(shè)備管理 程序，審核資源要求,資源要求能滿足？,放棄該 作業(yè),否,分配資源,調(diào)用進程管理 程序建立進程,進程調(diào)度,否,是,出 口,作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài),是,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,15,撤銷該作業(yè)的所有進程及作業(yè)的JCB,調(diào)用存儲管理，設(shè)備管理回收 分配給該作業(yè)的全部資源,調(diào)用會計程序，計算該作業(yè)的執(zhí)行費用,調(diào)度下一個作業(yè),作業(yè)從執(zhí)行狀態(tài)到完成狀態(tài),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,16,3.1 處理機調(diào)度的層次,2. 作業(yè)調(diào)度所考慮的問題： 每次能調(diào)入多少作業(yè)進入內(nèi)存取決于系統(tǒng)的“多道程序度” 和資源利用情況； 選擇哪些作業(yè)進入內(nèi)存取決于調(diào)

8、度算法和資源利用情況； 何時調(diào)入作業(yè)進入內(nèi)存取決于是否有作業(yè)退出系統(tǒng)，或內(nèi)存是否有足夠資源。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,17,作業(yè)控制塊JCB,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,18,作業(yè)調(diào)度算法規(guī)定了從后備作業(yè)隊列中選擇作業(yè)進入系統(tǒng)內(nèi)存的原則。 調(diào)度原則 應(yīng)與系統(tǒng)的整體設(shè)計目標(biāo)一致，盡量提高系統(tǒng)的吞吐量 均衡利用系統(tǒng)中各種資源，考慮負(fù)載均勻 對所有作業(yè)應(yīng)該公平合理，保證各類作業(yè)的執(zhí)行 對優(yōu)先級較高的作業(yè)優(yōu)先調(diào)度 應(yīng)有較快的響應(yīng)時間,3.作業(yè)調(diào)度原則與性能衡量,3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,19, 性能衡量 通常采用平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間 周轉(zhuǎn)時間T

9、i ： 作業(yè)i從提交時刻Tsi到完成時刻Tei稱為作業(yè)的周轉(zhuǎn)時間 Ti = Tei - Tsi 完成 提交,3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,20,作業(yè)平均周轉(zhuǎn)時間為（有n個作業(yè)，n=1) n T=1/n Ti i=1 一個作業(yè)的周轉(zhuǎn)時間說明了該作業(yè)在系統(tǒng)內(nèi)停留的時間 其中包含兩部分：一是等待時間；二為執(zhí)行時間 即 Ti = Twi + Tri (停留時間),3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,21, 帶權(quán)周轉(zhuǎn)時間Wi： Wi=Ti/Tri Tri :作業(yè)i 的實際運行時間 平均帶權(quán)周轉(zhuǎn)時間為： W=,3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,

10、22,3.2 作業(yè)調(diào)度,響應(yīng)時間：從提交一個請求到首次產(chǎn)生響應(yīng) CPU、I/O執(zhí)行期：分CPU忙和I/O忙 截止時間：某任務(wù)必須開始執(zhí)行（或必須完成）的最遲時間（開始截止、完成截止）。它是評價實時系統(tǒng)性能的重要指標(biāo)。 優(yōu)先權(quán),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,23,（1）先來先服務(wù)（FCFS）調(diào)度算法 既適合作業(yè)調(diào)度，也適合進程調(diào)度。 將用戶作業(yè)（/就緒進程）按提交順序（/變?yōu)榫途w狀態(tài)）的先后排成隊列，并按照先來先服務(wù)的方式進行調(diào)度處理。它是一種最普遍和最簡單的方法。 優(yōu)先考慮在系統(tǒng)中等待時間最長的作業(yè)（進程），而不管要求運行時間的長短。, 作業(yè)調(diào)度算法,3.2 作業(yè)調(diào)度,2020/10/1

11、1,數(shù)學(xué)科學(xué)學(xué)院,24,FCFS算法調(diào)度例,作業(yè),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,25,3.2 作業(yè)調(diào)度,FCFS調(diào)度算法的特點： 實現(xiàn)簡單； 效率較低； 有利于運行時間長的作業(yè)（進程），不利于短作業(yè)（進程）； 有利于CPU繁忙型的作業(yè)（進程），不利于I/O繁忙型的作業(yè)（進程）。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,26,（2）短作業(yè)（進程）優(yōu)先法（SJF/SPF）,既適合作業(yè)調(diào)度，也適合進程調(diào)度 短作業(yè)（進程）優(yōu)先調(diào)度算法：考慮作業(yè)（進程）的運行時間，每次總是選擇一個運行時間最短的作業(yè)（進程）執(zhí)行. 分為：非搶占式和搶占式 一般情況下這種調(diào)度算法比先來先服務(wù)調(diào)度算法的效率要高一些。,3.

12、2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,27,SJF/SPF算法例1,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,28,SJF/SPF算法例2,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,29,3.2 作業(yè)調(diào)度,SJF/SPF優(yōu)點：調(diào)度性能較好。 SJF/SPF缺點： 1）不利于長作業(yè)（進程）。 2）不考慮作業(yè)（進程）的緊迫程度。 3）估計的運行時間很難準(zhǔn)確獲得。 4）如果作業(yè)的到來順序及運行時間不合適，可能會出現(xiàn)饑餓現(xiàn)象。 例如，系統(tǒng)中有一個運行時間很長的作業(yè)JN，和幾個運行時間短的作業(yè)，若系統(tǒng)不斷地有運行時間小于JN的作業(yè)的到來，這樣作業(yè)JN就得不到調(diào)度而出現(xiàn)饑餓現(xiàn)象。,2020/10/11,數(shù)

13、學(xué)科學(xué)學(xué)院,30,3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,31,(3) 最高響應(yīng)比作業(yè)優(yōu)先算法（HRN） 最高響應(yīng)比作業(yè)優(yōu)先算法是對FCFS方式和SJF方式的一種綜合平衡。 先來先服務(wù)和短作業(yè)優(yōu)先算法都有其片面性。 先來先服務(wù)調(diào)度算法只考慮作業(yè)的等待時間，而忽視了作業(yè)的運行時間； 短作業(yè)優(yōu)先算法則相反，只考慮了作業(yè)運行時間，而忽視了作業(yè)等待時間。 響應(yīng)比高者優(yōu)先調(diào)度算法是介于這兩種算法之間的一種折衷的算法。,3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,32,3.2 作業(yè)調(diào)度,響應(yīng)比R：系統(tǒng)對作業(yè)的響應(yīng)時間與作業(yè)要 求運行時間的比值 R 響應(yīng)時間 / 要求運行時間 (作業(yè)

14、等待時間需運行時間)/需運行時間 1已等待時間 / 需運行時間 1W/T,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,33,響應(yīng)比R不僅是要求運行時間的函數(shù)，而且還是等待時間的函數(shù)。 由于R與要求運行時間成反比，故對短作業(yè)是有利的； 又因R與等待時間成正比，故長作業(yè)隨著其等待時間的增長，也可獲的較高的相應(yīng)比。 該算法既照顧了先來者，又優(yōu)待了短作業(yè)，是上述兩種算法的一種較好的折衷。,3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,34,作業(yè) 提交時刻 運行時間 開始時刻 完成時刻 周轉(zhuǎn)時間 帶權(quán)周轉(zhuǎn) 1 8.00 2.00 8.00 10.00 2.00 1.00 2 8.50 0.50 10.1

15、0 10.60 2.10 4.20 3 9.00 0.10 10.00 10.10 1.10 11.00 4 9.50 0.20 10.60 10.80 1.30 6.50 平均周轉(zhuǎn)時間1.625h 帶權(quán)周轉(zhuǎn)時間 5.675h Rp(1): 作業(yè)2: 1+(10-8.5)/0.5=4 作業(yè)3: 1+(10-9)/0.1=11 作業(yè)4: 1+(10-9.5)/0.2=3.5 Rp(2): 作業(yè)2: 1+(10.1-8.5)/0.5=3.2 作業(yè)4: 1+(10.1-9.5)/0.2=3 作業(yè)執(zhí)行順序：1，3，2，4,3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,35,HRN例,注：式中的

16、時間按分鐘計算,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,36,3.2 作業(yè)調(diào)度,該算法從理論上講是比較完備的，但 作業(yè)調(diào)度程序要統(tǒng)計作業(yè)的等待時間，使用用戶需估計的運行時間，不實際； 每次調(diào)度要做浮點運算（這是系統(tǒng)程序最忌諱的）浪費大量的計算時間，是系統(tǒng)程序所不允許的。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,37,3.2 作業(yè)調(diào)度,（4）優(yōu)先數(shù)調(diào)度算法 優(yōu)先數(shù)調(diào)度算法是綜合考慮各方面的因素（作業(yè)等待時間、運行時間、緩急程度，系統(tǒng)資源使用等），給每個作業(yè)設(shè)置一個優(yōu)先數(shù) 調(diào)度程序總是選擇一個優(yōu)先級最高（即優(yōu)先數(shù)最大或者最小）的作業(yè)調(diào)入（系統(tǒng)）內(nèi)存。 這種算法實現(xiàn)的困難在于如何綜合考慮，這些因素之間的關(guān)系

17、怎樣處理。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,38,3.3 進程調(diào)度,進程調(diào)度的功能 從就緒隊列中挑選一個進程到處理機上運行 作業(yè)調(diào)度程序在挑選作業(yè)進入主存運行時，要為該作業(yè)建立相應(yīng)的進程。在作業(yè)完成后要撤銷該作業(yè)的全部進程。 一個進程被建立后，系統(tǒng)為了便于對進程的管理，將系統(tǒng)中的所有進程按其狀態(tài)組織成不同的進程隊列。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,39,3.3 進程調(diào)度,進程調(diào)度的相關(guān)工作： 1.記錄和保持系統(tǒng)中所有進程的有關(guān)情況和狀態(tài)特征 有關(guān)進程調(diào)度的信息是記錄在PCB中的，在進程調(diào)度中主要用到的是進程的狀態(tài)、調(diào)度優(yōu)先級（優(yōu)先數(shù)）、就緒的進程隊列等。 2.決定分配（處理機）策略

18、確定進程調(diào)度的策略，如先來先服務(wù)、優(yōu)先數(shù)調(diào)度策略。調(diào)度策略不同，組織就緒進程隊列的方式也不同。 先來先服務(wù)調(diào)度策略，就緒隊列按等待時間大到小順序排隊； 優(yōu)先數(shù)調(diào)度調(diào)度策略，就緒進程隊列按優(yōu)先數(shù)的升序（或降序）的方式排隊。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,40,3.3 進程調(diào)度,3.實施處理機的分配 進行進程上下文的切換 總而言之，進程調(diào)度包括： 調(diào)度算法的選擇，即按什么原則分配CPU 調(diào)度時機的選擇，即何時分配CPU 實施進程調(diào)度，即如何分配CPU，CPU調(diào)度過程（調(diào)度程序，進程的上下文切換）,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,41,3.3 進程調(diào)度,進程調(diào)度程序（或稱調(diào)度程序）: 實施

19、進程調(diào)度的內(nèi)核程序。 在通常的操作系統(tǒng)原理中，該程序?qū)儆谙到y(tǒng)進程的執(zhí)行程序。 有些操作系統(tǒng)是把進程調(diào)度程序作一個特別的處理，如早期的操作系統(tǒng)中把進程調(diào)度程序稱為交通控制程序，不屬于系統(tǒng)中的任何進程。 進程上下文 是進程執(zhí)行活動全過程的靜態(tài)描述。包括計算機系統(tǒng)中與執(zhí)行該進程有關(guān)的各種寄存器的值、程序段，在經(jīng)過編譯之后形成的機器指令代碼集、數(shù)據(jù)集及各種堆棧值和PCB結(jié)構(gòu)。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,42,3.3 進程調(diào)度,進程調(diào)度的時機 指什么情況下引起進程調(diào)度程序工作。 進程調(diào)度的時機與進程調(diào)度的方式有關(guān)。 進程調(diào)度時機如下： （1）正在執(zhí)行的進程正確完成或由于某種錯誤而終止運行； （

20、2）執(zhí)行中的進程提出I/O請求，等待I/O完成時，轉(zhuǎn)進程調(diào)度；,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,43,3.3 進程調(diào)度,（3）在分時系統(tǒng)中，按照時間片輪轉(zhuǎn)，分給進程的時間片用完時； （4）按照優(yōu)先級調(diào)度、短作業(yè)優(yōu)先調(diào)度時，有更高優(yōu)先級進程變?yōu)榫途w時或出現(xiàn)更短進程時（即出現(xiàn)進程搶占因素時）； （5）在進程通信中，執(zhí)行中的進程執(zhí)行了某種原語操作，如P操作、阻塞原語和喚醒原語時，都可能引起進程調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,44,D,C,B,A,CPU,完成,3.3 進程調(diào)度,調(diào)度算法 1. 先來先服務(wù)調(diào)度算法 ( FCFS ) 最簡單的調(diào)度原則是先進先出就緒隊列,2020/10/11

21、,數(shù)學(xué)科學(xué)學(xué)院,45,3.3 進程調(diào)度,根據(jù)進程到達就緒隊列的時間來分配中央處理機，一旦一個進程獲得了中央處理機，就一直運行到結(jié)束，先來先服務(wù)是非剝奪調(diào)度。 這種調(diào)度從形式上講是公平的，但它使短進程要等待長進程的完成，重要的進程要等待不重要進程的完成。從這個意義上講又是不公平的。 先進先出調(diào)度使響應(yīng)時間的變化較小，因此它比其它大多數(shù)調(diào)度都可預(yù)測。由于這種調(diào)度方法不能保證良好的響應(yīng)時間，在處理交互式用戶時很少用這種方法。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,46,3.3 進程調(diào)度,在現(xiàn)代系統(tǒng)中，先進先出很少作為單獨的調(diào)度模式，而是常常嵌套在其它的調(diào)度模式中。 例如，許多調(diào)度模式根據(jù)優(yōu)先級將處理機

22、分配給進程，但具有相同優(yōu)先級的進程卻按先進先出進行分配。 2 .短進程優(yōu)先調(diào)度算法（同短作業(yè)優(yōu)先） 此時進程就緒隊列按照進程執(zhí)行時間的長短排隊。 可分為搶占式和非搶占式。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,47,3 . 時間片輪轉(zhuǎn)法（RR：Round Robin） 簡單時間片輪轉(zhuǎn)法 時間片輪轉(zhuǎn)法主要用于進程調(diào)度。 就緒隊列往往按進程到達的時間來排序。 進程調(diào)度程序按照先來先服務(wù)原則調(diào)度。 把系統(tǒng)的響應(yīng)時間分成大小相等（或不等）的時間單位，稱時間片。 每個進程被調(diào)度后，占用一個時間片，時間片用完后，該進程讓出CPU給下一個就緒的進程。 若該進程還沒有完成其運行，則返回到就緒隊列的末尾重新排隊等

23、待再次運行。即由運行狀態(tài)轉(zhuǎn)換成就緒狀態(tài)。如此，多個進程循環(huán)輪轉(zhuǎn)。,3.3 進程調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,48,時間片輪轉(zhuǎn)法例,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,49,時間片輪轉(zhuǎn)策略特別適合于分時系統(tǒng)。 在輪轉(zhuǎn)法中，時間片長度的選取非常重要，它會直接影響系統(tǒng)開銷和響應(yīng)時間。 如果時間片長度過短，則調(diào)度程序剝奪處理機的次數(shù)增多，這將使進程上下文交換次數(shù)也大大增加，加重了系統(tǒng)開銷； 如果時間片長度選擇過長（大）。大到一個進程足以完成其全部運行工作所需的時間，那么時間片輪轉(zhuǎn)法就退化為先來先服務(wù)策略了； 最佳時間片量值應(yīng)能使分時用戶得到好的響應(yīng)時間。,3.3 進程調(diào)度,2020/10/

24、11,數(shù)學(xué)科學(xué)學(xué)院,50,3.3 進程調(diào)度,最佳的時間片值是多少呢？ 它將隨系統(tǒng)而異，隨負(fù)載而異，同時也隨進程而異。 時間片的選取是實現(xiàn)各種調(diào)度算法的關(guān)鍵之處，而時間片的值的確定通常應(yīng)考慮終端數(shù)目，處理機能力、各終端任務(wù)的急迫程度、外存?zhèn)鬏斔俣鹊确矫娴囊蛩亍?時間片輪轉(zhuǎn)法亦可應(yīng)用于批處理系統(tǒng)的處理機調(diào)度。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,51,3.3 進程調(diào)度,設(shè)時間片為q，進程數(shù)為N，則進程的響應(yīng)時間T=Nq q的選擇一般在100毫秒級 影響時間片大小的因素： 系統(tǒng)響應(yīng)時間T： N一定，T與q成正比； 就緒隊列中進程數(shù)目N： T一定，就緒隊列中進程數(shù)越多，q值就越??； 進程切換t（轉(zhuǎn)換時

25、間)：t/q應(yīng)不大于某值，否則會影響T，從而影響q； 系統(tǒng)處理能力：程序處理時間、切換次數(shù)、響應(yīng)時間 一般處理能力:必須保證用戶鍵入的命令可在一個時間片內(nèi)處理完畢。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,52,F,C,B,A,.,CPU,完成,3.3 進程調(diào)度,幾種情況的調(diào)度： 進程在時間片內(nèi)執(zhí)行完畢提前調(diào)度 進程在執(zhí)行過程中提出I/O而阻塞重新調(diào)度 進程在一時間片內(nèi)未完成將該進程放就緒隊列末，重新調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,53,3.3 進程調(diào)度,系統(tǒng)按進程轉(zhuǎn)換成就緒狀態(tài)的時間的降序排隊，調(diào)度程序每次調(diào)度，總是從隊首移出一程的PCB，然后，將此進程投入運行（由就緒狀態(tài)轉(zhuǎn)換成運行狀

26、態(tài)）。一個運行時間片到的進程從運行狀態(tài)轉(zhuǎn)換成就緒狀態(tài)后，排在就緒隊列的隊尾。 評價： 優(yōu)點是實現(xiàn)簡單、系統(tǒng)開銷小 缺點是不靈活，當(dāng)系統(tǒng)中進程較少時，系統(tǒng)開銷變大 由于該算法簡單易于實現(xiàn)，且系統(tǒng)開銷較小，早期的分時操作系統(tǒng)和目前一些應(yīng)用系統(tǒng)中廣泛采用了這種調(diào)度算法。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,54,3.3 進程調(diào)度,對簡單時間片輪轉(zhuǎn)法的改進 將固定時間片改為可變時間片可變時間片輪轉(zhuǎn)法 將單就緒隊列改為多就緒隊列，每個隊列所賦予的時間片不同。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,55,3.3 進程調(diào)度, 可變時間片輪轉(zhuǎn)法（固定周期輪轉(zhuǎn)法） 思想：時間片的大小是可變的，系統(tǒng)可根據(jù)系 統(tǒng)中當(dāng)

27、前的進程數(shù)來確定時間片的大小 該算法從理論上克服了系統(tǒng)中進程數(shù)很少時系統(tǒng)開銷大的缺點。 但修改時間片的大小，統(tǒng)計系統(tǒng)進程的數(shù)量也需要消耗系統(tǒng)時間。 需調(diào)整時間片大小的周期，太大，等于是固定時間片，太小，系統(tǒng)開銷很大，得不嘗失。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,56,時間片 qT/N, T響應(yīng)時間, N最大進程數(shù) 每當(dāng)一輪調(diào)度開始時，系統(tǒng)便根據(jù)就緒隊列中已有進程數(shù)目計算一次q值，作為新一輪調(diào)度的時間片。 這種方法得到的時間片是隨就緒隊列中的進程數(shù)變化的。 例：若T=2s，N=20 ，q=0.1s， q=T/N， 設(shè)執(zhí)行一輪后N=10， 若固定T，則q=o.2s, 可減少系統(tǒng)開銷,3.3 進程

28、調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,57,3.3 進程調(diào)度,4.優(yōu)先級調(diào)度算法一種常用的進程調(diào)度算法是把處理機分配給具有最高優(yōu)先級的進程（用于分時系統(tǒng)和實時系統(tǒng)） 確定進程的優(yōu)先數(shù)：一種是靜態(tài)優(yōu)先數(shù)，另一種是動態(tài)優(yōu)先數(shù)（適合于分時系統(tǒng)和實時系統(tǒng)）。 優(yōu)先級調(diào)度算法可分為：搶占式（適合于分時系統(tǒng)和實時系統(tǒng)）和非搶占式（適合于批處理系統(tǒng)）,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,58,3.3 進程調(diào)度,優(yōu)先隊列： 可按優(yōu)先級設(shè)置多個隊列 在隊列中若有相同優(yōu)先級作業(yè)，按先來先服務(wù)原則排隊； 調(diào)度從最高優(yōu)先級隊列開始，每個隊列次序按到達的先后順序排隊。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,59,20

29、20/10/11,數(shù)學(xué)科學(xué)學(xué)院,60,3.3 進程調(diào)度,優(yōu)先數(shù)調(diào)度算法是目前操作系統(tǒng)廣泛采用的一種進程調(diào)度算法 這種算法按照某種原則由系統(tǒng)（或用戶、或系統(tǒng)與用戶結(jié)合）賦予每個進程一個優(yōu)先數(shù) 在處理機空閑時，進程調(diào)度程序就從就緒進程中選擇一個優(yōu)先數(shù)最大（或者最?。┑倪M程占用CPU（該進程就從就緒狀態(tài)轉(zhuǎn)換成運行狀態(tài)）。 采用這種調(diào)度算法的關(guān)鍵是如何確定進程的優(yōu)先數(shù)、一個進程的優(yōu)先數(shù)確定之后是固定的還是隨著該進程運行的情況的變化而變化。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,61,3.3 進程調(diào)度,1)靜態(tài)優(yōu)先數(shù) 靜態(tài)優(yōu)先數(shù)是在系統(tǒng)創(chuàng)建時確定的，一經(jīng)確定之后在整個進程運行期間不再改變。通常與作業(yè)優(yōu)先數(shù)

30、相同。 在有的系統(tǒng)中，分配給作業(yè)的優(yōu)先數(shù)還取決于它所占用的內(nèi)存的多少。作業(yè)越大，占用內(nèi)存越多，分配給它的優(yōu)先數(shù)越低。 顯然，不論是根據(jù)作業(yè)的執(zhí)行時間，還是根據(jù)作業(yè)的大小所確定的優(yōu)先數(shù)，都有利于短作業(yè)。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,62,3.3 進程調(diào)度,確定進程優(yōu)先數(shù)方法： 系統(tǒng)確定：（運行時間、使用資源，進程的類型） 用戶確定：（緊迫程度，計費等） 系統(tǒng)與用戶結(jié)合（用戶可以為本用戶的進程設(shè)置優(yōu)先數(shù)，但不是作調(diào)度用，系統(tǒng)還要根據(jù)系統(tǒng)情況把用戶設(shè)置的進程優(yōu)先數(shù)作為確定進程優(yōu)先數(shù)的一個參數(shù)）,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,63,3.3 進程調(diào)度,靜態(tài)優(yōu)先數(shù)確定規(guī)則： 進程類型：用戶進

31、程（包括：I/O繁忙和CPU繁忙、交互型和批處理型，前臺進程和后臺進程） 系統(tǒng)進程優(yōu)先級高于用戶進程（以便管理） I/O繁忙優(yōu)先級高于CPU繁忙進程（以保證CPU、 I/O并行） 交互型優(yōu)先級高于批處理型進程（以滿足響應(yīng)時間） 前臺進程優(yōu)先級高于后臺進程（分時系統(tǒng)）,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,64,3.3 進程調(diào)度,進程對資源的需求：作業(yè)短、I/O多、占內(nèi)存少可獲高優(yōu)先級 用戶需求：根據(jù)用戶提供的外部優(yōu)先數(shù)（考慮任務(wù)的緊迫程度及費用）及作業(yè)到達的順序確定,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,65,3.3 進程調(diào)度,2）動態(tài)優(yōu)先數(shù) 雖然基于靜態(tài)優(yōu)先數(shù)的調(diào)度算法比較簡單，易行，但畢竟不夠

32、精確。 因為進程的優(yōu)先數(shù)在它執(zhí)行前就已算好，且在整個執(zhí)行期間都保持不變，但隨著進程的推進，計算優(yōu)先數(shù)所依賴的特征很多都將隨之改變，因此靜態(tài)優(yōu)先數(shù)并非自始至終都能準(zhǔn)確地反映出這些特性 如果能在進程運行中，不斷的隨著特性的改變而修改其優(yōu)先數(shù)，顯然可以實現(xiàn)更多精確的調(diào)度，從而獲得更好的調(diào)度性能，這對分時系統(tǒng)顯得格外重要.,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,66,3.3 進程調(diào)度,動態(tài)進程優(yōu)先數(shù)： 在運行的過程中，根據(jù)系統(tǒng)的設(shè)計目標(biāo)，不斷地調(diào)整進程的優(yōu)先數(shù)。 在進程創(chuàng)建時，先賦一初值，隨著進程運行過程特性的改變修改優(yōu)先數(shù)。使其更為準(zhǔn)確。 優(yōu)點：能比較客觀地反映進程的實際情況和保證達到系統(tǒng)設(shè)計目標(biāo)。

33、如：對已占用較長時間CPU的進程，可降低其優(yōu)先級；對等待CPU時間較長的進程，可升高其優(yōu)先級,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,67,3.3 進程調(diào)度,例：設(shè)進程優(yōu)先數(shù)越小，其優(yōu)先級越高 進程 服務(wù)時間 優(yōu)先數(shù) 到達時刻 A 32 5 0 B 4 3 0 C 8 5 0 D 2 5 0 E 16 4 16 非剝奪靜態(tài)設(shè)置方式下運行情況： 時間： 14 36 52 60 62 執(zhí)行順序：B A E C D T=39.6 W=8.575,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,68,剝奪式動態(tài)設(shè)置方式下運行情況（設(shè)：每執(zhí)行10ms，優(yōu)先數(shù)+1；等待20ms，優(yōu)先數(shù)-1） 初始執(zhí)行時間：A32，B4，

34、C8，D2，E16,注：X*表示X完成，Xa表示X執(zhí)行的剩余時間為a,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,69,5. 多級反饋隊列調(diào)度算法 前面的算法多數(shù)需事先估計運行時間，較困難。 多級反饋隊列調(diào)度算法綜合了前面的算法，且不必估計運行時間。 它是一種可滿足各類進程需求的較好的算法。 算法思想：按不同作業(yè)的性質(zhì)和類型，將就緒隊列分為若干子隊列。各作業(yè)固定分屬一個隊列，不同隊列可采用不同的調(diào)度算法。,3.3 進程調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,70,3.3 進程調(diào)度,調(diào)度算法的實施過程： 1 設(shè)置多級就緒隊列； 2 各級就緒隊列具有不同大小的時間片； 3 一個新進程在系統(tǒng)隊列（最高優(yōu)先

35、級）； 4 按隊列優(yōu)先級從高到低進行進程調(diào)度； 5 一進程進入較高優(yōu)先級隊列時可能要重 新調(diào)度。 調(diào)度算法的特點：性能較好，能照顧到各種用戶利益,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,71,就緒隊列1,至CPU,S1,就緒隊列2,S2,至CPU,就緒隊列3,S3,至CPU,就緒隊列n,Sn,至CPU,時間片：s1s2s3sn,優(yōu)先級高,低,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,72,3.3 進程調(diào)度,調(diào)度算法： 1 設(shè)置多級就緒隊列；各隊列賦予不同的優(yōu)先級，第一個隊列優(yōu)先級最高； 2 各級就緒隊列具有不同大小的時間片；優(yōu)先級最高的隊列，時間片最短； 3 各隊列按FCFS排隊； 4 一個新進程插入一

36、級隊列； 5 按隊列優(yōu)先級從高到低進行進程調(diào)度；僅當(dāng)上級隊列空才調(diào)度下級隊列進程； 6 若進程在給定時間片未運行完畢，則降至下一級就緒隊列。 7 進程的執(zhí)行具有搶占性。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,73,3.3 進程調(diào)度,說明： I/O類進程及交互類進程優(yōu)先。一般設(shè)在一級隊列。該級隊列時間片的設(shè)置因盡量使多數(shù)I/O型進程產(chǎn)生一個I/O。以減少系統(tǒng)開銷； CPU型進程運行過程中要逐級下降； 因等待某事件進入阻塞隊列而又被喚醒的進程，一般插入到原隊列。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,74,實時調(diào)度是為了完成實時處理任務(wù)而分配計算機處理器的調(diào)度方法。 實時處理任務(wù)要求計算機在用戶允許的

37、時限范圍內(nèi)給出計算機的響應(yīng)信號。 實時處理任務(wù)可分為 硬實時任務(wù)（hard real-time task） 軟實時任務(wù)（soft real-time task）。 其中，前者要求計算機系統(tǒng)必須在用戶給定的時限內(nèi)完成，后者允許計算機系統(tǒng)在用戶給定的時限左右處理完畢。,3.4 實時調(diào)度算法,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,75,3.4 實時調(diào)度算法,一、對實時系統(tǒng)的要求： 1 提供必要的調(diào)度信息，如就緒時間、開始截止時間和完成截止時間、處理時間、資源要求、優(yōu)先級； 2 調(diào)度方式，廣泛采用搶占調(diào)度方式，特別是 在實時要求嚴(yán)格的實時系統(tǒng)； 3 具有快速響應(yīng)外部中斷的能力； 4 很快的任務(wù)分派能力和

38、進程和線程切換速度； 5 系統(tǒng)應(yīng)有很強的處理能力。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,76,3.4 實時調(diào)度算法,二、對幾種調(diào)度算法的評述： 1 時間片輪轉(zhuǎn)調(diào)度算法：這是一種常用于分時系統(tǒng)的調(diào)度算法，它只能適用于一般實時信息處理系統(tǒng)，而不能用于實時要求嚴(yán)格的實時控制系統(tǒng)?？色@得數(shù)秒至數(shù)十秒的響應(yīng)時間； 2 非搶占的優(yōu)先級調(diào)度算法：常用于多道批處理系統(tǒng)的調(diào)度算法，也可用于實時要求不太嚴(yán)格的實時控制系統(tǒng)?？色@得數(shù)秒至數(shù)百毫秒級的響應(yīng)時間； 3 基于時鐘中斷搶占的優(yōu)先級調(diào)度算法：用于大多數(shù)的實時系統(tǒng)中。調(diào)度延遲可降低為幾十毫秒至幾毫秒； 4 立即搶占的優(yōu)先級調(diào)度算法：這種算法適用于實時要求比較嚴(yán)格

39、的實時控制系統(tǒng)。調(diào)度延遲可降為幾十微秒。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,77,3.4 實時調(diào)度算法,三、代表性的實時調(diào)度算法： 1 時限式調(diào)度法(deadline scheduling)：是一種以滿足用戶要求時限為調(diào)度原則的算法。有周期性調(diào)度和非周期性調(diào)度。 時限包括：處理開始時限（開始截止時間）和處理結(jié)束時限（完成截止時間）兩種，在實際中可以使用任一種時限。 2 頻率單調(diào)調(diào)度(rate monotonic scheduling)：是一種被廣泛用于多周期性實時處理的調(diào)度算法。其基本原理是頻率越長（周期越長）的任務(wù)優(yōu)先級越低。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,78,四、實時調(diào)度算法實例

40、,1 最早截止時間優(yōu)先：在事前能知道各實時任務(wù)的開始截止時間，且對調(diào)度時延要求不太嚴(yán)格的情況下，可以采用此非剝奪性調(diào)度策略,1,3,4,2,1,2,3,4,開始截止時間,執(zhí)行任務(wù),任務(wù)到達,t,系統(tǒng)首先調(diào)度任務(wù)1執(zhí)行，在任務(wù)1執(zhí)行期間，任務(wù)2、3 先后到達，由于任務(wù)3的截止時間早于任務(wù)2的，故系統(tǒng)在 任務(wù)1后將調(diào)度任務(wù)3執(zhí)行。,1,3,4,2,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,79,3.4 實時調(diào)度算法,2 具有完成截止時間的周期性實時任務(wù)的調(diào)度 例：如果系統(tǒng)中有兩個周期性的實時任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms 任務(wù)B要求每50ms執(zhí)行一次，執(zhí)行時間為25ms。任

41、務(wù)A和B每次的開始截止時間分別為A1、A2、A3和B1、B2、B3見圖。 為了保證不遺漏任何一次截止時間，可采用最早截止時間優(yōu)先的剝奪策略。,2020/10/11,80,具有完成截止時間的周期性實時任務(wù)調(diào)度,A1(10) A2(30) A3(50) A4(70) A5(90) A6(110) A7(130) A8,0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160,t,0 10 30 40 45 55 70 80 90 100 110 130 140,A1 A2 A3 A4 A5 A6 A7,B1(20) B1(5) B2(15)

42、B2(10) B3(20),B1(25) B2(75) B3(125),開始截止時間,完成 A1 A2 A3 A4 A5 A6 A7 A8 截止 時間,0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160,t,B1 B2 B3,調(diào)度順序,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,81,什么是多處理機系統(tǒng) 多處理機操作系統(tǒng)的分類 多處理機系統(tǒng)調(diào)度策略,3.5 多處理機調(diào)度（自學(xué)）,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,82,多處理機系統(tǒng)：是一個具有兩個或多個處理機并能相互進行通信以協(xié)同一個大的給定問題求解的計算機系統(tǒng)。 特點： 1） 有兩個或多

43、個處理機 2） 共享主存或高速通信網(wǎng)絡(luò) 3） 共享輸入輸出子系統(tǒng) 4） 有單一完整的操作系統(tǒng) 5） 各級硬件和軟件相互作用,3.5.1.什么是多處理機系統(tǒng),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,83,主要功能： 進程分配 更好的利用多機硬件 資源在處理機之間的分配 改善程序的響應(yīng)時間 處理機的負(fù)載平衡 處理機間的協(xié)調(diào)和同步 因處理機故障引起的系統(tǒng)重組,3.5.1.什么是多處理機系統(tǒng),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,84,廣義上說，多處理機系統(tǒng)是：使用多處理機協(xié)調(diào)工作，來完成用戶所要求任務(wù)的計算機系統(tǒng)。它包括了 并行處理系統(tǒng)（parallel processing system），例如數(shù)據(jù)流機

44、(dataflow machine)和細(xì)胞陣列處理機(Celluar array processors)等 在物理上分散且通過不同的物理傳輸媒體傳輸數(shù)據(jù)的計算機網(wǎng)絡(luò)系統(tǒng)和計算機網(wǎng)絡(luò)為基礎(chǔ)的,對用戶透明的分布式系統(tǒng) 在同一的計算機系統(tǒng)里共享內(nèi)存的多處理機系統(tǒng). 廣義的多處理機計算機系統(tǒng)的一個共同的特點是有n個處理器(n1),能做到真正的并行處理,即能同時執(zhí)行n條指令.,3.5.1.什么是多處理機系統(tǒng),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,85,這里的多處理機操作系統(tǒng)是指：用來并行執(zhí)行用戶的幾個程序，以提高系統(tǒng)的吞吐率；或并行操作以提高系統(tǒng)可靠性的多處理操作系統(tǒng)。這種系統(tǒng)由共享公共內(nèi)存和外設(shè)的n(n

45、1)個 CPU組成。 概念上，在多處理機系統(tǒng)中的各進程的行為與在單機系統(tǒng)下的行為相同。 故對多處理機操作系統(tǒng)的要求與對多道程序的批處理系統(tǒng)沒有太多的區(qū)別。 但多處理機環(huán)境下，進程可在各處理機間進行透明遷移，由于進程上下文切換等帶來的系統(tǒng)開銷將使得多處理機操作系統(tǒng)的復(fù)雜度大大增加。 由于多處理機系統(tǒng)并行地執(zhí)行用戶的幾個程序（進程），這又帶來了多處理機條件下的并發(fā)執(zhí)行問題。,3.5.1.什么是多處理機系統(tǒng),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,86,使用多處理機系統(tǒng)的主要原因是 提高系統(tǒng)的可靠性； 在發(fā)生故障時能降級使用； 提高系統(tǒng)吞吐 。 故一個多處理機操作系統(tǒng)除了提高資源分配和管理，進程和處理機

46、管理，內(nèi)存和數(shù)據(jù)集保護以及文件系統(tǒng)等功能之外，還能提供系統(tǒng)結(jié)構(gòu)重組的能力，以支持系統(tǒng)的降級使用。 多處理機的調(diào)度策略也必須考慮到降級使用和結(jié)構(gòu)重組問題。,3.5.1.什么是多處理機系統(tǒng),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,87,多處理器系統(tǒng)的類型,(1) 緊密耦合(Tightly Coupted)MPS。 通常是通過高速總線或高速交叉開關(guān)，來實現(xiàn)多個處理器之間的互連的。 它們共享主存儲器系統(tǒng)和I/O設(shè)備，并要求將主存儲器劃分為若干個能獨立訪問的存儲器模塊，以便多個處理機能同時對主存進行訪問。 系統(tǒng)中的所有資源和進程，都由操作系統(tǒng)實施統(tǒng)一的控制和管理。,3.5.2多處理機操作系統(tǒng)的分類,2020

47、/10/11,數(shù)學(xué)科學(xué)學(xué)院,88,(2) 松散耦合(Loosely Coupled)MPS。 通常是通過通道或通信線路，來實現(xiàn)多臺計算機之間的互連。 每臺計算機都有自己的存儲器和I/O設(shè)備，并配置了OS來管理本地資源和在本地運行的進程。 故每一臺計算機都能獨立地工作， 必要時可通過通信線路與其它計算機交換信息，以及協(xié)調(diào)它們之間的工作。,3.5.2多處理機操作系統(tǒng)的分類,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,89,對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng),(1) 對稱多處理器系統(tǒng)SMPS(Symmetric MultiProcessor System) 在系統(tǒng)中所包含的各處理器單元，在功能和結(jié)構(gòu)上都是

48、相同的，當(dāng)前的絕大多數(shù)MPS都屬于SMP系統(tǒng)。例如，IBM公司的SR/6000 Model F50, 便是利用4片Power PC處理器構(gòu)成的。 (2) 非對稱多處理器系統(tǒng) 在系統(tǒng)中有多種類型的處理單元，它們的功能和結(jié)構(gòu)各不相同，其中只有一個主處理器，有多個從處理器。,3.5.2多處理機操作系統(tǒng)的分類,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,90,3.5.2多處理機操作系統(tǒng)的分類,多處理機操作系統(tǒng)可以分為三類： (1) 主從式（master-slave configuration） (2) 獨立監(jiān)控系統(tǒng)(Separate supervisor) (3) 移動式監(jiān)控系統(tǒng)(floating super

49、visor),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,91,(1)主從式（master-slave configuration） 主從式中，指定一臺特定的處理機為主處理機，由它負(fù)責(zé)對全系統(tǒng)的執(zhí)行進行控制. 在主從式操作系統(tǒng)中，主處理器上執(zhí)行操作系統(tǒng)程序，以控制其它從處理機的狀態(tài)，并為從處理機分配任務(wù)。 DEC system 10 ,Cyber 170 以及多處理機UNIX系統(tǒng)MPX都是主從式結(jié)構(gòu).,3.5.2多處理機操作系統(tǒng)的分類,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,92,3.5.2多處理機操作系統(tǒng)的分類,在主從式操作系統(tǒng)中,如果從處理機需要主處理機提供服務(wù)時,它們采用硬件中斷方式中斷處理機上執(zhí)行

50、的進程，以要求主處理機提供服務(wù). 這種結(jié)構(gòu)的操作系統(tǒng)一般重組功能較差,因為只有主處理機上執(zhí)行操作系統(tǒng)程序.如果主處理機失敗或發(fā)生不可恢復(fù)的錯誤時,整個系統(tǒng)將會癱瘓.,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,93,(2)獨立監(jiān)控系統(tǒng)(Separate supervisor) 獨立監(jiān)控系統(tǒng)的監(jiān)控程序在每個處理機上執(zhí)行, 每個處理機為自己的需要提供服務(wù)又互相通報執(zhí)行情況. 一般來說,每個監(jiān)控程序能重新裝入或在不同的處理機上復(fù)制獨立的副本. 獨立監(jiān)控系統(tǒng)不像主從結(jié)構(gòu)那樣易于崩潰,但其監(jiān)控程序在各處理機中的副本會占去大量的內(nèi)存.,3.5.2多處理機操作系統(tǒng)的分類,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,94,(

51、3)移動式監(jiān)控系統(tǒng)(floating supervisor) 移動式監(jiān)控系統(tǒng)：移動式監(jiān)控系統(tǒng)把監(jiān)控程序根據(jù)需要從一個處理機移到另一個處理機上.使所有資源有比較均衡的負(fù)載. 移動式監(jiān)控系統(tǒng)的處理機調(diào)度以及服務(wù)請求沖突等,大都采用優(yōu)先級的方式來解決. 所以 移動式監(jiān)控系統(tǒng)是一種效率最高,實現(xiàn)最難的多處理操作系統(tǒng).,3.5.2多處理機操作系統(tǒng)的分類,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,95,（1） 多處理機系統(tǒng)與單機調(diào)度的區(qū)別 多處理機調(diào)度與單機調(diào)度的主要區(qū)別涉及兩個資源分配問題： 存放程序或數(shù)據(jù)的存儲器分配及如何訪問他們 在多機系統(tǒng)中，由于各進程在物理上也同時執(zhí)行，而不是單機系統(tǒng)那樣的交叉執(zhí)行，這

52、些在物理上同時執(zhí)行的進程可能同時訪問物理存儲器的同一地址。 處理機對同一存儲塊的訪問必須是順序的。各進程同時訪問物理存儲器上的同一地址是不允許的。,3.5.3 多處理機系統(tǒng)調(diào)度策略,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,96,3.5.3 多處理機系統(tǒng)調(diào)度策略,將等待執(zhí)行的就緒進程分配到哪一個處理機上執(zhí)行 在單機系統(tǒng)中，由于只有一個處理機，在調(diào)度程序中選取了某個就緒狀態(tài)的進程之后，不須再選擇處理機。 而在多機系統(tǒng)中，為了盡量做到讓各處理機負(fù)荷平衡，可能會將處理機在進程之間進行多次切換。 如果被切換進程正在執(zhí)行其臨界區(qū)部分或系統(tǒng)中進程數(shù)目相當(dāng)多，這種頻繁的上下文轉(zhuǎn)換將會使系統(tǒng)效率大大下降。,2020

53、/10/11,數(shù)學(xué)科學(xué)學(xué)院,97,3.5.3 多處理機系統(tǒng)調(diào)度策略,為解決進程對處理機的分配問題，有些多處理機系統(tǒng)中采用了局部就緒隊列的方法限制進程的轉(zhuǎn)移。 局部就緒對列：把處于就緒狀態(tài)的進程分成不同的組，并使每一組進程和一個處理機對應(yīng)起來。 這樣，每個處理機只執(zhí)行與其對應(yīng)就緒隊列中的進程。各個就緒隊列中的進程不斷發(fā)生橫向轉(zhuǎn)移。這種方法減少了調(diào)度程序的開銷。但處理機的使用率卻因此下降。 如：系統(tǒng)中某個局部就緒隊列中因等待進程較多，使得對應(yīng)的處理機十分繁忙，而另外的處理機則因就緒隊列為空而處于空閑狀態(tài)。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,98,多處理機系統(tǒng)的調(diào)度目標(biāo)是： 以最高的可靠性，使用最

54、少的處理機在最短的時間內(nèi)完成最多的可以并行完成的進程。,3.5.3 多處理機系統(tǒng)調(diào)度策略,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,99,3.5.3 多處理機系統(tǒng)調(diào)度策略,（2）多處理機的調(diào)度評價 多處理機的調(diào)度有兩種評價模型： 一種是確定性模型，另一種是隨機性模性。 確定性模型：進程調(diào)度執(zhí)行之前，估計出這些被調(diào)度進程所需要的執(zhí)行時間，及這些進程之間的相互關(guān)系。 調(diào)度程序的目的：是根據(jù)給定的執(zhí)行時間和相互關(guān)系，確定出一個最佳的執(zhí)行順序。 故確定性模型只用來確定給定進程的執(zhí)行順序，而隨機性模性則常被用來研究動態(tài)調(diào)度技術(shù)。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,100,3.5.3 多處理機系統(tǒng)調(diào)度策略,（

55、3）多處理機系統(tǒng)調(diào)度方式 （自學(xué)） 自調(diào)度方式 成組調(diào)度方式 專用處理機分配方式,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,101,對稱多處理器系統(tǒng)中的進程分配方式 在SMP系統(tǒng)中，所有的處理器都是相同的，因而可把所有的處理器作為一個處理器池(Processor pool)，由調(diào)度程序或基于處理器的請求，將任何一個進程分配給池中的任何一個處理器去處理。在進行進程分配時，可采用以下兩種方式之一。 1) 靜態(tài)分配(Static Assigenment)方式 2) 動態(tài)分配(Dynamic Assgement)方式,3.5.3 多處理機系統(tǒng)調(diào)度策略,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,102,非對稱MPS中的進程分配方式 對于非對稱MPS，其OS大多采用主從(Master-Slave)式OS，即OS的核心部分駐留在一臺主機上(Master)，從機(Slave)上只是用戶程序，進程調(diào)度只由主機執(zhí)行 每當(dāng)從機空閑時，便向主機發(fā)送一索求進程的信號，然后等待主