處理機調度與死鎖

1、跳轉到第一頁操作系統(tǒng)的性能在很大程度上操作系統(tǒng)的性能在很大程度上取決于處理機調度性能的好壞，因取決于處理機調度性能的好壞，因而，處理機調度便成為操作系統(tǒng)設而，處理機調度便成為操作系統(tǒng)設計的中心問題之一。計的中心問題之一。第四章第四章 處理機調度與死鎖處理機調度與死鎖跳轉到第一頁提高處理機的利用率及改善系統(tǒng)性提高處理機的利用率及改善系統(tǒng)性能（吞吐量、響應時間）是處理機調度能（吞吐量、響應時間）是處理機調度的主要目標。的主要目標。在多道程序環(huán)境下，進程數(shù)目往往在多道程序環(huán)境下，進程數(shù)目往往多于處理機數(shù)目。這就要求系統(tǒng)能按照多于處理機數(shù)目。這就要求系統(tǒng)能按照某種算法，動態(tài)地把處理機分配給就緒某種算法

2、，動態(tài)地把處理機分配給就緒隊列中的一個進程，使之執(zhí)行。隊列中的一個進程，使之執(zhí)行。本章主要講述各種常用調度算法及本章主要講述各種常用調度算法及評價；介紹死鎖及其解決的辦法。評價；介紹死鎖及其解決的辦法。跳轉到第一頁4.1調度的基本概念調度的基本概念4.2調度算法調度算法4.3實時調度算法實時調度算法4.4多處理機調度多處理機調度本章主要內容4.5死鎖死鎖4.6 解決死鎖問題的方法解決死鎖問題的方法跳轉到第一頁4.1.1 作業(yè)的狀態(tài)及概念作業(yè)的狀態(tài)及概念1.1.作業(yè)：在一次應用業(yè)務處理過程中，從輸入開始到輸出結作業(yè)：在一次應用業(yè)務處理過程中，從輸入開始到輸出結束，用戶要求計算機所做的有關該次業(yè)務

3、處理的全部工作為束，用戶要求計算機所做的有關該次業(yè)務處理的全部工作為一個作業(yè)。一個作業(yè)。如：用語言編制一個程序，系統(tǒng)完成如下工作：如：用語言編制一個程序，系統(tǒng)完成如下工作：編輯編輯 編編譯譯 鏈接鏈接 執(zhí)行執(zhí)行以上幾個步驟總和就是一個作業(yè)。以上幾個步驟總和就是一個作業(yè)。3.3.作業(yè)的組成：由程序、數(shù)據(jù)和作業(yè)說明書組成。作業(yè)的組成：由程序、數(shù)據(jù)和作業(yè)說明書組成。 微機中：微機中：批處理文件或批處理文件或SHELLSHELL程序方式編寫作業(yè)說明程序方式編寫作業(yè)說明書。書。 2.2.作業(yè)步：作業(yè)步是在一個作業(yè)的處理過程中，計算機相對獨作業(yè)步：作業(yè)步是在一個作業(yè)的處理過程中，計算機相對獨立的工作。立的

4、工作。 4.1 調度的基本概念調度的基本概念跳轉到第一頁 作業(yè)說明書的主要內容作業(yè)基本情況描述 作業(yè)控制描述 作業(yè)資源要求描述 要求處理時間用戶名作業(yè)名使用語言名允許最大處理時間控制方式操作順序出錯處理等等內存空間外設類型和數(shù)量處理機優(yōu)先級庫函數(shù)或實用程序跳轉到第一頁4.4.作業(yè)的狀態(tài)及其轉換作業(yè)的狀態(tài)及其轉換不同的階段對應不同的狀態(tài)：不同的階段對應不同的狀態(tài)：后備狀態(tài)執(zhí)行狀態(tài)完成狀態(tài)后備狀態(tài)執(zhí)行狀態(tài)完成狀態(tài)等待等待就緒就緒后備后備狀態(tài)狀態(tài)等待等待就緒就緒執(zhí)行執(zhí)行交換調度交換調度進程調度進程調度作業(yè)調度作業(yè)調度完成完成狀態(tài)狀態(tài)線程調度線程調度內存內存外存外存跳轉到第一頁4.1.2分級調度分級調

