安全狀態(tài)的例子

1安全狀態(tài)的例子例：假定系統(tǒng)有三個進程P1、P2、P3，共有12臺磁帶機。進程P1總共要求10臺磁帶機，P2和P3分別要求4臺和九臺。設在T0時刻，進程P1、P2和P3已經獲得5臺、2臺和2臺，還有3臺空閑沒有分配。進程最大需求已分配可用P11053P2P34229T0時刻系統(tǒng)時安全的。這時存在一個安全序列<P2，P1，P3>2雖然并非所有不安全狀態(tài)都是死鎖狀態(tài)，但當系統(tǒng)進入不安全狀態(tài)后，便有可能進入死鎖狀態(tài)；反之只要系統(tǒng)處于安全狀態(tài)，系統(tǒng)便可避免進入死鎖狀態(tài)。因此，避免死鎖的實質是如何使系統(tǒng)不進入不安全狀態(tài)。系統(tǒng)的狀態(tài)可能通過下述來描述：進程剩余申請數(shù)＝最大申請數(shù)－占有數(shù)?？煞峙滟Y源數(shù)＝總數(shù)－占有數(shù)之和。

3銀行家算法銀行家算法是最有代表性的避免死鎖算法，是Dijkstra提出的銀行家算法。這是由于該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名。為實現(xiàn)銀行家算法，系統(tǒng)中必須設置若干數(shù)據(jù)結構。4一、銀行家算法中的數(shù)據(jù)結構1可利用資源向量Available

是一個含有m個元素，其中的每一個元素代表一類可利用的資源數(shù)目，其初值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。如果Available[j]=k，

表示系統(tǒng)中現(xiàn)有Rj類資源k個。2最大需求矩陣Max是一個含有n

m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Max(i,j)=k，

表示進程i需要Rj類資源的最大數(shù)目為k。Available=35428386153分配矩陣Allocation

是一個含有n

m的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。如果Allocation(i,j)=k，

表示進程i當前已分得Rj類資源k個。4需求矩陣Need

是一個含有n

m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Need(i,j)=k，

表示進程i還需要Rj類資源k個，方能完成其任務。

Need(i,j)=Max(i,j)-Allocation(i,j)

6二、銀行家算法設Requesti是進程Pi的請求向量，如果進程Pi需要K個Rj類資源，當Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進行檢查：1

如果Requesti≤Needi,則轉向步驟2；否則認為出錯。（因為它所需要的資源數(shù)已超過它所宣布的最大值。2如果Requesti≤Available,則轉向步驟3；否則，表示系統(tǒng)中尚無足夠的資源，Pi必須等待3

系統(tǒng)試探把要求的資源分配給進程Pi，并修改下面數(shù)據(jù)結構中的數(shù)值：Available:=Available-Requesti;Allocation:=Allocation+Requesti;Needi:=Needi-Requesti;4系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，正式將資源分配給進程Pi，以完成本次分配；否則，將試探分配作廢，恢復原來的資源分配狀態(tài)，讓進程Pi等待。

7三、安全性算法系統(tǒng)所執(zhí)行的安全性算法可描述如下：1設置兩個向量①工作向量Work.它表示系統(tǒng)可提供給進程繼續(xù)運行所需要的各類資源的數(shù)目，它含有m個元素，執(zhí)行安全算法開始時，Work:=Available。②Finish.它表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish[i]:=false；當有足夠的資源分配給進程時，令Finish[i]:=true.2從進程集合中找到一個能滿足下述條件的進程：①Finish[i]=false;②Needi≤Work.如找到，執(zhí)行步驟3；否則執(zhí)行步驟4。3當進程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故執(zhí)行：Work:=Work+Allocation;Finish[i]:=true;Gotostep2;4如果所有進程的Finish[i]=true，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。

要記住的一些變量的名稱1Available（可利用資源向量）某類可利用的資源數(shù)目，其初值是系統(tǒng)中所配置的該類全部可用資源數(shù)目。

2

