高級操作系統(tǒng)題目及答案

1、在實(shí)現(xiàn)RPC時(shí)，調(diào)用者如何得知被調(diào)用者實(shí)際運(yùn)行在哪個(gè)站點(diǎn)上，是一個(gè)必須要解決的問 題。當(dāng)系統(tǒng)生成與調(diào)用者對應(yīng)的stub時(shí)，可把該遠(yuǎn)程站點(diǎn)的地址也一同并入其中，不過這種 做法不太靈活。在進(jìn)行調(diào)用之前，與調(diào)用者對應(yīng)的stub向系統(tǒng)中的其它場點(diǎn)進(jìn)行廣播，請求有關(guān)的場點(diǎn) 通報(bào)其地址，這必然引起一系列的消息轉(zhuǎn)移。特別，當(dāng)這種廣播是在若干網(wǎng)絡(luò)之間進(jìn)行 時(shí)，其轉(zhuǎn)移速度是很慢的。由系統(tǒng)管理一個(gè)表，其表項(xiàng)的內(nèi)容為站點(diǎn)地址；該場點(diǎn)上將運(yùn)行的遠(yuǎn)程過程的名字?！霸敢狻碑a(chǎn)生一個(gè)可供其它場點(diǎn)引用的過程的那些場點(diǎn)就造一個(gè)表項(xiàng)到這個(gè)表中，該表項(xiàng)給 出了這些場點(diǎn)的地址和此遠(yuǎn)程過程的名字。希望引用遠(yuǎn)程過程的用戶可通過查詢此表獲取

2、有 關(guān)信息。開發(fā)過程大致是這樣的：調(diào)用者調(diào)用本地stub中的一個(gè)過程(開始遠(yuǎn)程過程調(diào)用請求).這個(gè)stub過程把有關(guān)的參數(shù)組裝成一個(gè)消息包或一組消息包，形成一條消息.運(yùn)行 此執(zhí)行過程的遠(yuǎn)程場點(diǎn)的IP地址和執(zhí)行該過程的進(jìn)程ID號也包含在這條消息中.將這條消息發(fā)送給對應(yīng)的RPC runtime(RPC運(yùn)行庫)子程序，由這個(gè)子程序?qū)⑾l(fā) 送到遠(yuǎn)程場點(diǎn).在接收到這條消息時(shí),server端的RPC runtime子程序引用與被調(diào)用者對應(yīng)的stub中 的一個(gè)子程序，并讓它來處理消息.與被調(diào)用者對應(yīng)的stub中的這個(gè)子程序撤卸消息，解析出相關(guān)參數(shù)，并用本地調(diào)用 方式執(zhí)行所指定的過程.返回調(diào)用結(jié)果，調(diào)用者對

3、應(yīng)的stub子程序執(zhí)行return語句返回到用戶，整個(gè)RPC過 程結(jié)束.此3問針對集中分布式死鎖檢測方法何時(shí)或在什么情況下構(gòu)造局部PWG才能反映系統(tǒng)資源的實(shí)際分配情況？(修改)1.每當(dāng)從局部等待圖中去掉一條邊或向局部等待圖插入一條新邊時(shí)周期性的，當(dāng)?shù)却龍D中已經(jīng)發(fā)生了若干改變時(shí)每當(dāng)協(xié)調(diào)者需要引用環(huán)路檢測算法時(shí)以下為死鎖檢測的基本假設(shè)進(jìn)程在整個(gè)系統(tǒng)內(nèi)統(tǒng)一命名每個(gè)結(jié)點(diǎn)有一個(gè)局部等待圖：Gk=(Vk, Ek)，(p, q)Ek等價(jià)于p申請q占有結(jié)點(diǎn)k的資源; 顯然，如果局部等待圖中有環(huán)，則有死鎖；所有的局部等待圖的并有環(huán)是系統(tǒng)死鎖的充要條 件。為什么不同站點(diǎn)上申請資源時(shí)要帶上時(shí)戳？(增加)不同的站點(diǎn)的

