分布式操作系统考试题

《分布式操作系统考试题》由会员分享，可在线阅读，更多相关《分布式操作系统考试题（17页珍藏版）》请在装配图网上搜索。

1、分布式操作系统1 在交换式 Dash 多处理机系统中，为了保持缓存一致性，采用了 Dash 协议，某一簇中的 一 CPU 写一未缓存的数据块，之后另外一簇的另外一 CPU 读该数据块。试详细说明写操 作和读操作是如何进行的。写操作：该CPU查看缓存发现没有该数据块，它在本地发送请求查看邻近CPU的缓存中是 否有该数据块。如果有，执行缓冲区到缓冲区的传送，如果块状态为干净宿主所在簇的其他 拷贝置为无效。如果在本地查找失败，CPU发送体育馆到其宿主所在簇。如果块为未缓存, 标记为脏并发送给请求者；如果块为干净，所有拷贝置为无效，标记为脏并发送给请求者； 如果块为脏，请求传送到拥有该数据块拷贝的远程

2、簇，该簇将自己的拷贝置为无效并满足写 操作。读操作：另一 CPU查看自己缓存与本地簇其他CPU缓存发现无此数据块。该CPU发送请 求包给宿主所在簇，发现所需块的状态为脏，目录查找拥有该块的簇的标志。该簇响应请求。 并将该数据块发送给请求簇，将其状态改为干净，还要给宿主所在簇发回一个拷贝以更新存 储器，这时块的状态被置为干净。2 在基于总线的多处理机系统中，遵循 write once 协议，假设有 C1，C2，C3，C4 四个 CPU， 一操作序列如下：C1读一字W1 （只存在于共享存储器中）、C1继续读该字、C2读该字； C1修改该字、C3读该字、C4读该字。试详细说明以上操作序列是如何执行的

3、。C1查看缓存发现没有该字，从共享存储器中读取W1,同时缓存中也存储W1,状态为干净。 C1又一次读W1。查看自己缓存发现存在该字，从缓存中读取W1。C2读W1先在自己缓 存中查找发现没有缓存，从共享存储器读取 W1 并存储在缓存中，状态为干净。 C1 修改 W1将缓存中的该字修改，状态变为脏，同时C2监听到写请求，将自己缓存中的W1置为 无效。C3读该字，C1发现读请求发信号禁止存储器响应，C1向C3提供该字并将自己的项 置为无效， C3 发现该字来自其他缓存其状态置为脏，并将自己缓存项标记为脏。 C4 读该字， C3发现读请求禁止存储器响应，并向C4提供该字，并且将自己的项置为无效。C4发

4、现该 字来自其他缓存，其状态为脏，则标记自己缓存项为脏。3 在分布式系统，为了获得文件读写的效率，需要使用高速缓存，说明设置缓存的各种方法 及用途。并说明解决一致性问题的四种算法及各种算法存在的问题。在一个各自有主存和磁盘的客户一服务器系统中，有四个地方可用来存储文件或存储部 分文件:服务器磁盘，服务器主存，客户磁盘（如果可用的话）或客户主存。在服务器内存设 置缓存，可以减少I/O次数，而在客户端内存和磁盘中设置缓存，可以减少网络通信。1. 在服务器磁盘 在服务器磁盘上，有允足的空间，存放在那里的所有文件对所有客户都是可访问的。而且，由于每一个文件只有一份拷贝，所以不会产生一致性的问题.2.

5、在服务器主存 将最近使用的文件保留在服务器的主存中。客户读取一个刚好在服务器主存中的文件，可以消除磁盘传送，但网络传送仍然存在。在服务器主存中设置高速缓存：容易、对客户是 完全透明的。由于服务器可以保证其主存和磁盘拷贝同步。从客户的观点看，每个文件只有 一个拷贝，不会产生一致性问题。3. 在客户磁盘 客户磁盘保存数据多但速度慢。如果使用大量的数据，客户磁盘高速缓存可能更好些。4. 客户端高速缓存此时有三种可使用的选择来精确定义高速缓存的位置：a）、在每个用户进程自己的地址 空间直接进行文件高速缓存b）、在内核中C）、在一个单独的用户级高速缓存管理者进程 中，它保持了（微）内核独立于文件系统编码

6、，因此易十编程，并巨更加灵活.四种算法：1直接写算法：（WRITE-THRONG算法）当修改一个高速缓存项（文件或块）时， 新的值保存在高速缓存中并立即写到服务器；2 延迟写：延迟写操作使得语义变得不清楚当另一个进程读此文件时，它所得结果取决于 时间选择延迟写只好在运行效率和清晰的语义之间权衡3 关闭时写：仅当文件关闭后才将文件写到服务器，与对话语义相配；4 集中控制算法：a 当打开一个文件时，打开该文件的机器向服务器发送一条消息服务器保存谁打开了 哪个文件以及打开是为了读还是写或者两者兼有b 如果文件是为读而打开，允许其他进程为读而打开，避免为写而打开如果某个进程 为写而打开一个文件，必须禁

7、止所有其他访问C 当关闭文件时，必须报告，以便服务器更新d 缺点：不健壮，不能规模化存在的问题：（1）直接写：有效，但不影响写流量（2）延迟写：效率较高，但可能语义不清（3）关闭时写：与会话语义相配（4）集中控制：UNIX语义，但不健壮，不能规模化。4给出实现文件复制的三种方法，并举例说明更新复制文件的Gifford算法，并说明某些服 务器崩溃时，应该采取什么措施三种方法：1、显式复制：当进程产生一个文件时，可以在其他服务器上生成另外的拷贝如果目 录服务存在允许一个文件有多个拷贝，所有拷贝的网络地址都可以和这个文件名联系起来2、懒惰复制：只要在某个服务器上建立每个文件的一个拷贝，服务器自己在其