5、度4.1.3 進程調度的功能和時機進程調度的功能和時機4.1.4 調度原則與性能衡量調度原則與性能衡量周轉時間：周轉時間： irwisieiiTTTTTniinTT11平均周轉時間：平均周轉時間： )/(11irniiiinTTWWW平均帶權周轉時間：平均帶權周轉時間： 作業(yè)調度、中級調度、進程調度作業(yè)調度、中級調度、進程調度 、線程調度、線程調度CPUCPU周期；調度方式周期；調度方式：剝奪方式和非剝奪方式：剝奪方式和非剝奪方式公平、有效、高吞吐量、及時響應、支持優(yōu)先公平、有效、高吞吐量、及時響應、支持優(yōu)先響應時間、截止時間響應時間、截止時間跳轉到第一頁4.2調度算法調度算法4.2.1 先來

6、先服務先來先服務FCFS( First-come-First-Serverd)作業(yè)號作業(yè)號到達時刻到達時刻運行時間運行時間開始時間開始時間完成時間完成時間周轉時間周轉時間帶權周轉時間帶權周轉時間10100101012151015142.8351151611114102161884平均周轉時間平均周轉時間T10.75(ms)；平均帶權周轉時間；平均帶權周轉時間W4.7(ms)。優(yōu)點：實現(xiàn)簡單，有利于長作業(yè)和優(yōu)點：實現(xiàn)簡單，有利于長作業(yè)和CPUCPU繁忙的進程繁忙的進程缺點：使短作業(yè)等待長作業(yè)，重要的作業(yè)等待可能不是很重要的長作業(yè)，缺點：使短作業(yè)等待長作業(yè)，重要的作業(yè)等待可能不是很重要的長作業(yè)，不

7、能用于分時和實時系統(tǒng)。不能用于分時和實時系統(tǒng)。跳轉到第一頁4.2.2 短作業(yè)優(yōu)先短作業(yè)優(yōu)先SF(Shortest-job/Process First) 作業(yè)號作業(yè)號到達時刻到達時刻運行時間運行時間開始時間開始時間完成時間完成時間周轉時間周轉時間帶權周轉時間帶權周轉時間10100101012151318173.43511011664102111331.5平均周轉時間平均周轉時間T9(ms)；平均帶權周轉時間；平均帶權周轉時間W2.975(ms)。優(yōu)點：有利于短作業(yè)或短進程。降低了作業(yè)的平均等待時間，提高了優(yōu)點：有利于短作業(yè)或短進程。降低了作業(yè)的平均等待時間，提高了系統(tǒng)的吞吐量。系統(tǒng)的吞吐量。缺點

8、：用戶可能有意或無意地縮短作業(yè)的估計執(zhí)行時間，致使該算法缺點：用戶可能有意或無意地縮短作業(yè)的估計執(zhí)行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先；不一定能真正做到短作業(yè)優(yōu)先； 跳轉到第一頁4.2.3 最高響應比優(yōu)先最高響應比優(yōu)先HRN(Hight-Response-Next)R響應時間響應時間/需運行的時間需運行的時間1已等待的時間已等待的時間/需運行的時間需運行的時間 作業(yè)號作業(yè)號到達時刻到達時刻運行時間運行時間開始時間開始時間完成時間完成時間周轉時間周轉時間帶權周轉時間帶權周轉時間101001010121511161533511011664102161884平均周轉時間平均周轉時間T9.75

9、(ms)；平均帶權周轉時間；平均帶權周轉時間W3.5（ms）。）。優(yōu)點：優(yōu)點：HRNHRN既照顧了短作業(yè)，也考慮了長作業(yè)；既照顧了短作業(yè)，也考慮了長作業(yè)；缺點：每次進行調度前，都要進行響應比計算，會增加系統(tǒng)的開銷；不能缺點：每次進行調度前，都要進行響應比計算，會增加系統(tǒng)的開銷；不能滿足緊迫作業(yè)或進程的需要。滿足緊迫作業(yè)或進程的需要。跳轉到第一頁4.2.4 優(yōu)先權優(yōu)先優(yōu)先權優(yōu)先HPF(Highest-Priority-First)進程進程到達時刻到達時刻CPU周期周期(ms)優(yōu)先數(shù)優(yōu)先數(shù)p10224P2082P3045P418103T23.5(ms)W3(ms)T26(ms)W3.89(ms)優(yōu)

10、點：可以使緊迫的任務得到優(yōu)先執(zhí)行。優(yōu)點：可以使緊迫的任務得到優(yōu)先執(zhí)行。缺點：靜態(tài)優(yōu)先級易于實現(xiàn)，系統(tǒng)開銷小，但作業(yè)或進程的優(yōu)先級缺點：靜態(tài)優(yōu)先級易于實現(xiàn)，系統(tǒng)開銷小，但作業(yè)或進程的優(yōu)先級不夠精確；動態(tài)優(yōu)先級須計算優(yōu)先級，增加系統(tǒng)的開銷。不夠精確；動態(tài)優(yōu)先級須計算優(yōu)先級，增加系統(tǒng)的開銷。跳轉到第一頁4.2.5 輪轉法輪轉法RR(Round Robin)4.2.6 多級反饋隊列算法多級反饋隊列算法MF(Multiple Feedback)q=R/Nmax優(yōu)點：可以使用戶得到及時的響應和服務。優(yōu)點：可以使用戶得到及時的響應和服務。缺點：短進程用戶和缺點：短進程用戶和I/OI/O繁忙型進程是不利的。特

11、別是，當繁忙型進程是不利的。特別是，當“緊迫型緊迫型”的進程到來時，并不能及時的得到處理。的進程到來時，并不能及時的得到處理。就緒隊列1就緒隊列iCPU就緒隊列nMFMF算法可以較好地協(xié)調長進程和短進程的執(zhí)行。算法可以較好地協(xié)調長進程和短進程的執(zhí)行。跳轉到第一頁4.3實時調度算法實時調度算法 4.3.1 實時系統(tǒng)的特點實時系統(tǒng)的特點計算結果的正確性、時限、周期與非周期任務；計算結果的正確性、時限、周期與非周期任務；快速的切換機制與搶占式的調度策略?？焖俚那袚Q機制與搶占式的調度策略。4.3.2 實時系統(tǒng)常用調度算法實時系統(tǒng)常用調度算法 1 1頻率單調調度頻率單調調度RMSRMS（Rate-Mon

12、otontic SchedulingRate-Monotontic Scheduling）算法）算法 2 2最早截止優(yōu)先最早截止優(yōu)先EDFEDF（Earliest-Deadline-FirstEarliest-Deadline-First）算法）算法 3 3最低松馳度優(yōu)先最低松馳度優(yōu)先LLFLLF（Least-laxity-FirstLeast-laxity-First）算法）算法 跳轉到第一頁4.4多處理機調度多處理機調度4.4.1 多處理機系統(tǒng)的類型多處理機系統(tǒng)的類型 4.4.2 多處理機系統(tǒng)調度方式多處理機系統(tǒng)調度方式1 1緊密耦合緊密耦合MPSMPS和松弛耦合和松弛耦合MPSMPS2

13、2對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng)對稱多處理器系統(tǒng)和非對稱多處理器系統(tǒng)1. 1. 非對稱多處理機系統(tǒng)調度方式非對稱多處理機系統(tǒng)調度方式2 2對稱多處理機系統(tǒng)調度方式對稱多處理機系統(tǒng)調度方式自調度和組調度自調度和組調度跳轉到第一頁4.5.1 死鎖的產生死鎖的產生1 1什么是死鎖什么是死鎖 R1R2P1P22 2產生死鎖的原因產生死鎖的原因: :系統(tǒng)資源不足，進程推進順序不恰當系統(tǒng)資源不足，進程推進順序不恰當4.5死鎖死鎖 死鎖死鎖是指一組并發(fā)進程彼此互相等待對方所擁有的資源，是指一組并發(fā)進程彼此互相等待對方所擁有的資源，且這些并發(fā)進程在得到對方的資源之前不會釋放自己所擁有的且這些并發(fā)進程在得

