計算機操作系統(tǒng)第四版第3章處理機調(diào)度與死鎖

1、第三章 處理機調(diào)度與死鎖 第三章處理機調(diào)度與死鎖 3.1 處理機調(diào)度的層次處理機調(diào)度的層次3.2 調(diào)度隊列模型和調(diào)度算法的目標(biāo)調(diào)度隊列模型和調(diào)度算法的目標(biāo)3.3 調(diào)度算法調(diào)度算法3.4 實時調(diào)度實時調(diào)度 （不講）（不講）3.5 死鎖概述死鎖概述3.6 預(yù)防死鎖預(yù)防死鎖3.7 避免死鎖避免死鎖3.8 死鎖的檢測與解除死鎖的檢測與解除 第三章 處理機調(diào)度與死鎖 （1 1）作業(yè)）作業(yè) 作業(yè)是一個比程序更為廣泛的概念，它不僅包含作業(yè)是一個比程序更為廣泛的概念，它不僅包含了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份了通常的程序和數(shù)據(jù)，而且還應(yīng)配有一份作業(yè)說作業(yè)說明書明書，系統(tǒng)根據(jù)該說明書來對程序的運行進行控系統(tǒng)

2、根據(jù)該說明書來對程序的運行進行控制制。 在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)在批處理系統(tǒng)中，是以作業(yè)為基本單位從外存調(diào)入內(nèi)存的。入內(nèi)存的。 批處理系統(tǒng)作業(yè)處理作業(yè)的基本概念第三章 處理機調(diào)度與死鎖 （2）作業(yè)步 在作業(yè)運行期間，每個作業(yè)都必須經(jīng)過若干個相對獨立，又相互關(guān)聯(lián)的順序加工步驟才能得到結(jié)果，把其中的每一個加工步驟稱為一個作業(yè)步。 典型的作業(yè)控制過程： “編譯”、“鏈接裝配”、“運行”批處理系統(tǒng)作業(yè)處理作業(yè)的基本概念第三章 處理機調(diào)度與死鎖 典型的作業(yè)步典型的作業(yè)步編譯編譯連接裝配連接裝配運行運行目標(biāo)目標(biāo)程序程序段段目標(biāo)目標(biāo)程序程序源程序源程序輸入數(shù)據(jù)輸入數(shù)據(jù)子程序子程序庫函數(shù)庫函

3、數(shù)動態(tài)庫函數(shù)動態(tài)庫函數(shù)計算結(jié)果計算結(jié)果作業(yè)的基本概念第三章 處理機調(diào)度與死鎖 （3）作業(yè)流 若干個作業(yè)進入系統(tǒng)后，被依次存放在外存上，這便形成了輸入作業(yè)流； 在操作系統(tǒng)的控制下，逐個作業(yè)進行處理，于是便形成了處理作業(yè)流。批處理系統(tǒng)作業(yè)處理作業(yè)的基本概念第三章 處理機調(diào)度與死鎖 （1）作業(yè)控制語言作業(yè)說明書是用戶用于描述批處理作業(yè)處理過程控制意圖的一種特殊程序。書寫作業(yè)說明書的語言稱為作業(yè)控制語言（JCL）（2）作業(yè)控制語言的類別 包括：I/O命令、編譯命令、操作命令以及條件命令等（3）作業(yè)說明書表達(dá)用戶對作業(yè)的控制意圖內(nèi)容：作業(yè)的基本描述作業(yè)控制描述資源要求描述批處理作業(yè)控制語言與作業(yè)說明書第

4、三章 處理機調(diào)度與死鎖 （1）作業(yè)控制塊（JCB：Job Control Block）是批處理作業(yè)在系統(tǒng)中存在的標(biāo)志，保存有系統(tǒng)對于作業(yè)進行管理和調(diào)度所需的全部信息，位于磁盤區(qū)域中。作業(yè)控制塊JCB和作業(yè)：一一對應(yīng)關(guān)系（2）作業(yè)控制塊的內(nèi)容作業(yè)控制塊中所包含的信息數(shù)量及內(nèi)容因系統(tǒng)而異作業(yè)控制塊與作業(yè)表作業(yè)標(biāo)識作業(yè)標(biāo)識用戶名稱用戶名稱用戶帳號用戶帳號調(diào)度信息調(diào)度信息資源需求資源需求作業(yè)狀態(tài)作業(yè)狀態(tài)作業(yè)類型作業(yè)類型輸入井地址輸入井地址輸出井地址輸出井地址進入系統(tǒng)時間進入系統(tǒng)時間開始處理時間開始處理時間作業(yè)完成時間作業(yè)完成時間作業(yè)退出時間作業(yè)退出時間資源使用情況資源使用情況第三章 處理機調(diào)度與死鎖

5、（3）作業(yè)控制塊的建立 當(dāng)作業(yè)開始由輸入設(shè)備向磁盤的輸入井傳輸時，作業(yè)注冊程序為其建立一個作業(yè)控制塊，進行初始化，初始化的大部分信息取自作業(yè)說明書。（4）作業(yè)控制塊的使用需要訪問作業(yè)控制塊的程序：作業(yè)注冊程序作業(yè)調(diào)度程序作業(yè)控制程序系統(tǒng)輸出程序 終止作業(yè)程序作業(yè)控制塊與作業(yè)表第三章 處理機調(diào)度與死鎖 （5）作業(yè)控制塊的撤消作業(yè)執(zhí)行完成后，其作業(yè)控制塊由系統(tǒng)撤消作業(yè)控制塊被撤消后其作業(yè)也不復(fù)存在（6）作業(yè)表 每個作業(yè)有個作業(yè)控制塊 所有作業(yè)JCB構(gòu)成一個作業(yè)表 作業(yè)表存放在外存固定區(qū)域中，長度是固定的 限制了系統(tǒng)所能同時容納的作業(yè)數(shù)量JCB1 JCB2 JCBi JCBn 作業(yè)表作業(yè)表作業(yè)控制塊

