操作系统原理6-处理机管理-华中科技大学计算机学院

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