高級(jí)操作系統(tǒng)試題

2．請(qǐng)求驅(qū)動(dòng)式令牌傳遞方法中，若pi發(fā)出request消息后久未獲得Token，該怎么處理？若引

入時(shí)戳，該算法應(yīng)做何修改？

答：

在請(qǐng)求驅(qū)動(dòng)式令牌傳遞方法中，或pi發(fā)出的request消息后久未獲得Token，應(yīng)該決定是站點(diǎn)故障還是Token丟失，需要有對(duì)應(yīng)邏輯環(huán)重構(gòu)方法和Token生成方法。

可以引入時(shí)時(shí)戳增加算法的強(qiáng)健性，具體如下:

(1)當(dāng)request消息后久未獲得令牌，則向其它進(jìn)程發(fā)詢(xún)問(wèn)消息；若其它進(jìn)程無(wú)反對(duì)消息到達(dá)，則重新生成令牌，否則繼續(xù)等待。

(2)若接收到詢(xún)問(wèn)消息的進(jìn)程是令牌的持有者，或已發(fā)出一樣Request消息，且自已Request消息的時(shí)戳先于詢(xún)問(wèn)進(jìn)程Request消息的時(shí)戳，則立即發(fā)回一條反對(duì)消息。

(3)令牌持有者傳遞令牌時(shí)，若發(fā)現(xiàn)接收者故障，需要調(diào)用邏輯環(huán)重構(gòu)算法進(jìn)行環(huán)重構(gòu)，再重新選擇接收者。

3.我們討論了資源管理中的“近者優(yōu)先”策略，試設(shè)計(jì)具體實(shí)現(xiàn)該策略的算法并進(jìn)行算法分析。

由近及遠(yuǎn)算法設(shè)計(jì)過(guò)程如下：

⑴申請(qǐng)者向其某個(gè)鄰結(jié)點(diǎn)發(fā)一搜索消息，附上對(duì)資源的需求及參數(shù)p，p為申請(qǐng)者的結(jié)點(diǎn)編號(hào)。

⑵接搜索消息后，將發(fā)來(lái)搜索消息的結(jié)點(diǎn)的編號(hào)和搜索消息中的參數(shù)p登記下來(lái)。我們定義發(fā)來(lái)搜索消息的結(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)編號(hào)，否則它先向其前結(jié)點(diǎn)發(fā)一消息，告訴自己是它的后結(jié)點(diǎn)。然后，發(fā)一消息給其上鄰結(jié)點(diǎn)，請(qǐng)求繼續(xù)搜索，并附上參數(shù)p，p為自己的結(jié)點(diǎn)編號(hào)。

⑶上鄰結(jié)點(diǎn)接繼續(xù)搜索消息后，如果還有尚未搜索的下鄰結(jié)點(diǎn)，那么就發(fā)一搜索消息給下鄰結(jié)點(diǎn)，附上參數(shù)p，p是從繼續(xù)搜索消息中復(fù)制的。如果所有的下鄰結(jié)點(diǎn)都已經(jīng)搜索過(guò)，但是它有后結(jié)點(diǎn)，則將繼續(xù)搜索消息轉(zhuǎn)發(fā)給它的后結(jié)點(diǎn)。如果既沒(méi)有尚未搜索的下鄰結(jié)點(diǎn)，又沒(méi)有后結(jié)點(diǎn)，則表示與它相連的所有結(jié)點(diǎn)都已經(jīng)搜索過(guò)。此時(shí)，它向其上鄰結(jié)點(diǎn)發(fā)一失敗消息。

⑷如果一個(gè)已經(jīng)被搜索過(guò)的結(jié)點(diǎn)又接到搜索消息，則將搜索消息退回，發(fā)搜索消息的結(jié)點(diǎn)就認(rèn)為該下鄰結(jié)點(diǎn)不存在。

⑸接成功或失敗消息后，如果該結(jié)點(diǎn)非申請(qǐng)者，則將此消息轉(zhuǎn)發(fā)給它的上鄰結(jié)點(diǎn)，否則搜索結(jié)束。申請(qǐng)者或者獲得最近的能夠提供所需要的資源的結(jié)點(diǎn)編號(hào)，或者系統(tǒng)中沒(méi)有所需要的資源。

