进程调度

进程调度

进程调度是OS中必不可少的一种调度。因此在三种类型的OS中,都无一例外地配置了进程调度。此外它也是对系统性能影响最大的一种处理机调度,相应的,有关进程调度的算法也较多。

进程调度的任务、机制和方式。

1. 进程调度的任务进程调度的任务主要有三:

   (1)保存处理机的现场信息。在进行调度时首先需要保存当前进程的处理机的现场信息,如程序计数器、多个通用寄存器中的内容等。

   (2)按某种算法选取进程。调度程序按某种算法从就绪队列中选取一个进程,将其状态改为运行状态,并准备把处理机分配给它。

   (3)把处理器分配给进程。由分派程序把处理器分配给该进程,此时需要将选中进程的进程控制块内有关处理机现场的信息装入处理器相应的各个寄存器中,把处理器的控制权交予该进程,让它从上次的断点处恢复运行。

2. 进程调度机制

   为了实现进程调度,在进程调度机制中,应具有如下三个基本部分,如图3-1所示.

   

   (1) 排队器。

   为了提高进程调度的效率,应事先将系统中的所有就绪进程按照一定的策略排成一个或多个队列,以便调度程序能最快地找到它。以后每当有一个进程转变为就绪状态时,排队器便将它插入到相应的就绪队列。

   (2) 分派器。

   分派器依据进程调度程序所选定的进程,将其从就绪队列中取出,然后进行从分派器到新选出进程间的上下文切换,将处理机分配给新选出的进程。

   (3) 上下文切换器。

   在对处理机进行切换时,会发生两对上下文的切换操作:

• 第一对上下文切换时, OS将保存当前进程的上下文,即把当前进程的处理机寄存器内容保存到该进程的进程控制块内的相应单元,再装入分派程序的上下文,以便分派程序运行.
• 第二对上下文切换是移出分派程序的上下文,而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中,以便新选进程运行。

在进行上下文切换时,需要执行大量的load和store等操作指令,以保存寄存器的内容。即使是现代计算机,每一次上下文切换所花费的时间大约可执行上千条指令。为此,现在已有靠硬件实现的方法来减少上下文切换时间。一般采用两组(或多组)寄存器,其中的一组寄存器供处理机在系统态时使用,而另一组寄存器供应用程序使用。在这样条件下的上下文切换,只需改变指针,使其指向当前寄存器组即可。

3. 进程调度方式

   早期所采用的非抢占方式存在着很大的局限性,很难满足交互性作业和实时任务的需求。为此,在进程调度中又引入了抢占方式。我们先了解一下非抢占方式时的情况.

   1)非抢占方式(Nonpreemptive Mode)

   在采用这种调度方式时,一旦把处理机分配给某进程后,就一直让它运行下去,决不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机,直至该进程完成,或发生某事件而被阻塞时,才把处理机分配给其它进程。

   在采用非抢占调度方式时,可能引起进程调度的因素可归结为:

   • 正在执行的进程运行完毕,或因发生某事件而使其无法再继续运行;
   • 正在执行中的进程因提出VO请求而暂停执行;
   • 在进程通信或同步过程中,执行了某种原语操作,如Block原语.

   这种调度方式的优点是实现简单,系统开销小,适用于大多数的批处理系统。但它不能用于分时系统和大多数实时系统。

   2)抢占方式(Preemptive Mode)

   这种调度方式允许调度程序根据某种原则,去暂停某个正在执行的进程,将已分配给该进程的处理机重新分配给另一进程。在现代OS中广泛采用抢占方式,这是因为:对于批处理机系统,可以防止一个长进程长时间地占用处理机,以确保处理机能为所有进程提供更为公平的服务。在分时系统中,只有采用抢占方式才有可能实现人一机交互。在实时系统中,抢占方式能满足实时任务的需求。但抢占方式比较复杂,所需付出的系统开销也较大。

   “抢占”不是一种任意性行为,必须遵循一定的原则。主要原则有:

   ①优先权原则,指允许优先级高的新到进程抢占当前进程的处理机,即当有新进程到达时,如果它的优先级比正在执行进程的优先级高,则调度程序将剥夺当前进程的运行,将处理机分配给新到的优先权高的进程。

   ②短进程优先原则,指允许新到的短进程可以抢占当前长进程的处理机,即当新到达的进程比正在执行的进程(尚须运行的时间)明显短时,将处理机分配给新到的短进程。

   ③时间片原则,即各进程按时间片轮转运行时,当正在执行的进程的一个时间片用完后,便停止该进程的执行而重新进行调度。