6、與作業(yè)表第三章 處理機調(diào)度與死鎖 一個作業(yè)從進入系統(tǒng)到運行結(jié)束，需要經(jīng)歷三個階段，處于三種狀態(tài)： “收容” “后備” “運行” “運行” “完成” “完成” 批處理作業(yè)的狀態(tài)及轉(zhuǎn)換第三章 處理機調(diào)度與死鎖 作業(yè)和進程的狀態(tài)轉(zhuǎn)換圖作業(yè)和進程的狀態(tài)轉(zhuǎn)換圖數(shù)據(jù)數(shù)據(jù)完成狀態(tài)完成狀態(tài)后備狀態(tài)后備狀態(tài)運行狀態(tài)運行狀態(tài)作業(yè)控制進程作業(yè)控制進程 輸入設(shè)備輸入設(shè)備數(shù)據(jù)數(shù)據(jù)源程序源程序輸出設(shè)備輸出設(shè)備作業(yè)說作業(yè)說明書明書輸輸入入井井運行運行等待等待就緒就緒輸輸出出井井輸輸入入程程序序輸輸出出程程序序作作業(yè)業(yè)調(diào)調(diào)度度進程進程調(diào)度調(diào)度批處理作業(yè)的狀態(tài)及轉(zhuǎn)換第三章 處理機調(diào)度與死鎖 分時系統(tǒng)中用戶控制作業(yè)的執(zhí)行大致有四

7、個階段：終端的連接用戶登錄控制作業(yè)執(zhí)行用戶退出分時系統(tǒng)的作業(yè)管理第三章 處理機調(diào)度與死鎖 (1) 終端的連接必須使終端設(shè)備與計算機系統(tǒng)在線路上接通近程終端是直接與計算機系統(tǒng)連接的，當(dāng)終端設(shè)備加電后，終端就與計算機系統(tǒng)在線路上接通了遠(yuǎn)程終端通過租用專線或交換線接到計算機系統(tǒng)，在終端加電后用戶還需通過電話撥號進行呼叫，直到接通分時系統(tǒng)的作業(yè)管理第三章 處理機調(diào)度與死鎖 (2) 用戶登錄用戶必須向系統(tǒng)登錄用戶首先輸入“登錄”命令（LOGON）命令 系統(tǒng)會向詢問用戶名、作業(yè)名、口令和資源需求等經(jīng)過識別用戶、核對口令，系統(tǒng)在終端上顯示“已登錄”和進入系統(tǒng)的時間等信息若口令不對或資源暫時不能滿足時，則系統(tǒng)

8、在終端上顯示“登錄不成功”并給出登錄失敗的原因用戶的登錄過程可看作是對終端作業(yè)的作業(yè)調(diào)度分時系統(tǒng)的作業(yè)管理第三章 處理機調(diào)度與死鎖 (3) 控制作業(yè)執(zhí)行登錄成功的終端用戶可從終端上輸入作業(yè)的程序和數(shù)據(jù)使用系統(tǒng)提供的命令語言或會話語句控制作業(yè)執(zhí)行每輸入一命令或一會話語句后，由系統(tǒng)解釋執(zhí)行且在終端上顯示執(zhí)行成功或問題由用戶決定下一步命令或會話直到作業(yè)完成分時系統(tǒng)的作業(yè)管理第三章 處理機調(diào)度與死鎖 (4) 用戶退出用戶輸入“退出”命令（LOGOFF 命令）請求退出系統(tǒng)系統(tǒng)接收命令后就收回該用戶所占的資源讓其退出同時在終端上顯示“退出時間”或“使用系統(tǒng)時間”分時系統(tǒng)的作業(yè)管理第三章 處理機調(diào)度與死鎖

9、處理機調(diào)度即對處理機進行分配。處理機調(diào)度即對處理機進行分配。 批處理系統(tǒng)中，一個作業(yè)，從進入系統(tǒng)并駐留在外存的后備隊列上開始，直到作業(yè)運行完成，可能要經(jīng)歷三級處理機調(diào)度：高級調(diào)度高級調(diào)度中級調(diào)度中級調(diào)度低級調(diào)度低級調(diào)度3.1 處理機調(diào)度的層次處理機調(diào)度的層次第三章 處理機調(diào)度與死鎖 1、高級調(diào)度、高級調(diào)度(High-Level Scheduling) 又稱為作業(yè)調(diào)度、長程調(diào)度、接納調(diào)度。 任務(wù)任務(wù)：（1）根據(jù)作業(yè)控制塊中的信息，審查系統(tǒng)中的資源能否滿足用戶作業(yè)對資源的需求。（2）按照一定的算法，從外存的后備隊列中選取某些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源。然后再將新創(chuàng)建的進程插入就

10、緒隊列，準(zhǔn)備執(zhí)行。 兩個決定兩個決定：（1）接納多少個作業(yè)取決于多道程序度（2）接納哪些作業(yè)取決于所采用的調(diào)度算法第三章 處理機調(diào)度與死鎖 2、低級調(diào)度、低級調(diào)度(Low-Level Scheduling) 又稱為進程調(diào)度、短程調(diào)度。 主要功能主要功能：(1) 保存當(dāng)前進程的處理機的現(xiàn)場信息。(2) 按某種算法從就緒隊列中選取一個進程，把它的狀態(tài)改為運行狀態(tài)，并準(zhǔn)備把處理機分配給它。 (3) 把處理器分配給進程。由分派程序把處理器分配給被選中的進程。為選中的進程恢復(fù)處理機現(xiàn)場，把處理器的控制權(quán)交給該進程。第三章 處理機調(diào)度與死鎖 (1) 排隊器 排隊器把系統(tǒng)中的所有就緒進程按照一定策略排成一個

11、或多個隊列。(2) 分派器(分派程序)。分派器把由進程調(diào)度程序所選定的進程，從就緒隊列中取出，然后進行上下文切換，將處理機分配給它 (3) 上下文切換器第一對：當(dāng)前進程上下文分派程序上下文第二對：分派程序上下文新選進程上下文進程調(diào)度中的三個基本機制進程調(diào)度中的三個基本機制第三章 處理機調(diào)度與死鎖 進程調(diào)度方式進程調(diào)度方式1 1非搶占方式（非剝奪式調(diào)度）非搶占方式（非剝奪式調(diào)度） 原理：一旦把處理機分配給某進程后，便讓該進程一直執(zhí)行，直至該進程完成或發(fā)生某事件而被阻塞時，才再把處理機分配給其他進程，決不允許某進程搶占已經(jīng)分配出去的處理機。 引起進程調(diào)度的原因：（1）正在執(zhí)行的進程執(zhí)行完畢或因發(fā)生

