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