計(jì)算機(jī)操作系統(tǒng)課件第三章.

1、第三章 處理機(jī)調(diào)度與死鎖3.1 3.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念3.2 3.2 調(diào)度算法調(diào)度算法3.3 3.3 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度3.4 3.4 多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度3.5 3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.6 3.6 預(yù)防死鎖的方法和死鎖避免預(yù)防死鎖的方法和死鎖避免3.7 3.7 死鎖的檢測(cè)和解除死鎖的檢測(cè)和解除 3.1 處理機(jī)調(diào)度的基本概念 在多道程環(huán)境下，進(jìn)程數(shù)目往往在多道程環(huán)境下，進(jìn)程數(shù)目往往多于處理機(jī)數(shù)目，致使它們爭(zhēng)用處理機(jī)。多于處理機(jī)數(shù)目，致使它們爭(zhēng)用處理機(jī)。這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)地把這就要求系統(tǒng)能按某種算法，動(dòng)態(tài)

2、地把處理機(jī)分配給處理機(jī)分配給就緒隊(duì)列就緒隊(duì)列中的一個(gè)進(jìn)程，中的一個(gè)進(jìn)程，使之執(zhí)行。分配處理機(jī)的任務(wù)是由進(jìn)程使之執(zhí)行。分配處理機(jī)的任務(wù)是由進(jìn)程調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計(jì)的調(diào)度程序完成的。它是操作系統(tǒng)設(shè)計(jì)的中心問(wèn)題之一。中心問(wèn)題之一。 進(jìn)程調(diào)度要解決的問(wèn)題WHATWHAT：按什么原則分配按什么原則分配CPUCPU 進(jìn)程調(diào)度算法進(jìn)程調(diào)度算法WHENWHEN：何時(shí)分配何時(shí)分配CPUCPU 進(jìn)程調(diào)度的時(shí)機(jī)進(jìn)程調(diào)度的時(shí)機(jī)HOWHOW： 如何分配如何分配CPUCPU CPUCPU調(diào)度過(guò)程（進(jìn)程的上下文切換）調(diào)度過(guò)程（進(jìn)程的上下文切換）1. 高級(jí)、中級(jí)和低級(jí)調(diào)度l處理機(jī)是計(jì)算機(jī)系統(tǒng)中的重要資源處理機(jī)是計(jì)

3、算機(jī)系統(tǒng)中的重要資源l處理機(jī)調(diào)度算法對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的綜處理機(jī)調(diào)度算法對(duì)整個(gè)計(jì)算機(jī)系統(tǒng)的綜合性能指標(biāo)有重要影響合性能指標(biāo)有重要影響l可把處理機(jī)調(diào)度分成三個(gè)層次：可把處理機(jī)調(diào)度分成三個(gè)層次： 高級(jí)調(diào)度 中級(jí)調(diào)度 低級(jí)調(diào)度 高級(jí)調(diào)度高級(jí)調(diào)度也稱為作業(yè)調(diào)度或長(zhǎng)程調(diào)度或宏觀調(diào)度也稱為作業(yè)調(diào)度或長(zhǎng)程調(diào)度或宏觀調(diào)度 高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天高級(jí)調(diào)度的時(shí)間尺度通常是分鐘、小時(shí)或天 中級(jí)調(diào)度中級(jí)調(diào)度涉及進(jìn)程在內(nèi)外存間的交換，從存儲(chǔ)器涉及進(jìn)程在內(nèi)外存間的交換，從存儲(chǔ)器資源管理的角度來(lái)看，把進(jìn)程的部分或全部換出資源管理的角度來(lái)看，把進(jìn)程的部分或全部換出到外存上，可為當(dāng)前運(yùn)行進(jìn)程的執(zhí)行提供所需內(nèi)到外存

4、上，可為當(dāng)前運(yùn)行進(jìn)程的執(zhí)行提供所需內(nèi)存空間，將當(dāng)前進(jìn)程所需部分換入到內(nèi)存。指令存空間，將當(dāng)前進(jìn)程所需部分換入到內(nèi)存。指令和數(shù)據(jù)必須在內(nèi)存里才能被處理機(jī)直接訪問(wèn)和數(shù)據(jù)必須在內(nèi)存里才能被處理機(jī)直接訪問(wèn) 低級(jí)調(diào)度低級(jí)調(diào)度也稱進(jìn)程調(diào)度或短程調(diào)度或微觀調(diào)度，也稱進(jìn)程調(diào)度或短程調(diào)度或微觀調(diào)度，從處理機(jī)資源分配的角度來(lái)看，處理機(jī)需要經(jīng)常從處理機(jī)資源分配的角度來(lái)看，處理機(jī)需要經(jīng)常選擇就緒進(jìn)程或線程進(jìn)入運(yùn)行狀態(tài)，低級(jí)調(diào)度的選擇就緒進(jìn)程或線程進(jìn)入運(yùn)行狀態(tài)，低級(jí)調(diào)度的時(shí)間尺度通常是毫秒級(jí)的。由于低級(jí)調(diào)度算法的時(shí)間尺度通常是毫秒級(jí)的。由于低級(jí)調(diào)度算法的頻繁使用，要求在實(shí)現(xiàn)時(shí)做到高效頻繁使用，要求在實(shí)現(xiàn)時(shí)做到高效2.進(jìn)

5、程調(diào)度的任務(wù) 進(jìn)程調(diào)度的任務(wù)是控制協(xié)進(jìn)程調(diào)度的任務(wù)是控制協(xié)調(diào)進(jìn)程對(duì)調(diào)進(jìn)程對(duì)CPUCPU的競(jìng)爭(zhēng)的競(jìng)爭(zhēng), ,即按一定即按一定的調(diào)度算法從就緒隊(duì)列中選中的調(diào)度算法從就緒隊(duì)列中選中一個(gè)進(jìn)程，把一個(gè)進(jìn)程，把CPUCPU的使用權(quán)交的使用權(quán)交給被選中的進(jìn)程。給被選中的進(jìn)程。3.確定算法的原則 具有公平性具有公平性 資源利用率高（特別是資源利用率高（特別是CPUCPU利用利用率）率） 在交互式系統(tǒng)情況下要追求響應(yīng)在交互式系統(tǒng)情況下要追求響應(yīng)時(shí)間（越短越好）時(shí)間（越短越好） 在批處理系統(tǒng)情況下要追求系統(tǒng)在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量吞吐量4.進(jìn)程調(diào)度方式 非搶占方式非搶占方式：分派程序一旦把處理機(jī)分：分派程

