高级操作系统答案

1、名词解释：分布式系统: 一个分布式系统是若干个具有自治功能的独立计算机的集合，但是对该系统的用户来说，感觉该系统就像一台计算机一样。硬件方面：每台计算机都是独立、自主的计算机；软件方面：用户感觉在独占系统。分布式系统物理上是分布的，逻辑上是一个整体。分布透明性: 分布透明性是一种现象，通过这种现象，系统中分布式的各个方面在用户与应用之间隐藏了起来，即分布式系统在用户和应用程序面前呈现为单个计算机系统。包括：访问透明、位置透明、移植透明、重定位透明、复制透明、并发透明、故障透明和持久性透明。多线程文件服务器：多线程是这样一种机制，它允许在程序中并发执行多个指令流，每个指令流都称为一个线程，彼此间

2、互相独立。文件服务器是一种器件，它的功能就是向服务器提供文件。标识符：是用户编程时使用的名字。我们用标识符这个名词来表示各资源项的名称。标识符可以用于多种目的，如访问，定位，调度，分配，故障控制，同步以及对象或资源的共享。在系统结构的各层次上，标识符以不同的方式出现。中间件：答案1：指一个软件层，放在应用程序和网络操作系统之间，它提供了一个编程抽象以及对底层网络、硬件、操作系统和编程语言异构性的屏蔽。答案2：中间件是一种独立的系统软件或服务程序，分布式应用软件借助这种软件在不同的技术之间共享资源。中间件位于客户机/ 服务器的操作系统之上，管理计算机资源和网络通讯。是连接两个独立应用程序或独立系

3、统的软件。相连接的系统，即使它们具有不同的接口，但通过中间件相互之间仍能交换信息。执行中间件的一个关键途径是信息传递。通过中间件，应用程序可以工作于多平台或 OS 环境。RPC：答：RPC是remote procedure call（远程过程调用）的简称。RPC思想是使远程的过程调用就像在本地的过程一样，调用者不应该意识到此调用的过程是在其他机器上实行的。 RPC的执行步骤： (1) 客户过程以普通方式调用相应的客户存根； (2) 客户存根建立消息，打包并激活内核陷阱； (3) 内核将消息发送到远程内核； (4) 远程内核将消息发送到服务器存根； (5) 服务器存根将消息解包，取出其中参数后调

4、用服务器过程； (6) 服务器完成工作或将结果返回服务器存根； (7) 服务器存根将它打包并激活内核陷阱； (8) 远程内核将消息发送至客户内核； (9) 客户内核将消息交给客户存根； (10) 客户存根将消息解包，从中取出结果返回给客户； 远程对象调用：远程对象调用是通过调用远程对象的方法实现的。远程对象调用=远程方法调用。失效：系统出错或不能满足它的承诺（提供服务）。容错：避免系统失效。在故障发生时系统仍能正常运行（提供服务）解答题简述处理机分配算法中的接受者发起的分布式启发性算法的算法实现过程及算法的特点。发送者发起的分布式启发算法：当创建进程时，创建进程的机器将对一个随机选取的机器发生

5、询问，询问它的负载是否低于某个阈值，如果是，将发送进程否则将选择另一台机子发送询问。如果在N次询问内还没有找到合适的机器，算法停止新进程将在创建它的机器上运行。该算法的缺点是：在负载十分严重的情况下，所有机器都会不停的毫无意义的向其他机器发送询问，想找到一台愿意接受更多工作的机器，在这种情况下，几乎没有进程会被减轻负载，但却会引起相当可观的额外开销。试举例说明没有统一时钟的分布式系统会发生什么问题？解答：当每台机器有它自己的时钟时，一个发生于另一事件之后的事件可能会被标记为一个比另一个事件更早的时间。例一致性协议中，复制的写协议有哪几种？请简单解释？答：复制的写协议：写操作可以在多个副本上执行

6、。包括两种类型：主动复制和基于法定数量的协议。 主动复制：每个副本有一个关联的进程，该进程执行更新操作。操作被发送到每个副本。 基于法定数量的协议，其基本思想是：在读或写一个复制的数据项之前要求申请并获得多个服务器的允许。试描述客户和服务器之间使用套接字的面向连接的通信是如何进行的？答：为了实现服务器与客户机的通信，服务器和客户机都必须建立套接字。服务器与客户机的工作原理可以用下面的过程来描述。 (1)服务器先用socket函数来建立一个套接字，用这个套接字完成通信的监听。 (2)用bind函数来绑定一个端口号和IP地址。因为本地计算机可能有多个网址和IP，每一个IP和端口有多个端口。需要指定