為了算法的強(qiáng)健性，我們?cè)黾酉铝幸?guī)則：

⑹如果發(fā)搜索消息到下鄰結(jié)點(diǎn)后，在某個(gè)T時(shí)間內(nèi)沒(méi)有收到回復(fù)消息，則認(rèn)為該下鄰結(jié)點(diǎn)已經(jīng)失效。然后，向另外一個(gè)下鄰結(jié)點(diǎn)發(fā)搜索消息，或者向后結(jié)點(diǎn)發(fā)繼續(xù)搜索消息。

不難看出，只要在算法執(zhí)行過(guò)程中不產(chǎn)生新的失效結(jié)點(diǎn)，并且失效結(jié)點(diǎn)不被恢復(fù)，增加了上述規(guī)則后，由近及遠(yuǎn)算法是強(qiáng)健的不難驗(yàn)證，采用由近及遠(yuǎn)算法搜索資源不會(huì)產(chǎn)生饑餓。被搜索到的每個(gè)結(jié)點(diǎn)幾乎都接收到這樣的三條消息，即搜索消息，通知誰(shuí)是后結(jié)點(diǎn)的消息和由前結(jié)點(diǎn)轉(zhuǎn)發(fā)來(lái)的繼續(xù)搜索消息。因此，如果不考慮一個(gè)結(jié)點(diǎn)多次被搜索的情況，或者近考慮樹(shù)形網(wǎng)絡(luò)的情況，在最壞情況下需要發(fā)4n條消息進(jìn)行資源搜索工作。此外，還要加上搜索到資源后轉(zhuǎn)發(fā)的成功信。因而，看起來(lái)由近及遠(yuǎn)算法比前兩種算法通信量大得多。但是，當(dāng)系統(tǒng)中有較多的結(jié)點(diǎn)擁有資源時(shí)，采用這種算法往往很快就能獲得資源。因此，對(duì)于“稀有”資源可能招標(biāo)算法或回聲算法比較合適，而對(duì)于普遍擁有的資源，則由近及遠(yuǎn)算法可能更好些。

算法讓資源申請(qǐng)者由近及遠(yuǎn)地搜索，直至遇到具有所需要資源的結(jié)點(diǎn)為止。按照由近及遠(yuǎn)地搜索資源，可使申請(qǐng)者總是在能夠提供資源的結(jié)點(diǎn)之間，選擇一個(gè)距離它最近的結(jié)點(diǎn)獲得資源。采用由近及遠(yuǎn)算法搜索資源不會(huì)產(chǎn)生饑餓，當(dāng)系統(tǒng)中有較多的結(jié)點(diǎn)擁有資源時(shí)，采用這種算法往往很快就能獲得資源。

上述算法略微改進(jìn)就可以具有較強(qiáng)的強(qiáng)健性。我們規(guī)定，發(fā)搜索消息至一個(gè)下鄰結(jié)點(diǎn)后，如果在T時(shí)間內(nèi)無(wú)回答，則認(rèn)為它已失效，然后向另外一個(gè)下鄰結(jié)點(diǎn)發(fā)搜索消息或者向其后結(jié)點(diǎn)轉(zhuǎn)發(fā)繼續(xù)搜索消息。不難驗(yàn)證，只要在算法執(zhí)行過(guò)程中不產(chǎn)生新的失效結(jié)點(diǎn)，并且失效結(jié)點(diǎn)不被恢復(fù)，則增加了如上規(guī)則后，由近及遠(yuǎn)算法是強(qiáng)健的。

5．試設(shè)計(jì)層次式死鎖檢測(cè)方法的具體算法并進(jìn)行算法分析。

答：

層次式死鎖檢測(cè)算法將這些信息分散給各個(gè)進(jìn)程來(lái)管理，是一種分布式死鎖檢測(cè)算法。

全局等待圖的每個(gè)站點(diǎn)管理自己的局部等待圖，被分散給若干控制者管理，這些控制者組織成樹(shù)型結(jié)構(gòu)，其中樹(shù)中的葉子結(jié)點(diǎn)包含單個(gè)站點(diǎn)的局部等待圖，每個(gè)非葉子結(jié)點(diǎn)控制著它下面子樹(shù)的控制者管理的等待圖。