14、到對方的資源之前不會釋放自己所擁有的資源，從而使并發(fā)進程不能繼續(xù)向前推進的狀態(tài)。陷入死鎖狀資源，從而使并發(fā)進程不能繼續(xù)向前推進的狀態(tài)。陷入死鎖狀態(tài)的進程稱之為死鎖進程。態(tài)的進程稱之為死鎖進程。跳轉到第一頁4.5.2 死鎖的必要條件死鎖的必要條件（1 1）互斥條件。指進程竟爭的資源具有互斥性，即在一段時間）互斥條件。指進程竟爭的資源具有互斥性，即在一段時間內某資源被一個進程占用，如果此時還有其它進程請求使用該內某資源被一個進程占用，如果此時還有其它進程請求使用該資源，則只能等待，直到占用該資源的進程用完后主動釋放。資源，則只能等待，直到占用該資源的進程用完后主動釋放。（2 2）不可剝奪條件（不可

15、搶占條件）。指已分配給某一進程的）不可剝奪條件（不可搶占條件）。指已分配給某一進程的資源，在它未使用完之前，不能強行剝奪，只能在使用完后，資源，在它未使用完之前，不能強行剝奪，只能在使用完后，由進程自己釋放。由進程自己釋放。（3 3）部分分配條件（請求與保持條件）。指進程已經占用了一）部分分配條件（請求與保持條件）。指進程已經占用了一部分資源，但又提出新的資源請求，而該資源又被其它的進程部分資源，但又提出新的資源請求，而該資源又被其它的進程所占用，此時請求進程只能阻塞，但又對自己占用的資源保持所占用，此時請求進程只能阻塞，但又對自己占用的資源保持不放。不放。（4 4）環(huán)路條件（循環(huán)等待條件）。