Max最大需求矩陣某個進程對某類資源的最大需求數(shù)

3

Allocation分配矩陣某類資源當前非配給某進程的資源數(shù)。4

Need需求矩陣某個進程還需要的各類資源數(shù)。

Need=Max-Allocation系統(tǒng)把進程請求的資源分配給它以后要修改的變量Available:=Available-Request;Allocation:=Allocation+Request;Need:=Need-Request;9銀行家算法之例假定系統(tǒng)中有五個進程{P0、P1、P2、P3、P4}和三種類型的資源{A，B，C}，每一種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖資源情況進程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P4010322902222433200(302)302211002743122(020)00011431332(230)332122200資源情況進程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P4010322902222433200(302)302211002743122(020)600011431332(230)753資源情況進程NeedABCworkABCWork＋AllocationABCAllocationABCP1P3P4P2P0finish532truetruetruetruetrue011211532743743431002745745600302104710477430101057最大值已分配還需要可用若P1發(fā)出請求向量Request（1，0，2）工作向量Work.它表示系統(tǒng)可提供給進程繼續(xù)運行所需要的各類資源的數(shù)目10,5711思考和練習假定系統(tǒng)中有五個進程{P0、P1、P2、P3、P4}和三種類型的資源{A，B，C}，每一種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖請找出該表中T0時刻以后存在的安全序列（至少2種）資源情況進程AllocationABCMaxABCNeedABCAvailableABCP0P1P2P3P4010322902222433200302211002743122600011431332753123死鎖的檢測和恢復死鎖的檢測和恢復技術是指定期啟動一個軟件檢測系統(tǒng)的狀態(tài)，若發(fā)現(xiàn)有死鎖存在，則采取措施恢復之。

(1)死鎖的檢測檢查死鎖的辦法就是由軟件檢查系統(tǒng)中由進程和資源構成的有向圖是否構成一個或多個環(huán)路，若是，則存在死鎖，否則不存在。13死鎖的檢測：實質是確定是否存在環(huán)路等待現(xiàn)象，一旦發(fā)現(xiàn)這種環(huán)路便認定死鎖存在，并識別出該環(huán)路所涉及的有關進程，以供系統(tǒng)采取適當?shù)拇胧﹣斫獬梨i。最常用的是一種基于資源分配圖RAG和死鎖定理的檢測死鎖算法。14資源分配圖（RAG）系統(tǒng)死鎖可用資源分配圖來描述，該圖是由一組結點N和一組邊E所組成的一對偶G=(N,E)。（用圓圈代表一個進程，用方框代表一類資源，由于一種類型的資源可能有多個，可用方框中的一個點代表一類資源中的一個資源）幾個概念：請求邊，分配邊

P1P2r1r2請求r2資源分配圖15封鎖進程：是指某個進程由于請求了超過了系統(tǒng)中現(xiàn)有的未分配資源數(shù)目的資源，而被系統(tǒng)封鎖的進程。非封鎖進程：即沒有被系統(tǒng)封鎖的進程資源分配圖的化簡方法：假設某個RAG中存在一個進程Pi，此刻Pi是非封鎖進程，那么可以進行如下化簡：當Pi有請求邊時，首先將其請求邊變成分配邊(即滿足Pi的資源請求)，而一旦Pi的所有資源請求都得到滿足，Pi就能在有限的時間內運行結束，并釋放其所占用的全部資源，此時Pi只有分配邊，刪去這些分配邊（實際上相當于消去了Pi的所有請求邊和分配邊），使Pi成為孤立結點。（反復進行）