12、某事件而無法再繼續(xù)運行；（2）正在執(zhí)行的進程提出I/O請求而暫停執(zhí)行；（3） 進程通信或同步過程中，執(zhí)行了某種原語操作（Block）。 特點：實現(xiàn)簡單，系統(tǒng)開銷較小，但不能反映各個進程重要、緊急程度的差異，難以滿足緊急任務(wù)的要求。第三章 處理機調(diào)度與死鎖 進程調(diào)度方式進程調(diào)度方式2 2搶占方式（剝奪式調(diào)度）搶占方式（剝奪式調(diào)度）原理：允許調(diào)度程序根據(jù)某種原則，暫停某個正在執(zhí)行的進程，將已分配給該進程的處理機重新分配給另一進程。搶占原則：（1）優(yōu)先權(quán)原則（2）短進程優(yōu)先原則 （3）時間片原則特點：反映了進程的優(yōu)先級特征，系統(tǒng)能及時處理緊急事件，但可能導(dǎo)致較大的系統(tǒng)開銷，算法也相對復(fù)雜一些。第三章

13、 處理機調(diào)度與死鎖 3、中級調(diào)度、中級調(diào)度(Intermediate-Level Scheduling) 又稱為中程調(diào)度、內(nèi)存調(diào)度。 引入了掛起狀態(tài)的操作系統(tǒng)中有中級調(diào)度。 中級調(diào)度：用來決定把外存上的哪些又具備運行條件的靜止就緒進程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為活動就緒狀態(tài)，掛在活動就緒隊列上等待進程調(diào)度。第三章 處理機調(diào)度與死鎖 3.2 調(diào)度隊列模型和調(diào)度算法的目調(diào)度隊列模型和調(diào)度算法的目標(biāo)標(biāo)3.2.1調(diào)度隊列模型調(diào)度隊列模型三種類型的調(diào)度隊列模型：一僅有進程調(diào)度的調(diào)度隊列模型二具有高級調(diào)度和低級調(diào)度的調(diào)度隊列模型三同時具有三級調(diào)度的調(diào)度隊列模型 第三章 處理機調(diào)度與死鎖 一僅有進程調(diào)度的

14、調(diào)度隊列模型分時系統(tǒng) 在分時系統(tǒng)中，用戶鍵入的命令和數(shù)據(jù)，都直接送入內(nèi)存。對于命令，由OS為之建立的一個進程。 僅有進程調(diào)度的調(diào)度隊列模型：就 緒 隊 列阻 塞 隊 列進程調(diào)度CPU進程完成等待事件交互用戶事件出現(xiàn)時間片完第三章 處理機調(diào)度與死鎖 二具有高級調(diào)度和低級調(diào)度的調(diào)度隊列模型批處理系統(tǒng)就 緒 隊 列進程調(diào)度CPU進程完成等待事件 1作業(yè)調(diào)度事件1出現(xiàn)時間片完等待事件 2事件2出現(xiàn)等待事件 n事件n出現(xiàn)后 備 隊 列第三章 處理機調(diào)度與死鎖 三同時具有三級調(diào)度的調(diào)度隊列模型就緒隊列進程調(diào)度CPU就緒，掛起隊列中級調(diào)度阻塞，掛起隊列阻塞隊列等待事件進程完成時間片完作業(yè)調(diào)度交互型作業(yè)后備隊

15、列批量作業(yè)掛起事件出現(xiàn)事件出現(xiàn)第三章 處理機調(diào)度與死鎖 3.2.2處理機調(diào)度算法的目標(biāo)處理機調(diào)度算法的目標(biāo)一、一、共同目標(biāo)共同目標(biāo) 1資源利用率 2公平性 3平衡性 4策略強制執(zhí)行第三章 處理機調(diào)度與死鎖 3.2.2處理機調(diào)度算法的目標(biāo)處理機調(diào)度算法的目標(biāo)二二批處理系統(tǒng)的目標(biāo)批處理系統(tǒng)的目標(biāo) 1平均周轉(zhuǎn)時間短平均周轉(zhuǎn)時間短 所謂周轉(zhuǎn)時間周轉(zhuǎn)時間，是指從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。它包括： （1）作業(yè)在外存后備隊列上等待調(diào)度的時間； （2）進程在就緒隊列上等待進程調(diào)度的時間； （3）進程在CPU上執(zhí)行的時間； （4）進程等待I/O操作完成的時間。第三章 處理機調(diào)度與死鎖 平

16、均周轉(zhuǎn)時間平均周轉(zhuǎn)時間可描述為：T=(Ti)/n; (i=1,2,.,n) 作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供的實際服務(wù)時間Ts之比，即W=T/Ts稱為帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間。 平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間可表示為：W=(Ti/Tsi)/n; (i=1,2,.,n) 3.2.2處理機調(diào)度算法的目標(biāo)處理機調(diào)度算法的目標(biāo)二二批處理系統(tǒng)的目標(biāo)批處理系統(tǒng)的目標(biāo) 第三章 處理機調(diào)度與死鎖 3.2.2處理機調(diào)度算法的目標(biāo)處理機調(diào)度算法的目標(biāo)二二批處理系統(tǒng)的目標(biāo)批處理系統(tǒng)的目標(biāo) 2系統(tǒng)吞吐量高系統(tǒng)吞吐量高3 處理機利用率高處理機利用率高第三章 處理機調(diào)度與死鎖 3.2.2處理機調(diào)度算法的目標(biāo)處理機調(diào)度算法

