【正文】 (1) 對(duì)于一個(gè)非空閑記錄來說，其鍵值 key 的雜湊值 hash ( key )是否一定與該記錄地址 addr 相同？ (2) 當(dāng)一記錄的沖突記數(shù)為0時(shí)，該記錄是否一定空閑？ (3) 當(dāng)一記錄空閑時(shí)，該記錄的沖突記數(shù)是否一定為0? 答：（1）不一定，當(dāng)前面記錄發(fā)生沖。文件描述符與文件是多對(duì)一。 8．采用文件連接技術(shù)后，文件名與文件是否一對(duì)一？文件號(hào)與文件是否一對(duì)一？文件描述符與文件是否一對(duì)一？ 答：文件名與文件是多對(duì)一?！?7. 說明對(duì)于如下文件操作命令，文件管理系統(tǒng)如何進(jìn)行合法性檢查。增加了內(nèi)外存?zhèn)鬏數(shù)拇螖?shù)，也容易導(dǎo)致FCB內(nèi)容的不一致。如果將這些信息合并到系統(tǒng)打開文件表中，就會(huì)導(dǎo)致一個(gè)共享文件占用多個(gè)系統(tǒng)打開文件表表目，這些表目的大部分內(nèi)容是重復(fù)的。其次，文件被打開后其控制信息 ( FCB )被緩沖到內(nèi)存系統(tǒng)空間，文件描述符作為用戶打開文件表中的入口地址直接與內(nèi)存 FCB 建立起聯(lián)系，而文件名無法做到這一點(diǎn)。若在系統(tǒng)打開文件表中又存在該文件的FCB的另一副本，不但占用內(nèi)存空間，另外無法更好實(shí)現(xiàn)多個(gè)進(jìn)程共享同一文件。這樣做的好處是FCB在內(nèi)存中只有一個(gè)副本，當(dāng)任何一個(gè)進(jìn)程對(duì)文件的操作導(dǎo)致FCB內(nèi)容變化時(shí)，內(nèi)存中的FCB內(nèi)容及時(shí)得到更新，當(dāng)所有進(jìn)程都不再需要該文件時(shí)，即當(dāng)最后一個(gè)進(jìn)程關(guān)閉該文件時(shí)，才將FCB的內(nèi)容回寫到外存上。多個(gè)進(jìn)程共享同一文件，即各自的用戶打開文件表目對(duì)應(yīng)系統(tǒng)打開文件表中的同一入口處。如果將整個(gè)文件目錄放入內(nèi)存，又要占用很大內(nèi)存空間，不可取。 4．文件在使用之前為何需要打開？多個(gè)進(jìn)程共享同一文件時(shí)，其FCB為何在內(nèi)存中只能保持一個(gè)副本？答：由于文件目錄和文件一起存放在外存上，當(dāng)存取文件時(shí)，必須先到外存中讀取文件目錄信息，從中得獲得文件的存放地址，然后再去存取文件。次部?jī)H包括一個(gè)文件名字和一個(gè)標(biāo)識(shí)文件主部的文件號(hào)，主部則包括除文件名字之外的所有信息和一個(gè)標(biāo)識(shí)該主部與多少個(gè)次部相對(duì)應(yīng)的連接計(jì)數(shù)。將FCB分為兩部分之后，文件目錄中僅保存FCB的次部，一個(gè)外存塊中可容納較多的FCB，從而大大地提高了文件的檢索速度。文件目錄是存于外存的，需要以塊為單位將其讀入內(nèi)存。同一文件也可以被同一用戶多次打開，每次打開時(shí)返回的文件描述符一般也不同。文件描述符是文件打開時(shí)返回的整數(shù)(入口地址)，對(duì)應(yīng)用戶打開文件表(如UNIX中的u_ofile)中的一個(gè)入口。答：文件名是文件的外部名字，通常是一個(gè)符號(hào)名(字符串)，同一文件可以有多個(gè)文件名(如通過link)。 答：某些系統(tǒng)可執(zhí)行程序，如shell、vi的長(zhǎng)度通常是固定不變的；而用戶正在編輯的文本文件或源代碼文件的長(zhǎng)度通常是動(dòng)態(tài)變化的。這里，段內(nèi)地址由兩部分構(gòu)成，即邏輯頁(yè)號(hào)和頁(yè)內(nèi)地址。(2) 其它進(jìn)程連接過但本進(jìn)程未連接過(共享段表有，段名段號(hào)對(duì)照表無): 為該段分配段號(hào)；填寫段名段號(hào)對(duì)照表，填寫段表(指向共享段表)，共享段表中共享記數(shù)加1；根據(jù)段號(hào)及段內(nèi)地址形成無障礙指示位的一般間接地址?！半s段”不共享，“純段”可共享。代碼段共享的必要條件是該段在運(yùn)行過程中不修改自身，即要求是“純代碼”(pure code)，而動(dòng)態(tài)連接需要修改連接字，這與共享的要求相矛盾。14．何謂請(qǐng)調(diào)？何謂預(yù)調(diào)？為何在預(yù)調(diào)系統(tǒng)中必須輔以請(qǐng)調(diào)？ 答：P157。13. 具有兩級(jí)頁(yè)表的頁(yè)式存儲(chǔ)管理與段頁(yè)式存儲(chǔ)管理有何差別？答：具有兩級(jí)頁(yè)表的頁(yè)式存儲(chǔ)管理的地址空間依然是一維的，頁(yè)的劃分對(duì)于進(jìn)程來說是透明的。共享段表用來實(shí)現(xiàn)段的共享和保護(hù)，該表中記錄所有共享段。因?yàn)閮?nèi)存分配的單位是頁(yè)，一個(gè)段內(nèi)邏輯上連續(xù)的頁(yè)面，可以分配到不連續(xù)的內(nèi)存頁(yè)面中，不要求一個(gè)段的所有邏輯頁(yè)都進(jìn)入內(nèi)存。 11. 在段式存儲(chǔ)管理中，段的長(zhǎng)度可否大于內(nèi)存的長(zhǎng)度？在段頁(yè)式存儲(chǔ)管理中呢？答：在段式存儲(chǔ)管理中，段的長(zhǎng)度不能大于內(nèi)存的長(zhǎng)度，因?yàn)橐粋€(gè)獨(dú)立的段占用一段連續(xù)的內(nèi)存空間，內(nèi)存分配是以段為單位進(jìn)行的，如果一個(gè)段的長(zhǎng)度大于內(nèi)存的長(zhǎng)度，那么該段將無法調(diào)入內(nèi)存。在?？梢詣?dòng)態(tài)增長(zhǎng)的情況下，系統(tǒng)開始可以為進(jìn)程分配一個(gè)基本長(zhǎng)度的?？臻g，這個(gè)長(zhǎng)度浪費(fèi)很小。 10． 舉例說明段長(zhǎng)動(dòng)態(tài)增長(zhǎng)的實(shí)際意義．答：允許段長(zhǎng)動(dòng)態(tài)增長(zhǎng)對(duì)于那些需要不斷增加或改變新數(shù)據(jù)或子程序的段來說很有好處。9. 比較段式存儲(chǔ)管理與頁(yè)式存儲(chǔ)管理的優(yōu)點(diǎn)和缺點(diǎn)．答：頁(yè)式存儲(chǔ)管理優(yōu)缺點(diǎn)： (1) 靜態(tài)等長(zhǎng)存儲(chǔ)分配簡(jiǎn)單，有效地解決了內(nèi)存碎片問題； (2) 共享和保護(hù)不夠方便。多級(jí)頁(yè)表會(huì)降低地址映射的速度，但通過快表可以將效率保持在合理的范疇內(nèi)。讀入后立即淘汰一個(gè)內(nèi)存頁(yè)面，此時(shí)可能也需執(zhí)行一次I/O傳輸，但對(duì)缺頁(yè)進(jìn)程來說不需等待，因而提高了響應(yīng)速度。5. 在某些虛擬頁(yè)式存儲(chǔ)管理系統(tǒng)中，內(nèi)存永遠(yuǎn)保持一個(gè)空閑頁(yè)面，這樣做有什么好處？ 答：在內(nèi)存沒有空閑頁(yè)架的情況下，需要按照置換算法淘汰一個(gè)內(nèi)存頁(yè)架，然后讀入所缺頁(yè)面，缺頁(yè)進(jìn)程一般需要等待兩次I/O傳輸時(shí)間。此種方法適用于內(nèi)存頁(yè)面的分配，但對(duì)于外存頁(yè)面的分配因分配和去配均需執(zhí)行一次I/O傳輸，速度較慢。(3)在段頁(yè)式存儲(chǔ)管理中，段的劃分對(duì)用戶是可見的，段內(nèi)頁(yè)的劃分對(duì)用戶是透明的，一個(gè)段由若干個(gè)頁(yè)構(gòu)成，所有頁(yè)的長(zhǎng)度相同。綜上所述，當(dāng)PPP3并發(fā)執(zhí)行時(shí)，沒有發(fā)生死鎖的可能性。 在本題中，進(jìn)程p1和p2都使用的資源集合是{a,b}，由于進(jìn)程p2在申請(qǐng)a之前已經(jīng)釋放了b，不存在占有b并且申請(qǐng)a的情況，所以進(jìn)程p1和p2之間不滿足死鎖的四個(gè)必要條件，不會(huì)產(chǎn)生死鎖；進(jìn)程p1和p3都使用的資源集合是{e,f,g}，進(jìn)程p1和p3都是先申請(qǐng)資源e，這兩個(gè)進(jìn)程同時(shí)申請(qǐng)資源，那么只能有一個(gè)進(jìn)程先獲得e，另一個(gè)進(jìn)程將因?yàn)榈貌坏絜而阻塞，獲得e的進(jìn)程將進(jìn)一步順利獲得資源f和g，從而運(yùn)行結(jié)束，釋放資源e,f和g，喚醒另一個(gè)進(jìn)程運(yùn)行。 又設(shè)系統(tǒng)中有PPP3三個(gè)進(jìn)程，其活動(dòng)分別為: P1活動(dòng): a b a b e f g e f g P2活動(dòng): b c b c d a d aP3活動(dòng): c d cd e g f e f g試分析當(dāng)PPP3并發(fā)執(zhí)行時(shí)，是否有發(fā)生死鎖的可能性，并說明原因。 其申請(qǐng)命令分別為a、b、c、d、e、f、g。10．某系統(tǒng)采用死鎖檢測(cè)手段發(fā)現(xiàn)死鎖，設(shè)系統(tǒng)中資源類集合為{A，B，C}，資源類A中共有8個(gè)實(shí)例，資源類B中共有6個(gè)實(shí)例，資源類C中共有5個(gè)實(shí)例．又設(shè)系統(tǒng)中進(jìn)程集合為{p1,p2,p3,p4,p5,p6}, 某時(shí)刻系統(tǒng)狀態(tài)如下： Allocation Request Available A B C A B C A B C p1: 1 0 0 0 0 0 2 2 1 p2: 3 2 1 0 0 0 p3: 0 1 2 2 0 2 p4: 0 0 0 0 0 0 p5: 2 1 0 0 3 1 p6: 0 0 1 0 0 0(1) 在上述狀態(tài)下系統(tǒng)依次接受如下請(qǐng)求：Request[1]=(1,0,0)；Request[2]=(2,1,0)； Request[4]=(0,0,2)．給出系統(tǒng)狀態(tài)變化情況，并說明沒有死鎖．答：如果系統(tǒng)只是接受請(qǐng)求，但是沒有分配資源給進(jìn)程，那么系統(tǒng)狀態(tài)變?yōu)椋篈llocation Request Available A B C A B C A B Cp1: 1 0 0 1 0 0 2 2 1p2: 3 2 1 2 1 0p3: 0 1 2 2 0 2p4: 0 0 0 0 0 2p5: 2 1 0 0 3 1p6: 0 0 1 0 0 0在該狀態(tài)下運(yùn)行死鎖檢測(cè)算法，可以找到一個(gè)進(jìn)程序列p4,p1,p2,p3,p5,p6，它使Finish=true，對(duì)于所有1≤i≤6，因而可以斷言系統(tǒng)當(dāng)前沒有進(jìn)入死鎖狀態(tài)。假設(shè)將資源分配給p2，則系統(tǒng)狀態(tài)變?yōu)? Allocation Need Available A B C D A B C D A B C D P0: 0 0 3 2 0 0 1 2 0 4 0 1 P1: 1 0 0 0 1 7 5 0 P2: 2 5 7 6 1 1 3 4 P3: 0 3 3 2 0 6 5 2 P4: 0 0 1 4 0 6 5 6運(yùn)行安全性檢測(cè)算法，Work=Available=（0, 4, 0, 1），F(xiàn)inish=false，此時(shí)所有Need￡Work均不成立，結(jié)果Finish[i[均為false，不存在安全進(jìn)程序列，系統(tǒng)處于不安全狀態(tài)。 　令Work = Available=（1, 6, 2, 3）運(yùn)行安全性檢測(cè)算法，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, 11）+(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； 可以找到一個(gè)安全進(jìn)程序列p0 ，p3 ，p4 ，p1 ,p2，它使Finish=true，對(duì)于所有0≤i≤4，因而可以斷言系統(tǒng)當(dāng)前處于安全狀態(tài)．（2）運(yùn)行銀行家算法，由于Request[2]=（1, 2, 2, 2）￡Need[2]=（2, 3, 5, 6），因而請(qǐng)求合法。9. 在銀行家算法中，若出現(xiàn)如下資源分配情況： Allocation Need Available A B C D A B C D A B C D P0: 0 0 3 2 0 0 1 2 1 6 2 3 P1: 1 0 0 0 1 7 5 0 P2: 1 3 5 4 2 3 5 6 P3: 0 3 3 2 0 6 5 2 P4: 0 0 1 4 0 6 5 6試問：(1)當(dāng)前狀態(tài)是否安全？ (2)如果進(jìn)程P2提出安全請(qǐng)求Request[2]=(1,2,2,2),系統(tǒng)能否將資源分配給它？說明原因．解：（1）當(dāng)前狀態(tài)是安全狀態(tài)。Need(1)+Need(2)+…Need(N) 3N。 V(s3)。 V(S1) P(s3) ； 駛?cè)?A。 駛?cè)?C。 V(s4)。 V(S2) P(s4) ； 駛?cè)?D。 駛?cè)?B。 V(s1)。 V(s4)。 駛?cè)?D。 W ：直行 P(s1)。 設(shè)位置資源C、B、A、D的編號(hào)從低到高依次為4，管理四個(gè)位置的信號(hào)量分別為s1,s2,s3,s4，信號(hào)量的初值均為1。7. 設(shè)有一個(gè)Ｔ型路口, 其中A、B、C、D處各可容納一輛車，車行方向如下圖所示，試找出死鎖并用有序分配法消除之. ：(1)E方向兩臺(tái)車分別位于A和B；S方向一臺(tái)車位于C；W方向一臺(tái)車位于D。如果系統(tǒng)不僅知道每個(gè)進(jìn)程所需資源的最大量，而且知道進(jìn)程有關(guān)資源的活動(dòng)序列，在這個(gè)更強(qiáng)的條件下，則可以給出避免死鎖的充要性算法（讀者可以證明），但其復(fù)雜度是很高(NP完全)的。5. 何謂銀行家算法的保守性? ：銀行家算法的保守性是指銀行家算法只給出了進(jìn)程需要資源的最大量，而所需資源的具體申請(qǐng)和釋放順序仍是未知的，因而銀行家只能往最壞處設(shè)想．例如：書中舉例p119頁(yè)。這也表明通過資源分配圖可以檢測(cè)死鎖存在與否，但卻不能檢測(cè)是否有進(jìn)程餓死；(4) 死鎖一定涉及多個(gè)進(jìn)程，而饑餓或被餓死的進(jìn)程可能只有一個(gè)。在忙式等待條件下發(fā)生的饑餓，稱為活鎖．考慮一臺(tái)打印機(jī)分配的例子，當(dāng)有多個(gè)進(jìn)程需要打印文件時(shí)，系統(tǒng)按照短文件優(yōu)先的策略排序，該策略具有平均等待時(shí)間短的優(yōu)點(diǎn)，似乎非常合理，但當(dāng)短文件打印任務(wù)源源不斷時(shí)，長(zhǎng)文件的打印任務(wù)將被無限期地推遲，導(dǎo)致饑餓以至餓死。 資源分配策略可能是公平的(fair)，能保證請(qǐng)求者在有限的時(shí)間內(nèi)獲得所需資源；資源分配策略也可能是不公平的(unfair)，即不能保證等待時(shí)間上界的存在。能看出，畫出的資源分配圖存在環(huán)路。 再證明必要條件：若死鎖產(chǎn)生，則存在一個(gè)循環(huán)等待進(jìn)程序列p1,p2,p3……pn,進(jìn)程p1正等待資源類rk1中唯一的一個(gè)實(shí)例，而rk1又被進(jìn)程p2所占用；進(jìn)程p2正等待資源類rk2中唯一的一個(gè)實(shí)例，而rk2又被進(jìn)程p3所占用；……。說明rk中有兩個(gè)以上的資源實(shí)例，與前提矛盾。 2. 試證明當(dāng)每個(gè)資源類中僅有一個(gè)資源實(shí)例時(shí)，資源分配圖中的環(huán)路是死鎖的充要條件。說法(4)正確，死鎖既可能