轮转调度算法

在分时系统中，最简单也是较常用的是基于时间片的轮转(round robin,RR)调度算法。

该算法采取了非常公平的处理机分配方式，即让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有n个进程，则每个进程每次大约都可获得1/的处理机时间。

1. 轮转法的基本原理

在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。系统可设置每隔一定时间（如30ms)便产生一次中断，去激活进程调度程序进行调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。这样，就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。

2. 进程切换时机 在RR调度算法中，应在何时进行进程的切换，可分为两种情况：

   ① 若一个时间片尚未用完，正在运行的进程便已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片。

   ② 在一个时间片用完时，计时器中断处理程序被激活。如果进程尚未运行完毕，调度程序将把它送往就绪队列的末尾。

3. 时间片大小的确定

   

   在轮转算法中，时间片的大小对系统性能有很大的影响。若选择很小的时间片，将有利于短作业，因为它能在该时间片内完成。但时间片小，意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销。反之，若时间片选择得太长，且为使每个进程都能在一个时间片内完成，RR算法便退化为FCFS算法，无法满足短作业和交互式用户的需求。一个较为可取的时间片大小是略大于一次典型的交互所需要的时间，使大多数交互式进程能在一个时间片内完成，从而可以获得很小的响应时间。图3-2示出了时间片大小对响应时间的影响，其中图(a)是时间片略大于典型交互的时间，而图(b)是时间片小于典型交互的时间。图3-3示出了时间片分别为q=1和q=4时对平均周转时间的影响。

   

优先级调度算法

在时间片轮转调度算法中，做了一个隐含的假设，即系统中所有进程的紧迫性是相同的。但实际情况并非如此。为了能满足实际情况的需要，在进程调度算法中引入优先级，而形成优先级调度算法。

1.优先级调度算法的类型

优先级进程调度算法，是把处理机分配给就绪队列中优先级最高的进程。这时，又可进一步把该算法分成如下两种。

(1) 非抢占式优先级调度算法。该算法规定，一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成，或者因该进程发生某事件而放弃处理机时，系统方可将处理机重新分配给另一优先级最高的进程。

(2) 抢占式优先级调度算法。把处理机分配给优先级最高的进程，使之执行。但在其执行期间，只要出现了另一个其优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。因此，在采用这种调度算法时，每当系统中出现一个新的就绪进程时，就将其优先级P与正在执行的进程j的优先级P进行比较，如果P≤P,原进程P便继续执行：但如果是P>P,则立即停止P的执行，进行进程切换，使i进程投入执行。抢占式的优先级调度算法常用于对实时性要求较高的系统中。

2.优先级的类型

优先级调度算法的关键在于：应如何确定进程的优先级，以及确定是使用静态优先级还是动态优先级。

(1) 静态优先级

静态优先级是在创建进程时确定的，在进程的整个运行期间保持不变。优先级是利用某一范围内的一个整数来表示的，例如0一255中的某一整数，又把该整数称为优先数。确定进程优先级大小的依据有如下三个：

• 进程类型。通常系统进程（如接收进程、对换进程）的优先级高于一般用户进程的优先级。
• 进程对资源的需求。对资源要求少的进程应赋予较高的优先级。
• 用户要求。根据进程的紧迫程度及用户所付费用的多少确定优先级。

静态优先级法简单易行，系统开销小，但不够精确，可能会出现优先级低的进程长期没有被调度的情况。

(2) 动态优先级

动态优先级是指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以便获得更好的调度性能。例如，可以规定在就绪队列中的进程随其等待时间的增长，使其优先级相应提高。若所有的进程都具有相同优先级初值，则最先进入就绪队列的进程会因其优先级变得最高，而优先获得处理机，这相当于FCFS算法。

若所有的就绪进程具有各不相同的优先级初值，那么对于优先级初值低的进程，在等待了足够的时间后，也可以获得处理机。当采用抢占式调度方式时，若再规定当前进程的优先级随运行时间的推移而下降，则可防止一一个长作业长期地垄断处理机。

多队列调度算法

如前所述的各种调度算法，尤其在应用于进程调度时，由于系统中仅设置一个进程的就绪队列，即低级调度算法是固定的、单一的，无法满足系统中不同用户对进程调度策略的不同要求，在多处理机系统中，这种单一调度策略实现机制的缺点更显突出，由此，多级队列调度算法能够在一定程度上弥补这一缺点。

该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。

多队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。

