第四章_死鎖1

1、 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System第四章 死鎖 資源 死鎖概述 鴕鳥算法 死鎖檢測 死鎖避免 死鎖預防 其他問題 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System資源u可搶占資源可搶占資源可以從擁有該資源的進程中搶占而不會產生任何副作用可以從擁有該資源

2、的進程中搶占而不會產生任何副作用處理器、內存處理器、內存u不可搶占資源不可搶占資源不引起相關計算失敗的情況下，無法把它從占有它的進程不引起相關計算失敗的情況下，無法把它從占有它的進程處搶占過來處搶占過來打印機，打印機，CDCD刻錄機（獨占型資源）刻錄機（獨占型資源） 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating Systemu進程使用資源進程使用資源( (不可搶占不可搶占) )所需要的事件可以表述為所需要的事件可以表述為請求資源請求資源使用資源使用資源釋放資源釋放資源u不同系統(tǒng)的資源請求、使用及釋放過程有所不同。不同系統(tǒng)的資源請求、使用及釋放過程

3、有所不同。資源u一般而言，進程間的死鎖問題多由不可搶占資源的排他性使一般而言，進程間的死鎖問題多由不可搶占資源的排他性使用引起。用引起。u對于可搶占資源，若存在潛在的死鎖，可以通過進程間的重對于可搶占資源，若存在潛在的死鎖，可以通過進程間的重新資源調配來解決新資源調配來解決. . 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System資源-資源獲取資源獲取typedef int semaphore;semaphore resource_1;void process_A(void) down(&resource_1); use_resource

4、_1(); up(&resourcde_1);typedef int semaphore;semaphore resource_1;semaphore resource_2;void process_A(void) down(&resource_1); down(&resource_2); use_resource_1(); up(&resourcde_2); up(&resource_1);圖圖. 采用信號量保護資源采用信號量保護資源a). 一個資源一個資源 b). 兩個資源兩個資源采用互斥信號量對資源進行獲取采用互斥信號量對資源進行獲取l一個進程的情形一個進程的情形 北京工商大學北京工商大

5、學 計信學院計信學院Operating SystemOperating System資源-資源獲取資源獲取l 兩個進程的情形兩個進程的情形typedef int semaphore;semaphore resource_1;semaphore resource_2;void process_A(void) down(&resource_1); down(&resource_2); use_both_resource(); up(&resource_2); up(&resource_1);void process_B(void) down(&resource_1); down(&resource

6、_2); use_both_resouce(); up(&resouce_2); up(&resouce_1);typedef int semaphore;semaphore resource_1;semaphore resource_2;void process_A(void) down(&resource_1); down(&resource_2); use_both_resource(); up(&resource_2); up(&resource_1);void process_B(void) down(&resource_2); down(&resource_1); use_both

7、_resouce(); up(&resouce_1); up(&resouce_2);圖圖. 左）無死鎖的互斥左）無死鎖的互斥 右）產生死鎖的互斥右）產生死鎖的互斥 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating SystemP、V操作不當產生死鎖生產者進程 消費者進程 P(mutex) P(mutex) P(empty) P(full) 緩沖區(qū)滿后，先后執(zhí)行生產者進程和消費者進程。 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System 死鎖概述-死鎖定義死鎖定義定義一如果一組進程中，每個進程都

8、在等待只能由該進程集合中其他進程才能引發(fā)的事件，這個進程集合就是死鎖的定義二一組進程中，每個進程都無限等待被該組進程中另一進程所占有的資源，因而永遠無法得到的資源，這種現象稱為死鎖，這一組進程就稱為死鎖進程 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System互斥（資源獨占）一個資源每次只能給一個進程使用占有等待一個進程在申請新的資源的同時保持對原有資源的占有 非剝奪（不可搶占）資源申請者不能強行的從資源占有者手中奪取資源，資源只能由占有者自愿釋放環(huán)路等待存在一個進程等待隊列 P1 , P2 , , Pn, 其中P1等待P2占有的資源，P2

