中国科学技术大学计算机学院：《高级操作系统 Advanced Operating System》课程教学资源（PPT课件）第四章 分布式进程和处理机管理（分布式处理机分配算法）

高级操作系统 Advanced Operating System 熊焰 xIong@ustc.edu.cn ●●●●● 0551-63600689 中国科学技术大学计算机学院0

高级操作系统 Advanced Operating System 熊焰 yxiong@ustc.edu.cn 0551-63600689 中国科学技术大学计算机学院

●●● ●●●● ●●●●● ●●●● 第四章分布式进程和处理机管理 ●分布式系统模型 分布式处理机分配算法 ●分布式进程调度 ●分布式系统容错 ●实时分布式系统

第四章 分布式进程和处理机管理 ⚫ 分布式系统模型 ⚫ 分布式处理机分配算法 ⚫ 分布式进程调度 ⚫ 分布式系统容错 ⚫ 实时分布式系统

●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 处理机分配的理由 ●分布式系统包括多个处理机,具有较大的分布处理 能力。 个作业将产生多个任务或进程,它们需要分配在 多个处理机上并行执行,以充分利用分布式系统提 供的巨大处理能力。 因此,分布式系统需要一个良好的处理机分配算 法来决定每个进程或任务应分配到哪一个处理机上执 通常,这个算法被称为处理机分配算法或任务分 配算法(而不称作进程分配算法,尽管但两者的意思 完全相同)

4.2 分布式处理机分配算法 处理机分配的理由: ⚫ 分布式系统包括多个处理机，具有较大的分布处理 能力。 ⚫ 一个作业将产生多个任务或进程，它们需要分配在 多个处理机上并行执行，以充分利用分布式系统提 供的巨大处理能力。 因此，分布式系统需要一个良好的处理机分配算 法来决定每个进程或任务应分配到哪一个处理机上执 行，通常，这个算法被称为处理机分配算法或任务分 配算法（而不称作进程分配算法，尽管但两者的意思 完全相同）

●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 ●●●● 处理机分配的基本模型、假定和目标: 1)关于处理器: ●假定所有的机器都是相同的,至少是代码兼容的, 不同的只是运行速度 ●有些还假定系统具有多个互不相关的处理机池,每 个处理机池都是相同的

4.2分布式处理机分配算法 处理机分配的基本模型、假定和目标： 1）关于处理器： ⚫ 假定所有的机器都是相同的，至少是代码兼容的， 不同的只是运行速度。 ⚫ 有些还假定系统具有多个互不相关的处理机池，每 一个处理机池都是相同的

●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 2)关于互连拓扑: ●假定系统是完全互连的,即每一个处理机都可以与 其它任意一个处理机通信。 这并不表示每一个机器与其它任意一台机器之间都有 线路直接连接,这个假定只是意味着每一对机器都可 以互相通信。至于消息是如何从一台机器到达另一台 机器的问题只是低层通信软件的事,处理机分配算法 无需考虑。但有一些处理机分配算法利用了网络的广 播或者多播的特性

4.2分布式处理机分配算法 2）关于互连拓扑： ⚫ 假定系统是完全互连的，即每一个处理机都可以与 其它任意一个处理机通信。 ⚫ 这并不表示每一个机器与其它任意一台机器之间都有 线路直接连接，这个假定只是意味着每一对机器都可 以互相通信。至于消息是如何从一台机器到达另一台 机器的问题只是低层通信软件的事，处理机分配算法 无需考虑。但有一些处理机分配算法利用了网络的广 播或者多播的特性

●●● ●●●● ●●●●● 4.2分布式处理机分配算法 ●●●● ●●0●● ●●●0 ●●●● 新进程的产生和处理机的分配: 当一个运行中的进程决定创建一个子进程时,产生了 下列工作: 在有些情况下,创建进程是由系统的命令解释程序 (即she)来完成的。它为用户执行其指定的命 令所对应的程序。 ●而在另一些情况下,用户进程本身也可以创建一个 或者多个子进程,以获得较高的系统性能。 ●对新进程必须考虑分配到哪个处理器上运行

4.2分布式处理机分配算法 新进程的产生和处理机的分配： ⚫ 当一个运行中的进程决定创建一个子进程时，产生了 下列工作： ⚫ 在有些情况下，创建进程是由系统的命令解释程序 （即shell）来完成的。它为用户执行其指定的命 令所对应的程序。 ⚫ 而在另一些情况下，用户进程本身也可以创建一个 或者多个子进程，以获得较高的系统性能。 ⚫ 对新进程必须考虑分配到哪个处理器上运行

●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 ●●●● 处理机分配策略可以分为两大类: 1)非迁移的 2)可迁移的 第一类是非迁移的( nonmigratory) ●在非迁移策略中,当创建一个进程时,系统就决定 它被分配到哪台处理机上。一旦一个进程被分配到 台机器上,那么,它就在那台机器上运行,一直 到终止,不管这台处理机的负载是多么的重,而别 的处理机是多么的空闲,它都不能迁移到别的处理 机上运行

4.2分布式处理机分配算法 处理机分配策略可以分为两大类： 1）非迁移的 2）可迁移的 ⚫ 第一类是非迁移的（nonmigratory） ⚫ 在非迁移策略中，当创建一个进程时，系统就决定 它被分配到哪台处理机上。一旦一个进程被分配到 一台机器上，那么，它就在那台机器上运行，一直 到终止，不管这台处理机的负载是多么的重，而别 的处理机是多么的空闲，它都不能迁移到别的处理 机上运行

●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 第二类是可迁移的( migratory) °对于可迁移策略来说,一个进程即使已经被分配到 台处理机上并已经运行了一段时间,如果其负载 变重了,它也可以动态地迁移到其它轻负载的处理 机上继续运行。 ●虽然可迁移策略可以使系统达到良好的负载平衡, 但实现起来却异常复杂

4.2分布式处理机分配算法 ⚫ 第二类是可迁移的（migratory） ⚫ 对于可迁移策略来说，一个进程即使已经被分配到 一台处理机上并已经运行了一段时间，如果其负载 变重了,它也可以动态地迁移到其它轻负载的处理 机上继续运行。 ⚫ 虽然可迁移策略可以使系统达到良好的负载平衡， 但实现起来却异常复杂

●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●0 ●●●● ●处理机分配算法必须尽可能优化。否则,我们 完全可以随机地或按数字顺序来分配处理机。 不同系统的优化内容是不一样的 优化目标1:提高处理机利用率 优化目标2:最小化平均响应时间

4.2分布式处理机分配算法 ⚫ 处理机分配算法必须尽可能优化。否则，我们 完全可以随机地或按数字顺序来分配处理机。 ⚫ 不同系统的优化内容是不一样的 ⚫ 优化目标1：提高处理机利用率 ⚫ 优化目标2：最小化平均响应时间

●●● ●●●● ●●●●● ●●●● 4.2分布式处理机分配算法 ●●0●● ●●●● ●●●● ●第一个优化目标就是: 尽量提高处理机的利用率 处理机的利用率 执行用户工作的周期数/小时 执行用户的周期数/小时+dk周期数/小时 让处理机在每个小时内执行用户工作的周期数尽 可能地多。 ●换句话说,要尽量减少空闲处理机周期数

4.2分布式处理机分配算法 ⚫ 第一个优化目标就是： 尽量提高处理机的利用率 ⚫ 让处理机在每个小时内执行用户工作的周期数尽 可能地多。 ⚫ 换句话说，要尽量减少空闲处理机周期数。 执行用户的周期数 小时 周期数 小时 执行用户工作的周期数 小时 处理机的利用率 / idle / / + =