高级操作系统AvancedOperatingSystem.ppt

高级操作系统Advanced Operating System 熊焰 yxiong@ustc.edu.cn 0551_3607394 中国科学技术大学计算机系 第三章 分布式进程和处理机管理 分布式系统模型 分布式处理机分配 分布式进程调度 分布式系统容错 实时分布式系统 3.3 分布式进程调度必要性 在分布式操作系统中，每个处理机只是进行自己的本地进程调度（假定它上面有多个进程在运行），而不管其它处理机正在干什么。 在大多数情况下，这种方式工作得很好。 但当一组相关的、彼此需要通讯的进程在不同的处理机上运行时，那么，各自独立的进程调度就不是最有效的方法了。 3.3 分布式进程调度必要性举例 4个进程：A、B、C、D 2个处理器：0，1，分时调度的时间片长度100ms A、B在处理器0上运行C、D在处理器1上运行 A需要向D发送大量的消息，或者对D进行许多远程调用 一种较坏的情况： A和D在两个处理器上，正好按时间片交叉运行 3.3 分布式进程调度必要性举例 在时间片0，A和C运行 若A启动后立即调用D，但此时C在运行，只有进程切换到D才能处理 100ms后，在时间片1，进程切换到B和D D收到A的消息，处理，并答复，但此时B在运行，只有进程切换到A才能处理 100ms后，在时间片2，进程切换到A和C A收到D的应答消息 综上，每次消息交换需要花费200ms因此，需要一个协同进程调度算法来保证相互通信的进程能够同步执行。 3.3 分布式进程调度协同进程调度算法 尽管动态地确定进程间的通信比较困难，但在大多数情况下，可以同时启动一组相互联系的进程。例如， 通常UNIX管道中过滤器之间的通信比它们与其它进程之间的通信要多。 假定：进程都是成组创建的，且组内进程之间的通信要比组间进程之间的通信多得多。 进一步地假定：系统有足够多的处理机来处理最大的一组进程，并且每一个处理机都是具有N个时间片的多进程处理机。 3.3 分布式进程调度协同进程调度算法 Ousterhout在1982年提出了一个基于协同调度概念的算法 算法在调度时考虑进程间的通信，保证同一组中的所有进程都在同一个时间片内同时运行 算法使用的数据结构：一个概念上的矩阵 行：每时间片一行，表示在该时间片内各处理器上运行的进程 列：每处理器一列，表示在该处理器上按时间片顺序的进程执行序列 3.3 分布式进程调度协同进程调度算法—基本思想 对每台处理机使用循环调度算法,例如 启动处理器0在时间片3的进程,然后启动处理器1在时间片3的进程,… 使每台处理机使用轮转调度算法,例如 所有的处理机首先运行时间片0中的进程一段时间,然后运行时间片1中的进程一段时间 算法可以用一个广播消息来通知所有处理机在何时进行进程切换，以便保证时间片的同步。 将同一组内所有进程都放在不同处理机上同一个时间片内并保证同一组内的所有进程同时被调度运行这样可以获得N倍的并行度，并使通信吞吐率达到最大。 为了提高性能，4个必须通信的进程应该分别放入处理机1、2、3、和4的时间片3中。 这种调度方法可以与MICROS使用的层次式进程管理算法结合起来使用，只要每一个系主任都保存他属下教师的矩阵，对矩阵中的进程分配时间片，并广播时间片同步消息即可 3.4 分布式容错系统 当一个系统没有完成它应该完成的任务，我们将其称之为失败或失效。例如， 在超市的分布式订购系统中，一个失败有可能导致罐装豆子缺货。 而在一个分布式航空交通指挥系统中，一个失败可能会导致一场巨大的灾难！ 随着分布式计算机系统广泛应用于安全要求较高的场合，防止失效就变得越来越重要了。 3.4 分布式容错系统3.4.1 部件错误 计算机中的部件错误可能会引起系统的失效， 这些部件包括处理机、内存、输入输出设备、电缆或者软件等。 这种部件错误实际上就是一个故障。它产生的原因是多方面的，例如， 设计错误、制造错误、编程错误、物理损坏、时钟不准、环境恶劣、操作错误、非法输入、线路咬坏等等。 当然，并不是所有的错误都会立即导致系统失效。 3.4 分布式容错系统错误的分类 错误一般被分为三类： 偶发性错误：偶尔发生一次，然后再也不会发生的错误。再重复操作一次，错误就会消失。 例如，一只鸟飞过微波传输器所发射的光束可能导致网络中一些数据位的丢失，但传输超时后再传输时，网络数据的传输又恢复正常。 间歇性错误：一会儿发生一会儿消失，反复不断。 例如，网线接触不良会造成网络一会儿连通一会儿断连，这种间歇性错误很难发现，因而危害性比较大。特别是当人们使用各种手段进行诊断时，故障又消失了。 永久性错误：当错误出现时，它是不会自动消失的，必须将发生错误的部件修复后，错误才能消失。 例如，芯片烧坏、软件错误以及磁盘磁头损坏等都属于