2014第三章處理機調(diào)度與死鎖

1、計算機操作系統(tǒng)楊為民 湯小丹 等 編著23.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因：(1) 競爭資源。 (2) 進程間推進順序非法。3產(chǎn)生死鎖的必要條件：(1) 互斥條件 (2) 請求和保持條件 (3) 不剝奪條件 (4) 環(huán)路等待條件3.5.2 產(chǎn)生死鎖的必要條件4處理死鎖的基本方法：(1) 預防死鎖：限制條件 (2) 避免死鎖：防止進入不安全狀態(tài) (3) 檢測死鎖：檢測進程和資源 (4) 解除死鎖：解脫死鎖進程3.5.3 處理死鎖的基本方法53.6 預防死鎖的方法3.6.1 預防死鎖3.6.2 系統(tǒng)安全狀態(tài)3.6.3 利用銀行家算法避免死鎖6預防死鎖：1. 摒棄“請求和保持”條件 2. 摒棄

2、“不剝奪”條件 3. 摒棄“環(huán)路等待”條件3.6.1 預防死鎖73.6.2 系統(tǒng)安全狀態(tài)1. 安全狀態(tài)在避免死鎖的方法中，允許進程動態(tài)地申請資源，但系統(tǒng)在進行資源分配之前，應先計算此次資源分配的安全性。若此次分配不會導致系統(tǒng)進入不安全狀態(tài)，則將資源分配給進程；否則，令進程等待。所謂安全狀態(tài)，是指系統(tǒng)能按某種進程順序(P1, P2, ，Pn)(稱P1, P2, , Pn序列為安全序列)，來為每個進程Pi分配其所需資源，直至滿足每個進程對資源的最大需求，使每個進程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。8進 程 最 大 需 求 已 分 配 可 用 P1P2P310

3、4952233.6.2 系統(tǒng)安全狀態(tài)2. 安全狀態(tài)之例我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進程P1、 P2和P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示： 93.6.2 系統(tǒng)安全狀態(tài)3. 由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進入不安全狀態(tài)。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進入不安全狀態(tài)。因為，此時也無法再找到一個安全序列，例如，把其余的2臺分配給

4、P2，這樣，在P2完成后只能釋放出4臺，既不能滿足P1尚需5臺的要求，也不能滿足P3尚需6臺的要求，致使它們都無法推進到完成，彼此都在等待對方釋放資源，即陷入僵局，結(jié)果導致死鎖。103.6.3 利用銀行家算法避免死鎖銀行家算法的實質(zhì):要設(shè)法保證系統(tǒng)動態(tài)分配資源后不進入不安全狀態(tài)，以避免可能產(chǎn)生的死鎖。銀行家算法的執(zhí)行有個前提條件，即要求進程必須預先提出自己的最大資源請求數(shù)量，這一數(shù)量不可能超過系統(tǒng)資源的總量，系統(tǒng)資源的總量是一定的。113.6.3 利用銀行家算法避免死鎖1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可

5、利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。12Needi,j=Maxi,j-Allocationi,j 3.6.3 利用銀行家算法避免死鎖(2) 最大需求矩陣Max。這是一個nm的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Maxi,j=K，則表示進程i需要Rj類資源的最大數(shù)目為K。(3) 分配矩陣Allocation。這也是一個nm的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。如果Allocationi,j=K，則表示進程i當前

6、已分得Rj類資源的數(shù)目為K。(4) 需求矩陣Need。這也是一個nm的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Needi,j=K，則表示進程i還需要Rj類資源K個，方能完成其任務。133.6.3 利用銀行家算法避免死鎖2. 銀行家算法設(shè)Requesti是進程Pi的請求向量，如果Requestij=K，表示進程Pi需要K個Rj類型的資源。當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：(1) 如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。(2) 如果RequestijAvailablej，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源

