2007級研究生《分布計算系統(tǒng)》考試題

2007級研究生《分布計算系統(tǒng)》考試題填空題（每空1分，共20分）名字按結(jié)構(gòu)可分為（絕對名字）和（相對名字）兩種。分布式文件系統(tǒng)中有如下共享語義：（）、（）、（）、（）。發(fā)生死鎖的四個充分必要條件是：（）、（）、（）、（）。處理死鎖的策略有如下四種：（）、（）、（）、（）。原子事務(wù)處理具有如下特性：（）、（）、（）、（）。進程轉(zhuǎn)移的形式有兩種：（）、（）。參考答案：絕對名字；相對名字UNIX語義；對話語義；對話語義；事務(wù)處理語義；不可改變的共享文件的語義互斥；不可剝奪的資源分配；占有并等待；循環(huán)等待預(yù)防；避免；忽略；檢測原子性（Atomicity）；一致性（Consistency）；孤立性（Isolation）；持久性（Durability）搶先方式（又稱為進程遷移）；非搶先方式（又稱為進程放置）選擇題，選擇一個最準確的答案（每小題2分，共20分）在公開密鑰加密方法中，A向B發(fā)送保密數(shù)據(jù)，A應(yīng)該選擇哪個密鑰加密數(shù)據(jù)？A的公開密鑰；B.B的公開密鑰；C.A的保密密鑰；D.B的保密密鑰。分布計算系統(tǒng)屬于如下并行結(jié)構(gòu)：單指令流單數(shù)據(jù)流（SISD）；B.單指令流多數(shù)據(jù)流（SIMD）；C.多指令流單數(shù)據(jù)流（MISD）；D.多指令流多數(shù)據(jù)流（MIMD）。3、在使用公開密鑰加密方法實現(xiàn)數(shù)字簽名時，A向B發(fā)送簽名報文，A應(yīng)該選擇哪個密鑰對數(shù)據(jù)簽名？A.A的公開密鑰；B.B的公開密鑰；C.A的保密密鑰；D.B的保密密鑰。對于兩階段封鎖，下面說法正確的是：A.兩階段封鎖的優(yōu)點之一是不會出現(xiàn)層疊回退的問題；B.層疊回退只會出現(xiàn)在鎖的收縮階段；C.層疊回退只會出現(xiàn)在鎖的增長階段；D.層疊回退在鎖的增長階段和鎖的收縮階段都可能出現(xiàn)。5、對于某個文件有5個副本，為了最有利于讀操作，下面哪種分配讀定額（NR）和寫定額（NW）的方案最合適？A.NR=4，NW=5；B.NR=1，NW=5；C.NR=4，NW=2；D.NR=3，NW=3。6、在分布式文件系統(tǒng)中，對于更新策略和共享語義之間的關(guān)系，下面說法正確的是：A.“關(guān)閉時寫”適合對話語義，“立即寫”適合UNIX語義；B.“關(guān)閉時寫”適合UNIX語義，“立即寫”適合對話語義；C.“關(guān)閉時寫”既適合UNIX語義，又適合對話語義；D.“立即寫”既適合UNIX語義，又適合對話語義。7、對于程序的粒度和聚類之間的關(guān)系，下面說法正確的是：A.對于粗粒度程序而言，性能最優(yōu)的聚類在線性聚類中；B.對于粗粒度程序而言，性能最優(yōu)的聚類在非線性聚類中；C.對于細粒度程序而言，性能最優(yōu)的聚類在線性聚類中；D.對于細粒度程序而言，性能最優(yōu)的聚類在非線性聚類中。8、關(guān)于平面地址和分層地址，下面說法正確的是：A.分層地址使得路由選擇容易，但是不容易創(chuàng)建新的地址；B.平面地址使得路由選擇容易，但是不容易創(chuàng)建新的地址；C.分層地址容易支持進程遷移，但是不容易創(chuàng)建新的地址；D.平面地址容易支持進程遷移，但是不容易創(chuàng)建新的地址。9、兩階段提交協(xié)議的主要作用是：A.實現(xiàn)分布式事務(wù)處理的全局恢復(fù)；B.實現(xiàn)原子事務(wù)處理的孤立性；C.實現(xiàn)原子事務(wù)處理的一致性；D.實現(xiàn)原子事務(wù)處理的局部恢復(fù)。對于以有向圖表示的名字空間，下面說法正確的是：該有向圖中所有目錄節(jié)點不僅有輸入的弧，而且有輸出的弧，而葉節(jié)點只有輸入的弧；該有向圖中只有一個根節(jié)點；該有向圖中某個節(jié)點可能有多個輸入的弧；該有向圖中任何節(jié)點只能有一個輸入的弧，但可以有多個輸出的弧。參考答案：1~5：BDCBB6~10：AADAC簡要回答下列各題（每小題2分，共20分）動態(tài)調(diào)度算法由哪幾個策略組成？在進程等待圖中，什么是“結(jié)”？如何區(qū)分“結(jié)”和循環(huán)？互斥算法的目的是什么？并發(fā)控制的目的是什么？什么是透明性？分布計算系統(tǒng)的透明性的含義是什么？什么是訪問控制？使用公開密鑰加密技術(shù)實現(xiàn)數(shù)字簽名，加密函數(shù)和解密函數(shù)需滿足什么條件？什么是兩個進程間的同步點？同步機構(gòu)的目的是什么？并發(fā)控制的正確性標準是什么？復(fù)制控制算法的作用是什么？什么是有狀態(tài)服務(wù)員？什么是無狀態(tài)服務(wù)員？

四、對于下圖所示的由三個進程組成的分布式系統(tǒng)，為所有的事件提供標量邏輯時間和向量邏輯時間，假設(shè)每個LCi（i=1，2，3）初始化為0，而且P1、P2、P3的d為1。（8分）空間時間C3C2C1C0B3B0B1B2A3A2A1A0P空間時間C3C2C1C0B3B0B1B2A3A2A1A0P3P2P1畫出下列調(diào)度的串行化圖，指出下列調(diào)度中哪些可串行化調(diào)度。（8分）L1=w2(y)w1(y)r3(y)r1(y)w2(x)r3(x)r3(z)r2(z)L2=r3(z)r3(x)w2(x)r2(z)w1(y)r3(y)w2(y)r1(y)L3=r3(z)w3(y)w2(x)r1(y)r3(y)r2(z)r3(z)w1(y)L4=r2(z)w2(y)w2(x)w1(y)r1(y)r3(y)r3(z)r3(x)

緩存緩存緩存p1p2Dw1w2CBA六、下面的以太網(wǎng)，連接有A、B、C、D四個節(jié)點。D節(jié)點為共享主存，有兩個頁面p1和p2，A、B、C可共享這兩個頁面。A、B、C各有一個緩存，且只能緩存一個頁面。p1的初值為w1，p2的初值為w2。A、B、C的緩存初始狀態(tài)為空。緩存緩存緩存p1p2Dw1w2CBA如果緩存一致性協(xié)議采取的是Berkeley探聽緩存寫無效協(xié)議，按順序有如下各步操作，寫出每步操作之后，各緩存和主存的值，以及各緩存的狀態(tài)（重寫、共享重寫、有效、無效或空）。（10分）A讀p1；B讀p