（1）27分布式系统的目标是给用户一种错觉，就像使用单一计算机一样，这需要透明性支持，说明分布式系统支持的各种类型的透明性。

1. 位置透明：用户不知道硬，软件资源的位置。资源的名字不应隐含有资源的位置信息
2. 迁移透明：资源无须更名就可以自由地从一地迁向另一地。
3. 复制透明：操作系统可以随意地为文件和其他资源进行附加拷贝而无须用户知道。
4. 并发透明：用户不会感觉其他用户存在。
5. 访问透明：隐藏了数据表示和获取资源的具体实现
6. 重定位透明：用户不必知道资源的位置是否改变
7. 故障透明：用户不必知道系统出现错误

（2）21组通信系统中，原子性的含义是什么，举例说明为什么要保证原子性。在保证原子性的同时还要保证消息顺序，举例说明保证消息顺序的必要性。Ｐ93

• 原子性含义：当一条消息发送给一个组后，不是该组的所有成员都正确收到，就是均为收到，不允许出现组内有些成员收到而有些成员收不到的情况。具有要么全有要么全无的传递叫做原子性或原子广播。

• 例：在一个复制的分布式数据库系统中，假设有一个进程给所有的数据库机器发送一条消息创建一个新记录，接着又发送一条消息区修改该记录，如果有些组成员未收到创建记录的消息，那么它们就无法执行修改操作，这样数据库也变得__不一致__。

• 例：如果消息都想改变数据库中的同一数值，则最终的结果和到达的顺序有关

####（2）22 说明RPC的主要步骤，在形式说明书中输入参数、输出参数、输入、输出参数的含义是什么，为什么要这样规定。如果服务器是无状态的，为什么读一个文件的过程需要给出position参数。P72

• RPC步骤：
  • 客户过程以普通方式调用相应的客户存根
  • 客户存根建立消息并激活内核陷阱
  • 内核将消息发送到远程内核
  • 远程内核将消息送到服务器存根
  • 服务器存根取出消息中的参数后调用服务器的过程
  • 服务器完成工作后将结果返回至服务器存根
  • 服务器存根将它打包并激活内核陷阱
  • 远程内核将消息发送至客户内核
  • 客户内核将消息交给客户存根
  • 客户存根从消息中取出结果返回给客户

• 形式说明书： 作为服务器，如果客户端传来的是输入参数，那么服务器就不必将这个数据传给客户端，减少了拷贝次数。如果是输出参数，那么客户端也不必拷贝数据到服务器。提高效率。输入／输出参数是从客户进程传递给服务进程经服务器修改后返回给客户进程。

• position参数： position指明了文件从何处开始读写
  • 支持文件的断点续传
  • 减少网络传输负载

####（2）23说明RPC的主要思想。在客户发出请求后，客户机正常，但未收到应答，应该是那些原因造成的。并说明在服务器崩溃的情况下，可采用哪些方法处理。P75

• RPC主要思想：使远程的过程调用看上去就像在本地的过程调用一样。即 ＲＰＣ透明性——调用者不应意识到此调用的过程时在其他机器上执行的，反之亦然。

• 原因：
  • 客户无法定位服务器
  • 客户发给服务器的请求消息丢失
  • 服务器发给客户的应答消息丢失
  • 服务器在受到请求后崩溃
• 由于服务器崩溃客户无法区分执行前执行后崩溃 三种方法：
  1. 第一种方法是等待服务器重启（或与另一个新服务器捆绑），然后重发请求。这种方法要求不断重试直至应答消息到来并传给客户。这种技术称作至少一次语义，它保证ＲＰＣ至少要执行一次，但也有可能执行多次。
  2. 第二种方法是立即放弃并报告失败。这是最多一次语义，它确保了ＲＰＣ最多执行一次，但可能没有执行。
  3. 第三种方法不做任何保证。当服务器崩溃时，客户得不到任何帮助和保证，ＲＰＣ可以不被执行或执行相当多次。这种方法最大的优点就是容易实现。
  4. 第四种精确一次语义。这种方法很难实现，客户无法直到具体位置，恢复很难实现。

####（2）24说明客户/服务器模式的主要思想，并说明在采用了阻塞的、有缓存的、可靠的发送和接收原语的情况下，系统是如何工作的。P52

• 主要思想： 构造一种操作系统，它由一组协同进程组成，这组进程称作服务器。为用户提供服务的进程称作客户，客户和服务器都运行在相同的微内核中。为了避免面向连接的协议加报文头，用户服务器模式常常以简单的面向非连接的请求/应答协议为基础。客户向服务器发出一个请求消息请求一些服务，服务器完成后返回所要的数据或者给出一个错误代码，指出工作未完成。

• 工作：当一个进程调用send原语，它指定了目的地以及发送到该目的地的缓冲数据。消息被传送时，发送的进程被阻塞（挂起）。直到消息传送完毕，其后的指令才能继续执行。如果客户端正在执行receive进程，则消息通过内核直接传送给receive进程地址，如果未执行，则传送到对应进程的内核邮箱进行缓存，等待receive进程的接收。服务器接收到客户端的消息，由内核发送ack确认消息通知客户端消息收到，同理客户端对消息进行处理，然后调用send原语进行消息的发送，发送时进程也被阻塞，客户端的接收端receive如果运行中则消息直接传入rece进程地址，如果挂起则传入客户端内核对应进程的邮箱进行缓存。如果receive进程确实接受到客户端的消息，则由内核发送ack进行确认。

