操作系统课件5

第六章处理机调度 6 1处理机的多级调度 一 批处理系统中的处理机调度在多用户批处理操作系统中 对处理机的分配分为两级 作业调度和进程调度 二 多任务操作系统中的处理机调度系统将用户提交的任务处理为进程 一个进程又可以创建多个子进程 这些进程都是分配资源和处理机的单位 三 多线程操作系统中的处理机调度系统为进程分配它所需要的资源 而处理机的分配单位则为线程 6 2作业调度6 2 1作业的状态 提交状态 后备状态 执行状态 完成状态 6 2 2作业调度的功能 作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变 作业调度功能 1 记录已进入系统的各作业的情况 JCB JobControlBlock 2 按一定的调度算法 从后备作业中选择一个或几个作业进入系统内存 3 为被选中的作业创建进程 并且为其申请系统资源 4 作业结束后作善后处理工作 6 2 3作业控制块 JCB JobControlBlock 每个作业进入系统时由系统为其建立一个作业控制块JCB JobControlBlock 它是存放作业控制和管理信息的数据结构 主要信息见右图 6 2 4调度性能的衡量 作业调度算法规定了从后备作业中选择作业进入系统内存的原则 这些原则的性能如何 就是本节所讨论的问题 一 确定调度算法时应考虑的因素1 应与系统的整体设计目标一致2 考虑系统中各种资源的负载均匀3 保证作业的执行4 对一些专用资源的使用特性的考虑 二 调度性能的衡量通常采用平均周转时间和带权平均周转时间作业的周转时间 ti tci tsiti 作业周转时间tci 作业完成时间tsi 作业提交时间 6 2 5先来先服务调度算法和短作业优先调度算法 先来先服务调度算法 先来先服务算法是按作业来到的先后次序进行调度的 换句话说 调度程序每次选择的作业是等待时间最久的 而不管作业的运行时间的长短 这种调度算法突出的优点是实现简单 但效率较低 在一些实时的系统和一般应用程序中采用这种算法的较多 短作业优先调度算法 短作业优先调度算法考虑作业的运行时间 每次总是选择一个运行时间最小的作业调入内存 系统 在一般情况下这种调度算法比先来先服务调度算法的效率要高一些 实现相对先来先服务调度算法要困难些 如果作业的到来顺序及运行时间不合适 会出现饿死现象 例如 系统中有一个运行时间很长的作业JN 和几个运行时间小的作业 然后 不断地有运行时间小于JN的作业的到来 这样 作业JN就得不到调度而饿死 另外 作业运行的估计时间也有问题 11 6 2 6其它几种调度算法 响应比高者优先调度算法 先来先服务和短作业优先算法都有其片面性 先来先服务调度算法只考虑作业的等待时间 而忽视了作业的运行时间 短作业优先算法则相反 只考虑了作业的运行时间 而忽视了作业的等待时间 响应比高者优先调度算法是介于这两种算法之间的一种拆衷的算法 这样算法从理论上讲是比较完备的 但作业调度程序要统计作业的等待时间 使用用户的估计的运行时间 并要作浮点运算 这是系统程序最忌讳的 浪费大量的计算时间 这是系统程序所不允许的 优先数调度算法优先数调度算法是终合考虑各方面的因素 作业等待时间 运行时间 缓急程度 系统资源使用等 给每个作业设置一个优先数 调度程序总是选择一个优先数最大 或者最小 的作业调入 系统 内存 这种算法实现的困难在于如何综合考虑 这些因素之间的关系怎样处理 6 3进程调度6 3 1调度 分派结构 处理机分配由调度和分派两个功能组成 调度 组织和维护就绪进程队列 包括确定调度算法 按调度算法组织和维护就绪进程队列 分派 是指当处理机空闲时 从就绪队列队首中移一个PCB 并将该进程投入运行 调度与进程控制和进程通信的功能有密切的联系 当一个进程阻塞时 这种进程将进入相应的等待队列中 并让出CPU 调用进程分派程序选择一个就绪进程占用CPU 当一进程被唤醒时 这种进程将插入到就绪进程队列中 在一般的操作系统教材中把上述功能称为进程调度 6 3 2进程调度的功能 1 记录和保持系统中所有进程的有关情况和状态特征有关进程调度的信息是记录在PCB中的 在进程调度中用到的主要是进程的状态 调度优先级 优先数 就绪进程队列等 2 决定分配 处理机 策略确定进程调度的策略 例如 先来先服务 优先数调度策略 调度策略的不同 组织就绪进程队列的方式也不同 先来先服务调度策略 就绪队列要按等待时间大到小的顺序排队 优先数调度 则就绪进程队列要按优先数的升序 或降序 的方式排队等等 3 实施处理机的分配当现行程序不能再继续运行 或者有理由认为应把处理机用于另一进程时 就进人处理机分派程序 调度时机可有以下几种可能 1 进程完成其任务时 2 在一次管理程序调用之后 该调用使现行程序暂时不能继续运行时 3 在一次出错陷人之后 该陷入使现行进程在出错处理时被挂起时 4 在分时系统中 当进程使用完规定的时间片 时钟中断使该进程让出处理机时 5 在采用可剥夺调度方式的系统中 当具有更高优先级的进程要求处理机时 处理机分派程序的操作是非常简单的 它包括如下内容 1 从选中进程的pcb中恢复现场 2 控制转向该进程 它从刚恢复的程序计数器所指示的指令地址开始执行 总而言之 进程调度包括 调度算法的选择 调度算法 调度时机的选择 调度时机 实施进程调度 调度程序 6 3 3调度方式 所谓的调度方式是指 当一进程正在处理机上执行时 若有某个更为 重要而紧迫 的进程需要进行处理 亦即 若有优先数更高的进程进人就绪队列时 如何分配处理机 两种分配方式 1 非剥夺调度方式2 剥夺调度方式此外 还有可选择剥夺 6 3 4调度用的进程状态变迁图 在这个图中新创建的进程进入低优先就绪状态 一个运行进程因时间片到 实际上是计算量大的进程 而转换成低优先就绪 进程因等待I O完成而转换成高优就绪 6 3 5进程优先数调度算法 优先数调度算法是目前操作系统广泛采用的一种进程调度算法 这种算法按照某种原则由系统 或用户 或系统与用户结合 赋予每个进程一个优先数 在处理机空闲时 进程调度程序就从就绪进程中选择一个优先数最大 或者最小 的进程占用CPU 该进程就从就绪状态转换成运行状态 采用这种调度算法的关键是如何确定进程的优先数 一个进程的优先数确定之后是固定的 还是随着该进程运行的情况的变化而变化 静态 进程的优先数在进程创建时确定后就不再变化确定进程优先数 系统确定 运行时间 使用资源 进程的类型 用户确定 紧迫程度 计费与进程优先数有关 系统与用户结合 用户可以为本用户的进程设置优先数 但不是作调度用 系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数 动态进程优先数 系统在运行的过程中 根据系统的设计目标 不断地调整进程的优先数 这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标 6 3 6循环轮转调度 循环轮转调度实际上是一种先来先服务算法的调度算法 它把系统的响应时间分成大小相等 或不相等 的时间单位 称为时间片 每个进程被调度到后 占用一个时间片 片用完后 该进程让出CPU 由运行状态转换成就绪状态 排在就绪队列的队尾 多个进程循环轮转 系统按进程转换成就绪状态的时间的降序排队 调度程序每次调度 总是从队首移出一进程的PCB 然后 将此进程投入运行 由就绪状态转换成运行状态 一个运行时间片到的进程从运行状态转换成就绪状态后 排在就绪队列的队尾 评价 优点是实现简单 系统开销小缺点是不灵活 当系统中进程较少时 系统开销变大由于该算法简单易于实现 且系统开销较小 早期的分时操作系统和目前一些应用系统中广泛采用了这种调度算法 二 可变时间片轮转调度为了克