第三章分布式进程和处理机管理 分布式系统模型 ·分布式处理机分配 ·分布式进程调度 ·分布式系统容错 ·实时分布式系统
第三章 分布式进程和处理机管理 ⚫ 分布式系统模型 ⚫ 分布式处理机分配 ⚫ 分布式进程调度 ⚫ 分布式系统容错 ⚫ 实时分布式系统
3.3分布式进程调度 必要性 在分布式操作系统中，每个处理机只是进行自 己的本地进程调度（假定它上面有多个进程在 运行)，而不管其它处理机正在干什么。 ·在大多数情况下，这种方式工作得很好。 。但当一组相关的、彼此需要通讯的进程在不同 的处理机上运行时，那么，各自独立的进程调 度就不是最有效的方法了
3.3 分布式进程调度 必要性 ⚫ 在分布式操作系统中，每个处理机只是进行自 己的本地进程调度（假定它上面有多个进程在 运行），而不管其它处理机正在干什么。 ⚫ 在大多数情况下，这种方式工作得很好。 ⚫ 但当一组相关的、彼此需要通讯的进程在不同 的处理机上运行时，那么，各自独立的进程调 度就不是最有效的方法了
3.3分布式进程调度 必要性举例 。4个进程：A、B、C、D 处理机 。2个处理器：0,1， 时间片0 1 分时调度的时间片长度100ms A ·A、B在处理器0上运行 1 B C、D在处理器1上运行 A ·A需要向D发送大量的消息，或者对D 3 B 进行许多远程调用 一种较坏的情况： 4 A A和D在两个处理器上，正好按时间片交 5 B D 叉运行
3.3 分布式进程调度 必要性举例 ⚫ 4个进程：A、B、C、D ⚫ 2个处理器：0，1， 分时调度的时间片长度100ms ⚫ A、B在处理器0上运行 C、D在处理器1上运行 ⚫ A需要向D发送大量的消息，或者对D 进行许多远程调用 ⚫ 一种较坏的情况： ⚫ A和D在两个处理器上，正好按时间片交 叉运行 A C B D A C B D A C B D 处理机 时间片 0 1 0 1 2 3 4 5
3.3分布式进程调度 必要性举例 在时间片0，A和C运行 若A启动后立即调用D,但此时C在运行，只 处理机 有进程切换到D才能处理 时间片0 。100ms后，在时间片1，进程切换到B和D A ● D收到A的消息，处理，并答复，但此时B在 运行，只有进程切换到A才能处理 B 100ms后，在时间片2，进程切换到A和C 2 ·A收到D的应答消息 3 B 。综上，每次消息交换需要花费200ms 4 A 因此，需要一个协同进程调度算法来保证 相互通信的进程能够同步执行。 5 B D
A C B D A C B D A C B D 处理机 时间片 0 1 0 1 2 3 4 5 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分布式进程调度 协同进程调度算法 尽管动态地确定进程间的通信比较困难，但在大多数 情况下，可以同时启动一组相互联系的进程。例如， 0 通常UNⅨ管道中过滤器之间的通信比它们与其它进程之间 的通信要多。 假定： 进程都是成组创建的，且组内进程之间的通信要比组 间进程之间的通信多得多。 ●进一步地假定： 系统有足够多的处理机来处理最大的一组进程，并且 每一个处理机都是具有N个时间片的多进程处理机
3.3 分布式进程调度 协同进程调度算法 ⚫ 尽管动态地确定进程间的通信比较困难，但在大多数 情况下，可以同时启动一组相互联系的进程。例如， ⚫ 通常UNIX管道中过滤器之间的通信比它们与其它进程之间 的通信要多。 ⚫ 假定： 进程都是成组创建的，且组内进程之间的通信要比组 间进程之间的通信多得多。 ⚫ 进一步地假定： 系统有足够多的处理机来处理最大的一组进程，并且 每一个处理机都是具有N个时间片的多进程处理机
3.3分布式进程调度 协同进程调度算法 处理机 时间片 1234 56 7 0 usterhout在1982年提出 0 × × 了一个基于协同调度概念 1 X × 的算法 2 × × X 算法在调度时考虑进程间的 通信，保证同一组中的所有 3 X × 进程都在同一个时间片内同 4 × X X 时运行 5 × × 。算法使用的数据结构：一个概念上的矩阵 行：每时间片一行，表示在该时间片内各处理器上运行的 进程 列：每处理器一列，表示在该处理器上按时间片顺序的进 程执行序列
3.3 分布式进程调度 协同进程调度算法 ⚫ Ousterhout在1982年提出 了一个基于协同调度概念 的算法 ⚫ 算法在调度时考虑进程间的 通信，保证同一组中的所有 进程都在同一个时间片内同 时运行 ⚫ 算法使用的数据结构：一个概念上的矩阵 ⚫ 行：每时间片一行，表示在该时间片内各处理器上运行的 进程 ⚫ 列：每处理器一列，表示在该处理器上按时间片顺序的进 程执行序列 × 处理机 时间片 0 1 2 3 4 5 6 7 0 1 2 3 4 5 × × × × × × × × × × × × ×
3.3分布式进程调度 协同进程调度算法一基本思想 对每台处理机使用循环调度算法，例如 启动处理器0在时间片3的进程，然后启动处理器1在时间片3 的进程，… ·使每台处理机使用轮转调度算法，例如 所有的处理机首先运行时间片0中的进程一段时间，然后运行 时间片1中的进程一段时间 ● 算法可以用一个广播消息来通知所有处理机在何时进 行进程切换，以便保证时间片的同步 。 将同一组内所有进程都放在不同处理机上同一个时间 片内并保证同一组内的所有进程同时被调度运行这样 可以获得N倍的并行度，并使通信吞吐率达到最大
3.3 分布式进程调度 协同进程调度算法—基本思想 ⚫ 对每台处理机使用循环调度算法,例如 ⚫ 启动处理器0在时间片3的进程,然后启动处理器1在时间片3 的进程,… ⚫ 使每台处理机使用轮转调度算法,例如 ⚫ 所有的处理机首先运行时间片0中的进程一段时间,然后运行 时间片1中的进程一段时间 ⚫ 算法可以用一个广播消息来通知所有处理机在何时进 行进程切换，以便保证时间片的同步。 ⚫ 将同一组内所有进程都放在不同处理机上同一个时间 片内并保证同一组内的所有进程同时被调度运行这样 可以获得N倍的并行度，并使通信吞吐率达到最大
处理机 01234567 为了提高性能，4个必须 时间片 0 × × 通信的进程应该分别放入 1 X × 处理机1、2、3、和4的时 2 × × × 间片3中。 3 X X ·这种调度方法可以与MICROS 4 X X × 使用的层次式进程管理算法 5 × X 结合起来使用，只要每一个 系主任都保存他属下教师的矩阵，对矩阵中的进程 分配时间片，并广播时间片同步消息即可
⚫ 为了提高性能，4个必须 通信的进程应该分别放入 处理机1、2、3、和4的时 间片3中。 ⚫ 这种调度方法可以与MICROS 使用的层次式进程管理算法 结合起来使用，只要每一个 系主任都保存他属下教师的矩阵，对矩阵中的进程 分配时间片，并广播时间片同步消息即可 × 处理机 时间片 0 1 2 3 4 5 6 7 0 1 2 3 4 5 × × × × × × × × × × × × ×
3.4分布式容错系统 当一个系统没有完成它应该完成的任务，我们 将其称之为失败或失效。例如， 在超市的分布式订购系统中，一个失败有可能导致 罐装豆子缺货。 而在一个分布式航空交通指挥系统中，一个失败可 能会导致一场巨大的灾难！ ● 随着分布式计算机系统广泛应用于安全要求较 高的场合，防止失效就变得越来越重要了
3.4 分布式容错系统 ⚫ 当一个系统没有完成它应该完成的任务，我们 将其称之为失败或失效。例如， ⚫ 在超市的分布式订购系统中，一个失败有可能导致 罐装豆子缺货。 ⚫ 而在一个分布式航空交通指挥系统中，一个失败可 能会导致一场巨大的灾难！ ⚫ 随着分布式计算机系统广泛应用于安全要求较 高的场合，防止失效就变得越来越重要了
3.4分布式容错系统 3.4.1部件错误 。计算机中的部件错误可能会引起系统的失效， 这些部件包括处理机、内存、输入输出设备、电缆 或者软件等。 这种部件错误实际上就是一个故障。它产生的 原因是多方面的，例如， 设计错误、制造错误、编程错误、物理损坏、时钟 不准、环境恶劣、操作错误、非法输入、线路咬坏 等等。 当然，并不是所有的错误都会立即导致系统失 效
3.4 分布式容错系统 3.4.1 部件错误 ⚫ 计算机中的部件错误可能会引起系统的失效， ⚫ 这些部件包括处理机、内存、输入输出设备、电缆 或者软件等。 ⚫ 这种部件错误实际上就是一个故障。它产生的 原因是多方面的，例如， ⚫ 设计错误、制造错误、编程错误、物理损坏、时钟 不准、环境恶劣、操作错误、非法输入、线路咬坏 等等。 ⚫ 当然，并不是所有的错误都会立即导致系统失 效