1、第三章 處理機(jī)調(diào)度與死鎖 第三章處理機(jī)調(diào)度與死鎖 3.1 處理機(jī)調(diào)度的層次與調(diào)度算法的目標(biāo)處理機(jī)調(diào)度的層次與調(diào)度算法的目標(biāo)3.2 作業(yè)與作業(yè)調(diào)度作業(yè)與作業(yè)調(diào)度3.3 進(jìn)程調(diào)度進(jìn)程調(diào)度3.4 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度 3.5 死鎖概述死鎖概述3.6 預(yù)防死鎖預(yù)防死鎖3.7 避免避免死鎖死鎖3.8 死鎖死鎖的檢測(cè)與解除的檢測(cè)與解除 第三章 處理機(jī)調(diào)度與死鎖 3.1 處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo) 3.1.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次1. 高級(jí)調(diào)度高級(jí)調(diào)度(High Level Scheduling) 又稱長程調(diào)度或作業(yè)調(diào)度，調(diào)度對(duì)象是作業(yè)。涉及兩個(gè)決定： 1) 接

2、納多少個(gè)作業(yè) ； 2) 接納哪些作業(yè)。 l 在多道程序系統(tǒng)中，調(diào)度的實(shí)質(zhì)是一種資源分配，處理機(jī)調(diào)度是對(duì)處理機(jī)資源進(jìn)行分配。處理機(jī)調(diào)度算法是根據(jù)處理機(jī)分配策略所規(guī)定的處理機(jī)分配算法。第三章 處理機(jī)調(diào)度與死鎖 3.1.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次2. 低級(jí)調(diào)度低級(jí)調(diào)度(Low Level Scheduling) 又稱短程調(diào)度或進(jìn)程調(diào)度，調(diào)度對(duì)象是進(jìn)程。主要功能是根據(jù)算法，決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，并由分派程序?qū)⑻幚頇C(jī)分配給被選中的進(jìn)程。3. 中級(jí)調(diào)度中級(jí)調(diào)度(Intermediate Scheduling) 又稱內(nèi)存調(diào)度。主要目的是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。將那些暫時(shí)不能

3、運(yùn)行的進(jìn)程調(diào)至外存上去等待，稱為就緒駐外存狀態(tài)或掛起狀態(tài)；把外存上的又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊(duì)列上等待進(jìn)程調(diào)度。 第三章 處理機(jī)調(diào)度與死鎖 3.1.2 處理機(jī)調(diào)度算法的目標(biāo)處理機(jī)調(diào)度算法的目標(biāo)1. 處理機(jī)調(diào)度算法的共同目標(biāo)處理機(jī)調(diào)度算法的共同目標(biāo)(1) 資源利用率。為提高系統(tǒng)的資源利用率，應(yīng)使系統(tǒng)中的處理機(jī)和其它所有資源都盡可能保持忙碌狀態(tài)?？臻e等待時(shí)間有效工作時(shí)間有效工作時(shí)間的利用率CPUCPUCPUCPU(2) 公平性使諸進(jìn)程都獲得合理的CPU時(shí)間，不會(huì)發(fā)生進(jìn)程饑餓現(xiàn)象。(3) 平衡性 保持系統(tǒng)資源使用的平衡性。(4) 策略強(qiáng)制執(zhí)行第三章 處

4、理機(jī)調(diào)度與死鎖 3.1.2 處理機(jī)調(diào)度算法的目標(biāo)處理機(jī)調(diào)度算法的目標(biāo)2. 批處理系統(tǒng)的目標(biāo)批處理系統(tǒng)的目標(biāo)平均周轉(zhuǎn)時(shí)間短 周轉(zhuǎn)時(shí)間，指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。包括四部分時(shí)間：作業(yè)在外存后備隊(duì)上等待調(diào)度的時(shí)間；進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間，進(jìn)程在CPU上執(zhí)行的時(shí)間，進(jìn)程等待I/O操作完成的時(shí)間。(2) 系統(tǒng)吞吐量高 吞吐量，指在單位時(shí)間內(nèi)系統(tǒng)所完成的作業(yè)數(shù)。(3) 處理機(jī)利用率高第三章 處理機(jī)調(diào)度與死鎖 3.1.2 處理機(jī)調(diào)度算法的目標(biāo)處理機(jī)調(diào)度算法的目標(biāo)3. 分時(shí)系統(tǒng)的目標(biāo)分時(shí)系統(tǒng)的目標(biāo)響應(yīng)時(shí)間快 響應(yīng)時(shí)間快是選擇分時(shí)系統(tǒng)中進(jìn)程調(diào)度算法的重要準(zhǔn)則。響應(yīng)時(shí)間，

5、從用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直到屏幕上顯示出處理結(jié)果為止的一段時(shí)間間隔。(2) 均衡性系統(tǒng)響應(yīng)時(shí)間的快慢應(yīng)與用戶所請(qǐng)求的復(fù)雜性相適應(yīng)。第三章 處理機(jī)調(diào)度與死鎖 3.1.2 處理機(jī)調(diào)度算法的目標(biāo)處理機(jī)調(diào)度算法的目標(biāo)4. 實(shí)時(shí)系統(tǒng)的目標(biāo)實(shí)時(shí)系統(tǒng)的目標(biāo)截止時(shí)間的保證 截止時(shí)間：某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。調(diào)度算法必須保證實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。(2) 可預(yù)測(cè)性第三章 處理機(jī)調(diào)度與死鎖 3.2 作業(yè)和作業(yè)調(diào)度作業(yè)和作業(yè)調(diào)度3.2.1 批處理系統(tǒng)中的作業(yè)批處理系統(tǒng)中的作業(yè)1. 作業(yè)和作業(yè)步作業(yè)和作業(yè)步在作業(yè)運(yùn)行期間，每個(gè)作業(yè)都必須經(jīng)過若干個(gè)相對(duì)獨(dú)立，又相互關(guān)聯(lián)的順序加工步驟