17、的目標(biāo)三三分時系統(tǒng)的目標(biāo)分時系統(tǒng)的目標(biāo) 1響應(yīng)時間快響應(yīng)時間快 是從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間，或說直到在屏幕上顯示出結(jié)果為止的一段時間間隔。它包括：(1）從鍵盤輸入的請求信息傳送到處理機的時間； (2）處理機對請求信息進行處理的時間； (3）將所形成的響應(yīng)回送到終端顯示器的時間。2均衡性均衡性 是指系統(tǒng)響應(yīng)時間的快慢應(yīng)與用戶所是指系統(tǒng)響應(yīng)時間的快慢應(yīng)與用戶所請求服務(wù)的復(fù)雜性相適應(yīng)。請求服務(wù)的復(fù)雜性相適應(yīng)。第三章 處理機調(diào)度與死鎖 3.2.2處理機調(diào)度算法的目標(biāo)處理機調(diào)度算法的目標(biāo)四四實時系統(tǒng)的目標(biāo)實時系統(tǒng)的目標(biāo) 1.截止時間的保證截止時間的保證 所謂截止時間

18、截止時間，是指某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間。2.可預(yù)測性可預(yù)測性第三章 處理機調(diào)度與死鎖 3.3調(diào)度算法調(diào)度算法 作業(yè)調(diào)度的職責(zé)作業(yè)調(diào)度的職責(zé)就是根據(jù)一定的算法，從多個在外存上處于后備隊列中的作業(yè)中選擇其中一些調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源，然后，再將新創(chuàng)建的進程排在就緒隊列上，準(zhǔn)備執(zhí)行。 進程調(diào)度的職責(zé)進程調(diào)度的職責(zé)就是根據(jù)一定的算法，從多個就緒進程中選擇其中之一來占用CPU。從宏觀上講，進程調(diào)度把一個物理上的CPU變?yōu)槎鄠€邏輯上的CPU。第三章 處理機調(diào)度與死鎖 3.3調(diào)度算法調(diào)度算法 先來先服務(wù)(First Come First Served,FCFS)

19、 短作業(yè)(進程) 優(yōu)先(Shortest Job First,SJF或Shortest Process First,SPF) 時間片輪轉(zhuǎn)調(diào)度算法(Round Robin ,RR) 優(yōu)先級調(diào)度算法(Priority-Scheduling Algorithm,PSA) 高響應(yīng)比優(yōu)先調(diào)度算法 (Highest Response Ratio Next, HRRF) 多隊列調(diào)度算法 多級反饋隊列調(diào)度算法第三章 處理機調(diào)度與死鎖 先來先服務(wù)調(diào)度算法（先來先服務(wù)調(diào)度算法（FCFS） FCFS調(diào)度算法最簡單，既適合于作業(yè)調(diào)度，又適合于進程調(diào)度。 作業(yè)調(diào)度：每次調(diào)度是從后備作業(yè)隊列中，選擇一個或多個最先進入該隊

20、列的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放人就緒隊列。 進程調(diào)度：每次調(diào)度是從就緒隊列中，選擇一個最先進入該隊列的進程，把處理機分配給它，使之投入運行。該進程一直運行到完成或發(fā)生某事件而阻塞后，才放棄處理機。第三章 處理機調(diào)度與死鎖 先來先服務(wù)調(diào)度算法（先來先服務(wù)調(diào)度算法（FCFS） 特點：有利于長作業(yè)（進程），不利于短作業(yè)（進程），有利于CPU繁忙型的作業(yè)，不利于I/O繁忙型的作業(yè)。 CPU繁忙型作業(yè)繁忙型作業(yè)：需要大量的 CPU時間進行計算 I/O繁忙型作業(yè)繁忙型作業(yè)：需頻繁地請求I/O，每次I/O的操作時間很短 例：下表列出了A、B、C、D四個作業(yè)第三章 處理機調(diào)度與死鎖

21、 例考慮5個進程P1，P2，P3，P4，P5，見下表。規(guī)定進程的優(yōu)先數(shù)越小，優(yōu)先級越高。試描述在采用先來先服務(wù)調(diào)度算法時各個進程運行過程，并計算進程平均周轉(zhuǎn)時間。假設(shè)忽略進程的調(diào)度時間。第三章 處理機調(diào)度與死鎖 短作業(yè)（進程）優(yōu)先調(diào)度算法（短作業(yè)（進程）優(yōu)先調(diào)度算法（SJPF） 對短作業(yè)或短進程優(yōu)先調(diào)度。 短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法 每次調(diào)度是從后備作業(yè)隊列中，選擇一個或多個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放人就緒隊列。 短進程優(yōu)先調(diào)度算法短進程優(yōu)先調(diào)度算法每次調(diào)度是從就緒隊列中，選擇一個估計運行時間最短的進程，把處理機分配給它，使之投入運行。該

22、進程一直運行到完成或發(fā)生某事件而阻塞后，才放棄處理機。第三章 處理機調(diào)度與死鎖 例：下表列出了例：下表列出了A A、B B、C C、D D、E E五個作業(yè)五個作業(yè)FCFS和和SJPF比較比較 第三章 處理機調(diào)度與死鎖 SJPF算法的特點算法的特點 SJPF算法優(yōu)點算法優(yōu)點：能有效地降低作業(yè)的平均等待時間，提高系統(tǒng)吞吐量。 SJPF算法缺點算法缺點：(1) 對長作業(yè)不利，可能導(dǎo)致長作業(yè)（進程）長期不被調(diào)度。(2) 完全沒有考慮到作業(yè)的緊迫程度，因而不能保證緊迫作業(yè)（進程）會被及時處理。(3)該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。第三章 處理機調(diào)度與死鎖 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法 既可用于作業(yè)

23、調(diào)度，也可用于進程調(diào)度。 作業(yè)調(diào)度作業(yè)調(diào)度：系統(tǒng)為每個作業(yè)設(shè)置一個優(yōu)先數(shù)（對應(yīng)一個優(yōu)先權(quán)），每次調(diào)度是從后備作業(yè)隊列中，選擇若干個優(yōu)先權(quán)最優(yōu)先權(quán)最高高的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放人就緒隊列。 進程調(diào)度進程調(diào)度：系統(tǒng)為每個進程設(shè)置一個優(yōu)先數(shù)（對應(yīng)一個優(yōu)先權(quán)），每次調(diào)度是從就緒隊列中，選擇一個優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進程，把處理機分配給它，使之投入運行。可進一步把該算法分為非搶占(非剝奪)式優(yōu)先級調(diào)度算法和搶占(剝奪)式優(yōu)先級調(diào)度算法。第三章 處理機調(diào)度與死鎖 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法 非搶占式優(yōu)先權(quán)調(diào)度非搶占式優(yōu)先權(quán)調(diào)度：系統(tǒng)一旦把CPU分配給優(yōu)先權(quán)最高的進程后，該

24、進程便一直執(zhí)行下去，僅當(dāng)該進程運行結(jié)束或因發(fā)生某事件不能繼續(xù)運行時，系統(tǒng)才進行重新調(diào)度。 優(yōu)缺點：進程切換次數(shù)少，系統(tǒng)開銷??；可能導(dǎo)致優(yōu)先級低的進程長期搶占不到CPU。 搶占式優(yōu)先權(quán)調(diào)度搶占式優(yōu)先權(quán)調(diào)度：系統(tǒng)把CPU分配給優(yōu)先權(quán)最高的進程，使之執(zhí)行。但在其執(zhí)行期間，當(dāng)系統(tǒng)中有另一優(yōu)先權(quán)更高的進程變成就緒狀態(tài)時，系統(tǒng)就立即剝奪現(xiàn)運行進程占用CPU的權(quán)力，使新到的優(yōu)先權(quán)更高的進程投入運行。 優(yōu)缺點：反映了進程的優(yōu)先權(quán)特征，使系統(tǒng)能及時處理緊急事件；系統(tǒng)開銷較大。第三章 處理機調(diào)度與死鎖 例考慮5個進程P1，P2，P3，P4，P5，見下表。規(guī)定進程的優(yōu)先數(shù)越小，優(yōu)先級越高。試描述在采用下述幾種調(diào)度算

25、法時各個進程運行過程，并計算采用每種算法時的進程平均周轉(zhuǎn)時間。假設(shè)忽略進程的調(diào)度時間。（1）非剝奪(非搶占)式優(yōu)先級調(diào)度等法；（2）剝奪(搶占)式優(yōu)先級調(diào)度算法。第三章 處理機調(diào)度與死鎖 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法 優(yōu)先級優(yōu)先級是利用某一范圍內(nèi)的一個整數(shù)來表示。例如，07或0255中的某一整數(shù)，又稱該整數(shù)為優(yōu)先數(shù)優(yōu)先數(shù)。 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法的關(guān)鍵關(guān)鍵： 優(yōu)先級的類型(靜態(tài)優(yōu)先級、動態(tài)優(yōu)先級) 如何確定進程的優(yōu)先級。 確定進程優(yōu)先級的依據(jù)確定進程優(yōu)先級的依據(jù)有：（1）進程類型進程類型。系統(tǒng)進程的優(yōu)先權(quán)高于一般用戶進程的優(yōu)先權(quán)。（2）進程對資源的需求進程對資源的需求。如估計執(zhí)行時間短及

26、資源需求量少的進程，應(yīng)賦予較高的優(yōu)先權(quán)。（3）用戶要求用戶要求。由用戶進程的緊迫程度及用戶所付費用的多少來定第三章 處理機調(diào)度與死鎖 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法優(yōu)先級的類型優(yōu)先級的類型1靜態(tài)優(yōu)先級靜態(tài)優(yōu)先級是在創(chuàng)建進程時確定的，且規(guī)定它在進程的整個運行期間保持不變。 靜態(tài)優(yōu)先級法簡單易行、系統(tǒng)開銷小，但不夠精確，很可能出現(xiàn)優(yōu)先級低的作業(yè)（進程）長期沒有被調(diào)度的情況，僅在要求不太高的系統(tǒng)中使用。 第三章 處理機調(diào)度與死鎖 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法優(yōu)先級的類型優(yōu)先級的類型2動態(tài)優(yōu)先級動態(tài)優(yōu)先級是指在創(chuàng)建進程時所賦予的優(yōu)先級，是可以隨進程的推進或隨其等待時間的增加而改變的。 在就緒隊列中的進程

27、，隨其等待時間的增長，其優(yōu)先級以在就緒隊列中的進程，隨其等待時間的增長，其優(yōu)先級以速率速率a增加。增加。優(yōu)先級較低的進程在等待足夠的時間后，其優(yōu)先級將提高到可被調(diào)度執(zhí)行。 若所有進程具有相同的優(yōu)先級初值，相當(dāng)于FCFS算法。 若所有進程具有各不相同的優(yōu)先級初值，對于優(yōu)先級初值低的進程，在等待足夠的時間后，其優(yōu)先級便可能升為最高，從而可以獲得處理機執(zhí)行。 進程每執(zhí)行一個時間片，其優(yōu)先級就以速率進程每執(zhí)行一個時間片，其優(yōu)先級就以速率b下降下降，從而一個進程持續(xù)執(zhí)行時，其優(yōu)先級將降低到出讓CPU。防止一個長作業(yè)長期地壟斷處理機。第三章 處理機調(diào)度與死鎖 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 既可

28、用于作業(yè)調(diào)度，也可用于進程調(diào)度。 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法把短作業(yè)優(yōu)先調(diào)度算法和動態(tài)動態(tài)優(yōu)先級機制優(yōu)先級機制結(jié)合起來。作業(yè)優(yōu)先級的變化規(guī)律描述為 等待時間加上要求服務(wù)時間，就是系統(tǒng)對該作業(yè)的響應(yīng)時響應(yīng)時間間，故該優(yōu)先級又相當(dāng)于響應(yīng)比Rp。即第三章 處理機調(diào)度與死鎖 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 作業(yè)調(diào)度作業(yè)調(diào)度：系統(tǒng)為每個作業(yè)設(shè)置一個響應(yīng)比，作業(yè)的等待時間越長，響應(yīng)比越高。每次調(diào)度是從后備作業(yè)隊列中，選擇若干個響應(yīng)比最高響應(yīng)比最高的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進程，然后放入就緒隊列。 進程調(diào)度進程調(diào)度：系統(tǒng)為每個進程設(shè)置一個響應(yīng)比。每次調(diào)度是從就緒隊列

29、中，選擇一個響應(yīng)比最高響應(yīng)比最高的進程，把處理機分配給它，使之投入運行。 每當(dāng)要進行調(diào)度之前，先做響應(yīng)比的計算。 當(dāng)響應(yīng)比相同時，第一時間調(diào)度的必然是最短的作業(yè)。第三章 處理機調(diào)度與死鎖 高響應(yīng)比優(yōu)先調(diào)度算法的特點高響應(yīng)比優(yōu)先調(diào)度算法的特點高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法 (1)如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其響應(yīng)比愈高，因而該算法有利短作業(yè)。 (2)當(dāng)要求服務(wù)的時間相同時，作業(yè)的響應(yīng)比決定于其等待時間。因此它實現(xiàn)的是先來先服務(wù)。 (3)對于長作業(yè)，作業(yè)的響應(yīng)比可以隨著等待時間的增加而以速率a提高，也可獲得處理機。 既照顧了短作業(yè)，又不致使長作業(yè)的等待時間過長，從而改善

30、了處理機調(diào)度性能。第三章 處理機調(diào)度與死鎖 例有三個作業(yè)A(到達(dá)時間8:50，執(zhí)行時間1.5小時)、B(到達(dá)時間9:30，執(zhí)行時間0.4小時)、C(到達(dá)時間9:30，執(zhí)行時間1小時)。當(dāng)作業(yè)全部到達(dá)后，批處理單道系統(tǒng)按照響應(yīng)比高者優(yōu)先算法進行調(diào)度，則作業(yè)被選中的次序是（）A、(ABC) B、(BAC) C、(BCA) D、(CBA) E、(CAB) F、(ACB)高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法第三章 處理機調(diào)度與死鎖 時間片輪轉(zhuǎn)調(diào)度算法時間片輪轉(zhuǎn)調(diào)度算法(RR)基本思想基本思想： 系統(tǒng)將所有的就緒進程按先來先服務(wù)的原則，排成一個隊列，并把CPU的處理時間劃分成一個個時間片，就緒隊列中

31、的每個進程輪流運行一個時間片。 當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，去激活進程調(diào)度程序進行調(diào)度。調(diào)度程序便據(jù)此中斷信號來停止當(dāng)前進程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進程，同時也讓它執(zhí)行一個時間片。 時間片大小的選擇非常重要。一個較為可取的大小是，時間片略大于一次典型的交互所需要的時間。這樣可使大多數(shù)進程在一個時間片內(nèi)完成，獲得很小的響應(yīng)時間。第三章 處理機調(diào)度與死鎖 例考慮5個進程P1，P2，P3，P4，P5，見下表。試描述在采用時間片輪轉(zhuǎn)調(diào)度算法（時間片為1ns）時各個進程運行過程，并計算進程平均周轉(zhuǎn)時間。假設(shè)忽略進程的調(diào)度時間。第三

32、章 處理機調(diào)度與死鎖 基本思想基本思想： 設(shè)置多個就緒隊列，將不同類型或性質(zhì)的進程固定分配在不同的就緒隊列； 不同的就緒隊列采用不同的調(diào)度算法； 一個就緒隊列中的進程可以設(shè)置不同的優(yōu)先級，不同的就緒隊列本身也可以設(shè)置不同的優(yōu)先級。優(yōu)點：系統(tǒng)可以針對不同用戶進程的需求，提供多種調(diào)度策略。多隊列調(diào)度算法多隊列調(diào)度算法（多處理機系統(tǒng)使用）（多處理機系統(tǒng)使用）第三章 處理機調(diào)度與死鎖 設(shè)置多個就緒隊列設(shè)置多個就緒隊列，分別賦予不同的優(yōu)先級，如逐級降低。每個隊列中進程執(zhí)行時間片的長度也不同，優(yōu)先級越低，時間片越長。每個隊列都采用每個隊列都采用FCFSFCFS算法。算法。當(dāng)一個新進程進入內(nèi)存后，先將它放入

33、第一個隊列的末尾，按FCFS算法調(diào)度；若在第一個隊列的一個時間片未能執(zhí)行完，則降低投入到第二個隊列的末尾，同樣按FCFS算法調(diào)度；如此下去，降低到最后的隊列，則按時間片輪轉(zhuǎn)算法調(diào)度直到完成。按隊列優(yōu)先級調(diào)度。按隊列優(yōu)先級調(diào)度。僅當(dāng)較高優(yōu)先級的隊列空閑時，調(diào)度程序才調(diào)度較低優(yōu)先級的隊列中的進程執(zhí)行。如果進程執(zhí)行時有新進程進入較高優(yōu)先級的隊列，則搶先執(zhí)行新進程，并把被搶先的進程投入原隊列的末尾。調(diào)度機制：調(diào)度機制：多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法第三章 處理機調(diào)度與死鎖 終端型進程(屬于交互型進程，通常較?。?讓其進入最高優(yōu)先級隊列，以及時響應(yīng)I/O交互。通常執(zhí)行一個小時間片，要求可在最高

34、優(yōu)先級隊列所規(guī)定的時間片內(nèi)處理完一次I/O請求的數(shù)據(jù)，然后轉(zhuǎn)入到阻塞隊列。其周轉(zhuǎn)時間很短。 短批處理型進程：通常只需在前幾個隊列中各執(zhí)行一個時間片即可完成，其周轉(zhuǎn)時間仍然很短。 長批處理型(計算型)進程：每次都執(zhí)行完時間片，進入更低級隊列。最終采用最大時間片按輪轉(zhuǎn)方式來執(zhí)行，以減少調(diào)度次數(shù)。多級反饋隊列調(diào)度算法的性能多級反饋隊列調(diào)度算法的性能第三章 處理機調(diào)度與死鎖 習(xí)題習(xí)題1、有5個待運行作業(yè)J1、J2、J3、J4、J5，各自預(yù)計運行時間分別是9、6、3、5、7。假定這些作業(yè)同時到達(dá)，并且在一臺處理機上按單道方式執(zhí)行。討論采用哪種調(diào)度算法和哪種運行次序?qū)⑹蛊骄苻D(zhuǎn)時間最短，平均周轉(zhuǎn)時間為多少

35、？2、有5個任務(wù)A、B、C、D、E，它們幾乎同時到達(dá)，預(yù)計它們的運行時間為10、6、2、4、8min。其優(yōu)先權(quán)分別為3、5、2、1、4，這里5為最高優(yōu)先權(quán)。對于下列每一種調(diào)度算法，計算其平均進程周轉(zhuǎn)時間(進程切換開銷可不考慮)。(1)先來先服務(wù)(按A、B、C、D、E)算法(2)優(yōu)先權(quán)調(diào)度算法(3)時間片輪轉(zhuǎn)算法第三章 處理機調(diào)度與死鎖 3.5死鎖概述死鎖概述3.5.1 資源問題資源問題可重用性資源和可消耗性資源 可重用性資源是指可供用戶重復(fù)使用多次的資源。系統(tǒng)中大多數(shù)資源都屬于此類。 可消耗性資源又稱臨時性資源，是指在進程運行期間，由進程動態(tài)的創(chuàng)建和消耗的。第三章 處理機調(diào)度與死鎖 3.5.1

36、 資源問題資源問題可搶占性資源和不可搶占性資源 可搶占性資源是指某進程在獲得這類資源后，該資源可以再被其他進程或系統(tǒng)搶占。如：CPU和主存都屬于可搶占性資源。 不可搶占性資源是指系統(tǒng)把這類資源分配給某進程后，再不能強行收回，只能在進程用完后自行釋放，如磁帶機、打印機等。第三章 處理機調(diào)度與死鎖 3.5.2產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因可歸結(jié)為：（1）競爭不可搶占性資源（2）競爭可消耗性資源（3）進程推進順序不當(dāng)?shù)谌?處理機調(diào)度與死鎖 例：有兩個進程PA和PB，它們在運行的過程中要共享使用兩個獨占設(shè)備R1和R2。設(shè)SR1：表示設(shè)備R1可用，初值為1；SR2表示設(shè)備R2可用，兩個進程

37、并發(fā)執(zhí)行的程序如下：PAPB3.5.2產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因競爭不可搶占性資源第三章 處理機調(diào)度與死鎖 進程推進順序非法引起死鎖進程推進順序非法引起死鎖1、進程推進順序合法、進程推進順序合法不會引起進程死鎖的推進順序2、進程推進順序非法、進程推進順序非法PAPBPAPB第三章 處理機調(diào)度與死鎖 死鎖的定義死鎖的定義 死鎖死鎖就是兩個或兩個以上的進程等候著一個永遠(yuǎn)不會發(fā)生的事件時所處的一種系統(tǒng)狀態(tài)。 兩個或兩個以上并發(fā)進程，如果每個進程持有某種資源，而又等待著別的進程釋放它或它們現(xiàn)在保持著的資源，否則就不能向前推進。此時，每個進程都占用了一定的資源，但又都不能向前推進。這種現(xiàn)象稱為死鎖死鎖

38、。 死鎖死鎖是指多個進程在運行過程中因競爭資源而造成的一種僵局，當(dāng)進程處于這種僵持狀態(tài)時，若無外力作用，它們都將無法再向前推進。 （教材）（教材）如果一組進程中的每一個進程都在等待僅由該組進程中的其它進程才能引發(fā)的事件，那么這組進程是死鎖死鎖的。第三章 處理機調(diào)度與死鎖 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件1互斥條件互斥條件進程對所分配到的資源進行排它性使用 2請求和保持條件請求和保持條件進程處于等待資源狀態(tài)但又對自己已獲得的資源保持不放。 3不可搶占條件不可搶占條件進程已獲得的資源，在未使用完之前，不能被搶占，只能在使用完時由自己釋放。 4循環(huán)等待條件循環(huán)等待條件在發(fā)生死鎖時，必然存在一個進

39、程資源的環(huán)形鏈，即存在一組進程P1，P2，Pn，其中每一個進程都在等待另一個進程占用的資源，即P1等待P2占用的資源，P2等待P3占用的資源，P（n-1）等待Pn占用的資源，而Pn又等待P1所占用的資源。第三章 處理機調(diào)度與死鎖 處理死鎖的方法處理死鎖的方法1預(yù)防死鎖預(yù)防死鎖 通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個條件，來預(yù)防發(fā)生死鎖。 預(yù)防死鎖是一種較簡單和直觀的事先預(yù)防的方法，但由于其所施加的限制條件往往太嚴(yán)格，可能會導(dǎo)致系統(tǒng)資源利用率和系統(tǒng)吞吐量降低。第三章 處理機調(diào)度與死鎖 處理死鎖的方法處理死鎖的方法2避免死鎖避免死鎖 在資源的動態(tài)分配過程中，用某種方法去防

40、止系統(tǒng)進入不安全狀態(tài)，從而避免發(fā)生死鎖。 避免死鎖也是一種事先預(yù)防的方法，但較難實現(xiàn)。它只需事先加以較弱的限制條件，便可獲得較高的資源利用率和系統(tǒng)吞吐量。第三章 處理機調(diào)度與死鎖 處理死鎖的方法處理死鎖的方法3檢測死鎖檢測死鎖允許系統(tǒng)在運行過程中發(fā)生死鎖，但可通過系統(tǒng)所設(shè)置的檢測機構(gòu)，及時地檢測出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進程和資源；然后解除死鎖。4解除死鎖解除死鎖當(dāng)檢測到系統(tǒng)中已發(fā)生死鎖時，采取相應(yīng)措施，將進程從死鎖狀態(tài)中解脫出來。常用的方法是撤消或掛起一些進程，以便回收一些資源，再將這些資源分配給已處于阻塞狀態(tài)的進程，使之轉(zhuǎn)為就緒狀態(tài)，以繼續(xù)運行。第三章 處理機調(diào)度與死鎖 3.6

41、預(yù)防死鎖預(yù)防死鎖 預(yù)防死鎖的方法預(yù)防死鎖的方法是使產(chǎn)生死鎖的四個必要條件使產(chǎn)生死鎖的四個必要條件中的第中的第2 2、3 3、4 4條件之一不能成立條件之一不能成立。 具體的方法有一、破壞“請求和保持”條件二、破壞”不可搶占”條件 三、破壞“循環(huán)等待”條件第三章 處理機調(diào)度與死鎖 破壞破壞“請求和保持請求和保持”條件條件靜態(tài)分配資源靜態(tài)分配資源 靜態(tài)分配靜態(tài)分配就是要求每一個進程在開始執(zhí)行前就一次性地申請它在整個執(zhí)行過程中所需要的全部資源，僅當(dāng)系統(tǒng)能滿足進程資源申請要求且把資源分配給進程后，該進程才能開始執(zhí)行。這種策略也稱預(yù)分配資源。 實現(xiàn)簡單，易行且安全。但降低了資源的利用率，并且使得進程延遲

42、運行。第三章 處理機調(diào)度與死鎖 破壞破壞“不可搶占不可搶占”條件條件搶占式分配資源法搶占式分配資源法： 在采用這種方法時，進程是逐個地提出對資源的要求的。 如果一個進程已經(jīng)占有了某些不可搶占性資源又要申請新的資源，而新的資源請求不能立即得到滿足必須等待時，它必須釋放已經(jīng)保持的所有資源，待以后需要時再重新申請。 目前搶占式分配策略只適用于主存空間和處理器，而對打印機、磁帶機等不能采用這種分配策略。第三章 處理機調(diào)度與死鎖 破壞破壞“循環(huán)等待循環(huán)等待”條件條件采用按序分配資源法： 把系統(tǒng)中所有資源按類型排一個順序，并賦予每一個資源一個確定編號(例如打印機為1、磁帶機為2、磁盤為3、等等)，規(guī)定任何

43、一個進程申請兩個以上的資源時，總是先申請編號小的資源，再申請編號大的資源。第三章 處理機調(diào)度與死鎖 例如，系統(tǒng)共有m個資源，假定編號為1，2，m，于是這m個資源是 r1，r2， rm 任何一個進程在得到了資源ri之后，若再申請資源rj，則必定是ij?？梢宰C明按這種策略分配資源時不會出現(xiàn)循環(huán)等待資源的情況。 可用反證法，假定有循環(huán)等待資源的情況，則一定存在一組進程p1，p2，pn，其中每一個進程Pi（i=1，2，nl）都在等待資源rki（lkim），而資源rki已被進程pi+1占用， pn等待的資源被P1占用。依照按序分配的資源分配原則可推出knk1k2k(n-1)kn于是，發(fā)生了knk1而k1

44、kn的矛盾。故存在循環(huán)等待資源的假設(shè)是不能成立的。三、摒棄三、摒棄“環(huán)路等待環(huán)路等待”條件條件第三章 處理機調(diào)度與死鎖 在避免死鎖避免死鎖的方法中，允許進程動態(tài)地申請資源，但把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)。系統(tǒng)在進程資源分配之前，應(yīng)先計算此次資源分配的安全性，若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則將資源分配給進程，否則等待。只要能使系統(tǒng)始終都處于安全狀態(tài)，便可避免發(fā)生死鎖。3.7 避免死鎖避免死鎖第三章 處理機調(diào)度與死鎖 所謂安全狀態(tài)安全狀態(tài)，是指系統(tǒng)能按某種順序如(稱序列為安全序列)，來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。 若系統(tǒng)

