2.2、线程的调度

1、调度的概念

在多道程序系统中，进程的数量往往多于处理器的个数，进程争用处理器的情况在所难免。处理器调度是对处理器进行分配，就是从就绪队列中，按照一定的算法，选择一个进程并将处理器分配给他运行，以实现进程的并发执行。

处理器调度是多道程序操作系统的基础，它是操作系统设计的核心问题。

一个作业从提交开始知道完成，往往要经历一下三级调度：

1）作业调度。作业调度又称高级调度：其主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个或多个作业，给他们分配内存、输入输出设备等必要的资源。并建立相应的进程，以使他们获得竞争处理器的权利。

多道批处理系统中大多配有作业调度，而其它系统中通常不需要配置作业调度。作业调度的执行频率较低，通常为几分钟一次。

2）中级调度。中级调度又称内存调度。引入中级调度视为了提高内存利用率和系统吞吐率，为此，应使那些暂时不能运行的进程调至外存等待，把此时的进程状态称为挂起状态。当他们已具备运行条件且内存有稍有空闲时，由中级调度来决定，吧外存上那些已具备运行条件的就绪进程，在重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。

3）进程调度。进程调度又称为低级调度，其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理器分配给它。进程调度是操作系统中最基本的一中调度，在一般操作系统中都不需配置进程调度。进程调度的频率很高，一般几十毫秒一次。

作业调度从外存的后备队列中选择一批作业进入内存，为他们建立进程。这些进程被送入就绪队列。进程调度从就绪队列中选出一个进程，并把其状态改为运行状态，把CPU分配给它。中级调度是位于高级调度和低级调度之间的一种调度。为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。当内存空间宽松式，通过中级调度选择具备运行条件的进程，将其唤醒。

2、调度的时机、切换与过程

进程调度和切换程序是操作系统内核程序。当请求调度的事件发生后，才可能会运行进程调度程序，当调度了新的就绪进程后，才会去进行进程间的切换。

现在操作系统中，不能进行进程的调度与切换的情况有以下几种：

1） 在处理中断的过程中：中断处理过程复杂，在实现上很难做到，而且中断处理时系统工作的一部分，逻辑上不属于某一进城，不应被剥夺处理器资源。

2） 进程在操作系统内核程序临界区中：进入临界区后，需要独占式的访问共享数据，理论上必须加锁，以防止其他并行程序的进入，在解锁前不应该切换到其他进程，以加快该共享数据的释放。

3） 其他需要完全屏蔽中断的原子操作过程中：如加锁、解锁、中断现场保护、恢复等等源自操作。在原子过程中，连中断都要屏蔽，更不应该进行进程的切换。

如果在上述过程中发生了引起调度的条件，并不能马上进行调度和切换，应置系统请求调度标志，知道上述过程结束后才能进行相应的调度和切换。

应该进行进程的调度与切换的情况有：

1） 当发生引起调度条件且当前进程无法继续运行下去时，可以马上进行调度与切换。如果操作系统只在这种情况下进行进程调度，就是非剥夺调度。

2） 当中断处理结束后或自陷处理结束后，返回被中断进程的用户态程序执行现场前，若置上请求调度标志，即可马上进行进程调度与切换。如果操作系统支持这种情况下的运行调度程序，就实现了剥夺方式的调度。

进程切换往往在调度完成后立刻发生，它要求保存源进程当前切换点的县城信息，恢复被调度进程的现场信息。现场切换时，操作系统内核将远近程的现场信息推入到当前进程的内核对战来保存他们，并更新堆栈指针。内核完成从新进程的内核栈中装入新进程的县城信息、更新当前运行进程空间指针、重设PC寄存器等相关工作之后，开始运行新的进程。

3、进程调度方式

所谓进程调度方式是指当某一个进程正在处理器上执行时，若有某个更为重要或紧迫的进程需要处理，既有优先权更高的进程进入就绪队列，此时应如何分配处理器。通常有一下两种进程调度方式：

（1） 非剥夺调度方式

非剥夺调度方式又称为非抢占调度方式，是指当一个进程正在处理器上执行时，即使有某个更为重要或紧迫的进程进入就绪状态，仍然让正在执行的进程继续执行，知道该进程完成或发生某种时间而进入阻塞状态时，才把处理器分配给更为重要或紧迫的进程。

（2） 剥夺调度方式

剥夺调度方式又称为抢占方式，是指当一个进程正在处理器上执行时，若有某个更为重要或紧迫的进程需要使用处理器，则立即暂停正在执行的进程，将处理器分配给这个更为重要或紧迫的进程。

“剥夺”不是一种任意性行为，必须遵循一定的原则：优先权原则，短进程优先原则和时间片原则。

4、调度的基本准则

不同的调度算法具有不同的特性，在选择调度算法时，必须考虑算法所具有的特性。为了比较处理器调度算法的性能，人们提出很多评价准则，下面介绍主要的几种准则：

（1） CPU利用率

CPU是计算机系统中最重要的资源之一，所以应尽可能使CPU保持在忙状态，是这一资源利用率最高。

（2） 系统吞吐量

系统吞吐量表示单位时间内CPU完成作业的数量。长作业需要消耗较长的处理器时间，因此会降低系统的吞吐量。而对于短作业，他们所需要消耗的处理器时间端，因此能提高系统的吞吐量。调度算法和方式的不同，也会对系统的吞吐量产生较大的影响。

（3） 周转时间

周转时间是指从作业提交到作业完成所经历的时间，包括作业等待、在就绪队列中排队、在处理器上运行以及进行输入输出操作所花费的时间的总和。

作业的周转时间=作业完成时间-作业提交时间

（4） 等待时间

等待时间是指进程处于等处理器状态时间之和，等待时间越长，用户满意度越低。处理器调度算法实际上并不影响作业执行或输入输出操作时间，只影响作业在就绪队列中等待所花的时间。因此，衡量一个调度算法优劣常常只需简单地考察等待时间。

（5） 响应时间

响应时间是指从用户提交请求到系统首次产生响应所有的时间。在交互式系统中，周转时间不可能是最好的评测准则，一般采用响应时间作为衡量调度算法的重要准则之一。从用户的角度来看，调度策略应尽量降低响应时间，使响应时间处在用户能够接受的范围之内。

5、典型的调度算法

通常系统的设计目标不同，所采用的调度算法也不同。在操作系统中存在多种调度算法，其中有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的调度算法两者都适用。下面介绍几种常用的调度算法：

（1） FIFS先来先服务调度算法

特点：算法简单，但是效率低；有利于长作业，不利于短作业；有利于CPU繁忙型作业而不利于IO繁忙型作业。

（2） SJF短作业优先调度算法

短作业（进程）优先调度算法是指对短作业祸端进程优先调度的算法。短作业优先调度算法是从后备队列中选择一个或若干个估计运算时间最短的作业，将他们呢掉入内存运行。

SJF调度算法的缺点：

1） 该算法对长作业不理。

2） 该算法完全未考虑作业的紧迫程度

3） 由于作业的长短只根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意的缩短其作业的估计运行时间，致使该算法不一定能真正做到算作业优先调度。

4） 注意：SJF调度算法的平均等待时间、平均周转时间最少。

（3） 优先级调度算法

（4） 高响应比优先调度算法

高响应比优先调度算法主要用于作业调度。同时考虑从每个作业的等待时间和估计需要运行的时间。

（5） 时间片轮转调度算法

时间片轮转调度算法主要适用于分时系统。

（6） 多级反馈队列调度算法

多级反馈队列调度算法主要是时间片轮转调度算法和优先级调度算法的综合和发展。通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。