LINUX进程调度算法的分析
何 翔，顾 新
（西安电子科技大学，陕西西安 710071）
摘 要进程调度对一个操作系统来说是至关重要的，它起着非常关键的作用。本文针对Linux操作系统中的普通进程调度算法进行了分析，对以进程为CPU时间分配单位和以用户为CPU时间分配单位的两种算法进行了分析和对比。对它们在不同环境下对进程调度效率和公平性的影响进行了探讨，并总结出它们各自适用的环境。
最后为了进一步提高进程调度的效率和公平性，提出了混合算法的思想。
关键词进程调度；普通进程；动态优先级
中图分类号 TP316
1 前 言
在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期）
21
LINUX 进程调度算法的分析
IT Age/ Sep. 15, 2005
22c=-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:1
N :M 1:1
LINUX 进程调度算法的分析
电子科技/2005年9月15
234 混合算法的思想
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, 2005
24在schedule()函数选择下一个进程时，它将判断是否需要计算进程的counter 值，这个过程在运行队列中所有进程都用完了时间片时才被调用。而正是在这时把混合调度算法的代码加入被调用的那段程序中，所以对系统的效率影响最小。
4.2 算法效率分析
通过前面的分析可以看出，影响按进程调度算法的效率主要是它的核心算法中扫描整个可运行队列链表的那个循环。也就是说那个循环对当前可运行队列中的所有进程进行了一次遍历。它的输入是goodness()函数的返回值即权值（weight ）和假设的初始权值c =－1000。它的输出是可以占有CPU 的下一个可运行队列中的进程。我们假设按进程调度算法中核心算法的时间复杂度为O (n )，其中n 为可运行队列中的进程数。
影响按用户调度算法效率主要是两次用户结构的遍历和一次对进程队列的遍历。第一次遍历用户结构所作的操作比较简单，只是把变量move_task 置空。第二次遍历用户结构所作的操作稍微复杂一些，主要是把CPU 时间为0的用户置于队尾并且重新计算其可占用CPU 的时间。因为系统中的用户数大大少于进程数且这两次遍历所进行的操作时间相差不大，所以这两个循环的时间复杂度都可看作O (m )，其中m 为用户数。还有一次进程队列的遍历其操作主要是对进程占用CPU 时间的计算和用户占用CPU 时间的调整。它和按进程调度算法中进程队列遍历所进行的操作（对进程权值进行比较）相比，稍微复杂一些。因为按进程调度算法中的进程遍历其主要操作的依据（权值的计算）是在goodness()中进行的，所以省去了大部分的时间。所以可以把按用户调度算法中进程队列遍历的时间复杂度约等于O (n )这里的n 是进程数。因此按用户调度算法的时间复杂度为2O (m )+O (n )。
我们提出的混合算法是在按用户调度算法的基础上进行改进的，加入代码的时机和按用户调度算法相同，但却精简了很多。因为我们的目的是进行判断，选择最合适的调度算法，而不是进行真正的调度。因此只需要遍历一次用户结构，即获得用户结构中的计数器的值并对其进行排序。而且在遍历中把用户结构的move_task 变量置空，这样既不影响效率也为以后选中按用户调度算法时节省了一次用户结构的遍历。接下来进行和常数值的比较，最后进行实际算法的选择。混合算法的时间复杂度为O (m )+O (n 1)其中O (n 1)是排序的时间复杂度n 1为排序基数。因为排序是针对简单整型数进行的冒泡排序，其基数为可运行队列中的进程数，所以其操作时间不会超过遍历进程的操作时间。我们可以假设其约等于O (n )。这样混合算法的时间复杂度为O (m )+O (n )。
综合起来按进程调度算法的时间复杂度为O (n )它的效率最高。按用户调度算法的时间复杂度为2O (m )+O (n )它的公平行最好。混合算法的时间复杂度为O (m )+O (n )它的效率比按用户算法的效率要高一点，当用户数很大时效率会更显著。比按进程调度算法的效率要稍微低一点，但公平行却高很多，尤其是当系统中有些用户拥有的进程数相差很大时，公平性体现的更明显。
在特殊情况下，即用户数非常大且它们拥有的进程数都很接近的情况下才会出现效率下降的问题。但这种情况很少出现，因为Linux 的用户数是在动态变化着的，不太经常在很长时间内一直保持一个很大的用户数。即便是这样也不太可能在系统中用户所拥有的进程数都很平均，所以这种情况不会影响混合算法的实际效果。
5 结束语
混和算法可以在一定程度上有效的解决以上两种算法各自的不足，提高系统效率和公平性。混合算法的效率和算法中常数的取值有很大的关系。算法中常数的确定是和系统实际运行环境密切相关的，如果此常数确定的比较合理，系统调度的效率会有进一步的提高。 参考文献
1 毛德操, 胡希明. Linux 内核源代码情景分析. 杭州: 浙江大学出版社, 2003.
2 陈莉君. Linux 操作系统内核分析. 北京:人民邮电出版社,
2003.
3 彭晓鸣, 王强. Linux 核心源代码分析. 北京: 人民邮电出版社, 2000.
作者简介
何翔（1974—）男，西安电子科技大学2003级硕士生。研究方向：嵌入式系统应用。
顾新，男，西安电子科技大学副教授。研究方向：图形图像处理、嵌入式开发。
（下转第28页）
I E 浏览器常见故障分析与解决方案
IT Age/ Sep. 15, 2005
28HinfSection DefaultInstall 132 %windir%＼Inf ＼ie.inf”。
9 QQ 能上，但网页无法打开
【故障现象】尝试浏览网页时，IE 浏览器提示“该页无法显示”，但QQ 等即时通讯工具工作正常。
【故障分析】由于病毒原因或软件导致Winsock. dll 、Wsock32.dll 或Wsock.vxd （VXD 只在Windows 9x 系统下存在）等文件丢失或损坏。
【故障解决】
① 使用系统命令SFC （Windwos 9x ）、SFC/ Scannow （Windwos 2000/XP ）检测系统并进行修复。
② 使用Winsock Fix 工具进行自动修复。该工具下载地址为https://www.doczj.com/doc/6a4412057.html,/soft/35272. htm.
③ 产生这种现象还可能是因为网络设置错误、域名解析不正常，以及错误的防火墙策略造成的，若上面方法不奏效请 检查这三个方面。
10 无法用IE 下载文件
【故障现象】用IE 下载文件时，右键菜单里的“目标另存为”和“打印目标”等几项始终显示为灰色，用一些IE 修复工具修复IE ，故障依旧。
【故障分析】这不是由于恶意代码引起的问题，所以这些工具无效的。
【故障解决】在IE 选项里面选择内容选项卡，把分级审查禁用。如果分级审查已经禁用，那么先启用一次，再禁用就可以了。 参考文献
1 电脑报. 2004年合订本(下), 西南师范大学出版社, 12.
2 电脑爱好者. 2004年合订本(上), 电脑爱好者杂志社, 220.
作者简介
卢江（1962—），男，长安大学信息工程学院工程师。研究方向：计算机网络，数据库应用。
徐丽（1977—），女，长安大学信息工程学院讲师。研究方向：计算机网络信息技术。
Common Troubles of the IE Explorer and their Solutions
Lu Jiang, Xu Li
(Information Engineering Institute, Chang ′ an University Xi ′ an 710064, China)
Abstract With the constant development of network information, the Internet is reaching every corner of the world. It has become the most effective way of obtaining and exchanging information. The IE explorer has become people’s most commonly used and familiar network tool. This paper analyzes the common troubles in the use of the IE explorer and offers solutions. Keywords IE explorer; troubles; solution; schemes
（上接第24页）
Analysis of the LINUX Schedule Algorithm
He Xiang, Gu Xin
(Xidian University, Xi ′ an 710071, China)
Abstract Processes schedule is critical for the OS. This paper analyzes the Linux schedule algorithm and makes a comparison between the schedule algorithm with processes the as CPU time distribution unit and that with users as the CPU time distribution unit. It also compares the efficiency and justice of processes schedule in different conditions and summarizes the suitable conditions for the two algorithms above. Finally, to improve the efficiency and justice of processes schedule, this paper bring forwards a notion of mixing schedule algorithm.
Keywords processes schedule; non-real time processes