6、才能得到結(jié)果，每一個(gè)加工步驟稱為一個(gè)作業(yè)步。2. 作業(yè)控制塊（作業(yè)控制塊（Job Control Block, JCB）作業(yè)在系統(tǒng)中存在的標(biāo)志，其中保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。第三章 處理機(jī)調(diào)度與死鎖 3.2.1 批處理系統(tǒng)中的作業(yè)批處理系統(tǒng)中的作業(yè)3. 作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài)作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài)（1）收容階段 用戶提交的作業(yè)輸入到硬盤上，再為該作業(yè)建立JCB，并把它放入作業(yè)后備隊(duì)列中。作業(yè)處于“后備狀態(tài)”。（2）運(yùn)行階段作業(yè)調(diào)度選中作業(yè)后，為其分配必要的資源和建立進(jìn)程，并放入就緒隊(duì)列。一個(gè)作業(yè)從第一次進(jìn)入就緒狀態(tài)開始，直到它運(yùn)行結(jié)束前，處于“運(yùn)行狀態(tài)”。 （3

7、）完成階段 第三章 處理機(jī)調(diào)度與死鎖 3.2.3 先來先服務(wù)先來先服務(wù)(FCFS)和短作業(yè)優(yōu)先和短作業(yè)優(yōu)先(SJF)調(diào)度算法調(diào)度算法1. 先來先服務(wù)（先來先服務(wù)（first-come first-served,FCFS）調(diào)度算法）調(diào)度算法 最簡(jiǎn)單的調(diào)度算法，既可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。當(dāng)在作業(yè)調(diào)度中采用該算法時(shí)，系統(tǒng)將從后備隊(duì)列中選擇最先進(jìn)入該隊(duì)列的作業(yè)，將它們調(diào)入內(nèi)存；當(dāng)在進(jìn)程調(diào)度采用FCFS算法時(shí)，從就緒的進(jìn)程隊(duì)列選擇最先進(jìn)入的進(jìn)程。第三章 處理機(jī)調(diào)度與死鎖 2. 短作業(yè)優(yōu)先短作業(yè)優(yōu)先(short job first, SJF)調(diào)度算法調(diào)度算法 SJF算法以作業(yè)的長短計(jì)算優(yōu)先級(jí)，作

8、業(yè)越短，其優(yōu)先級(jí)越高。3.2.3 先來先服務(wù)先來先服務(wù)(FCFS)和短作業(yè)優(yōu)先和短作業(yè)優(yōu)先(SJF)調(diào)度算法調(diào)度算法uSJF算法的缺點(diǎn)：(1) 必須預(yù)知作業(yè)的運(yùn)行時(shí)間。(2) 對(duì)長作業(yè)非常不利，長作業(yè)的周轉(zhuǎn)時(shí)間會(huì)明顯地增長。(3) 在采用SJF算法時(shí)，人-機(jī)無法實(shí)現(xiàn)交互。(4) 該調(diào)度算法完全未考慮作業(yè)的緊迫程度，故不能保證緊迫性作業(yè)能得到及時(shí)處理。第三章 處理機(jī)調(diào)度與死鎖 3.2.4 優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法1. 優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法(priority-scheduling algorithm, PSA) PSA基于作業(yè)的緊迫程度，由外

9、部賦予作業(yè)相應(yīng)的優(yōu)先級(jí)，調(diào)度算法根據(jù)該優(yōu)先級(jí)進(jìn)行調(diào)度。PSA可作為作業(yè)調(diào)度算法，也可作為進(jìn)程調(diào)度算法。第三章 處理機(jī)調(diào)度與死鎖 要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)優(yōu)先權(quán)的變化規(guī)律可描述為： 由于等待時(shí)間與服務(wù)時(shí)間之和，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為： 要求服務(wù)時(shí)間響應(yīng)時(shí)間要求服務(wù)時(shí)間要求服務(wù)時(shí)間等待時(shí)間優(yōu)先權(quán)2. 高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法(Higher Response Ratio Next, HRRN)3.2.4 優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先級(jí)調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法HRRN考慮了作業(yè)的等待時(shí)間和作業(yè)運(yùn)行時(shí)間。

10、第三章 處理機(jī)調(diào)度與死鎖 3.3 進(jìn)程調(diào)度進(jìn)程調(diào)度3.3.1 進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式1. 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)(1) 保存處理機(jī)的現(xiàn)場(chǎng)信息(2) 按某種算法選取進(jìn)程(3) 把處理器分配給進(jìn)程2. 進(jìn)程調(diào)度機(jī)制進(jìn)程調(diào)度機(jī)制 為了實(shí)現(xiàn)進(jìn)程調(diào)度，應(yīng)具有如下三個(gè)基本機(jī)制：(1)排隊(duì)器。將系統(tǒng)中所有的就緒進(jìn)程按照一定的方式排成一個(gè)或多個(gè)隊(duì)列。第三章 處理機(jī)調(diào)度與死鎖 3.3.1 進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式2. 進(jìn)程調(diào)度機(jī)制進(jìn)程調(diào)度機(jī)制(2) 分派器。從就緒隊(duì)列中取出由進(jìn)程調(diào)度程序所選定的進(jìn)程，然后進(jìn)行從分派器到新選出進(jìn)程間的上下文切換，將處

11、理機(jī)分配給該進(jìn)程。 (3) 上下文切換機(jī)制。兩對(duì)上下文切換：操作系統(tǒng)將保存當(dāng)前進(jìn)程的上下文，而裝入分派程序的上下文，以便分派程序運(yùn)行；移出分派程序的上下文，而把新選進(jìn)程的CPU現(xiàn)場(chǎng)信息裝入到處理機(jī)的各個(gè)相應(yīng)寄存器中。 第三章 處理機(jī)調(diào)度與死鎖 3進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式 1) 非搶占方式(Nonpreemptive Mode)在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，不管它要運(yùn)行多長時(shí)間，都一直讓它運(yùn)行下去，決不會(huì)因?yàn)闀r(shí)鐘中斷等原因而搶占正在運(yùn)行進(jìn)程的處理機(jī)，也不允許其它進(jìn)程搶占已經(jīng)分配給它的處理機(jī)。直至該進(jìn)程完成，自愿釋放處理機(jī)，或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程。

12、3.3.1 進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式 自行分析：引起進(jìn)程調(diào)度的原因。自行分析：引起進(jìn)程調(diào)度的原因。第三章 處理機(jī)調(diào)度與死鎖 2) 搶占方式搶占方式(Preemptive Mode)允許調(diào)度程序根據(jù)某種原則去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。搶占調(diào)度方式是基于一定原則的，主要有如下幾條： 3進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式 優(yōu)先權(quán)原則。允許優(yōu)先權(quán)高的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)。 短進(jìn)程優(yōu)先原則。允許新到的短進(jìn)程短可以搶占當(dāng)前較長進(jìn)程的處理機(jī)。 時(shí)間片原則。各進(jìn)程按時(shí)間片輪流運(yùn)行，當(dāng)一個(gè)時(shí)間片用完后，便停止該進(jìn)程的執(zhí)行而重新進(jìn)行調(diào)度。第三章