7、一个IP和端口进行监听。 (3)服务器调用listen函数，使服务器的这个端口和IP处于监听状态，等待客户机的连接。 (4)客户机用socket函数建立一个套接字，设定远程IP和端口。 (5)客户机调用connect函数连接远程计算机指定的端口。 (6)服务器用accept函数来接受远程计算机的连接，建立起与客户机之间的通信。 (7)建立连接以后，客户机用write函数向socket中写入数据。也可以用read函数读取服务器发送来的数据。 (8)服务器用read函数读取客户机发送来的数据，也可以用write函数来发送数据。 (9)完成通信以后，用close函数关闭socket连接。 客户机与服

8、务器建立面向连接的套接字进行通信，请求与响应过程可用图来表示。文件更新有哪几种主要算法？简述其算法思想？ 答：文件更新有主拷贝复制和表决（Voting）算法两种主要算法。主拷贝复制算法：指定一个服务器为主服务器，其它服务器为从服务器；当要更新一个复制文件，将该更新文件送至主服务器；在主服务器处完成修改，然后向各从服务器发命令，完成修改；容错方法：将日志写在稳定存储器。 表决（Voting）算法：基本思想：在读或写一个复制文件之前要求申请并获得多个服务器的允许，并将新的版本号与文件联系起来，用以识别文件版本； 读法定数（read quorum）Nr:读文件操作前必须达到的服务器数； 写法定数（w

9、rite quorum）Nw:更新文件前必须达到的服务器数； Nr与Nw遵循的规则：NwN/2（服务器总数的一半），NrNwN。基于物理时钟的同步算法有哪几种？简述他们的算法实现过程。答：主要有三种：Cristian算法、Berkeley算法、Averaging算法。Cristian算法： 有一个时间服务器，提供标准时钟，其它系统通过询问与它同步。 在/2秒的周期内，每个机器向服务器发出校时请求，服务器用CUTC进行响应，各机器根据响应值重置自己的时钟。 由于时钟是不可回卷的，对于当前时钟值已经大于CUTC的机器必须动态调整自己时钟的H值，减慢时钟推进的速率，逐渐地消化与标准时钟之间的差距。

10、由于请求与响应的传输与处理会产生延迟，进而影响时钟的精度。因此要求询问者要统计它与服务器之间的RTT，并利用它对得到的时间响应值进行修正。Berkeley算法： 时间服务器（time daemon）没有标准时钟，它通过定期地询问各个机器的当前时间并从中求出平均值作为当前的标准时间，然后再广播给各个机器。当前时钟慢于新标准时间的机器重置自己的时钟；当前时钟快于新标准时间的机器要调整自己的H值，以消化这个时间误差。时间服务器的时钟由系统管理员手工校正。Averaging算法： 定义一个固定的同步间隔R，每经过R时刻，所有的机器广播自己的当前时钟。在经过规定的接收间隔S之后，所有的机器根据接收到的时

11、钟值计算自己的当前时钟值。 由于大家都不考虑传输延迟，所以实际得到的时钟值是滞后的，即在R+t的时刻得到R时刻的时钟值，并将其作为自己R+t时刻的时钟值。 时钟值计算的最简单方法是求平均值。如果要求更精确，则可以去掉m个最大值和n个最小值之后再计算平均值，这可以过滤掉一些病态的时钟值。简述处理机分配算法中图论算法的算法思想及目标。答：图论算法的思想：整个系统可以表示为一张带权图，每个节点表示一个进程；子图内每条边表示两个进程之间的通信量；从一个子图连向另一个子图的边表示网络通信。 算法的目标：在满足所有的资源限制下，找到一种划分方式使网络通信量最小。请说出路径N: 的名称解析过程答：这个路径名

12、的解析是从命名图中节点N开始的，首先在节点N的目录表中查找名字label-1，得到label-1所代表的节点的标识符；然后在label-1所代表的节点的目录表中查找名字label-2，得到label-2所代表的节点的标识符；此过程一直进行下去，如果N:在命名图中是实际存在的，就能够得到label-n所代表的节点的标识符，从而得到该节点的内容。以客户为中心的一致性模型有哪几种？试分别举例说明答：单调读一致性：当一个进程读了数据项x的值后，所有后续的对x的读操作，都将返回相同的值，或者更新的值。也就是说，单调读一致性保证，如果一个进程已经在t时刻看到x的值，那么以后它不会再看到较老版本的x的值。例