4、請求消息附上唯一的標(biāo)識(時(shí)戳)，可以避免報(bào)告假死鎖解決接收消息的順序與發(fā)送消息的順序不一致問題時(shí)間戳及全排序保證了不會死鎖。增加時(shí)間戳，防止回應(yīng)的不及時(shí)(令牌丟失、令牌者故障)利用時(shí)間戳來標(biāo)明申請資源的先后次序，以此來盡量消除對共享資源的競爭。當(dāng)協(xié)調(diào)者故障時(shí)咋辦？如國協(xié)調(diào)者進(jìn)程由于所在的處理機(jī)故障而無法正常工作，系統(tǒng)只得通過在另一個(gè)處理機(jī)上重 新開始一個(gè)新的協(xié)調(diào)者副本才能運(yùn)行。當(dāng)協(xié)調(diào)者進(jìn)程故障時(shí)，需要安排新進(jìn)程代替它：選一個(gè)進(jìn)程；通知其它進(jìn)程；建立相應(yīng)隊(duì)列; 恢復(fù)工作。為了適應(yīng)模塊性、自治性和強(qiáng)健性的要求，系統(tǒng)設(shè)置了多個(gè)控制機(jī)構(gòu)來管理，這樣就形成了 多個(gè)資源與多個(gè)控制機(jī)構(gòu)之間比較復(fù)雜的關(guān)系。當(dāng)

5、協(xié)調(diào)者故障時(shí)，選擇算法必須挑選具有最高優(yōu)先數(shù)的某個(gè)活躍進(jìn)程作為替換者，這個(gè)優(yōu)先 數(shù)還必須告之系統(tǒng)中的每一活躍進(jìn)程。此外，該算法還必須提供某種方式以便于已從故障中 恢復(fù)的進(jìn)程去識別當(dāng)前的協(xié)調(diào)者。具體的協(xié)調(diào)者選擇算法有1.適用于共享通路結(jié)構(gòu)系統(tǒng)的Bully選擇算法，其中每個(gè)進(jìn)程都可 以向系統(tǒng)中其他進(jìn)程發(fā)送消息，2.適用于組織成一個(gè)環(huán)（物理環(huán)或邏輯環(huán)）結(jié)構(gòu)系統(tǒng)的算 法（基于環(huán)的算法）怎樣設(shè)計(jì)該算法（怎樣設(shè)計(jì)死鎖檢測算法？）（層次式方法下面的思考題）層次式死鎖檢測算法分布式算法（修改）（1）開始時(shí)只有最低層的管理者，它們管理各自的PWG（2）檢查每個(gè)管理者各自的PWG，如果存在環(huán)路，表示系統(tǒng)中存在死鎖

6、，算法結(jié)束（3）若任一 2個(gè)管理者的PWG有公共節(jié)點(diǎn)出現(xiàn)，則在每一個(gè)這樣的管理者之上構(gòu)造一 個(gè)新的管理者，并將這些公共管理站點(diǎn)作為該新管理者所管理PWG的一部分，若節(jié) 點(diǎn)公共節(jié)點(diǎn)Pi，Pj出現(xiàn)在其中，且其下屬之一的PWG中存在從Pi到Pj的路徑，則 將Pi-Pj插入新的PWG中。（4）如果構(gòu)造不出新的層次，則算法結(jié)束，返回系統(tǒng)無死鎖，如果可以構(gòu)造新的層次，則重復(fù)第2步。每個(gè)結(jié)點(diǎn)管理自己的局部等待圖，其中一部分結(jié)點(diǎn)被指定為控制者，這些控制者構(gòu)成一個(gè)樹 型結(jié)構(gòu)，樹中每個(gè)非葉結(jié)點(diǎn)管理它的子樹中的控制結(jié)點(diǎn)的局部等待圖設(shè)A、B、C都是控制者（非葉結(jié)點(diǎn)），C是A和B的前輩結(jié)點(diǎn)，如果p同時(shí)出現(xiàn) 在A與B的局

7、部等待圖中，則從C到A和從C至U B的路上的所有控制者結(jié)點(diǎn)的局部等待圖中都含有p。如果p、q是C的局部等待圖中的結(jié)點(diǎn)，且在C的某個(gè)后代結(jié)點(diǎn)的局部等待圖中含有 邊（p, q），則C的局部等待圖中亦含此邊。如果系統(tǒng)中某一個(gè)控制者的局部等待圖中有環(huán)，則有死鎖發(fā)生。為什么設(shè)計(jì)近者優(yōu)先搜索算法？不難驗(yàn)證，采用由近及遠(yuǎn)算法搜索資源不會產(chǎn)生饑餓。被搜索到的每個(gè)結(jié)點(diǎn)幾乎都接收到這 樣的三條消息，即搜索消息，通知誰是后結(jié)點(diǎn)的消息和由前結(jié)點(diǎn)轉(zhuǎn)發(fā)來的繼續(xù)搜索消息。因 此，如果不考慮一個(gè)結(jié)點(diǎn)多次被搜索的情況，或者近考慮樹形網(wǎng)絡(luò)的情況，在最壞情況下需 要發(fā)4n條消息進(jìn)行資源搜索工作。此外，還要加上搜索到資源后轉(zhuǎn)發(fā)的成功