16、指進程發(fā)生死鎖時，必然存）環(huán)路條件（循環(huán)等待條件）。指進程發(fā)生死鎖時，必然存在一個進程資源的環(huán)形鏈。即一組進程在一個進程資源的環(huán)形鏈。即一組進程P1P1，P2P2，PnPn，其，其中，中，P1P1正在等待正在等待P2P2占用的資源；占用的資源；P2P2正在等待正在等待P3P3占用的資源，占用的資源，PnPn正在等待正在等待P1P1占用的資源。圖占用的資源。圖4 47 7所示為兩個進程竟爭所示為兩個進程竟爭兩個資源的環(huán)形鏈圖。兩個資源的環(huán)形鏈圖。跳轉到第一頁4.6.1 死鎖的預防死鎖的預防1 1防止防止“部分分配部分分配”條件的出現(xiàn)條件的出現(xiàn)2 2防止防止“環(huán)路等待環(huán)路等待”條件的出現(xiàn)條件的出現(xiàn)

17、4.6.2 死鎖的避免死鎖的避免1 1安全狀態(tài)安全狀態(tài)T T存在安全序列（存在安全序列（p2p2，p1p1，p3p3），系統(tǒng)處于安全狀），系統(tǒng)處于安全狀態(tài)。態(tài)。此時，系統(tǒng)進入不安全狀態(tài)。此時，系統(tǒng)進入不安全狀態(tài)。 4.6解決死鎖的方法解決死鎖的方法跳轉到第一頁2 2銀行家算法銀行家算法（1 1）數(shù)據(jù)結構）數(shù)據(jù)結構 銀行家算法中用到下列數(shù)據(jù)結構，令銀行家算法中用到下列數(shù)據(jù)結構，令n n是系統(tǒng)中的進程數(shù)，是系統(tǒng)中的進程數(shù)，m m是資源類數(shù)。是資源類數(shù)。 可用資源向量可用資源向量A A（AvailableAvailable）。向量）。向量A A的長度為的長度為m m，向量元素，向量元素Aj(j=1A

18、j(j=1，2 2，m)m)為系統(tǒng)中資源類為系統(tǒng)中資源類r rj j的當前可用數(shù)。的當前可用數(shù)。 最大需求矩陣最大需求矩陣M M（MaxMax）。）。M M是一個是一個n nm m的矩陣，矩陣元素的矩陣，矩陣元素Mi,jMi,j為進為進程程p pi i關于資源類關于資源類r rj j的最大需求數(shù)，每個進程必須預先申報。的最大需求數(shù)，每個進程必須預先申報。 資源占用矩陣資源占用矩陣U U（UseUse）。）。U U是一個是一個n nm m的矩陣，矩陣元素的矩陣，矩陣元素Ui,jUi,j為進為進程程p pi i關于資源類關于資源類r rj j的當前占用數(shù)。的當前占用數(shù)。 剩余需求矩陣剩余需求矩陣N

19、 N（NeedNeed）。）。N N是一個是一個n nm m的矩陣，矩陣元素的矩陣，矩陣元素NIi,jNIi,j是是進程進程p pi i還需要的資源類還需要的資源類r rj j的單位數(shù)。顯然有，的單位數(shù)。顯然有，NIi,jNIi,jMi,jMi,jUi,jUi,j。 （2 2）簡記法）簡記法 為了簡化對算法的描述，對上述數(shù)據(jù)結構采用如下的簡記法為了簡化對算法的描述，對上述數(shù)據(jù)結構采用如下的簡記法 令令X X和和Y Y為長度是為長度是m m的向量，若的向量，若XYXY，當且僅當對任意的，當且僅當對任意的i i（i i1 1，2 2，m m）有）有XiYiXiYi。 對于對于n nm m的矩陣的矩