9、等待P3占有的資源，Pn等待P1占有的資源，形成一個進程等待環(huán)路死鎖的四個必要條件死鎖的四個必要條件 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System死鎖建模-資源分配圖形式化描述資源分配圖 G=(V,E),其中頂點集V=PR,P是進程集合：P=P1,P2,Pn資源集R=r1,r2,rm,ri表示系統(tǒng)中的ri類資源E是邊的集合，E中有兩類邊分配邊 (rj,Pi)請求邊( Pi,rj) 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating SystemARSRRBB圖. 資源分配圖a).占有一個資源

10、 b).請求一個資源 c). 死鎖如果各類資源數為1，則系統(tǒng)出現死鎖的充要條件是資源分配圖含圈 PiPP.死鎖建模-資源分配圖 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System死鎖定理如果資源分配圖中沒有環(huán)路，則系統(tǒng)中沒有死鎖，如果資源分配圖中沒有環(huán)路，則系統(tǒng)中沒有死鎖，如果圖中存在環(huán)路則系統(tǒng)中如果圖中存在環(huán)路則系統(tǒng)中可能可能存在死鎖存在死鎖如果每個資源類中只包含一個資源實例，則環(huán)路如果每個資源類中只包含一個資源實例，則環(huán)路是死鎖

11、存在的充分必要條件是死鎖存在的充分必要條件有環(huán)有死鎖有環(huán)有死鎖有環(huán)無死鎖有環(huán)無死鎖 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System解決死鎖問題的方法按照死鎖發(fā)生的時間過程，來思考解決思索問題的方法忽略問題鴕鳥算法設計無死鎖的系統(tǒng)死鎖防止在應用編程時或資源分配管理設計時破壞死鎖的必要條件死鎖避免進行資源分配時，判斷是否存在安全序列，存在情況下進行分配，否則拒絕分配允許死鎖、出現排除死鎖檢測死鎖恢復 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System鴕鳥算法 鴕鳥算法的思路鴕鳥算法的

12、思路當計算機系統(tǒng)中存在死鎖的威脅但是很少出現時當計算機系統(tǒng)中存在死鎖的威脅但是很少出現時, ,人們采取的辦法是不去管它人們采取的辦法是不去管它, ,而是忽略它而是忽略它. .* *如如果系統(tǒng)遇見死鎖崩潰果系統(tǒng)遇見死鎖崩潰, ,則重新啟動系統(tǒng)則重新啟動系統(tǒng); ;* *設計者不會以性能損失和可用性損失為代價去防止死鎖設計者不會以性能損失和可用性損失為代價去防止死鎖.;.; 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System死鎖檢測和死鎖恢復允許死鎖發(fā)生，然后再恢復-允許死鎖發(fā)生，操作系統(tǒng)不斷監(jiān)視系統(tǒng)進展情況，判斷死鎖是否發(fā)生-一旦死鎖發(fā)生則采

13、取專門的措施，解除死鎖并以最小的代價恢復操作系統(tǒng)運行（死鎖恢復） 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System檢測時機：檢測時機： 當進程等待時檢測死鎖 定時檢測 系統(tǒng)資源利用率下降時檢測死鎖死鎖檢測和死鎖恢復 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System每種類型一個資源的死鎖檢測資源分配圖化簡檢測有向圖環(huán)路的算法（P249)每種類型多個資源的死鎖檢測基于矩陣的算法（例P251)死鎖檢測 北京工商大學北京工商大學 計信學院計信學院Operating SystemOpera

14、ting System死鎖檢測不做死鎖避免，定期檢測死鎖是否發(fā)生采用化簡資源分配圖的方法可以檢測系統(tǒng)中有無進程處于死鎖狀態(tài)資源分配圖的簡化過程在圖中找一個進程頂點在圖中找一個進程頂點i i, P, Pi i沒有請求邊或請求邊均能立即滿足沒有請求邊或請求邊均能立即滿足若找到這樣的若找到這樣的P Pi i則將與則將與i i相連的邊全部刪去，轉相連的邊全部刪去，轉；否則化簡過程結；否則化簡過程結束束如果化簡后所有的進程頂點都成了如果化簡后所有的進程頂點都成了孤立點孤立點，則稱該圖可完全化簡；否則，則稱該圖可完全化簡；否則稱該圖是不可完全化簡的稱該圖是不可完全化簡的系統(tǒng)中有死鎖的充分必要條件是資源分配