13、處理機(jī)調(diào)度與死鎖 3.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法1輪轉(zhuǎn)法的基本原理輪轉(zhuǎn)法的基本原理 基于時(shí)間片的輪轉(zhuǎn)(Round Robin, RR)調(diào)度算法。就緒隊(duì)列上的每個(gè)進(jìn)程每次僅運(yùn)行一個(gè)時(shí)間片。 系統(tǒng)將所有的就緒進(jìn)程按FCFS策略排成一個(gè)就緒隊(duì)列,每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，調(diào)度程序便把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。第三章 處理機(jī)調(diào)度與死鎖 3.3.2 輪轉(zhuǎn)調(diào)度算法輪轉(zhuǎn)調(diào)度算法2進(jìn)程切換時(shí)機(jī)進(jìn)程切換時(shí)機(jī) 若一個(gè)時(shí)間片未用完，正

14、在運(yùn)行的進(jìn)程便已經(jīng)完成，則立即激活調(diào)度程序，將它從就緒隊(duì)列中刪除，再調(diào)度就緒隊(duì)列中隊(duì)首的進(jìn)程運(yùn)行，并啟動(dòng)一個(gè)新的時(shí)間片。 在一個(gè)時(shí)間片用完時(shí)，計(jì)時(shí)器中斷處理程序被激活。3時(shí)間片大小的確定時(shí)間片大小的確定 時(shí)間片的大小對(duì)系統(tǒng)性能有很大的影響?？扇〉臅r(shí)間片大小是略大于一次典型的交互所需要的時(shí)間，使大多數(shù)交互式進(jìn)程能在一個(gè)時(shí)間片內(nèi)完成。第三章 處理機(jī)調(diào)度與死鎖 3.3.3 優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法1. 優(yōu)先級(jí)調(diào)度算法的類型優(yōu)先級(jí)調(diào)度算法的類型(1) 非搶占式優(yōu)先級(jí)調(diào)度算法(2) 搶占式優(yōu)先級(jí)調(diào)度算法 把處理機(jī)分配給優(yōu)先級(jí)最高的進(jìn)程，使之執(zhí)行。但在執(zhí)行期間，只要出現(xiàn)了另一個(gè)其優(yōu)先級(jí)更高的進(jìn)程，調(diào)度

15、程序就將處理機(jī)分配給新到的優(yōu)先級(jí)最高的進(jìn)程。第三章 處理機(jī)調(diào)度與死鎖 3.3.3 優(yōu)先級(jí)調(diào)度算法優(yōu)先級(jí)調(diào)度算法2. 優(yōu)先級(jí)的類型優(yōu)先級(jí)的類型(1) 靜態(tài)優(yōu)先級(jí) 靜態(tài)優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)確定的，在進(jìn)程的整個(gè)運(yùn)行期間保持不變。確定優(yōu)先級(jí)大小的依據(jù)有： 進(jìn)程類型。通常系統(tǒng)進(jìn)程的優(yōu)先級(jí)高于一般用戶進(jìn)程；進(jìn)程對(duì)資源的需求。對(duì)資源要求少的進(jìn)程應(yīng)賦予較高的優(yōu)先級(jí)；用戶要求。 (2) 動(dòng)態(tài)優(yōu)先級(jí) 在創(chuàng)建進(jìn)程初賦予一個(gè)優(yōu)先級(jí)，然后其值隨進(jìn)程的推進(jìn)或等待時(shí)間的增加而改變。第三章 處理機(jī)調(diào)度與死鎖 3.3.3 多隊(duì)列調(diào)度算法多隊(duì)列調(diào)度算法 該算法將系統(tǒng)中的進(jìn)程就緒隊(duì)列從一個(gè)拆分為若干個(gè)，將不同類型或性質(zhì)的進(jìn)程固定分

16、配在不同的就緒隊(duì)列，不同的就緒隊(duì)列采用不同的調(diào)度算法，一個(gè)就緒隊(duì)列中的進(jìn)程可以設(shè)置不同的優(yōu)先級(jí)，不同的就緒隊(duì)列也可設(shè)置不同的優(yōu)先級(jí)。第三章 處理機(jī)調(diào)度與死鎖 圖 3-5 多級(jí)反饋隊(duì)列調(diào)度算法 就緒隊(duì)列1就緒隊(duì)列2就緒隊(duì)列3就緒隊(duì)列nS1S2S3至CPU至CPU至CPU至CPU(時(shí)間片：S1S2S3)3.3.4 多級(jí)反饋隊(duì)列多級(jí)反饋隊(duì)列(multileved feedback queue)調(diào)度算法調(diào)度算法1. 調(diào)度機(jī)制調(diào)度機(jī)制第三章 處理機(jī)調(diào)度與死鎖 (1) 設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。 第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，第二個(gè)隊(duì)列次之，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。該算法賦予各個(gè)隊(duì)列中

17、進(jìn)程執(zhí)行時(shí)間片的大小也各不相同。3.3.4 多級(jí)反饋隊(duì)列多級(jí)反饋隊(duì)列(multileved feedback queue)調(diào)度算法調(diào)度算法1. 調(diào)度機(jī)制調(diào)度機(jī)制第三章 處理機(jī)調(diào)度與死鎖 (2) 每個(gè)隊(duì)列都采用FCFS算法。當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；否則，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，如此下去，當(dāng)一個(gè)長進(jìn)程從第一隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按RR方式運(yùn)行。3

18、.3.4 多級(jí)反饋隊(duì)列多級(jí)反饋隊(duì)列(multileved feedback queue)調(diào)度算法調(diào)度算法1. 調(diào)度機(jī)制調(diào)度機(jī)制第三章 處理機(jī)調(diào)度與死鎖 (3) 按隊(duì)列優(yōu)先級(jí)調(diào)度。僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行； 僅當(dāng)?shù)?(i-1) 隊(duì)列均空時(shí)，才會(huì)調(diào)度第i隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在第i隊(duì)列中為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i隊(duì)列的末尾，把處理機(jī)分配給新到的高優(yōu)先權(quán)進(jìn)程。 3.3.4 多級(jí)反饋隊(duì)列多級(jí)反饋隊(duì)列(multileved feedback queue)調(diào)度算法調(diào)度算

