Linux进程调度一、概述自1991年Linux操作系统出现以来，Linux操作系统以令人惊异的速度迅速在服务器和桌面系统中获得了成功。

它已经被业界认为是未来最有前途的操作系统之一，并且在嵌入式领域，由于Linux操作系统具有开放源代码、良好的可移植性、丰富的代码资源以及异常的健壮，使得它获得越来越多的关注。

[1]本文分析了Linux操作系统中几种常用的调度算法。

二、高级、中级和低级调度在操作系统中，存在很多种调度，如用户提交作业的调度、运行进程的调度、I/O 请求的调度、存储空间切换的调度等。

在不同的操作系统中所采用的调度方式不完全相同，在执行调度时所采用的调度算法也可能不同。

因此，可从不同的角度对调度进行分类。

常用的一种分类方法是按调度的层次，把调度分为高级调度、中级调度和低级调度。

（1）高级调度高级调度通常也称作业调度，用于决定把外存上处于后备队列中的哪些作业调入内存，准备执行。

系统接纳一个作业后，将它变为一个或者多个进程，为它们分配除了处理机之外的必要的系统资源后，将其排入就绪队列，准备执行。

值得注意的是，在批处理系统中，作业进入系统后，是先驻留在外存上的，因此，需要有作业调度，以将它们分批装入内存；在分时系统中，为了能及时响应，用户通过键盘输入的命令或数据等，都是直接送入内存，因而无须配置作业调度；类似地，在实时系统中，通常也不需要作业调度。

（2）中级调度中级调度大多针对于分时系统，是按一定的算法在内存和外存之间进行进程对换，目的在于缓和内存的紧张。

为此，应使那些暂时不具备执行条件的进程不再占用宝贵的内存空间，将它们挂起并调至外存上等待，称此时进程的状态为挂起状态。

当这些进程重新又具备执行条件，且内存已空闲时，再由中级调度决定，将外存上哪些已具备执行条件的进程解除挂起后重新调入内存，排在进程就绪队列上，等待进程调度。

由此可见，中级调度实质上是决定允许哪些进程有资格参与竞争处理机资源。

中级调度实施的方法是“挂起”和“解除挂起”进程，将进程的程序和数据在内存与外存间进行对换，以达到短期调整系统负荷的作用。

所以中级调度也常称为进程对换。

中级调度实际上就是存储器管理中的进程对换功能。

（3）低级调度低级调度就是指进程调度，它决定就绪队列中的哪个进程可以获得处理机。

被低级调度选中的进程将实际获得处理机，并可立即在处理机上执行它的程序。

在以进程为单位的操作系统中，进程调度是最基本的调度，在 3 种基本类型的操作系统中，都必须配置低级调度。

三、进程调度的方式进程调度通常有以下两种方式。

（1）非剥夺方式非剥夺方式也称非抢占方式。

采用这种调度方式时，一旦把处理机分配给某个进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才把处理机分配给其他进程，决不允许其他进程强占已分配出去的处理机。

这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。

但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。

显然，在要求比较严格的实时系统中，不宜采用这种调度方式。

（2）剥夺方式剥夺方式也称抢占方式，其含义是根据某种原则，强行剥夺现行进程正在使用的处理机，并把处理机分配给其他进程。

剥夺原则如下所述。

①优先级原则。

通常对一些重要和紧急的进程，赋予较高的优先级。

优先级高的进程可以剥夺优先级低的进程而执行。

②短进程优先原则。

当到达的进程比正在执行的进程明显短时，将剥夺长进程的执行而优先执行短进程。

③时间片原则。

每个进程被分配给一个同样的时间片，时间片用完后重新进行处理机调度。

④强制性剥夺。

极重要的进程或人工干预，强制引起处理机调度。

四、进程调度算法在Linux操作系统中，有五种常用的进程调度算法：先来先服务（FCFS）调度算法、短进程优先（SPF）调度算法、高优先级优先（HPF）调度算法、时间片轮转法（RR）以及多级反馈队列调度算法。

1. 先来先服务（FCFS）调度算法在进程调度中，采用FCFS调度算法时，进程调度程序从就绪进程队列中，选择一个最先进入队列的进程，把CPU分配给它，让它进入执行状态。

该进程一直执行，直到进程完成或因等待某事件发生阻塞时，才放弃CPU。

为了实现FCFS调度算法，系统只要按先进先出（FIFO）规则建立进程就绪队列即可，也就是进程控制块入队时加在队列末尾，调度出队时从队列首开始顺序扫描，将相关的PCB调度移出相应队列。

FCFS调度算法具有一定的公平性，并且实现也比较容易，这是它的优点。

但是，它的缺点是实际上不公平，它比较有利于长进程，而不利于短进程。

因为对于那些执行时间较短的进程来说，如果它们在某些执行时间很长的进程开始执行之后到达，则短进程将等待很长的时间。

在实际操作系统中，尽管很少单独使用FCFS算法，但FCFS算法可以和其他一些算法配合起来使用。

2. 短进程优先（SPF）调度算法短进程优先（SPF）调度算法，是指对执行时间短的进程优先调度的算法。

SPF是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或因等待某事件发生而放弃处理机时，再重新调度。

采用SPF算法，平均周转时间比FCFS调度算法有很多改善，这是它的优点。

SPF 调度算法的缺点也很多：第一，对长进程非常不利。

长进程的周转时间往往比较长，更严重的是存在着不确定的延迟现象。

第二，紧迫进程不能及时处理。

