1、東北農(nóng)業(yè)大學(xué)王艷操作系統(tǒng)原理Page 2用戶用戶用戶用戶用戶用戶作業(yè)作業(yè)1作業(yè)作業(yè)2作業(yè)作業(yè)3作業(yè)作業(yè)4外存外存后備隊(duì)列后備隊(duì)列作業(yè)調(diào)度程序作業(yè)調(diào)度程序內(nèi)存內(nèi)存CPU進(jìn)程調(diào)度進(jìn)程調(diào)度Page 3第三章 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.1.1 3.1.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次1 1 高級調(diào)度高級調(diào)度 長程調(diào)度、作業(yè)調(diào)度，調(diào)度對象為作業(yè)。長程調(diào)度、作業(yè)調(diào)度，調(diào)度對象為作業(yè)。2 2 低級調(diào)度低級調(diào)度 進(jìn)程調(diào)度、短程調(diào)度，調(diào)度對象為進(jìn)程。進(jìn)程調(diào)度、短程調(diào)度，調(diào)度對象為進(jìn)程。3 3 中級調(diào)度中級調(diào)度 內(nèi)存調(diào)度，為提高內(nèi)存利用率和系統(tǒng)吞吐量。內(nèi)存調(diào)度，為提高內(nèi)存利用

2、率和系統(tǒng)吞吐量。Page 4第三章 處理機(jī)調(diào)度與死鎖CPU就緒隊(duì)列阻塞隊(duì)列后備作業(yè)隊(duì)列高級調(diào)度低級調(diào)度時(shí)間片用完進(jìn)程完成等待事件事件解除Page 5第三章 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.1.2 3.1.2 處理機(jī)算法的目標(biāo)處理機(jī)算法的目標(biāo)1 1 處理機(jī)算法的共同目標(biāo)處理機(jī)算法的共同目標(biāo)（1 1）資源利用率）資源利用率（2 2）公平性）公平性（3 3）平衡性）平衡性（4 4）策略強(qiáng)制執(zhí)行性）策略強(qiáng)制執(zhí)行性Page 6第三章 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.1.2 3.1.2 處理機(jī)算法的目標(biāo)處理機(jī)算法的目標(biāo)2 2 批處理系統(tǒng)的目標(biāo)批處理系

3、統(tǒng)的目標(biāo)（1 1）平均周轉(zhuǎn)時(shí)間短）平均周轉(zhuǎn)時(shí)間短作業(yè)提交開始到作業(yè)完成為止的時(shí)間間隔作業(yè)提交開始到作業(yè)完成為止的時(shí)間間隔系統(tǒng)：作業(yè)的平均周轉(zhuǎn)時(shí)間盡可能少系統(tǒng)：作業(yè)的平均周轉(zhuǎn)時(shí)間盡可能少用戶：自己作業(yè)周轉(zhuǎn)時(shí)間盡量少用戶：自己作業(yè)周轉(zhuǎn)時(shí)間盡量少指標(biāo)：平均周轉(zhuǎn)時(shí)間指標(biāo)：平均周轉(zhuǎn)時(shí)間指標(biāo)：帶權(quán)周轉(zhuǎn)時(shí)間指標(biāo)：帶權(quán)周轉(zhuǎn)時(shí)間Page 7第三章 處理機(jī)調(diào)度與死鎖作業(yè)平均周轉(zhuǎn)時(shí)間（作業(yè)平均周轉(zhuǎn)時(shí)間（T）帶權(quán)平均周轉(zhuǎn)時(shí)間（帶權(quán)平均周轉(zhuǎn)時(shí)間（W）T（ ）=niTi1n1n為作業(yè)數(shù)目， 第i個(gè)作業(yè)的周轉(zhuǎn)時(shí)間Ti Ei SiEi：作業(yè)完成時(shí)間 Si：作業(yè)提交時(shí)間W（ ） n1=niriTi1ri 為某作業(yè)為某作業(yè)i的實(shí)

4、際執(zhí)行時(shí)間的實(shí)際執(zhí)行時(shí)間3.1 處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.1.2 3.1.2 處理機(jī)算法的目標(biāo)處理機(jī)算法的目標(biāo)Page 8第三章 處理機(jī)調(diào)度與死鎖3.1 處理機(jī)調(diào)度的層次和調(diào)度算法的目標(biāo)3.1.2 3.1.2 處理機(jī)算法的目標(biāo)處理機(jī)算法的目標(biāo)2 2 批處理系統(tǒng)的目標(biāo)批處理系統(tǒng)的目標(biāo)（2 2）系統(tǒng)吞吐量）系統(tǒng)吞吐量（3 3）處理機(jī)利用率高）處理機(jī)利用率高3 3 分時(shí)系統(tǒng)的目標(biāo)分時(shí)系統(tǒng)的目標(biāo)（1 1）響應(yīng)時(shí)間快）響應(yīng)時(shí)間快（2 2）均衡性）均衡性4 4 實(shí)時(shí)系統(tǒng)的目標(biāo)實(shí)時(shí)系統(tǒng)的目標(biāo)（1 1）截止時(shí)間的保證）截止時(shí)間的保證（2 2）可預(yù)測性）可預(yù)測性Page 9第三章 處理機(jī)調(diào)度與死鎖3.