8、信。因而，看 起來由近及遠(yuǎn)算法比前兩種算法通信量大得多。但是，當(dāng)系統(tǒng)中有較多的結(jié)點(diǎn)擁有資源時(shí)， 采用這種算法往往很快就能獲得資源。因此，對于“稀有”資源可能招標(biāo)算法或回聲算法比 較合適，而對于普遍擁有的資源，則由近及遠(yuǎn)算法可能更好些。算法讓資源申請者由近及遠(yuǎn)地搜索，直至遇到具有所需要資源的結(jié)點(diǎn)為止。按照由近及遠(yuǎn)地 搜索資源，可使申請者總是在能夠提供資源的結(jié)點(diǎn)之間，選擇一個(gè)距離它最近的結(jié)點(diǎn)獲得資 源。采用由近及遠(yuǎn)算法搜索資源不會產(chǎn)生饑餓，當(dāng)系統(tǒng)中有較多的結(jié)點(diǎn)擁有資源時(shí)，采用這 種算法往往很快就能獲得資源。上述算法略微改進(jìn)就可以具有較強(qiáng)的強(qiáng)健性。我們規(guī)定，發(fā)搜索消息至一個(gè)下鄰結(jié)點(diǎn)后，如 果在T時(shí)間

9、內(nèi)無回答，則認(rèn)為它已失效，然后向另外一個(gè)下鄰結(jié)點(diǎn)發(fā)搜索消息或者向其后結(jié) 點(diǎn)轉(zhuǎn)發(fā)繼續(xù)搜索消息。不難驗(yàn)證，只要在算法執(zhí)行過程中不產(chǎn)生新的失效結(jié)點(diǎn)，并且失效結(jié) 點(diǎn)不被恢復(fù)，則增加了如上規(guī)則后，由近及遠(yuǎn)算法是強(qiáng)健的?！昂弦灰婚撝怠彼惴ㄔ趺磳?shí)現(xiàn)，分析其算法復(fù)雜度。下面僅從算法的時(shí)空復(fù)雜性及算法的輸出與最優(yōu)解的差距等方面來簡單地分析該算法。為 此，假定有n個(gè)模塊等待分配給m個(gè)同構(gòu)的處理機(jī)。我們可用一個(gè)矩陣表示1MC開銷，由 對稱性知，存貯這方面的數(shù)據(jù)只需n(n-1)/Z個(gè)單元。用另一矩陣存放當(dāng)完成了一次成功的合 一后，修改相關(guān)模塊的IMC開銷后的信息，這也只需n(n-1)/ 2個(gè)單元。不難看出，合一過 程