45、不存在這樣一個安全序列，稱系統(tǒng)處于不安全狀態(tài)不安全狀態(tài)。 雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當(dāng)系統(tǒng)進入不安全狀態(tài)后，便可能進而進入死鎖狀態(tài)；反之，只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進入死鎖狀態(tài)。 避免死鎖的實質(zhì)避免死鎖的實質(zhì)在于：如何使系統(tǒng)不進入不安全狀態(tài)。3.7.1 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài) 第三章 處理機調(diào)度與死鎖 假定系統(tǒng)有三個進程P1、P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。設(shè)在T0時刻，進程Pl、P2和P3已分別獲得5臺、2臺和2臺，尚有3臺空閑未分，如下表所示： 進程 最大需求 已分配 可用P1 10 5 3P2 4 2P3 9

46、 2在T0時刻，系統(tǒng)是否存在安全序列？系統(tǒng)是否安全？安全狀態(tài)之例安全狀態(tài)之例 第三章 處理機調(diào)度與死鎖 如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。 避免死鎖的基本思想避免死鎖的基本思想：確保系統(tǒng)始終處于安全狀態(tài)。由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 第三章 處理機調(diào)度與死鎖 3.7.2 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 避免死鎖算法中最有代表性的算法是Dijkstra E.W 于1968年提出的銀行家算法。 為實現(xiàn)銀行家算法，每一個新進程在進入系統(tǒng)時，它必須申明在運行過程中，可能需要的每種資源類型的最大數(shù)目，其數(shù)目不應(yīng)超過系統(tǒng)所擁有的資源

