2023年 吉林大学 分布计算系统 期末真题（回忆版）

2023年吉林大学分布计算系统会议期末真题

一、填空题（10分，每空1分）

1. 名字解析方法分为（）、（）

2. 如果有n个进程参加互斥，使用时间戳算法完成一次互斥需要（）个报文，使用Ricart-Agrawala互斥算法完成一次互斥需要（）个报文

3. 一个文件有n个副本，使用同步表表决发完成一次更新，共需传送（）个报文

4. 由局部检查点组成的两种不一致的全局状态为（）、（）

5. 在分布式共享存储器中，目录方式的缓存一致性协议有如下三种：（）、（）、（）

二、判断题（10分，每个1分）

1. 在公开密钥加密方法中，A想B发送保密数据，A一个个选择B的保密密钥加密数据

2. 分布式计算系统属于多指令多数据流（MIMD）并行结构

3. 在使用公开密钥加密方法实现数字签名时，A向B发送签名报文，A应该选择A的保密密钥对数据签名

4. 在分布式文件系统中，“关闭时写”适合对话语义，“立即写”适合UNIX语义

5. 对于细粒度程序而言，性能最优的聚类在非线性聚类中

6. 两阶段提交协议的主要作用是实现分布式事物处理的全局回复

7. 对于以有向图表示的名字空间，该有向图中所有目录节点不仅有输入的弧，而且还有输出的弧，而叶节点只有输入的弧

8. 对于某个多副本文件，为了有利于读操作，应分配较大的读定额（NR）和较小的写定额（NW）

9. 复制控制算法是为了保证分布式数据库的内部一致性

10. 分布式文件系统的事务处理语义可以通过加锁的方式来实现

三、简答题（30分，每个3分）

1. 什么是名字透明度，什么是位置透明度，他们的区别是什么？
2. 操作系统的硬件异构性主要表现在哪些方面？
3. 常用的地址结构的两种形式是什么，以及他们对应的优缺点？
4. 报文摘要的基本属性有什么？
5. 异步检查点，怎么获得最近的一致检查点集合？
6. 互斥的目的是什么，什么是正确的互斥算法？
7. 并发控制的目的和正确性标准是什么？
8. 在先发生关系如何确定先后次序，什么情况下在先发生关系事因果相连的，什么情况下是并发的？
9. 基于时间戳的预防死锁的方法有哪几个，怎么解决“饥饿”问题？
10. 什么是有状态服务员，什么是无状态服务员？

四、计算大题（20分，每个10分）

1、有三个账户A、B、C,分别存款400,500,600元，有如下应用实例：A向B转账100元，B向C转账150元，C向A转账200元。

问：如何编制转账程序以实现可串行化调度（程序只需要给出读写原语和加锁解锁原语）在此情况下，三个实例是否可能发生死锁，如果有可能发生死锁，死锁是怎么发生的？是否会发生 层叠回退的现象，如果发生层叠回退，层叠回退是怎么发生的？

2、下面的以太网，连接有A，B，C、D四个节点，D节点为共享主存，有两个页面p1和p2，A，B，C可共享者两个页面。A，B，C各有一个缓存，且只能缓存一个页面，p1的初始值为w1，p2的初始值为w2。A，B，C的缓存初始状态为无效。

如果缓存一致性协议采用的事Berkeley探听缓存写无效协议，按顺序有如下各步操作，写出每步操作之后，各缓存和主存的值，以及各缓存的状态（重写、有效、无效）

1. A读p1
2. B读p2
3. C向p1写入w3
4. A读p2
5. C向p2写入w4

五、综述题（30分，每个15分）

1、哪些问题与共享资源相关，以及对应的解决办法？

2、请说明分布计算系统的多副本数据的必要性，说明本课程那些内容与多数据副本相关？