19、法1. 調(diào)度機(jī)制調(diào)度機(jī)制第三章 處理機(jī)調(diào)度與死鎖 3.3.6 基于公平原則的調(diào)度算法基于公平原則的調(diào)度算法1. 保證調(diào)度算法保證調(diào)度算法 向用戶所做出的保證并不是優(yōu)先運(yùn)行，而是明確的性能保證，該算法做到調(diào)度的公平性。在實(shí)施公平調(diào)度算法時(shí)系統(tǒng)須具有的功能：(1) 跟蹤計(jì)算每個(gè)進(jìn)程自創(chuàng)建以來已經(jīng)執(zhí)行的處理時(shí)間。 (2) 計(jì)算每個(gè)進(jìn)程應(yīng)獲得的處理機(jī)時(shí)間。 (3) 計(jì)算進(jìn)程獲得處理機(jī)時(shí)間的比率。 (4) 比較各進(jìn)程獲得處理機(jī)時(shí)間的比率。 (5) 調(diào)度程序應(yīng)選擇比率最小的進(jìn)程將處理機(jī)分配給它，并讓該進(jìn)程一直運(yùn)行，直到超過最接近它的進(jìn)程比率為止。第三章 處理機(jī)調(diào)度與死鎖 3.3.6 基于公平原則的調(diào)度算法

20、基于公平原則的調(diào)度算法2. 公平分享調(diào)度算法公平分享調(diào)度算法 在該調(diào)度算法中，調(diào)度的公平性主要是針對(duì)用戶而言，使所有用戶能獲得相同的處理機(jī)時(shí)間，或所要求的時(shí)間比例。第三章 處理機(jī)調(diào)度與死鎖 3.4 實(shí)實(shí) 時(shí)時(shí) 調(diào)調(diào) 度度3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1提供必要的信息提供必要的信息 (1) 就緒時(shí)間。該任務(wù)成為就緒狀態(tài)的起始時(shí)間； (2) 開始截止時(shí)間和完成截止時(shí)間；(3) 處理時(shí)間； (4) 資源要求；(5) 優(yōu)先級(jí)。如果某任務(wù)的開始截止時(shí)間 已經(jīng)錯(cuò)過，則為該任務(wù)賦予“絕對(duì)”優(yōu)先級(jí)；如果開始截 止時(shí)間的推遲對(duì)任務(wù)的繼續(xù)運(yùn)行無重大影響，則可為該 任務(wù)賦予“相對(duì)”優(yōu)先級(jí)。

21、第三章 處理機(jī)調(diào)度與死鎖 2系統(tǒng)處理能力強(qiáng)系統(tǒng)處理能力強(qiáng) 在實(shí)時(shí)系統(tǒng)中，通常都有著多個(gè)實(shí)時(shí)任務(wù)。假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù)，它們的處理時(shí)間可表示為Ci，周期時(shí)間表示為Pi，則在單處理機(jī)情況下，必須滿足下面的限制條件： 3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件11miiiPC提高系統(tǒng)處理能力的途徑：其一是增強(qiáng)單處理機(jī)系統(tǒng)的處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間；其二是采用多處理機(jī)系統(tǒng)。NPCmiii1第三章 處理機(jī)調(diào)度與死鎖 3.4.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件3采用搶占式調(diào)度機(jī)制采用搶占式調(diào)度機(jī)制在含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用搶占機(jī)制。當(dāng)一

22、個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許將當(dāng)前任務(wù)暫時(shí)掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，這樣便可滿足該硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。4具有快速切換機(jī)制具有快速切換機(jī)制(1)對(duì)外部中斷的快速響應(yīng)能力。具有快速硬件中斷機(jī)構(gòu)(2) 快速的任務(wù)分派能力。適當(dāng)?shù)販p小每個(gè)運(yùn)行功能單位，以減少任務(wù)切換的時(shí)間開銷。第三章 處理機(jī)調(diào)度與死鎖 3.4.2實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度算法的分類1非搶占式調(diào)度算法非搶占式調(diào)度算法1) 非搶占式輪轉(zhuǎn)調(diào)度算法該算法常用于工業(yè)生產(chǎn)的群控系統(tǒng)中，由一臺(tái)計(jì)算機(jī)控制若干個(gè)相同的(或類似的)對(duì)象，為每一個(gè)被控對(duì)象建立一個(gè)實(shí)時(shí)任務(wù)，并將它們排成一個(gè)輪轉(zhuǎn)隊(duì)列。 2) 非搶占式優(yōu)先調(diào)度算法針對(duì)較為嚴(yán)

23、格的實(shí)時(shí)任務(wù)，采用該算法為這些任務(wù)賦予較高的優(yōu)先級(jí)。當(dāng)這些實(shí)時(shí)任務(wù)到達(dá)時(shí)，把它們安排在就緒隊(duì)列的隊(duì)首，等待當(dāng)前任務(wù)自我終止或運(yùn)行完成后才能被調(diào)度執(zhí)行。第三章 處理機(jī)調(diào)度與死鎖 3.4.2實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度算法的分類2搶占式調(diào)度算法搶占式調(diào)度算法1) 基于時(shí)鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法 在某實(shí)時(shí)任務(wù)到達(dá)后，如果該任務(wù)的優(yōu)先級(jí)高于當(dāng)前任務(wù)的優(yōu)先級(jí)，這時(shí)并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)鐘中斷到來時(shí)，調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給新到的高優(yōu)先權(quán)任務(wù)。第三章 處理機(jī)調(diào)度與死鎖 3.4.2實(shí)時(shí)調(diào)度算法的分類實(shí)時(shí)調(diào)度算法的分類2搶占式調(diào)度算法搶占式調(diào)度算法2) 立即搶占(Imm

24、ediate Preemption)的優(yōu)先權(quán)調(diào)度算法在這種調(diào)度策略中，要求操作系統(tǒng)具有快速響應(yīng)外部事件中斷的能力。一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請(qǐng)求中斷的緊迫任務(wù)。第三章 處理機(jī)調(diào)度與死鎖 圖3-5 實(shí)時(shí)進(jìn)程調(diào)度 (a) 非搶占式輪轉(zhuǎn)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度實(shí)時(shí)進(jìn)程搶占當(dāng)前進(jìn)程并立即執(zhí)行(d) 立即搶占的優(yōu)先權(quán)調(diào)度調(diào)度時(shí)間進(jìn)程 1進(jìn)程 2實(shí)時(shí)進(jìn)程要求調(diào)度進(jìn)程 n實(shí)時(shí)進(jìn)程調(diào)度實(shí)時(shí)進(jìn)程運(yùn)行(b) 非搶占式優(yōu)先權(quán)調(diào)度當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度 當(dāng)前進(jìn)程運(yùn)行完成調(diào)度時(shí)間當(dāng)前進(jìn)程實(shí)時(shí)進(jìn)程請(qǐng)求調(diào)度 時(shí)鐘中斷到來時(shí)調(diào)度時(shí)間(c) 基于時(shí)