47、總量。 銀行家算法：當(dāng)進程請求一組資源時，系統(tǒng)必須首先確定是否有足夠的資源分配給該進程。若有，再進一步計算在將這些資源分配給進程后，是否會使系統(tǒng)處于不安全狀態(tài)。如果不會，才將資源分配給它；否則，讓進程等待。第三章 處理機調(diào)度與死鎖 1.可利用資源向量可利用資源向量AvailableAvailable 是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目。2.最大需求矩陣最大需求矩陣MaxMax 是個nm的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Maxi，jk，表示進程i需要Rj類資源的最大數(shù)目為k。3.分配矩陣分配矩陣AllocationAllocat

48、ion是一個nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每個進程的資源數(shù)。如果Allocationi,jk，表示進程i當(dāng)前已分得Rj類資源的數(shù)目為k。4.需求矩陣需求矩陣NeedNeed是一個nm的矩陣，用以表示每一個進程尚需的各類資源數(shù)，如果Needi,j=k，表示進程i還需要Rj類資源k個，方能完成其任務(wù)。三矩陣間存在下述關(guān)系：三矩陣間存在下述關(guān)系：Needi,j = Maxi,j- Allocationi,jNeedi,j = Maxi,j- Allocationi,j一、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)一、銀行家算法中的數(shù)據(jù)結(jié)構(gòu)第三章 處理機調(diào)度與死鎖 設(shè)Requesti是進程是進程Pi的請

