LINUX进程调度算法的分析何 翔，顾 新（西安电子科技大学，陕西西安 710071）摘 要进程调度对一个操作系统来说是至关重要的，它起着非常关键的作用。

本文针对Linux操作系统中的普通进程调度算法进行了分析，对以进程为CPU时间分配单位和以用户为CPU时间分配单位的两种算法进行了分析和对比。

对它们在不同环境下对进程调度效率和公平性的影响进行了探讨，并总结出它们各自适用的环境。

最后为了进一步提高进程调度的效率和公平性，提出了混合算法的思想。

关键词进程调度；普通进程；动态优先级中图分类号 TP3161 前 言在Linux操作系统中，有两种常用的普通进程调度算法。

它们分别以进程和用户为调度单位来进行CPU时间的分配。

这两种算法分别体现了多进程环境下系统运行的高效性和多用户环境下的公平性。

但是这两种算法都有各自的适用环境，因此它们各自都有优缺点。

本文从多用户的公平性和多进程的高效性出发对这两种算法进行了分析和比较，最后提出了混合算法的思想，使进程调度更加高效和公平。

2 进程调度进程调度要满足高效率，公平性，响应时间快，周转时间短和吞吐量大等要求。

Linux操作系统的内核根据进程响应时间的情况把进程分为3大类：交互进程；批处理进程；实时进程。

内核在此基础上实现了3种不同的调度策略：SCHED_ FIFO(即先进现出策略)；SCHED_RR（即轮转策略）；SCHED_OTHER（适合交互分时的程序）。

进程调度时机，即调度器何时开始启动。

可以在以下几个时刻进行进程调度：（1）进程状态转换的时刻；（2）可运行队列中新增加一个进程时；（3）当前进程的时间片用完时；（4）进程从系统返回到用户态时；（5）内核处理完中断后，进程返回到用户态时。

在以上几种情况下进程调度可以解释为在下面几个状态中进行切换。

进程调度的流程如图1所示。

图1 进程调度的流程图图1的转换条件如下：（1）调度；（2）时间片用完；（3）跟踪并调度；（4）退出；（5）收到信号并醒来；（6）等待资源到位再调度；（7）等待资源到位再调度；（8）等待资源到位；（9）资源到位或收到信号。

3 普通进程调度算法的分析3.1 按进程调度的算法分析Schedulue()是按进程调度算法的主要函数，是系统的核心函数。

它的核心代码如下：next=idle_task(this_cpu);电子科技 2005年第9期（总第192期）21LINUX 进程调度算法的分析IT Age/ Sep. 15, 200522c=-1000;list_for_each(tmp,&runqueue_head){p=list_entry(tmp, struct task_struct, run_list);if(can_schedule(p, this_cpu)){int weight =goodness(p , this_cpu, prev->active_mm);if(weight>c)c=weight, next=p;}}这种算法是对可运行队列中的进程进行一次遍历，拿当前进程的权值和其余进程的权值进行比较。

初始的权值为c =－1000，这只有在可运行队列为空时才成立，其他进程的权值（weight ）是由goodness()函数计算出来的。

当队列中某个进程的权值最大且大于当前进程的权值时，系统就把CPU 的占有权让给这个进程，否则当前进程继续占有CPU 。

这种算法在用户拥有的进程数相差不大时，可以提高系统效率。

但在各用户进程数相差悬殊时，就会产生某些拥有很少进程的用户的“饥饿感”并加大进程调度的不公平性。

举个例子——例如A ，B 两个用户，A 用户开了99个进程，B 用户只开了1个进程，根据按进程的调度算法，CPU 的时间是平均分配给每个进程的，因此系统将大部分的CPU 时间分配给了A 用户，而B 用户得到的CPU 时间只有1％。

所以B 用户一定感到很不公平。

3.2 按用户调度的算法分析算法流程如图2所示。

图中标号含义如下： （1）遍历所有用户结构，并把move_task 置空； （2）访问每一个进程；（3）判断进程所属用户的CPU 时间是否为0； （4）重新计算该进程的counter 值； （5）判断是否遍历完了所有的进程； （6）访问每一个用户；（7）判断此用户的CPU 时间是否为0； （8）把该用户放到可运行队列尾部； （9）重新计算该用户的CPU 时间； （10）判断是否遍历完了所有用户； （11）结束算法。