令A(yù)，B，C是控制者，C是A和B的唯一的父親。若結(jié)點(diǎn)Pi出現(xiàn)在控制者A和B的局部等待圖中，那么把Pi插入到下面的等待圖中：

控制者C的等待圖中；

從C到A的路徑中每一個(gè)控制者的等待圖中；

從C到B的路徑中每一個(gè)控制者的等待圖中

此外，如果進(jìn)程Pi和Pj出現(xiàn)在控制者D的等待圖中，而且在D的孩子之一的等待圖中存在從Pi

到Pj的路徑，那么邊(Pi，Pj)也必須在D的等待圖中出現(xiàn)。

如果，這些等待圖中任何一個(gè)存在環(huán)路那么該系統(tǒng)發(fā)生死鎖需引用死鎖解除算法。

例如，考慮圖中的系統(tǒng)，該系統(tǒng)的樹(shù)形結(jié)構(gòu)如下圖所示。由于Pi和Pj都在A和B中出現(xiàn)，所以它們也出現(xiàn)在C中。由于在A中存在從P2

到P3的路徑，因此，C中包含邊(P2，P3)。類(lèi)似地，因?yàn)锽中存在從P3

到P2的路徑，所以C中也包含邊(P3，P2)。注意，C的等待圖中存在環(huán)路，從而隱含該系統(tǒng)已出現(xiàn)死鎖。

7.試對(duì)“合一閾值”（merge-threshold）啟發(fā)式任務(wù)分配算法進(jìn)行詳細(xì)設(shè)計(jì)，并對(duì)其進(jìn)行時(shí)間和空間復(fù)雜性分析

解答過(guò)程如下：

假定：系統(tǒng)中的處理機(jī)是相同的，且模塊的優(yōu)先級(jí)也是一樣的。

算法思想：該算法分成兩個(gè)階段：合一、調(diào)整。先將

IMC（模塊間通信）

最大者合并在一起（打算分給同一個(gè)處理機(jī)），第二階段看此分配是否超出“閾值”，對(duì)超出者進(jìn)行調(diào)整。

算法描述：

設(shè)有

n

個(gè)模塊，h

個(gè)處理機(jī)：

V={

m1,m2,…,mn

}

P={

P1,P2,…,Ph}

1、令S=

{{

m1},{

m2},…,{

mn

}

}

2、從S中尋找Si，Sj，它們之間存在最大的IMC，如果合并Si、Sj后滿(mǎn)足內(nèi)存和實(shí)時(shí)要求，則

a)

合并Si、Sj。即用Si∪Sj代替Si，Sj；

b)

對(duì)于任取Sk∈S

&

Sk≠Si

&

Sk≠Sj

執(zhí)行

用Sk與Si和Sj的IMC的和作為Sk與Si∪Sj的IMC；

3、重復(fù)

2，直到找不到可以合并的；

4、將

S

中未被合并的模塊放入一個(gè)“族”

5、如果

S

中現(xiàn)有模塊族數(shù)≤h，則將它們分配給各個(gè)處理機(jī)，否則，對(duì)本次合一結(jié)果進(jìn)行調(diào)整；

6、對(duì)于每一個(gè)處理機(jī)Pi，執(zhí)行如下操作

a)

如果Pi分得的模塊超過(guò)閾值，則選一個(gè)模塊遷移到輕載者；

7、如果對(duì)于每一個(gè)處理機(jī)，都沒(méi)有超過(guò)閾值，則算法結(jié)束，否則，算法失敗；

8、以一定的策略將多出來(lái)的族放入其它族中，使|S|≤h，然后轉(zhuǎn)

6。

下面僅從算法的時(shí)空復(fù)雜性及算法的輸出與最優(yōu)解的差距等方面來(lái)簡(jiǎn)單地分析該算法。為此，假定有n個(gè)模塊等待分配給m個(gè)同構(gòu)的處理機(jī)。我們可用一個(gè)矩陣表示1MC開(kāi)銷(xiāo)，由對(duì)稱(chēng)性知，存貯這方面的數(shù)據(jù)只需n(n-1)/2個(gè)單元。用另一矩陣存放當(dāng)完成了一次成功的合一后，修改相關(guān)模塊的IMC開(kāi)銷(xiāo)后的信息，這也只需n(n-1)/