5、2 作業(yè)與作業(yè)調(diào)度3.2.1 3.2.1 批處理系統(tǒng)中的作業(yè)批處理系統(tǒng)中的作業(yè)1 1 作業(yè)和作業(yè)步作業(yè)和作業(yè)步 （1 1）作業(yè)（）作業(yè)（JobJob）：）：程序程序+數(shù)據(jù)數(shù)據(jù)+作業(yè)說明符作業(yè)說明符 （2 2）作業(yè)步：）作業(yè)步：作業(yè)執(zhí)行過程中的加工步驟作業(yè)執(zhí)行過程中的加工步驟2 2 作業(yè)控制塊（作業(yè)控制塊（JCBJCB） (1)(1)作業(yè)存在的標(biāo)識(shí)作業(yè)存在的標(biāo)識(shí) (2)(2)保存系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度的所有信息保存系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度的所有信息Page 10第三章 處理機(jī)調(diào)度與死鎖3.2 作業(yè)與作業(yè)調(diào)度3.2.1 3.2.1 批處理系統(tǒng)中的作業(yè)批處理系統(tǒng)中的作業(yè)3 3 作業(yè)運(yùn)行的三個(gè)階段和

6、三種狀態(tài)作業(yè)運(yùn)行的三個(gè)階段和三種狀態(tài)后備狀態(tài)后備狀態(tài)運(yùn)行狀態(tài)運(yùn)行狀態(tài)完成狀態(tài)完成狀態(tài)（1 1）三）三個(gè)階段個(gè)階段收容階段收容階段運(yùn)行階段運(yùn)行階段完成階段完成階段（2 2）三種狀態(tài)）三種狀態(tài)Page 11第三章 處理機(jī)調(diào)度與死鎖3.2 作業(yè)與作業(yè)調(diào)度 3.2.2 3.2.2 作業(yè)調(diào)度的主要任務(wù)作業(yè)調(diào)度的主要任務(wù)1 1 決定接納多少個(gè)作業(yè)決定接納多少個(gè)作業(yè)多道程序度多道程序度2 2 接納哪些作業(yè)接納哪些作業(yè)調(diào)度算法調(diào)度算法Page 12第三章 處理機(jī)調(diào)度與死鎖3.2 作業(yè)與作業(yè)調(diào)度 3.2.3 3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法1 1 先來先服務(wù)算法先來先服務(wù)算法 （

7、1 1）FCFSFCFS：First Come First ServeFirst Come First Serve （2 2）適用于作業(yè)、進(jìn)程調(diào)度）適用于作業(yè)、進(jìn)程調(diào)度 （3 3）選擇最先進(jìn)入的作業(yè)）選擇最先進(jìn)入的作業(yè)/ /進(jìn)程進(jìn)程 （4 4）例子：）例子：Page 13第三章 處理機(jī)調(diào)度與死鎖作業(yè)到達(dá)t服務(wù)t開始t結(jié)束tTWA01B1100C21D31000111011011021022021110011001001991.99平均周轉(zhuǎn)時(shí)間：平均周轉(zhuǎn)時(shí)間：t=100t=100帶權(quán)平均周轉(zhuǎn)時(shí)間帶權(quán)平均周轉(zhuǎn)時(shí)間w=25.9975w=25.9975優(yōu)點(diǎn)：實(shí)現(xiàn)簡單（優(yōu)待大作業(yè)） 缺點(diǎn)：對短作業(yè)不利3

8、.2 作業(yè)與作業(yè)調(diào)度 3.2.3 3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法Page 14第三章 處理機(jī)調(diào)度與死鎖2 2 短作業(yè)優(yōu)先算法短作業(yè)優(yōu)先算法 （1 1）SJSJ（P P）F F：Shortest JobShortest Job（ProcessProcess） First First （2 2）適用于作業(yè)、進(jìn)程調(diào)度）適用于作業(yè)、進(jìn)程調(diào)度 （3 3）選擇短的作業(yè)）選擇短的作業(yè)/ /進(jìn)程進(jìn)程 （4 4）例子：）例子：3.2 作業(yè)與作業(yè)調(diào)度 3.2.3 3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法Page 15第三章 處理機(jī)調(diào)度與死鎖進(jìn)程ABCDE平

9、均到達(dá)t01234服務(wù)t43524 先 來 先 服 務(wù) 算 法開始t完成tTW 短 作 業(yè) 優(yōu) 先 算 法開始t完成tTW作業(yè)作業(yè)情況情況算法算法0447712121414184162102115.5143.592.804691318469134182.67163.231.592.2582.143.2 作業(yè)與作業(yè)調(diào)度 3.2.3 3.2.3 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法Page 16第三章 處理機(jī)調(diào)度與死鎖1 1 優(yōu)先級調(diào)度算法（優(yōu)先級調(diào)度算法（PSAPSA）3.2 作業(yè)與作業(yè)調(diào)度 3.2.4 3.2.4 優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先