49、求向量的請求向量。如果Requestijk，表示進程Pi只需要k個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：(1)如果Requestij Needi,jNeedi,j，則轉(zhuǎn)向步驟2；否則，認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。(2)如果Requestij Availablejj，則轉(zhuǎn)向步驟3；否則，表示系統(tǒng)中尚無足夠的資源，Pi必須等待。(3)系統(tǒng)試探把要求的資源分配給進程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablejj:= Availablejj - Requestij;Allocationi,j := Allocationi,j + Reque

50、stij;Needi,j := Needi,j - Requestij;(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進程Pi等待。二、銀行家算法二、銀行家算法 第三章 處理機調(diào)度與死鎖 (1)設(shè)置兩個向量設(shè)置兩個向量、工作向量工作向量Work表示系統(tǒng)可提供給進程繼續(xù)運行所需要的各類資源數(shù)目，它含有m個元素，開始時，Work := Available。、Finish表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成，開始時Finishi:=false ；當(dāng)有足夠資源時，令Fi

51、nishi:=true 。(2)從進程集合中找到一個能滿足下述條件的進程從進程集合中找到一個能滿足下述條件的進程： Finishi:=false Needi,j=workj如找到，執(zhí)行步驟(3)；否則，執(zhí)行步驟(4)。(3)當(dāng)進程當(dāng)進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：的資源，故應(yīng)執(zhí)行：Workj:= Workj+ Allocationi,j ;Finishi:=true go to step 2；(4)如果所有進程的如果所有進程的Finishi=true，則表示系統(tǒng)處于安全狀態(tài)；否則，則表示系統(tǒng)處于安全狀

52、態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。系統(tǒng)處于不安全狀態(tài)。三、安全性算法三、安全性算法 第三章 處理機調(diào)度與死鎖 假定系統(tǒng)中有五個進程：P0，P1，P2，P3，P4和三種類型的資源A，B，C，每一種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖315所示。 資源情況進程MAXABCAllocationABCNeedABCAvailableABCP0753010743332(230)P1322200122(302)(020)P2902302600P3222211011P4433002431問：問：（1）當(dāng)前系統(tǒng)是否是安全的？（2）如果進程P1已發(fā)出資源請求向量(1，0，2)，系統(tǒng)能否將資源分配給它？若進程P4發(fā)出資源請求向量(3，3，0)呢？若進程P0發(fā)出資源請求向量(0，2，0)呢？四、銀行家算法之例