####（2）25 客户为了发送消息给服务器，它必须知道服务器的地址，给出三种寻址机制的基本原理，并说明三种机制存在的问题。

• 三种寻址方式：
  1. 机器，进程编制方式：机器号和进程号。机器号用于内核将消息正确的发送到适当的机器上，进程号用来使内核决定消息发送到哪个进程。
  2. 带有广播的进程编址：发送者广播一个特殊的定位包，包含目的地地址的进程，网络上所有机器均可以收到，所有内核查看地址是不是自己的，如果是，则发送’我在这里‘给出网络地址（机器号），发送内核使用这个地址并记住他。
  3. 通过名字进行寻址：用一台机器提供高层的机器名和机器的地址映射来避免广播网络的额外负担，进程像服务器一样，用ASCII字符串指出，并且这些字符串可以嵌入程序中，不用二进制进程号和机器号。每次机器运行的时候，首先试图使用服务器，客户机发出一请求消息给一个特殊映射服务器，通常叫做名字服务器，问一个目前服务器所在的机器号，有了这个地址后可以直接发送请求。
• 问题：
  1. 不透明（机器，进程号）
  2. 系统负担大
  3. 需要中间件——名字服务器

####（2）26在实现客户机-服务器协议时，需要哪些基本类型的包，说明每种包的源、目的地以及作用，并说明下图的含义。P63

• 客户机　服务器协议：

代码 | 包类型 | 来源 | 目的 | 作用 :— | :— | :— | :— | :— REQ | 请求 | 客户 | 服务器 | 客户要求服务 REP | 应答 | 服务器 | 客户 | 服务器对客户的应答 ACK | 确认 | 服务器，客户 | 其他 | 前面的包已经到达 AYA | 你在这里吗? | 客户 | 服务器 | 查看服务器是否崩溃 IAA | 我在这里 | 服务器 | 客户 | 服务器没有崩溃 TA | 再试一次？ | 服务器 | 客户 | 服务器没有空间 AU | 地址未知 | 服务器 | 客户 | 没有进程在使用此地址

• 含义：
  1. 客户机发送REQ请求，要求服务，服务器发ACK送确认。
  2. 客户机发送AYA查看服务器是否崩溃，服务器IAA确认没有崩溃，对客户进行应答REP。
  3. 客户端发送确认消息ACK。

####（3）13 在机器0上进程0在等待机器0上进程1所拥有的资源，进程1在等待机器1上进程2所拥有的资源，进程2在等待进程机器1上3，4所拥有的资源，进程3在等待机器2上进程5所拥有的资源，机器2上的进程5在等待机器0上进程0所拥有的资源，画出简化的资源图并说明用Chandy-Misra-Hass提出的分布式死锁检测算法如何检测死锁，并打破死锁。P134

• 因为消息转了一圈又回到最初的发送者，检测到死锁。
• 两种方法：
  1. 令最初发送探测消息的进程自杀。但是如果多个进程同时阻塞，同时发送探测消息，那么每个进程都会发现死锁，并因此而自杀。
  2. 将每个进程的标识符添加到探测消息的末尾，将编号最大的进程中止或者发送消息请求它自杀。多个进程发现同一环路会选择同一个牺牲者。

####（3）14在分布式系统事务提交操作可能需要不同机器上的多个进程的协作，举一个实际例子，并说明实现原子性提交的两阶段提交协议的基本思想ｐ128

• 例子：并行计算，需要各机器协同操作。

• 基本思想：执行事务的进程起协调者作用，提交协议开始时协调者先写入一条日志条目以表明它要开始提交协议，然后它给每个进程（下属）发送一条消息通知他们为提交做好准备。 当一个下属收到消息后，它先进行检查以确认是否为提交做好准备，然后将它的决定发回给协调者。当协调者收到了所有的响应后，它就直到是否可以提交或中止。如果所有的进程都准备提交，那么事务就可以提交了。如果一个或者几个进程不能提交，那么事务就得中止。无论时哪一种，协调者都要写入一条日志记录并给每个下属发送一条消息以便将决定通知他们。正是因为写入的日志才使得事务真正被提交，并且无论发生什么它都会继续下去。

（3）15说明基于时间戳的乐观并发控制算法的基本原理，并举例说明。 P130

• 基本原理： 所谓的乐观的并发控制，其核心思想为：尽管放心的去做你想做的，不用在意其他人正在做什么。如果有问题出现，那么以后再考虑。在实际情况中，冲突相对来说非常少，所以这个策略大部分时间都可以正常工作；而基于时间戳的并发控制方法是指在一个事物开始做BEGIN_TRANSACTION的时候给它分配一个时间戳。通过使用Lamport的算法，我们可以确保时间戳是唯一的， 系统中每个文件都拥有一个相关的读取时间戳和写入时间戳，以判断哪个已提交的进程最近一次读取或写入过该文件。如果事务都很短小而且在时间间隔上比较大，那么一般来说当一个进程试图访问某个文件时，该文件的读写时间戳将低于当前事务的时间戳。这种次序意味着事务正在以正确的顺序进行处理，一切正常。 当次序不正确的时候，就表明一个晚于当前事务开始的事务试图插入，访问文件并提交。这种情况意味着当前事务开始得过早了，因此需要中止。