20、陣Z Zn nm m，Z Zi i（i i1 1，2 2，n n）表示矩陣）表示矩陣Z Zn nm m的第的第i i個行個行向量。向量。跳轉到第一頁（3 3）算法描述）算法描述 令令RRRRi i是長度為是長度為m m的進程的進程p pi i的資源請求向量，元素的資源請求向量，元素RRi,jRRi,j是進程是進程p pi i希望請求分配的資源類希望請求分配的資源類r rj j的單位數(shù)。當進程的單位數(shù)。當進程p pi i向系統(tǒng)提交一個資源請求向系統(tǒng)提交一個資源請求向量向量RRRRi i時，系統(tǒng)調用銀行家算法執(zhí)行下述工作：時，系統(tǒng)調用銀行家算法執(zhí)行下述工作： 若若RRRRi i NNi i，則有（

21、，則有（RRiRRiU Ui i）M Mi i，即進程，即進程p pi i請求的資源單位數(shù)大請求的資源單位數(shù)大于它申請的最大需求數(shù)，故請求無效，作出錯處理；否則進行下一步。于它申請的最大需求數(shù)，故請求無效，作出錯處理；否則進行下一步。 若若RRRRi i A A，則進程，則進程p pi i必須等待，即系統(tǒng)當前沒有足夠的資源滿足必須等待，即系統(tǒng)當前沒有足夠的資源滿足進程進程p pi i當前的請求；否則進行下一步；當前的請求；否則進行下一步； 系統(tǒng)進行假分配，即假設系統(tǒng)給進程系統(tǒng)進行假分配，即假設系統(tǒng)給進程p pi i分配所請求的資源，對資分配所請求的資源，對資源分配狀態(tài)作如下修改：源分配狀態(tài)作如

22、下修改： A AA ARRRRi i；U Ui iU Ui iRRRRi i；N Ni iNiNiRRRRi i； 調用安全算法檢查此次資源分配后的現(xiàn)行狀態(tài)是否安全狀態(tài)。若調用安全算法檢查此次資源分配后的現(xiàn)行狀態(tài)是否安全狀態(tài)。若安全，則正式將資源分配給進程安全，則正式將資源分配給進程p pi i，完成進程，完成進程p pi i的資源請求分配工作。的資源請求分配工作。否則，拒絕分配讓進程等待，并恢復此次的假設分配，即撤消步驟否則，拒絕分配讓進程等待，并恢復此次的假設分配，即撤消步驟對對分配狀態(tài)所作的修改。分配狀態(tài)所作的修改。跳轉到第一頁（4 4）安全算法描述）安全算法描述 設向量設向量W W（W

23、orkWork），向量元素），向量元素Wj(j=1Wj(j=1，2 2，m)m)表示系統(tǒng)可表示系統(tǒng)可供給各個進程繼續(xù)運行的供給各個進程繼續(xù)運行的j j類資源數(shù)；向量類資源數(shù)；向量F F（FinishFinish），向量元素），向量元素Fi(i =1Fi(i =1，2 2，n)n)表示系統(tǒng)是否有足夠的資源可使進程表示系統(tǒng)是否有足夠的資源可使進程pipi完成。初完成。初始化始化W WA A，F(xiàn)i=falseFi=false。 從進程集合中找到一個進程從進程集合中找到一個進程p pi i，有，有Fi=falseFi=false且且NiWNiW，則執(zhí)行，則執(zhí)行步驟步驟；如果這樣的進程不存在，則轉去執(zhí)行步驟；如果這樣的進程不存在，則轉去執(zhí)行步驟； 進程進程p pi i可得到所需的全部資源，順利執(zhí)行完成，并釋放它所占可得到所需的全部資源，順利執(zhí)行完成，并釋放它所占用的資源，所以執(zhí)行用的資源，所以執(zhí)行W WW WU Ui i及及Fi=trueFi=true，轉去執(zhí)行，轉去執(zhí)行； 若對所有的進程，都有若對所有的進程，都有Fi=trueFi=true，則存在一個安全序列，現(xiàn)行，則存在一個安全序列，現(xiàn)行狀態(tài)是安全的，否則是不安全的。狀態(tài)是安全的，否則是不安全的。例例410 )0010(，A0014063213541000001245U16420020100207