7、，Pi須等待。 143.6.3 利用銀行家算法避免死鎖(3) 系統(tǒng)試探著把資源分配給進程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej = Availablej-Requestij; Allocationi,j= Allocationi,j+Requestij; Needi,j = Needi,j-Requestij;(4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。 153.6.3 利用銀行家算法避免死鎖3. 安全性算法 設(shè)置兩個向量： 工作向

8、量Work: 它表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work=Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi=false; 當有足夠資源分配給進程時， 再令Finishi=true。163.6.3 利用銀行家算法避免死鎖(2) 從進程集合中找到一個能滿足下述條件的進程： Finishi=false; Needi,jWorkj； 若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。(3) 當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應執(zhí)行：Workj=Work

9、i+Allocationi,j;Finishi=true;go to step 2; (4) 如果所有進程的Finishi=true都滿足， 則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。17圖 3-15 T0時刻的資源分配表 3.6.3 利用銀行家算法避免死鎖4. 銀行家算法之例 假定系統(tǒng)中有五個進程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖 3-15 所示。18圖 3-16 T0時刻的安全序列 3.6.3 利用銀行家算法避免死鎖(1) T0時刻的安全性：193.6.3 利用銀行家算法避免死鎖(2) P1請

10、求資源：P1發(fā)出請求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系統(tǒng)先假定可為P1分配資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如圖 3-15 中的圓括號所示。 再利用安全性算法檢查此時系統(tǒng)是否安全。20圖 3-17 P1申請資源時的安全性檢查 3.6.3 利用銀行家算法避免死鎖21(3) P4請求資源：P4發(fā)出請求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進行檢查： Req

11、uest4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0)不小于等于 Available(2, 3, 0)，讓P4等待。 (4) P0請求資源：P0發(fā)出請求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進行檢查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系統(tǒng)暫時先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖 3-18 所示。 3.6.3 利用銀行家算法避免死鎖22圖 3-18 為P0分配資源后的有關(guān)資源數(shù)據(jù) 3.6.3 利用銀行家算法避免死鎖233.7 死鎖

12、的檢測與解除3.7.1 死鎖的檢測3.7.2死鎖的解除243.7.1死鎖的檢測當系統(tǒng)為進程分配資源時，若未采取任何限制性措施，則系統(tǒng)必須提供檢測和解除死鎖的手段，為此，系統(tǒng)必須做到：(1) 保存有關(guān)資源的請求和分配信息；(2) 提供一種算法，以利用這些信息來檢測系統(tǒng)是否已進入死鎖狀態(tài)。253.7.1死鎖的檢測1資源分配圖(Resource Allocation Graph)系統(tǒng)死鎖可利用資源分配圖來描述。該圖是由一組結(jié)點N和一組邊E所組成的一個對偶G=(N,E)，它具有下述形式的定義和限制：把N分為兩個互斥的子集，即一組進程結(jié)點P=p1，p2，pn和一組資源結(jié)點R=r1，r2，rn，N=PR。

13、在圖3-20所示的例子中，P=p1，p2，R=r1，r2，N=r1，r2p1，p2。 263.7.1死鎖的檢測(2) 凡屬于E中的一個邊eE，都連接著P中的一個結(jié)點和R中的一個結(jié)點，e=pi，rj是資源請求邊，由進程pi指向資源rj，它表示進程pi請求一個單位的rj資源。e=rj，pi是資源分配邊，由資源rj指向進程pi，它表示把一個單位的資源rj分配給進程pi。圖3-13中示出了兩個請求邊和兩個分配邊，即E=(p1，r2)，(r2，p2)，(p2，r1)，(r1，p1)。我們用圓圈代表一個進程，用方框代表一類資源。由于一種類型的資源可能有多個，我們用方框中的一個點代表一類資源中的一個資源。此

14、時，請求邊是由進程指向方框中的rj，而分配邊則應始于方框中的一個點。27圖3-20每類資源有多個時的情況 3.7.1死鎖的檢測283.7.1死鎖的檢測2死鎖定理我們可以利用把資源分配圖加以簡化的方法，來檢測當系統(tǒng)處于S狀態(tài)時是否為死鎖狀態(tài)。簡化方法如下：(1) 在資源分配圖中，找出一個既不阻塞又非獨立的進程結(jié)點Pi。在順利的情況下，Pi可獲得所需資源而繼續(xù)運行，直至運行完畢，再釋放其所占有的全部資源，這相當于消去pi所求的請求邊和分配邊，使之成為孤立的結(jié)點。29圖3-21資源分配圖的簡化 3.7.1死鎖的檢測303.7.1死鎖的檢測(2) p1釋放資源后，便可使p2獲得資源而繼續(xù)運行，直至p2