10、調(diào)度算法先來先服務(wù)算法先來先服務(wù)算法等待時(shí)間為優(yōu)先級等待時(shí)間為優(yōu)先級短作業(yè)優(yōu)先算法短作業(yè)優(yōu)先算法作業(yè)長短為優(yōu)先級作業(yè)長短為優(yōu)先級優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法作業(yè)的緊迫程度作業(yè)的緊迫程度Page 17第三章 處理機(jī)調(diào)度與死鎖2 2 高響應(yīng)比優(yōu)先權(quán)調(diào)度算法（高響應(yīng)比優(yōu)先權(quán)調(diào)度算法（HRRNHRRN）（1 1）HRRNHRRN是介于是介于FCFSFCFS和和SJPSJP（F F）之間的一種折中算法）之間的一種折中算法（2 2）優(yōu)先權(quán)）優(yōu)先權(quán)3.2 作業(yè)與作業(yè)調(diào)度 3.2.4 3.2.4 優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先權(quán)優(yōu)先權(quán)= =（等待時(shí)間（等待時(shí)間+

11、+要求服務(wù)時(shí)間）要求服務(wù)時(shí)間）/ /要求服務(wù)時(shí)間要求服務(wù)時(shí)間動(dòng)態(tài)優(yōu)先權(quán)：隨等待時(shí)間延長而增加動(dòng)態(tài)優(yōu)先權(quán)：隨等待時(shí)間延長而增加響應(yīng)比響應(yīng)比R=R=（等待時(shí)間（等待時(shí)間+ +要求服務(wù)時(shí)間）要求服務(wù)時(shí)間）/ /要求服務(wù)時(shí)間要求服務(wù)時(shí)間 = =響應(yīng)時(shí)間響應(yīng)時(shí)間/ /要求服務(wù)時(shí)間要求服務(wù)時(shí)間Page 18第三章 處理機(jī)調(diào)度與死鎖2 2 高響應(yīng)比優(yōu)先權(quán)調(diào)度算法（高響應(yīng)比優(yōu)先權(quán)調(diào)度算法（HRRNHRRN）（3 3）優(yōu)點(diǎn)）優(yōu)點(diǎn)等待時(shí)間相同，則處理時(shí)間短，優(yōu)先級等待時(shí)間相同，則處理時(shí)間短，優(yōu)先級R高。高。作業(yè)處理時(shí)間相同，則等待時(shí)間決定優(yōu)先級作業(yè)處理時(shí)間相同，則等待時(shí)間決定優(yōu)先級R。對于長作業(yè)，等待足夠時(shí)間，對

12、于長作業(yè)，等待足夠時(shí)間，R增加，可獲得處理機(jī)。增加，可獲得處理機(jī)。SJFFCFS（4 4）缺點(diǎn)）缺點(diǎn)增加系統(tǒng)開銷增加系統(tǒng)開銷3.2 作業(yè)與作業(yè)調(diào)度 3.2.4 3.2.4 優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法Page 19第三章 處理機(jī)調(diào)度與死鎖2 2 高響應(yīng)比優(yōu)先權(quán)調(diào)度算法（高響應(yīng)比優(yōu)先權(quán)調(diào)度算法（HRRNHRRN）（5 5）例子）例子到達(dá)t服務(wù)t開始t完成tTWA04B13C25D32E44平均04Rb=1，Rc=0.4Rd=0.5，Re=047Rc=1，Rd=2，Re=0.7579Rc=1.4，Re=1.2591414184162122.463143.

13、58.42.383.2 作業(yè)與作業(yè)調(diào)度 3.2.4 3.2.4 優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先級調(diào)度算法和高響應(yīng)比優(yōu)先調(diào)度算法Page 20（1）FCFS（2）SJ（P）F（3 3）HRNHRNPage 21名稱ABCDE平均到達(dá)01234CPU36452FCFS開始完成TWSJF開始完成TWHRN開始完成TW0339913131818203181115161.332.753810.63.220314203791479311951153.171.252.22.58.62.02033911151520911318131771.333.253.43.59.62.496Page 22第三章

14、 處理機(jī)調(diào)度與死鎖3.3 進(jìn)程調(diào)度1 1 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù) (1)(1)保存處理機(jī)現(xiàn)場信息保存處理機(jī)現(xiàn)場信息 (2)(2)按某種算法選取進(jìn)程按某種算法選取進(jìn)程 (3)(3)把處理機(jī)分配給進(jìn)程把處理機(jī)分配給進(jìn)程2 2 進(jìn)程調(diào)度機(jī)制進(jìn)程調(diào)度機(jī)制 (1)(1)排隊(duì)器排隊(duì)器 (2)(2)分派器分派器 (3)(3)上下文切換機(jī)制上下文切換機(jī)制 3.3.1 3.3.1 進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式進(jìn)程調(diào)度的任務(wù)、機(jī)制和方式Page 23第三章 處理機(jī)調(diào)度與死鎖3.3 進(jìn)程調(diào)度3 3 調(diào)度方式調(diào)度方式 (1)(1)非搶占式非搶占式 引發(fā)進(jìn)程調(diào)度的事件引發(fā)進(jìn)程調(diào)度的事件執(zhí)行完畢、進(jìn)程阻塞、執(zhí)行原語執(zhí)