6、序一旦把處理機(jī)分配給某進(jìn)程后便讓它一直運(yùn)行下去，直配給某進(jìn)程后便讓它一直運(yùn)行下去，直到進(jìn)程完成或發(fā)生某事件而阻塞時(shí)，才到進(jìn)程完成或發(fā)生某事件而阻塞時(shí)，才把處理機(jī)分配給另一個(gè)進(jìn)程。把處理機(jī)分配給另一個(gè)進(jìn)程。 搶占方式：搶占方式：當(dāng)一個(gè)進(jìn)程正在運(yùn)行時(shí)，系當(dāng)一個(gè)進(jìn)程正在運(yùn)行時(shí)，系統(tǒng)可以基于某種原則，剝奪已分配給它統(tǒng)可以基于某種原則，剝奪已分配給它的處理機(jī)，將之分配給其它進(jìn)程。搶占的處理機(jī)，將之分配給其它進(jìn)程。搶占原則有：優(yōu)先權(quán)原則、短進(jìn)程優(yōu)先原則、原則有：優(yōu)先權(quán)原則、短進(jìn)程優(yōu)先原則、時(shí)間片原則。時(shí)間片原則。5.進(jìn)程調(diào)度性能衡量的指標(biāo) 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 響應(yīng)時(shí)間響應(yīng)時(shí)間 CPU-I/OCPU-I/O執(zhí)

7、行期執(zhí)行期6.進(jìn)程調(diào)度模型 1)只有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型圖 3 - 1 僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型2)具有高低級(jí)調(diào)度的調(diào)度隊(duì)列模型圖 3-2 具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型3)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型圖 3-3 具有三級(jí)調(diào)度時(shí)的調(diào)度隊(duì)列模型7.選擇進(jìn)程調(diào)度方式的準(zhǔn)則 面向用戶的準(zhǔn)則：周轉(zhuǎn)時(shí)間短；響面向用戶的準(zhǔn)則：周轉(zhuǎn)時(shí)間短；響應(yīng)時(shí)間快；截止時(shí)間的保證；優(yōu)先應(yīng)時(shí)間快；截止時(shí)間的保證；優(yōu)先權(quán)準(zhǔn)則權(quán)準(zhǔn)則 面向系統(tǒng)的準(zhǔn)則：系統(tǒng)吞吐量高；面向系統(tǒng)的準(zhǔn)則：系統(tǒng)吞吐量高；處理機(jī)利用率好；各類資源的平衡處理機(jī)利用率好；各類資源的平衡利用利用3.2 3.2 進(jìn)程調(diào)度算法 先進(jìn)先出先進(jìn)先出(FIFO)(F

8、IFO)算法算法 最短最短CPUCPU運(yùn)行期優(yōu)先調(diào)度算法運(yùn)行期優(yōu)先調(diào)度算法 最高優(yōu)先權(quán)優(yōu)先調(diào)度算法最高優(yōu)先權(quán)優(yōu)先調(diào)度算法 輪轉(zhuǎn)法輪轉(zhuǎn)法 多級(jí)反饋隊(duì)列多級(jí)反饋隊(duì)列 1.先進(jìn)先出(FIFO)算法 該算法總是把處理機(jī)分配給最先進(jìn)入就緒隊(duì)列該算法總是把處理機(jī)分配給最先進(jìn)入就緒隊(duì)列的進(jìn)程，一個(gè)進(jìn)程一旦分得處理機(jī)，便執(zhí)行下去，的進(jìn)程，一個(gè)進(jìn)程一旦分得處理機(jī)，便執(zhí)行下去，直到該進(jìn)程完成或阻塞時(shí)，才釋放處理機(jī)。直到該進(jìn)程完成或阻塞時(shí)，才釋放處理機(jī)。 優(yōu)點(diǎn)優(yōu)點(diǎn): :實(shí)現(xiàn)簡(jiǎn)單實(shí)現(xiàn)簡(jiǎn)單. . 缺點(diǎn)缺點(diǎn): :沒(méi)考慮進(jìn)程的優(yōu)先級(jí)沒(méi)考慮進(jìn)程的優(yōu)先級(jí) 2.最短CPU運(yùn)行期優(yōu)先調(diào)度算法 該算法從就緒隊(duì)列中選出該算法從就緒隊(duì)列

9、中選出“下一個(gè)下一個(gè)CPUCPU執(zhí)行期執(zhí)行期”最短的進(jìn)程，為之分配最短的進(jìn)程，為之分配處理機(jī)。處理機(jī)。 該算法雖可獲得較好的調(diào)度性能，但該算法雖可獲得較好的調(diào)度性能，但難以準(zhǔn)確地知道下一個(gè)難以準(zhǔn)確地知道下一個(gè)CPUCPU執(zhí)行期，執(zhí)行期，而只能根據(jù)每一個(gè)進(jìn)行的執(zhí)行歷史來(lái)而只能根據(jù)每一個(gè)進(jìn)行的執(zhí)行歷史來(lái)預(yù)測(cè)。預(yù)測(cè)。 4.最高優(yōu)先權(quán)優(yōu)先調(diào)度算法 該算法總是把處理機(jī)分配給就緒隊(duì)列中具該算法總是把處理機(jī)分配給就緒隊(duì)列中具有最高優(yōu)先權(quán)的進(jìn)程。常用以下兩種方法來(lái)確有最高優(yōu)先權(quán)的進(jìn)程。常用以下兩種方法來(lái)確定進(jìn)程的優(yōu)先權(quán)定進(jìn)程的優(yōu)先權(quán)( (優(yōu)先級(jí)根據(jù)優(yōu)先數(shù)來(lái)決定優(yōu)先級(jí)根據(jù)優(yōu)先數(shù)來(lái)決定) ) 靜態(tài)優(yōu)先數(shù)法靜態(tài)優(yōu)先

10、數(shù)法：靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確：靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，在整個(gè)運(yùn)行期間不再改變。依據(jù)有：進(jìn)定的，在整個(gè)運(yùn)行期間不再改變。依據(jù)有：進(jìn)程類型、進(jìn)程對(duì)資源的要求、用戶要求的優(yōu)先程類型、進(jìn)程對(duì)資源的要求、用戶要求的優(yōu)先權(quán)。權(quán)。 動(dòng)態(tài)優(yōu)先數(shù)法：動(dòng)態(tài)優(yōu)先數(shù)法：在進(jìn)程創(chuàng)建時(shí)創(chuàng)立一個(gè)優(yōu)先數(shù)，在進(jìn)程創(chuàng)建時(shí)創(chuàng)立一個(gè)優(yōu)先數(shù)，但在其生命周期內(nèi)優(yōu)先數(shù)可以動(dòng)態(tài)變化。如等但在其生命周期內(nèi)優(yōu)先數(shù)可以動(dòng)態(tài)變化。如等待時(shí)間長(zhǎng)優(yōu)先數(shù)可改待時(shí)間長(zhǎng)優(yōu)先數(shù)可改變變圖 3-4 FCFS和SJF調(diào)度算法的性能 3. FCFS和SJF的性能比較 優(yōu)先權(quán)的變化規(guī)律可描述為：優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時(shí)間與服務(wù)時(shí)間之和，就是系