15、圖不可完全化簡經過化簡后，非孤立點的進程處于死鎖狀態(tài)。 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System資源分配圖的簡化過程資源分配圖的簡化過程在圖中找一個進程頂點在圖中找一個進程頂點i i, P, Pi i的請求邊均能立即滿足的請求邊均能立即滿足若找到這樣的若找到這樣的P Pi i則將與則將與i i相連的邊全部刪去，轉相連的邊全部刪去，轉；否則化簡過程結束否則化簡過程結束如果化簡后所有的進程頂點都成了如果化簡后所有的進程頂點都成了孤立點孤立點，則稱該圖可，則稱該圖可完全化簡；否則稱該圖是不可完全化簡的完全化簡；否則稱該圖是不可完全化簡

16、的系統(tǒng)中有死鎖的系統(tǒng)中有死鎖的充分必要條件充分必要條件是是資源分配圖不可完全化簡資源分配圖不可完全化簡。經過化簡后，非孤立點的進程處于死鎖狀態(tài)。經過化簡后，非孤立點的進程處于死鎖狀態(tài)。 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System死鎖恢復 利用搶占恢復利用搶占恢復 強行剝奪現有運行進程的資源給競爭的進程使用強行剝奪現有運行進程的資源給競爭的進程使用. 利用回退恢復利用回退恢復利用檢查點機制利用檢查點機制(checkpoint),通過保存檢查點內容通過保存檢查點內容進行回退到死鎖前狀態(tài)，人工干預資源的使用進行回退到死鎖前狀態(tài)，人工干預

17、資源的使用. 通過殺死進程恢復通過殺死進程恢復殺掉環(huán)里的進程殺掉環(huán)外部的進程殺死可以從頭開始重新執(zhí)行的進程 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating Systeml 剝奪哪個進程的哪些資源;l 需要為剝奪資源的進程做些什么（剝奪資源的進程需要重新運行或回退到某一點開始繼續(xù)運行）l 怎樣保證不發(fā)生“餓死”現象l 怎么使進程回到原來狀態(tài)帶來的開銷最小搶占和回退時需要考慮的問題 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System死鎖避免基本思想：基本思想：l 在系統(tǒng)運行過程中，對進程發(fā)出的每一

18、個系統(tǒng)能夠滿足的資源申請進行動態(tài)檢查，并根據檢查結果決定是否分配資源，若分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。l 這是一種保證系統(tǒng)不進入死鎖狀態(tài)的動態(tài)策略。 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System死鎖避免p資源軌跡圖（P252)p安全狀態(tài)和不安全狀態(tài)安全狀態(tài)和不安全狀態(tài)設系統(tǒng)中有n個進程，若存在一個序列P1，2n使得Pi(i1，2n)以后還需要的資源可以通過系統(tǒng)現有資源加上所有Pj(ji)占有的資源來滿足 ，則稱這個系統(tǒng)處于安全狀態(tài)序列, , ,n稱為安全序列p操作方法操作方法在系統(tǒng)處理資源申請時，判斷如果滿足某個

19、進程的申請時，系統(tǒng)是否還處于安全狀態(tài)？是則滿足本次資源申請 ，否則拒絕 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System不安全狀態(tài)l 不安全狀態(tài):不存在一個安全序列l(wèi) 不安全狀態(tài)不一定導致死鎖 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System死鎖避免l 只要能使系統(tǒng)總是處于安全狀態(tài)就可避免死鎖的發(fā)生.l 每當有進程退出資源申請時,系統(tǒng)可以通過分析各個進程已經占有的資源數目、尚需資源的數目以及系統(tǒng)中可以分配的剩余資源數目，以決定是否為當前的申請進程分配資源。l 如果能使系統(tǒng)處于安全