15、行完畢、進(jìn)程阻塞、執(zhí)行原語 特點(diǎn)特點(diǎn)實(shí)現(xiàn)簡單、開銷小、不能立即執(zhí)行實(shí)現(xiàn)簡單、開銷小、不能立即執(zhí)行（2 2）搶占式搶占式 基本原則基本原則優(yōu)先權(quán)原則、短作業(yè)（進(jìn)程）優(yōu)先、時(shí)間片原則優(yōu)先權(quán)原則、短作業(yè)（進(jìn)程）優(yōu)先、時(shí)間片原則 特點(diǎn)特點(diǎn)開銷大、公平、響應(yīng)及時(shí)開銷大、公平、響應(yīng)及時(shí) Page 24第三章 處理機(jī)調(diào)度與死鎖3.3 進(jìn)程調(diào)度3.3.2 3.3.2 輪轉(zhuǎn)調(diào)度算法（輪轉(zhuǎn)調(diào)度算法（RRRR）1 1 輪轉(zhuǎn)法的基本原理輪轉(zhuǎn)法的基本原理 按按FCFSFCFS將就緒進(jìn)程排成一個(gè)就緒隊(duì)列，進(jìn)程按時(shí)間片輪將就緒進(jìn)程排成一個(gè)就緒隊(duì)列，進(jìn)程按時(shí)間片輪流使用流使用CPUCPU。3 3 時(shí)間片大小的確定時(shí)間片大小的

16、確定 太長太長不能及時(shí)響應(yīng)不能及時(shí)響應(yīng) 太短太短頻繁切換，降低頻繁切換，降低CPUCPU效率效率2 2 進(jìn)程切換時(shí)機(jī)進(jìn)程切換時(shí)機(jī)（1 1）時(shí)間片未完，進(jìn)程已完成）時(shí)間片未完，進(jìn)程已完成（2 2）時(shí)間片完，進(jìn)程未完成）時(shí)間片完，進(jìn)程未完成Page 25第三章 處理機(jī)調(diào)度與死鎖ABCDEABCDEABCEACE(a) q1(b) q412345678910 11 12 13 14 15 16 17tPage 26第三章 處理機(jī)調(diào)度與死鎖進(jìn)程名 A B C D E 平均 到達(dá)時(shí)間 0 1 2 3 4 作業(yè) 情況 時(shí) 間 片 服務(wù)時(shí)間 4 3 4 2 4 完成時(shí)間 15 12 16 9 17 周轉(zhuǎn)時(shí)間

17、 15 11 14 6 13 11.8 RR q=1 帶權(quán)周轉(zhuǎn)時(shí)間 3.75 3.67 3.5 3 3.33 3.46 完成時(shí)間 4 7 11 13 17 周轉(zhuǎn)時(shí)間 4 6 9 10 13 8.4 RR q=4 帶權(quán)周轉(zhuǎn)時(shí)間 1 2 2.25 5 3.33 2.5 Page 27第三章 處理機(jī)調(diào)度與死鎖3.3 進(jìn)程調(diào)度3.3.3 3.3.3 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法1 1 優(yōu)先級調(diào)度算法類型優(yōu)先級調(diào)度算法類型 （1 1）非搶占式優(yōu)先權(quán)調(diào)度算法）非搶占式優(yōu)先權(quán)調(diào)度算法 批處理系統(tǒng)、實(shí)時(shí)性要求不高的實(shí)時(shí)系統(tǒng)批處理系統(tǒng)、實(shí)時(shí)性要求不高的實(shí)時(shí)系統(tǒng) （2 2）搶占式優(yōu)先權(quán)算法）搶占式優(yōu)先權(quán)算法 嚴(yán)格

18、的實(shí)時(shí)系統(tǒng)，高性能的分時(shí)、批處理系統(tǒng)嚴(yán)格的實(shí)時(shí)系統(tǒng)，高性能的分時(shí)、批處理系統(tǒng)Page 28第三章 處理機(jī)調(diào)度與死鎖3.3 進(jìn)程調(diào)度3.3.33.3.3 優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法2 2 優(yōu)先級的類型優(yōu)先級的類型（1 1）靜態(tài)優(yōu)先級）靜態(tài)優(yōu)先級進(jìn)程創(chuàng)建時(shí)確定，在進(jìn)程整個(gè)運(yùn)行期間保持不變。進(jìn)程創(chuàng)建時(shí)確定，在進(jìn)程整個(gè)運(yùn)行期間保持不變。進(jìn)程類型進(jìn)程類型進(jìn)程對資源的需求進(jìn)程對資源的需求用戶要求用戶要求 簡單易行，系統(tǒng)開銷小，但不夠精確，優(yōu)先級低的進(jìn)程簡單易行，系統(tǒng)開銷小，但不夠精確，優(yōu)先級低的進(jìn)程長期不被調(diào)用長期不被調(diào)用Page 29第三章 處理機(jī)調(diào)度與死鎖3.3 進(jìn)程調(diào)度3.3.33.3.3 優(yōu)先級

