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

1、第三章,處理機(jī)調(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)度主要討論處理機(jī)分配問題,在多道單處理機(jī)系統(tǒng)環(huán)境下，內(nèi)存就緒隊(duì)列往往有多個(gè)進(jìn)程等待處理機(jī)，而分配處理機(jī)的任務(wù)通常是由調(diào)度程序完成的。 由于處理機(jī)是計(jì)算機(jī)系統(tǒng)中最重要的資源，故提高處理機(jī)的利用率、改善系統(tǒng)性能很大程度取決于處理機(jī)調(diào)度性能的優(yōu)劣。 處理機(jī)調(diào)度的主要目標(biāo) 對CPU資源進(jìn)行合理的分配使用，以提高CPU利用率 使各用戶公平地得到處理機(jī)資源 減少用戶的響應(yīng)時(shí)間。 處理機(jī)調(diào)度管理問題是操作系統(tǒng)設(shè)計(jì)的

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

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

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

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

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

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

8、度算法和資源利用情況； 何時(shí)調(diào)入作業(yè)進(jìn)入內(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è)隊(duì)列中選擇作業(yè)進(jìn)入系統(tǒng)內(nèi)存的原則。 調(diào)度原則 應(yīng)與系統(tǒng)的整體設(shè)計(jì)目標(biāo)一致，盡量提高系統(tǒng)的吞吐量 均衡利用系統(tǒng)中各種資源，考慮負(fù)載均勻 對所有作業(yè)應(yīng)該公平合理，保證各類作業(yè)的執(zhí)行 對優(yōu)先級較高的作業(yè)優(yōu)先調(diào)度 應(yīng)有較快的響應(yīng)時(shí)間,3.作業(yè)調(diào)度原則與性能衡量,3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,19, 性能衡量 通常采用平均周轉(zhuǎn)時(shí)間和帶權(quán)平均周轉(zhuǎn)時(shí)間 周轉(zhuǎn)時(shí)間T

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

10、22,3.2 作業(yè)調(diào)度,響應(yīng)時(shí)間：從提交一個(gè)請求到首次產(chǎn)生響應(yīng) CPU、I/O執(zhí)行期：分CPU忙和I/O忙 截止時(shí)間：某任務(wù)必須開始執(zhí)行（或必須完成）的最遲時(shí)間（開始截止、完成截止）。它是評價(jià)實(shí)時(shí)系統(tǒng)性能的重要指標(biāo)。 優(yōu)先權(quán),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,23,（1）先來先服務(wù)（FCFS）調(diào)度算法 既適合作業(yè)調(diào)度，也適合進(jìn)程調(diào)度。 將用戶作業(yè)（/就緒進(jìn)程）按提交順序（/變?yōu)榫途w狀態(tài)）的先后排成隊(duì)列，并按照先來先服務(wù)的方式進(jìn)行調(diào)度處理。它是一種最普遍和最簡單的方法。 優(yōu)先考慮在系統(tǒng)中等待時(shí)間最長的作業(yè)（進(jìn)程），而不管要求運(yùn)行時(shí)間的長短。, 作業(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)度算法的特點(diǎn)： 實(shí)現(xiàn)簡單； 效率較低； 有利于運(yùn)行時(shí)間長的作業(yè)（進(jìn)程），不利于短作業(yè)（進(jìn)程）； 有利于CPU繁忙型的作業(yè)（進(jìn)程），不利于I/O繁忙型的作業(yè)（進(jìn)程）。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,26,（2）短作業(yè)（進(jìn)程）優(yōu)先法（SJF/SPF）,既適合作業(yè)調(diào)度，也適合進(jìn)程調(diào)度 短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法：考慮作業(yè)（進(jìn)程）的運(yùn)行時(shí)間，每次總是選擇一個(gè)運(yùn)行時(shí)間最短的作業(yè)（進(jìn)程）執(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ǎn)：調(diào)度性能較好。 SJF/SPF缺點(diǎn)： 1）不利于長作業(yè)（進(jìn)程）。 2）不考慮作業(yè)（進(jìn)程）的緊迫程度。 3）估計(jì)的運(yùn)行時(shí)間很難準(zhǔn)確獲得。 4）如果作業(yè)的到來順序及運(yùn)行時(shí)間不合適，可能會出現(xiàn)饑餓現(xiàn)象。 例如，系統(tǒng)中有一個(gè)運(yùn)行時(shí)間很長的作業(yè)JN，和幾個(gè)運(yùn)行時(shí)間短的作業(yè)，若系統(tǒng)不斷地有運(yùn)行時(shí)間小于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è)的等待時(shí)間，而忽視了作業(yè)的運(yùn)行時(shí)間； 短作業(yè)優(yōu)先算法則相反，只考慮了作業(yè)運(yùn)行時(shí)間，而忽視了作業(yè)等待時(shí)間。 響應(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)時(shí)間與作業(yè)要 求運(yùn)行時(shí)間的比值 R 響應(yīng)時(shí)間 / 要求運(yùn)行時(shí)間 (作業(yè)

14、等待時(shí)間需運(yùn)行時(shí)間)/需運(yùn)行時(shí)間 1已等待時(shí)間 / 需運(yùn)行時(shí)間 1W/T,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,33,響應(yīng)比R不僅是要求運(yùn)行時(shí)間的函數(shù)，而且還是等待時(shí)間的函數(shù)。 由于R與要求運(yùn)行時(shí)間成反比，故對短作業(yè)是有利的； 又因R與等待時(shí)間成正比，故長作業(yè)隨著其等待時(shí)間的增長，也可獲的較高的相應(yīng)比。 該算法既照顧了先來者，又優(yōu)待了短作業(yè)，是上述兩種算法的一種較好的折衷。,3.2 作業(yè)調(diào)度,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,34,作業(yè) 提交時(shí)刻 運(yùn)行時(shí)間 開始時(shí)刻 完成時(shí)刻 周轉(zhuǎn)時(shí)間 帶權(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)時(shí)間1.625h 帶權(quán)周轉(zhuǎn)時(shí)間 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、時(shí)間按分鐘計(jì)算,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,36,3.2 作業(yè)調(diào)度,該算法從理論上講是比較完備的，但 作業(yè)調(diào)度程序要統(tǒng)計(jì)作業(yè)的等待時(shí)間，使用用戶需估計(jì)的運(yùn)行時(shí)間，不實(shí)際； 每次調(diào)度要做浮點(diǎn)運(yùn)算（這是系統(tǒng)程序最忌諱的）浪費(fèi)大量的計(jì)算時(shí)間，是系統(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è)等待時(shí)間、運(yùn)行時(shí)間、緩急程度，系統(tǒng)資源使用等），給每個(gè)作業(yè)設(shè)置一個(gè)優(yōu)先數(shù) 調(diào)度程序總是選擇一個(gè)優(yōu)先級最高（即優(yōu)先數(shù)最大或者最小）的作業(yè)調(diào)入（系統(tǒng)）內(nèi)存。 這種算法實(shí)現(xiàn)的困難在于如何綜合考慮，這些因素之間的關(guān)系

