分布式操作系统考试题剖析

分布式操作系统1在交换式Dash多处理机系统中，为了保持缓存一致性，采用了Dash协议，某一簇中的一CPU写一未缓存的数据块，之后另外一簇的另外一CPU读该数据块。试详细说明写操作和读操作是如何进行的。写操作：该CPU查看缓存发现没有该数据块，它在本地发送请求查看邻近CPU的缓存中是否有该数据块。如果有，执行缓冲区到缓冲区的传送，如果块状态为干净宿主所在簇的其他拷贝置为无效。如果在本地查找失败，CPU发送体育馆到其宿主所在簇。如果块为未缓存，标记为脏并发送给请求者；如果块为干净，所有拷贝置为无效，标记为脏并发送给请求者；如果块为脏，请求传送到拥有该数据块拷贝的远程簇，该簇将自己的拷贝置为无效并满足写操作。读操作：另一CPU查看自己缓存与本地簇其他CPU缓存发现无此数据块。该CPU发送请求包给宿主所在簇，发现所需块的状态为脏，目录查找拥有该块的簇的标志。该簇响应请求。并将该数据块发送给请求簇，将其状态改为干净，还要给宿主所在簇发回一个拷贝以更新存储器，这时块的状态被置为干净。2在基于总线的多处理机系统中，遵循writeonce协议，假设有C1，C2，C3，C4四个CPU，一操作序列如下：C1读一字W1（只存在于共享存储器中）、C1继续读该字、C2读该字；C1修改该字、C3读该字、C4读该字。试详细说明以上操作序列是如何执行的。C1查看缓存发现没有该字，从共享存储器中读取W1，同时缓存中也存储W1，状态为干净。C1又一次读W1。查看自己缓存发现存在该字，从缓存中读取W1。C2读W1先在自己缓存中查找发现没有缓存，从共享存储器读取W1并存储在缓存中，状态为干净。C1修改W1将缓存中的该字修改，状态变为脏，同时C2监听到写请求，将自己缓存中的W1置为无效。C3读该字，C1发现读请求发信号禁止存储器响应，C1向C3提供该字并将自己的项置为无效，C3发现该字来自其他缓存其状态置为脏，并将自己缓存项标记为脏。C4读该字，C3发现读请求禁止存储器响应，并向C4提供该字，并且将自己的项置为无效。C4发现该字来自其他缓存，其状态为脏，则标记自己缓存项为脏。3在分布式系统，为了获得文件读写的效率，需要使用高速缓存，说明设置缓存的各种方法及用途。并说明解决一致性问题的四种算法及各种算法存在的问题。在一个各自有主存和磁盘的客户一服务器系统中，有四个地方可用来存储文件或存储部分文件:服务器磁盘，服务器主存，客户磁盘(如果可用的话)或客户主存。在服务器内存设置缓存，可以减少I/O次数，而在客户端内存和磁盘中设置缓存，可以减少网络通信。1.在服务器磁盘在服务器磁盘上，有允足的空间，存放在那里的所有文件对所有客户都是可访问的。而且，由于每一个文件只有一份拷贝，所以不会产生一致性的问题.2.在服务器主存将最近使用的文件保留在服务器的主存中。客户读取一个刚好在服务器主存中的文件，可以消除磁盘传送，但网络传送仍然存在。在服务器主存中设置高速缓存：容易、对客户是完全透明的。由于服务器可以保证其主存和磁盘拷贝同步。从客户的观点看，每个文件只有一个拷贝，不会产生一致性问题。3.在客户磁盘客户磁盘保存数据多但速度慢。如果使用大量的数据，客户磁盘高速缓存可能更好些。4.客户端高速缓存此时有三种可使用的选择来精确定义高速缓存的位置：a)、在每个用户进程自己的地址空间直接进行文件高速缓存。b)、在内核中。c）、在一个单独的用户级高速缓存管理者进程中，它保持了(微)内核独立于文件系统编码，因此易十编程，并巨更加灵活.四种算法：1直接写算法：（WRITE-THRONG算法）当修改一个高速缓存项（文件或块）时，新的值保存在高速缓存中并立即写到服务器；2延迟写：延迟写操作使得语义变得不清楚。当另一个进程读此文件时，它所得结果取决于时间选择。延迟写只好在运行效率和清晰的语义之间权衡。3关闭时写：仅当文件关闭后才将文件写到服务器，与对话语义相配；4集中控制算法：a当打开一个文件时，打开该文件的机器向服务器发送一条消息。服务器保存谁打开了哪个文件以及打开是为了读还是写或者两者兼有。b如果文件是为读而打开，允许其他进程为读而打开，避免为写而打开。如果某个进程为写而打开一个文件，必须禁止所有其他访问。c当关闭文件时，必须报告，以便服务器更新。d缺点：不健壮，不能规模化。存在的问题：(1)直接写：有效，但不影响写流量。(2)延迟写：效率较高，但可能语义不清。(3)关闭时写：与会话语义相配。(4)集中控制：UNIX语义，但不健壮，不能规模化。4给出实现文件复制的三种方法，并举例说明更新复制文件的Gifford算法，并说明某些服务器崩溃时，应该采取什么措施。三种方法：1、显式复制：当进程产生一个文件时，可以在其他服务器上生成另外的拷贝。如果目录服务存在允许一个文件有多个拷贝，所有拷贝的网络地址都可以和这个文件名联系起来。2、懒惰复制：只要在某个服务器上建立每个文件的一个拷贝，服务器自己在其他的服务器上也可自动生成副本。3、使用组通信：所有的写系统调用同时传送到所有的服务器。于是，其他的拷贝在原文件产生时就产生了。Gifford算法：即表决（voting）,其基本思想是在读或写一个拷贝文件之前要求中请并获得多个服务器的允许。下面举一简单的例子来说明该算法是如何工作的：假设一个文件在N个服务器上都有拷贝。建立一个更新文件的规则:首先客户必须和超过半数的服务器联系，并让它们同意它进行更新。如果它们同意，就改变文件，并将一个新的版本号和新文件联系起来。该版本号用来标识该文件的版本，这对所有新近更新的文件都是一样的。当读一个已有拷贝的文件时，客户必须和超过半数的服务器联系，并请求它们发送与该文件相联系的版本号。如果所有版本号相一致，则说明这是最新的版本，如果企图只更新剩余服务器，会因为数目不足而失败。例如，有5个服务器，客户已确定它们中的三个有版本号8，则其他两个的版本号不可能是9。因为任何从版本号8到版本号9的成功更新需要三个服务器同意，而不是两个。Gifford的方案实际上比这更普通一些。在该方案中，读一个已有N个拷贝存在的文件时，客户需要获得一个读法定数，它是任何Nr个或更多服务器的任一集合。同样，修改一个文件需要一个至少Nw个服务器的写法定数Nr和Nw的值必须满足约束条件Nr+NwN。只有在适当数目的服务器同意参与时，文件才能读或写文件。假设最近的写法定数由从C到L的10个服务器组成，所有这些服务器得到了新版本和新版本号，任何随后的由3个服务器组成的读法定数中将至少包含一个该集合中的成员。当客户查看版本号时，它将知道哪一个是最新的并得到它。解决办法：虚像表决通过为每个已崩溃的服务器建立一个没有存储器的虚拟服务器解决了服务器崩溃的问题。虚设者不允许出现在读法定数中，但它可以加入写法定数中。当一个崩溃的服务器重新启动时，它必须获得一个读法定数来找到最新的版本。在它开始正常工作之前，它将为自己拷贝一份该拷贝。5试说明举例什么是有状态服务器，什么是无状态服务器，并对有状态和无状态服务器进行详细的比较。无状态服务器：当客户发送一个请求到给服务器，服务器完成请求，发送一个应答，然后从内部表中移出关于该请求的所有信息。在请求之间，服务器不保存具体客户的信息。有状态服务器：服务器保存两个请求之间的客户的状态信息。比较：无状态服务器的优点：容错、不需要OPEN/CLOSE调用、没有服务器表空间的浪费、没有打开文件数目的限制、客户崩溃时不会造成服务器错误。有状态服务器的优点：请求消息比较短，减少网络带宽、更好的性能、可以预读，预先读信息块减少延迟、易于幂等性（客户第二次发送相同请求时，可以不用再传输）、可以对文件加锁。无状态服务器在本质上有更多的容错。不需要OPEN和CLOSE调用，这就减少了消息编号，特别对于那些整个文件用一次就可读出的普通情况，服务器不用浪费空间来存放表。使用表时，如果太多的客户一次打开太多的文件，则将表填满，就不能打开新的文件。最后对于状态服务器，如在文件打开时窗户出了故障，服务器就会牌困境中。如果它对此束手无策，它的表最终将充满垃圾。如果它超时了还未打开文件，那么客户因两个请求之间等待时间太长将被拒绝服务。有状态服务器由于READ和WRITE消息并不是必须包含文件名，所以它可以更短些，这样就使用更小的网络带宽。由于关于打开文件的信息在文件关闭之前都可保存在主存储器中，所以有较好的性能。由于大多数文件都是按顺序读的，可以预先读信息块减少延迟。6在分布式系统中，可支持上载/下载文件模式或远程访问模式，说明这两种模式并进行比较。上载/下载模式：文件服务只提供两种主要的操作：读文件和写文件。读文件操作是将整个文件以一个文件服务器传送到提出请求的客户；写操作是将整个文件从客户传送到服务器。优点：概念简单。使用这种模式不需要掌握复杂的文件接口，而且整个文件传送也是高效的。缺点：客户端必具有足够大的存储空间来存储所需的所有文件。如果只需要文件的一小部分，移动整个文件是很浪费的。远程访问模式：文件服务提供了大量的操作用于打开和关闭文件，读写文件的一部分，在文件中来回移动，检查和改变文件属性等。优点：在客户端不需要很大的空间，当仅需要文件的一小部分时，不需要传送整个文件。7分布式协同一致算法的目标是使所有无故障处理机对待某些问题的意见达到一致，在3个正常处理机，2个出错处理机的情况下，用Lamport算法能否达成一致，给出算法的具体步骤。假设：正常处理机为：ABC。错误处理机为：DE。1.每个处理发送消息给其它处理机消息：A：1B：2C：3D：x1y1z1m1E：x2y2z2m22.把第一步声明的结果收集组成向量的形式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）3.每个处理现将各自的向量传递给其它处理机。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在实时分布式系统中，事件触发和时间触发系统的含义是什么，给出一个例子，并说明为什么动态调度适合于事件触发系统，给出三种动态调度算法。事件触发系统：当一个重要的外部事件触发时，它被传感器察觉到，并导致与传感器相连的CPU得到一个中断请求。时间触发系统：每△t毫秒产生一次时钟中断，在每一次时钟滴答时，对传感器进行采样，并驱动执行机构。中断仅在时钟滴答时发生。例：考虑对一个100层楼的电梯控制器的设计。假定电梯在60层等客人。有人在一层按下按钮。就在100毫秒后，另一人在100层上按下按钮。在事件触发系统中，第一次按钮产生一个中断，使电梯启动下行，就在做出下行决定后，第二个按钮事件到来，因此第二个事件被记录下来以作为将来的参考，但电梯还是下行。在时间触发系统中，它每500毫秒采样一次，若两次按下按钮事件都在一次采样周期中出现，控制就必须做出决定。动态调度是在运行期间检测到事件时进行调度，用事件触发系统可以在低负载更快的响应。算法：1.比率单调算法2.最早时限优先法3.最小余度法9主动复制容错的典型例子是三模冗余容错，说明某组成部件出错和某表决器出错时，是如何容错的。如果在某一级上同时有两个表决器出错，其它所有部件和表决器均正常，能否屏蔽错误，为什么？如果服务器采用主动复制的方法会存在什么问题，如何解决？每个设备复制三次，结果是每级电路都设置了三个表决器，每个表决器都有三个输入和一个输出。若两个或三个输入相同，输出则等于该输入。若三个输入各不相同，输出就是不定值。1.假设A2失效，V1V2V3都得到两个好的输入和一个坏的输入，每个都输出正确值到第二级。2.A2B3C1都出错，A2出错V1V2V3都输出正确值到第二级，同理B3出错V4V5V6也都输出正确值到第三级