2007级研究生《分布计算系统》考试题

2007级研究生《分布计算系统》考试题填空题（每空1分，共20分）名字按结构可分为（绝对名字）和（相对名字）两种。分布式文件系统中有如下共享语义：（）、（）、（）、（）。发生死锁的四个充分必要条件是：（）、（）、（）、（）。处理死锁的策略有如下四种：（）、（）、（）、（）。原子事务处理具有如下特性：（）、（）、（）、（）。进程转移的形式有两种：（）、（）。参考答案：绝对名字；相对名字UNIX语义；对话语义；对话语义；事务处理语义；不可改变的共享文件的语义互斥；不可剥夺的资源分配；占有并等待；循环等待预防；避免；忽略；检测原子性（Atomicity）；一致性（Consistency）；孤立性（Isolation）；持久性（Durability）抢先方式（又称为进程迁移）；非抢先方式（又称为进程放置）选择题，选择一个最准确的答案（每小题2分，共20分）在公开密钥加密方法中，A向B发送保密数据，A应该选择哪个密钥加密数据？A的公开密钥；B.B的公开密钥；C.A的保密密钥；D.B的保密密钥。分布计算系统属于如下并行结构：单指令流单数据流（SISD）；B.单指令流多数据流（SIMD）；C.多指令流单数据流（MISD）；D.多指令流多数据流（MIMD）。3、在使用公开密钥加密方法实现数字签名时，A向B发送签名报文，A应该选择哪个密钥对数据签名？A.A的公开密钥；B.B的公开密钥；C.A的保密密钥；D.B的保密密钥。对于两阶段封锁，下面说法正确的是：A.两阶段封锁的优点之一是不会出现层叠回退的问题；B.层叠回退只会出现在锁的收缩阶段；C.层叠回退只会出现在锁的增长阶段；D.层叠回退在锁的增长阶段和锁的收缩阶段都可能出现。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、在分布式文件系统中，对于更新策略和共享语义之间的关系，下面说法正确的是：A.“关闭时写”适合对话语义，“立即写”适合UNIX语义；B.“关闭时写”适合UNIX语义，“立即写”适合对话语义；C.“关闭时写”既适合UNIX语义，又适合对话语义；D.“立即写”既适合UNIX语义，又适合对话语义。7、对于程序的粒度和聚类之间的关系，下面说法正确的是：A.对于粗粒度程序而言，性能最优的聚类在线性聚类中；B.对于粗粒度程序而言，性能最优的聚类在非线性聚类中；C.对于细粒度程序而言，性能最优的聚类在线性聚类中；D.对于细粒度程序而言，性能最优的聚类在非线性聚类中。8、关于平面地址和分层地址，下面说法正确的是：A.分层地址使得路由选择容易，但是不容易创建新的地址；B.平面地址使得路由选择容易，但是不容易创建新的地址；C.分层地址容易支持进程迁移，但是不容易创建新的地址；D.平面地址容易支持进程迁移，但是不容易创建新的地址。9、两阶段提交协议的主要作用是：A.实现分布式事务处理的全局恢复；B.实现原子事务处理的孤立性；C.实现原子事务处理的一致性；D.实现原子事务处理的局部恢复。对于以有向图表示的名字空间，下面说法正确的是：该有向图中所有目录节点不仅有输入的弧，而且有输出的弧，而叶节点只有输入的弧；该有向图中只有一个根节点；该有向图中某个节点可能有多个输入的弧；该有向图中任何节点只能有一个输入的弧，但可以有多个输出的弧。参考答案：1~5：BDCBB6~10：AADAC简要回答下列各题（每小题2分，共20分）动态调度算法由哪几个策略组成？在进程等待图中，什么是“结”？如何区分“结”和循环？互斥算法的目的是什么？并发控制的目的是什么？什么是透明性？分布计算系统的透明性的含义是什么？什么是访问控制？使用公开密钥加密技术实现数字签名，加密函数和解密函数需满足什么条件？什么是两个进程间的同步点？同步机构的目的是什么？并发控制的正确性标准是什么？复制控制算法的作用是什么？什么是有状态服务员？什么是无状态服务员？

四、对于下图所示的由三个进程组成的分布式系统，为所有的事件提供标量逻辑时间和向量逻辑时间，假设每个LCi（i=1，2，3）初始化为0，而且P1、P2、P3的d为1。（8分）空间时间C3C2C1C0B3B0B1B2A3A2A1A0P空间时间C3C2C1C0B3B0B1B2A3A2A1A0P3P2P1画出下列调度的串行化图，指出下列调度中哪些可串行化调度。（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六、下面的以太网，连接有A、B、C、D四个节点。D节点为共享主存，有两个页面p1和p2，A、B、C可共享这两个页面。A、B、C各有一个缓存，且只能缓存一个页面。p1的初值为w1，p2的初值为w2。A、B、C的缓存初始状态为空。缓存缓存缓存p1p2Dw1w2CBA如果缓存一致性协议采取的是Berkeley探听缓存写无效协议，按顺序有如下各步操作，写出每步操作之后，各缓存和主存的值，以及各缓存的状态（重写、共享重写、有效、无效或空）。（10分）A读p1；B读p