12.说明RICART和AGRAWALE分布式互斥算法；假定A和B是相互独立的两个临界区，进程0要进入A，进程1要进入B，R-A分布式互斥算法会导致死锁吗？
说明理由。
答：
RICART和AGRAWALE算法要求系统中所有事件都是全序的，也就是说，对任何事件组消息，哪个先发必须无歧义，算法如下：
当一个进程想进入临界区时，他要建立一个包括他要进入的临界区的名字、处理机号、当前时间的消息，然后将消息发送给所有其他进程，也包括发送给自身，当一个进程接收另一个进程消息时，它取决于接受方的状态以及临界区的名字有三种情况：
1）接受者不在临界区，也不想进入临界区，他就向发送者发送OK消息；2）接受者已经在临界区，它不必回答，而是负责对请求队列排队；3）接收者要进入临界区，但是还没有进入，它要负责将发来的消息和它发送给其他进程的时间戳对比，取小的那个。
如果来的消息时间戳小，接收者发送OK消息，否则接收者负责排列请求队列而不发送任何消息。
在发送完允许进入临界区的请求后，进程将不再做任何事，仅等待所有的允许消息，一旦得到允许，它就进入临界区。
它从临界区退出时，向队列中所有进程发送OK消息，并将它从队列中删除。
该算法可能导致死锁，例如：
A和B是相互独立的两个临界区，进程0要进入A，进程1要进入B，而此时进程0在B中，进程1在A中就会进入死锁。
13.举例说明用私有工作空间实现事务处理时的基本思想。
答：
在进程开始一个事务时给它分配一个包含了所有需要访问的文件的私有工作空间，在事务提交或终止前，所有的读写操作都在私有空间而不是真正的文件系统中进行，存在的问题是所有内容都拷贝到私有空间，代价难以承受。
优化方法是：
1）私有空间中只包含一个指向父辈工作区的指针，当事务处于最顶层时，它的工作区是真正的文件系统。
2）使用索引节点，索引是一个与判断文件所在的磁盘块位置有关的数据库，给方法不将全部文件考入私有空间，而只是拷贝索引。
14.说明在分布式系统中实现原子性提交的两阶段提交协议的基本思想及其优点。
答：
两阶段提交协议的基本思想是有一个进程作为协调者，通常是执行事务的进程。
在准备提交阶段，协调者向日志中写入Prepare，然后向所有服务器发送准备提交消息，服务器接收到消息后，检查自己是否准备提交，如果是就向日志中写入Ready，然后向协调者发送准备好消息。
在提交阶段，协调者接收所有响应后决定提交还是撤销，如果所有服务器都准备提交，则提交事务；否则撤销事务。
无论如何协调者都会写入日志，并发送决定消息，服务器接到消息后也将结果写入日志，并发送结束消息，完成整个过程
15.举例说明为什么使用集中式的死锁检测算法会产生假死锁，并给出一种解决办法。
答：
集中式的死锁检测算法每台机器的资源图中只包含它自己的进程和资源，协调者节点保存整个系统（所有资源图的集合）的资源图。
当机器资源图发生变化时相应的消息发送给协调者以提供更新，当协调者检测到环路时，它终止一个进程以解决死锁。
如上图圆表示进程，方框表示资源，开始时如同a，b，c所示，过来一段时间，B释放R并请求T，这是一个合法的操作，机器0向协调者发送一条消息申明它释放资源R，机器1向协调者发送一条消息声明进程B正在等待它的资源T，不幸的是机器1的消息先到达协调者，导致生成资源图如图d所示。
协调者得出错误的结论——死锁存在，这种情况称为假死锁。
解决办法是：
使用Lamport算法以提供全局统一的时间，对协调者收到的消息按照时间戳排序
16.说明wait-die和wound-wait分布式死锁预防方法。
事务时间戳为50的进程申请事务时间戳为100的进程占用的资源。
按以上两种策略，结果会如何?
。
答：
（时间戳越小的进程越是年老）wait-die死锁预防算法：
当较老的进程请求年轻进程所占有的资源时，老进程只能等待；如果年轻进程请求老进程占有的资源时，年轻进程会被终止。
Wound-wait死锁预防算法：
当老进程请求年轻进程所拥有的资源时，老进程抢占年轻进程的资源，年轻进程被终止；当年轻进程请求老进程所拥有的资源时，年轻进程等待。
第四章
17.叙述实现线程包的方法及其优缺点。
答：
1在用户空间实现线程：
是将线程包完全放到用户空间中去，内核对此一无所知。
优点：
在不支持线程的操作系统中实现；线程切换比使用内核陷阱快一个数量级；允许每个进程有自己定制的调度算法。
缺点：
阻塞调用怎样实现？
系统调用改为非阻塞，SELECT。
如何实现调度？
旋转锁，始终信号中断。
2在内核中实现线程：
当一个线程想去创建一个新线程或撤销已存在的线程时，它发出一个内核调用，由它完成创建和回收工作。
内核中每个进程都有一张包含线程信息（线程的寄存器、状态、优先权等）的表。
优点：
容易实现调度。
缺点：
系统开销大。
3调度者行为：
内核分配一定数量的虚拟处理机给每个进程，并且让（用户空间）运行期系统将线程分配给处理机。
优点：
效率，很好地解决了控制权由阻塞线程传递给非阻塞线程。
缺点：
可能产生死锁，与分层系统的内在结构违背。
18.说明发送者发起的分布式启发算法和接收者发起的分布式启发算法及各自的主要缺点。
答：
发送者发起的分布式启发算法：
当创建进程时，创建进程的机器将对一个随机选取的机器发生询问，询问它的负载是否低于某个阈值，如果是，将发送进程否则将选择另一台机子发送询问。
如果在N次询问内还没有找到合适的机器，算法停止新进程将在创建它的机器上运行。
该算法的缺点是：
在负载十分严重的情况下，所有机器都会不停的毫无意义的向其他机器发送询问，想找到一台愿意接受更多工作的机器，在这种情况下，几乎没有进程会被减轻负载，但却会引起相当可观的额外开销。
接收者发起的分布式启发算法：
当一个进程结束时，系统将检查自己是否有足够的工作可做，如果没有，将随机向一台机器申请工作，如果那台机器没有要给予的工作，系统将继续询问第二，第三台机器，如果询问N台机器都没有申请到工作，系统将暂停申请开始处理系统队列中一个等待进程，当这个进程结束后，开始下一轮的申请；如果系统无事可做，则将进入空闲状态，一定时间后从新开始申请。
给算法的缺点是：
系统在无事可做时会造成相当大的询问负载。
19.举例说明Lamport等人提出的算法是如何解决Byzantine将军问题的。
答：
Lamport等人设计了一种递归算法可在特定条件下解决这一问题。
例如：
N=4（有四个将军），M=1（其中有一个叛徒），对这样的参数，参数运行四步。
第一步，每个将军发送可靠的消息给其他所有的将军，声明自己真实的军队人数，忠诚的将军声明的是真值，叛徒则可能对其他每个将军都撒一个不同的谎。
如图a；
第二步，把第一步声明的结果组成向量形式，如图b；
第三步，每个将军把图b中各自的向量传递给其他每一个将军，这里叛徒再一次撒谎，使用了12个新值。
A—J。
如图c；
第四步，每个将军检查所有新接收向量的每一个元素，若某个值占多数则把该值放入结果向量中，
20.简述三模冗余的基本思想，并举例说明三模冗余能否处理Byzabtine故障。
答：
三模冗余是使用物理冗余来提供容错的技术，是使用主动复制方法的容错。
在电子电路中有设备A、B、C，然后每个设备复制三次，结果就是每级电路都设置了三个表决器，每个表决器有三个输入和一个输出，若两个或者三个输入相同，输出则等于输入，若三个输入各不相同，输出就是不定值，这种设计就是TMR。
若处理机是Byzabtine类型的，出错的处理机仍然工作并发出错误的随机的应答，那么至少需要2k+1个处理机才能达到k级容错。
最坏情况下k个失效的处理机偶然（甚至有意）地产生相同的应答，然而剩下的k+1个未出错的处理机也将产生相同的应答，因此客户机可以根据大多数的应答得到正确结果。
三模冗余在每组中有一个部件出现Byzabtine故障时可以处理，而一组中有两个甚至三个同时出现Byzabtine故障则不能处理。
21.举例说明采用图论确定性算法进行处理机分配的实现方法。
答：
整个系统可以表示为一张带权图，每个节点表示一个进程，每条边表示两个进程之间的通信量。
从数学角度看，整个问题就变成了如何根据特定的限制将图划分成k（k为系统中cpu数量）个不相连的子图（如每个子图的总cpu和内存需求在一定限制内）。
对于每种满足限制的解决方案，子图内部的边意味着机器内部的通信，可以忽略。
从一个子图连向另一个子图的边表示网络通信。
该算法的目标就是在满足限制下，找到一种划分方式使网络通信量最小。
下图表示了图的两种划分:
方案A:
通信量=（3＋2＋4＋4）＋（2＋8＋5＋2）＝30
方案B:
通信量=（3＋2＋4＋4）＋（3＋5＋5＋2）＝28
第五章
35、使用上载/下载模式的文件服务器系统与使用远程访问模式的文件系统之间有什么区别？
答：
文件服务分为两种类型：
上载/下载模式和远程访问模式。
上载/下载模式。
只提供两种主要的操作（读文件和写文件），读操作将整个文件从文件服务器传输到请求客户端，写操作则刚好相反，文件系统运行在客户端。
优点是系统概念简单，应用程序取得需要的文件，并在本地使用它。
当程序结束时，将所有修改的文件或新创建的文件写回去，不需要管理复杂的文件服务接口，文件传输效率高。
缺点是客户端需要足够的存储空间，当需要部分文件是需要传输整个文件。
远程访问模式。
提供了大量的操作，如打开、关闭文件，读写部分文件等等。
文件系统在服务器端运行。
优点是客户不需要大量存储空间，当需要部分文件是不需要传输整个文件。
22.分布式系统中处理共享文件的四种方法（文件共享的四种语义）。
答：
1）UNIX语义。
系统使所有的操作都有一个绝对时间顺序，READ操作读取最近一个WRITE操作后的内容，要求对一个文件系统的任何操作对所有进程都是及时可见的。
2）会话语义。
对于打开文件的修改最初只对修改文件的进程是可见的，当文件关闭后，对文件的修改对其他进程才是可见的。
3）不可修改语义。
不允许打开文件进行写操作，只提供CREATE和READ两种操作。
只能进程讲的的共享和复制。
4）事务语义。
使用原子事务，即所有的操作要么全做，要么全不做。
23.说明无状态服务器和有状态服务器，并说明二者的区别。
状态服务器
如果是状态化请求，那么服务端一般需要保存请求的相关信息，每个请求可以默认地使用以前的请求信息。
状态服务器具有以下特点：
-保存客户请求的数据（状态）
-服务端容易对客户状态进行管理
-服务端并不要求每次客户请求都携带额外的状态数据
无状态服务器
无状态服务器处理的客户信息必须全部来自于请求所携带的信息以及其他服务器自身所保存的、并且可以被所有请求所使用的公共信息。
无状态服务器具有以下特点：
-并不保存客户请求的数据（状态）
-客户在请求时需要携带额外的状态数据
-无状态服务器更加健壮，重启服务器不会丢失状态信息，这使得维护和扩容更加简单
24.说明保持客户高速缓存一致性的四种算法。
答：
1）直接写，当缓存中的文件被更新后，新的值在缓存在保存，而且同时发送到服务器，而当另外的进程访问文件时，读到的是最新值，但是存在一个问题，其他进程在更新之前读到的文件内容可能是过期的，那么在每次用到文件时需要从服务器中读取文件版本进行比较，查看是否过期，但是每次都要在服务器和客户端之间通信，这样就体现不出缓存的作用了。
2）延迟写，操作不立即发送给服务器，而是延迟一段时间，也就减少了网络消息，当进程读取文件时，依赖于时间。
具体读到的是那次操作的结果不确定，语义模糊。
3）关闭写，操作只有在文件关闭后才写回服务器，配合session语义。
4）集中控制，就是在文件服务器上保存了进程对文件的操作方式等信息，类似于锁机制的管理，避免写操作的文件被其他进程操作，但是当修改的操作结束时，会将操作结束消息通知服务器，操作的结果也就立即会送到服务器
25.说明分布式系统提供文件复制服务的原因以及实现复制的三种方法。
答：
分布式系统通常保持文件的多个拷贝，每个拷贝放在一台单独的文件服务器上，提供这种服务主要有一些几种原因：
1）数据不丢失，通过对每个文件的独立备份来增加系统的可靠性；2）当一个文件服务器出现问题时，仍然允许进行文件访问；3）负载均衡，将工作量分配到多个服务器上。
三种复制方法一次如上图所示：
1）显示复制，如图a所示，是为编程人员控制整个进程所用，当进程产生一个文件时，可以在其他服务器上生产另外的拷贝，如果目录服务允许一个文件有多个拷贝，所有拷贝的网络地址都可以和这个文件名联系起来。
2）懒惰拷贝，如图b所示，只要在某个服务器上建立每个文件的一个拷贝服务器自己在其他的服务器上也可以自动生成副本。
3）用组复制文件，如图c所示，所有的写系统调用同时传送到所有的服务器，于是，其他的拷贝在源文件产生时就产生了。
26.说明更新复制文件的两种主要算法：
主拷贝算法、Gifford算法。
答：
主拷贝算法，使用时，指定一个服务器为主服务器，其他所有服务器为从服务器，当要更新一个复制文件时，我们就将该改变发送至主服务器上，在本地完成修改，然后向各从服务器发出命令，命令他们也完成修改。
这样可以在任何一个（主或者从）服务器上进行读操作。
这种方法简单，但是有个问题，当主服务器停机时，所有的更细将不能进行。
Gifford算法，基本思想是在读写一个复制文件之前要求先申请并获得多个服务器的允许。
例如，读一个已经有N个副本的复制文件，客户需要获得一个读法定数，它是任何Nr个或更多个服务器的任一集合，同样的，修改一个文件需要一个至少Nw个服务器的写法定数。
Nr和Nw的值必修满足约束条件Nr+Nw>N，只有在适当数目的服务器同意参与时，文件才能进行读写操作。
第六章
27.说明在Dash交换式多处理机系统中，如何读写一个存储器中的字。
CPU如何读取一个存储器中的字。
CPU首先检查自己的缓存。
若缓存中无此字，则在本地簇内发出请求，询问本地簇的其他cPu缓存中是否有此字。
若有，该数据块从该缓存传送到发出申请的CPU缓存中。
若数据块的状态是CLEAN,拷贝此数据块。
若块的状态是DIRTY，其目录将此块标记为CLEAN，使之共享无论如何，只妥命中缓存就能满足指令，但不影响任何目录的位图。
如果数据块不在任何簇的缓存中，CPU将发一请求信包给该块的宿主所在簇，这可以由存储器地址的高4位来确定。
宿主所在簇可能就是请求者所在的簇。
在这种情况下消息并未被实际发送。
宿主所在簇的目录管理硬件检查它的表以确定块的状态。
若为UNCACHED或CLEAN，硬件从全局存储器中取出块，将其发送到请求簇，该簇更新其日录，表明该块已在缓冲区中（如果还没有这样标记）。
如所需块的状态为DIRTY,目录硬件查找拥有该块的簇的标志，该簇响应请求。
拥有DIRTY块的簇将数据块发给请求簇，并因为数据块己共享，将其状态改为CLEAN;它还要给宿主所在簇发回一个拷贝以更新存储器，这时块的状态被置为CLEAN。
若块被置为一个新状态，因为目录跟踪状态的变化，其目录也将随之改变。
写操作与此不同。
在写以前，执行写操作的CPU必须确定它拥有系统中该缓存块的唯一拷贝。
若该CPU的缓存中己有此数据块.且状态为DIRTY，可以立即写;若
升级会员 