####（3）16举例说明RICART和AGRAWALE分布式互斥算法；假定A和B是相互独立的两个临界区，进程0按A、B顺序进入，进程1按B、A顺序进入，R-A分布式互斥算法会导致死锁吗？说明理由。P114

• R-A算法： 当一个进程想进入临界区时，它要建立一个包括它要进入的临界区的名字，处理机号和当前时间的消息，然后将消息发送给所有其他进程。概念上讲也包括它自身，发送的消息假设是可靠的，也就是，每条消息都应该被确认。如可能应该使用可靠的组通信，避免使用单个消息通信。 当一个进程接收另一个进程请求消息时，它取决于接收方的状态以及临界区的命名，由三种状况要加以区别： １若接收者不再临界区，也不想进入临界区，它就像发送者发送ＯＫ消息 ２若接收者已经在临界区，它就不必回答，而是负责对请求队列排队； ３若接收者要进入临界区，但还是没有进入时，它要将发来的消息和它发送给其余进程的时间戳对比，取小的那个。如果发来的时间戳小，则发送OK消息。如果接收者更小，则接受者负责排列请求队列，而不发送任何消息。 在发送完允许进入临界区的请求后，进程将不做任何事，仅等待所有的允许消息，一旦得到允许，它就进入临界区。它从临界区退出时，向队列中的所有进程发送ＯＫ消息，并将它从队列中删除。

• 不会，如果进程０的时间戳小于进程１的时间戳，则进程１将会发送OK，进程０则会将进程１加入请求队列。

####（3）17在分布式系统中，许多算法都需要一个进程充当协调者，因此需要协调者选举算法。试说明欺负算法的主要思想，并说明在8个进程的情况下号码为3的进程发现协调者崩溃后的选举过程。P118

• 主要思想：当一个进程发现协调者不再相应请求时，它就发起选举。在某一时刻，一个进程只能从号码比它小的进程那里得到一个选举消息，当它到达时，接收者就发送回ＯＫ消息，表明它的存在并接管，然后接收者主持选举。出了一个进程外的其余进程都得放弃，这一个进程就是新的协调者，它将选举获胜的消息发送给所有进程，告之它时新的协调者。 若一个进程刚刚崩溃过，而又得到恢复，它主持选举，若它刚好时当前运行进程中号码最大的，它就会获得选举胜利，从而接管协调者的工作，所以最大的进程总能获胜，故而将该算法命名为欺负算法。

• 过程：一组由１～８号共八个进程组成，开始８号进程是协调者，它突然崩溃。３号进程发现协调者崩溃，所以它向所有比它进程号大的进程，即4，5，6，7，8发送选举消息，进程4，5，6，７接收消息后发送回ＯＫ消息，３号进程接收到第一个应答时就知道自己的工作结束了。进程４，5，6，7都主持选举，每个进程仅把消息发送给比自己进程号大的进程，所以进程４发送给５，6，7，而５，6，7分别返回ＯＫ消息给进程４，同理５，6进程也会得到比它程序号大的进程的ＯＫ消息，最后进程７已经直到进程８已经崩溃，而且它将是胜利者。如果从磁盘或其他地方无法得到一些信息表明原 来的协调者在哪里失败了，进程７则要做这部分工作。当它准备接管时，进程７向所有运行进程发送COORDINATOR协调者消息，进程3接收到这条消息后，发现进程８已经死了，进程７时新的协调者，进程４就可以继续它刚才所尝试进行的工作，这样，进程８的失效得到了处理，而且工作又得到了继续。如果进程８重新启动，它就会向所有的进程发送协调者消息，使他们收到欺负。

####（3）18在分布式系统中获得互斥的方法之一是采用集中式的算法，如果有四个进程P0，P 1，P2，P3，P0首先申请资源S，之后P1，P2，P3随后申请资源S，试说明采用集中式的算法是如何实现互斥的。P112

• 集中式算法：选一个进程为协调者，无论什么时候进程进入临界区，它将向协调者发送请求消息，说明它想进入哪个临界区并希望获得允许，如果该临界区内没有其他任何程序，协调者就发送允许进入消息，当应答到达时，请求着就可以进入临界区。

• p0首先申请资源S，资源S没有被占用，P0进入临界区，P1 P2 P3向协调者申请进入临界区，因为临界区被占用，协调者发送“拒绝请求”，把３个进程临时排在等待的队列中，当进程P0从临界区退出时，它向协调者发送释放互斥消息访问，协调者从推迟请求队列中取出最前面的进程，向它发送允许进入消息。如果该进程仍然阻塞（即这是第一条发给它的允许消息）它不被阻塞且进入临界区。其后同理。

####（3）19有三个进程分别运行在不同的机器上，每个机器都有自己的时钟并以不同且不变的速率工作（进程1的时钟嘀嗒了6下时，进程2的时钟嘀嗒了8下，而进程3的时钟嘀嗒了10下），举例说明进程之间消息传递中违反先发生关系的情况，并说明如何用Lamport方法解决。P104

• lamport算法：
  1. 若在同一进程中ａ发生在ｂ之前，则C(a) < C(b);
  2. 若ａ和ｂ分别代表发送消息和接收消息，则C(a) < C(b);
  3. 对所有时间ａ和ｂ，C(a) 不等于C(b)