11、由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于于響應(yīng)比響應(yīng)比R RP P。據(jù)此，又可表示為：。據(jù)此，又可表示為： 5.高響應(yīng)比優(yōu)先調(diào)度算法6. 輪轉(zhuǎn)法 把把CPUCPU劃分成若干時(shí)間片劃分成若干時(shí)間片, ,并且按順序賦并且按順序賦給就緒隊(duì)列中的每一個(gè)進(jìn)程，進(jìn)程輪流占有給就緒隊(duì)列中的每一個(gè)進(jìn)程，進(jìn)程輪流占有CPUCPU，當(dāng)時(shí)間片用完時(shí)，即使進(jìn)程未執(zhí)行完，當(dāng)時(shí)間片用完時(shí)，即使進(jìn)程未執(zhí)行完畢，系統(tǒng)也剝奪該進(jìn)程的畢，系統(tǒng)也剝奪該進(jìn)程的CPUCPU，將該進(jìn)程排，將該進(jìn)程排在就緒隊(duì)列末尾。同時(shí)系統(tǒng)選擇另一個(gè)進(jìn)程在就緒隊(duì)列末尾。同時(shí)系統(tǒng)選擇另

12、一個(gè)進(jìn)程運(yùn)行運(yùn)行 簡(jiǎn)單輪轉(zhuǎn)法：簡(jiǎn)單輪轉(zhuǎn)法：系統(tǒng)將所有就緒進(jìn)程系統(tǒng)將所有就緒進(jìn)程按按FIFOFIFO規(guī)規(guī)則排隊(duì)，按一定的時(shí)間間隔把處理機(jī)分配給則排隊(duì)，按一定的時(shí)間間隔把處理機(jī)分配給隊(duì)列中的進(jìn)程。這樣，就緒隊(duì)列中所有進(jìn)程隊(duì)列中的進(jìn)程。這樣，就緒隊(duì)列中所有進(jìn)程均可獲得一個(gè)時(shí)間片的處理機(jī)而運(yùn)行。均可獲得一個(gè)時(shí)間片的處理機(jī)而運(yùn)行。 多級(jí)隊(duì)列方法：多級(jí)隊(duì)列方法：將系統(tǒng)中所有進(jìn)程分成若干將系統(tǒng)中所有進(jìn)程分成若干類，每類為一級(jí)。類，每類為一級(jí)。 7.分時(shí)系統(tǒng)中常用時(shí)間片輪轉(zhuǎn)法時(shí)間片選擇問(wèn)題： 固定時(shí)間片固定時(shí)間片 可變時(shí)間片可變時(shí)間片與時(shí)間片大小有關(guān)的因素： 系統(tǒng)響應(yīng)時(shí)間系統(tǒng)響應(yīng)時(shí)間 就緒進(jìn)程個(gè)數(shù)就緒進(jìn)程個(gè)數(shù)

13、 CPUCPU能力能力 1)簡(jiǎn)單輪轉(zhuǎn)法的調(diào)度模型2)多隊(duì)列反饋調(diào)度算法 將就緒隊(duì)列分為將就緒隊(duì)列分為N N級(jí)，每個(gè)就緒隊(duì)列級(jí)，每個(gè)就緒隊(duì)列分配給不同的時(shí)間片，隊(duì)列級(jí)別越高，分配給不同的時(shí)間片，隊(duì)列級(jí)別越高，時(shí)間越小，級(jí)別越低，時(shí)間片越大，最時(shí)間越小，級(jí)別越低，時(shí)間片越大，最后一級(jí)采用時(shí)間片輪轉(zhuǎn)，其他隊(duì)列采用后一級(jí)采用時(shí)間片輪轉(zhuǎn)，其他隊(duì)列采用先進(jìn)先出；先進(jìn)先出； 系統(tǒng)從第一級(jí)調(diào)度，當(dāng)?shù)谙到y(tǒng)從第一級(jí)調(diào)度，當(dāng)?shù)谝患?jí)為空時(shí)，系統(tǒng)轉(zhuǎn)向第二個(gè)隊(duì)一級(jí)為空時(shí)，系統(tǒng)轉(zhuǎn)向第二個(gè)隊(duì)列，列，.當(dāng)運(yùn)行進(jìn)程用完一個(gè)時(shí)間片，當(dāng)運(yùn)行進(jìn)程用完一個(gè)時(shí)間片，放棄放棄CPUCPU時(shí)，進(jìn)入下一級(jí)隊(duì)列；等待進(jìn)時(shí)，進(jìn)入下一級(jí)隊(duì)列；等待進(jìn)程

14、被喚醒時(shí)，進(jìn)入原來(lái)的就緒隊(duì)列；當(dāng)程被喚醒時(shí)，進(jìn)入原來(lái)的就緒隊(duì)列；當(dāng)進(jìn)程第一次就緒時(shí)，進(jìn)入第一級(jí)隊(duì)列進(jìn)程第一次就緒時(shí)，進(jìn)入第一級(jí)隊(duì)列 * * 首先系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列首先系統(tǒng)中設(shè)置多個(gè)就緒隊(duì)列* * 每個(gè)就緒隊(duì)列分配給不同時(shí)間片，優(yōu)先級(jí)高的每個(gè)就緒隊(duì)列分配給不同時(shí)間片，優(yōu)先級(jí)高的為第一級(jí)隊(duì)列，時(shí)間片最小，隨著隊(duì)列級(jí)別的為第一級(jí)隊(duì)列，時(shí)間片最小，隨著隊(duì)列級(jí)別的降低，時(shí)間片加大降低，時(shí)間片加大* * 各個(gè)隊(duì)列按照先進(jìn)先出調(diào)度算法各個(gè)隊(duì)列按照先進(jìn)先出調(diào)度算法* * 一個(gè)新進(jìn)程就緒后進(jìn)入第一級(jí)隊(duì)列一個(gè)新進(jìn)程就緒后進(jìn)入第一級(jí)隊(duì)列* * 進(jìn)程由于等待而放棄進(jìn)程由于等待而放棄CPUCPU后，進(jìn)入等待隊(duì)列，一

