分布计算系统备考重点

分布计算系统
课程笔记

2024期末真题 ​

判断题（2*5） ​

  1. 在公开密钥加密方法中，A向B发送保密数据，A应该选择B的保密密钥加密数据
  2. 在使用公开密钥加密方法实现数字签名时，A向B发送签名报文，A应该选择A的保密密钥对数据签名
  3. 在分布式文件系统中，“关闭时写”适合UNIX语义，“立即写”适合对话语义
  4. 对于某个多副本文件，为了有利于读操作，应分配较大的读定额（NR）和较小的写定额（NW）
  5. 分布式文件系统的事务处理语义可以通过加锁的方式来实现

简答题（4*5） ​

  1. 在先发生关系如何确定先后次序，什么情况下在先发生关系是因果相连的，什么情况下是并发的？
  2. 互斥的目的是什么，什么是正确的互斥算法？
  3. 并发控制的目的和正确性标准是什么？
  4. 基于时间戳的预防死锁的方法有哪几个，怎么解决“饥饿”问题？
  5. 什么是有状态服务员，什么是无状态服务员？

大题（10*4） ​

  1. 有三个账户A、B、C,分别存款400,500,600元，有如下应用实例：A向B转账100元，B向C转账150元，C向A转账200元。问：如何编制转账程序以实现可串行化调度（程序只需要给出读写原语和加锁解锁原语）在此情况下，三个实例是否可能发生死锁，如果有可能发生死锁，死锁是怎么发生的？是否会发生 层叠回退的现象，如果发生层叠回退，层叠回退是怎么发生的？
  2. 说明意图表方法和先写运行记录方法这两种实现原子事物处理局部恢复的方法中，哪种与两阶段封锁相匹配，哪种与严格两阶段封锁相匹配？
  3. 在Maekawa互斥算法中，设有13个进程(P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13)，请给出每个进程的请求子集，要求请求子集中的进程尽量少，并且每个请求子集包含的进程数相同，各进程在请求子集中出现的机会均等，以本例说明Maekawa互斥算法的两个极端情况是什么？
  4. 在使用对话语义的分布式文件系统中，文件F的内容为"abcde"，有A,B,C三个用户访问文件F，A、B在同一主机上，C在另一个主机上，A、B、C打开文件F，A将文件改为"UVWXYZ"，此时ABC读到的内容是什么？B、C关闭后再打开，读到的内容是什么？A、B、C关闭再打开，他们读到的内容是什么？

论述题（15*2） ​

  1. 本课程哪些内容与共享资源相关？
  2. 本课程哪些内容与多数据副本相关？

2023期末真题解析 ​

此部分题目以CC 4.0 BY-SA协议摘自Phi_jida

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

  1. 名字解析方法分为（重复解析）、（递归解析）

重复，即让顾客按照服务员给出的地址寻找下一个服务员重复进行解析
递归，即服务员按照地址寻找下一级服务员，递归进行解析

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

时间戳算法需要向所有的n-1歌进程发送请求报文，并收到所有进程的回答报文后才能进入临界区，退出临界区时发送n-1个释放报文，所以是3(n-1)
ra算法其他进程先比较请求方的时间戳，如果比自己晚，就在自己使用完临界区后再发回答报文，因此不需要释放报文，所以是2(n-1)

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

n个控制者需要向所有其他n-1个控制者发送投票报文，每个控制者完成本地副本更新后需要向所有其他n-1个控制者发送END报文，所以是n×[2(n−1)]n\times [ 2(n-1)]

  1. 由局部检查点组成的两种不一致的全局状态为（丢失报文）、（孤儿报文）
  1. 丢失报文。进程i的检查点状态显示它给进程j发送了报文m，但是进程j并没有关于该报文的纪录。 （发了没收到）
  2. 孤儿报文。进程j的检查点状态显示它收到了一个来自进程i的报文m，但是进程i的状态显示它没有向进程j发送过报文m。（收到了但是没有来源）
  1. 在分布式共享存储器中，目录方式的缓存一致性协议有如下三种：（全映像目录）、（有限目录）、（链式目录）

全映像目录的每个目录项保持N个指针，这里N是系统中处理器的个数。有限目录和全映像目录的不同之处在于，有限目录的每个目录项具有固定数量的指针，与系统中处理机数量无关。链式目录与全映像目录相似，只是它将目录分布于各缓存器。
意思是全映像目录指针管够，有限目录只能保存最新的若干指针，链式目录相同的对象只指向最新的，最新的指向次新的。

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

  1. 在公开密钥加密方法中，A向B发送保密数据，A应该选择B的保密密钥加密数据（x）

应选择B的公钥进行加密，这样B就可以用自己的私钥解密

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

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

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

UNIX语义下，对文件的修改是实时可看的；对话语义下，文件修改在本地其他用户是实时可看的，远程用户在修改保存后重新打开才看到修改后的内容

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

细粒度最优聚类不知道，粗粒度最优聚类一定的线性聚类中。

  1. 两阶段提交协议的主要作用是实现分布式事物处理的全局恢复（√）

两阶段提交协议(2PC) 是一个分布式提交协议，分布式提交用于保证一个进程组中的每一个成员要么都执行某一个操作，要么都不执行这个操作。分布式提交用于分布式事务处理的全局恢复。

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