• Lamport的解决方案是直接使用先发生关系，因为C在60时刻离开，只能在61时刻或更晚时刻到达，所以每条消息都携带发送者的时钟以指出其发送的时刻，当消息到达时，接收者时钟惹比消息发送时钟小，就立即将自己的时钟调到比发送时间大1或更多的值。在右图中，我们看到C现在到达的时间是61，同样D到达的时间是70。

（3）20在很多分布式系统应用中，需要物理时钟同步，举一个例子，并说明物理时钟同步的三种算法，Cristian 算法、Berkeley算法及平均值算法。

• 物理时钟：实时系统。
• 物理时钟同步的算法：
  • Cristian算法：客户与时间服务器联系。时间服务器可以精确地提供当前时间。
  • Berkeley算法：该系统中的时间服务器是主动的，它定期地询问每台机器的时间。基于这些回答，它计算出一个平均时间，并告诉所有其他机器将他们的时钟拨快到一个新的时间，或者拨慢，直到某个指定的减少量到达为止。
  • 平均值算法：将时间划分成固定长度的再同步间隔，第i次间隔开始于T0+iR，而结束于T0+(i+1)R，这里的T0是过去某一约定的时间，R时一个系统参数。在每次间隔的开始处，每台机器根据自己的时钟广播发送当前的时间，由于在不同机器上的时钟不可能完全同速工作，这种广播就不会完全同时发生。在机器广播发送时间之后，它启动本地计时器收集在S时间间隔中到达的其他广播，当所有广播到达后，执行一个算法，得到新的时间值。

####（4）7 分布式协同一致算法的目标是使所有无故障处理机对待某些问题的意见达到一致，在3个正常处理机，2个出错处理机的情况下，用Lamport算法能否达成一致，给出算法的具体步骤。P176 177

• 已证明了一个有m个处理机出错的系统中要实现协同一致，只有当有2m+1个正常处理机时才可能。处理机总数为3m+1。换种说法即是，只有大于2/3的处理机正常工作时，协同一致才是可能的。

• 步骤：

  1. 每个处理机发送消息给其它处理机，声明自己的数据，正常处理机声明的是真值，出错的处理机所有值可能都不正确。
  2. 把第一步声明的结果收集组成向量的形式。
  3. 每个处理机将各自的向量传递给其它每个处理机。
  4. 每个处理机检查接受向量的第ｉ个元素，若有一个值占多数，则把该数写到结果向量里，如果没有一个值占多数，则该元素标记为unknow。

####（4）8在实时分布式系统中，事件触发和时间触发系统的含义是什么，给出一个例子，并说明__为什么动态调度适合于事件触发系统__，给出三种动态调度算法。P182　187

• 事件触发和时间触发：
  • 事件触发：当一个重要的外部事件触发时，它被传感器察觉到，并导致与传感器相连的CPU得到一个终端请求。
  • 时间触发：每△T毫秒产生一次时钟中断。在每一次时钟滴答时，对（选定的）传感器进行采样，并且驱动（特定的）执行机构，中断仅在时钟滴答时发生。
• 三种动态调度算法：
  • 比率单调算法：它是设计用来抢占式调度一个单一处理机上的没有顺序的互斥限制的周期性任务的。它事先给每个任务分配一个与其执行频率相等的优先级。运行时，调度程序总是选择优先级最高的任务运行，如有必要，可先暂停运行当前任务。
  • 最早时限优先算法：每当监测到一个事件时，调度程序就将其加入等待任务队列中。这个等待队列根据这些任务的时限排序，最近的时限在最前面。然后，调度程序就从列表选择第一个任务调度，就是距它最后时限最近的一个。
  • 最小余度（松弛度）算法：即选择有最小余度的任务，即选择有最小喘息余地的任务来运行。

####（4）9主动复制容错的典型例子是三模冗余容错，说明某组成部件出错和某表决器出错时，是如何容错的。如果在某一级上同时有两个表决器出错，其它所有部件和表决器均正常，能否屏蔽错误，为什么？如果服务器采用主动复制的方法会存在什么问题，如何解决？P173

• 主要思想：主动复制是使用物理冗余来提供容错的一种著名的技术。这种方法多年来也应用于电子电路的容错。 例子：每个设备复制三次，每级电路都设置三个表决器，每个表决器都有三个输入和一个输出。若两个或三个输入相同，输出则等于输入。

• （1）假设A2失效，V1，V2，V3，都得到两个好的输入和一个坏的输入，这样每个都输出正确值到第二级。 （2）若在（1）基础上B3、C1也出错，这些影响也会被屏蔽。 （3）假设V1失灵，B1的输入也就是错误的，但只要其他都正常，B2、B3姜产生相同输出，并且V4、V5、V6将都产生正确的输出到第三级。

• 不能，因为每一级只有三个表决器，如果同时有两个表决器坏掉的话，超过了三分之二的要求，不能输出正确的结果。

####（4）10使用主机后备容错方法容错的主要思想是：在任何一个时刻都有一台服务器是主机，若主机失效了，后备的服务器将承担其任务。试说明主机后备方法的工作原理及存在的问题，及解决办法。P174

• 基本思想：在任一时刻都有一台服务器是主机，它完成所有的工作。若这个主服务器失效了，后备的服务器将承担其任务。