15、后，進(jìn)入等待隊(duì)列，一旦等待的事件發(fā)生，則回到原來(lái)的就緒隊(duì)列旦等待的事件發(fā)生，則回到原來(lái)的就緒隊(duì)列* * 當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，可以搶占當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒時(shí)，可以搶占CPUCPU，被搶占進(jìn)程回到原來(lái)一級(jí)就緒隊(duì)列末尾，被搶占進(jìn)程回到原來(lái)一級(jí)就緒隊(duì)列末尾* * 當(dāng)?shù)谝患?jí)隊(duì)列空時(shí)，就去調(diào)度第二級(jí)隊(duì)列，如當(dāng)?shù)谝患?jí)隊(duì)列空時(shí)，就去調(diào)度第二級(jí)隊(duì)列，如此類推此類推* * 當(dāng)時(shí)間片到后，進(jìn)程放棄當(dāng)時(shí)間片到后，進(jìn)程放棄CPUCPU，回到下一級(jí)隊(duì)列，回到下一級(jí)隊(duì)列 3)多隊(duì)列反饋調(diào)度算法8.進(jìn)程調(diào)度的時(shí)機(jī)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢，或由于某種錯(cuò)誤而當(dāng)一個(gè)進(jìn)程運(yùn)行完畢，或由于某種錯(cuò)誤而終止運(yùn)行終止運(yùn)行當(dāng)一個(gè)

16、進(jìn)程在運(yùn)行中處于等待狀態(tài)（等待當(dāng)一個(gè)進(jìn)程在運(yùn)行中處于等待狀態(tài)（等待I/OI/O）分時(shí)系統(tǒng)中時(shí)間片到分時(shí)系統(tǒng)中時(shí)間片到當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒（可搶占當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒（可搶占式）式） 例如：新創(chuàng)建一個(gè)進(jìn)程，一個(gè)等待進(jìn)程變例如：新創(chuàng)建一個(gè)進(jìn)程，一個(gè)等待進(jìn)程變成就緒成就緒在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操作（原語(yǔ)操作（P P操作，阻塞原語(yǔ)，喚醒原語(yǔ)）操作，阻塞原語(yǔ)，喚醒原語(yǔ)）何時(shí)切換進(jìn)程 只要只要OSOS取得對(duì)取得對(duì)CPUCPU的控制，進(jìn)程切換就可的控制，進(jìn)程切換就可能發(fā)生，如能發(fā)生，如: :超級(jí)用戶調(diào)用超級(jí)用戶調(diào)用來(lái)自程序的顯式請(qǐng)求來(lái)自程

17、序的顯式請(qǐng)求 ( (如：打開文如：打開文件件) )，該進(jìn)程通常會(huì)被阻塞，該進(jìn)程通常會(huì)被阻塞陷阱陷阱最末一條指令導(dǎo)致出錯(cuò)，會(huì)引起進(jìn)程最末一條指令導(dǎo)致出錯(cuò)，會(huì)引起進(jìn)程移至退出狀態(tài)移至退出狀態(tài)中斷中斷 外部因素影響當(dāng)前指令的執(zhí)行，控制外部因素影響當(dāng)前指令的執(zhí)行，控制被轉(zhuǎn)移至被轉(zhuǎn)移至IHIH（中斷處理程序）（中斷處理程序）9.引起進(jìn)程調(diào)度的原因 正在執(zhí)行的進(jìn)程執(zhí)行完畢或因發(fā)生某事正在執(zhí)行的進(jìn)程執(zhí)行完畢或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；件而不能再繼續(xù)執(zhí)行； 執(zhí)行中的進(jìn)程因提出執(zhí)行中的進(jìn)程因提出I/OI/O請(qǐng)求而暫停執(zhí)行；請(qǐng)求而暫停執(zhí)行； 在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原在進(jìn)程通信或同步過(guò)程中執(zhí)行了某種原

18、語(yǔ)操作語(yǔ)操作如如P P操作、阻塞、掛起原語(yǔ)等；操作、阻塞、掛起原語(yǔ)等； 在可搶占式調(diào)度中，有比當(dāng)前進(jìn)程優(yōu)先在可搶占式調(diào)度中，有比當(dāng)前進(jìn)程優(yōu)先權(quán)更高的進(jìn)程進(jìn)入就緒隊(duì)列；權(quán)更高的進(jìn)程進(jìn)入就緒隊(duì)列； 在時(shí)間片輪轉(zhuǎn)法中，時(shí)間片完。在時(shí)間片輪轉(zhuǎn)法中，時(shí)間片完。 通常系統(tǒng)是按先來(lái)先服務(wù)或優(yōu)先權(quán)形式通常系統(tǒng)是按先來(lái)先服務(wù)或優(yōu)先權(quán)形式來(lái)組織調(diào)度隊(duì)列。來(lái)組織調(diào)度隊(duì)列。 10.進(jìn)程調(diào)度算法 其中，其中，RQRQ為就緒隊(duì)列指針，為就緒隊(duì)列指針，EPEP為運(yùn)行隊(duì)為運(yùn)行隊(duì)列指針列指針。 3.3 3.3 實(shí)實(shí) 時(shí)時(shí) 調(diào)調(diào) 度度1.1.實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件 提供必要的信息提供必要的信息( (就緒時(shí)間

19、、截止時(shí)間、處理就緒時(shí)間、截止時(shí)間、處理時(shí)間、資源優(yōu)先級(jí)時(shí)間、資源優(yōu)先級(jí)) ) 系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng) 采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制 具有快速切換機(jī)制具有快速切換機(jī)制 2.實(shí)時(shí)調(diào)度算法的分類1)非搶占式調(diào)度算法 : 非搶占式輪轉(zhuǎn)調(diào)度算法 非搶占式優(yōu)先調(diào)度算法2)搶占式調(diào)度算法: 基于時(shí)鐘中斷的搶占優(yōu)先調(diào)度算法 立即搶占優(yōu)先權(quán)調(diào)度算法。圖 3-5 實(shí)時(shí)進(jìn)程調(diào)度 圖 3-6 EDF算法用于非搶占調(diào)度方式 3.常用的幾種實(shí)時(shí)調(diào)度算法1 1）最早截止時(shí)間優(yōu)先即）最早截止時(shí)間優(yōu)先即EDF(Earliest Deadline EDF(Earliest Deadline First)First

20、)算法算法圖 3-7 A和B任務(wù)每次必須完成的時(shí)間2）最低松弛度優(yōu)先(LLF)算法 該算法是根據(jù)任務(wù)緊急該算法是根據(jù)任務(wù)緊急( (或松弛或松弛) )的程度，來(lái)確定任的程度，來(lái)確定任務(wù)的優(yōu)先級(jí)。該算法主要用于可搶占調(diào)度方式中。務(wù)的優(yōu)先級(jí)。該算法主要用于可搶占調(diào)度方式中。 假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A A和和B B，任務(wù)任務(wù)A A要求每要求每 20 ms20 ms執(zhí)行一次，執(zhí)行時(shí)間為執(zhí)行一次，執(zhí)行時(shí)間為 10 ms10 ms；任務(wù)；任務(wù)B B只要求每只要求每50 ms50 ms執(zhí)行一次，執(zhí)行一次，執(zhí)行時(shí)間為執(zhí)行時(shí)間為 25 25 msms。

