【正文】 哪個(gè)進(jìn)程（如果有）是死鎖的或可能變成死鎖的？解： a. 0 0 0 00 7 5 06 6 2 22 0 0 20 3 2 0 ，因?yàn)橹辽儆幸粋€(gè)進(jìn)程執(zhí)行序列，不會導(dǎo)致死鎖，運(yùn)行順序是p1, p4, p5, p2, p3. ，因?yàn)镻1進(jìn)程當(dāng)前分配與最大需求正好相等，P1進(jìn)程可以運(yùn)行直至結(jié)束，接下來運(yùn)行其他進(jìn)程 ,P3,P4,P5可能死鎖 ，當(dāng)進(jìn)程P1,P4,P5執(zhí)行完可用資源為（4，6，9，8），P2,P3將死鎖，所以不安全，完全不可以立即同意系統(tǒng)剩下的全部請求。 ，并給出結(jié)果。Available=(2 1 0 0) 2 0 0 1 0 0 1 0Request= 1 0 1 0 Allocation= 2 0 0 12 1 0 0 0 1 2 0解： 1. W = (2 1 0 0)2. Mark P3。 W = (2 1 0 0) + (0 1 2 0) = (2 2 2 0)3. Mark P2。 W = (2 2 2 0) + (2 0 0 1) = (4 2 2 1)4. Mark P1。 no deadlock detected 沒有死鎖，用戶進(jìn)程進(jìn)程Ｐ和一個(gè)輸出進(jìn)程Ｏ，它們之間用兩個(gè)緩沖區(qū)連接。進(jìn)程以相等大小的塊為單位交換數(shù)據(jù)，這些塊利用輸入緩沖區(qū)和輸出緩沖區(qū)之間的移動邊界緩存在磁盤上，并取決于進(jìn)程的速度。所使用的通信原語確保滿足下面的資源約束：i+o ≤max其中，max表示磁盤中的最大塊數(shù)，i表示磁盤中的輸入塊數(shù)目， o表示磁盤中的輸出塊數(shù)目。I輸入緩沖區(qū)P輸出緩沖區(qū)o以下是關(guān)于進(jìn)程的知識：１. 只要環(huán)境提供數(shù)據(jù)，進(jìn)程Ｉ最終把它輸入到磁盤上（只要磁盤空間可用）。２. 只要磁盤可以得到輸入，進(jìn)程Ｐ最終消耗掉它，并在磁盤上為每個(gè)輸入塊輸出有限量的數(shù)據(jù)（只要磁盤空間可用）。３. 只要磁盤可以得到輸出，進(jìn)程Ｏ最終消耗掉它。說明這個(gè)系統(tǒng)可能死鎖。解：當(dāng)I的速度遠(yuǎn)大于P的速度，有可能使磁盤上都是輸入數(shù)據(jù)而此時(shí)P進(jìn)程要處理輸入數(shù)據(jù)，即要將處理數(shù)據(jù)放入輸出數(shù)據(jù)區(qū)。于是P進(jìn)程等待磁盤空間輸出，I進(jìn)程等待磁盤空間輸入，二者死鎖。，仍然通話輸入和輸出緩沖區(qū)之間的邊界可以根據(jù)進(jìn)程的要求變化。解：為輸出緩沖區(qū)保留一個(gè)最小數(shù)目(稱為reso)塊, 但是當(dāng)磁盤空間足夠大時(shí)允許輸出塊的數(shù)目超過這一個(gè)界限。 資源限制現(xiàn)在變成Ｉ + Ｏ ≤maxＩ≤ max – reso當(dāng)0 reso max如果程序 P 正在等候遞送輸出給磁盤, 程序 O 最后處理所有的早先輸出而且產(chǎn)生至少reso頁, 然后讓 P 繼續(xù)執(zhí)行。 因此 P 不會因?yàn)?O 而延遲。如果磁盤充滿I/O，Ｉ能被延遲。 但是遲早, 所有的早先的輸入可以被Ｐ處理完，而且對應(yīng)的輸出將會被 O 處理,因而可以讓Ｉ繼續(xù)執(zhí)行。，一個(gè)磁鼓（磁盤的先驅(qū)，用做輔存）被劃分為輸入緩沖區(qū)，處理和輸出緩沖區(qū)，它們的邊界可以移動，這取決于所涉及的進(jìn)程速度。磁鼓的當(dāng)前狀態(tài)可以用以下參數(shù)描述： max表示磁鼓中的最大頁數(shù)，i示磁鼓中的輸入頁數(shù)，p示磁鼓中的處理頁數(shù)，o示磁鼓中的輸出頁數(shù)，reso出保留的最小頁數(shù)，resp理保留的最小頁數(shù)。解：Ｉ + Ｏ + Ｐ≤ max –Ｉ + Ｏ≤ max – respＩ + Ｐ ≤ max – resoＩ ≤ max – (reso + resp)６．９在ＴＨＥ多道程序設(shè)計(jì)系統(tǒng)中，一頁可以進(jìn)行下列狀態(tài)轉(zhuǎn)換：→輸入緩沖區(qū)（輸入生產(chǎn)）→處理區(qū)域（輸入消耗）→輸出緩沖區(qū)（輸出生產(chǎn)）→空（輸出生產(chǎn)）→處理區(qū)域（輸出消耗）→空（過程調(diào)用）a根據(jù)Ｉ，Ｏ和Ｐ的量定義這些轉(zhuǎn)換的結(jié)果。，用戶進(jìn)程和輸出進(jìn)程的假設(shè)，它們中的任何一個(gè)轉(zhuǎn)換是否會導(dǎo)致死鎖。解： 1. i ← i + 12. i← i – 1。 p ← p + 13. p← p – 1。 o← o + 14. o ← o – 15. p← p + 16. p ← p – 1b. 結(jié)合在對問題 的解決辦法被列出的資源限制, 我們能總結(jié)下列各項(xiàng):6. 過程返回能立刻發(fā)生因?yàn)樗麄冎会尫刨Y源。5. 程序調(diào)用可能用盡磁盤片 (p= max – reso) 導(dǎo)致死鎖。4. 當(dāng)有輸出時(shí)輸出消耗能立刻發(fā)生。3. 輸出生產(chǎn)能暫時(shí)被延遲直到所有的早先輸出被消耗而且為下一步的輸出至少可以產(chǎn)生reso頁。2. 只要有輸入，輸入消耗能立刻發(fā)生。1. 輸入生產(chǎn)被延遲直到所有先前輸入和對應(yīng)的輸出已經(jīng)被消耗。 此時(shí), 當(dāng) i= o=0,如果消費(fèi)進(jìn)程還沒有占用完磁盤空間 ( p max – reso)，可以產(chǎn)生輸入。結(jié)論: 分配給消費(fèi)進(jìn)程的不受控制的存儲空間是唯一可能引發(fā)死鎖的因素。，其單元如下分配三個(gè)進(jìn)程：進(jìn)程 最大 占用 1 70 45 2 60 40 3 60 15使用銀行家算法，以確定同意下面的任何一個(gè)請求是否安全。如果安全，說明能保證的終止序列；如果不安全，給出結(jié)果分配簡表。a．第４個(gè)進(jìn)程到達(dá)，最多需要６０個(gè)存儲單元，最初需要２５個(gè)單元。b第４個(gè)進(jìn)程到達(dá)，最多需要６０個(gè)存儲單元，最初需要３５個(gè)單元。解： ，則儲存器單元共用去25＋15＋40＋45=125個(gè)單元，還有25個(gè)存儲單元，則可以安全執(zhí)行全部進(jìn)程。安全順序是1－2－3－4，則還有15個(gè)資源可以用，此時(shí)處于不安全狀態(tài)，結(jié)果分配見表 進(jìn)程 最大 占有 需要 空閑 1 70 45 25 152 60 40 203 60 15 454 60 35 25。解：不切實(shí)際的: 不能總是預(yù)先知道最大要求, 進(jìn)程數(shù)目和資源數(shù)目可能隨著時(shí)間改變 。大多數(shù)的操作系統(tǒng)忽視死鎖。，使得進(jìn)程Ｐ０產(chǎn)生的Ｔ類型的數(shù)據(jù)元素經(jīng)進(jìn)程序列Ｐ1Ｐ2…Ｐn1,并且按該順序在元素上操作。，包含所有部分消耗的數(shù)據(jù)元素，并按下面的格式為進(jìn)程Ｐi(0≤i≤n1)寫一個(gè)算法。Repeat從前驅(qū)接收消耗給后續(xù)發(fā)送Forever假設(shè)Ｐ0收到Ｐn1發(fā)送的空元素。該算法能夠使進(jìn)程直接在緩沖區(qū)中保存的消息上操作，而無需復(fù)制。解：ar buffer: array 0..max1 of shared T。available: shared array 0..n1 of 0..max。 Initializationvar K: 1..n1。region available dobeginavailable(0) := max。for every k do available (k) := 0。end Process ivar j: 0..max1。 succ: 0..n1。beginj := 0。 succ := (i+1) mod n。repeatregion available doawait available (i) 0。region buffer(j) do consume element。region available dobeginavailable (i) := available(i) – 1。available (succ) := available (succ) + 1。endj := (j+1) mod max。foreverendP0 waits for Pn1 ANDP1 waits for P0 AND. . . . .Pn1 waits for Pn2 因?yàn)?available (0) = 0) AND(available (1) = 0) AND. . . . .(available (n1) = 0) 但是如果max 0,這個(gè)條件不成立，因?yàn)榕R界域滿足 claim(1)+ claim(2)+ …+claim(n) available(1)+available(2)+…+available(n)=max　，一次只能保留或釋放一個(gè)單元。每個(gè)進(jìn)程最大需要２個(gè)單元。說明不會死鎖。，一次只能保留或釋放一個(gè)單元。每個(gè)進(jìn)程最大需要單元數(shù)不超過Ｍ，并且所有最大需求的總和小于Ｍ+Ｎ。說明不會發(fā)生死鎖。解：，最壞情況下，每個(gè)進(jìn)程需要獲得一個(gè)，系統(tǒng)還剩1個(gè)，這一個(gè)資源，無論分給誰都能完成。完成進(jìn)程釋放資源后，使剩余進(jìn)程也完成，故系統(tǒng)不會死鎖。，最壞情況下，每個(gè)進(jìn)程都得到X1個(gè)資源都在申請最后一個(gè)資源，這時(shí)系統(tǒng)剩余資源數(shù)量為MN(X－1)，只要系統(tǒng)還有一個(gè)剩余資源，就可以使其中的一個(gè)進(jìn)程獲得所需要的全部資源，該進(jìn)程運(yùn)行結(jié)束以后釋放資源，就可以使其他進(jìn)程得到全部資源的 滿足，因此，當(dāng)MN(X1)》1時(shí)系統(tǒng)不會發(fā)生死鎖，解這個(gè)不等式X《（M+N1）,系統(tǒng)不會發(fā)生死鎖，因此，當(dāng)所有進(jìn)程的需求總和小于M+N時(shí)，系統(tǒng)是不會發(fā)生死鎖的。，當(dāng)前的聲明和分配矩陣是 3 1 2 1 C = 9 A= 3 7 2對于安全狀態(tài)，需要的最小資源數(shù)目是多少？解：最小資源數(shù)是３個(gè)，總共有１０個(gè)資源。Ｐ２獲得一個(gè)資源，完成后釋放兩個(gè)資源，Ｐ１獲得三個(gè)資源，完成后釋放三個(gè)資源，接下來Ｐ４獲得五個(gè)資源，釋放完資源后，Ｐ３獲得所需的６個(gè)資源后完成。：1銀行家算法，2死鎖檢測并殺死線程，釋放所有資源，３事先保留所有資源，４如果線程需要等待，５資源排序，６重新執(zhí)行檢測死鎖并退回線程的動作。評價(jià)解釋死鎖的不同方法使用的一個(gè)標(biāo)準(zhǔn)是，哪種方法允許最大的并發(fā)。換言之，在沒有死鎖時(shí)，哪種方法允許最多數(shù)目的線程無需要等待繼續(xù)前進(jìn)？對下面列出的６種處理死鎖的方法，給出從１到６的一個(gè)排序（１表示最大程序的并發(fā)），并解釋你的排序。另一個(gè)標(biāo)準(zhǔn)是效率；哪種方法需要最小的處理器開銷？假設(shè)死鎖很少發(fā)生，給出各種方法從１到６的一個(gè)排序（１表示最有效），并解釋這樣排序的原因。如果死鎖發(fā)生很頻繁，你的順序需要改變嗎？解：a從最多并發(fā)事件到最少, 有一個(gè)大概的次序如下：1. 死鎖檢測并殺死線程，釋放所有資源發(fā)現(xiàn)死鎖并退回線程的動作，如果線程需要等候那么重新開始線程而且釋放所有的資源，在死鎖發(fā)生之前，這些運(yùn)算法則都不會限制并發(fā), 因?yàn)樗麄冄鲑囘\(yùn)行時(shí)間檢查而并非靜態(tài)的限制。 他們的效果在死鎖被發(fā)現(xiàn)比較難以描述：他們?nèi)匀辉试S許多并發(fā)(在一些情形，他們增加它), 但是很難有準(zhǔn)確的估計(jì)。 第三個(gè)運(yùn)算法則是最奇怪的, 因?yàn)槿绱撕笤S多的它的并發(fā)將會是無用的重復(fù)。 因?yàn)榫€程競爭執(zhí)行時(shí)間, 這一個(gè)運(yùn)算法則也影響運(yùn)行速度。 因此在兩者的極端,它以這順序被列出兩次。2. 銀行家的運(yùn)算法則資源排序這些運(yùn)算法則因?yàn)橄拗贫喾N的可允許的計(jì)算，而相對早先兩種法則會引起更多的不必要的等候。 銀行家的運(yùn)算法則避免不安全的配置 和資源排序限制配置序列以便線程在他們是否一定等候的時(shí)候有較少的選擇。3. 事先保留所有的資源這一個(gè)運(yùn)算法則相比前兩個(gè)要允許更少的并發(fā), 但是比最壞的那一種有更少的缺點(diǎn)。因?yàn)橐A(yù)先保留所有的資源,線程必須等候比較長的而且當(dāng)他們工作的時(shí)候更有可能阻塞其他的線程,因此系統(tǒng)上來說具有更多的線性。4. 如果線程需要等待，則重新啟動線程并且釋放所有的資源如上所述, 這一個(gè)運(yùn)算法則在區(qū)別最多和最少并發(fā)上有疑問,這具體要看并發(fā)的定義。b從最高效率到最低，有如下大概的一個(gè)順序：1. 預(yù)先保留所有的資源資源排序因?yàn)樗麄儧]有包括運(yùn)行時(shí)間經(jīng)常開支，所以這些運(yùn)算法則最有效率。注意這是在相同的靜態(tài)限制下的結(jié)果。2. 銀行家的運(yùn)算法則發(fā)現(xiàn)死鎖而且殺死線程,釋放它的資源這些運(yùn)算法則在概略的配置上包括運(yùn)行時(shí)間檢查。 銀行家的運(yùn)算法則運(yùn)行搜尋查證復(fù)雜度在線程和配置的數(shù)字和死鎖檢測中是 O(n m)，死鎖檢測的復(fù)雜度是 O(n)。資源從屬鏈被線程數(shù)目，資源數(shù)目和分配數(shù)目限制。3. 發(fā)現(xiàn)死鎖并退回線程的動作這一個(gè)運(yùn)算法則運(yùn)行也需要運(yùn)行上述的相同的時(shí)間檢查。在寫內(nèi)存上的復(fù)雜度為O(n) 。4. 如果線程需要等待，則重新啟動線程并釋放所有的資源這一個(gè)運(yùn)算法則是非常無效率，有如下兩個(gè)理由。 首先, 因?yàn)榫€程有重新開始的危險(xiǎn), 他們完成的可能性低。其次，他們與其他重新開始線程競爭有限的執(zhí)行時(shí)間, 因此整個(gè)系統(tǒng)運(yùn)行的速度很慢。一位饑餓的哲學(xué)家首先拿起他左邊的叉子，如果他右邊的叉子也是可用的，則拿起右邊的叉子開始吃飯，否則他放下左邊的叉子，并重復(fù)這個(gè)循環(huán)。解：如果哲學(xué)家們步調(diào)完全一致地拿起左邊叉子又放下的話，他們會重復(fù)這一過程，導(dǎo)致饑餓情況的出現(xiàn)。一類總是先拿起左邊的叉子（左撇子），另一類總是先拿起右邊的叉子（右撇子）。右撇子的行為如下：begin repeat think。 wait(fork[(i+1)mod5])。 wait(fork[i])。 eat。signal(fork[i])。sig