• 在RPC过程中，主机崩溃后产生情况如下：

  1. 如果主机在执行任务前崩溃，则没有损失。客户端会超时重发直到连上后备机，任务只被执行一次。 解决方案：客户端只是在超时后，再次重新发送请求消息，直到发送一定次数后，或者因得不到响应而停止发送请求消息，或者它的请求分别得到主服务器和备份服务器的处理，并且只执行一次。
  2. 如果主机在执行任务后向后备机发送更新消息前崩溃，此时后备机接管，请求消息再次到来，则任务被执行2次。 解决方案：还没有有效的解决方案，一般来说，在主服务器崩溃后，只正确执行一次请求消息的处理是非常困难的。
  3. 如果主机在后备机执行任务后自己发送响应消息前崩溃，则任务共被执行三次。一次主机完成，一次后备机完成，一次后备机接管时完成。如果请求消息带有序号，则可以减少任务执行次数。 解决方案：若每个请求消息都带有标志信息，那么请求消息只被执行两次。一般来说，在主服务器崩溃后，只正确执行一次请求消息的处理是非常困难的

####（4）11一个典型的集中的、启发式的处理机分配算法，即上-下算法。说明该算法的目标，并说明该算法的主要原理。P165

• 目标：让一个等了很久的，没有使用任何处理机的申请优先于已经占用了许多多处理机的申请。此为该算法的目标即公平的分配系统资源。

• 原理：该算法是一个不需要事前了解任何信息的启发性算法。算法中有一个协调者，保存着一张使用情况的表，每个工作站在表中都有一个条目，初值为0。当有重要的时间发生时，将给协调者发信息以更新使用情况表。算法将根据使用情况表决定处理机的分配。这些决定发生在调度事件发生时：有进程请求处理机、处理机进入空闲状态或者是发生了时钟中断。使用情况表中的记录值可以为整数、零或是负数。整数表示用户纯粹是在使用系统资源，负数表示用户需要系统资源，零则介于两者中间。

####（4）12 在支持多线程的系统中，可采用三种模型来组织多线程，详细说明这三种模型。如果在不支持多线程系统中实现文件服务，如何构造文件服务器。P141

• 派遣者/工作者模型: 某一个线程作为派遣者，它从系统邮箱内读出输入请求，然后检查请求，选择一个空闲的工作者线程去处理它。然后派遣者唤醒睡眠的工作者。 工作者被唤醒后，它检查共享块缓冲区是否可以满足这个请求。如不能满足，给磁盘发送消息，要求所需的数据块。且进入休眠状态等待磁盘操作的完成.
• 团队模型： 所有线程都是平等的，每个都获得和处理自己的请求。没有派遣者。如果工作来了不能处理，尤其是如果每个线程用来处理一种特殊的工作，可以维护一个队列，挂起的作业保存在作业队列中。线程在察看系统信箱前先察看作业队列。

• 管道线模型： 这种模型中第一个线程产生一些数据传给下一个线程去处理。数据持续从一个线程传到另一个线程，经过的每一个线程都进行处理。

• 有限状态机，当请求到来后有唯一的一个线程检查它，如果缓冲区能满足，进行运行，但是如果不能，就必须向磁盘发送一条消息。然而这时文件服务器并不阻塞，而是将当前请求的状态记录在一张表中，然后去获得吓一跳消息，下条消息可能时请求一个新工作或者时磁盘关于上次操作的应答。如果时请求一个新工作，就激活它。如果时从磁盘发来的应答，那么从表中取出相关信息并处理这个应答。由于这里不允许发送消息并且阻塞以等带应答，因此不能使用远程过程调用，原语应是非阻塞调用的ｓｅｎｄ和ｒｅｃｅｉｖｅ。

####（5）3在分布式系统，为了获得文件读写的效率，需要使用高速缓存，说明设置缓存的各种方法及用途。并说明解决一致性问题的四种算法及各种算法存在的问题。P208

• 方法及用途：
  • 最简单的选择是在每个用户进程自己的地址空间直接进行文件高速缓存，典型地，高速缓存由系统调用库管理。当打开、关闭、读和写文件时，该库只是保存最常用的文件.这样当重新使用文件时，它已经是可用的了。当该进程退出时，所有被修改过的文件都回写到服务器中。尽管这种模式的系统开销很小，但它仅当单个进程重复地打开和关闭文件时才有效率。一个数据库管理程序进程可能满足这种要求，但是在通常的程序开发环境中，大多数进程对每个文件只读一次，因此库中的高速缓存是无益可获的。
  • 第二个设置高速缓存的地方是在内核中，这里的缺点是在所有情况下都需要内核调用，甚至对于高速速缓存命中。但事实是，高速缓存使进程获益比补偿多。例如，假设一个两遍扫描编译器作为两个进积运行。第一遍扫描写一个中间文件而由第一遍扫描来读。当第一遍扫描进程结束后，该中间文件可能在高速缓存中，所以在第二遍扫描进程读人时没有必要进行服务器调用.
  • 设置高速缓存的第三个地方是在一个单独的用户级高速缓存管理者进程中，用户级高速缓存器管理者的优点是它保持了(微)内核独立于文件系统编码，因为它是完全孤立的，因此易十编程，并巨更加灵活。