21、 在剛開始時(shí)在剛開始時(shí)( (t t1 1=0)=0)，A A1 1必須在必須在20ms20ms時(shí)完成，而它本身運(yùn)行時(shí)完成，而它本身運(yùn)行又需又需 10 ms10 ms，可算出，可算出A A1 1的松弛度為的松弛度為10ms10ms；B B1 1必須在必須在50ms50ms時(shí)完時(shí)完成，成， 而它本身運(yùn)行就需而它本身運(yùn)行就需25 ms25 ms，可算出，可算出B B1 1的松弛度為的松弛度為25 ms25 ms，故調(diào)度程序應(yīng)先調(diào)度故調(diào)度程序應(yīng)先調(diào)度A A1 1執(zhí)行。在執(zhí)行。在t t2 2=10 ms=10 ms時(shí)，時(shí)，A A2 2的松弛度可的松弛度可按下式算出：按下式算出：A A2 2的松弛度的松弛

22、度= =必須完成時(shí)間必須完成時(shí)間- -其本身的運(yùn)行時(shí)其本身的運(yùn)行時(shí)間間- -當(dāng)前時(shí)間當(dāng)前時(shí)間= =40 ms-10 ms-10 ms=20 ms 40 ms-10 ms-10 ms=20 ms 類似地，可算出類似地，可算出B1B1的松弛度為的松弛度為15ms15ms，調(diào)度程序應(yīng)選擇，調(diào)度程序應(yīng)選擇B2B2運(yùn)行。運(yùn)行。t t3=30 ms3=30 ms時(shí)，時(shí)，A2A2的松弛度已減為的松弛度已減為0 0，B1B1的松弛度為的松弛度為15 ms15 ms，于是調(diào)度程序應(yīng)搶占，于是調(diào)度程序應(yīng)搶占B1B1的處理機(jī)而調(diào)度的處理機(jī)而調(diào)度A2A2運(yùn)行運(yùn)行圖 3-8 利用ELLF算法進(jìn)行調(diào)度的情況3.5 產(chǎn)生死

23、鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件3.5.1 3.5.1 死鎖的概念死鎖的概念1.1.死鎖例子死鎖例子: : 一個(gè)由于一個(gè)由于申請(qǐng)不同類型資源申請(qǐng)不同類型資源而產(chǎn)生死鎖的例子而產(chǎn)生死鎖的例子 設(shè)系統(tǒng)有一臺(tái)打印機(jī)設(shè)系統(tǒng)有一臺(tái)打印機(jī)(R1)(R1)一臺(tái)掃描儀一臺(tái)掃描儀(R2)(R2)，兩，兩進(jìn)程共享這兩臺(tái)設(shè)備。進(jìn)程共享這兩臺(tái)設(shè)備。 用信號(hào)量用信號(hào)量S1S1表示表示R1R1是否可用，用信號(hào)量是否可用，用信號(hào)量S2S2表示表示R2R2是否可用是否可用， S1S1、 S2S2初值為初值為1 1。死鎖例子死鎖例子 這兩個(gè)進(jìn)程在并發(fā)執(zhí)行過(guò)程中，可這兩個(gè)進(jìn)程在并發(fā)執(zhí)行過(guò)程中，可能會(huì)發(fā)生死鎖。大家可以思

24、考一下，如能會(huì)發(fā)生死鎖。大家可以思考一下，如何修改，進(jìn)程才不會(huì)發(fā)生死鎖。何修改，進(jìn)程才不會(huì)發(fā)生死鎖。2.死鎖概念 指多個(gè)進(jìn)程因競(jìng)爭(zhēng)共享資源而造成的一種僵指多個(gè)進(jìn)程因競(jìng)爭(zhēng)共享資源而造成的一種僵局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能局，若無(wú)外力作用，這些進(jìn)程都將永遠(yuǎn)不能再向前推進(jìn)。再向前推進(jìn)。 即：一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等待被該即：一組進(jìn)程中，每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無(wú)法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，無(wú)法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖，這一組進(jìn)程就稱為死鎖進(jìn)程。這一組進(jìn)程就稱為死鎖進(jìn)程。3.關(guān)于死鎖的一些結(jié)論關(guān)于死

25、鎖的一些結(jié)論 參與死鎖的進(jìn)程最少是兩個(gè)參與死鎖的進(jìn)程最少是兩個(gè) 參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源資源 參與死鎖的所有進(jìn)程都在等待資源參與死鎖的所有進(jìn)程都在等待資源 參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集程的子集注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資注：如果死鎖發(fā)生，會(huì)浪費(fèi)大量系統(tǒng)資源，甚至導(dǎo)致系統(tǒng)崩潰。源，甚至導(dǎo)致系統(tǒng)崩潰。4.永久性資源和臨時(shí)性資源 永久性資源：可以被多個(gè)進(jìn)程多次使永久性資源：可以被多個(gè)進(jìn)程多次使用（可再用資源）用（可再用資源） 可搶占資源可搶占資源( (如如CPUCPU和內(nèi)存和內(nèi)存) ) 不可搶占資源（如打印

26、機(jī)、磁帶機(jī)）不可搶占資源（如打印機(jī)、磁帶機(jī)） 臨時(shí)性資源：只可使用一次的資源；臨時(shí)性資源：只可使用一次的資源；如信號(hào)量如信號(hào)量, ,中斷信號(hào)，同步信號(hào)等中斷信號(hào)，同步信號(hào)等（可消耗性資源）（可消耗性資源）“申請(qǐng)申請(qǐng)-分配分配-使用使用-釋放釋放”模式模式3.5.2 產(chǎn)生死鎖的原因1.1.競(jìng)爭(zhēng)系統(tǒng)資源競(jìng)爭(zhēng)系統(tǒng)資源2.2.進(jìn)程的推進(jìn)順序不當(dāng)進(jìn)程的推進(jìn)順序不當(dāng) 1. 1. 競(jìng)爭(zhēng)系統(tǒng)資源 若系統(tǒng)中只有一臺(tái)打印機(jī)若系統(tǒng)中只有一臺(tái)打印機(jī)R1R1和一臺(tái)和一臺(tái)讀卡讀卡機(jī)機(jī)R2R2，可供進(jìn)程，可供進(jìn)程P1P1和和P2P2共享。若共享。若形形成環(huán)路等待成環(huán)路等待，這樣會(huì)產(chǎn)生死鎖，這樣會(huì)產(chǎn)生死鎖。2.2.進(jìn)程的推進(jìn)