25、鐘中斷搶占的優(yōu)先權(quán)搶占調(diào)度調(diào)度時(shí)間實(shí)時(shí)進(jìn)程第三章 處理機(jī)調(diào)度與死鎖 3.4.3最早截止時(shí)間優(yōu)先最早截止時(shí)間優(yōu)先EDF(Earliest Deadline First)算法算法該算法是根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間愈早，其優(yōu)先級(jí)愈高。該算法要求在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時(shí)間的早晚排序；當(dāng)然，具有最早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。調(diào)度程序在選擇任務(wù)時(shí)，總是選擇就緒隊(duì)列中的第一個(gè)任務(wù)，為之分配處理機(jī)，使之投入運(yùn)行。最早截止時(shí)間優(yōu)先算法既可用于搶占式調(diào)度，也可用于非搶占式調(diào)度方式中。 第三章 處理機(jī)調(diào)度與死鎖 圖 3-6EDF算法用于非搶占調(diào)度的調(diào)度方式

26、1342開始截止時(shí)間任務(wù)執(zhí)行任務(wù)到達(dá)12 341342t3.4.3最早截止時(shí)間優(yōu)先最早截止時(shí)間優(yōu)先EDF(Earliest Deadline First)算法算法1. 非搶占式調(diào)度方式用于非周期實(shí)時(shí)任務(wù)第三章 處理機(jī)調(diào)度與死鎖 2. 搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)A1B1A2B1A3 B2 A4B2A5B1A2A3B2A5A1B1B1A2B1A3B2A4B2A5 B2A1A2B2A3A4A5B1最后期限B2最后期限A1最后期限A2最后期限A3最后期限A4最后期限A5最后期限到達(dá)時(shí)間、執(zhí)行時(shí)間和最后期限A1固定優(yōu)先級(jí)調(diào)度固定優(yōu)先級(jí)調(diào)度A2B1A3A4A5，B2A5，

27、B2A4A1(錯(cuò)過)A2B1A3(錯(cuò)過)A1A2B1(錯(cuò)過)A3A4A5，B20102030405060708090100時(shí)間t/ms使用完成最后期限最早和最后期限調(diào)度(A有較高優(yōu)先級(jí))(B有較高優(yōu)先級(jí))圖3-7 EDF算法用于搶占調(diào)度方式第三章 處理機(jī)調(diào)度與死鎖 3.4.4 最低松弛度優(yōu)先最低松弛度優(yōu)先LLF(Least Laxity First)算法算法 該算法是根據(jù)任務(wù)緊急的程度，來確定任務(wù)的優(yōu)先級(jí)。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級(jí)就愈高，以使之優(yōu)先執(zhí)行。 在實(shí)現(xiàn)該算法時(shí)要求系統(tǒng)中有一個(gè)按松弛度排序的實(shí)時(shí)任務(wù)就緒隊(duì)列，松弛度最低的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇就緒隊(duì)列中的

28、隊(duì)首任務(wù)執(zhí)行。 該算法主要用于可搶占調(diào)度方式中。第三章 處理機(jī)調(diào)度與死鎖 A1A2A3A4A5A6A7A820406080100120140160B1B2B3t03.4.4 最低松弛度優(yōu)先最低松弛度優(yōu)先LLF(Least Laxity First)算法算法圖 3-8A和B任務(wù)每次必須完成的時(shí)間 u例：假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為25ms。第三章 處理機(jī)調(diào)度與死鎖 t1A1(10)10203040506080t0t10B1(20)t2t370A2(10)A3(10)A4(10)t4t

29、5t6t7t8B1(5)B2(15)B2(10)圖 3-9利用LLF算法進(jìn)行調(diào)度的情況 3.4.4 最低松弛度優(yōu)先最低松弛度優(yōu)先LLF(Least Laxity First)算法算法 為保證不遺漏任何一次截止時(shí)間，應(yīng)采用最低松弛度優(yōu)先的搶占調(diào)度策略。 松弛度=必須完成時(shí)間-其本身的運(yùn)行時(shí)間-當(dāng)前時(shí)間第三章 處理機(jī)調(diào)度與死鎖 u調(diào)度算法總結(jié)調(diào)度算法總結(jié)1.1.先來閑服務(wù)算法（先來閑服務(wù)算法（FCFSFCFS）2.2.短作業(yè)優(yōu)先（短作業(yè)優(yōu)先（SJFSJF）3. 優(yōu)先級(jí)調(diào)度算法（優(yōu)先級(jí)調(diào)度算法（PSA）4.高響應(yīng)比優(yōu)先調(diào)度算法（高響應(yīng)比優(yōu)先調(diào)度算法（HRRN）5.時(shí)間片輪轉(zhuǎn)法（時(shí)間片輪轉(zhuǎn)法（RR）6

30、.多級(jí)隊(duì)列調(diào)度算法多級(jí)隊(duì)列調(diào)度算法7.多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法第三章 處理機(jī)調(diào)度與死鎖 u問題分析問題分析1. 有一個(gè)內(nèi)存中只能裝入兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法。有下表所示的作業(yè)序列，表中所列的優(yōu)先數(shù)是指進(jìn)程調(diào)度的優(yōu)先數(shù)，且優(yōu)先數(shù)越小優(yōu)先級(jí)越高。 作業(yè)數(shù)作業(yè)數(shù) 到達(dá)時(shí)間到達(dá)時(shí)間估計(jì)運(yùn)行時(shí)間估計(jì)運(yùn)行時(shí)間優(yōu)先數(shù)優(yōu)先數(shù)A BCD 10: 00 10: 20 10: 30 10: 50 40分分 30分分 50分分 20分分 5 3 4 6列出所有作業(yè)進(jìn)入內(nèi)存的時(shí)刻以及結(jié)束的時(shí)刻。計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間。第三章 處理