8、他的服 务器上也可自动生成副本3、使用组通信：所有的写系统调用同时传送到所有的服务器于是，其他的拷贝在原 文件产生时就产生了Gifford算法：即表决（vo ting）,其基本思想是在读或写一个拷贝文件之前要求中请并获得多个服务器的允许下面举一简单的例子来说明该算法是如何工作的：假设一个文件在N个服务器上都有拷贝。建立一个更新文件的规则:首先客户必须和超 过半数的服务器联系，并让它们同意它进行更新如果它们同意，就改变文件，并将一个新 的版本号和新文件联系起来该版本号用来标识该文件的版本，这对所有新近更新的文件都 是一样的当读一个已有拷贝的文件时，客户必须和超过半数的服务器联系，并请求它们发送与

9、该 文件相联系的版本号如果所有版本号相一致，则说明这是最新的版本，如果企图只更新剩 余服务器，会因为数目不足而失败例如，有5 个服务器，客户已确定它们中的三个有版本 号8，则其他两个的版本号不可能是9因为任何从版本号8到版本号9的成功更新需要三 个服务器同意，而不是两个Gifford的方案实际上比这更普通一些。在该方案中，读一个已有N个拷贝存在的文件 时，客户需要获得一个读法定数，它是任何Nr个或更多服务器的任一集合。同样，修改一 个文件需要一个至少Nw个服务器的写法定数Nr和Nw的值必须满足约束条件Nr+NwN。只 有在适当数目的服务器同意参与时，文件才能读或写文件假设最近的写法定数由从C到

10、L的10个服务器组成，所有这些服务器得到了新版本和 新版本号，任何随后的由3 个服务器组成的读法定数中将至少包含一个该集合中的成员。当 客户查看版本号时，它将知道哪一个是最新的并得到它。解决办法：虚像表决通过为每个已崩溃的服务器建立一个没有存储器的虚拟服务器解决 了服务器崩溃的问题。虚设者不允许出现在读法定数中，但它可以加入写法定数中。当一个 崩溃的服务器重新启动时，它必须获得一个读法定数来找到最新的版本。在它开始正常工作 之前，它将为自己拷贝一份该拷贝。5 试说明举例什么是有状态服务器，什么是无状态服务器，并对有状态和无状态服务器进 行详细的比较。无状态服务器：当客户发送一个请求到给服务器，

11、服务器完成请求，发送一个应答，然后从 内部表中移出关于该请求的所有信息。在请求之间，服务器不保存具体客户的信息。 有状态服务器：服务器保存两个请求之间的客户的状态信息。比较：无状态服务器的优点：容错、不需要OPEN/CLOSE调用、没有服务器表空间的浪费、没 有打开文件数目的限制、客户崩溃时不会造成服务器错误。有状态服务器的优点：请求消息比较短，减少网络带宽、更好的性能、可以预读，预先读信 息块减少延迟、易于幂等性（客户第二次发送相同请求时，可以不用再传输）、可以对文件 加锁。无状态服务器在本质上有更多的容错。不需要OPEN和CLOSE调用，这就减少了消息编 号，特别对于那些整个文件用一次就可

12、读出的普通情况，服务器不用浪费空间来存放表。使 用表时，如果太多的客户一次打开太多的文件，则将表填满，就不能打开新的文件。最后对 于状态服务器，如在文件打开时窗户出了故障，服务器就会牌困境中。如果它对此束手无策， 它的表最终将充满垃圾。如果它超时了还未打开文件，那么客户因两个请求之间等待时间太 长将被拒绝服务。有状态服务器由于READ和WRITE消息并不是必须包含文件名，所以它可以更短些，这 样就使用更小的网络带宽。由于关于打开文件的信息在文件关闭之前都可保存在主存储器 中，所以有较好的性能。由于大多数文件都是按顺序读的，可以预先读信息块减少延迟。6 在分布式系统中，可支持上载/下载文件模式或

13、远程访问模式，说明这两种模式并进行比 较。上载/下载模式：文件服务只提供两种主要的操作：读文件和写文件。读文件操作是将整个 文件以一个文件服务器传送到提出请求的客户；写操作是将整个文件从客户传送到服务器。优点：概念简单。使用这种模式不需要掌握复杂的文件接口，而且整个文件传送也是高 效的。缺点：客户端必具有足够大的存储空间来存储所需的所有文件。如果只需要文件的一小 部分，移动整个文件是很浪费的。远程访问模式：文件服务提供了大量的操作用于打开和关闭文件，读写文件的一部分，在文 件中来回移动，检查和改变文件属性等。优点：在客户端不需要很大的空间，当仅需要文件的一小部分时，不需要传送整个文件。7 分布

14、式协同一致算法的目标是使所有无故障处理机对待某些问题的意见达到一致，在 3 个正常处理机，2个出错处理机的情况下，用Lamport算法能否达成一致，给出算法的具 体步骤。假设：正常处理机为：ABC。错误处理机为：DE。1. 每个处理发送消息给其它处理机消息：A： 1 B： 2 C： 3 D： x1 y1 z1 m1 E： x2 y2 z2 m22. 把第一步声明的结果收集组成向量的形式A： (1, 2, 3, xl, x2)B： (1, 2, 3, yl, y2)C： (1, 2, 3, zl, z2)D： (1, 2, 3, 4, m2)E： (1, 2, 3, m1, 5)3. 每个处理现

15、将各自的向量传递给其它处理机。A：(1, 2, 3, y1, y2)(1, 2, 3, z1, z2)(1, 2, 3, 4, m2)(1, 2, 3, m1, 5)每个处理机检查所有接收向量的第i个元素。若某个值占多数，放入结果向量中，否则，标记为UNKNOWNA 会得出结论(1, 2, 3, UNKNOWN, UNKNOWN)其他处理机进行相同的操作ABC 得到一致的向量(1, 2, 3, UNKNOWN, UNKNOWN)8在实时分布式系统中，事件触发和时间触发系统的含义是什么，给出一个例子，并说明为 什么动态调度适合于事件触发系统，给出三种动态调度算法。事件触发系统：当一个重要的外部事