27、順序不當(dāng) 在進(jìn)程在進(jìn)程P1P1和和P2P2并發(fā)執(zhí)行時(shí)，按照左圖曲并發(fā)執(zhí)行時(shí)，按照左圖曲線線所示順序推進(jìn)時(shí)，兩進(jìn)程會(huì)順?biāo)卷樞蛲七M(jìn)時(shí)，兩進(jìn)程會(huì)順利完成，我們稱這種推進(jìn)順序是合法的。利完成，我們稱這種推進(jìn)順序是合法的。若按曲線若按曲線的順序推進(jìn)時(shí)，進(jìn)入不安全的順序推進(jìn)時(shí)，進(jìn)入不安全區(qū)區(qū)D D內(nèi)，兩進(jìn)程再推進(jìn)會(huì)產(chǎn)生死鎖。內(nèi)，兩進(jìn)程再推進(jìn)會(huì)產(chǎn)生死鎖。3.5.3 產(chǎn)生死鎖的必要條件 互斥條件互斥條件（資源獨(dú)占）（資源獨(dú)占） 請(qǐng)求和保持條件請(qǐng)求和保持條件（部分分配，（部分分配，占有申請(qǐng)）占有申請(qǐng)） 不剝奪條件（不剝奪條件（不可強(qiáng)占）不可強(qiáng)占） 環(huán)路等待條件。環(huán)路等待條件。解決死鎖的基本辦法 預(yù)防死鎖 避免

28、死鎖 檢測(cè)死鎖 解除死鎖3.6 預(yù)防死鎖的方法和避免死鎖 1.1.預(yù)防死鎖的方法預(yù)防死鎖的方法 在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具在系統(tǒng)設(shè)計(jì)時(shí)確定資源分配算法，保證不發(fā)生死鎖。具體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一。體的做法是破壞產(chǎn)生死鎖的四個(gè)必要條件之一。 1)資源一次性分配；( (破壞請(qǐng)求和保持條件破壞請(qǐng)求和保持條件) ) 2)可剝奪資源；即當(dāng)某進(jìn)程新的資源未滿足時(shí)，釋放已占即當(dāng)某進(jìn)程新的資源未滿足時(shí)，釋放已占有的資源有的資源( (破壞不可剝奪條件破壞不可剝奪條件) ) 3)資源有序分配法；做法：系統(tǒng)給每類資源賦予一個(gè)編號(hào)，；做法：系統(tǒng)給每類資源賦予一個(gè)編號(hào)，每一個(gè)進(jìn)程按

29、編號(hào)遞增的順序請(qǐng)求資源，釋放則相反每一個(gè)進(jìn)程按編號(hào)遞增的順序請(qǐng)求資源，釋放則相反( (破破壞環(huán)路等待條件壞環(huán)路等待條件) )2. 死鎖避免 死鎖避免定義: :在系統(tǒng)運(yùn)行過(guò)程中，對(duì)進(jìn)程發(fā)出的在系統(tǒng)運(yùn)行過(guò)程中，對(duì)進(jìn)程發(fā)出的每一個(gè)系統(tǒng)能夠滿足的資源申請(qǐng)進(jìn)行動(dòng)態(tài)檢查，并每一個(gè)系統(tǒng)能夠滿足的資源申請(qǐng)進(jìn)行動(dòng)態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可根據(jù)檢查結(jié)果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。能發(fā)生死鎖，則不予分配，否則予以分配。 預(yù)防死鎖的幾種策略，會(huì)嚴(yán)重地?fù)p害了系統(tǒng)性能。預(yù)防死鎖的幾種策略，會(huì)嚴(yán)重地?fù)p害了系統(tǒng)性能。因此要施加較弱的限制，從而獲得較滿意得系

30、統(tǒng)性因此要施加較弱的限制，從而獲得較滿意得系統(tǒng)性能來(lái)避免死鎖。能來(lái)避免死鎖。 由于在避免死鎖的策略中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資由于在避免死鎖的策略中，允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源。因而，系統(tǒng)在進(jìn)行資源分配之前預(yù)先計(jì)算資源源。因而，系統(tǒng)在進(jìn)行資源分配之前預(yù)先計(jì)算資源分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安分配的安全性。若此次分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，進(jìn)程等待。全狀態(tài)，則將資源分配給進(jìn)程；否則，進(jìn)程等待。其中最具有代表性的避免死鎖算法是銀行家算法。其中最具有代表性的避免死鎖算法是銀行家算法。3. 安全狀態(tài)與不安全狀態(tài) 安全狀態(tài)指系統(tǒng)能按某種進(jìn)程安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順

31、序來(lái)為每個(gè)進(jìn)程分配其所需資順序來(lái)為每個(gè)進(jìn)程分配其所需資源，直至最大需求，使每個(gè)進(jìn)程源，直至最大需求，使每個(gè)進(jìn)程都可順序完成。若系統(tǒng)不存在這都可順序完成。若系統(tǒng)不存在這樣一個(gè)序列，則稱系統(tǒng)處于不安樣一個(gè)序列，則稱系統(tǒng)處于不安全狀態(tài)。全狀態(tài)。 1)安全序列 一個(gè)進(jìn)程序列一個(gè)進(jìn)程序列PP1 1，P Pn n 是安全的，是安全的，如果對(duì)于每一個(gè)進(jìn)程如果對(duì)于每一個(gè)進(jìn)程P Pi i(1(1i in n），它以），它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程源量與所有進(jìn)程P Pj j (j i ) (j i )當(dāng)前占有資當(dāng)前占有資源量之和，系統(tǒng)處于安全狀態(tài)。源量

32、之和，系統(tǒng)處于安全狀態(tài)。 ( (安全狀態(tài)一定是沒(méi)有死鎖發(fā)生的安全狀態(tài)一定是沒(méi)有死鎖發(fā)生的) )進(jìn)進(jìn) 程程 最最 大大 需需 求求 已已 分分 配配 可可 用用 P1P2P3104952232) 2) 安全狀態(tài)之例安全狀態(tài)之例 我們通過(guò)一個(gè)例子來(lái)說(shuō)明安全性。假定系我們通過(guò)一個(gè)例子來(lái)說(shuō)明安全性。假定系統(tǒng)中有三個(gè)進(jìn)程統(tǒng)中有三個(gè)進(jìn)程P P1 1、 P P2 2和和P P3 3，共有，共有1212臺(tái)磁帶機(jī)。臺(tái)磁帶機(jī)。進(jìn)程進(jìn)程P P1 1總共要求總共要求1010臺(tái)磁帶機(jī)，臺(tái)磁帶機(jī)，P P2 2和和P P3 3分別要求分別要求4 4臺(tái)和臺(tái)和9 9臺(tái)。假設(shè)在臺(tái)。假設(shè)在T T0 0時(shí)刻，進(jìn)程時(shí)刻，進(jìn)程P P1