31、機(jī)調(diào)度與死鎖 u問題分析問題分析2. 對(duì)下面的5個(gè)非周期性實(shí)時(shí)任務(wù)，按最早開始截止時(shí)間優(yōu)先調(diào)度算法應(yīng)如何進(jìn)行CPU調(diào)度？進(jìn)程 到達(dá)時(shí)間執(zhí)行時(shí)間開始截止時(shí)間A BCDE 10 20 40 50 60 20 20 20 20 20 110 20 50 90 70第三章 處理機(jī)調(diào)度與死鎖 u問題分析問題分析3. 若有3個(gè)周期性任務(wù)，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms；任務(wù)B要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為15ms，應(yīng)如何按最低松弛優(yōu)先算法對(duì)它們進(jìn)行CPU調(diào)度？第三章 處理機(jī)調(diào)度與死鎖 3.5死死 鎖鎖 概概 述述3.5.1 資源問題資源問題 系統(tǒng)中有許多不同類型的資源，其中需要采用互

32、斥方法訪問的、不可以被搶占的資源常常會(huì)引起死鎖。1. 可重用性資源和消耗性資源可重用性資源和消耗性資源2. 可搶占性資源和不可搶占性資源可搶占性資源和不可搶占性資源l可重用性資源，一種可供用戶重復(fù)使用多次的資源。其請(qǐng)求和釋放通常利用系統(tǒng)調(diào)用，系統(tǒng)大多數(shù)資源屬于可重用性資源。l消耗性資源，又稱臨時(shí)性資源。是在進(jìn)程運(yùn)行期間，由進(jìn)程動(dòng)態(tài)地創(chuàng)建和消耗。如進(jìn)程間通信的消息。第三章 處理機(jī)調(diào)度與死鎖 3.5.2 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖 死鎖的起因源于多個(gè)進(jìn)程對(duì)不可搶占資源或可消耗資源的爭(zhēng)奪。1. 競(jìng)爭(zhēng)不可搶占性資源引起死鎖競(jìng)爭(zhēng)不可搶占性資源引起死鎖 系統(tǒng)中所擁有的不可搶占性資源不能滿足諸進(jìn)程

33、運(yùn)行的需要，會(huì)使得進(jìn)程在運(yùn)行過程中，因爭(zhēng)奪這些資源而陷入僵局。例：兩進(jìn)程P1和P2準(zhǔn)備寫兩文件f1和f2. P1 P2 Open(f1, w) Open(f2, w)Open(f2, w) Open(f1, w)第三章 處理機(jī)調(diào)度與死鎖 R1R2P1P21. 競(jìng)爭(zhēng)不可搶占性資源引起死鎖競(jìng)爭(zhēng)不可搶占性資源引起死鎖例：兩進(jìn)程P1和P2準(zhǔn)備寫兩文件R1和R2. P1 P2 Open(R1, w) Open(R2, w)Open(R2, w) Open(R1, w)圖3-12共享文件時(shí)的死鎖情況 第三章 處理機(jī)調(diào)度與死鎖 2. 競(jìng)爭(zhēng)可消耗資源引起死鎖競(jìng)爭(zhēng)可消耗資源引起死鎖3.5.2 計(jì)算機(jī)系統(tǒng)中的死鎖

34、計(jì)算機(jī)系統(tǒng)中的死鎖S2P1S3P3S1P2 圖中S1、S2和S3是臨時(shí)性資源。進(jìn)程P1產(chǎn)生消息S1，利用Send(P2, S1)原語將它發(fā)送給P2；又要求從P3接收消息S3；進(jìn)程P2產(chǎn)生消息S2，利用Send(P3, S2)原語將它發(fā)送給P3，又需要接收進(jìn)程P1所產(chǎn)生的消息S1；進(jìn)程P3產(chǎn)生消息S3，又要求從進(jìn)程P2接收其所產(chǎn)生的消息S2；P1： send(P2, S1)； receive(P3, S3)； P2： send(P3, S2)； receive(P1, S1)； P3： send(P1, S3)； receive(P2, S2)； 如果三個(gè)進(jìn)程間的消息通信如下：如果三個(gè)進(jìn)程間的消

35、息通信如下：P1： receive (P3, S3)； send(P2, S1)； P2： receive(P1, S1)； send(P3, S2)； P3： receive(P2, S2)； send(P1, S3)； 第三章 處理機(jī)調(diào)度與死鎖 3 3進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程在運(yùn)行過程中，對(duì)資源進(jìn)行申請(qǐng)和釋放的順序是否合法，也是系統(tǒng)中是否會(huì)產(chǎn)生死鎖的一個(gè)重要因素。3.5.2 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖進(jìn)程推進(jìn)順序合法進(jìn)程推進(jìn)順序合法P1：Request(R1)P1：Request(R2) P1：Release(R1) P1：Release(R2) P2

36、：Request(R2) P2：Request(R1) P2：Release(R2) P2：Release(R1)； 舉例：系統(tǒng)中只有一臺(tái)打印機(jī)R1和一臺(tái)磁帶機(jī)R2，供進(jìn)程P1和P2共享.第三章 處理機(jī)調(diào)度與死鎖 圖3-14進(jìn)程推進(jìn)順序?qū)λ梨i的影響 P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1) P1Rel(R2)D3.5.2 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖若并發(fā)進(jìn)程若并發(fā)進(jìn)程P1和和P2按曲線按曲線所示的順序推進(jìn)，它們所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)將進(jìn)入不安全區(qū)D內(nèi)。內(nèi)。第三章 處理機(jī)調(diào)度與死鎖 2)

37、進(jìn)程推進(jìn)順序非法進(jìn)程推進(jìn)順序非法若并發(fā)進(jìn)程P1和P2按曲線所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)D內(nèi)。此時(shí)P1保持了資源R1，P2保持了資源R2，系統(tǒng)處于不安全狀態(tài)。因?yàn)檫@時(shí)兩進(jìn)程再向前推進(jìn)，便可能發(fā)生死鎖。例如，當(dāng)P1運(yùn)行到P1：Request(R2)時(shí)，將因R2已被P2占用而阻塞；當(dāng)P2運(yùn)行到P2：Request(R1)時(shí)，也將因R1已被P1占用而阻塞，于是發(fā)生了進(jìn)程死鎖。 3 3進(jìn)程推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序不當(dāng)引起死鎖3.5.2 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖第三章 處理機(jī)調(diào)度與死鎖 3.5.3 死鎖的定義、必要條件和處理方法死鎖的定義、必要條件和處理方法 如果一組進(jìn)程中的每一