2個(gè)單元。不難看出，合一過(guò)程采用的是一種局部性“貪心”策略,即每次查找一對(duì)這樣的模塊，它們經(jīng)合一后不僅清除最大的IMC開(kāi)銷(xiāo)，而且相應(yīng)的處理機(jī)應(yīng)滿(mǎn)足應(yīng)時(shí)和（或）存貯要求。若令T(n)為合一過(guò)程最壞情況下的時(shí)間復(fù)雜性，則不難得到下面的遞推式：

T(n)

＝

查找具有最大IMC開(kāi)銷(xiāo)模塊對(duì)的時(shí)間

+

修改其它模塊對(duì)的IMC開(kāi)銷(xiāo)的時(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)整過(guò)程中，可用數(shù)組Tv[1

..m]存放各處理機(jī)的閾值，用Load[1

..m]存放各處理機(jī)上的實(shí)際負(fù)載。在合一過(guò)程中，由于一對(duì)模塊合一后會(huì)引起相關(guān)模塊對(duì)的IMC發(fā)生變更，因此，在執(zhí)行調(diào)整過(guò)程中，很難知道分離出哪個(gè)模塊（或模塊族）會(huì)使得處理開(kāi)銷(xiāo)最小，故此時(shí)采用隨機(jī)策略。在此，不妨把調(diào)整過(guò)程進(jìn)一步描述為：

⑴計(jì)算各處理機(jī)的實(shí)際負(fù)載與其閾值之差Di，i

＝

1,2,…,m；

⑵按Di的不增次序排序各處理機(jī)，并用j（j

＝

1,2,…,m）指稱(chēng)經(jīng)排序后位于序號(hào)j處的處理機(jī)；

⑶對(duì)于j

＝

1,2,…,m-1執(zhí)行下面的操作：

若處理機(jī)j的Dj大于0，則用隨機(jī)方法從處理機(jī)j上選定一模塊（或模塊族）并把它遷移到處理機(jī)j＋1上。重復(fù)此過(guò)程，直至處理機(jī)j的Dj不大于0。必要時(shí)，可對(duì)模塊族進(jìn)行分裂。

若處理機(jī)j的Dj不大于0，則不做任何遷移工作。

⑷若處理機(jī)m的Dm大于0，則報(bào)告“失敗”，否則調(diào)整成功。

由上不難得知，調(diào)整過(guò)程的時(shí)間復(fù)雜性約為O(m3)。

8.何謂OS的安全性？對(duì)分布式OS而言，必須優(yōu)先突破的安全技術(shù)是哪些。

答：

OS的安全性指信息的保密性，完整性和可用性。安全操作系統(tǒng)，是指計(jì)算機(jī)信息系統(tǒng)在自主訪問(wèn)控制、強(qiáng)制訪問(wèn)控制、標(biāo)記、身份鑒別、客體重用、審計(jì)、數(shù)據(jù)完整性、隱蔽信道分析、可信路徑、可信恢復(fù)等十個(gè)方面滿(mǎn)足相應(yīng)的安全技術(shù)要求。

網(wǎng)絡(luò)是分布式系統(tǒng)的基礎(chǔ)，分布式系統(tǒng)是網(wǎng)絡(luò)的高級(jí)發(fā)展形式。而網(wǎng)絡(luò)方面的故障（帶寬、信息丟失、通信延遲、網(wǎng)絡(luò)負(fù)載趨于飽和、網(wǎng)絡(luò)分割等等），會(huì)抵消通過(guò)建立分布式系統(tǒng)所獲得的大部分優(yōu)勢(shì)。

若允許用戶(hù)很方便地存取整個(gè)系統(tǒng)，則他們同樣也就能很方便地存取與其無(wú)關(guān)的數(shù)據(jù)，從而導(dǎo)致對(duì)保密數(shù)據(jù)的訪問(wèn)，破壞了安全性。此外。分布式系統(tǒng)在地域、資源、功能方面地分散性，也帶來(lái)了系統(tǒng)的安全隱患。

所以對(duì)于分布式OS應(yīng)該首先突破隱蔽信道分析、可信路徑、可信恢復(fù)等安全技術(shù)。