33、1、P P2 2和和P P3 3已分已分別獲得別獲得5 5臺(tái)、臺(tái)、2 2臺(tái)和臺(tái)和2 2臺(tái)磁帶機(jī)臺(tái)磁帶機(jī)，尚有，尚有3 3臺(tái)空閑未臺(tái)空閑未分配，如下表所示分配，如下表所示：3) 3) 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 如果不按照安全序分配資源，則系如果不按照安全序分配資源，則系統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例統(tǒng)可能會(huì)由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在如，在T T0 0時(shí)刻以后，時(shí)刻以后，P P3 3又請(qǐng)求又請(qǐng)求1 1臺(tái)磁帶機(jī)，臺(tái)磁帶機(jī)，若此時(shí)系統(tǒng)把剩余若此時(shí)系統(tǒng)把剩余3 3臺(tái)中的臺(tái)中的1 1臺(tái)分配給臺(tái)分配給P P3 3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。則系統(tǒng)便進(jìn)入不安全狀態(tài)。

34、 因?yàn)?，此時(shí)因?yàn)?，此時(shí)也無(wú)法再找到一個(gè)安全序列，也無(wú)法再找到一個(gè)安全序列， 例如，把例如，把其余的其余的2 2臺(tái)分配給臺(tái)分配給P P2 2，這樣，在，這樣，在P P2 2完成后完成后只能釋放出只能釋放出4 4臺(tái)，既不能滿足臺(tái)，既不能滿足P P1 1尚需尚需5 5臺(tái)的臺(tái)的要求，也不能滿足要求，也不能滿足P P3 3尚需尚需6 6臺(tái)的要求，致臺(tái)的要求，致使它們都無(wú)法推進(jìn)到完成，彼此都在等待使它們都無(wú)法推進(jìn)到完成，彼此都在等待對(duì)方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死對(duì)方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。鎖。安全狀態(tài)與不安全狀態(tài) 不安全狀態(tài)不安全狀態(tài): :不存在一個(gè)安全序列，不存在一個(gè)安全序列，不安全狀

35、態(tài)不一定導(dǎo)致死鎖不安全狀態(tài)不一定導(dǎo)致死鎖4.利用銀行家算法避免死鎖1)1)銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) (1) 可利用資源向量可利用資源向量AvailableAvailable。這是一個(gè)含有。這是一個(gè)含有m m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果的分配和回收而動(dòng)態(tài)地改變。如果AvailableAvailablej j=K=K，則表示系統(tǒng)中現(xiàn)

36、有，則表示系統(tǒng)中現(xiàn)有R Rj j類資源類資源K K個(gè)。個(gè)。 (2) (2) 最大需求矩陣最大需求矩陣MaxMax。這是一個(gè)。這是一個(gè)n nm m的矩陣，它定義的矩陣，它定義了系統(tǒng)中了系統(tǒng)中n n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m m類資源的最大需求。如果類資源的最大需求。如果MaxMaxi,ji,j=K=K，則表示進(jìn)程，則表示進(jìn)程i i需要需要R Rj j類資源的最大數(shù)目為類資源的最大數(shù)目為K K。 (3) (3) 分配矩陣分配矩陣AllocationAllocation。這也是一個(gè)。這也是一個(gè)n nm m的矩陣，的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。它定義

37、了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果如果AllocationAllocationi,ji,j=K=K，則表示進(jìn)程，則表示進(jìn)程i i當(dāng)前已分得當(dāng)前已分得R Rj j類資源類資源的數(shù)目為的數(shù)目為K K。 (4) (4) 需求矩陣需求矩陣NeedNeed。這也是一個(gè)。這也是一個(gè)n nm m的矩陣，用以表的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果NeedNeedi,ji,j= =K K，則表，則表示進(jìn)程示進(jìn)程i i還需要還需要R Rj j類資源類資源K K個(gè)，方能完成其任務(wù)個(gè)，方能完成其任務(wù)。 NeedNeedi,ji,j=Max=Maxi,ji

38、,j-Allocation-Allocationi,ji,j 2)2)銀行家算法銀行家算法 設(shè)設(shè)RequestRequesti i是進(jìn)程是進(jìn)程P Pi i的請(qǐng)求向量，如果的請(qǐng)求向量，如果RequestRequesti ij j= =K K，表示進(jìn)程表示進(jìn)程P Pi i需要需要K K個(gè)個(gè)R Rj j類型的資源。當(dāng)類型的資源。當(dāng)P Pi i發(fā)出資源請(qǐng)求后，發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：系統(tǒng)按下述步驟進(jìn)行檢查： (1) (1) 如果如果RequestRequesti ij jNeedNeedi,ji,j，便轉(zhuǎn)向步，便轉(zhuǎn)向步驟驟2 2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣；否則認(rèn)為

39、出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過(guò)它所宣布的最大值。布的最大值。 (2) (2) 如果如果RequestRequesti ij jAvailableAvailablej j，便轉(zhuǎn)，便轉(zhuǎn)向步驟向步驟(3)(3)；否則，；否則， 表示尚無(wú)足夠表示尚無(wú)足夠資源資源，P Pi i須等待。須等待。 (3) (3) 系統(tǒng)試探著把資源分配給進(jìn)程系統(tǒng)試探著把資源分配給進(jìn)程P Pi i，并修改下面數(shù)據(jù)結(jié)，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：構(gòu)中的數(shù)值：AvailableAvailablej j=Available=Availablej j-Request-Requesti ij j; ; AllocationAlloca

