分布式操作系统考试题.doc

分布式操作系统 1在交换式Dash多处理机系统中，为了保持缓存一致性，采用了Dash协议，某一簇中的一CPU写一未缓存的数据块，之后另外一簇的另外一CPU读该数据块。试详细说明写操作和读操作是如何进行的。 写操作：该CPU查看缓存发现没有该数据块，它在本地发送请求查看邻近CPU的缓存中是否有该数据块。如果有，执行缓冲区到缓冲区的传送，如果块状态为干净宿主所在簇的其他拷贝置为无效。如果在本地查找失败，CPU发送体育馆到其宿主所在簇。如果块为未缓存，标记为脏并发送给请求者；如果块为干净，所有拷贝置为无效，标记为脏并发送给请求者；如果块为脏，请求传送到拥有该数据块拷贝的远程簇，该簇将自己的拷贝置为无效并满足写操作。 读操作：另一CPU查看自己缓存与本地簇其他CPU缓存发现无此数据块。该CPU发送请求包给宿主所在簇，发现所需块的状态为脏，目录查找拥有该块的簇的标志。该簇响应请求。并将该数据块发送给请求簇，将其状态改为干净，还要给宿主所在簇发回一个拷贝以更新存储器，这时块的状态被置为干净。 2在基于总线的多处理机系统中write once协议 b 如果文件是为读而打开，允许其他进程为读而打开，避免为写而打开。如果某个进程为写而打开一个文件，必须禁止所有其他访问。 c 当关闭文件时，必须报告，以便服务器更新。 d缺点：不健壮，不能规模化。 存在的问题：(1)直接写：有效，但不影响写流量。 (2)延迟写：效率较高，但可能语义不清。 (3)关闭时写：与会话语义相配。 (4)集中控制：UNIX语义，但不健壮，不能规模化。 4给出实现文件复制的三种方法，并举例说明更新复制文件的Gifford算法。 有状态服务器：服务器保存两个请求之间的客户的状态信息。 比较： 无状态服务器的优点：容错、不需要OPEN/CLOSE调用、没有服务器表空间的浪费、没有打开文件数目的限制、客户崩溃时不会造成服务器错误。 有状态服务器的优点：请求消息比较短，减少网络带宽、更好的性能、可以预读，预先读信息块减少延迟、易于幂等性（客户第二次发送相同请求时，可以不用再传输）、可以对文件加锁。 无状态服务器在本质上有更多的容错。不需要OPEN和CLOSE调用，这就减少了消息编号，特别对于那些整个文件用一次就可读出的普通情况，服务器不用浪费空间来存放表。使用表时，如果太多的客户一次打开太多的文件，则将表填满，就不能打开新的文件。最后对于状态服务器，如在文件打开时窗户出了故障，服务器就会牌困境中。如果它对此束手无策，它的表最终将充满垃圾。如果它超时了还未打开文件，那么客户因两个请求之间等待时间太长将被拒绝服务。 有状态服务器由于READ和WRITE消息并不是必须包含文件名，所以它可以更短些，这样就使用更小的网络带宽。由于关于打开文件的信息在文件关闭之前都可保存在主存储器中，所以有较好的性能。由于大多数文件都是按顺序读的，可以预先读信息块减少延迟。 6 在分布式系统中，可支持上载/下载文件模式或远程访问模式，说明这两种模式并进行比较。 上载/下载模式：文件服务只提供两种主要的操作：读文件和写文件。读文件操作是将整个文件以一个文件服务器传送到提出请求的客户；写操作是将整个文件从客户传送到服务器。 优点：概念简单。使用这种模式不需要掌握复杂的文件接口，而且整个文件传送也是高效的。 缺点：客户端必具有足够大的存储空间来存储所需的所有文件。如果只需要文件的一小部分，移动整个文件是很浪费的。 远程访问模式：文件服务提供了大量的操作用于打开和关闭文件，读写文件的一部分，在文件中来回移动，检查和改变文件属性等。 优点：在客户端不需要很大的空间，当仅需要文件的一小部分时，不需要传送整个文件。 7 分布式协同一致算法的目标是使所有无故障处理机对待某些问题的意见达到一致，在3个正常处理机，2个出错处理机的情况下，用Lamport算法能否达成一致，给出算法的具体步骤。 假设：正常处理机为：ABC。错误处理机为：DE。 每个处理发送消息给其它处理机消息： A：1 B：2 C：3 D：x1 y1 z1 m1 E：x2 y2 z2 m2 把第一步声明的结果收集组成向量的形式 A：（1，2，3，x1，x2） B：（1，2，3，y1，y2） C：（1，2，3，z1，z2） D：（1，2，3，4，m2） E：（1，2，3，m1，5） 每个处理现将各自的向量传递给其它处理机。 A： （1，2，3，y1，y2） （1，2，3，z1，z2） （1，2，3，4，m2） （1，2，3，m1，5） 每个处理机检查所有接收向量的第i个元素。若某个值占多数，放入结果向量中，否则，标记为UNKNOWN A会得出结论（1，2，3，UNKNOWN，UNKNOWN） 其他处理机进行相同的操作 ABC得到一致的向