19、調(diào)度算法優(yōu)先級調(diào)度算法2 2 優(yōu)先級的類型優(yōu)先級的類型（2 2）動(dòng)態(tài)優(yōu)先級）動(dòng)態(tài)優(yōu)先級進(jìn)程創(chuàng)建之初確定，隨進(jìn)程推進(jìn)或等待時(shí)間的增加而改變進(jìn)程創(chuàng)建之初確定，隨進(jìn)程推進(jìn)或等待時(shí)間的增加而改變隨等待時(shí)間的增長，優(yōu)先級相應(yīng)提高隨等待時(shí)間的增長，優(yōu)先級相應(yīng)提高搶占式調(diào)度方式中，規(guī)定當(dāng)前進(jìn)程的優(yōu)先級隨運(yùn)行搶占式調(diào)度方式中，規(guī)定當(dāng)前進(jìn)程的優(yōu)先級隨運(yùn)行 時(shí)間的推移而下降時(shí)間的推移而下降Page 30第三章 處理機(jī)調(diào)度與死鎖3.3 進(jìn)程調(diào)度 3.3.4 3.3.4 多隊(duì)列調(diào)度算法多隊(duì)列調(diào)度算法就緒隊(duì)列就緒隊(duì)列多個(gè)多個(gè)不同隊(duì)列不同隊(duì)列不同優(yōu)先級不同優(yōu)先級不同隊(duì)列不同隊(duì)列不同調(diào)度算法不同調(diào)度算法Page 31第三章

20、 處理機(jī)調(diào)度與死鎖3.3 進(jìn)程調(diào)度3.3.5 3.3.5 多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法1 1 調(diào)度機(jī)制調(diào)度機(jī)制（1）建立多個(gè)就緒隊(duì)列，優(yōu)先級遞減）建立多個(gè)就緒隊(duì)列，優(yōu)先級遞減就緒隊(duì)列 1就緒隊(duì)列 2就緒隊(duì)列 3就緒隊(duì)列 nS1S2S3至CPU至CPU至CPU至CPU(時(shí)間片： S1 S2 S3)Page 32第三章 處理機(jī)調(diào)度與死鎖3.3 進(jìn)程調(diào)度3.3.5 3.3.5 多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法1 1 調(diào)度機(jī)制調(diào)度機(jī)制（2）每個(gè)隊(duì)列都采用）每個(gè)隊(duì)列都采用FCFS算法，第算法，第n個(gè)隊(duì)列個(gè)隊(duì)列 采用采用RR方式調(diào)度方式調(diào)度（3）按隊(duì)列優(yōu)先級調(diào)度。首先調(diào)度最高優(yōu)先級）按

21、隊(duì)列優(yōu)先級調(diào)度。首先調(diào)度最高優(yōu)先級 隊(duì)列中的進(jìn)程運(yùn)行，僅當(dāng)?shù)谝魂?duì)列空閑時(shí)隊(duì)列中的進(jìn)程運(yùn)行，僅當(dāng)?shù)谝魂?duì)列空閑時(shí) 才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行。才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行。Page 33第三章 處理機(jī)調(diào)度與死鎖3.3 進(jìn)程調(diào)度3.3.5 3.3.5 多級反饋隊(duì)列調(diào)度算法多級反饋隊(duì)列調(diào)度算法2 2 調(diào)度算法性能調(diào)度算法性能 若規(guī)定第一個(gè)隊(duì)列的時(shí)間片略大于多數(shù)人機(jī)交互所若規(guī)定第一個(gè)隊(duì)列的時(shí)間片略大于多數(shù)人機(jī)交互所需處理時(shí)間時(shí)，便能較好滿足各種類型用戶的需要。需處理時(shí)間時(shí)，便能較好滿足各種類型用戶的需要。終端型用戶終端型用戶短批處理作業(yè)用戶短批處理作業(yè)用戶長批處理作業(yè)用戶長批處理作業(yè)用戶Page 34第三

22、章 處理機(jī)調(diào)度與死鎖3.5 產(chǎn)生死鎖的原因和必要條件 1 1 典型死鎖的例子典型死鎖的例子 P1P1：申請：申請R1R1 申請申請R2R2 P2P2：申請：申請R2R2 申請申請R1R1 P1P1擁有擁有R1R1申請申請R2R2，P2P2擁有擁有R2R2申請申請R1 R1 Page 35第三章 處理機(jī)調(diào)度與死鎖3.5 產(chǎn)生死鎖的原因和必要條件 3.5.1 3.5.1 資源問題資源問題1 1 可重用性資源和消耗性資源可重用性資源和消耗性資源 (1)(1)可重用性資源：供用戶使用多次的資源可重用性資源：供用戶使用多次的資源一個(gè)可重用性資源單元只能分配給一個(gè)進(jìn)程使用一個(gè)可重用性資源單元只能分配給一個(gè)