在多处理机系统中，该算法由于安排了多个就绪队列，因此，很方使为每个处理机设置一个单独的就绪队列。这样，不仅对每个处理机的调度可以实施各自不同的调度策略，而且对于一个含有多个线程的进程而言，可以根据其要求将其所有线程分配在一一个就绪队列，全部在一个处理机上运行。再者，对于一组需要相互合作的进程或线程而言，也可以将它们分配到一组处理机所对应的多个就绪队列，使得它们能同时获得处理机并行执行。

多级反馈队列(multileved feedback queue)调度算法

前面介绍的各种用于进程调度的算法都有一定的局限性。如果未指明进程长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而下述的多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，还可以较好地满足各种类型进程的需要，因而它是目前公认的一种较好的进程调度算法。

1. 调度机制

   多级反馈队列调度算法的调度机制可描述如下：

   (1) 设置多个就绪队列。在系统中设置多个就绪队列，并为每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余队列的优先级逐个降低。该算法为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。例如第二个队列的时间片要比第一个的时间片长一倍,...,第i+1个队列的时间片要比第i个的时间片长一倍。图3-4是多级反馈队列算法的示意图。

   

   (2)每个队列都采用FCFS算法。当新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可撒离系统否则，即它在一个时间片结束时尚未完成，调度程序将其转入第二队列的末尾等待调度：

   如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，…，依此类推。当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。

   (3)按队列优先级调度。调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行：换言之，仅当第1一(-1)所有队列均空时，才会调度第ⅰ队列中的进程运行。如果处理机正在第1队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第ⅰ队列的末尾，而把处理机分配给新到的高优先级进程。

2. 调度算法的性能

   在多级反馈队列调度算法中，如果规定第一个队列的时间片略大于多数人机交互所需之处理时间时，便能较好地满足各种类型用户的需要。

   (1) 终端型用户。由于终端型用户提交的作业多属于交互型作业，通常较小，系统只要能使这些作业在第一队列规定的时间片内完成，使可使终端型用户感到满意。

   (2) 短批处理作业用户。对于这类作业，如果可在第一队列中执行完成，便获得与终端型作业一样的响应时间。对于稍长的短作业，也只需在第二和第三队列各执行一时间片完成，其周转时间仍然较短。

   (3) 长批处理作业用户。对于长作业，它将依次在第1,2，·，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。

基于公平原则的调度算法

以上介绍的几种调度算法所保证的知识优先运行，如优先级算法是优先级最高的作业优先运行，但并不保证作业占用了多少处理机时间。另外也未考虑到调度的公平性。本小节将介绍两种相对公平的调度算法。

1. 保证调度算法

   保证调度算法是另外一种类型的调度算法，它向用户所做出的保证并不是优先运行，而是明确的性能保证，该算法可以做到调度的公平性。一种比较容易实现的性能保证是处理机分配的公平性。如果在系统中有n个相同类型的进程同时运行，为公平起见，须保证每个进程都获得相同的处理机时间1/n。在实施公平调度算法时系统中必须具有这样一些功能：

   (1)跟踪计算每个进程自创建以来已经执行的处理时间。

   (2)计算每个进程应获得的处理机时间，即自创建以来的时间除以。

   (3)计算进程获得处理机时间的比率，即进程实际执行的处理时间和应获得的处理机时间之比。

   (4)比较各进程获得处理机时间的比率。如进程A的比率最低，为0.5，而进程B的比率为0.8，进程C的比率为1.2等。

   (5)调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程比率为止。

2. 公平分享调度算法

   分配给每个进程相同的处理机时间，显然，这对诸进程而言，是体现了一定程度的公平，但如果各个用户所拥有的进程数不同，就会发生对用户的不公平问题。假如系统中仅有两个用户，用户1启动了4个进程，用户2只启动1个进程，采用轮转法让每个进程轮流运行一个时间片时间，对进程而言很公平，但用户1和用户2得到的处理机时间分别为80%和20%，显然对用户2而言就有失公平。在该调度算法中，调度的公平性主要是针对用户而言，使所有用户能获得相同的处理机时间，或所要求的时间比例。然而调度又是以进程为基本单位，为此，必须考虑到每一个用户所拥有的进程数目。例如系统中有两个用户，用户1有4个进程A、B、C、D,用户2只有1个进程E。为保证两个用户能获得相同的处理机时间，则必须执行如下所示的强制调度序列：

   A E B E C E D E A E B E C E D E....

   如果希望用户1所获得的处理机时间是用户2的倍，则必须执行如下所示的强制调度序列：

   A B E C D E A B E C D E A B E C D E....