。16死鎖定理：系統(tǒng)中某個時刻S為死鎖狀態(tài)的充要條件是S時刻系統(tǒng)的資源分配圖是不可完全簡化的。在經過一系列的簡化后，若能消去圖中的所有邊，使所有的進程都成為孤立結點，則稱該圖是可完全簡化的；反之的是不可完全簡化的。P1P2r1r2P1P2r1r2P1P2r1r217死鎖的恢復。是與檢測死鎖相配套的一種措施，用于將進程從死鎖狀態(tài)下解脫出來。常用的方法有：1撤消進程；最簡單撤消進程的方法是使全部死鎖的進程夭折掉；另一方法是按照某種順序逐個地撤消進程，直至有足夠的資源可用，死鎖狀態(tài)消除為止2掛起進程（剝奪資源）。使用掛起/激活機構掛起一些進程，剝奪它們的資源以解除死鎖，待條件滿足時，再激活進程。目前掛起法比較受到重視。181．（北大95）一個OS有20個進程，競爭使用65個同類資源，申請方式是逐個進行的，一旦某個進程獲得它所需要的全部資源，則立即歸還所有資源。每個進程最多使用三個資源。若僅考慮這類資源，該系統(tǒng)有無可能產生死鎖，為什么？2．死鎖和饑餓的主要差別是什么？例題191答：不可能。因為死鎖產生的原因有兩點：系統(tǒng)資源不足或推進順序不當，在本題中，進程所需的最大資源數(shù)為60，而系統(tǒng)共有該類資源65個，其資源數(shù)已足夠系統(tǒng)內各進程使用。2答：簡言之，死鎖是某進程等待一個不會發(fā)生的事件的一種現(xiàn)象；而饑餓現(xiàn)象是某進程正等待這樣一個事件，它發(fā)生了但總是受到其它進程的影響，以至輪不到（或很難輪到）該進程。

201.在某系統(tǒng)中，三個進程共享四臺同類型的設備資源，這些資源一次只能一臺地為進程服務和釋放，每個進程最多需要二臺設備資源，試問在系統(tǒng)中是否會產生死鎖？2.某系統(tǒng)中有n個進程和m臺打印機，系統(tǒng)約定：打印機只能一臺一臺地申請、一臺一臺地釋放，每個進程需要同時使用的打印機臺數(shù)不超過m。如果n個進程同時使用打印機的總數(shù)小于m+n，試討論，該系統(tǒng)可能發(fā)生死鎖嗎?并簡述理由。3.僅涉及一個進程的死鎖有可能存在嗎?為什么?作業(yè)2122

小結進程的并發(fā)執(zhí)行，使得它們之間存在著兩種制約關系：由共享資源引起的間接制約關系稱為互斥；由于協(xié)作完成同一任務而引起的直接制約關系稱為同步。為了正確地解決進程之間的同步和互斥，系統(tǒng)設置同步機構：鎖和信號量機構。這種同步機構稱為低級通信。進程之間的高級通信機構有消息緩沖、信箱、管道、共享內存和共享文件等機構，其最大特點是通信雙方可交換大量的數(shù)據(jù)。23

系統(tǒng)中并發(fā)運行進程由于共享資源或相互通信，如果調度不當，可能導致系統(tǒng)死鎖。解決死鎖的方法有三種：(1)預防死鎖，它是通過破壞死鎖的四個必要條件實現(xiàn)的。

(2)避免死鎖，它是在進程請求分配資源時，采用銀行家算法等防止系統(tǒng)進入不安全狀態(tài)。

(3)檢測和恢復死鎖，它是通過設置一個死鎖檢測機構進行死鎖檢測，一旦檢測出來，通過逐一撤消進程使系統(tǒng)恢復。243.9線程(Thread)3.9.1線程的概念引入的線程目的：提高系統(tǒng)的執(zhí)行效率，減少處理機的空轉時間和調度切換（保護現(xiàn)場信息）的時間，便于系統(tǒng)管理。（減少程序并發(fā)執(zhí)行時所付出的時空開銷，使OS具有更好的并發(fā)性。）

25分析說明：進程的兩個基本屬性：1進程是一個可擁有資源的獨立單位；2進程又是一個可獨立調度和分配的基本單位。合起來，進程便成為一個能獨立運行的基本單位，從而構成了程序并發(fā)執(zhí)行的基礎。簡言之，由于進程是一個資源的擁有者