1第六章 处理机管理2第六章 处理机调度 6.1 处理机的二级调度宏观上：作业调度 微观上：进程调度3P106 11sb:缓冲区s中是否有空，初值为1； tb: 缓冲区t中是否有空，初值为1； sa:缓冲区s中是否有数据，初值为0； ta: 缓冲区t中是否有数据，初值为0；45这样做程序运行的结果是正确的，但并行工作的程度大 大降低，如何改？67对于 1 p1与P2、P3、 P4同步（三个信号灯） 对于 2 P3、P4与p5同 步（二个信号灯） 信号灯初值均为186.2 作业调度 6.2.1作业调度的功能作业调度的主要任务是完成作业从后备状态到执行状态 和从执行状态到完成状态的转变。 作业调度功能： 1.记录已进入系统的各作业的情况（JCB，Job Control Block）； 2.按一定的调度算法，从后备作业中选择一个或几个作 业进入系统内存； 3.为被选中的作业创建进程，并且为其申请系统资源； 4.作业加束后作善后处理工作。96.2 作业调度 6.2.2 作业控制块（JCB，Job Control Block）每个作业进入系统时由 系统为其建立一个作业 控制块JCB（Job Control Block)，它是 存放作业控制和管理信 息的数据结构，主要信 息见右图。106.2.3 调度性能的衡量作业调度算法规定了从后备作业中选择作业进入系统内 存的原则，这些原则的性能如何，就是本节所讨论的 问题。 一、确定调度算法时应考虑的因素 1.应与系统的整体设计目标一致 2.考虑系统中各种资源的负载均匀 3.保证作业的执行 4.对一些专用资源的使用特性的考虑116.2.3 调度性能的衡量二、调度性能的衡量 通常采用平均周转时间和带权平 均周转时间 作业的周转时间：ti = tci-tsiti:作业周转时间tci：作业完成时间tsi: 作业提交时间126.2.3 调度性能的衡量 136.2.4 先来先服务调度算法和短作业优先调度算法先来先服务调度算法： 先来先服务算法是按作业来到的先后次序进行调 度的，换句话说，调度程序每次选择的作业是 等待时间最久的，而不管作业的运行时间的长 短。这种调度算法突出的优点是实现简单，效 率软低，在一些实际的系统和一般应用程序中 采用这种算法的较多。146.2.4 先来先服务调度算法和短作业优先调度算法短作业优先调度算法： 短作业优先调度算法考虑作业的运行时间，每次 总是选择一个运行时间最小的作业调入内存（ 系统）.在一般情况下这种调度算法比先来先服务调度算法的效率要高一 些。实现相对先来先服务调度算法要困难些，如果作业的到来顺 序及运行时间不合适，会出现饿死现象，例如，系统中有一个运 行时间很长的作业JN，和几个运行时间小的作业，然后，不断地 有运行时间小于JN的作业的到来，这样，作业JN就得不可调度而 饿死。另外，作业运行的估计时间也有问题。156.2.4 先来先服务调度算法和短作业优先调度算法 166.2.5 其它几种调度算法响应比高者优先调度算法： 先来先服务和短作业优先算法都有其片面性，先来先服务调度算法只考虑作 业的等待时间，而忽视了作业的运行时间，短作业优先算法则相反，只考虑 了作业的运行时间，而忽视了作业黪等待时间。响应比高者优先调度算法是 介于这两种算法之间的一种拆衷的算法。176.2.5 其它几种调度算法 响应比高者优先调度算法这样算法从理论上讲是比较完备的，但作 业调度程序要统计作业的等待时间，使 用用户的估计的运行时间，并要作浮点 运算（这是系统程序最忌讳的）浪费大 量的计算时间，这是系统程序所不允许 的。186.2.5 其它几种调度算法优先数调度算法 优先数调度算法是终合考虑各方面的因素（作业 等待时间、运行时间、缓急程度，系统资源使 用等），给每个作业设置一个优先数，调度程 序总是选择一个优先数最大（或者最小）的作 业调入（系统）内存。这种算法实现的困难在 于如何终合考虑，这些因素之间的关系怎样处 理。196.2.5 其它几种调度算法均衡调度算法 均衡调度算法就是一种更为理想化的调度算法， 如何实现就更困难，并且算法本身的开销有时 会远选大于先来先服务和小作业优先调度算法 的不足，这也是这两种算法被众多系统采用的 最根本的原因。206.3 进程调度 6.3.1 调度/分派结构处理机分配由调度和分派两个功能组成。 调度：组织和维护就绪进程队列。包括确定调度算法 、按调度算法组织和维护就绪进程队列。 分派：是指当处理机空闲时，从就绪队列队首中移一 个PCB，并将该进程投入运行。 调度与进程控制和进程通信的功能有密切的联系，当一个进 程阻塞时，这种进程将进入相应的等待队列中，并让出CPU ，调用进程分派程序选择一个就绪进程占用CPU；当一进程 被唤醒时，这种进程将插入到就绪进程队列中。 在一般的操作系统教材中把上述功能称为进程调度。216.3.2 进程调度的功能1.记录和保持系统中所有进程的有关情况和状态 特征有关进程调度的信息是记录在PCB中的，在进程调度中 用到的主要是进程的状态、调度优先级（优先数）、就绪进程队列等。226.3.2 进程调度的功能2.决定分配（处理机）策略 确定进程调度的策略，例如，先来先服务、优先数调度 策略，调度策略的不同，组织就绪进程队列的方式也 不同。先来先服务调度策略，就绪队列要按等待时间 大到小的顺序排队；优先数调度，则就绪进程队列要 按优先数的升疗（或降序）的方式排队。等等。236.3.2 进程调度的功能3.实施处理机的分配总而言之，进程调度包括： 调度算法的选择（调度算法） 调度时机的选择（调度时机）实施进程调度（调度程序）246.3.2 进程调度的功能调度时机（UNIX系统中）： （1）进程自动放弃处理机： 当进程进入高低优先级睡眠状态时（在sleep()程序中）； 在进程进入暂停状态时（在stop()程序中）； 进程进入僵死状态时 （在exit()程序中）；256.3.2 进程调度的功能在中断自陷总控程序中，当先前态是用户态，且runrun标志大于0， 则进行强迫调度，强行剥夺现运行进程的处理机，转进程调度程 序。 runrun标志大于0是说明系统中处于就绪状态的进程的优先级高于现 运行进程的优先级，这时要进行强迫调度，出现这种情况有两种 可能：高低优先级睡眠进程被唤醒后其优先级高于现运行进程； 当一个进程占用一段时间的CPU后，它的优先级要降低，造成现运 行进程的优先级低于系统中的其它就绪进程（时间片到是其中的 一种情况）。 教材p136进程调度的几种时机是一般操作系统原理中的概念。 2）强迫调度266.3.2 进程调度的功能实施进程调度的程序称为进程调度程序（或称调度程序） ，在通常的操作系统原理中，该程序属于系统进程的执行程 序，有的操作系统是把进程调度程序作一个特别的处理，如 早期的操作系统中把进程调度程序称为交通控制程序，不属 于系统中的任何进程。在UNIX系统中，进程调度程序swtch( )分属 个不同的进程，即调用swtch( )的进程让出处理 机的进程）、0进程、被调度到的进程。276.3.3 调度方式（略） 286.3.4 调度用的进程状态变迁图在这个图中新创建的进 程进入低优就绪状态， 一个运行进程因时间片 到（实际上是计算量大 的进程）而转换成低优 就绪；进程因等待I/O 完成而转换高优就绪.296.3.4 调度用的进程状态变迁图调度程序首先看高优就绪 进程队列是否为空，若不 为空，则从高优就绪进程 中选择一个进程占用CPU ，否则，从低优就绪队列 中选择。 这种调度效果是 能充分地利用系统资源。 为什么？ UNIX系统的进程调度 状态变迁图，与前一 种调度变迁图有着异 曲同功的效果。306.3.5 进程优先数调度算法优先数调度算法是目前操作系统广泛采用的一种进 程调度算法，这种算法按照某种原则由系统（或用户 、或系统与用户结合）赋予每个进程一个优先数，在 处理机空闲时，进程调度程序就从就绪进程中选择一 个优先数最大（或者最小）的进程占用CPU（该进程 就从就绪状态转换成运行状态）。采用这种调度算法的关键是如何确定进程的优先数 、一个进程的优先数确定之后是固定的，还是随着该 进程运行的情况的变化而变化。316.3.5 进程优先数调度算法静态： 进程的优先数在进程创建时确定后就不再变化确定进程优先数： 系统确定：（运行时间、使用资源，进程的类型） 用户确定：（紧迫程度，计费与进程优先数有关） 系统与用户结合（用户可以为本用户的进程设置优先数 ，但不是作调度用，系统还要根据系统情况把用户设 置的进程优先数作为确定进程优先数的一个参数）326.3.5 进程优先数调度算法动态进程优先数：系统在运行的过程中，根据系统的设计目标，不断 地调整进程的优先数，这种方法的优点是能比较客 观地反映进程的实际情况和保证达到系统设计目标 。336.3.6 循环轮转调度循环轮转调度实际上是一种先来先服务算法的调度算法 ，它把系统的响应时间分成大小相等（或不相等）的 时间单位，称为时间片。每个进程被调度到后，占用 一个时间片，片用完后，该进程让出CPU，由运行状态 转换成就绪状态，排在就绪队列的队尾。多个进程循 环轮转。346.3.6 循环轮转调度 356.3.6 循环轮转调度系统按进程转换成就绪状态的时间的降序排队，调度程序每次调 度，总是从队首移出一程的PCB，然后，将此进程投入运行（ 由就绪状态转换成运行状态）。一个运行时间片到的进程从运 行状态转换成就绪状态后，排在就绪队列的队尾。 评价： 优点是实现简单、系统开销小 缺点是不灵活，当系统中进程较少时，系统开销变大为什么？由于该算法简单易于实现，且系统开销较小，早期的分时操作 系统和目前一些应用系统中广泛采用了这种调度算法。366.3.6 循环轮转调度二、可变时间片轮转调度为了克服前种调度算法的缺点，人们设计出一种可变 时间片的调度算法，其思想是：时间片的大小是可变 的，系统可根据系统中当前的进程数来确定时间片的 大小。这种算法从理论上克服了系统中进程数很少时系统开 销大的缺点，但修改时间片的大小，统计系统进程的 数量也需要消耗系统时间，还有一个调整时间片大小 的周期，太大，等于是固定时间片，太小，系统开销 很大，得不尝失。376.4 UNIX系统的进程调度 6.4.1 UNIX调度算法我们从调度算法、调度时机、调度程序三个方面来分析 UNIX系统的进程调度。 一、调度算法UNIX系统采用优先数调度算法，每个进程有一个进 程优先数，p_pri是proc结构中的一个变量，其取值范 围是127127，其值越小，进程的优先级越高（即 ，调度程序总是从就绪状态的进程中选择一个优先数 最小的进程占用CPU）。386.4 UNIX系统的进程调度 6.4.1 UNIX调度算法优先数的确定： 1.系统设置在进程进入睡眠状态时，在SLEEP（）中设置将要进入 睡眠状态进程的优先数，当该进程被唤醒后，就以系 统给它设置的优先数去参与处理机的竟争。396.4 UNIX系统的进程调度 6.4.1 UNIX调度算法进程进入高优先级睡眠的原因： （1）0进程（100优先数）； （2）因资源请求得不到满足的进程，磁盘（80），打印机（20），； （3）等待块设备I/O完成的进程，（50）。进程进入低优先级睡眠的原因： (1）因等待字符设备I/O完成的进程，（020的优先数）； (2) 所有处于用户态运行进程，优先数一般情况下为大于100。这样做的目的是为什么？为使系统资源得到充分的利用，换句话说，是为了提高系统资 源的使用效率。406.4 UNIX系统的进程调度 6.4.1 UNIX调度算法2.优先数的计算 （1）计算公式：p_pri = 127, (p_cpu/16+p_nice+PUSER)其中：p_cpu 进程占用CPU的程度p_nice 用户通过系统调用nice(priority)设置的进程优先数。PUSER 常数，其