15、完成后又釋放出它所占有的全部資源，形成圖(c)所示的情況。(3) 在進行一系列的簡化后，若能消去圖中所有的邊，使所有的進程結(jié)點都成為孤立結(jié)點，則稱該圖是可完全簡化的；若不能通過任何過程使該圖完全簡化，則稱該圖是不可完全簡化的。對于較復雜的資源分配圖，可能有多個既未阻塞，又非孤立的進程結(jié)點，已經(jīng)證明，所有的簡化順序，都將得到相同的不可簡化圖?？梢宰C明：S為死鎖狀態(tài)的充分條件是：當且僅當S狀態(tài)的資源分配圖是不可完全簡化的。該充分條件被稱為死鎖定理。313.7.1死鎖的檢測3死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)死鎖檢測中的數(shù)據(jù)結(jié)構(gòu)類似于銀行家算法中的數(shù)據(jù)結(jié)構(gòu)：(1) 可利用資源向量Available，它表示了m類資

16、源中每一類資源的可用數(shù)目。(2) 把不占用資源的進程(向量Allocationi:=0)記入L表中，即LiL。(3) 從進程集合中找到一個RequestiWork的進程，做如下處理： 將其資源分配圖簡化，釋放出資源，增加工作向量Work:=Work + Allocation i。 將它記入L表中。323.7.1死鎖的檢測(4) 若不能把所有進程都記入L表中，便表明系統(tǒng)狀態(tài)S的資源分配圖是不可完全簡化的。 因此，該系統(tǒng)狀態(tài)將發(fā)生死鎖。Work:=Available；L:=Li |Allocation i=0Request i=0for all LiL dobeginfor all Request

17、 iWork dobeginWork:=Work + Allocation i；LiL；endenddeadlock:= (L=p1，p2，pn)；333.7.2死鎖的解除當發(fā)現(xiàn)有進程死鎖時，便應立即把它們從死鎖狀態(tài)中解脫出來。常采用解除死鎖的兩種方法是：(1) 剝奪資源。從其它進程剝奪足夠數(shù)量的資源給死鎖進程，以解除死鎖狀態(tài)。(2) 撤消進程。最簡單的撤消進程的方法是使全部死鎖進程都夭折掉；稍微溫和一點的方法是按照某種順序逐個地撤消進程，直至有足夠的資源可用，使死鎖狀態(tài)消除為止。在出現(xiàn)死鎖時，可采用各種策略來撤消進程。例如，為解除死鎖狀態(tài)所需撤消的進程數(shù)目最??；或者，撤消進程所付出的代價最小

18、等。一種付出最小代價的方法如圖3-22所示。34圖 3-22付出代價最小的死鎖解除方法 3.7.2死鎖的解除353.7.2死鎖的解除假定在死鎖狀態(tài)時，有死鎖進程P1，P2，Pk。首先，撤消進程P1，使系統(tǒng)狀態(tài)由SU1，付出的代價為CU1，然后，仍然從S狀態(tài)中撤消進程P2，使狀態(tài)由SU2，其代價為CU2，如此下去可得到狀態(tài)U1，U2，Un。若此時系統(tǒng)仍處于死鎖狀態(tài)，需再進一步撤消進程，如此下去，直至解除死鎖狀態(tài)為止。這種方法為解除死鎖狀態(tài)可能付出的代價將是k(k-1)(k-2)/2C。顯然，所花費的代價很大，因此，這是一種很不實際的方法。36一個比較有效的方法是對死鎖狀態(tài)S做如下處理：從死鎖狀態(tài)

19、S中先撤消一個死鎖進程P1，使系統(tǒng)狀態(tài)由S演變成U1，將P1記入被撤消進程的集合d(T)中，并把所付出的代價C1加入到rc(T)中；對死鎖進程P2、P3等重復上述過程，得到狀態(tài)U1，U2，Ui，Un，然后，再按撤消進程時所花費代價的大小，把它插入到由S狀態(tài)所演變的新狀態(tài)的隊列L中。顯然，隊列L中的第一個狀態(tài)U1是由S狀態(tài)花最小代價撤消一個進程所演變成的狀態(tài)。在撤消一個進程后，若系統(tǒng)仍處于死鎖狀態(tài)，則再從U1狀態(tài)按照上述處理方式再依次地撤消一個進程，得到U1，U2，Uk狀態(tài)，再從狀態(tài)中選取一個代價最小的Uj ，如此下去，直到死鎖狀態(tài)解除為止。為把系統(tǒng)從死鎖狀態(tài)中解脫出來，所花費的代價可表示為：R