38、個(gè)進(jìn)程都在等待僅由該組進(jìn)程中的其它進(jìn)程才能引發(fā)的事件，則該組進(jìn)程是死鎖的。2. 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件(1)互斥條件：指進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用，即在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占用。如果此時(shí)還有其它進(jìn)程請(qǐng)求該資源，則請(qǐng)求者只能等待，直至占有該資源的進(jìn)程用畢釋放。1.死鎖（死鎖（Deadlock）的定義）的定義第三章 處理機(jī)調(diào)度與死鎖 (2) 請(qǐng)求和保持條件 指進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源又已被其它進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)自己已獲得的其它資源保持不放。(3) 不可搶占條件 指進(jìn)程已獲得的資源，在未使用完之前，不能被剝奪，只能在使

39、用完時(shí)由自己釋放。2. 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件(4) 循環(huán)等待條件 指在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程資源的環(huán)形鏈。3.5.3 死鎖的定義、必要條件和處理方法死鎖的定義、必要條件和處理方法第三章 處理機(jī)調(diào)度與死鎖 3. 處理死鎖的方法處理死鎖的方法3.5.3 死鎖的定義、必要條件和處理方法死鎖的定義、必要條件和處理方法(1) 預(yù)防死鎖。通過設(shè)置某些限制條件，破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件。(2) 避免死鎖。在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。(3) 檢測(cè)死鎖。通過系統(tǒng)所設(shè)置的檢測(cè)機(jī)構(gòu)，及時(shí)地檢測(cè)出死鎖的發(fā)生，并精確地確定與死鎖

40、有關(guān)的進(jìn)程和資源； 然后，采取適當(dāng)措施，從系統(tǒng)中將已發(fā)生的死鎖清除掉。 (4) 解除死鎖，與檢測(cè)死鎖相配套。第三章 處理機(jī)調(diào)度與死鎖 3.6預(yù)預(yù) 防防 死死 鎖鎖3.6.1破壞破壞“請(qǐng)求和保持請(qǐng)求和保持”條件條件 系統(tǒng)保證：當(dāng)一個(gè)進(jìn)程在請(qǐng)求資源時(shí)，它不能持有不可搶占資源。可采用兩種協(xié)議：1 1第一種協(xié)議第一種協(xié)議系統(tǒng)規(guī)定所有進(jìn)程在開始運(yùn)行之前，都必須一次性地申請(qǐng)其在整個(gè)運(yùn)行過程所需的全部資源。通過破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)。第三章 處理機(jī)調(diào)度與死鎖 3.6.1摒棄摒棄“請(qǐng)求和保持請(qǐng)求和保持”條件條件2 2第二種協(xié)議第二種協(xié)議 允許一個(gè)進(jìn)程只獲得運(yùn)行初期所需的資源后，便開始運(yùn)行。進(jìn)

41、程運(yùn)行過程中再逐步釋放已分配給自己的、且已用畢的餓全部資源，然后再請(qǐng)求新的所需資源。問題討論問題討論：有一個(gè)進(jìn)程，它所要完成的任務(wù)是，先將數(shù)據(jù)從磁帶尚復(fù)制到磁盤文件上，然后對(duì)磁盤文件進(jìn)行排序，最后把結(jié)果打印出來。第三章 處理機(jī)調(diào)度與死鎖 3.6.2破壞破壞“不可搶占不可搶占”條件條件在采用這種方法時(shí)系統(tǒng)規(guī)定，進(jìn)程是逐個(gè)地提出對(duì)資源的要求的。當(dāng)一個(gè)已經(jīng)保持了某些資源的進(jìn)程，再提出新的資源請(qǐng)求而不能立即得到滿足時(shí)，必須釋放它已經(jīng)保持了的所有資源，待以后需要時(shí)再重新申請(qǐng)。 這意味著某一進(jìn)程已經(jīng)占有的資源，在運(yùn)行過程中會(huì)被暫時(shí)地釋放掉，也可認(rèn)為是被剝奪了，從而摒棄了“不可搶占”條件。 第三章 處理機(jī)調(diào)

42、度與死鎖 3.6.3破壞破壞“循環(huán)循環(huán)等待等待”條件條件系統(tǒng)將所有資源按類型進(jìn)行線性排隊(duì)，并賦予不同的序號(hào)。所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按照：資源序號(hào)遞增的次序提出。例如：一個(gè)進(jìn)程在開始時(shí)，可以請(qǐng)求某類資源Ri的單元。以后，當(dāng)且僅當(dāng)F(Rj)F(Ri)時(shí)，進(jìn)程才可以請(qǐng)求資源Rj的單元。這樣，不可能再出現(xiàn)環(huán)路，破壞了“循環(huán)等待”條件。 在采用這種策略時(shí)，應(yīng)如何來規(guī)定每種資源的序號(hào)十分重要。第三章 處理機(jī)調(diào)度與死鎖 3.7避免死鎖避免死鎖3.7.1系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)1 1安全狀態(tài)安全狀態(tài)在資源動(dòng)態(tài)分配過程中，防止系統(tǒng)進(jìn)入不安全狀態(tài)。安全狀態(tài)安全狀態(tài)指系統(tǒng)能按某種進(jìn)程順序(P1,P2,Pn)

43、來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)不安全狀態(tài)。第三章 處理機(jī)調(diào)度與死鎖 2 2安全狀態(tài)舉例安全狀態(tài)舉例假定系統(tǒng)中有三個(gè)進(jìn)程P1、P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。在T0時(shí)刻，資源分配如下表所示： 進(jìn) 程 最 大 需 求 已 分 配 可 用 P1 10 5 3 P2 4 2 P3 9 2 3.7.1系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)u在T0時(shí)刻，存在一個(gè)安全序列，因此是安全的。u若在T0時(shí)刻以后P3又請(qǐng)求1個(gè)資源，系統(tǒng)將資源分配給P3，則