23、進(jìn)程使用請求資源請求資源使用資源使用資源釋放資源釋放資源系統(tǒng)中每一類可重用性資源中的單元數(shù)目是相對系統(tǒng)中每一類可重用性資源中的單元數(shù)目是相對 固定的，進(jìn)程在運(yùn)行期間既不能創(chuàng)建也不能刪除固定的，進(jìn)程在運(yùn)行期間既不能創(chuàng)建也不能刪除計(jì)算機(jī)系統(tǒng)中大多數(shù)資源都屬于可重用性資源計(jì)算機(jī)系統(tǒng)中大多數(shù)資源都屬于可重用性資源Page 36第三章 處理機(jī)調(diào)度與死鎖3.5 產(chǎn)生死鎖的原因和必要條件 3.5.1 3.5.1 資源問題資源問題1 1 可重用性資源和消耗性資源可重用性資源和消耗性資源 (2)(2)可消耗性資源：臨時(shí)資源可消耗性資源：臨時(shí)資源可以請求若干個(gè)可消耗性資源單元可以請求若干個(gè)可消耗性資源單元進(jìn)程運(yùn)行

24、過程中，可以不斷的創(chuàng)造可消耗性資源的單元進(jìn)程運(yùn)行過程中，可以不斷的創(chuàng)造可消耗性資源的單元每一類可消耗性資源中的單元數(shù)目是可以不斷變化的每一類可消耗性資源中的單元數(shù)目是可以不斷變化的生產(chǎn)者創(chuàng)建，消費(fèi)者進(jìn)程消耗生產(chǎn)者創(chuàng)建，消費(fèi)者進(jìn)程消耗Page 37第三章 處理機(jī)調(diào)度與死鎖3.5 產(chǎn)生死鎖的原因和必要條件 3.5.1 3.5.1 資源問題資源問題2 2 可搶占性資源和不可搶占性資源可搶占性資源和不可搶占性資源 (1)(1)可搶占性資源可搶占性資源磁帶機(jī)、打印機(jī)等磁帶機(jī)、打印機(jī)等（2 2）不可搶占性資源）不可搶占性資源CPU、主存等，此類資源不會(huì)引起死鎖、主存等，此類資源不會(huì)引起死鎖Page 38第

25、三章 處理機(jī)調(diào)度與死鎖3.5 產(chǎn)生死鎖的原因和必要條件 3.5.3.5. 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖競爭非剝奪性資源競爭非剝奪性資源R1R1：磁帶機(jī)：磁帶機(jī) R2R2：打印機(jī)：打印機(jī) R1R2P1P2Page 39第三章 處理機(jī)調(diào)度與死鎖3.5 產(chǎn)生死鎖的原因和必要條件 3.5.3.5. 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖競爭可消耗性資源競爭可消耗性資源P1： Release(S1)； Reqaest(S3)； P2： Release(S2)； Request(S1)； P3： Release(S3)； Request(S2)； P1： Request(S3)； Release(S

26、1)； P2： Request(S1)； Release(S2)； P3： Request(S2)； Release(S3)； S2P1S3P3S1P2Page 40第三章 處理機(jī)調(diào)度與死鎖3.5 產(chǎn)生死鎖的原因和必要條件 3.5.3.5. 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖進(jìn)程間推進(jìn)順序非法進(jìn)程間推進(jìn)順序非法（）合法（）合法P1：Request(R1)；Request(R2)；P1：Releast(R1)；Release(R2)；P2：Request(R2)；Request(R1)；P2：Release(R2)；Release(R1)； Page 41第三章 處理機(jī)調(diào)度與死鎖3.5 產(chǎn)生死

27、鎖的原因和必要條件 3.5.3.5. 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖（2）進(jìn)程間推進(jìn)順序非法）進(jìn)程間推進(jìn)順序非法P2Rel(R1)P2Rel(R2)P2Req(R1)P2Req(R2)P1Req(R1)P1Req(R2)P1Rel(R1) P1Rel(R2)DPage 42第三章 處理機(jī)調(diào)度與死鎖3.5 產(chǎn)生死鎖的原因和必要條件 3.5.3.5. 計(jì)算機(jī)系統(tǒng)中的死鎖計(jì)算機(jī)系統(tǒng)中的死鎖（2）進(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)，便可能

28、發(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)程死鎖。Page 43第三章 處理機(jī)調(diào)度與死鎖3.5 產(chǎn)生死鎖的原因和必要條件 3.5.3.5. 死鎖的定義、必要條件和處理方法死鎖的定義、必要條件和處理方法互斥條件互斥條件請求和保持條件請求和保持條件不剝奪條件不剝奪條件環(huán)路等待條件環(huán)路等待條件死鎖：多個(gè)進(jìn)程因共享資源而產(chǎn)生的僵局，沒有外死鎖：多個(gè)進(jìn)程因共享資源而產(chǎn)生的僵局，沒有外 力作用將無法向前推進(jìn)。力作用將無法向前推進(jìn)。Page 44第三章 處理機(jī)調(diào)度與死鎖3.5