20、(S)min=minCUi+minCUj+minCUk+ 3.7.2死鎖的解除37策略死鎖預防死鎖避免死鎖檢測和恢復很保守；對資源不做調(diào)配使用介于預防和檢測方法之間，安全狀態(tài)下才分配非常開放；申請資源就分配，但定期檢測死鎖采用的不同方式一次性分配所有資源搶占式分配資源資源編號，按序分配至少應找出一個安全序列定期調(diào)用檢測算法，查看是否出現(xiàn)死鎖主要優(yōu)點適用于執(zhí)行單一突發(fā)活動的進程不需要搶占適用于資源狀態(tài)便于保存和恢復的情況由于系統(tǒng)設(shè)計時已解決問題，不需要運行時計算不需要搶占從來不延誤進程的開始執(zhí)行便于聯(lián)機處理主要缺點效率低延誤進程的開始執(zhí)行搶占動作比實際需要的次數(shù)更多易出現(xiàn)環(huán)路重啟不允許增加對資源

21、的申請必須知道以后對資源的申請情況進程可能被阻塞很長時期喪失固有的搶占性38例 某系統(tǒng)有11臺打印機，N個進程共享打印機資源，每個進程要求3臺。當N的取值不超過_時，系統(tǒng)不會發(fā)生死鎖。最壞的情況是：N個進程每個進程都得到了兩臺打印機，都去申請第3臺打印機。為了保證系統(tǒng)不會發(fā)生死鎖，此時剩余打印機至少應該還有1臺，即有：11-2N1解得N5。39作業(yè)修訂版:P101 1、6、16、19、20第三版：P114 1、10、18、21、2240第四章 存儲器管理4.1 存儲器的層次結(jié)構(gòu)4.2 程序的裝入和鏈接 4.3 連續(xù)分配方式 4.4 基本分頁存儲管理方式 4.5 基本分段存儲管理方式 4.6 虛

22、擬存儲器的基本概念 4.7 請求分頁存儲管理方式 4.8 頁面置換算法 4.9 請求分段存儲管理方式414.1 存儲器的層次結(jié)構(gòu)1、多級存儲器結(jié)構(gòu)424.1 存儲器的層次結(jié)構(gòu)2、主存儲器與寄存器主存儲器、寄存器3、高速緩存和磁盤緩存高速緩存、磁盤緩存434.2 程序的裝入和鏈接在多道程序環(huán)境下，要使程序運行，必須先為之創(chuàng)建進程。而創(chuàng)建進程的第一件事，便是將程序和數(shù)據(jù)裝入內(nèi)存。將一個用戶源程序變?yōu)橐粋€可在內(nèi)存中執(zhí)行的程序，通常都要經(jīng)過以下幾個步驟：首先是要編譯，由編譯程序(Compiler)將用戶源代碼編譯成若干個目標模塊(Object Module)；其次是鏈接，由鏈接程序(Linker)將編

23、譯后形成的一組目標模塊，以及它們所需要的庫函數(shù)鏈接在一起，形成一個完整的裝入模塊(Load Module)；最后是裝入，由裝入程序(Loader)將裝入模塊裝入內(nèi)存。圖4-1示出了這樣的三步過程。本節(jié)將扼要闡述程序(含數(shù)據(jù))的鏈接和裝入過程。44圖 4-1 對用戶程序的處理步驟 4.2 程序的裝入和鏈接454.2.1 程序的裝入1. 絕對裝入方式(Absolute Loading Mode) 程序中所使用的絕對地址，既可在編譯或匯編時給出，也可由程序員直接賦予。但在由程序員直接給出絕對地址時，不僅要求程序員熟悉內(nèi)存的使用情況，而且一旦程序或數(shù)據(jù)被修改后，可能要改變程序中的所有地址。因此，通常是寧可在程序中采用符號地址，然后在編譯或匯編時，再將這些符號地址轉(zhuǎn)換為絕對地址。46圖 4-2 作業(yè)裝入內(nèi)存時的情況 4.2.1 程序的裝入2. 可重定位裝入方式(Relocation Loading Mode)474.2.1 程序的裝入3. 動態(tài)運行時裝入方式(Denamle Run-time Loading)動態(tài)運行時的裝入程序，在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進