13、：读email(旧金山-纽约）例a：符合单调读一致性例b: 不能保证单调读一致性；单调写一致性：一个进程对数据项x的写操作，必须在该进程对x的所有后续写操作之前完成。例：软件库更新（版本1,.,n)例a：符合单调写一致性例b: 不能保证单调写一致性；读自己写一致性（写后读）：一个进程对数据项x的写操作结果，总能被该进程对x的后续读操作读到。例1：Web网页更新、浏览：服务器更新，本地缓存未更新。例2：数字图书馆密码更新：管理服务器更新密码，其他服务器拷贝尚未更新。例a：符合写后读一致性例b: 不能保证写后读一致性；写跟随读一致性（读后写）：一个进程在对数据项x读操作之后对x的写操作，必须在x已

14、读出的相同值或者更近的值之上进行例：BBS跟帖（读原文章A,写回应文章B）例a：符合写跟随读一致性例b: 不能保证写跟随读一致性存储器一致性模型有哪几种？试分别解释其含义。所谓存储一致性模型，实际上是系统设计者与应用程序员之间的一种约定。如果应用软 件遵从一定的规则访问虚拟内存系统，则应用软件可以获得正确的存储访问结果；反之，如果破坏了约定的规则，则存储访问的正确性不受保证。按照一致性从强到弱的顺序，可以区别为下面几种类别。 (1)、严格一致性模型 这是对一致性要求最严格的一种模型，它由下面的条件来描述：任何对内存位置X的读操作将返回最近位置对X进行写操作的值。 在DSM系统中，这是一种理想的

15、模型，但是受到网络延迟的影响而不可能实现。在DSM系 统中实现的多种一致性模型，都是对严格一致性模型在不同程度上的放松。而在单机环境下，任何存储访问序列都满足严格一致性要求。 (2)、顺序一致性模型 顺序一致性对存储器的限制比严格一致性要弱一些，顺序一致性的存储器要满足以下的条件： 1） 每个进程的内部操作顺序是确定不变的； 2） 假如所有的CPU上的进程都对某一个存储单元执行操作，那么，它们的操作顺序是确定的，即任一进程都可以感知到这些进程同样的操作顺序。 上述条件的含义是指，当多个进程分别在不同的机器上并发执行的时候，只要所有的进 程都保持同样的顺序访问存储器，那么，任何有效的交叉访问执行

16、都是可以接受的。在 顺序一致性模型中，时间不再是影响一致性的因素，它关心的是：所有进程都必须能够感受到一直的内存访问序列。 顺序一致性模型不确保进程的一次读操作可以返回由另一进程所写入的最新值。在没有显式的同步操作的情况下，再一次运行同样的程序不能保证获得同样的结果。 (3)、因果一致性模型 因果一致性模型是对顺序一致性的弱化，它要求在具有潜在因果关系（Happened - Bef ore）的操作之间保持其一致的顺序。一般性的描述如下：有潜在性因果相关的写操作必须以同样的顺序被各个进程所感知，而并发的写操作在不同的机器上有不同的顺序。在基于因果顺序一致性模型的存储管理系统中合法的操作序列在顺序

17、一致性或者严格一致性模型中可能会成为非法操作。 (4)、管道一致性模型 管道一致性模型是在因果一致性模型上的进一步弱化，它满足下面的条件：由某一个进程完成的写操作可以被其他所有的进程按照顺序的感知到，而从不同进程中来的写操作对不同的进程可以有不同的顺序。 管道一致性模型相对来说比较容易实现，所以在应用中具有一定的吸引力。实际上，它对于不同进程所感知到的写操作顺序并没有保证，除非是从同一个进程源来的写操作，则必须按照顺序到达别的所有的进程，类似于它们处在一条管道中一样。除此以外在管道一致性 模型中，有不同进程产生的写操作完全是并行的。 （5）、弱一致性模型 尽管管道一致性模型与较之严格的一致性模

18、型相比，能够获得更好的性能。但因为它对同一个进程(源)所产生的结果仍然作了必须按序送达到所有别的进程的要求，所以在很多应用方面仍然受到了模型的限制。并非所有的进程都要求看到所有的写操作的结果，让他们按照顺序看到写操作的结果更是没有必要。这样处理，模型的开销会严重影响应用程序的性能。考虑到运算的中间结果在大多数情况下并没有必须传送出去的必要的具体情况，我们必须对一致性要求作进一步的放松，修改为只有在需要传播写操作的结果的时候才将结果传送出去，除此之外，一切读写操作都完全是并行的。为了达到同步操作的目的，在弱一致性模型中引入了同步变量。弱一致性模型必须满足的条件有下面几点: l 对同步变量的访问满