10、采用的是一種局部性“貪心”策略，即每次查找一對這樣的模塊，它們經(jīng)合一后不僅清除 最大的IMC開銷，而且相應(yīng)的處理機(jī)應(yīng)滿足應(yīng)時(shí)和(或)存貯要求。若令T(n)為合一過程最 壞情況下的時(shí)間復(fù)雜性，則不難得到下面的遞推式：T(n)=查找具有最大IMC開銷模塊對的時(shí)間+修改其它模塊對的IMC開銷的時(shí)間+ T(n-1)顯然，T(n) = O(n3)。若經(jīng)合一處理后剩下的模塊數(shù)大于m，則認(rèn)為合一失敗(此時(shí)，不必進(jìn)入“調(diào)整”階段)。 為此，可假定經(jīng)合一處理后的模塊數(shù)小于等于m?！罢{(diào)整”階段是“合一”階段的繼續(xù)。在 調(diào)整過程中，可用數(shù)組Tv1 . m存放各處理機(jī)的閾值，用Load1 . m存放各處理機(jī)上的實(shí) 際

11、負(fù)載。在合一過程中，由于一對模塊合一后會引起相關(guān)模塊對的IMC發(fā)生變更，因此， 在執(zhí)行調(diào)整過程中，很難知道分離出哪個(gè)模塊(或模塊族)會使得處理開銷最小，故此時(shí)采 用隨機(jī)策略。在此，不妨把調(diào)整過程進(jìn)一步描述為：計(jì)算各處理機(jī)的實(shí)際負(fù)載與其閾值之差Di，i = 1, 2,m；按Di的不增次序排序各處理機(jī)，并用j (j = 1, 2,，m)指稱經(jīng)排序后位于序號j處的 處理機(jī)；對于j = 1, 2,m-1執(zhí)行下面的操作：若處理機(jī)j的Dj大于0，則用隨機(jī)方法從處理機(jī)j上選定一模塊(或模塊族)并把它遷移到 處理機(jī)j+1上。重復(fù)此過程，直至處理機(jī)j的Dj不大于0。必要時(shí)，可對模塊族進(jìn)行分裂。 若處理機(jī)j的Dj

12、不大于0，則不做任何遷移工作。若處理機(jī)m的Dm大于0，則報(bào)告“失敗”，否則調(diào)整成功。由上不難得知，調(diào)整過程的時(shí)間復(fù)雜性約為O(m3)。假定：系統(tǒng)中的處理機(jī)是相同的，且模塊的優(yōu)先級也是一樣的。算法思想：該算法分成兩個(gè)階段：合一、調(diào)整。先將IMC (模塊間通信)最大者合并在一 起(打算分給同一個(gè)處理機(jī))，第二階段看此分配是否超出“閾值”，對超出者進(jìn)行調(diào)整。算法描述：設(shè)有n個(gè)模塊，h個(gè)處理機(jī)：V= m1, m2,mn P= P1, P2,，Ph1、令 S= m1, m2, mn 2、 從S中尋找Si，Sj，它們之間存在最大的IMC，如果合并Si、Sj后滿足內(nèi)存和實(shí)時(shí)要求， 則a）合并 Si、Sj。即

13、用 SiU Sj 代替 Si, Sj；b）對于任取SkS & Sk尹Si & Sk尹Sj執(zhí)行 用Sk與Si和Sj的IMC的和作為Sk與SiUSj的 IMC；3、重復(fù)2,直到找不到可以合并的；4、將S中未被合并的模塊放入一個(gè)“族”5、如果S中現(xiàn)有模塊族數(shù)Wh,則將它們分配給各個(gè)處理機(jī)，否則，對本次合一結(jié)果進(jìn) 行調(diào)整；6、對于每一個(gè)處理機(jī)Pi,執(zhí)行如下操作a）如果Pi分得的模塊超過閾值，則選一個(gè)模塊遷移到輕載者；7、如果對于每一個(gè)處理機(jī)，都沒有超過閾值，則算法結(jié)束，否則，算法失敗；8、以一定的策略將多出來的族放入其它族中，使|S|Wh，然后轉(zhuǎn)6。（6）如何設(shè)計(jì)近者優(yōu)先搜索算法？由近及遠(yuǎn)算法申請者向

14、其某個(gè)鄰結(jié)點(diǎn)發(fā)一搜索消息，附上對資源的需求及參數(shù)p，p為申請者的結(jié)點(diǎn)編 號。接搜索消息后，將發(fā)來搜索消息的結(jié)點(diǎn)的編號和搜索消息中的參數(shù)p登記下來。我們定義 發(fā)來搜索消息的結(jié)點(diǎn)為它的上鄰結(jié)點(diǎn)，搜索消息中的參數(shù)p所規(guī)定的結(jié)點(diǎn)為它的前結(jié)點(diǎn)。如 果接到搜索消息的結(jié)點(diǎn)具有所需要的資源，則向它的上鄰結(jié)點(diǎn)發(fā)一成功消息，并附上自己的 結(jié)點(diǎn)編號，否則它先向其前結(jié)點(diǎn)發(fā)一消息，告訴自己是它的后結(jié)點(diǎn)。然后，發(fā)一消息給其上 鄰結(jié)點(diǎn)，請求繼續(xù)搜索，并附上參數(shù)p，p為自己的結(jié)點(diǎn)編號。上鄰結(jié)點(diǎn)接繼續(xù)搜索消息后，如果還有尚未搜索的下鄰結(jié)點(diǎn)，那么就發(fā)一搜索消息給下鄰 結(jié)點(diǎn)，附上參數(shù)p，p是從繼續(xù)搜索消息中復(fù)制的。如果所有的下鄰結(jié)點(diǎn)都已經(jīng)搜索過，但 是它有后結(jié)點(diǎn)，則將繼續(xù)搜索消息轉(zhuǎn)發(fā)給它的后結(jié)點(diǎn)。如果既沒有尚未搜索的下鄰結(jié)點(diǎn)，又 沒有后結(jié)點(diǎn)，則表示與它相連的所有結(jié)點(diǎn)都已經(jīng)搜索過。此時(shí)，它向其上鄰結(jié)點(diǎn)發(fā)一失敗消 息。如果一個(gè)已經(jīng)被搜索過的結(jié)點(diǎn)又接到搜索消息，則將搜索消息退回，發(fā)搜索消息的結(jié)點(diǎn)就 認(rèn)為該下鄰結(jié)點(diǎn)不存在。接成功或失敗消息后，如果該結(jié)點(diǎn)非申請者，則將此消息轉(zhuǎn)發(fā)給它的上鄰結(jié)點(diǎn)，否則搜索 結(jié)束。申請者或者獲得