16、件触发时，它被传感器察觉到，并导致与传感器相连的 CPU得到一个中断请求。时间触发系统：每At毫秒产生一次时钟中断，在每一次时钟滴答时，对传感器进行采样， 并驱动执行机构。中断仅在时钟滴答时发生。例：考虑对一个100层楼的电梯控制器的设计。假定电梯在60层等客人。有人在一层按下 按钮。就在100毫秒后，另一人在100层上按下按钮。在事件触发系统中，第一次按钮产生 一个中断，使电梯启动下行，就在做出下行决定后，第二个按钮事件到来，因此第二个事件 被记录下来以作为将来的参考，但电梯还是下行。在时间触发系统中，它每500毫秒采样一 次，若两次按下按钮事件都在一次采样周期中出现，控制就必须做出决定。动

17、态调度是在运行期间检测到事件时进行调度，用事件触发系统可以在低负载更快的响应。 算法：1.比率单调算法2最早时限优先法3.最小余度法9主动复制容错的典型例子是三模冗余容错，说明某组成部件出错和某表决器出错时，是如 何容错的。如果在某一级上同时有两个表决器出错，其它所有部件和表决器均正常，能否 屏蔽错误，为什么？如果服务器采用主动复制的方法会存在什么问题，如何解决？ 每个设备复制三次，结果是每级电路都设置了三个表决器，每个表决器都有三个输入和一个 输出。若两个或三个输入相同，输出则等于该输入。若三个输入各不相同，输出就是不定值。1. 假设A2失效，V1 V2 V3都得到两个好的输入和一个坏的输入

18、，每个都输出正确值到第二级。2. A2 B3 Cl都出错,A出错VI V2 V3都输出正确值到第二级，同理B3出错V4 V5 V6 也都输出正确值到第三级。C1出错同理。这些影响都被屏蔽，输出结果仍正确不能。因为每一级只有三个表决器，如果有两个同时坏掉超过三分之二的要求，不能输出正 确结果。存在问题：所有请求到达所有服务器的顺序就相同。解决方法：1 对所有请求做全局计数编号。2 使用 Lamport 逻辑时钟。10 使用主机后备容错方法容错的主要思想是：在任何一个时刻都有一台服务器是主机，若 主机失效了，后备的服务器将承担其任务。试说明主机后备方法的工作原理及存在的问题 及解决办法。工作原理：

19、在任一时刻都有一台服务器是主机，它完成所有的工作。若这个主服务器失 效了，后备的服务器将承担其任务。1. 如果主机在执行任务前崩溃，则没有损失。客户端会超时重发直到连上后备机，任务只 被执行一次。解决方案：客户端只是在超时后，再次重新发送请求消息，直到发送一定次数后，或者 因得不到响应而停止发送请求消息，或者它的请求分别得到主服务器和备份服务器的处 理，并且只执行一次。2. 如果主机在执行任务后向后备机发送更新消息前崩溃，此时后备机接管，请求消息再次 到来，则任务被执行2次。解决方案：还没有有效的解决方案，一般来说，在主服务器崩溃后，只正确执行一次请 求消息的处理是非常困难的。3. 如果主机在

20、后备机执行任务后自己发送响应消息前崩溃，则任务共被执行三次。一次主 机完成，一次后备机完成，一次后备机接管时完成。如果请求消息带有序号，则可以减 少任务执行次数。解决方案：若每个请求消息都带有标志信息，那么请求消息只被执行两次。一般来说， 在主服务器崩溃后，只正确执行一次请求消息的处理是非常困难的。解决办法：是使用主机和备份机之间共享的两端口磁盘。在这种配置下，当主机得到一 个请求后，在做任何事之前先将请求写入磁盘，并且也把执行的结果写人磁盘，不再需要向 备份机发送消息并接收从备份机发来的消息了，若主机崩溃，备份机可通过读磁盘而得到整 个系统现在的状态。 11一个典型的集中的、启发式的处理机分

21、配算法，即上-下算法。说明该算法的目标，并说 明该算法的主要原理。 目标：让一个等了很久的，没有使用任何处理机的申请优先于已经占用了许多多处理机的申 请。此为该算法的目标即公平的分配系统资源。 主要原理：算法中有一个协调者，保存着一张使用情况的表，每个工作站在表中都有一个条 目，初值为 0。当有重要的时间发生时，将给协调者发信息以更新使用情况表。算法将根据 使用情况表决定处理机的分配。这些决定发生在调度事件发生时：有进程请求处理机、处理 机进入空闲状态或者是发生了时钟中断。使用情况表中的记录值可以为整数、零或是负数。 整数表示用户纯粹是在使用系统资源，负数表示用户需要系统资源，零则介于两者中间

22、。12在支持多线程的系统中，可采用三种模型来组织多线程，详细说明这三种模型。如果在 不支持多线程系统中实现文件服务，如何构造文件服务器。派遣者/工作者模型：某一个线程作为派遣者，它从系统邮箱内读出输入请求，然后检查请求，选择一个空闲 的工作者线程去处理它。然后派遣者唤醒睡眠的工作者。工作者被唤醒后，它检查共享块 缓冲区是否可以满足这个请求。如不能满足，给磁盘发送消息，要求所需的数据块。且进入 休眠状态等待磁盘操作的完成.团队模型：所有线程都是批平等的，每个都获得和处理自己的请求。没有派遣者。如果工作来了不 能处理，尤其是如果每个线程用来处理一种特殊的工作，可以维护一个队列，挂起的作业保 存在作