• 四种算法：
  1. 直接写算法：(WRITE-THRONG算法)当修改一个高速缓存项(文件或块)时，新的值保存在高速缓存中并立即写到服务器；
  2. 延迟写：延迟写操作使得语义变得不清楚。当另一个进程读此文件时，它所得结果取决于时间选择。延迟写只好在运行效率和清晰的语义之间权衡。
  3. 关闭时写：仅当文件关闭后才将文件写到服务器，与对话语义相配；
  4. 集中控制算法： a 当打开一个文件时，打开该文件的机器向服务器发送一条消息。服务器保存谁打开了哪个文件以及打开是为了读还是写或者两者兼有。 b 如果文件是为读而打开，允许其他进程为读而打开，避免为写而打开。如果某个进程为写而打开一个文件，必须禁止所有其他访问。 c 当关闭文件时，必须报告，以便服务器更新。
• 缺点：
  1. 直接写：有效，但不影响写流量。
  2. 延迟写：效率较高，但可能语义不清。
  3. 关闭时写：与会话语义相配。
  4. 集中控制：UNIX语义，但不健壮，不能规模化。

####（5）4给出实现文件复制的三种方法，并举例说明更新复制文件的Gifford算法，并说明某些服务器崩溃时，应该采取什么措施。p212 P213

• 文件复制的三种方法：
  1. 显示复制，当一个进程产生一个文件时，它只在一台指定的服务器上进行，然后，如果需要的话，它可以在其他的服务器上生成另外的拷贝。如果目录服务器允许一个文件有多个拷贝，则所有拷贝的网络地址都可以和这个文件名联系起来，因此当用该文件名进行查找时，能找到它所有的拷贝。当该文件随后被打开时，它将以某种顺序对其拷贝一次进行尝试，直到找到一个可用的为止。
  2. 懒惰复制，只要在某个服务器上建立每个文件的一个拷贝，在编程人员后来不知道的情况下，服务器自己在其他的服务器上也可以自动地生成副本。系统必须足够聪明以便能够从这些拷贝中找到任何一个所需的拷贝。
  3. 用组复制文件，所有的写系统调用都同时传送到所有的服务器，这样，其他的拷贝在原文件产生的时候就产生了。

• Gifford基本思想：在读或写一个复制文件之前要求申请并获得多个服务器的允许。服务器在改变文件时，将一个新的版本号和新的文件联系起来。版本号用来该文件的版本。读一个已有N个复制存在的文件时，客户需要获得一个读法定数Nr，修改一个文件需要一个写法定数Nw，Nr和Nw的值必须满足约束条件Nr+Nw>N。即只有在适当数目的服务器参与时，文件才能被读或写。

• 解决办法：虚像表决通过为每个已经崩溃的服务器建立一个没有存储器的虚拟服务器。虚设者不允许出现在读法定数中，可以加入写法定数。

####（5）5 试说明举例什么是有状态服务器，什么是无状态服务器，并对有状态和无状态服务器进行详细的比较。

• 无状态服务器：当客户发送一个请求到给服务器，服务器完成请求，发送一个应答，然后从内部表中移出关于该请求的所有信息。在请求之间，服务器不保存具体客户的信息。
• 有状态服务器：服务器保存两个请求之间的客户的状态信息。

####（5）6 在分布式系统中，可支持上载/下载文件模式或远程访问模式，说明这两种模式并进行比较。P195

• 上载/下载模式： 文件服务只提供两种主要的操作：读文件和写文件。读文件将整个文件从一个文件服务器传送到提出请求的客户。写操作将整个文件从客户传送到服务器。 优点：概念简单。使用这种模式不需要掌握复杂的文件接口。整个文件的传送是高效的。
  缺点：客户端必须具有足够大的存储空间来存储所需的所有文件。如果只需要文件的一小部分，移动整个文件是很浪费的。

• 远程访问模式： 文件服务提供了大量的操作用于打开和关闭文件，读写文件的一部分，在文件中来回移动，检查和改变文件属性等。 优点：在客户端不需要很大的空间，当仅需要文件的一小部分时，需要传送整个文件。

####（6）1在交换式Dash多处理机系统中，为了保持缓存一致性，采用了Dash协议，某一簇中的一CPU写一未缓存的数据块，之后另外一簇的另外一CPU读该数据块。试详细说明写操作和读操作是如何进行的。P237

• 写操作和读操作： 查找该块簇的目录可知此未缓存的数据块，在缓冲中找不到，只能是属主所在族的存储器把块数据发送到缓存中，并把属主所在族的目录标记该块为脏。之后另外一簇的另外一CPU读该数据块，查找该块簇的目录可知此是脏数据块，若该数据块在该cpu的缓存中，则直接使用该块；若该数据块在该cpu邻近cpu的缓存中，则把邻近块发送到所需cpu的缓存中和属主所在族，通知属主所在族将其标记为干净，并存储在属主所在族中；若该数据块在其他族的缓存中，发送块到所需cpu的缓存中和属主所在族，通知属主所在族将其标记为干净。

####（6）2在基于总线的多处理机系统中，遵循write once协议，假设有C1，C2，C3，C4四个CPU，一操作序列如下：C1读一字W1（只存在于共享存储器中）、C1继续读该字、C2读该字；C1修改该字、C3读该字、C4读该字。试详细说明以上操作序列是如何执行的。P232

