【文章內(nèi)容簡介】 信號量機制來描述下述前趨圖M1 解答：首先定義信號量S12,S13,S24,S25,S56,S46,S36的初值都為0，分別表示相對應(yīng)的進程是否完成(2’)：COBEGIN (`6’=1’*6)Process M1:begin V(S12) V(S13) endProcess M2:begin P(S12) V(24) V(25) endProcess M3:begin P(S13) V(S36) endProcess M4:begin P(S14) V(S46) endProcess M5:begin P(S25) V(S56) endProcess M6:begin P(S36)P(S46) P(S56) end COEND13設(shè)系統(tǒng)有三個并發(fā)進程R,C,P，共享一個能存放n個數(shù)據(jù)的環(huán)形緩沖區(qū)buf。進程R負責(zé)從輸入設(shè)備上讀數(shù)據(jù)，每讀一個后把它存放在緩沖區(qū)buf的一個單元中；進程C負責(zé)從緩沖區(qū)讀數(shù)據(jù)并進行處理，之后將處理結(jié)果再送入緩沖區(qū)的一個單元中；進程P負責(zé)從緩沖區(qū)讀進程C處理的結(jié)果并打印。請用P、V操作為三進程的正確執(zhí)行寫出同步算法。解答：解決同步問題需設(shè)一個互斥信號量mux，用于控制三個進程互斥使用緩沖區(qū)，初值為1；再設(shè)三個同步信號量，用于控制對緩沖區(qū)的空閑數(shù)量和不同數(shù)據(jù)個數(shù)的記錄。S0表示緩沖區(qū)空閑個數(shù)，初值為n；S1表示緩沖區(qū)中輸入數(shù)據(jù)的個數(shù)，初值為0；S2表示緩沖區(qū)中輸出數(shù)據(jù)的個數(shù)，初值為0。(4’)算法描述如下：(`6’=2’*3) 進程R 進程C 進程P L1: L2: L3:P(S0) P(S1) P(S2)P(mux) P(mux) P(mux)讀一個數(shù)據(jù) 從緩沖區(qū)中取一個 從緩沖區(qū)中讀 送緩沖區(qū) 數(shù)據(jù)處理后放回去 輸出數(shù)據(jù)V(mux) V(mux) V(mux)V(S1) V(S2) V(S0) 打印gotoL1: gotoL2: gotoL3:名詞解釋1死鎖是指在一個進程集合中的每個進程都在等待僅由該集合中的另一個進程才能引發(fā)的事件而無限期地僵持下去的局面。2饑餓在系統(tǒng)中，每個資源占有者都在有限時間內(nèi)釋放它所占有的資源，但資源中存在某些申請者由于某種原因卻永遠得不到資源的一種錯誤現(xiàn)象。3死鎖防止要求進程申請資源時遵循某種協(xié)議，從而打破產(chǎn)生死鎖的四個必要條件中的一個或幾個，保證系統(tǒng)不會進入死鎖狀態(tài)。4死鎖避免對進程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查，并根據(jù)檢查結(jié)果決定是否進行資源分配。就是說，在資源分配過程中若預(yù)測有發(fā)生死鎖的可能性，則加以避免。這種方法的關(guān)鍵是確定資源分配的安全性。5安全序列針對當(dāng)前分配狀態(tài)來說，系統(tǒng)至少能夠按照某種次序為每個進程分配資源（直至最大需求），并且使他們依次成功地運行完畢，這種進程序列{p1,p2,…,pn}就是安全序列。簡答題1計算機系統(tǒng)中產(chǎn)生死鎖的根本原因是什么?死鎖發(fā)生的四個基本條件是什么？答: 計算機系統(tǒng)中產(chǎn)生死鎖的根本原因是：資源有限且操作不當(dāng) 。死鎖發(fā)生的四個基本條件有互斥條件、請求保持條件（占有且等待條件）、非剝奪條件（不可搶占條件）和環(huán)路條件（循環(huán)等待條件） 。2簡述發(fā)生死鎖的四個必要條件?答： 四個必要條件是：互斥條件、占有且等待條件（請求保持條件）、不可搶占條件（非剝奪條件）和循環(huán)等待條件（環(huán)路條件）。 互斥條件——某個資源在一段時間內(nèi)只能由一個進程占有，不能同時被兩個及其以上的進程占有。 占有且等待條件——進程至少已經(jīng)占有一個資源，但又申請新的資源。 不可搶占條件——一個進程所占有的資源再用完之前，其他進程不能強行奪走資源，只能由該進程用完之后主動釋放。 循環(huán)等待條件——存在一個進程等待序列{P1,P2,…,Pn}，其中，P1等待P2所占有的某個資源，P2等待P3所占有的某個資源，……，而Pn等待P1所占有的某個資源，從而形成一個進程循環(huán)等待。 3什么是死鎖？解決死鎖的方法一般有那幾種?答: 死鎖是指在一個進程集合中的每個進程都在等待僅由該集合中的另一個進程才能引發(fā)的事件而無限期地僵持下去的局面。 解決死鎖問題的一般方法為：死鎖的預(yù)防、死鎖的避免、死鎖的檢測和恢復(fù)。 4死鎖預(yù)防的基本思想是什么?死鎖避免的基本思想是什么?答:死鎖預(yù)防的基本思想是:要求進程申請資源是遵循某種協(xié)議,從而打破產(chǎn)生思索的四個必要條件中的一個或幾個,保證系統(tǒng)不會進入死鎖狀態(tài). 死鎖避免的基本思想是:對進程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查,在資源分配過程中若預(yù)測有發(fā)生死鎖的可能性,. 5什么是死鎖的安全序列?何謂系統(tǒng)是安全的？答：進程的安全序列{P1,P2,…,PN}是這樣組成的：若對于每個進程Pi（1=I=n），它需要的附加資源可以被系統(tǒng)中當(dāng)前可用資源加上所有進程Pj（ji）當(dāng)前占有資源之和所滿足，則{ P1,P2,…,PN }為一個安全序列。 “系統(tǒng)是安全的”是指系統(tǒng)中的所有進程能夠按照某種次序分配資源，并且依次運行完畢。即系統(tǒng)中的進程處于安全序列中。 6資源按序分配法為什么能夠預(yù)防死鎖？證明：采用反證法來證明。 若存在循環(huán)等待，設(shè)在環(huán)路上的一組進程為{P0,P1,P2,…,Pn}，這里Pi等待進程Pi+1占有資源Ri（下角標(biāo)取模運算，從而，Pn等待p0占有的資源）。由于Pi+1占有資源Ri,又申請資源Ri+1,從而一定存在F(i)F(i+1), 該式對所有的i都成立。于是就有： F(R0)F(R1)…F(Rn)F(R0) 由傳遞性得到： F(R0)F(R0) 顯然，這是不可能的，因而，上述假設(shè)不成立，表明不會出現(xiàn)循環(huán)等待條件。7死鎖和“饑餓”之間的主要差別是什么?答：死鎖：多個并發(fā)進程相互等待對方占用的資源而產(chǎn)生的錯誤現(xiàn)象。 餓死：在系統(tǒng)中，由于系統(tǒng)采用的資源分配算法不當(dāng)，雖然每個資源占有者都在有限時間內(nèi)釋放它所占的資源，但仍然使一些進程永遠得不到資源的一種錯誤現(xiàn)象。 綜合題1設(shè)系統(tǒng)中有三種類型的資源（A,B,C）和五個進程（P1,P2,P3,P4,P5）,A資源的數(shù)量為17，B資源的數(shù)量為5，C資源的數(shù)量為20。在T0時刻系統(tǒng)狀態(tài)如表39所試。系統(tǒng)采用銀行家算法來避免死鎖。①T0時刻是否為安全狀態(tài)？若試，請給出安全序列。②在T0時刻，若進程P2請求資源（0，3，4），能否實現(xiàn)資源分配？為什么？③在②的基礎(chǔ)上，若進程P4請求資源（2，0，1），能否實現(xiàn)資源分配？為什么?④在③的基礎(chǔ)上，若進程P1請求資源（0，2，0），能否實現(xiàn)資源分配？為什么?表39 T0時刻系統(tǒng)狀態(tài)進程 最大資源需求量 已分配資源數(shù)量 系統(tǒng)剩余資源數(shù)量 A B C A B C A B CP1 5 5 9 2 1 2 2 3 3P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4 解：①T0時刻是安全狀態(tài)，因為存在一個安全序列{P4,P5,P1,P2,P3} (2’)②不能實現(xiàn)資源分配，因為所剩余的資源數(shù)量不夠。 (2’)③可以分配。當(dāng)分配完成后，系統(tǒng)剩余的資源向量為（0，3，2），這時，仍可找到一個安全序列{P4,P5,P1,P2,P3} (3’)④不能分配。如果分配的話，則系統(tǒng)剩余的資源向量為（0，1，2），這時無法找到一個安全序列。(3’)2在銀行家算法中，系統(tǒng)有5個進程和3個資源。若出現(xiàn)以下資源分配情況： 進程 資源最大請求 已分配資源 p0 7, 5, 3 0, 1, 0 p1 3, 2, 2 2, 1, 0 p2 9, 0, 2 3, 0, 2 p3 2, 2, 2 2, 1, 1 p4 4, 3, 3 0, 0, 2系統(tǒng)剩余資源數(shù)量為(3,2,2)。1） 該狀態(tài)是否安全(給出詳細的檢查過程)?2） 如果進程依次有如下資源請求p1:資源請求Request(1,0,2)?p4:資源請求Request(3,3,0)?p0:資源請求Request(0,1,0)?則系統(tǒng)如何進行資源分配，才能避免死鎖？解:1)該系統(tǒng)狀態(tài)是否安全,系統(tǒng)只要按照這個序列為進程分配資源,所有進程就都可順利完成。若找不到,可先求出進程的剩余請求矩陣. 進程 資源最大需求 已分配資源 剩余資源請求 P0 7, 5, 3 0, 1, 0 7, 4, 3 P1 3, 2, 2 2, 1, 0 1, 1, 2 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 系統(tǒng)剩余資源向量A=(3,2,2)，在進程剩余資源請求矩陣中找，是否有一行，選進程P1，滿足它的全部資源請求，它在有限時間內(nèi)能釋放全部資源，并標(biāo)記它為完成使系統(tǒng)剩余資源向量A=(5,3,2).之后再重復(fù)上述過程，從而找到了一個進城完成序列為：P1,P3,P4,P2,P0 (2’)。由此可見，系統(tǒng)狀態(tài)是安全的(2’)。2）p1:資源請求Request(1,0,2)時，由1）可知，可以立即滿足它，使得A=(2,2,0),P1的分配向量為(3,1,2)，其剩余向量變?yōu)?0,1,0). (2’)p4:資源請求Request(3,3,0)時，由于系統(tǒng)剩余資源向量A=(2,2,0)，顯然不能滿足它的請求，因為系統(tǒng)剩余資源向量A小于P4的請求 (2’)p0:資源請求Request(0,1,0)時，由于系統(tǒng)剩余資源向量A=(2,2,0)，若滿足它的請求，使得系統(tǒng)剩余資源向量A=(2,1,0)。之后，系統(tǒng)仍可以找到一個進程完成序列P1,P4,P0,P4,P2。故可以滿足它的請求。 (2’)3系統(tǒng)有同類資源10個，進程pp2和p3需要該類資源的最大數(shù)量分別為8，6，7。它們使用資源的次序和數(shù)量如下圖所示。1） 試給出采用銀行家算法分配資源時，進行第5次分配后各進程的狀態(tài)及各進程占用資源情況。2） 在以后的申請中，那次的申請可以得到最先滿足?給出一個進程完成序列。次序 進程 申請量 次序 進程 申請量1 P1 3 5 P2 22 P2 2 6 P1 33 P3 4 7 P3 34 P1 2 8 P2 2解：1）計算第5次分配后進程的狀態(tài)和占用資源情況：(`5’=1’*5)① p1申請3個，滿足，系統(tǒng)還剩7個②p2申請2個，滿足（因為系統(tǒng)的7個可以使p2運行完），系統(tǒng)還剩5個③p3申請4個，因為若滿足它的請求，可能使以后的任何進程都不能運行完，故p3等待④p1申請2個，滿足（系統(tǒng)還剩5個可以滿足p1的最大請求），系統(tǒng)還剩3個⑤ p2申請2個，不能滿足，等待。此時系統(tǒng)的分配情況如下：p1分配5個后正在運行，p2分配2個后等待分配2個，p3等待分配4個，系統(tǒng)還剩3個。2）p1接著運行，p1申請3個可滿足(2’)。P1運行完成后，釋放資源，使系統(tǒng)的資源數(shù)量變?yōu)?個。首先將p3喚醒，滿足它的4個資源，系統(tǒng)還剩4個，可以喚醒p2，滿足它的2個請求。系統(tǒng)還剩2個。P3申請3個，不能滿足，等待。P2申請2個，系統(tǒng)滿足它，p2接著運行；p2完成，釋放資源，使系統(tǒng)資源變?yōu)?個。系統(tǒng)喚醒p3，滿足它的資源請求，最終p3完成，釋放資源，使資源數(shù)量恢復(fù)為10個。找到的進程完成序列為p1,p2,p3。 (3’)4設(shè)系統(tǒng)中有150個可用的同類資源。在某時刻系統(tǒng)中的進程已獲得的資源和最大請求資源如下所示，請用銀行家算法分別判斷完成下列請求時，系統(tǒng)是否安全？若安全，請給出進程的完成序列。如不安全，請說明原因。 進程 最大需求量 當(dāng)前已分配量 p1 70 25 p2 60 40 p3 60 45 p4 60 0(1) 進程p4當(dāng)前請求25個資源；(2) 之后p4又提出35個資源的請求。解答：系統(tǒng)當(dāng)前剩余資源量為：150 – 25 – 40 – 45 = 40 (2’)(1) 可以滿足(2’)，假定先分配p4的25個資源，系統(tǒng)還剩15個。將這15個資源可先分配給p