29、產(chǎn)生死鎖的原因和必要條件 3.5.3 3.5.3 處理死鎖的基本方法處理死鎖的基本方法1 預(yù)防死鎖預(yù)防死鎖2 避免死鎖避免死鎖3 檢測死鎖檢測死鎖4 解除死鎖解除死鎖0 鴕鳥策略鴕鳥策略出現(xiàn)頻率極少時(shí)，置之不理出現(xiàn)頻率極少時(shí)，置之不理設(shè)置條件，破壞死條件之一設(shè)置條件，破壞死條件之一分配資源時(shí)避免進(jìn)入不安全狀態(tài)分配資源時(shí)避免進(jìn)入不安全狀態(tài)允許發(fā)生，及時(shí)檢測并消除允許發(fā)生，及時(shí)檢測并消除撤銷掛起進(jìn)程，回收資源撤銷掛起進(jìn)程，回收資源Page 45第三章 處理機(jī)調(diào)度與死鎖1 1 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件互斥條件互斥條件請求和保持條件請求和保持條件不剝奪條件不剝奪條件環(huán)路等待條件環(huán)路等待條件

30、Page 46第三章 處理機(jī)調(diào)度與死鎖2 2 處理死鎖的基本方法處理死鎖的基本方法1 預(yù)防死鎖預(yù)防死鎖2 避免死鎖避免死鎖3 檢測死鎖檢測死鎖4 解除死鎖解除死鎖0 鴕鳥策略鴕鳥策略Page 47第三章 處理機(jī)調(diào)度與死鎖1 1 摒棄摒棄“請求和保持請求和保持”條件條件（1 1）思想：要么分配所有資源，要么不分配）思想：要么分配所有資源，要么不分配 3.6.1 3.6.1 預(yù)防死鎖預(yù)防死鎖（2 2）優(yōu)點(diǎn)：簡單易實(shí)現(xiàn)、安全性好）優(yōu)點(diǎn)：簡單易實(shí)現(xiàn)、安全性好 （3 3）缺點(diǎn)：資源浪費(fèi)嚴(yán)重、進(jìn)程延遲進(jìn)行）缺點(diǎn)：資源浪費(fèi)嚴(yán)重、進(jìn)程延遲進(jìn)行 3.6 預(yù)防死鎖的方法 Page 48第三章 處理機(jī)調(diào)度與死鎖3.

31、6 預(yù)防死鎖的方法 2 2 摒棄摒棄“不剝奪不剝奪”條件條件（1 1）思想：逐個(gè)提出對資源的請求，有需求不滿足時(shí)）思想：逐個(gè)提出對資源的請求，有需求不滿足時(shí) 釋放資源，視為剝奪。釋放資源，視為剝奪。 3.6.1 3.6.1 預(yù)防死鎖預(yù)防死鎖（2 2）優(yōu)點(diǎn)：進(jìn)程可快速開始）優(yōu)點(diǎn)：進(jìn)程可快速開始 （3 3）缺點(diǎn)：實(shí)現(xiàn)復(fù)雜、開銷大；延長周轉(zhuǎn)時(shí)間；）缺點(diǎn)：實(shí)現(xiàn)復(fù)雜、開銷大；延長周轉(zhuǎn)時(shí)間； 運(yùn)行具有信息不連續(xù)性運(yùn)行具有信息不連續(xù)性Page 49第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 3 3 摒棄摒棄“環(huán)路等待環(huán)路等待”條件條件（1 1）思想：對全部資源編號(hào)，規(guī)定申請資源時(shí)按編號(hào)）思想：對全部資源

32、編號(hào)，規(guī)定申請資源時(shí)按編號(hào) 遞增順序。遞增順序。 3.6.1 3.6.1 預(yù)防死鎖預(yù)防死鎖（2 2）優(yōu)點(diǎn)：資源利用率和系統(tǒng)吞吐量改善）優(yōu)點(diǎn)：資源利用率和系統(tǒng)吞吐量改善 （3 3）缺點(diǎn)：限制新設(shè)備的添加；資源浪費(fèi)；）缺點(diǎn)：限制新設(shè)備的添加；資源浪費(fèi)； 限制用戶編程的靈活性限制用戶編程的靈活性Page 50第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 1 1 避免死鎖避免死鎖 分配資源前，先計(jì)算此次資源分配的安全性，若不會(huì)進(jìn)入分配資源前，先計(jì)算此次資源分配的安全性，若不會(huì)進(jìn)入不安全狀態(tài)，則分配資源，否則，進(jìn)程等待。不安全狀態(tài)，則分配資源，否則，進(jìn)程等待。 3.6.2 3.6.2 系統(tǒng)安全狀態(tài)系統(tǒng)

33、安全狀態(tài)2 2 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài) 系統(tǒng)能按某種進(jìn)程順序系統(tǒng)能按某種進(jìn)程順序(P1，P2，Pn)，來為每個(gè)進(jìn)，來為每個(gè)進(jìn)程程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對資源的最大需求，分配其所需資源，直至滿足每個(gè)進(jìn)程對資源的最大需求，使每個(gè)進(jìn)程都可順利地完成。使每個(gè)進(jìn)程都可順利地完成。 稱為系統(tǒng)安全狀態(tài)，稱為系統(tǒng)安全狀態(tài)，P1，P2，Pn為安全序列。為安全序列。Page 51第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 3 3 系統(tǒng)不安全狀態(tài)系統(tǒng)不安全狀態(tài) 如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。于不安全狀態(tài)。 3.6.2 3.6

