【正文】 忙式等待條件下發(fā)生的饑餓，稱為活鎖。例如不公平的互斥算法。4． 死鎖與餓死之間有何相同點和不同點? 答：餓死與死鎖有一定聯(lián)系：二者都是由于競爭資源而引起的，但又有明顯差別，主要表現(xiàn)在如下幾個方面：(1) 從進程狀態(tài)考慮，死鎖進程都處于等待狀態(tài)，忙式等待(處于運行或就緒狀態(tài))的進程并非處于等待狀態(tài)，但卻可能被餓死；(2) 死鎖進程等待永遠不會被釋放的資源，餓死進程等待會被釋放但卻不會分配給自己的資源，表現(xiàn)為等待時限沒有上界(排隊等待或忙式等待)；(3) 死鎖一定發(fā)生了循環(huán)等待，而餓死則不然。這也表明通過資源分配圖可以檢測死鎖存在與否，但卻不能檢測是否有進程餓死；(4) 死鎖一定涉及多個進程，而饑餓或被餓死的進程可能只有一個。饑餓和餓死與資源分配策略(policy)有關，因而防止饑餓與餓死可從公平性考慮，確保所有進程不被忽視，如FCFS分配算法。5． 何謂銀行家算法的保守性? 舉例說明之。 答：銀行家算法的保守性是指銀行家算法只給出了進程需要資源的最大量，而所需資源的具體申請和釋放順序仍是未知的，因而銀行家只能往最壞處設想．考慮資源集合R={A(1),B(1)}，進程集合P={p1,p2}，已知進程p1和進程p2的活動序列分別為：p1：a,b,。 p2：b,b,a,。顯然p1和p2的資源最大需求量均為A(1)，B(1)。假定某時刻系統(tǒng)狀態(tài)如下：Claim AllocationNeed AvailableABABABABp1:11100101p2:110011即此時p1的a被系統(tǒng)接受。 其后系統(tǒng)接收到的命令有兩種可能，一是p1的請求b，二是p2的請求b。 假定為p2的請求b，因Request[2]=(0,1)￡Need[2]=(1,1)，故該請求是合法的。又Request[2]=(0,1)￡Available=(0,1)，故該請求系統(tǒng)當前能夠滿足。假定分配，系統(tǒng)狀態(tài)變化如下：Claim AllocationNeed AvailableABABABABp1:11100100p2:110110運行安全性檢測算法發(fā)現(xiàn)此時系統(tǒng)處于不安全狀態(tài)，因而取消分配，p2等待。實際上如果真正實施分配系統(tǒng)并不會進入死鎖狀態(tài)，因為分配后按照p2(),p1(b),p1(),p1(),p2 (b),p2(a),p2(),p2()的次序兩個進程可以執(zhí)行完，這是一個p1和p2交叉執(zhí)行的次序，而不是一個順序執(zhí)行的次序，銀行家算法不能判斷。6． 能否給出避免死鎖的充要性算法? 為什么? 答：目前關于避免死鎖的算法，如銀行家算法是充分性算法，即確保系統(tǒng)時刻處于安全狀態(tài)，這是在系統(tǒng)已知每個進程所需資源最大量的條件下可以給出的最好結(jié)果。如果系統(tǒng)不僅知道每個進程所需資源的最大量，而且知道進程有關資源的活動序列，在這個更強的條件下，則可以給出避免死鎖的充要性算法（讀者可以證明），但其復雜度是很高(NP完全)的。而且由于程序中分支和循環(huán)的存在，事先給出進程有關資源的命令序列一般是不可能的。7． 設有一個Ｔ型路口，其中A、B、C、D處各可容納一輛車，車行方向如下圖所示，試找出死鎖并用有序分配法消除之。要求資源編號合理。 AB E：左轉(zhuǎn)W：直行DC/\|S:左轉(zhuǎn)解：(1)Ｅ方向兩臺車分別位于A和B；S方向一臺車位于C；W方向一臺車位于D。(2)S方向兩臺車分別位于B和C；E方向一臺車位于A；W方向一臺車位于D。設位置資源C、B、A、D的編號從低到高依次為4，管理四個位置的信號量分別為s1,s2,s3,s4，信號量的初值均為1。車輛活動如下：semaphore s1=1,s2=1,s3=1,s4=1。W：直行P(s1)。 //按序申請P(s4)。駛?cè)隓。駛?cè)隒。V(s4)。駛出C。V(s1)。E：左轉(zhuǎn)P(s2)。駛?cè)隑。P(s3)；駛?cè)階。V(S2)P(s4)；駛?cè)隓。V(s3)；駛出D。V(s4)。S：左轉(zhuǎn)P(s1)。駛?cè)隒。P(s2)；駛?cè)隑。V(S1)P(s3)；駛?cè)階。V(s2)；駛出A。V(s3)。8． 設系統(tǒng)中僅有一個資源類，其中共有M個資源實例，使用此類資源的進程個數(shù)共有N個，它們所需資源最大量總和為S，試證明發(fā)生死鎖的必要條件是S3M+N。 證明：假定發(fā)生死鎖，且參與死鎖的進程個數(shù)為n(2￡n￡N)，參與死鎖的n個進程已經(jīng)占有系統(tǒng)中全部M個資源實例，而還沒夠(因它們處于無限期等待狀態(tài))，每個進程至少還需要一個資源實例，因而參與死鎖進程所需要資源總量3M＋n。每個未參與死鎖進程至少需要一個資源實例(若不需要則不屬于N集合中，它們沒有參與死鎖是因為它們在得到并使用完資源后已經(jīng)將其釋放)，由于共有Nn個未參與死鎖的進程，它們所需資源總量3Nn。由此可知，全部進程所需要的資源總量S3(M+n)+(Nn)=M+N。9． 在銀行家算法中，若出現(xiàn)如下資源分配情況： Allocation NeedAvailableABCDABCDABCDP0:003200121623P1:10001750P2:13542356P3:03320652P4:00140656試問：(1)當前狀態(tài)是否安全？(2)如果進程P2提出安全請求Request[2]=(1,2,2,2),系統(tǒng)能否將資源分配給它？說明原因．解：（1）當前狀態(tài)是安全狀態(tài)。運行安全性檢查算法如下：1）Work = Available；Finish = false；2）尋找滿足如下條件的i:Finish[i]==false并且Need[i]≤Work[i]；如果不存在，則轉(zhuǎn)步驟4）；3）Work = Work + Allocation[i]；Finish[i] = true；轉(zhuǎn)步驟2）4）如果對于所有i，F(xiàn)inish[i] = true，則系統(tǒng)處于安全狀態(tài)，否則處于不安全狀態(tài)。令Work = Available=（1, 6, 2, 3）運行安全性檢測算法，F(xiàn)inish[0]=false并且Need[0]=(0 0 1 2)Work,則Work = Work + Allocation[0]=（1, 6, 2, 3）+（0, 0, 3, 2）=（1, 6, 5, 5）；Finish[0] = true；Finish[3]=false并且Need[3]=（0, 6, 5, 2）Work,則Work = Work + Allocation[3]=（1, 6, 5, 5）+（0, 3, 3, 2）=（1, 9, 8, 7）；Finish[3] = true；Finish[4]=false并且Need[4=（0, 6, 5, 6）Work,則Work = Work + Allocation[4]=（1, 9, 8, 7）+（0, 0, 1, 4 ）=（1, 9, 9, 11）；Finish[4] = true；Finish[1]=false并且Need[1]=（1, 7, 5, 0）Work,則Work = Work + Allocation[4]=（1, 9, 9, 1）+(1, 0, 0, 0 )=(2, 9, 9, 11)；Finish[1] = true；Finish[2]=false并且Need[2]=（2, 3, 5, 6）Work,則Work = Work + Allocation[4]=（2, 9, 9, 11）+（1, 3, 5, 4 ）=（3, 12, 14, 15）；Finish[2] = true；可以找到一個安全進程序列p0,p3，p4，p1,p2，它使Finish[i]=true，對于所有0≤i≤4，因而可以斷言系統(tǒng)當前處于安全狀態(tài)．（2）運行銀行家算法，由于Request[2]=（1, 2, 2, 2）￡Need[2]=（2, 3, 5, 6），因而請求合法。進一步，Request[2]=（1, 2, 2, 2）￡Available=（1, 6, 2, 3），故該請求是可以滿足的。假設將資源分配給p2，則系統(tǒng)狀態(tài)變?yōu)?Allocation NeedAvailableABCDABCDABCDP0:003200120401P1:10001750P2:25 761134P3:03320652P4:00140656運行安全性檢測算法，Work=Available=（0, 4, 0, 1），F(xiàn)inish[i]=false，此時所有Need[i]￡Work[i]均不成立，結(jié)果Finish[i]均為false，不存在安全進程序列，系統(tǒng)處于不安全狀態(tài)。系統(tǒng)將取消資源分配并恢復原來狀態(tài)，進程p2等待。10． 某系統(tǒng)采用死鎖檢測手段發(fā)現(xiàn)死鎖，設系統(tǒng)中資源類集合為{A，B，C}，資源類A中共有8個實例，資源類B中共有6個實例，資源類C中共有5個實例．又設系統(tǒng)中進程集合為{p1,p2,p3,p4,p5,p6}，某時刻系統(tǒng)狀態(tài)如下： Allocation RequestAvailable ABCAB CA B Cp1: 10 000 02 2 1p2: 3 2 10 0 0p3: 0 1220 2p4: 00000 0p5: 21003 1p6: 00100 011． 在上述狀態(tài)下系統(tǒng)依次接受如下請求：Request[1]=(1,0,0)；Request[2]=(2,1,0)；Request[4]=(0,0,2)。給出系統(tǒng)狀態(tài)變化情況，并說明沒有死鎖。在由(1)所確定的狀態(tài)下系統(tǒng)接收如下請求：Request[1]=(0,3,1)，說明此時已發(fā)生死鎖，并找出參與死鎖的進程。 解：（1）①如果系統(tǒng)只是接受請求，但是沒有分配資源給進程，那么系統(tǒng)狀態(tài)變?yōu)椋篈llocation RequestAvailable ABCAB CA B Cp1: 10 010 02 2 1p2: 3 2 12 1 0p3: 0 1220 2p4: 00000 2p5: 21003 1p6: 0 0100 0在該狀態(tài)下運行死鎖檢測算法，可以找到一個進程序列p4,p1,p2,p3,p5,p6，它使Finish[i]=true，對于所有1≤i≤6，因而可以斷言系統(tǒng)當前沒有進入死鎖狀態(tài)。②如果系統(tǒng)接受請求后，將一個A分配給進程p1，則系統(tǒng)狀態(tài)變?yōu)椋篈llocation RequestAvailable ABCAB CA B Cp1: 20 00 0 012 1p2: 3 2 12 1 0p3: 0 1220 2p4: 00000 2p5: 21003 1p6: 00100 0在該狀態(tài)下運行死鎖檢測算法，可以找到一個進程序列p4,p1,p2,p3,p5,p6，它使Finish[i]=true，對于所有1≤i≤6，因而可以斷言系統(tǒng)當前沒有進入死鎖狀態(tài)。（2）設在（1）的①狀態(tài)下系統(tǒng)接收如下請求：Request[1]=(0,3,1)，則系統(tǒng)狀態(tài)變?yōu)椋篈llocation RequestAvailable ABCAB CA B Cp1: 10 013 12 2 1p2: 3 2 12 1 0p3: 0 1220 2p4: 00000 2p5: 21003 1p6: 00100 0在該狀態(tài)下運行死鎖檢測算法，可以找到一個進程序列p4,p2,p3,p5,p6,p1，它使Finish[i]=true，對于所有1≤i≤6，因而可以斷言系統(tǒng)當前沒有進入死鎖狀態(tài)．設在（1）的②狀態(tài)下系統(tǒng)接收如下請求：Request[1]=(0,3,1)，則系統(tǒng)狀態(tài)變?yōu)椋篈llocation RequestAvailable ABCAB CA B Cp1: 20 003 11 2 1p2: 3 2 12 1 0p3: 0 1220 2p4: 00000 2p5: 21003 1p6: 00100 0在該狀態(tài)下運行死鎖檢測算法，找不到一個進程序列使Finish[i]=true，對于所有1≤i≤6，因為存在i∈{1，2，3，5}，使Finish[i]=false，因而可以斷言系統(tǒng)已經(jīng)進入死鎖狀態(tài)，進程p1,p2,p3,p5卷入死鎖．六、 存儲管理習題及解答:1．考慮下述存儲管理方式中，進程空間和邏輯空間的編址情況： （1）界地址存儲管理方式，進程空間的首地址；（2）頁式存儲管理，進程空間的首地址；（3）段式存儲管理，進程空間各段的首地址；（4）段頁式存儲管理，進程空間各段的起始地址。答：（1）界地址存儲管理方式，進程空間的首地址從0開始編址；（2）頁式存儲管理，進程空間的首地址從0開始編址；（3）段式存儲管理，進程空間各段的首地址從0開始編址；（4）段頁式存儲管理，進程空間各段的起始地址從0開始編址。2．對于如下存儲管理方式來說，進程地址空間各是幾維的？ （1）頁式；（2）段式；（3）段頁式答：（1）頁式存儲管理中，進程地址空間是一維的；（2）段式存儲管理中，進程地址空間是二維的；（3）段頁式存儲管理中，進程地址空間是二維的。3．在頁式存儲管理中，頁的劃分對用戶是否可見？在段式存儲管理中，段的劃分對用戶是否可見？在段頁式存儲管理中，段的劃分對用戶是否可見？段內(nèi)頁的劃分對用戶是否可見？ 　　答：(1)在頁式存儲管理中，分頁對于用戶是透明的，一個進程由若干個頁構成，所有頁的長度相同；(2)在段式存儲管理中，分段對于用戶是可見的，一個進程由若干個段構成，各個段的長度可以不同，一個段恰好對應一個程序單位；(3)在段頁式存儲管理中，段的劃分對用戶是可見的，段內(nèi)頁的劃分對用戶是透明的，一個段由若干個頁構成，所有頁的長度相同。4．為什么空閑頁面鏈適合管理內(nèi)存空間，而不適合管理外存空間？ 答：空閑頁面鏈是將所有的空閑頁面連成一個鏈，分配時可取鏈頭的頁面，去配時可將被釋放的頁面連入鏈頭。此種方法適用于內(nèi)存頁面的分配，但對于外存頁面的分配因分配和去配均需執(zhí)行一次I/O傳輸，速度較慢。特別是當要申請多個頁面時，需要進行多次I/O傳輸，分配效率太低。5．在某些虛擬頁式存儲管理系統(tǒng)