该算法完全未考虑进程的紧迫程度，调度程序仅按照进程运行时间从短到长按部就班地进行调度，因而不能保证紧迫性的进程得到及时处理。

第三，执行时间的估计值不准确。

由于进程的长短只是根据用户所估计的执行时间而定，所以有的用户为了先得到调度而有意缩短其进程的估计执行时间，致使该算法不一定能真正做到短进程优先调度。

3. 高优先级优先（HPF）调度算法考虑到系统中的紧迫进程能得到优先处理，引入了高优先级优先（HPF）调度算法，处理机总是分配给就绪进程队列中优先级最高的进程。

为了加速进程调度，进程就绪队列按优先级由高到低排列，调度时，只要把处理机分配给队首进程即可。

HPF进程调度可以是剥夺式或非剥夺式的。

在非剥夺方式下，系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去，直到被阻塞。

在剥夺方式下，系统同样是把处理机分配给就绪队列中优先级最高的进程，使之运行。

一旦出现了另一个优先级更高的就绪进程时，便立即实施剥夺。

进程调度程序就停止原最高优先级进程的运行，而将处理机分配给新出现的优先级最高的进程。

因此，系统将保证在任何时刻现行进程的优先级不低于任一就绪进程的优先级。

显然，剥夺式HPF 算法更严格地反映了优先级的特征，使得高优先级进程能尽快完成其任务，当然也增加了一定的系统开销。

在采用高优先级优先调度算法的系统中，进程的优先级对进程的调度至关重要，因为优先级的高低将直接影响到就绪进程被调度执行的次序。

进程的优先级可采用静态优先级和动态优先级两种，优先级可由用户自定或由系统确定。

（1）静态优先级静态优先级是在创建进程时确定进程的优先级，并且规定优先级在进程的整个生命期中都保持不变。

一般地，优先级用某一范围内的一个整数表示，例如，用0～63或0～255 中的某一整数表示。

在不同的操作系统中的优先级的用法也有不同，有些系统用“0”表示优先级最高，数值越大，优先级愈低；有些系统则正好相反，优先级的高低正好与整数值的大小相一致，“0”表示优先级最低。

一般地，进程的静态优先级可根据进程类型（系统进程或用户进程）、进程功能以及资源需求等来指定。

静态优先级调度算法的优点是简单易行、系统开销小。

其缺点是不太灵活，很可能出现低优先级的进程长期得不到调度而等待的情况。

因此，静态优先级调度算法仅适用于实时要求不太高的系统。

（2）动态优先级在创建一个进程时，根据进程的基本特性为其设置一个初始优先级，而后在进程的运行过程中，随着进程特性和运行环境的变化而动态地改变进程的优先级。

例如，使进程的优先级随其等待CPU 的时间的增长而提高，随其占用CPU 时间的增长而降低。

这样，即使低优先级进程，也会因其优先级逐渐提高而被调度选中。

显然，动态优先级的采用，使相应的优先级调度算法比较灵活、科学，可防止有些进程一直得不到调度或有些进程长期垄断处理机的情况出现。

但是，系统动态地确定进程的优先级需要花费相当多的程序执行时间，因而系统开销较大。

4. 时间片轮转法（RR ）时间片轮转法（RR ）的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例。

时间片轮转法的基本思想是将CPU 的处理时间分成固定大小的时间片。

如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的 CPU ，而排到就绪队列的末尾，等待下一次调度。

同时，进程调度程序又去调度当前就绪队列中的第一个进程。

RR 的原理如图1所示。

图1 时间片轮转法 在RR 中，事件片长度的选取非常重要。

首先，时间片长度的选择会直接影响系统开销和响应事件。

如果时间片长度过短，则进程切换次数大大增加，从而加重了系统开销。

如果时间片长度过长，比如一个时间片能保证就绪队列中所需执行时间最长的进程能执行完毕，则轮转法变成了先来先服务（FCFS ）调度算法。

一般来说，时间片长度q 的选择是根据系统对响应时间的要求R 和就绪队列中所允许的最大进程数N MAX 确定的。

即[3]q=R/N MAX5. 多级反馈队列调度算法前面介绍的几种进程调度算法，都有一定的局限性。

在实际系统中，所采用的调度模式往往是这些基本调度算法的结合。

图 1 是多级反馈队列调度算法的完成示意。

多级反馈队列就是综合了FCFS、RR和HPF的一种进程调度算法，其原理如图2，基本思想如下所述。

（1）系统按优先级设置N个就绪进程队列，第一级队列的优先级最高，其余队列的优先级逐个降低，第N级队列的优先级最低。

（2）每个就绪队列对应有一个时间片Si(i=1,2,…,n)，且有S1<S2<…<Sn；（3）除第n个队列按RR法调度外，其余各个队列均按FCFS调度。

（4）当一个新进程被建立后首先进入第一队列末尾，按FCFS原则排队等待调度。

当轮到该进程执行时，如能在该时间片S1内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二个队列的末尾，同样地按FCFS原则等待调度执行；如果它在第二个队列中运行一个时间片S2后仍未完成，再将它转入第三个队列末尾，按FCFS原则排队等待调度执行。

如此下去，当一个长进程从第一个队列降到第N队列后，在第N队列中便采用RR法调度运行。

（5）由于第一级队列的优先级最高，其余队列的优先级逐个降低，第N级队列的优先级最低，所以仅当第一个队列空闲时，调度程序才调度第二个队列的进程运行；一般仅当1～（i-1）队列均空时，才会调度第i个队列中的进程运行。