第四章 任务分配与调度.pptVIP

第四章 任务分配与调度 §4.1 多机操作系统概述 1. 主要特征 并行性——多机操作系统的主要目标是增强程序执行的并行性，以获得更高的系统处理能力，提高系统的运算速度，满足各应用领域对计算机系统性能的需求 分布性—— 任务分布——问题分解后，分解成为多个子任务，分配到不同的处理机上运行 控制分布——处理机结点由自己的操作系统或管理程序管理和控制本结点的资源和进程 资源分布——系统所有资源分布在各结点上，便于各进程对资源的共享 通信与同步——存在结点内并发进程之间的同步和通信，各不同结点进程之间需要同步和通信 系统容错——当系统中某一个部件或结点发生故障，系统应能动态重新组合，降级使用 2. 多机操作系统分类 基本特点： 要求主处理机速度快，能使各从处理机尽可能处于“忙”状态 由于只有一台处理机进行管理，不存在访问各种文件和表格的冲突问题 不要求各管理程序模块编写为可重入结构 软硬件结构简单，但灵活性差 一旦主处理机发生故障，系统瘫痪 处理较多短任务时，增大管理工作量，主机负担重，系统效率低。 适用于由功能相差很大的处理机组成的非对称系统及工作负载不是太重的情况 管理程序的代码必须是可重入的，或者是为每个处理机装入专用的管理程序副本 某个处理机出了故障不一定会引起整个系统瘫痪，但恢复困难。 难以处理系统负载平衡 适合于松散耦合的多处理机系统 浮动管理——主处理机可以从一个处理机浮动到另一个处理机，任何处理机均可成为主处理机。 在同一时间里可以有多个处理机处于管态，可能发生访问表格、数据冲突，用互斥访问解决。 OS对处理机是透明的，并有较高的可靠性及灵活性，较难设计。 当某台处理机发生故障，易于降级使用。 适用于同构型多机系统。对于异构型多处理系统，OS设计将更困难。 §4.2 任务分配——调度策略 1、 概述 调度——为了优化某个目标函数，在一组具有任意特性的处理机中对一组进程进行调度。调度主要作出两个决定： 决定把程序和数据分配到物理存储器的什么位置 决定每个进程在哪个处理机上运行 调度算法是对一组给定进程进行调度的过程，目的是研究处理机的分配和进程调度技术，以达到使用最少数量的处理机在最短时间内完成并行程序。 调度算法效率： 当调度算法可以描述为一个多项式算法，效率较高 当调度算法可以描述为一个指数算法，效率较低 与调度相关的一些性能指标（参数） 最小完成时间 所需最少处理机数目 最小平均流 处理机最大利用率 处理机最小空闲时间 一般情况下，寻找最优的调度算法不一定是最好的调度算法或不存在最优调度算法。所以最优调度算法往往指为合理的调度算法 长期进程调度——选择和激活一个新进程使其进入处理环境 短期进程调度——选择一个进程送入所分配的处理机 两类调度： 确定性调度——在求解问题前必须给出表示问题特征所需要的所有信息，主要有每个任务的运行时间和各任务之间的关系 不确定性调度——系统运行过程中根据系统状态对任务进行分配 在确定性调度中，任务的执行时间很难直接给出。一般是最大任务的执行时间或估计值，由于任务执行时间不确切，造成系统调度效率较低。 在不确定性调度中，使各处理机尽可能处于“忙”状态。可以有效利用系统资源，但会增加系统额外开销。 两种调度方法： 抢先调度——一个任务完成之前允许被打断，以后可以接续恢复执行的调度 非抢先调度——当一台处理机分配给某个任务后，该处理机为该任务提供服务直至该任务完成 2、确定性调度 进程调度过程往往采用Gantt图表示。 非抢先调度 给定一个任务图，结点表示子任务，有向线表示各子任务之间关系，结点右侧数字表示子任务的运行时间。 从上图可以看出，处理机空闲时立即分配任务不一定获得最小完成时间。 最早调度策略——从开始结点计算结点的最早分配时间 最晚调度策略——从结束结点推算计算最晚调度时间 一个任务图的任务分配是一个网络规划问题 一个任务图，可由图G=(T,Q）表示： T={t1,t2,t3,……….tn} T为任务集 ti为结点权，表示子任务的运行时间。 Q={q1,q2,q3,……. qm} Q为通信集 qj＝（ ti,tk)为 ti与 tk两个结点之间边的权，表示两个子任务之间的通信量。 确定性调度，结点权是个常数，不确定性调度结点权是不确定的数。 一个多机系统可由系统图H＝（P,E) 表示 P={p1,p2,……….Ps} P为处理机集 Pi为结点权，表示处理机速度 E={e1,e2,……… er} E通信链路集 ej为有向边权，表示两个处理机之间通信链路的带宽 最小完成时间的非抢先调度 HU调度算法： 设任务图为一棵根数，所有任务结点权为单位时间，可以解决： 给定处理机数目，决定执行任