• 执行：
  1. C1读W1未命中，W1读入C1缓存并标记为干净。
  2. C1继续读W1命中，则直接读。
  3. C2读W1未命中，W1读入C2缓存并标记为干净，C1内存检测到C2读操作，未做反应。
  4. C1修改W1，C2检测到C1的写操作，将内存中的W1置无效，C1中修改项被标记为脏。
  5. C3读该字，C1内存检测到动作发信号禁止存储器响应，然后C1提供C3所需的字并把该字标记为无效，C3发现该字来自其他缓存并不是来自存储器且状态为脏，所以C3标记该字为脏
  6. C4同理。

####28详细分析影响分布式系统规模（Size）可伸缩性的三个因素，即集中式的服务、数据和算法。试举例说明分布和复制技术是如何提高可伸缩性的。P8

• 三个因素：
  • 服务：许多服务时以集中式方式实现的，他们由分布式系统中一台特定的计算机上运行的单个服务器来提供。用户增多时该服务器将成为系统的瓶颈。但是有时为了安全性不可避免的使用集中式服务。
  • 数据：因特网的域名系统不会用单个表单来记录域名。
  • 算法：任何一个算法是通过从所有站点收集信息，然后将这些信息发送到某个计算机加以处理，随后又向系统发布计算结果的方式来执行，那么只应该采用分布式算法。
• 分布和复制：
  • 分布：分布技术时把某个组建分割成多个部分，然后再将他们分散到系统中去。例：因特网DNS。
  • 复制：复制不仅能够增加可用性，而且还有助于组件间的负载平衡，从而使性能得到提高。例：许多Web用户认为如果浏览器返回一个在最近几分钟内正确性未经验证的缓存文档是可以接受的。

####29在分布式操作系统中，说明单内核的含义，并说明为什么采用微内核技术，通常微内核提供应提供哪些服务？

• 单内核：每台机器都运行一个传统的内核，内核自身提供了大多数的服务，此外它还增加了网络功能和远程服务集合，大部分的系统调用都是通过内核陷阱到达内核，在内核中完成相应的工作，然后将结果返回给用户进程。
• 除了单内核外，还有一种叫微内核，它本身提供很少的服务，大量的操作系统服务都是从用户级服务器获得。相比单内核技术，微内核技术与之不同，它不提供对文件系统、目录系统、整个进程管理、或许多系统调用的处理，具有更高的灵活性，只需要提供一些必要的简单的服务
• 服务：进程间通信机制；某些内存管理功能；少量的低层进程的管理和调度；低层输入/输出服务。

####30解决可伸缩性的技术包括隐藏通信延迟、分布和复制，试举例说明分布和复制技术是如何解决可伸缩性的。

• 同28

####31在分布式系统中，软件体系结构是一个非常重要的概念，涉及如何组织软件成分及如何交互等，详细说明四种Architectural Style。P24

• 四种Architectural Style:
  • 基于分层的体系结构。此种体系结构中，组件组成了不同的层，其中上层中的组件可以调用下面的层,其中一个关键因素是，其控制系统是从一层到另一层的：请求从上而下，而请求结果则从下往上。
  • 基于对象的体系结构。这是一种很松散的组织结构，基本上每个对象都对应一个组件，这些组件是通过远程过程调用机制来连接的。
  • 基于数据为中心的体系结构。该结构的进程通信需要一个公用（被动或主动的）的仓库。如已经开发了很多网络应用程序，它们依赖一个共享的分布式文件系统，其中的所有的通信都是通过文件虚拟发生的。同样，基于Web的分布式系统大部分也是以数据为中心的，进程通信使用了共享的基于Web的数据服务。
  • 基于事件的体系结构。进程基本上是通过事件的传播通信的，事件传播还可以有选择地携带数据。对于分布式系统来说，事件传播通常与发布/订阅系统有关。其基本思想是，进程发布事件，然后，中间件将确保那些订阅了 这些事件的进程才接收它们。

####32客户机服务器应用可以将软件成分分为三层，说明每一层的作用，并说明Internet搜索引擎是如何按三层结构组织软件成分的。P26

• 软件分成三层：
  • 用户接口层：含有直接与用户交互所需的一切。
  • 处理层：包含所有应用程序。
  • 数据层：管理要使用的实际数据。

• 搜索引擎的用户接口：用户输入关键字字符串，然后显示出Web网页列表。后端是由一个巨大的Web网页数据库组成，这些Web网页时预取的，且已加索引。搜索引擎的核心时把用户的关键字字符串转换成一个或多个数句库查询程序。它可以把结果排名成一个列表，并把该列表转换成HTML页面列表。在客户－服务器模型中，这种信息检索部分往往放在处理层。

####33 P2P是典型的非集中式体系结构，说明在结构化P2P系统中如何组织节点和数据，如何查找数据，如何进行成员管理。P31

• 从一个大的标示符空间中选取一个随机关键值赋给数据项。同样从这个标示符空间中选取一个随机数赋给该系统中的节点。当查找数据时，会返回对应数据项的结点的网络地址。 在Chord中，结点按逻辑组成一个还，这样，关键值K的数据项映射到最新标识符id>=k的结点。该结点称为关键值k的后继者，记做succ(k)。要真正查找数据项，运行在任意结点上的应用程序可调用函数LOOKUP(k),它可返回succ(k)的网络地址。此时，应用程序就可以与该结点联系以获得该数据项的副本。
• 成员管理：
  • 加入系统：它首先生成一个随机标识符id。（如果标识符空间足够大，那么生成的标识符与实际标识符相等的概率接近于０）然后，结点可以进行一个对id查找，返回网络地址succ(id) 。此时，所加入的结点只需与succ(id)及其前继者联系，并把自己插入到该环中即可。
  • 离开系统：结点id告之其前继者和后继者它要离开，并把其数据项转移给succ(id)。