20、狀態(tài)，則可為進程分配資源，否則暫且不為申請進程分配資源。 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System銀行家算法 把操作系統(tǒng)比作一個銀行家 各種資源比作周轉資金 申請資源的進程比作向銀行貸款的顧客 操作系統(tǒng)的資源分配問題轉化為銀行家利用其資金發(fā)放貸款的問題。 1. 銀行家能貸款給顧客，滿足顧客對資金的要求。（操作系統(tǒng)能滿足每個進程對資源的要求） 2. 銀行家可以安全地回收其全部貸款，而不至于破產。（系統(tǒng)不處于死鎖） 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System為了保證資金

21、的安全，銀行家規(guī)定：當一個顧客對資金的最大需求量不超過銀行家現有的資金時就可接納該顧客；顧客可以分期貸款，但貸款的總數不能超過顧客對資金的最大需求量；當銀行家現有的資金不能滿足顧客尚需的貸款數額時，對顧客的貸款可推遲支付，但總能使顧客在有限的時間內得到貸款；當顧客得到所需的全部資金后，一定能在有限的時間內歸還所有資金。 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System操作系統(tǒng)按照銀行家的規(guī)定為進程分配資源進程提出對資源的最大需要量。每次申請能時系統(tǒng)需判斷該進程的申請之和是否超過它的最大需求量。若沒超過，還需測試系統(tǒng)現存的資源能否滿足該進

22、程尚需的最大資源量。若滿足，則按當前申請分配，否則推遲分配。這樣做能保證在任何時刻至少有一個進程可以得到所需要的全部資源而執(zhí)行結束，結束后歸還的資源加入到系統(tǒng)的剩余資源中，這些資源又至少可以滿足另一個進程的最大需求。最后保證系統(tǒng)中的所有進程都能在有限地時間內得到需要的全部資源。 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System銀行家算法-單個資源的銀行家算法設銀行家有10萬貸款，P,Q,R分別需要8,3,9萬元搞項目（假設任何人滿足資金總額后都會歸還所有貸款）如果P已申請到了4萬，Q申請2萬，R申請2萬，則銀行家還剩2萬此時，如果Q又申

23、請1萬顯然，如果滿足Q的申請，有安全序列 如果Q申請之后，R要申請4萬。如果滿足R的申請，則不存在安全序列 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System資源分配程序的工作過程當進程提出資源申請時系統(tǒng)首先檢查該進程對資源的申請量是否超過其最大需求量系統(tǒng)現有資源能否滿足進程需要若能則進一步檢查若把資源分給該進程系統(tǒng)能否處于安全狀態(tài)若安全則分配，否則置該進程為等待資源狀態(tài) 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量P12

24、97P25105P3242系統(tǒng)剩余資源量系統(tǒng)剩余資源量3系統(tǒng)處于安全狀態(tài)系統(tǒng)處于安全狀態(tài),安全序列為安全序列為P3 P2 P1例：12個同類資源供3個進程共享 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating SystemP1提出再申請一個資源目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量P1396P25105P3242系統(tǒng)剩余資源量系統(tǒng)剩余資源量2系統(tǒng)處于不安全狀態(tài)系統(tǒng)處于不安全狀態(tài) 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating Systemn：系統(tǒng)中進程的總數m：資源類總數Availabl

25、e:可使用資源向量 ARRAY1.m of integer;Availablej=k 表示系統(tǒng)中有k個j類資源。Max:最大需求矩陣 ARRAY1.n,1.m of integer;Maxi,j=k 表示進程i最多需要k個j類資源。銀行家算法-多個資源的銀行家算法 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating SystemAllocation:分配矩陣ARRAY1.n,1.m of integer;Allocationi,j=k 表示進程i當前已分得k個j類資源。Need:需求矩陣 ARRAY1.n,1.m of integer; Needi,j

26、 表示進程i還需要k個j類資源。Request:進程申請資源向量 ARRAY1.n,1.m of integer; Requesti,j 表示進程i需要申請k個j類資源。銀行家算法-多個資源的銀行家算法 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System簡記符號：AvailableMaxiAllocationiNeediRequesti銀行家算法-多個資源的銀行家算法 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System當進程pi提出資源申請時，系統(tǒng)執(zhí)行下列步驟：（1）若Request