23、业队列中。线程在察看系统信箱前先察看作业队列。管道线模型：第一个线程产生一些数据传给下一个线程去处理。数据持续从一个线程传到另一个线程， 经过的每一个线程都进行处理。文件服务器在无多线程的情况下可以让它作为单线程执行。文件服务器的主循环是接收 一个请求并检查它，并且在下一个请求到来前完成它。当文件服务器等待磁盘操作时，它是 空闲的且不处理另一请求，如果文件服务器运行于一个专用的机器上，当文件服务器等待磁 盘时，CPU也是空闲的。13在机器0上进程0在等待机器0上进程1所拥有的资源，进程1在等待机器1上进程2 所拥有的资源，进程2在等待进程机器1上3, 4所拥有的资源，进程3在等待机器2上进 程

24、5所拥有的资源，机器2上的进程5在等待机器0上进程0所拥有的资源，画出简化的 资源图并说明用Chandy-Misra-Hass提出的分布式死锁检测算法如何检测死锁，并打破死 锁。检测死锁：当某个进程等待资源时，例如进程0等待进程1。此时，生成一个特殊的探测消 息并发送给占用资源的进程。消息由三个数字构成：阻塞的进程，发送消息的进程，接收消 息的进程，如由0到1的初始消息包含三元组(0,0,1)。接到消息后，接受者检查以确定它 自己是否也在等待其它进程。如果是，那么消息就要被更新，第一个字段保持不变，第二个 字段改为当前进程号，第三个字段改为等待的进程号。然后消息接着被发送到等待的进程。 如果在

25、等待多个进程，就需要发送多个不同的消息。不论资源时在本地还是在远程，该算法 都要继续下去。如果消息转了一圈后又回到了最初的发送者，那么就说明存在一个有死锁的 环路系统。打破死锁：1令最初发送探测消息的进程自杀。但是如果多个进程同时阻塞，同时发送探测 消息，那么每个进程都会发现死锁，并因此而自杀。2将每个进程的标识符添加到探测消息的末尾，将编号最大的进程中止或者发送消息请求它自杀。多个进程发现同一环路会选择同一个牺牲者。14在分布式系统事务提交操作可能需要不同机器上的多个进程的协作，举一个实际例子， 并说明实现原子性提交的两阶段提交协议的基本思想。基本思想：有一个进程作为协调者，通常是执行事务的

26、进程。在准备提交阶段，协调者向日 志中写入Prepare，然后向所有服务器发送准备提交消息。服务器接收消息后，检查自己是 否准备提交，如果是，就向日志中写入Ready，然后向协调者发送准备好消息。在提交阶段， 协调者接收所有响应后决定提交或终止。如果所有服务器都准备提交，则提交事务。如果有 一个服务器未准备好，则终止事务。无论结果如何，协调者都会写入日志，并发送决定消息。 服务器接到消息后，也将结果写入日志，并发送结束消息，完成整个过程。例子：航空订票系统。预订一张从A到D的机票。若选A作为协调者，在准备提交阶段， 协调者A向日志中写入Prepare，然后向服务器B、C、D发送准备提交消息。服

27、务器B、C、 D接收消息后，检查自己是否准备提交，如果是，就向日志中写入Ready，然后向协调者A 发送准备好消息。在提交阶段，协调者A接收所有响应后决定提交或终止。如果所有服务器 都准备提交，则提交事务，完成订票。如果有一个服务器未准备好，则终止事务。15说明基于时间戳的乐观并发控制算法的基本原理，并举例说明。基于时间戳的并发控制方法是指在一个事物开始做BEGIN_TRANSACTION的时候给它分配一 个时间戳。通过使用Lamport的算法，我们可以确保时间戳是唯一的。系统中的每个文件都 拥有一个相关的读取时间戳，以判断哪个已经提交的进程最近一次读取或写入过该文件。如 果事务都很短小而且在

28、时间间隔上比较大，那么一般来说当一个进程试图访问某个文件时， 该文件的读写时间戳将低于当前事务的时间戳。这种词性意味着事务正在以正确的顺序进行 处理，一切正常。当次序不正确时，就表明一个晚于当前事务开始的事务试图插入、访问文 件并提交。这种情况意味着当前事务开始的过早了，因此需要终止。用例F-来说明时间戳方法将会非匍同单 =假險有三T爭春仏卫村加os很导以刚帧卄賄延 行丁+井FL要僮用厲和”罄嘤的所宵玄件因此这些文件的圃百酎间魅榔将被设図成。的时间 載：PAJy同时幵Sfh 但炉的时间徹小于y当然会大于口的时同槪“甘先我们來寿垮弓文件朗情况一集-母它将分别调用自己的时何戡厂利将睾写人的宜件 的