图2 算法流程图算法中的用户结构如下： struct user_struct {atomic_t count; atomic_t processes; atomic_t files; struct user_struct *next, **pprev; uid_t uid; struct user_struct *our_next ，*our_prev; //遍历用户结构时所需的两个指针 struct task_struct *move_task; //保存当前进程信息的指针long cpu_ticks; //用户实际拥有CPU 时间的变量 }这种算法是以用户为单位来分配CPU 的占用时间在用户拥有进程数相差很大时，可以有效的提高调度的公平性。

但在用户拥有的进程数相差不大时，就会因为多余的循环而使系统效率下降。

我们假设有两个用户分别拥有M 和N 个进程，对以上两种算法进行了，如表1。

表1 两种算法比较运行状态两用户瞬时CPU 占用之比进程瞬时占用率之比进程占用CPU 时间之比按进程调度算法 M 个进程M :N 1:1 1:1 按用户调度算法N 个进程1:1N :M 1:1LINUX 进程调度算法的分析电子科技/2005年9月15234 混合算法的思想4.1 算法描述在以上分析的基础之上笔者提出了一种混合算法的思想。

它是在按用户调度算法的基础上进行修改而得来的。

算法中主要增加了一个常数和一个数据结构，如下：const int ourschedule; //常数 struct mixing_struct { int user[UID_SZ]; //保存各用户的进程数 int max_process; //用户中拥有最多的进程数 int min_process; //用户中拥有最少的进程数 }该算法分为两个阶段。

第一个阶段：需要对每个用户所拥有的进程数进行统计。

在进程控制块task_struct 结构中有个指针user ，用来指向一个user_struct 结构。

一个用户常常有许多个进程，所以有关用户的一些信息并不专属于某一个进程。

这样，属于同一个用户的进程就可以通过指针user 共享这些信息。

显然，每个用户有且有一个user_struct 结构。

结构中有个计数器count,对属于该用户的进程数进行计数。

在进行下一个进程调度开始时对所有用户结构struct user_struct 进行遍历。

在遍历过程中计录用户结构中的count 值并写入数组int user[UID_SZ]中。

UID_SZ 代表系统中的用户数。

然后再对该数组进行排序，并把排序结果的最大，最小值分别写入变量max_process ，min_process 中。

因为在每次进程调度时用户数的变动不会太大且用户中的进程数也不会有太大的变动，所以采取冒泡排序的方法。

这样可以提高排序的效率。

最后用排序中的最大值减去最小值得到一个差值。

第二个阶段：根据常数和差值的比较结果选择调度算法，当差值等于或大于这个常数值时，也就是说系统中有些用户所拥有的进程数相差过大时就选择按用户为CPU 时间分配单位的调度算法，否则就选择按进程为CPU 时间分配单位的调度算法。

算法流程如图3所示。

算法思想如下：user_struct up; //进程结构变量 const int ourschedule; //常数值int difference; //差值mixing_struct userstruct; //记录用户进程数的结构变量 for_each_user_struct(up) //遍历每一个用户结构 userstruct .user[]=count; //统计所有计数器的值 for(i=0;i< UID_SZ,i++) {对计数值进行排序；max_process=排序最大值； min_process=排序最小值；}difference= max_process -min_process; if(difference >=ourschedule) {选择按用户调度的算法； } else {选择按进程调度的算法； }图3 算法流程图schedule()函数是被频繁调用的一个函数，它的运行直接影响到了系统的效率，因此所添加的代码应该是被调用的频率越小越好。

在这种原则之下，我们发现有一段代码只有在CPU 的时间段（epoch ）全部耗尽的时候才去调用。

而在此时可以根据我们添加代码的调度信息，达到选择调度算法的目的。

LINUX 进程调度算法的分析IT Age/ Sep. 15, 200524在schedule()函数选择下一个进程时，它将判断是否需要计算进程的counter 值，这个过程在运行队列中所有进程都用完了时间片时才被调用。

而正是在这时把混合调度算法的代码加入被调用的那段程序中，所以对系统的效率影响最小。

4.2 算法效率分析通过前面的分析可以看出，影响按进程调度算法的效率主要是它的核心算法中扫描整个可运行队列链表的那个循环。

也就是说那个循环对当前可运行队列中的所有进程进行了一次遍历。

它的输入是goodness()函数的返回值即权值（weight ）和假设的初始权值c =－1000。

它的输出是可以占有CPU 的下一个可运行队列中的进程。

我们假设按进程调度算法中核心算法的时间复杂度为O (n )，其中n 为可运行队列中的进程数。

影响按用户调度算法效率主要是两次用户结构的遍历和一次对进程队列的遍历。

第一次遍历用户结构所作的操作比较简单，只是把变量move_task 置空。

第二次遍历用户结构所作的操作稍微复杂一些，主要是把CPU 时间为0的用户置于队尾并且重新计算其可占用CPU 的时间。

因为系统中的用户数大大少于进程数且这两次遍历所进行的操作时间相差不大，所以这两个循环的时间复杂度都可看作O (m )，其中m 为用户数。

还有一次进程队列的遍历其操作主要是对进程占用CPU 时间的计算和用户占用CPU 时间的调整。

它和按进程调度算法中进程队列遍历所进行的操作（对进程权值进行比较）相比，稍微复杂一些。

因为按进程调度算法中的进程遍历其主要操作的依据（权值的计算）是在goodness()中进行的，所以省去了大部分的时间。