27、iNeedi,轉（2）； 否則錯誤返回（2）若RequestiAvailable, 轉（3）；否則進程等待銀行家算法-多個資源的銀行家算法 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System(3）假設系統(tǒng)分配了資源，則有：Available:=Available-Requesti;Allocationi:= Allocationi+Requesti;Needi:=Needi-Requesti若系統(tǒng)新狀態(tài)是安全的，則分配完成若系統(tǒng)新狀態(tài)是不安全的，則恢復原狀態(tài)，進程等待銀行家算法-多個資源的銀行家算法 北京工商大學北京工商大學 計信學院計信

28、學院Operating SystemOperating System為進行安全性檢查，定義數據結構：Work:ARRAY1.m of integer;Worki=k 表示剩余i類資源k個。Finish:ARRAY1.n of Boolean;Finishi=true 表示進程i能獲得所需資源執(zhí)行完畢，并能釋放全部獲得資源。初值為False.銀行家算法-多個資源的銀行家算法 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System安全性檢查的步驟：(1) Work:=Available; Finish:=false;(2) 尋找滿足條件的i： a

29、.Finishi=false; b.NeediWork;如果不存在，則轉(4)銀行家算法-多個資源的銀行家算法 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System(3) Work:=Work+Allocationi; Finishi:=true; 轉(2)(4) 若對所有i,Finishi=true,則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)銀行家算法-多個資源的銀行家算法多個資源的銀行家算法實例3類資源類資源A、B、C。A=10，B=5，C=7。現有?，F有5個進程個進程P1、P2、P3、P4、P5. 資源申請資源申請進程進程目前占有量目前占

30、有量最大需求量最大需求量尚需要量尚需要量 A B CA B CA B CP1 0 1 07 5 37 4 3P2 2 0 03 2 21 2 2P3 3 0 29 0 26 0 0P4 2 1 12 2 20 1 1P5 0 0 24 3 34 3 1系統(tǒng)剩余資源量系統(tǒng)剩余資源量 A B C 3 3 2系統(tǒng)處于安全狀態(tài)，安全序列系統(tǒng)處于安全狀態(tài)，安全序列P2、P4、 P5、 P3、 P1P2提出申請，A=1, B=0, C=2后 資源申請資源申請進程進程目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量 A B CA B CA B CP1 0 1 07 5 37 4 3P2 3 0 23

31、 2 20 2 0P3 3 0 29 0 26 0 0P4 2 1 12 2 20 1 1P5 0 0 24 3 34 3 1系統(tǒng)剩余資源量系統(tǒng)剩余資源量 A B C 2 3 0系統(tǒng)處于安全狀態(tài)，安全序列系統(tǒng)處于安全狀態(tài)，安全序列P2、P4、 P5、 P1、 P3P5提出申請，A=3, B=3, C=0后 資源申請資源申請進程進程目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量 A B CA B CA B CP1 0 1 07 5 37 4 3P2 3 0 23 2 20 2 0P3 3 0 29 0 26 0 0P4 2 1 12 2 20 1 1P5 0 0 24 3 34 3 1

32、系統(tǒng)剩余資源量系統(tǒng)剩余資源量 A B C 2 3 0申請超出了當前剩余資源數量，不實施分配。申請超出了當前剩余資源數量，不實施分配。P1提出申請，A=0, B=2, C=0后 資源申請資源申請進程進程目前占有量目前占有量最大需求量最大需求量尚需要量尚需要量 A B CA B CA B CP1 0 3 07 5 37 2 3P2 3 0 23 2 20 2 0P3 3 0 29 0 26 0 0P4 2 1 12 2 20 1 1P5 0 0 24 3 34 3 1系統(tǒng)剩余資源量系統(tǒng)剩余資源量 A B C 2 1 0預分配后，系統(tǒng)處于不安全狀態(tài)，不能給預分配后，系統(tǒng)處于不安全狀態(tài)，不能給P1實施