34、.2 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)4 4 進(jìn)入不安全狀態(tài)，可能會(huì)導(dǎo)致死鎖進(jìn)入不安全狀態(tài)，可能會(huì)導(dǎo)致死鎖 不進(jìn)入不安全狀態(tài)，一定不會(huì)死鎖不進(jìn)入不安全狀態(tài)，一定不會(huì)死鎖 Page 52第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 5 5 例子例子 1212臺(tái)磁帶機(jī)，三個(gè)進(jìn)程在臺(tái)磁帶機(jī)，三個(gè)進(jìn)程在T T0 0時(shí)刻的狀態(tài)時(shí)刻的狀態(tài) 3.6.2 3.6.2 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)進(jìn) 程 最 大 需 求 已 分 配 可 用 P1 10 5 3 P2 4 2 P3 9 2 為安全序列為安全序列 Page 53第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 6 6 由安全狀態(tài)向不安全狀態(tài)轉(zhuǎn)換由安全狀態(tài)向不安全

35、狀態(tài)轉(zhuǎn)換 T0T0時(shí)刻時(shí)刻P3P3又申請又申請1 1臺(tái)，剩余臺(tái)，剩余2 2臺(tái)臺(tái) 3.6.2 3.6.2 系統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài) 找不到安全序列找不到安全序列 Page 54第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 1 1 所需數(shù)據(jù)結(jié)構(gòu)所需數(shù)據(jù)結(jié)構(gòu)(1)(1)可利用資源向量可利用資源向量AvailableAvailable3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 m個(gè)元素的數(shù)組每類可利用的資源數(shù)目初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變 Availablej=K，則表示系統(tǒng)中現(xiàn)有R j類資源K個(gè)Page 55第三章 處

36、理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 1 1 所需數(shù)據(jù)結(jié)構(gòu)所需數(shù)據(jù)結(jié)構(gòu)(2)(2)最大需求矩陣最大需求矩陣MaxMax3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 nm的矩陣n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對m類資源的最大需求如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最 大數(shù)目為KPage 56第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 1 1 所需數(shù)據(jù)結(jié)構(gòu)所需數(shù)據(jù)結(jié)構(gòu)(3)(3)分配矩陣分配矩陣AllocationAllocation3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 nm的矩陣定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一 進(jìn)程的資源數(shù)如

37、果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分 得R j類資源的數(shù)目為KPage 57第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 1 1 所需數(shù)據(jù)結(jié)構(gòu)所需數(shù)據(jù)結(jié)構(gòu)(4)(4)需求矩陣需求矩陣NeedNeed3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 nm的矩陣表示每一個(gè)進(jìn)程尚需的各類資源數(shù)如果Needi,j=K，則表示進(jìn)程i還需要R j類資源K個(gè)Needi, j=Maxi, j-Allocationi, j Page 58第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 2 2 銀行家算法銀行家算法3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法

38、避免死鎖 設(shè)Request i是進(jìn)程Pi的請求向量，如果Request i j =K，表示進(jìn)程P i需要K個(gè)R j類型的資源。當(dāng)P i發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：(1) 如果Requesti jNeedi,j，便轉(zhuǎn)向步驟(2)；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 (2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。 Page 59第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 2 2 銀行家算法銀行家算法3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖 (3) 系統(tǒng)試探著把資源分配給進(jìn)

39、程P i，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej:= Availablej-Request ij； Allocationi,j:= Allocationi,j+Request ij； Needi,j:= Needi,j-Request ij； (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。 Page 60第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 3 3 安全性算法安全性算法3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免

40、死鎖(1) 設(shè)置兩個(gè)向量： 工作向量Work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work:=Available。 Finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi:=false；當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finishi:=true。 Page 61第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 3 3 安全性算法安全性算法3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖(2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false； Needi,jWorkj；

41、若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。Page 62第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 3 3 安全性算法安全性算法3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖(3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj:= Workj+Allocationi,j； Finishi:=true； go to step （2）； (4) 如果所有進(jìn)程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 Page 63第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 4 4 例子例子3.

42、6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖假定系統(tǒng)中有五個(gè)進(jìn)程P0，P1，P2，P3，P4和三類資源A，B，C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖所示。 Max Allocation 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

43、 Page 64第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 4 4 例子例子3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖(1) 檢測T0時(shí)刻的安全性（板書講解）Max Allocation 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 存在著一個(gè)安全

44、序列P1，P3，P4，P2，P0，故系統(tǒng)是安全的Page 65第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 4 4 例子例子3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖(2) P1請求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查是否分配資源給P1.（板書講解）Max Allocation 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

45、 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 Page 66第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 4 4 例子例子3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖(3) P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：（板書講解）Max Allocation 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

46、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 Page 67第三章 處理機(jī)調(diào)度與死鎖3.6 預(yù)防死鎖的方法 4 4 例子例子3.6.3 3.6.3 利用銀行家算法避免死鎖利用銀行家算法避免死鎖(4) P0請求資源：P0發(fā)出請求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：（板書講解）Max Allocation 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 Page 68第三章 處理機(jī)調(diào)度與死鎖銀行家算法銀行家算法1 判斷請求是否大于最大需求判斷請求是否大于最大需求2 判斷請求是否大于可用資源量判斷請求是否大于可用資源量3 假定資源分配，修改