29、读石时间槪5和几“籐非ye经勒束片提立否财砧和g郁应谏总a的时刚戰因此 也就小于厂我f门看到F比7心和卩叶都丸仃还未揚仝L因此写人是可接 爺的，呵以姿诚进荷。占提宏后.结果就将眉持丸的了E 0的时间戡记貳在文件屮已当筮试验 写的时I即戢口在由2丄g种创叩0不太建运a F囁谨取(只写人少立件井提我q那么眉事务就輻擞中 止。但魁它可以采用一亍新的时间fit生部重新幵始现在芮*看看渎取的情况口在图3-21(e)中稅野冲宠圉此读取操作可LI立即执行“隹 asi2wn中.展亍闯人祈进人井试闇与文科“由于冃人占的时阀戡小十戸的，閃此庐就芾要寻 特直到它握交随后H就可以虧取备丸阵縦绫执行了“在.刈釦S了乂件

30、井已提处a这 iKQ仍必瓢被中止住图321 g屮y正柱惨 改文理.尽席它还未撫握交，述尼奸始得太早仍必烦中止。读1 6举例说明RICART和AGRAWALE分布式互斥算法;假定A和B是相互独立的两个临 界区，进程0按A、B顺序进入，进程1按B、A顺序进入，R-A分布式互斥算法会导致死锁吗？说明理由。RICART和AGRAWALE算法要求系统中所有事件都是全序的，也就是说，对任何事件组消 息哪个先发生哪个后发生必须无歧义，算法如下：（1）当一个进程想进入临界区时，他要建立一个包括它要进入的临界区的名字、处理机号、 当前时间的消息，然后将消息发送给所有其他进程，也包括发送给自身。（2）当一个进程接

31、收到另一个进程消息时，它取决于接受方的状态以及临界区的命名，有 三种情况：1接受者不在临界区，也不想进入临界区，他就向发送者发送OK消息。2接受 者已经在临界区，它不必回答，而是负责对请求队列排队。 3 接收者要进入临界区，但是还 没有进入，它要负责将发来的消息和它发送给其他进程的时间戳对比，取小的那个。如果来 的消息时间戳小，接收者发送OK消息，否则接收者负责排列请求队列而不发送任何消息。（3）在发送完允许进入临界区的请求后，进程将不再做任何事，仅等待所有的允许消息， 一旦得到允许它就进入临界区。（4）它从临界区退出时向队列中所有进程发送OK消息，并将它从队列中删除。不会导致死锁。进程0、1

32、分别进入A、B临界区，假设进程0先在A中执行完后，退出A 临界区，并发送ok消息给所有的等待进程，之后申请临界区B，因为进程1此时在临界区B 中，所以进程1负责将进程0排在临界队列中，当进程1执行完后退出B，它将进程0的请 求从队列中取出，并向进程0发送0K,允许进程0进入临界区B,自己再去申请进入临界区 A.所以不会产生死锁。17 在分布式系统中，许多算法都需要一个进程充当协调者，因此需要协调者选举算法。试 说明欺负算法的主要思想，并说明在8个进程的情况下号码为 3的进程发现协调者崩溃后 的选举过程。欺负算法：当一个进程发现协调者不再响应请求时，它发起选举。进程 P 选举过程如 下： P 向

33、所有号码比它大的进程发送选举消息 若无人响应， P 获胜成为协调者。 若有号码比它大的进程响应，响应者接管， P 的工作完成。 假设8个进程为进程0到进程7，原协调者为进程7 进程3发现协调者崩溃，进程3主持选举，进程4进程5和进程6应答，通知进程3停止，进程4进程5进程6分别主持选举，进程6通知进程5和进程4停止，进程6获胜并 通知所有进程。18在分布式系统中获得互斥的方法之一是釆用集中式的算法，如果有四个进程P0, P 1， P2, P3, P0首先申请资源S,之后P 1, P2, P3随后申请资源S,试说明采用集中式的算 法是如何实现互斥的。首先选择一个进程为协调者。无论什么时候进程要进

34、入临界区，它向协调者发送请求消 息，说明它想进入哪个临界区并希望获得允许。如果当前该临界区内没有其他任何进程，协 调者就发出允许进入消息。如当P0请求资源S时，当应答到达时，P0就可以进入临界区。 此时若P1请求资源S,协调者知道该临界区已经有一个进程，所以不能同意P1的请求。此 时协调者可以发送“拒绝请求”应答，把进程2 的请求临时排在队列中。或者协调者回避应 答，这样就阻塞了进程2，使它等待应答。当进程P1从临界区退出时，它向协调者发送释放互斥消息的访问，此时协调者从推迟 请求队列中取出最前面的进程即P2，向它发送允许进入消息。如果该进程仍然阻塞，它不 被阻塞且进入临界区。如果明确发送一消

35、息拒绝它进入临界区，此进程应该查询输入的消息， 或者接着将它阻塞，不管怎么样，当它发现允许进入时，它还可以进入临界区。如果进程在 阻塞状态，它就会被唤醒进入临界区。19有三个进程分别运行在不同的机器上，每个机器都有自己的时钟并以不同且不变的速率 工作（进程1的时钟嘀嗒了 6下时，进程2的时钟嘀嗒了 8下，而进程3的时钟嘀嗒了 10 下），举例说明进程之间消息传递中违反先发生关系的情况，并说明如何用Lamport方法解 决。000681Q12rIS201824730243230丸36豳42151148占7 -60旳76S5进程E进程I 琲程2Lamport解决方案使用先发生关系，每条消息携带发送

36、者的时钟以指出其发送的时刻， 当消息到达时，接收者时钟若比消息发送时钟小，就立即将自己的时钟调到比发送时间大1 或更多的值。如上图，其中消息C从进程2到进程1是在60时刻离开，56时刻到达。同理，消息D 从进程1到进程0是在64时序离开，54时刻到达，这是绝对不可能出现的。Lamport的解决方案是：因为C在60时刻离开，只能在61时刻或更晚时刻到达，所以每条 消息都携带发送者的时钟以指出其发送的时刻，当消息到达时，接收者时钟若比消息发送时 钟小，就立即将自己的时钟调到比发送时间大1或更多的值。在b中，我们看到C现在到达 的时间是61，同样D到达的时间是70。20在很多分布式系统应用中，需要物

37、理时钟同步，举一个例子，并说明物理时钟同步的三 种算法，Cristian算法、Berkeley算法及平均值算法。例子：导弹发射，不同的控制站必须同步时钟，否则无法准确的控制导弹的发送时间及 导弹运行轨道。Cristian 算法：适合于只有一台机器上有颐接收器（时间服务器）,苴它所有机器与 它同步的系统发送机器时间服务器 TO和T1都是由相同时钟测量的每台机器以小于或等于5/2P秒的周期定期地向时间服务器发送消息询问当前的时间, 时间服务器接到消息后就尽快回答含有当前时间CUT值的消息。Berkeley 算法：时间守护进程（时间服务器）定期地询问每台机器的时间。然后基于这些回答计算出平 均值并告

38、诉所有的机器将它们的时钟拨快或拨慢到一个新的值。（适合于没有WWV接收器的 系统）平均值算法：将时间分成固定长度的再同步间隔，第i次间隔开始于T+iR,结束于T+（i+l）R .T0 是过去某一约定的时间，R是一个系统参数。在每次间隔开始处，每台机器根据自己的时钟 广播发送当前的时间。 在机器广播发送时间之后，它启动本地计时器收集在S时间间隔 中到达的其他广播。当所有广播到达后，执行一个算法，得到新的时间值。这个算法可以是 求这些值得平均值，或者是去掉m个最大值和m个最小值，平均其余值。21组通信系统中，原子性的含义是什么，举例说明为什么要保证原子性。在保证原子性的 同时还要保证消息顺序，举例

39、说明保证消息顺序的必要性。原子性：当条消息发送给一个组后，不是该组所有成员都正确收到，就是均未收到。不允许 出现组内有些成员收到而有些成员收不到的情况。即要么全有要么全无。例：在一个复制的分布式数据库系统中，假设有一个进程给所有的数据库机器发送一个消息 创建一个新记录，接着又发送一条消息去修改该记录如果有些组成员未接收到建设记录的消 息，它们就无法执行修改操作，这样数据库也将变得不一致。如果系统能够保证将每条消息 发送到该组的所有成员，该过程就比较简单。如果不能保证，该消息就不发给组中的任何一 个成员，并将失败报告给发送者以作适当的恢复处理。保证消息顺序： 个例rr d从图中我们可以看出:进程

40、1首先收到了来自进程0的消息，然后收到了来自进程4的消息。 进程3开始没有收到消息，继而收到了进程4和进程0的消息。这样进程4和进程0的两条 消息以不同的顺序到达了进程1和进程3。如果进程0和进程4都想去改变数据库中的同一 个值，那么进程1和进程3执行的最终结果是不相同的。不用说这与组内部分成员收到消息 而部分成员未收到消息的情形是一样糟糕的。因此为了使得编程更加的合理，系统必须很好 的定义一种关于消息传递顺序的语义。22说明RPC的主要步骤，在形式说明书中输入参数、输出参数、输入输出参数的含义是 什么，为什么要这样规定。如果服务器是无状态的，为什么读一个文件的过程需要给出 position

41、参数。RPC的主要步骤：（1）客户过程以普通方式调用相应的客户存根。（2）客户存根建立消息并激活内核陷阱。（3）内核将消息发送到远程内核。（4）远程内核将消息送到服务器存根。（5）服务器存根取出消息中的参数后调用服务器的过程。（6）服务器完成工作后将结果返回至服务器存根。（7）服务器存根将它打包并激动内核陷阱。（8）远程内核将消息发送至客户内核。（9）客户内核将消息交给客户存根。（10）客户存根从消息中取出结果返回给客户。X Include cation of f.i e server. version , 1:丄long read (in char name MAXPATHl Ho ut c

42、har buf BUFSTZEJ,in long byres,:. n long position;long writetin char name MftX_PArH , ir char buf BJJE_SIZE,in long tiytesj in long posi ：.ion); l:iL cieate (rn char KAK_PATH ,in in: mode);Lnt delete (in ct:ar I4AX_pathj)；end;12-20对图2占无狀态服务蛊的形武说期书每一过程都给出了参数类型。每个参数都被指明为输入参数、输出参数、或者输入/输 出参数。一个输入参数，文件名

43、name，是从客户进程传递给服务器进程的，它告诉服务器 进程对哪个文件进行读、写、创建、删除等操作。参数bytes告诉服务器进程有多少个字节 要传送。参数position指明了文件从何处开始读写。输出参数，如read中的buf用作服务器 进程传递消息给客户进程的。buf是文件服务器存放客户所需数据的地方。输入/输出参数从 客户进程传递给服务器进程，经服务器进程修改后返回给客户进程。因为服务器是无状态的，所以服务器不保存客户的信息，所以就需要position参数来指 明文件从何处开始读写。23说明RPC的主要思想。在客户发出请求后，客户机正常，但未收到应答，应该是那些原 因造成的。并说明在服务器

44、崩溃的情况下，可采用哪些方法处理。主要思想：允许程度去调用位于其他机器上的过程。当位于机器A的一个进行调用机器B 上的某个过程时，机器A上的该进程被扶起，被调用的过程在机器B上执行。调用者将消 息放在参数表中传送给被调用者，结果作为过程的返回值给调用者。原因：客户无法定位服务器。客户发送给服务器的请求消息丢失服务器发送给客户的 应答消息丢失服务器在收到请求后崩溃客户机在发送请求后崩溃。服务器崩溃的处理方案：1、等待服务器重新启动，然后重发请求。该方法要求不断重试直 至应答应答消息来到并传给客户。这种技术称为至少语义，它保证RPC至少执行一次，但也 有可能执行多次。2、立即放弃并报告失败。它是最

45、多一次语义，确保了RPC最多执行一次， 但可能没有执行。3、不作任何保证。当服务器崩溃时，客户得不到任何帮助和保证。RPC 可以不被执行或执行相当多次。这种方法的最大优点就是易于实现。24说明客户/服务器模式的主要思想，并说明在采用了阻塞的、有缓存的、可靠的发送和接 收原语的情况下，系统是如何工作的。主要思想：构造一种操作系统，它由一组协同进程组成，这组进程称作服务器。为用户提供 服务的进程称作客户，客户和服务器都运行在相同的微内核中。进程调用send原语，它指定了目的地以及发送到该目的地的缓冲区数据。消息被发送 时，发送的进程被阻塞。直到消息传送完毕，其后的指令才能继续执行。之后对接收信息感

46、 兴趣的进程可以让内核为之建立一个邮箱，并指定一个地址以便于寻找网络信包。所有具有 该地址的输入消息被放入邮箱中，调用receive时只要从邮箱中取出一条消息，邮箱为空时 阻塞。可靠的原语有三种：重新定义非可靠原语。要求接收机器的内核给发送机器的内 核发送一个确认消息。只有当收到这个确认消息后，发送内核释放用户进程。客户机在发 送消息阻塞后，服务器的内核不发送确认消息，而是将应答作为确认消息。25客户为了发送消息给服务器，它必须知道服务器的地址，给出三种寻址机制的基本原理， 并说明三种机制存在的问题。1机器、进程编址方式：带有机器号和进程号，机器号用于使内核将消息正确地发送到适当 的机器上；进

47、程号用来使内核决定消息要给哪一个进程。缺点：不透明；2带有广播的进程编址：进程在相当大且专用的地址空间中选择自己的标识号，发送者广播 一个特殊的定位包，包含目的进程的地址，所有内核检查并察看地址是不是它们的。缺点：给系统造成额外负担。3通过名字服务器进行地址查询:在客户机中存放ASCII服务器的名字，每次客户机运行时， 首先试图使用服务器，客户机发出一请求消息给一个特殊映射服务器，问一个目前服务器所 在的机器号，有了这个地址后，可以直接发送请求。缺点：需一个中间部件：26在实现客户机-服务器协议时，需要哪些基本类型的包，说明每种包的源、目的地以及作 用，并说明下图的含义。包:包类型源地址目的地

48、址作用请求REQ客户服务器客户请求服务器提供服务应答REP服务器客户服务器对客户应答确认ACK客户、服务器其他确认正确接受前面的包你在这里吗AYA客户服务器查看服务器是否崩溃我在这里IAA服务器客户服务器没有崩溃再试一次TA服务器客户服务器没有空间地址未知AV服务器客户没有进程在使用此地址图的含义：客户向服务器发送请求信息，服务器确认正确接受到请求信息，客户再次确认服 务器是否崩溃，服务器回答没有崩溃，服务器对客户请求应答，客户确认收到应答。27分布式系统的目标是给用户一种错觉，就像使用单一计算机一样，这需要透明性支持， 说明分布式系统支持的各种类型的透明性。位置透明是用户不知道资源位于何处，

49、在一个真正的分布式系统中，用户不知道硬、软 件资源如CPU、打印机、文件和数据库的位置。资源的名字不应含有资源的位置信息。迁移透明是指资源无须更名就可自由地从一地迁向另一地。复制透明，系统就可以随意地为文件和其他资源进行附加拷贝而无须用户知道。并发透明，多个用户可以自动的共享资源，当两个用户试图同时更新相同的文件时，任 一用户不会发现其他用户的存在。并行透明，系统活动可以在用户没有感觉的情况下并行发生。从理论上说，一个分布式 系统在用户面前的表现就像一个传统的但处理机时分系统。系统活动可以再用户没有感觉的 情况下并行发生。28详细分析影响分布式系统规模（Size）可伸缩性的三个因素，即集中式的

50、服务、数据和 算法。试举例说明分布和复制技术是如何提高可伸缩性的。许多服务是以集中的方式实现的，它们由分布式系统中一台特定的计算机上运行的单个 服务器来提供。这种方案的问题是：用户增多时该服务器将成为系统的瓶颈。即使它拥有无 限的处理能力和存储能力，在系统达到一定规模后与该服务器的通信也将发生困难，从而使 得系统规模无法继续增长。集中式数据：如果要保存5000 万人的电话号码和地址，假设每条数据记录占50 个字条， 一个 2.5GB 的硬盘就可以提供足够的存储空间。如果只用一个数据库，无疑会使得这个数 据库的进出通信线路中都充满了数据。集中式算法：在大型分布式系统中，海量的信息必须在许多线路之

51、间进行跌幅传送。收 集并传送所有的输入和输出信息的做法本身就有弊端，因为这些消息会造成部分网络过载。 29 在分布式操作系统中，说明单内核的含义，并说明为什么采用微内核技术，通常微内核 提供应提供哪些服务？ 单内核：每台机器都运行一个传统的内核，内核自身提供了大多数的服务。 微内核：内核尽可能少的提供服务，大量的操作系统服务可从用户级服务器上获得。微内 核具有更好的灵活性。提供的服务：1.进程间通信机制 2.某些内存管理功能 3.少量的低层进程管理和调度 4. 低 层输入/输出服务。30 解决可伸缩性的技术包括隐藏通信延迟、分布和复制，试举例说明分布和复制技术是如 何解决可伸缩性的。隐藏通信延

52、迟：尽量避免等待远程服务对请求的响应。例如，当对远程计算机的某个服务发 出请求时，在发出请求端，除了等待服务器响应之外，还可以利用这段时间做其他工作。 分布：分布技术把某个组件分割成多个部件，然后再将它们分散到系统中去。例子：因特网 DNS 名字空间是由域组成的分层树状结构，域又划分为互不重叠的区。每个区内的名字都 由单个域名服务器处理。在不涉及太多细节的情况下，可以把每个路径名想象成因特网上的 主机名，与该主机的网络地址相关。31 在分布式系统中，软件体系结构是一个非常重要的概念，涉及如何组织软件成分及如何 交互等，详细说明四种Architectural Style。1. 分层体系结构：组件

53、组成了不同的层，其中L层中的组件可以调用下面的L。ii-12. 基于对象的体系结构：是一种很松散的组织结构。每个对象都对应一个组件，这些组件 是通过过程调用机制来连接的。3. 以数据为中心的体系结构：从这种思想发展而来：进程通信需要通过一个公用仓库。4. 基于事件的体系结构：进程基本上是通过事件的传播来通信的，事件传播还可以有选择 地携带数据。32客户机服务器应用可以将软件成分分为三层，说明每一层的作用，并说明Internet搜索 引擎是如何按三层结构组织软件成分的。（1）用户接口层：用户接口层含有直接与用户交互所需的一切。（2）处理层：处理层通常包含有应用程序。（3）数据层：数据层管理要使用

54、的实际数据。用户输入关键字字符串，然后显示出Web网页的列表。后端是由一个巨大的Web网页 数据库组成，这些 Web 网页是预取的，且已加索引。搜索引擎的核心是把用户的关键字字 符串转换成HTML页面列表。在客户-服务器模型中，这种信息检索部分往往放在处理层。33 P2P是典型的非集中式体系结构，说明在结构化P2P系统中如何组织节点和数据，如何 查找数据，如何进行成员管理。在结构化的点对点体系结构中，覆盖网络是用一个确定性的过程来构成的。这个使用最 多的进程是通过一个分布式哈希表来组织进程的。在基于DHT的系统中，从一个大的标识 符空间中选取一个随机关键值赋给该数据项。同样从这个标识符空间中选

55、取一个随机数赋给 该系统中的结点。根据某种距离尺度把数据项的关键值唯一地映射给结点的标识符。当查找 数据项时，会返回对应数据项的结点的网络地址。这可以通过把数据项的请求跌幅给相应的 结点来完成。如果某个结点要加入该系统，它首先生成一个随机标识符id。然后，结点就可以进行一 个对id的查找，返回网络地址succ（id）。此时，所加入的结点只需与succ（id）及其前继者联 系，并把自己插入到该环中即可。结点离开是结点 id 告知其前继者它要离开，并把其数据 项转移给 succ（id）。34 BitTorrent 系统采用了集中与分布相结合的体系结构，说明 BitTorrent 系统的主要构成 成

56、分，并说明其工作原理。构成成分：Web服务器，文件服务器，跟踪器，结点。 基本思想是：当一个终端用户要查找某个文件时，他可以从其他用户那里下载文件块，直到 所下载的文件块能够组装成完整的文件为止。一个重要的设计目标是确保协作性。35 说明虚拟化的含义，为了实现虚拟化，计算机系统通常提供四种类型的接口，说明这四 种接口，并说明两种实现方式。虚拟化就是只有单个处理器但感觉有多个处理器机制可以扩展到其他资源。 四种类型的接口：（1）由机器指令组成，可由任何程序激起的硬件软件界面。（2）由机器指令组成，只有特权程序才可激活的硬件软件界面。（3）由操作系统提供的系统调用组成的界面。（4）由库调用组成的界

57、面，通常形成了所谓的应用程序编程接口。 实现方式：第一， 可以构建一个运行时系统，实质上提供一套抽象指令集来执行程序。 第二， 提供一种系统，把它做成一层完全屏蔽硬件但提供一个同样指令集的界面。36 在分布式系统中，为什么需要 代码迁移？代码迁移可以分为 Sender-initiated 和 Receiver-initiated,解释其中的含义，并举例说明。如果把进程由负载较重的机器上转移到负载较轻的机器上去，就可以提升系统的整体性 能。Sender-initiated 是在发送者启动的迁移，代码当前驻留在哪台机器上或者正在哪台机器 上执行，就由该机器来启动迁移。通过因特网向Web数据库服务器

58、发送搜索程序以在该服 务器上进行查询就是发送者启动迁移的一个例子。Receiver-initiated是在接收者启动的迁移，代码迁移的主动权掌握在目标机器手中。Java 小程序就是接收者启动的一个例子。37为了支持大规模网络中的移动实体可以采用Home-Based方法，说明其工作原理，并说 明存在的问题及可能的解决办法。每个移动主机都使用一个固定的IP地址，所有与该IP地址进行的通信一开始都被转发 到移动主机的宿主代理中。宿主代理位于局域网中，与包含在移动主机IP地址中的网络地 址相对应。当一台移动主机转移到另一个网络中时，它会请求一个可以用来通信的临时地址。 这种转交地址要在宿主代理中注册。

59、当宿主代理接收到发给移动主机的数据包时，它会查找 主机的当前位置。如果主机是在当前本地网络中，那么就只需转发数据包。否则，它会建立 一条通往主机当前位置的通道，也就是说，它会把数据组装成IP包，然后发送给转交地址。 同时，将把主机的当前位置告诉数据包的发送者。存在的问题： 1.为了与移动实体通信，客户首先必须与宿主位置进行联系，而宿主位置可能 与实体本身牌完全不同的位置，结果是增加了通信延迟。2.它使用固定的宿主位置，必须保证宿主位置始终存在。 解决方法：在传统的命名服务中注册宿主位置，然后让客户首先查找宿主位置所在的位置。由于可以假定宿主位置是相对稳定的，所以在查找到它以后可以有效地缓存它。

60、38在DHT-based系统中可以采用finger table提高査找效率，说明其工作原理，并举例说 明。原理：如果用FTp表示结点p的指状表，那么有FT i=succ(p+2i-i)第i个实体指向p后2i-i的第一个结点。要键值k,结点p立即把该请求转发给在p的 指状表中索引为j的结点q,其中：q=FTpjWkvFTpj+l例：我们从结点1解析k=26。首先，结点1在其指状表中查找k=26,发现该值大于FT15, 表示该请求将转发给结点18( = FT5),而结点18将选择结点20,因为FT182kFT183o 最后，该请求从结点20转发给结点21,从结点21又转发给结点28,该结点负责k=26。此 时，结点28的地址返回给结点1,于是就完成了该键值的分析。一个查找通常需要O(log(N) 步，其中N为系统中的结点数。