####34 BitTorrent系统采用了集中与分布相结合的体系结构，说明BitTorrent系统的主要构成成分，并说明其工作原理。P37

• 主要构成：Web服务器，文件服务器，跟踪器
• 工作原理：
  • 基本思想：当一个终端用户要查找某个文件时，他可以从其他用户那里下载文件块，直到所下载的文件块能够组装完整的文件为止。
  • 具体实现：要下载一个文件，用户需要访问一个全局目录，这种目录含有指向名为.torrent文件的引用。一个torrent文件含有要下载特定文件的信息。特别地，它指向一个跟踪器。这是一个服务器，它保持有活动结点的精确记录，而这些结点具有所有请求的文件块。一旦结点确定了从哪里可以下载文件块，下载结点就变成了活动的。此时，它就被强制为其他结点提供帮助。

####35说明虚拟化的含义，为了实现虚拟化，计算机系统通常提供四种类型的接口，说明这四种接口，并说明两种实现方式。P56

• 虚拟化含义：有单个处理机但感觉有多个处理器机制可以扩展到其他资源，导致所谓的资源虚拟化。
• 四种类型的接口：
  • 由__机器指令__组成，可由任何程序激起的硬件软件界面。
  • 由__机器指令__组成，只由特权程序（操作系统）才可激活的硬件软件界面。
  • 由操作系统提供的__系统调用__组成的界面
  • 由库调用组成的界面，通常形成了所谓的__应用程序编程接口__(API)
• 两种实现方式：
  • 第一：可以构建一个运行时系统，实质上提供一套抽象指令集来执行程序。指令可以被翻译执行，也可以仿真执行。
  • 第二：提供一种系统。把它做成一层完全屏蔽硬件但提供一个同样指令集的界面。关键是这个界面可以同时提供给不同的程序。结果可以由多个不同的操作系统独立并发的运行在同一平台。

####36在分布式系统中，为什么需要代码迁移？代码迁移可以分为Sender-initiated和Receiver-initiated，解释其中的含义，并举例说明。P74

• 代码迁移
  • 基本思想：如果把进程由负载较重的机器上转移到负载较轻的机器上去，就可以提升系统的整体性能。
  • 除了性能方面还有灵活性方面的原因。实现代码迁移可以动态地配置分布式系统。
• Sender-initiated and Receiver-initiated：
  • Sender-initiated:代码当前驻留在哪台机器上或者正在哪台机器上执行，就由该机器启动代码迁移。例：通过因特网向Web服务器发送搜索程序以在该服务器上进行查询。
  • Receiver-initiated:代码迁移的主动权掌握在目标机器手中。例：Java applet。服务器控制客户端的迁移。

####37 为了支持大规模网络中的移动实体可以采用Home-Based方法，说明其工作原理，并说明存在的问题及可能的解决办法。P134

• 工作原理：持续跟踪实体的当前位置，可以使用特殊的技术来预防网络故障或者进程失效。每个移动主机都使用一个固定的IP地址，所有与该IP地址进行的通信一开始都被转发到移动主机的宿主代理中。宿主代理位于局域网中，与包含在移动主机IP地址中网络地址相对应。当一台移动主机转移到另一个网络中时，它会请求一个可以用来通信的临时地址，这种转交地址要在宿主代理中注册。当宿主代理接收到发送给移动主机的数据包时，它会查找主机的当前位置。如果主机是在当前本网络中，那么就只需转发数据包，否则，它会建立一条通往主机当前位置的通道，也就是说，它会把数据组装成IP包，然后发送给转交地址，同时把主机的当前位置告诉数据包的发送者。

• 存在问题：
  • 为了与移动实体通信，客户首先必须与宿主位置进行联系，而宿主位置可能与实体本身处于完全不同的位置，结果增加了通信延迟。
  • 固定宿主位置。必须保证宿主位置始终存在，否则无法与实体联系。
• 解决方法：在传统的命名服务中注册宿主位置，然后让客户首先查找宿主位置所在的位置。由于可以假定宿主位置是相对稳定的，所以查找到它以后可以有效地缓存它。

####38在DHT-based系统中可以采用finger　table提高查找效率，说明其工作原理，并举例说明。

• 工作原理：每个Chord结点不是现行的进行键值查找，而是维护一个最多有m个实体的指状表。如果用FTp表示结点p的指状表，那么有：

即第i个实体指向p后2^(i - 1)的第一个结点。要查找键值k，结点p立即把该请求转发给在p指状表中索引为i的结点q，其中：

• 例：从结点１解析k=26。首先，结点１在其指状表中查找k=26，发现该值大于FT1[ 5 ]，表示该请求将转发给结点18，而结点18将选择结点20，因为FT18[ 2 ] < k <= FT18[ 3 ]。最后，该请求从结点20转发给结点21，从结点21 又转发给28，该结点负责k=26。此时，结点28的地址返回给结点1,于是就完成了该键值的解析。