44、進(jìn)入不安全狀態(tài)。第三章 處理機(jī)調(diào)度與死鎖 3.7.2利用銀行家算法避免死鎖利用銀行家算法避免死鎖 銀行家算法是一種最有代表性的避免死鎖的算法，該算法原本為銀行系統(tǒng)設(shè)計(jì)的，以確保銀行在發(fā)放現(xiàn)金貸款時(shí)，不會(huì)發(fā)生不能滿足所有客戶需求的情況。在避免死鎖方法中允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次分配資源的安全性，若分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配，否則等待。第三章 處理機(jī)調(diào)度與死鎖 3.7.2利用銀行家算法避免死鎖利用銀行家算法避免死鎖1 1銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1)可利用資源向量Available，是一個(gè)含有m個(gè)元素的數(shù)組。其中每一個(gè)元素代表一

45、類可利用的資源數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如Availablej=K.(3) 分配矩陣Allocation，nm的矩陣。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得R j類資源的數(shù)目為K。(4) 需求矩陣Need，nm的矩陣。如果Needi,j=K，則表示進(jìn)程i還需要R j類資源K個(gè)，方能完成其任務(wù)。(2)最大需求矩陣Max，一個(gè)nm的矩陣。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。 第三章 處理機(jī)調(diào)度與死鎖 2銀行家算法銀行家算法設(shè)Request i是進(jìn)程Pi的請(qǐng)求向量。當(dāng)P i發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：(3) 系統(tǒng)試探著

46、把資源分配給進(jìn)程Pi，并修改： Availablej= Availablej-Request ij； Allocationi,j=Allocationi,j+Request ij；Needi,j=Needi,j-Request ij； (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。(1) 如果Request ijNeedi,j，轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯(cuò)。(2) 如果RequestijAvailablej，轉(zhuǎn)向步驟(3)；否則，Pi須等待。 3.7.2利用銀行家算法避免死鎖利用銀行家算法避免死鎖第三章 處理機(jī)調(diào)度與死鎖 3 3安全性算法安全性算法3.7.2利用銀行家算法

47、避免死鎖利用銀行家算法避免死鎖(2)(2)從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程：從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false； Needi,jWorkj； 若找到，執(zhí)行步驟若找到，執(zhí)行步驟(3)(3) 否則，執(zhí)行步驟否則，執(zhí)行步驟(4)(4)。(1)(1)設(shè)置兩個(gè)向量：工作向量設(shè)置兩個(gè)向量：工作向量Work，Work=Available; Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。(3)(3)當(dāng)進(jìn)程當(dāng)進(jìn)程Pi獲得資源，可順利執(zhí)行，直至完成，并釋放出分配給它獲得資源，可順利執(zhí)行，直至完成，并

48、釋放出分配給它 的資源，故應(yīng)執(zhí)行：的資源，故應(yīng)執(zhí)行：Workj=Workj+Allocationi,j； Finishi=true； go to step 2； (4)(4)如果所有進(jìn)程的如果所有進(jìn)程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；都滿足，則表示系統(tǒng)處于安全狀態(tài)； 否則，系統(tǒng)處于不安全狀態(tài)。否則，系統(tǒng)處于不安全狀態(tài)。 第三章 處理機(jī)調(diào)度與死鎖 4銀行家算法之例銀行家算法之例假定系統(tǒng)中有五個(gè)進(jìn)程P0,P1,P2,P3,P4和三類資源A,B,C，各資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖。 3.7.2利用銀行家算法避免死鎖利用銀行家算法避免死鎖Max A

49、llocation Need Available 資源 情況 進(jìn) 程 A B C A B C A B C A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 (2 3 0) P1 3 2 2 2 0 0 1 2 2 (3 0 2) (0 2 0) P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 圖3-15 T0時(shí)刻的資源分配表 第三章 處理機(jī)調(diào)度與死鎖 (1) T0時(shí)刻的安全性：利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析可知，在T0時(shí)刻存在著一個(gè)安全序列P1，P3，P4，P2，P0，故系統(tǒng)是安全的。

50、 圖3-16T0時(shí)刻的安全序列 Work Need Allocation Work+Allocation 資源 情況 進(jìn) 程 A B C A B C A B C A B C Finish P1 3 3 2 1 2 2 2 0 0 5 3 2 true P3 5 3 2 0 1 1 2 1 1 7 4 3 true P4 7 4 3 4 3 1 0 0 2 7 4 5 true P2 7 4 5 6 0 0 3 0 2 10 4 7 true P0 10 4 7 7 4 3 0 1 0 10 5 7 true 4銀行家算法之例銀行家算法之例第三章 處理機(jī)調(diào)度與死鎖 再利用安全性算法檢查此時(shí)系統(tǒng)是

51、否安全。如圖3-17所示。 圖3-17P1申請(qǐng)資源時(shí)的安全性檢查 Work Need Allocation Work+Allocation 資源 情況 進(jìn) 程 A B C A B C A B C A B C Finish P1 2 3 0 0 2 0 3 0 2 5 3 2 true P3 5 3 2 0 1 1 2 1 1 7 4 3 true P4 7 4 3 4 3 1 0 0 2 7 4 5 true P0 7 4 5 7 4 3 0 1 0 7 5 5 true P2 7 5 5 6 0 0 3 0 2 10 5 7 true 4銀行家算法之例銀行家算法之例第三章 處理機(jī)調(diào)度與死鎖

52、(3)P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request4(3，3，0)Need4(4，3，1)； Request4(3，3，0)Available(2，3，0)，讓P4等待。 (4)P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request0(0，2，0)Need0(7，4，3)； Request0(0，2，0)Available(2，3，0)；系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖3-18所示。 4銀行家算法之例銀行家算法之例第三章 處理機(jī)調(diào)度與死鎖 圖3-18為P0分配資源后的有關(guān)資源數(shù)據(jù) Allocation Need Available 資源 情況 進(jìn) 程 A B C A B C A B C P0 0 3 0 7 3 2 2 1 0 P1 3 0 2 0 2 0 P2 3 0 2 6 0 0 P3 2 1 1 0 1 1 P4 0 0 2 4 3 1 第三章 處理機(jī)調(diào)度與死鎖 (5)進(jìn)行安全性檢查：可用資源Available(2，1，0)已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。思考：思考：如果在銀行家算法中，把P0發(fā)出的請(qǐng)求向量改為Request0(0，1，0)，系統(tǒng)是否能將資源分配給它？4銀行家算法之例銀行家算法之例第三