17、怎樣處理。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,38,3.3 進(jìn)程調(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)為了便于對進(jìn)程的管理，將系統(tǒng)中的所有進(jìn)程按其狀態(tài)組織成不同的進(jìn)程隊(duì)列。,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,39,3.3 進(jìn)程調(diào)度,進(jìn)程調(diào)度的相關(guān)工作： 1.記錄和保持系統(tǒng)中所有進(jìn)程的有關(guān)情況和狀態(tài)特征 有關(guān)進(jìn)程調(diào)度的信息是記錄在PCB中的，在進(jìn)程調(diào)度中主要用到的是進(jìn)程的狀態(tài)、調(diào)度優(yōu)先級（優(yōu)先數(shù)）、就緒的進(jìn)程隊(duì)列等。 2.決定分配（處理機(jī)）策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

32、精確。 因?yàn)檫M(jìn)程的優(yōu)先數(shù)在它執(zhí)行前就已算好，且在整個(gè)執(zhí)行期間都保持不變，但隨著進(jìn)程的推進(jìn)，計(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)度性能，這對分時(shí)系統(tǒng)顯得格外重要.,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,66,3.3 進(jìn)程調(diào)度,動態(tài)進(jìn)程優(yōu)先數(shù)： 在運(yùn)行的過程中，根據(jù)系統(tǒng)的設(shè)計(jì)目標(biāo)，不斷地調(diào)整進(jìn)程的優(yōu)先數(shù)。 在進(jìn)程創(chuàng)建時(shí)，先賦一初值，隨著進(jìn)程運(yùn)行過程特性的改變修改優(yōu)先數(shù)。使其更為準(zhǔn)確。 優(yōu)點(diǎn)：能比較客觀地反映進(jìn)程的實(shí)際情況和保證達(dá)到系統(tǒng)設(shè)計(jì)目標(biāo)。

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

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

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

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

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

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

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

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

