|
|
|
在多道程序操作系统中，经常会出现多个任务同时去竞争CPU的情形，换句话说，就是在系统的就绪队列中，有两个或多个任务同时处于就绪状态。假设在系统中只有一个CPU，而且这个CPU已经空闲下来了，现在的问题就是：对于就绪队列当中的那些任务，应该选择哪一个去运行？在操作系统当中，负责去做出这个选择的那一部分程序，就称为是调度器，而调度器在决策过程中所采用的算法，就称为是调度算法。如果从资源管理的角度来看，也可以把调度器看成是CPU这个资源的管理者。
|
|
|
|
|
|
|
|
任务调度的首要问题是何时进行调度，即调度发生的时机。一般来说，在以下几种情形下，可能会发生任务的调度。
|
|
|
|
（1）当一个新的任务被创建时，需要做出一个调度决策，是立即执行这个新任务还是继续执行父任务？
|
|
|
|
（2）当一个任务运行结束时，它不再占用CPU，这时调度器必须作出一个决策，从就绪队列中选择某个任务去运行。如果此时没有任务处于就绪状态，系统一般会调度一个特殊的空闲任务。
|
|
|
|
（3）当一个任务由于I/O操作、信号量或其他原因被阻塞时，也必须另选一个任务运行。
|
|
|
|
（4）当一个I/O中断发生时，表明某个I/O操作已经完成，而等待该I/O操作的任务将从阻塞状态变为就绪状态，此时可能需要做出一个调度决策，是立即执行这个新就绪的任务，还是继续执行刚才被中断的那个任务。
|
|
|
|
（5）当一个时钟中断发生时，表明一个时钟节拍已经结束。这时，可能会唤醒一些延时的任务，使它们变为就绪状态，也可能会发现当前任务的时间片已用完，从而把它变为就绪状态。在这些情形下，也需要调度器来重新调度。
|
|
|
|
|
|
任务调度的第二个问题是调度的方式，主要有两种方式：不可抢占调度和可抢占调度。
|
|
|
|
（1）不可抢占方式（non preemptive）。如果一个任务被调度程序选中，就会一直地运行下去，直到它因为某种原因（如I/O操作或任务间的同步）被阻塞了，或者它主动地交出了CPU的使用权。在不可抢占的调度方式下，当出现调度时机当中的前三种情形时，即新任务创建、任务运行结束及任务被阻塞，都有可能会发生调度。而对于第四种和第五种情形，即发生各种中断的时候，虽然也会有中断处理程序，但是它并不会去调用调度程序。因此，当中断处理完成后，又会回到刚才被打断的任务继续执行。
|
|
|
|
（2）可抢占方式（preemptive）。当一个任务正在运行的时候，调度程序可以去打断它，并安排另外的任务去运行。在这种调度方式下，对于调度时机当中的所有五种情形，都有可能会发生调度。另外，在其他的一些情形下，假设调度算法是按照任务的优先级来进行调度，那么一旦在就绪队列当中有任务的优先级高于当前正在运行的任务，就可能立即进行调度，转让CPU。
|
|
|
|
实时操作系统大都采用了可抢占的调度方式，使一些比较重要的关键任务能够打断那些不太重要的非关键任务的执行，以确保关键任务的截止时间能够得到满足。
|
|
|
|
|
|
在嵌入式操作系统当中，存在着多种调度算法，每一种算法都有各自的优点和缺点。因此，任务调度的第三个问题是调度算法的性能指标，即如何来评价一个调度算法的好坏。这些指标主要包括：
|
|
|
|
.响应时间：调度器为一个就绪任务进行上下文切换时所需的时间，以及任务在就绪队列中的等待时间；
|
|
|
|
|
|
.调度开销：调度器在做出调度决策时所需要的时间和空间开销；
|
|
|
|
.公平性：大致相当的两个任务所得到的CPU时间也应该是大致相同的。另外，要防止饥饿，即某个任务始终得不到处理器去运行；
|
|
|
|
.均衡性：要尽可能使整个系统的各个部分（CPU、I/O）都忙起来，提高系统资源的使用效率；
|
|
|
|
|
|
在这些指标当中，有一些是可以共存的，也有一些是相互牵制的。因此，对于一个实际的调度算法来说，这些指标不可能全部都实现，而是要根据系统的需要，有一个综合的权衡和折衷的过程。
|
|
|
|
|
|
（1）可抢占调度（preemptive scheduling）。允许任务执行中被其他任务抢占的调度程序，称作可抢占调度程序，其采用调度算法称作抢占式调度算法。抢占式调度提供了很大的灵活性，因为任务执行能被分割成任意的时间间隔来适应不同的执行方式，从而获得更高的处理器利用率。但进行可调度性分析时必须考虑现场切换的时间，而且这一时间必须显著的小于任务的执行时间，否则会浪费大量的处理器时间用于抢占造成的现场切换。使用抢占式调度算法时，每个任务使用一个栈空间，所以还会消耗较多的内存资源。
|
|
|
|
（2）不可抢占调度（non-preemptive scheduling）。不允许任务执行中被其他任务抢占的调度程序称作不可抢占式调度程序，使用的算法称作非抢占式调度算法。在不可抢占式调度中，任务一旦执行就不会被其他任务抢占，因此使用了比可抢占式调度要少的现场切换，节省了处理器时间。但由于不允许抢占，有时会降低任务集合的可调度性。不可抢占式调度的一种极端形式是按照先到先出（服务）FIFO（First-In-First-Out，FIFO）的方式执行任务。后到的高优先级任务会被排在前面的低优先级任务之后而被阻塞，而且阻塞时间是不确定的，会显著降低高优先级任务的可调度性。使用不可抢占式调度算法时，因为任务之间可以共享一个栈空间，所以能够减少内存消耗。
|
|
|
|
不可抢占调度由于任务的独占性，优点是共享数据的保护需求较低，缺点是系统的响应时间得不到保证。由于机载领域实时要求较高，不选择这种调度方式。
|
|
|
|
（3）同优先级任务的时间片轮转调度算法（round-robin）。同优先级任务的时间片轮转调度是轮转调度的一种，目的是使实时系统中优先级相同的任务具有平等的运行权利。时间片轮转调度算法是指当有两个或多个就绪任务具有相同的优先级且它们是就绪任务中优先级最高的任务时，任务调度程序按照这组任务就绪的先后次序调度第一个任务，让它运行一段时间。运行的这段时间称为时间片（time slicing）。当任务运行完一个时间片后，该任务即使还没有停止运行，也必须释放处理器让下一个与它相同优先级的任务运行（假设这时没有更高优先级的任务就绪）。释放处理器的任务被排到同优先级就绪链的链尾，等待再次运行。
|
|
|
|
|
|
|
|
先来先服务算法（First Come First Served，FCFS），也叫做先进先出算法（First In First Out，FIFO），是最简单的一种调度算法。顾名思义，先来先服务的基本思想就是按照任务到达的先后次序来进行调度（如下图所示）。它是一种不可抢占的调度方式，如果当前任务占用着CPU在运行，那么就要一直等到它执行完毕或者因为某种原因被阻塞，才会让出CPU给其他的任务。另外，对于一个被阻塞的任务，当它被唤醒之后，就把它放在就绪队列的末尾，重新开始排队。
|
|
|
|
|
|
|
|
先来先服务算法的最大优点就是简单，易于理解也易于实现。它的缺点也很明显：一批任务的平均周转时间取决于各个任务到达的顺序，如果短任务位于长任务之后，那么将增大平均周转时间。
|
|
|
|
|
|
为了改进FCFS算法，减少平均周转时间，人们又提出了短作业优先算法（Shortest Job First，SJF）。SJF算法的基本思路是：各个任务在开始执行前，必须事先预计好它的执行时间，然后调度算法将根据这些预计时间，从中选择用时较短的任务优先执行。SJF算法有两种实现方案：
|
|
|
|
.不可抢占方式：当前任务正在运行的时候，即使来了一个比它更短的任务，也不会被打断，只有当它运行完毕或者是被阻塞时，才会让出CPU，进行新的调度。
|
|
|
|
.可抢占方式：如果一个新的短任务到来了，而且它的运行时间要小于当前正在运行的任务的剩余时间，那么这个新任务就会抢占CPU去运行。这种方法，也称为最短剩余时间优先算法（Shortest Remaining Time First，SRTF）。
|
|
|
|
不可抢占的SJF算法如下图所示，由于任务T3的执行时间最短，所以首先被调度运行，其次是T1和T2。
|
|
|
|
|
|
|
|
可以证明，对于一批同时到达的任务，采用SJF算法将得到一个最小的平均周转时间。例如，假设有四个任务A、B、C、D，它们的运行时间分别是a、b、c和d，假设它们的到达时间是差不多的，调度顺序为A、B、C、D。那么任务A的周转时间为a，B的周转时间为a+b，C的周转时间为a+b+c，D的周转时间为a+b+c+d，因此，最后的平均周转时间为（4a+3b+2c+d）/4，从这个式子来看，显然，只有当a
|
|
|
|
|
|
时间片轮转算法（Round Robin，RR）的基本思路是：把系统当中的所有就绪任务按照先来先服务的原则，排成一个队列。然后，在每次调度的时候，把处理器分派给队列当中的第一个任务，让它去执行一小段CPU时间，或者叫时间片。当这个时间片结束的时候，如果任务还没有执行完的话，将会发生时钟中断，在时钟中断里面，调度器将会暂停当前任务的执行，并把它送到就绪队列的末尾，然后执行当前的队首任务。反之，如果一个任务在它的时间片用完之前就已经运行结束了或者是被阻塞了，那么它就会立即让出CPU给其他的任务。
|
|
|
|
|
|
.公平性：各个就绪任务平均地分配CPU的使用时间。例如，假设有n个就绪任务，那么每个任务将得到1/n的CPU时间。
|
|
|
|
.活动性：每个就绪任务都能一直保持着活动性，假设时间片的大小为q，那么每个任务最多等待（n-1）q这么长的时间，就能再次得到CPU去运行。
|
|
|
|
在采用时间片轮转算法时，时间片的大小q要适当选择，如果选择不当，将影响到系统的性能和效率。
|
|
|
|
.如果q太大，每个任务都在一个时间片内完成，这就失去了轮转法的意义，退化为先来先服务算法了，这就使各个任务的响应时间变长。
|
|
|
|
.如果q太小，每个任务就需要更多的时间片才能运行完，这就使任务之间的切换次数增加，从而增大了系统的管理开销，降低了CPU的使用效率。
|
|
|
|
因此，如何来选择一个合适的q值，既不能太大，也不能太小，这是时间片轮转法的最大问题。一般来说，这个值选在20～50ms是比较合适的。
|
|
|
|
|
|
优先级调度算法的基本思路是：给每一个任务都设置一个优先级，然后在任务调度的时候，在所有处于就绪状态的任务中选择优先级最高的那个任务去运行。例如，短作业优先算法其实也是一个优先级算法，每个任务的优先级就是它的运行时间，运行时间越短，优先级越高。
|
|
|
|
优先级算法可以分为两种：可抢占方式和不可抢占方式。它们的区别在于：当一个任务正在运行的时候，如果这时来了一个新的任务，其优先级更高，那么在这种情形下，是立即抢占CPU去运行新任务，还是等当前任务运行完了再说。
|
|
|
|
在任务优先级的确定方式上，可以分为静态方式和动态方式两种。
|
|
|
|
.静态优先级方式：在创建任务的时候就确定任务的优先级，并且一直保持不变直到任务结束。优先级的确定可以依据任务的类型或重要性，例如，系统任务的优先级要高于用户任务，实时任务的优先级要高于非实时任务。静态优先级方式有一个很大的缺点：高优先级的任务会一直占用着CPU运行，而那些低优先级的任务可能会长时间地得不到CPU，一直处于“饥饿”状态。
|
|
|
|
.动态优先级方式：在创建任务的时候确定任务的优先级，但是该优先级可以在任务的运行过程中动态改变，以便获得更好的调度性能。例如，为了防止静态优先级方式中出现的“饥饿”现象，系统可以根据任务占用CPU的运行时间和它在就绪队列中的等待时间来不断地调整它的优先级。这样，即便是一个优先级比较低的任务，如果它在就绪队列中的等待时间足够长，那么它的优先级就会不断提高，最终可以被调度执行。
|
|
|
|
在优先级算法中，高优先级的任务将抢占低优先级的任务。对于优先级相同的任务，通常的做法是把任务按照不同的优先级进行分组，然后在不同组的任务之间使用优先级算法，而在同一组的各个任务之间使用时间片轮转法。
|
|
|
|
采用优先级调度算法，还有一个问题就是可能会发生优先级反转的现象。在理想情况下，当高优先级任务处于就绪状态后，会立即抢占低优先级任务而得到执行。但在实际系统当中，在各个任务之间往往需要用到各种共享资源，如I/O设备、信号量、邮箱等等。在这种情形下，可能会出现高优先级任务被低优先级任务阻塞，等待它释放资源，而低优先级任务又在等待中等优先级任务的现象，这种现象称为“优先级反转”。
|
|
|