40、tioni,ji,j=Allocation=Allocationi,ji,j+Request+Requesti ij j; ;NeedNeedi,ji,j=Need=Needi,ji,j-Request-Requesti ij j; ; (4) (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程P Pi i，以完，以完成本次分配；否則，成本次分配；否則， 將本次的試探分配作廢，恢復(fù)將本次的試探分配作廢，恢復(fù)原來(lái)的資原來(lái)的資源分配狀態(tài)，讓進(jìn)程源分配狀態(tài)，讓

41、進(jìn)程P Pi i等待。等待。 3)3)安全性算法安全性算法(1) (1) 設(shè)置兩個(gè)向量：設(shè)置兩個(gè)向量： 工作向量工作向量Work: Work: 它表示系它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有它含有m m個(gè)元素，在執(zhí)行安全算法開始時(shí)，個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work=Available; Work=Available; Finish: Finish: 它表示系統(tǒng)是否它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做時(shí)先做FinishFinishi i=false; =false

42、; 當(dāng)有足夠資源分配當(dāng)有足夠資源分配給進(jìn)程時(shí)，給進(jìn)程時(shí)， 再再令令FinishFinishi i=true=true。 (2) (2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finish Finishi i=false; =false; Need Needi,ji,jWorkWorkj j； 若若找到，找到， 執(zhí)行步驟執(zhí)行步驟(3)(3)， 否則，執(zhí)行步驟否則，執(zhí)行步驟(4)(4)。 (3) (3) 當(dāng)進(jìn)程當(dāng)進(jìn)程P Pi i獲得資源后，可順利執(zhí)行，直至完成，并釋放獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：出分配給它的資源

43、，故應(yīng)執(zhí)行： WorkWorkj j=WorkWorki i+Allocation+Allocationi,ji,j; ; FinishFinishi i=true;true; go to step 2; go to step 2; (4) (4) 如果所有進(jìn)程的如果所有進(jìn)程的FinishFinishi i=true=true都滿足，都滿足， 則表示系則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。處于不安全狀態(tài)。圖圖 3-8 3-8 T T0 0時(shí)刻的資源分配表時(shí)刻的資源分配表 4) 4) 銀行家算法之例銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程假定系統(tǒng)中有五個(gè)進(jìn)程P

44、P0 0, P, P1 1, P, P2 2, P, P3 3, P, P4 4和三類資源和三類資源A, B, CA, B, C，各種資源的數(shù)量分別為，各種資源的數(shù)量分別為1010、5 5、7 7，在，在T T0 0時(shí)刻的資源分配情況如時(shí)刻的資源分配情況如圖圖 3-15 3-15 所示所示。(1) (1) T T0 0時(shí)刻的安全性：時(shí)刻的安全性： 圖 3-9 T0時(shí)刻的安全序列 (2) P(2) P1 1請(qǐng) 求 資 源 ：請(qǐng) 求 資 源 ： P P1 1發(fā) 出 請(qǐng) 求 向 量發(fā) 出 請(qǐng) 求 向 量RequestRequest1 1(1(1，0 0，2)2)，系統(tǒng)按銀行家算法進(jìn)行檢查：，系統(tǒng)按銀

45、行家算法進(jìn)行檢查： Request Request1 1(1, 0, 2)Need(1, 0, 2)Need1 1(1, 2, 2)(1, 2, 2) Request Request1 1(1, 0, 2)Available(1, 0, 2)Available1 1(3, 3, 2) (3, 3, 2) 系 統(tǒng) 先 假 定 可 為系 統(tǒng) 先 假 定 可 為 P P1 1分 配 資 源 ， 并 修 改分 配 資 源 ， 并 修 改Available, AllocationAvailable, Allocation1 1和和NeedNeed1 1向量，由此形成向量，由此形成的資源變化情況如圖的資源

46、變化情況如圖 3-15 3-15 中的圓括號(hào)所示。中的圓括號(hào)所示。 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 圖圖 3-10 P3-10 P1 1申請(qǐng)資源時(shí)的安全性檢查申請(qǐng)資源時(shí)的安全性檢查 (3) P(3) P4 4請(qǐng)求資源：請(qǐng)求資源：P P4 4發(fā)出請(qǐng)求向量發(fā)出請(qǐng)求向量RequestRequest4 4(3,3,0)(3,3,0)，系統(tǒng)按銀行家算法進(jìn)行檢查：系統(tǒng)按銀行家算法進(jìn)行檢查： Request Request4 4(3,3,0)Need(3,3,0)Need4 4(4,3,1);(4,3,1); Request Request4 4(3,3,0)A

47、vailable(2,3,0)(3,3,0)Available(2,3,0)，讓，讓P P4 4等待。等待。 (4) P(4) P0 0請(qǐng)求資源：請(qǐng)求資源：P P0 0發(fā)出請(qǐng)求向量發(fā)出請(qǐng)求向量RequstRequst0 0(0,2,0)(0,2,0)，系統(tǒng)按銀行家算法進(jìn)行檢查：系統(tǒng)按銀行家算法進(jìn)行檢查： Request Request0 0(0,2,0)Need(0,2,0)Need0 0(7,4,3);(7,4,3); Request Request0 0(0,2,0)Available(2,3,0);(0,2,0)Available(2,3,0); 系統(tǒng)暫時(shí)先假定可為系統(tǒng)暫時(shí)先假定可為P

48、P0 0分配資源，并修改分配資源，并修改有關(guān)數(shù)據(jù)，如圖有關(guān)數(shù)據(jù)，如圖 3-11 3-11 所示。所示。 圖圖 3-11 3-11 為為P P0 0分配資源后的有關(guān)資源數(shù)據(jù)分配資源后的有關(guān)資源數(shù)據(jù) 允許死鎖發(fā)生，操作系統(tǒng)不斷允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)監(jiān)視系統(tǒng)進(jìn)展情況，判斷死鎖是否發(fā)生生 一旦死鎖發(fā)生則采取專門的措一旦死鎖發(fā)生則采取專門的措施，解除死鎖并以最小的代價(jià)恢復(fù)操施，解除死鎖并以最小的代價(jià)恢復(fù)操作系統(tǒng)運(yùn)行作系統(tǒng)運(yùn)行3.7 死鎖的檢測(cè)和解除1.檢測(cè)時(shí)機(jī) 當(dāng)進(jìn)程等待時(shí)檢測(cè)死鎖當(dāng)進(jìn)程等待時(shí)檢測(cè)死鎖 （其缺點(diǎn)是系統(tǒng)的開銷大）（其缺點(diǎn)是系統(tǒng)的開銷大） 定時(shí)檢測(cè)定時(shí)檢測(cè) 系統(tǒng)資源利用率下降時(shí)檢測(cè)死