41、務(wù)A和B每次的開始截止時(shí)間分別為A1、A2、A3和B1、B2、B3見圖。 為了保證不遺漏任何一次截止時(shí)間，可采用最早截止時(shí)間優(yōu)先的剝奪策略。,2020/10/11,80,具有完成截止時(shí)間的周期性實(shí)時(shí)任務(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),開始截止時(shí)間,完成 A1 A2 A3 A4 A5 A6 A7 A8 截止 時(shí)間,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,什么是多處理機(jī)系統(tǒng) 多處理機(jī)操作系統(tǒng)的分類 多處理機(jī)系統(tǒng)調(diào)度策略,3.5 多處理機(jī)調(diào)度（自學(xué)）,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,82,多處理機(jī)系統(tǒng)：是一個(gè)具有兩個(gè)或多個(gè)處理機(jī)并能相互進(jìn)行通信以協(xié)同一個(gè)大的給定問題求解的計(jì)算機(jī)系統(tǒng)。 特點(diǎn)： 1） 有兩個(gè)或多

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

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

45、1)個(gè) CPU組成。 概念上，在多處理機(jī)系統(tǒng)中的各進(jìn)程的行為與在單機(jī)系統(tǒng)下的行為相同。 故對多處理機(jī)操作系統(tǒng)的要求與對多道程序的批處理系統(tǒng)沒有太多的區(qū)別。 但多處理機(jī)環(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.5.1.什么是多處理機(jī)系統(tǒng),2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,86,使用多處理機(jī)系統(tǒng)的主要原因是 提高系統(tǒng)的可靠性； 在發(fā)生故障時(shí)能降級使用； 提高系統(tǒng)吞吐 。 故一個(gè)多處理機(jī)操作系統(tǒng)除了提高資源分配和管理，進(jìn)程和處理機(jī)

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

47、/10/11,數(shù)學(xué)科學(xué)學(xué)院,88,(2) 松散耦合(Loosely Coupled)MPS。 通常是通過通道或通信線路，來實(shí)現(xiàn)多臺計(jì)算機(jī)之間的互連。 每臺計(jì)算機(jī)都有自己的存儲器和I/O設(shè)備，并配置了OS來管理本地資源和在本地運(yùn)行的進(jìn)程。 故每一臺計(jì)算機(jī)都能獨(dú)立地工作， 必要時(shí)可通過通信線路與其它計(jì)算機(jī)交換信息，以及協(xié)調(diào)它們之間的工作。,3.5.2多處理機(jī)操作系統(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)各不相同，其中只有一個(gè)主處理器，有多個(gè)從處理器。,3.5.2多處理機(jī)操作系統(tǒng)的分類,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,90,3.5.2多處理機(jī)操作系統(tǒng)的分類,多處理機(jī)操作系統(tǒng)可以分為三類： (1) 主從式（master-slave configuration） (2) 獨(dú)立監(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） 主從式中，指定一臺特定的處理機(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)MPX都是主從式結(jié)構(gòu).,3.5.2多處理機(jī)操作系統(tǒng)的分類,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,92,3.5.2多處理機(jī)操作系統(tǒng)的分類,在主從式操作系統(tǒng)中,如果從處理機(jī)需要主處理機(jī)提供服務(wù)時(shí),它們采用硬件中斷方式中斷處理機(jī)上執(zhí)行

50、的進(jìn)程，以要求主處理機(jī)提供服務(wù). 這種結(jié)構(gòu)的操作系統(tǒng)一般重組功能較差,因?yàn)橹挥兄魈幚頇C(jī)上執(zhí)行操作系統(tǒng)程序.如果主處理機(jī)失敗或發(fā)生不可恢復(fù)的錯誤時(shí),整個(gè)系統(tǒng)將會癱瘓.,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,93,(2)獨(dú)立監(jiān)控系統(tǒng)(Separate supervisor) 獨(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ī)中的副本會占去大量的內(nèi)存.,3.5.2多處理機(jī)操作系統(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ù)需要從一個(gè)處理機(jī)移到另一個(gè)處理機(jī)上.使所有資源有比較均衡的負(fù)載. 移動式監(jiān)控系統(tǒng)的處理機(jī)調(diào)度以及服務(wù)請求沖突等,大都采用優(yōu)先級的方式來解決. 所以 移動式監(jiān)控系統(tǒng)是一種效率最高,實(shí)現(xiàn)最難的多處理操作系統(tǒng).,3.5.2多處理機(jī)操作系統(tǒng)的分類,2020/10/11,數(shù)學(xué)科學(xué)學(xué)院,95,（1） 多處理機(jī)系統(tǒng)與單機(jī)調(diào)度的區(qū)別 多處理機(jī)調(diào)度與單機(jī)調(diào)度的主要區(qū)別涉及兩個(gè)資源分配問題： 存放程序或數(shù)據(jù)的存儲器分配及如何訪問他們 在多機(jī)系統(tǒng)中，由于各進(jìn)程在物理上也同時(shí)執(zhí)行，而不是單機(jī)系統(tǒng)那樣的交叉執(zhí)行，這

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

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

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

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