19、足一致性的要求 l 对同步变量的访问，只有在以前的写操作在各处都完成之后才能完成。 l 对数据的操作（读或写），只有在以前的对同步变量的操作完成之才能完成。 第一点说明所有的进程都能以同样的顺序感知到所有对同步变量的访问。当一个进程访问某同步变量时，它会把对该同步变量的访问广播出去，在该进程对该同步变量访问操作成功之前，任何别的进程对同步变量的访问都将被阻塞。 第二点说明对同步变量的访问会导致对内存进行刷新的结果。当一个同步访问完成之后，那么，所有先前的写操作可以同时确保完成。当某进程对一个共享数据作了更新之后面，它可以通过同步操作将新值传播出去。 第三点说明当一个进程在读一个共享数据（非同步

20、变量）时，通过同步操作，它能获得该共享数据的最新值。（6）、释放一致性模型 对于同步变量的访问，弱一致性模型存在一个问题：无法区分进程是准备进入临界区还是已经完成对共享变量的操作而准备退出临界区，其结果就是进程在以下两种情况下都必须采取同步操作： l 将局部写操作的结果传播出去 l 从别的机器上收集共享数据的最新值 如果将进入和退出临界区这两个动作区分，则可以实现一种更为高效的存储一致性模型-释放一致性模型。释放一致性模型提供了两类同步操作：Acquire和Release。某进程将要进入临界区时执行Acquire操作，退出时执行Release操作。也可以不用临界区而用栅栏（Barrier）同步

21、来实现释放的一致性协议。栅栏是一种同步机制，它要求所有的进程全都到达程序的某一点后，各个进程才能继续往下执行。 借助于Acquire和Release操作，我们可以把某些特殊的共享变量保护起来，并维护它们的一致性。当然，应用程序必须确知它需要维护其一致性的数据，这也给应用程序的编制增加了一些协议开销，但是整体性能提高了。通常，如果一个分布式共享存储系统满足释放一致性，则它必须遵守以下的规则： l 某进程只有在成功完成Acquire操作之后，才能确保对一般共享变量（非共享同步变量）访问的正确性。 l 某进程只有在完成对共享数据的读写操作之后，Release操作才能完成。l Acquire和Rele

22、ase操作必须满足管道一致性要求。为了更进一步提高性能，另外一种实现释放一致性模型的协议被称之为懒惰释放一致性（Lazy Release Consistency），与之对应，一般的实现被称为勤释放一致性（Eager Release Consistency）。它们之间的区别在于，勤释放一致性协议在Release操作结束之后，将所有已修改的数据传送给所有的别的进程。这样，别的进程都将拥有此最新数据的一个副本并可在本地访问它们。但实际情况是有可能别的进程并不需要该共享数据，这样就浪费了带宽并给程序带来不必要的延迟。懒惰释放一致性协议在Release操作结束之后，并不急于传送新的数据，而是在别的进程执

23、行Acquire操作之后，由别的进程向它提出获取新的数据的请求时，它响应该请求并把共享数据的最新值传送给特定的进程，这样系统的性能又获得了提高。（7）、单项一致性模型另外一种用于提高临界区操作并行性的一致性模型是单项一致性模型。和释放一致性类似，它要求编程人员在临界区的开始和结束时使用Acquire和Release操作，但与释放一致性不同的是，它要求每个共享变量都与某同步变量相关联，同步变量可以是锁或者栅栏。以并行访问一个数组的不同元素为例，它要求给不同的数组元素加不同的锁，只有 当对同步变量的Acquire操作完成之后，相关的共享数据才得到一致性保证。单项一致性模型也不同于懒惰释放一致性模型，后者并不将共享数据与锁或栅栏相关联，而是在对同步变量作Acquire操作之后，才能确定它需要那些共享数据。满足单项一致性的条件是:l 在当前拥有者对数据的更新操作为完成之前，不能执行另一个进程对同步变量的Acquire操作。 l 如果某一个进程正以互斥模式访问某同步变量。则在该进程释放此同步变量之前，任何别的进程即使在非互斥模式下都将无法获得该同步变量。l 如果某进程正以互斥模式访问一个同步变量，则在该进程完成操作之后，任何进程在以