根目录节点没有输入的弧

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

只有大于等于定额的管理员同意才能读或写，因此有利于读，要将读定额尽量设置小

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

保证的是数据库副本间相互的一致性

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

事务处理语义要求可串行化的文件处理，然而锁的增长阶段容易产生死锁。

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

  1. 什么是名字透明度，什么是位置透明度，他们的区别是什么？
  • 名字透明。名字透明指的是对象的命名在全局是唯一的，不管在什么地方访问该对象使用的名字都是一样的。这样一来，在系统中移动一个程序不影响它的正确性。
  • 位置透明。位置透明指的是资源的名字中不包含该资源的位置信息。这样一来，当该资源在系统中移动时，在资源名字保持不变的情况下，原有的程序都可正常运行。
  1. 操作系统的硬件异构性主要表现在哪些方面？

指令系统不同，数据表示方法不同，机器配置不同

  1. 常用的地址结构的两种形式是什么，以及他们对应的优缺点？

分层地址和平面地址

  • 平面地址
    • 优点：进程迁移时仍可用原地址
    • 缺点：路由选择困难，地址赋值复杂
  • 分层地址
    • 优点：路由选择容易，可在每个网络单独决定主机号码，并自动给出高位地址
    • 缺点：进程迁移时不能用原来地址
  1. 报文摘要的基本属性有什么？
  1. 给出报文P就很容易计算出其报文摘要MD(P)。
  2. 只给出MD(P)，几乎无法推导出P。（单向性）
  3. 无法生成这样的两条报文，它们具有同样的报文摘要。 （抗碰撞性）
  1. 异步检查点，怎么获得最近的一致检查点集合？
  1. 比较发送的和接收的报文数量来检测孤儿报文的存在。如果接收到的报文数目和任何发送报文的进程发送的报文的数目是一致的，那么就可以认为找到了一个局部检查点的一致集合。
  2. 使用间隔依赖图来进行检测。如果每个进程i的向量时钟是LCi，一个检查点集合是一致的，当且仅当不存在i和j满足LCi＜LCj。
  1. 互斥的目的是什么，什么是正确的互斥算法？

互斥算法的主要目标是保证在任一个时刻只能有一个进程访问临界区。一个正确的互斥算法必须避免冲突(死锁和饿死)和保证公平性。为此，算法应满足以下三个条件：

  1. 已获得资源的进程必须先释放资源之后，另一个进程才能得到资源；
  2. 不同的请求应该按照这些请求的产生顺序获得满足，请求应该按照某种规则进行排序，例如使用逻辑时钟确定请求的顺序；
  3. 若获得资源的每个进程最终都释放资源，则每个请求最终都能满足。
  1. 并发控制的目的和正确性标准是什么？

并发控制的目的是在有多个用户的情况下允许每个用户像单个用户那样访问共享资源，多个用户同时访问时互相不干扰。并发控制要解决多个用户的活动之间的切换，保护一个用户的活动不受另一个用户的活动的影响，以及对相互依赖的若干活动进行同步等问题。

并发控制的正确性标准：

  1. 用户交给系统的每个事务处理最终将被执行，并最终得到完成；
  2. 多个事务处理并发执行的结果和这多个事务处理串行执行的结果相同。
  1. 在先发生关系如何确定先后次序，什么情况下在先发生关系是因果相连的，什么情况下是并发的？
  1. 如果a和b均是同一进程中的两个事件，并且a在b之前出现，则a→b；
  2. 若a代表“一个进程发送一个报文”这个事件，b代表“另一个进程接收这个报文”这个事件，则a→b；
  3. 如果a→b，且b→c，则a→c。

两个不同的事件a和b，如果a→b，或b→a，则事件a和b是因果关联的。如果a→b和b→a均不成立，则称事件a和b是并发的。

  1. 基于时间戳的预防死锁的方法有哪几个，怎么解决“饥饿”问题？
  1. 等待-死亡方案。年轻者请求年老者资源，年轻者死亡。年老者请求年轻者资源，年老者等待。
  2. 伤害-等待方案。年轻者请求年老者资源，年轻者等待。年老者请求年轻者资源，年轻者死亡。
  1. 什么是有状态服务员，什么是无状态服务员？

当一个服务员在为其顾客请求进行服务的时候，如果它保存其顾客的有关信息时，称该服务员是有状态的。相反，如果服务员在为其顾客请求进行服务的时候不保存该顾客的任何信息，就称该服务员是无状态的

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

  1. 有三个账户A、B、C,分别存款400,500,600元，有如下应用实例：A向B转账100元，B向C转账150元，C向A转账200元。问：如何编制转账程序以实现可串行化调度（程序只需要给出读写原语和加锁解锁原语）在此情况下，三个实例是否可能发生死锁，如果有可能发生死锁，死锁是怎么发生的？是否会发生 层叠回退的现象，如果发生层叠回退，层叠回退是怎么发生的？

  2. Berkeley探听缓存写无效协议（奔腾2007年第六题）

其他历年题目 ​

信息安全原理复习重点
分布计算系统笔记——第十章 分布式共享存储器