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

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

四、對(duì)于下圖所示的由三個(gè)進(jìn)程組成的分布式系統(tǒng)，為所有的事件提供標(biāo)量邏輯時(shí)間和向量邏輯時(shí)間，假設(shè)每個(gè)LCi（i=1，2，3）初始化為0，而且P1、P2、P3的d為1。（8分）空間時(shí)間C3C2C1C0B3B0B1B2A3A2A1A0P空間時(shí)間C3C2C1C0B3B0B1B2A3A2A1A0P3P2P1畫(huà)出下列調(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四個(gè)節(jié)點(diǎn)。D節(jié)點(diǎn)為共享主存，有兩個(gè)頁(yè)面p1和p2，A、B、C可共享這兩個(gè)頁(yè)面。A、B、C各有一個(gè)緩存，且只能緩存一個(gè)頁(yè)面。p1的初值為w1，p2的初值為w2。A、B、C的緩存初始狀態(tài)為空。緩存緩存緩存p1p2Dw1w2CBA如果緩存一致性協(xié)議采取的是Berkeley探聽(tīng)緩存寫(xiě)無(wú)效協(xié)議，按順序有如下各步操作，寫(xiě)出每步操作之后，各緩存和主存的值，以及各緩存的狀態(tài)（重寫(xiě)、共享重寫(xiě)、有效、無(wú)效或空）。（10分）A讀p1；B讀p