Linux与UNIX进程调度策略的比较分析崔洪星（华中科技大学机械科学与工程学院 M201170270）摘要：文章先是阐述了进程调度策略的引入、概念、分类和原则，接着就Linux和UNIX不同操作系统的进程策略进行了描述，最后比较得出结论。
1.进程调度概述当计算机是多道程序设计系统时，通常会有多个进程竞争CPU。
当多个处于就绪态而只有一个CPU时，操作系统就必须决定运行哪一个进程。
操作系统中做出这种决定的部分称为调度器。
它使用的算法称为调度算法。
通常进程调度的功能应由以下3部分组成：（1）确定调度时机（2）执行调度算法（确定调度策略、计算优先级），即选择哪些进程运行。
（3）完成调度过程的具体操作，主要是原来运行的进程退出CPU,保护退出进程的运行现场，选中进程占用CPU,恢复选中进程的运行现场。
进程调度分为两大类：一类是抢占式（剥夺式），系统中出现优先权高的可运行进程，立即让它执行；另一类是非抢占式（非剥夺式），系统中即使出现优先权高的可运行进程，也要等到调度时机出现时，才让它运行。
非抢占式的进程调度时机分为两种情况:进程自动放弃CPU和进程由核心态转入用户态。
（1）进程自动放弃CPU有以下几种情况:●进程已完成（虽然时间片未用完）；●进程等待某事件（如I/0，等待资源，……）；●时间片用完；●进程需要与其他进程保持同步；●……（2）进程由核心态转入用户态时系统产生一次调度，将最高优先权的就绪进程投入运行。
不同的环境需要不同的调度算法，这是因为不同的应用领域有不同的目标。
换句话说，在不同的系统中，调度器的优化目标是不同的。
为了设计一个调度算法，应当首先明确一个好的调度算法必须做什么。
一些目标是根据环境（批处理、交互式或实时）设定的，而另外一些目标是在各种情况下都使用的。
公平在所有的情况下，都是非常重要的，相对于处于同等地位的进程而言，给予一个进程更多的CPU时间是不公平的。
当然，不同种类的进程应该得到不同的处理。
下面将对Linux和UNIX进程的调度原理分别进行讨论。
2.Linux 进程调度原理调度程序运行时，要在所有可运行状态的进程中选择最值得运行的进程投入运行。
选择进程的依据是什么呢？在每个进程的task_struct 结构中有以下四项：policy、priority、counter、rt_priority。
这四项是选择进程的依据。
其中，policy是进程的调度策略，用来区分实时进程和普通进程，实时进程优先于普通进程运行；priority是进程(包括实时和普通)的静态优先级；counter是进程剩余的时间片，它的起始值就是priority的值；由于counter在后面计算一个处于可运行状态的进程值得运行的程度goodness时起重要作用，因此，counter 也可以看作是进程的动态优先级。
rt_priority是实时进程特有的，用于实时进程间的选择。
Linux用函数goodness()来衡量一个处于可运行状态的进程值得运行的程度。
该函数综合了以上提到的四项，还结合了一些其他的因素，给每个处于可运行状态的进程赋予一个权值(weight)，调度程序以这个权值作为选择进程的唯一依据。
关于goodness()的情况在后面将会详细分析。
linux内核的三种调度方法① SCHED_OTHER 分时调度策略，② SCHED_FIFO实时调度策略，先到先服务③ SCHED_RR实时调度策略，时间片轮转实时进程将得到优先调用，实时进程根据实时优先级决定调度权值，分时进程则通过nice和counter值决定权值，nice越小，counter 越大，被调度的概率越大，也就是曾经使用了cpu最少的进程将会得到优先调度。
SHCED_RR和SCHED_FIFO的不同：当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。
放在队列尾保证了所有具有相同优先级的RR 任务的调度公平。
SCHED_FIFO一旦占用cpu则一直运行。
一直运行直到有更高优先级任务到达或自己放弃。
如果有相同优先级的实时进程（根据优先级计算的调度权值是一样的）已经准备好，FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。
而RR可以让每个任务都执行一段时间。
当policy分别为以下值时：1) SCHED_OTHER：这是普通的用户进程，进程的缺省类型，采用动态优先调度策略，选择进程的依据主要是根据进程goodness值的大小。
这种进程在运行时，可以被高goodness值的进程抢先。
2) SCHED_FIFO：这是一种实时进程，遵守POSIX1.b标准的FIFO(先入先出)调度规则。
它会一直运行，直到有一个进程因I/O阻塞，或者主动释放CPU，或者是CPU被另一个具有更高rt_priority的实时进程抢先。
在Linux实现中，SCHED_FIFO进程仍然拥有时间片-只有当时间片用完时它们才被迫释放CPU。
因此，如同POSIX1.b一样，这样的进程就象没有时间片(不是采用分时)一样运行。
Linux中进程仍然保持对其时间片的记录（不修改counter）主要是为了实现的方便，同时避免在调度代码的关键路径上出现条件判断语句 if (！(current->；；policy&；；SCHED_FIFO)){...}-要知道，其他大量非FIFO进程都需要记录时间片，这种多余的检测只会浪费CPU资源。
（一种优化措施，不该将执行时间占10%的代码的运行时间减少到50%；而是将执行时间占90%的代码的运行时间减少到95%。
0.9+0.1*0.5=0.95>；；0.1+0.9*0.9=0.91）3) SCHED_RR：这也是一种实时进程，遵守POSIX1.b标准的RR(循环round-robin)调度规则。
除了时间片有些不同外，这种策略与SCHED_FIFO类似。
当SCHED_RR进程的时间片用完后，就被放到SCHED_FIFO和SCHED_RR队列的末尾。
只要系统中有一个实时进程在运行，则任何SCHED_OTHER进程都不能在任何CPU运行。
每个实时进程有一个rt_priority，因此，可以按照rt_priority在所有SCHED_RR进程之间分配CPU。
其作用与SCHED_OTHER进程的priority作用一样。
只有root用户能够用系统调用sched_setscheduler，来改变当前进程的类型(sys_nice，sys_setpriority)。
3.UNIX进程调度策略3.1 调度算法原理UNIX的调度策略基于优先数pri。
特点是pri动态改变，核心态（kernel）进程不可剥夺，用户态（user mode）进程可剥夺。
其中：0<=pri<=127, [0,49] ∈kernel,[50,127] ∈user mode proc 中，关于pri的信息有： p-pri当前调度使用的pri；p-usrpri用户态下的pri；p-cpu 当前使用CPU的程度；p-nice 取值范围[0,39],默认为20。
p-pri和p-usrpri用途不一样，p-pri是调度使用的pri。
当进程处于用户态时，p-pri=p-usrpri；当进程执行系统调用时被封锁，即处于核心态，这时p-pri值暂时降低p-pri（进程的优先权暂时升高）存放相应的核心态的pri值。
例如：进程被封锁时，系统有个sleep状态，其pri∈[0,49].唤醒时p-pri的值为sleep状态的pri，因为其pri小于p-usrpri，所以这时系统调用被唤醒后，能优先执行。
执行完后，置p-pri=p-usrpri。
p-usrpri每秒计算一次：p-usrpri=50+（p-cpu/a）+2*p-nice （a=2，4，8，16）从上式可知，对于等待I/O的进程（如Shell命令，editor），若p-cpu 值低，优先权高，易被调度；计算多的进程，使用CPU较多，p-cpu值高，优先权低。
优先权改变快慢是值得注意的问题，改变太慢，优先权低的进程长期不能得到执行，理想的情况应当是在一段时间内，分时的各个进程取一个相近的pri值，并在该值上下波动，波动值的大小取决与已使用的CPU的时间。
计算公式中，除数因子a就是为了达到这一目标设置的。
a的取值大小直接影响各种性质类型获得CPU的概率。
a越大，p-cpu衰减越快，获得CPU的概率越大。
通常a=4，因为是每计算一次p-cpu/4，不占用CPU的进程的p-cpu值会衰减较快，有较大几率得到重新调度。
3.2 进程调度的操作过程3.2.1 现运行进程到非运行进程的转换（主要功能是保护现场）。
①填写p-wchan、u-rsav[2]；②修改text结构中共享正文段数；③UISA-u-uisa、UISA-u-uisd。
……3.2.2 选中进程置换为运行状态（主要功能为恢复现场）。
①映像（用户态、核心态、数据、用户栈）是否在内存。
如果映像不在内存要将其掉入。
若此时内存有足够大的空间，则掉入；若内存空闲空间不够，则淘汰内存中的某些页面，这时要涉及淘汰策略。
②KISA[6]-ppda。
Proc[n].p-addr写入KISA6.③根据p-text找到text结构。
如果text不在内存中要将其调入内存。
若此时内存空闲空间足够大，则调入，若内存空闲空间不够大，则淘汰某些页面。
④由p-addr或KISA[6]找到user，并执行如下操作：4.总结通过对linux和NUIX两种不同操作系统的调度策略进行比较分析，我们发现，它们有很多相似之处，原因在于它们都是分时操作系统，总的来说，UNIX系统的调度策略要略微简单一些。