33、資源分配。實施資源分配。 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System銀行家算法的缺點算法花費時間多要求每類資源的數量固定不變事先知道資源的最大需求量資源利用率有時會降低 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System死鎖預防死鎖避免從本質上來說是不可能的因為需要預先知道未來請求的最大資源量實際中，使用死鎖避免的方法思想：思想：在設計系統(tǒng)時，通過確定資源分配算法，排除發(fā)生死鎖的可能性具體的做法破壞產生死鎖的四個必要條件中的任一個 北京工商大學北京工商大學 計信學院計信學院O

34、perating SystemOperating System破壞“互斥使用/資源獨占”條件資源轉換技術：把獨占資源變?yōu)楣蚕碣Y源SPOOLing技術 解決不允許任何進程直接占有打印機的問題設計一個“精靈deamon”進程/線程負責管理打印機，進程需要打印時，將請求發(fā)給該daemon，由它完成打印任務 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System破壞“占有且等待”條件l 實施方案1：靜態(tài)資源分配策略 要求每個進程在運行前必須一次性申請它所要求的所有資源，且僅當該進程所要資源均可滿足時才給予一次性分配 優(yōu)點：優(yōu)點：簡單、安全、容易實施

35、缺點：缺點：嚴重浪費資源；一些進程長期占用資源，會導致其他使用該資源的進程得不到運行（饑餓）。 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System破壞“互斥使用/資源獨占”條件實現方案2：動態(tài)資源分配在允許進程動態(tài)申請資源前提下，一個進程在申請新的資源不能立即得到滿足而變?yōu)榈却隣顟B(tài)之前，必須釋放已占有的全部資源，若需要再重新申請缺點：缺點：會使進程處于等待狀態(tài) 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System破壞“不可搶占”條件實現方案：虛擬化資源搶占資源當一個進程申請的資源被其他

36、進程占用時，可以通過操作系統(tǒng)搶占這一資源(兩個進程優(yōu)先級不同)局限性：適用于狀態(tài)易于保存和恢復的資源CPU、內存 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System破壞“環(huán)路等待”條件采用資源有序分配策略采用資源有序分配策略把系統(tǒng)中所有資源編號進程在申請資源時必須嚴格按資源編號的遞增次序進行，否則操作系統(tǒng)不予分配。資源編號原則資源編號原則緊缺、稀少的資源編號較大。 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating SystemR=r1,r2,r3,rm表示一組資源，定義函數表示一組資源，定義函數

37、F(R)=N,其中，其中，N是一組自然數是一組自然數,表示資源的編號。假定表示資源的編號。假定m=4,r1,r2,r3,r4分別分別為磁盤機、磁帶機、掃描儀和打印機。并且為磁盤機、磁帶機、掃描儀和打印機。并且F(掃描儀）掃描儀）=1，F(磁盤機）磁盤機）=5，F(磁帶機）磁帶機）=4，F(打印機）打印機）=2。證明：證明：假設采用該策略后，系統(tǒng)仍存在環(huán)路，環(huán)路中的進程假設采用該策略后，系統(tǒng)仍存在環(huán)路，環(huán)路中的進程為為P1,P2,P3Pn,其中其中Pi等待等待Pi+1的資源，的資源，Pn等待等待P0占有的占有的資源。由于資源。由于Pi占有資源占有資源ri,又要申請又要申請ri+1,因此存在因此存

38、在F(ri)F(ri+1),該式對所有該式對所有F都成立，即：都成立，即： F(r0)F(r1)F(r2).F(rn)F(r0)利用利用反證法反證法證明該策略能破壞循環(huán)等待條件證明該策略能破壞循環(huán)等待條件 北京工商大學北京工商大學 計信學院計信學院Operating SystemOperating System其他問題兩階段加鎖數據庫應用中使用第一階段：進程試圖對所需記錄加鎖；如果成功，就開始第二階段；如果不成功，就釋放所有加鎖的記錄，重新開始第一階段第二階段：真正讀寫記錄，完成更新后釋放鎖通信死鎖A和B通信過程中，A發(fā)送消息給B，但由于網絡原因，B并沒有收到A在等待B回復，而B在等待A發(fā)送信息，造成死鎖不是典