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