分布式操作系统终极整理

（6）1在交换式Dash多处理机系统中，为了保持缓存一致性，采用了Dash协议，某一簇中的一CPU写一未缓存的数据块，之后另外一簇的另外一CPU读该数据块。试详细说明写操作和读操作是如何进行的。查找该块簇的目录可知此未缓存的数据块，在缓冲中找不到，只能是属主所在族的存储器把块数据发送到缓存中，并把属主所在族的目录标记该块为脏。之后另外一簇的另外一CPU读该数据块，查找该块簇的目录可知此是脏数据块，若该数据块在该cpu的缓存中，则直接使用该块；若该数据块在该cpu邻近cpu的缓存中，则把邻近块发送到所需cpu的缓存中和属主所在族，通知属主所在族将其标记为干净，并存储在属主所在族中；若该数据块在其他族的缓存中，发送块到所需cpu的缓存中和属主所在族，通知属主所在族将其标记为干净。（6）2在基于总线的多处理机系统中，遵循writeonce协议，假设有C1，C2，C3，C4四个CPU，一操作序列如下：C1读一字W1（只存在于共享存储器中）、C1继续读该字、C2读该字；C1修改该字、C3读该字、C4读该字。试详细说明以上操作序列是如何执行的。（5）3在分布式系统，为了获得文件读写的效率，需要使用高速缓存，说明设置缓存的各种方法及用途。并说明解决一致性问题的四种算法及各种算法存在的问题。方法：最简单的选择是在每个用户进程自己的地址空间直接进行文件高速缓存，典型地，高速缓存由系统调用库管理。当打开、关闭、读和写文件时，该库只是保存最常用的文件.这样当重新使用文件时，它已经是可用的了。当该进程退出时，所有被修改过的文件都回写到服务器中。尽管这种模式的系统开销很小，但它仅当单个进程重复地打开和关闭文件时才有效率。一个数据库管理程序进程可能满足这种要求，但是在通常的程序开发环境中，大多数进程对每个文件只读一次，因此库中的高速缓存是无益可获的。第二个设置高速缓存的地方是在内核中，这里的缺点是在所有情况下都需要内核调用，甚至对于高速速缓存命中。但事实是，高速缓存使进程获益比补偿多。例如，假设一个两遍扫描编译器作为两个进积运行。第一遍扫描写一个中间文件而由第一遍扫描来读。当第一遍扫描进程结束后，该中间文件可能在高速缓存中，所以在第二遍扫描进程读人时没有必要进行服务器调用.设置高速缓存的第三个地方是在一个单独的用户级高速缓存管理者进程中，用户级高速缓存器管理者的优点是它保持了(微)内核独立于文件系统编码，因为它是完全孤立的，因此易十编程，并巨更加灵活。四种算法：1直接写算法：（WRITE-THRONG算法）当修改一个高速缓存项（文件或块）时，新的值保存在高速缓存中并立即写到服务器；2延迟写：延迟写操作使得语义变得不清楚。当另一个进程读此文件时，它所得结果取决于时间选择。延迟写只好在运行效率和清晰的语义之间权衡。3关闭时写：仅当文件关闭后才将文件写到服务器，与对话语义相配；4集中控制算法：a当打开一个文件时，打开该文件的机器向服务器发送一条消息。服务器保存谁打开了哪个文件以及打开是为了读还是写或者两者兼有。b如果文件是为读而打开，允许其他进程为读而打开，避免为写而打开。如果某个进程为写而打开一个文件，必须禁止所有其他访问。c当关闭文件时，必须报告，以便服务器更新。d缺点：不健壮，不能规模化。(1)直接写：有效，但不影响写流量。(2)延迟写：效率较高，但可能语义不清。(3)关闭时写：与会话语义相配。(4)集中控制：UNIX语义，但不健壮，不能规模化。（5）4举例说明更新复制文件的Gifford算法，并说明某些服务器崩溃时，应该采取什么措施。Gifford推荐了一种更健全的方法，即表决其基本思想是在读或写一个拷贝文件之前要求申请并获得多个服务器的允许。例子：假设一个文件在N个服务器上都有拷贝。建立一个更新文件的规则:首先客户必须和超过平数的服务器联系，并让它们同意它进行更新。如果它们同意，就改变文件，并将一个新的版本号和新文件联系起来。该版本号用来标识该文件的版本，这对所有新近更新的文件都是一样的。当读一个已有拷贝的文件时，客户必须和超过半数的服务器联系，并请求它们发送与该文件相联系的版本号。如果所有版本号相一致，则说明这是最新的版本，如果企图只更新剩余服务器，会因为数目不足而失败。当一个崩溃的服务器重新启动时，它必须获得一个读法定数来找到最新的版本。在它开始正常工作之前，它将为自己拷贝一份该拷贝。由于该算法和基木的表决算法.具有相同的特性，因此它是可行的。这里唯一的区别是允许死的机器加人写法定数，但要满足一旦死机恢复，它们在进行服务之前应立即获得当前的版本的条件。（5）5试说明举例什么是有状态服务器，什么是无状态服务器，并对有状态和无状态服务器进行详细的比较。无状态服务器指当客户发送一个请求给服务器时，服务器完成请求，发送一个应答，然后从内部表中移出移出该请求的所有信息。在请求之间，服务器不保存具体客户的信息:有状态服务器指服务器应该保存两个请求之间的客户的状态信息。毕竟，集中式操作系统保存了关于活动进程的状态信息。（5）6在分布式系统中，可支持上载/下载文件模式或远程访问模式，说明这两种模式并进行比较。根据是否义持上载/下载模式或远程访问模式，文件服务可以分成两大类。在上载/下载模式中，文件服务只提供两种操作:读文件和写文件。前一个操作是将整个文件从一个文件服务器传送到提出要求的客户;后一个操作是将整个文件从客户传送到服务器。因此这种概念模式是在任一方向上传送整个文件。这些文件可以存储在内存或本地的硬盘中，视需要而定。上载/下载的优点是概念简单。应用程序取得它们所需的文件，然后在本地使用它们。任何修改过的文件或新创建的文件在程序结束时都要将它回写。使用这种模式不需要掌握复杂的文们亡接口，而且整个文件传送也是高效的.，但是，客户端必须具有足够大的存储空间来存储所需的所有文件。而且，如果只需要文件的一小部分，移动整个文件是很浪费的。文件服务的另一种类型是远程访问模式，在这种模式中，文件服务提供了大量的操作用于打开和关闭文件，读写文件的一部分，在文件中来回移动检查和改变文件属性，等等。而在上载/下载模式中，文件服务只提供物理存储和传送，在这里文件系统运行在服务器上而不是运行在客户端。远程存取模式的优点是在客户端不需要很大的空间，与下又需要文件的一小部分时，不需要传送整个文件。（4）7分布式协同一致算法的目标是使所有无故障处理机对待某些问题的意见达到一致，在5个正常处理机，3个出错处理机的情况下，用Lamport算法能否达成一致，给出算法的具体步骤。已证明了一个有m个处理机出错的系统中要实现协同一致，只有当有2m+1个正常处理机时才可能。处理机总数为3m+1。换种说法即是，只有大于2/3的处理机正常工作时，协同一致才是可能的。举例给出算法的步骤：1.每个将军发送消息给其它将军，声明自己真实的军队人数2.把第一步声明的结果收集组成向量的形式。（b）3.每个将军将各自的向量传递给其它每个将军。（c）（4）8在采用三模冗余容错的系统中，说明某组成部件出错和某表决器出错时，是如何容错的。如果在某一级上同时有两个表决器出错，其它所有部件和表决器均正常，能否屏蔽错误，为什么？主要思想：主动复制是使用物理冗余来提供容错的一种著名的技术。这种方法多年来也应用于电子电路的容错。例子：思想：每个设备复制三次，每级电路都设置三个表决器，每个表决器都有三个输入和一个输出。若两个或三个输入相同，输出则等于输入。最坏？？--A2、V1+B1、V4+C1错误（1）假设A2失效，V1，V2，V3，都得到两个好的输入和一个坏的输入，这样每个都输出正确值到第二级。（2）若在（1）基础上B3、C1也出错，这些影响也会被屏蔽。（3）假设V1失灵，B1的输入也就是错误的，但只要其他都正常，B2、B3姜产生相同输出，并且V4、V5、V6将都产生正确的输出到第三级。不能，因为每一级只有三个表决器，如果同时有两个表决器坏掉的话，超过了三分之二的要求，不能输出正确的结果。（4）9使用主机后备容错方法容错的主要思想是：在任何一个时刻都有一台服务器是主机，若主机失效了，后备的服务器将承担其任务。试说明主机后备方法的工作原理及存在的问题基本思想：在任一时刻都有一台服务器是主机，它完成所有的工作。若这个主服务器失效了，后备的服务器将承担其任务。在RPC过程中，主机崩溃后产生情况如下：1.如果主机在执行任务前崩溃，则没有损失。客户端会超时重发直到连上后备机，任务只被执行一次。解决方案：客户端只是在超时后，再次重新发送请求消息，直到发送一定次数后，或者因得不到响应而停止发送请求消息，或者它的请求分别得到主服务器和备份服务器的处理，并且只执行一次。2.如果主机在执行任务后向后备机发送更新消息前崩溃，此时后备机接管，请求消息再次到来，则任务被执行2次。解决方案：还没有有效的解决方案，一般来说，在主服务器崩溃后，只正确执行一次请求消息的处理是非常困难的。3.如果主机在后备机执行任务后自己发送响应消息前崩溃，则任务共被执行三次。一次主机完成，一次后备机完成，一次后备机接管时完成。如果请求消息带有序号，则可以减少任务执行次数。解决方案：若每个请求消息都带有标志信息，那么请求消息只被执行两次。一般来说，在主服务器崩溃后，只正确执行一次请求消息的处理是非常困难的（4）10一个典型的集中的、启发式的处理机分配算法，即上-下算法。说明该算法的目标，并说明该算法的主要原理。目标：让一个等了很久的，没有使用任何处理机的申请优先于已经占用了许多多处理机的申请。此为该算法的目标即公平的分配系统资源。原理：该算法是一个不需要事前了解任何信息的启发性算法。算法中有一个协调者，保存着一张使用情况的表，每个工作站在表中都有一个条目，初值为0。当有重要的时间发生时，将给协调者发信息以更新使用情况表。算法将根据使用情况表决定处理机的分配。这些决定发生在调度事件发生时：有进程请求处理机、处理机进入空闲状态或者是发生了时钟中断。使用情况表中的记录值可以为整数、零或是负数。整数表示用户纯粹是在使用系统资源，负数表示用户需要系统资源，零则介于两者中间。（4）11在支持多线程的系统中，可采用三种模型来组织多线程，详细说明这三种模型。如果在不支持多线程系统中实现文件服务，如何构造文件服务器。派遣者/工作者模型:某一个线程作为派遣者，它从系统邮箱内读出输入请求，然后检查请求，选择一个空闲的工作者线程去处理它。然后派遣者唤醒睡眠的工作者。工作者被唤醒后，它检查共享块缓冲区是否可以满足这个请求。如不能满足，给磁盘发送消息，要求所需的数据块。且进入休眠状态等待磁盘操作的完成.团队模型：所有线程都是批平等的，每个都获得和处理自己的请求。没有派遣者。如果工作来了不能处理，尤其是如果每个线程用来处理一种特殊的工作，可以维护一个队列，挂起的作业保存在作业队列中。线程在察看系统信箱前先察看作业队列。管道线模型：这种模型中第一个线程产生一些数据传给下一个线程去处理。数据持续从一个线程传到另一个线程，经过的每一个线程都进行处理。如何构造服务器：（3）12在机器0上进程0在等待机器0上进程1所拥有的资源，进程1在等待机器1上进程2所拥有的资源，进程2在等待进程机器1上3，4所拥有的资源，进程3在等待机器2上进程5所拥有的资源，机器2上的进程5在等待机器0上进程0所拥有的资源，画出简化的资源图并说明用Chandy-Misra-Hass提出的分布式死锁检测算法如何检测死锁，并打破死锁。101234756机器0机器1机器2检测死锁：当某个进程等待资源时，例如进程0等待进程1，将调用Chandy-Misra-Has算法。此时，生成一个特殊的探测消息并发送给占用资源的进程。消息由三个数字构成：阻塞的进程，发送消息的进程，接收消息的进程，如由0到1的初始消息包含三元组(0,0,1)。接到消息后，接受者检查以确定它自己是否也在等待其它进程。如果是，那么消息就要被更新，第一个字段保持不变，第二个字段改为当前进程号，第三个字段改为等待的进程号。然后消息接着被发送到等待的进程。如果在等待多个进程，就