陈亮强，钱振江，2

（1.常熟理工学院计算机科学与工程学院，江苏 常熟 215500；2.南京大学计算机科学与技术系，江苏 南京 210023）

一种Minix进程调度的改进算法

陈亮强1，钱振江1，2

（1.常熟理工学院计算机科学与工程学院，江苏 常熟 215500；2.南京大学计算机科学与技术系，江苏 南京 210023）

为了提升Minix进程调度的性能，通过研究和借鉴Linux进程调度算法的思想，提出了一种Minix进程调度的改进算法.针对Minix多级队列调度算法的时间片固定的缺点，通过使时间片基于进程的优先级动态变化让Minix调度器在调度进程时更加体现公平性.

Minix；进程调度；公平性

1 引言

操作系统的发展经历了漫长的过程，但是真正快速发展起来是从20世纪60年代开始的.目前市场上主要被人们认可的可以用于实际生产生活的操作系统数量并不多，其中Linux占的比重很大，而Minix却相形见绌.就发展时间来看，Minix出现的时间要早于Linux，但是后者用户的基数与前者不在一个数量级上. Minix与Linux都是类Unix的操作系统，而Linux当中的许多思想也是借鉴于Minix，只是当初Minix的开发者作为大学教授只想要将该操作系统作为一款学生学习操作系统理念的工具而没有过多扩展其功能［1］，而Linux的发展是许多人共同努力的结果.Linux内核从最初的版本开始经过不断的改进，慢慢适应了市场的要求，许多原本有缺陷的地方也在原始开发者的努力和社区开发者们的帮助下逐渐完善.单就调度器这块，Linux采用的调度算法就经历了几次大的变化，从O（n）调度算法到O（1）调度算法再到CFS调度算法［2］，不仅操作系统的调度性能提升很大，而且在调度公平性方面也取得了很好的效果.

为了更好地发展Minix，目前Minix开发团队推出了最新的Minix 3，主要用于小型PC机和嵌入式系统.为了使操作系统变得更加可靠，Minix 3采用了微内核的设计理念，并且越来越模块化，但是这些特性并不影响对其内部某一功能模块的研究［1］.为了增强Minix的性能，提升其进程调度的效率和公平性是一个很好的切入点.通过改进Minix进程调度器的调度算法使Minix的进程调度达到一个负载平衡的状态，这样有利于Minix的后续发展.既然要对Minix当中的进程调度算法进行改进，那么首先应当分析它的不足之处，哪些方面还有待提高.在Minix 3中进程调度器采用的是多级队列调度算法，这个算法会在第4节详细介绍.通过对这个算法的过程分析可以发现，在调度进程时，调度的公平性并没有得到很好的保障，未实现进程调度的相对公平.和Minix具有同样的情况，Linux 2.6采用的O（1）调度算法［3］在公平性方面也处理得不是很好，但是到了Linux 2.6.23之后Linux内核就改用CFS（完全公平）调度算法［4］，这时Linux才真正实现了进程调度的相对公平.O（1）调度和CFS调度是目前Linux操作系统用的最多的调度算法，是操作系统进程调度的前沿.通过研究它们，开发者对操作系统进程管理方面有了更深层的认识.并且实现Minix进程间调度更加公平的改进方案，对于现代许多调度算法来说也有很大的启迪作用.有些算法可能随着时代的发展因为某些方面的不足而慢慢被淘汰，但是通过对这些算法进行一些改进可能就会有意想不到的效果.

2 相关工作

Linux之父Linus Torvalds在开发Linux时借鉴了不少Minix的内容，现在为了更好的发展Minix，就需要反过来借鉴Linux成熟的算法.第3节对O（1）调度算法和CFS调度算法进行研究，对CFS调度器取代O（1）调度器成为当前Linux内核调度器的原因进行探索［5］.通过对它们的数据结构、优先级、时间片和工作流程等方面的研究来挖掘出其最本质的设计理念，然后借鉴这些理念可以在公平性方面对Minix的多级队列调度算法［1］进行改进，让其调度器在调度进程时更能达到进程间调度的相对公平的效果，这样才更加符合现代操作系统的需要.下面主要研究CFS调度在O（1）调度的基础上如何实现进程间调度的相对公平，然后从研究的成果中提取出最本质的事物，即设计思想，比如权重和虚拟运行时间的概念等.并通过这些思想，对多级队列调度中已有的优先级和时间片进行改进，也加入权重和阈值等来对进程的时间片进行动态的变化以实现公平的原则.最后，还需要通过实验来亲自验证这种改进方案的可行性.

3 Linux中的调度思想

在Linux操作系统中，有实时进程和普通进程之分，对于这两种进程有3种方式的调度策略，它们分别为SCHED_FIFO、SCHED_RR和SCHED_NORMAL，前两个适合于实时进程，而最后一个适合于普通进程.对O（1）调度算法和CFS调度算法的研究主要围绕着普通进程展开.

3.1 O（1）调度算法

Linux的O（1）调度器对可运行态进程进行调度主要是通过内核源码中的schedule（）函数［6］实现的.该函数的核心执行步骤如下：

步骤1若当前处理器的运行队列上没有任何可运行态进程，那么为了实现多处理器间的负载平衡，则从其他处理器上调一些可运行态进程过来.若调完后当前处理器的运行队列上还是没有进程可运行，则在处理器上运行idle进程来使处理器处于低功耗模式直到有可运行态进程出现.若运行队列上有可运行态进程则执行步骤2；

步骤2判断active队列是否为空.当active队列为空，即表示所有活动进程都运行完了，这时就要让expired队列中的过期进程再次变为活动进程.但是并不需要将expired队列中的进程一个个移进active队列中去，只需要将active和expired的指针指向的地址互换就行了；

步骤3步骤2执行成功后active队列中必定存在活动进程，这时通过active中的优先级位图bitmap来选择优先级最高且有可运行态进程的优先级队列；

步骤4最后选择active的bitamp所指向链表中的第一个进程运行即可.

通过以上这4个核心步骤，O（1）调度器基本完成了对于可运行态进程的一次调度过程，如图1所示. 3.2CFS调度算法

图1 O（1）算法调度过程

3.2.1 引言

从Linux2.6.23开始，对于普通进程的调度已经不再使用O（1）调度算法了.因为考虑到O（1）调度的一些不足以及公平性方面的缺陷，所以改用完全公平调度（CFS）算法.不同于O（1）调度，CFS调度基于公平的理念，对进程一视同仁，不再对交互式进程进行区别，也不再根据进程的平均睡眠时间来确定奖励bonus并以此来调整动态优先级.取而代之，CFS通过权重使每个进程都能够获得公平的运行时间.更为关键的是，CFS调度算法的设计和实现都很简单，且实际性能非常优越.CFS的主要调度方式是通过红黑树的树型结构来选择虚拟运行时间最小的进程来运行，CFS调度器的整体结构如图2所示.

图2 CFS调度器的整体结构

3.2.2 虚拟运行时间

为了实现公平，开发者将虚拟运行时间引入到CFS调度中来取代优先级对于选择进程运行的决定地位，在内核源码中用vruntime字段［7］来表示虚拟运行时间.并且在CFS中主要有两个要素可以决定进程的虚拟运行时间，它们分别是进程的权重和进程实际运行的时间.调度器总是调度虚拟运行时间最小的进程，并且在每一次时钟中断到来时，内核都要重新计算当前进程的虚拟运行时间.正在运行的进程的虚拟运行时间随着运行时间的增长而增长，当它的虚拟运行时间不是可运行态进程中的最小值时它就会被其他可运行态进程抢占，而且能够看出虚拟运行时间与当前进程运行的时间、虚拟运行时间与当前进程的权重的关系：虚拟运行时间与当前进程运行的时间成正比，与当前进程的权重成反比.

由此可见，当一个进程的优先级越高，运行的时间越少时，这个进程的虚拟运行时间就越小，此进程就越应该被调度执行.

3.2.3 红黑树

相比于O（1）调度，CFS调度没有用运行队列来维护可运行态进程，而是用红黑树来组织普通进程.红黑树［7］本质上是一棵二叉查找树，它具有以下5个特点：

特点1每个叶结点都是空结点，并且它们是黑色的；特点2根结点是黑色的；

特点3红色结点的子结点必定是黑色的；

特点4对于任意结点而言，其到叶节点的每条路径上的黑色结点的数目都相同；

特点5每个结点不是黑色就是红色.

这些特点决定了红黑树是自平衡的，虽然红黑树没有达到恒定O（1）的时间复杂度，但是它最差的时间复杂度也为O（logn），这就决定了它可以在插入和删除等操作上表现得非常高效.

CFS使用的红黑树是以时间为顺序的，它的结点由调度实体来描述，关于调度实体的概念将在下一节组调度中介绍，而进程的虚拟运行时间和权重也存放在这个结构中，图3描绘了CFS中红黑树的结构.

内核通过红黑树来对虚拟运行时间进行排序，红黑树的最左侧结点的虚拟运行时间最少，所以该结点所表示的进程将是下一个要被调度的进程.

3.3 两种算法的比较

图3 CFS中红黑树的结构

通过对于O（1）调度和CFS调度的研究，发现它们的区别归根结底在于两者设计思想的不同.O（1）调度是通过优先级来实现对时间片的绝对映射，而CFS调度对于时间片的映射则是通过权重完成的.CFS调度相比O（1）调度的最主要优势在于它实现了进程间调度的相对公平，而这也是调度算法设计中非常重要的一个部分.虽然O（1）调度的恒定的时间复杂度O（1）也是一大特色，只是CFS的O（log n）的性能已经能够满足系统的需要，而且CFS的设计与实现简单，实际运行高效，不像O（1）调度有那么多的复杂公式，弥补了O（1）调度的许多不足之处.所以，这些因素最终决定了CFS调度要取代O（1）调度的位置.但是也不能完全否定O（1）调度算法，它对于以后进程调度算法的发展还是有许多值得借鉴的地方.

4 改进Minix调度算法

4.1多级队列调度算法

4.1.1 数据结构

和O（1）调度类似，多级队列调度在数据结构方面也采用了优先级队列.在多级队列调度中，一共有16个优先级队列，每个优先级对应一个队列［1］，其结构如图4所示.

在优先级队列中，队列0的优先级最大，而队列15的优先级最小.head指针指向队首进程，而tail指针指向队尾进程，这样就可以方便地实现进程的出队和入队操作.

图4 初始进程队列

4.1.2 调度流程

步骤1调度器维护16个队列，一个优先级级别与一个队列相对应.队列的序号越大，优先级越低；步骤2队列的优先级越高，该队列分配的时间片越大；步骤3若某一队列中进程不唯一，则轮到该进程运行时，它运行完了又会回到本队列的队尾；

步骤4若某一队列中进程唯一，即轮到该队列中进程运行时本次运行的进程也是下次要运行的进程，则在该进程连续两次运行完之后就会被安排到优先级更低的队列队尾，也就是说进程被降低了优先级，即进行优先级的数值+1的惩罚；

步骤5若一个进程被降低了优先级后，它又阻碍了其他进程的运行，则会被再次降低优先级，但是可降低到的最低优先级值为14，即普通进程不能和IDLE进程同处一个队列.若它运行完一个时间片后没有阻碍其他进程的运行，调度器将提高它的优先级，即进行优先级值-1的奖励.对于优先级的提高，最高可到达它所被允许的最大优先级为止；

步骤6最低优先级队列只能由IDLE进程使用，它在系统无其他就绪进程运行时运行.用户进程默认启动时的优先级要高于IDLE进程；

步骤7虽然队列内的调度很像时间片轮转调度，但是又有区别.如果一个进程阻塞时没有用完本身所拥有的时间片，那么当这个进程再次变为就绪状态时，系统就会将它放到它之前所在队列的队首等待被调度，而且它运行时的时间片是它上次运行剩下的时间片.调度器通过这种方式可以加快I/O调度；

步骤8系统进程的优先级高于用户进程的优先级，只有在所有系统进程都运行完后才能运行用户进程；

步骤9调度器调度进程时，总是以队列0作为起点，依次检查该队列是否有就绪进程存在.若有，则选择队首进程运行，否则检查下一个次高优先级队列.若前15个队列都没有就绪进程存在，则运行IDLE进程使CPU处于低功耗模式，直到系统产生下一个中断为止.

多级队列调度的流程如图5所示.

4.2 改进方案

4.2.1 调度的不足

从CFS调度和多级队列调度中可以看出，虽然两者都可以防止某一进程长时间得不到运行的情况，但是CFS调度在进程间调度公平方面做得更好，而多级队列调度恰恰在这方面有所欠缺.

多级队列调度在数据结构方面与O（1）调度很相似，都采取优先级队列，当一个进程长时间占用CPU时，系统就会降低它的优先级直到下一个进程被调度运行为止.但是在进程降低优先级的过程中，系统会根据它所在的优先级队列分配时间片然后让其等待运行，进程被分配的时间片是固定的，这样就有可能等到其他进程有机会运行的时候已经过了很长时间，即其他进程的等待时间很长，使进程调度不公平.

图5 多级队列调度

4.2.2 进程公平性方面的改进

对于多级队列调度算法存在的不足，Linux2.6的O（1）调度器也存在这样的问题，但是Linux2.6.23之后的CFS调度就这样的问题提出了权重和虚拟运行时间的概念，以此来动态划分时间片.基于这些思想，改进方案也是对多级队列调度的时间片进行动态划分，主要提出两个改进的想法，一个是引用权重的思想来对时间片进行动态的变化，让长时间占用CPU的进程能够更快被其他进程取代；另一个就是通过阈值的设定防止进程所分配的时间片超出最小范围，因为时间片太小的话会使进程切换过度频繁而浪费许多不必要的切换时间.下面就这两个方面进行讨论：

（一）通过权重实现时间片的动态划分

因为一个进程在某个优先级队列中连续两次运行后系统就会降低它的优先级，然后它的时间片会被系统重新分配，并将它放在优先级更低的队列中和其他原有的进程一起进行时间片轮转调度.改进后，采用权重来对进程的时间片进行动态划分，权重的计算见公式1.

公式1

其中，weight表示进程的权重，max_priority表示进程的最大优先级，priority表示进程的当前优先级.

权重是根据进程优先级的降低程度计算出来的，然后由权重再来计算当前进程将被分配的时间片大小，具体见公式2．

公式2

其中，now_times表示进程当前的时间片，times表示进程的初始时间片.

通过以上两个公式就可以动态改变进程的时间片，假如进程因为持续占用CPU而导致优先级降低的话，它本身的时间片也是降低的，并且降低的幅度越大，时间片也就下降得越快，这样其他优先级低的进程就有更大的机会运行了，体现了进程间调度的公平性.

（二）利用阀值限定时间片的范围

若进程优先级下降幅度太大，就会导致划分的时间片太小，时间片太小就会使进程切换过度频繁而浪费许多不必要的切换时间.为了防止这种情况的发生，设定一个固定的阀值来对时间片进行检测.当时间片小于这个阀值时，时间片就会按照阀值的大小被分配，具体见公式3.

公式3

其中，threshold表示阀值的大小.

通过以上两个方法，实现了在进程调度公平性方面对Minix的多级队列调度算法的改进.

5 实验及结果分析

5.1 实验设计

为了验证Minix当中的多级队列调度算法改进的可行性，可通过具体的实验来实现.实验的环境是minix 3.3.0，并且采用两种实验环境，一个是未修改过内核的环境，另一个是已经修改过内核并将内核重新编译过的环境.

图6 两次实验结果比较

图7 进程运行的CPU时间比较

实验采用了14个C语言程序，分别是从program1到program14.它们都是用来执行长时间的运算，这样能够保证每个C语言程序都需要大量占用CPU时间.为了模拟真实的多进程运行，通过Shell脚本程序来静态改变这14个进程的优先级，并且优先级越高的进程执行计算功能的时间越长，即所需要的CPU时间越长.进程优先级计算见公式4.

公式4

在实验中，让这14个程序在系统中同时执行.并且通过time命令采集它们的real、sys和user的值，并将其输出到固定的文件当中，然后对文件中的数据进行分析.为了保证数据的准确性，让每个程序运行10次然后取它们的平均值，这样就避免了因为某个数据而影响整体的结果.以上这些实验步骤先在未修改过内核的环境中执行一遍，再在已经修改过内核的环境中执行一遍，将两次运行的结果进行比对并得出结论.图6显示了实验后每个进程结束的时间、每个进程占用的CPU时间和每个进程等待的时间，再通过时间比较的结果观察改进后的调度算法是否更加体现了进程间调度的公平性.

5.2 实验结果

通过实验，对实验采集到的数据进行分析，绘制出图7、图8和图9这3个折线图，并根据这3个图来观察改进前后进程调度的情况.

图8 进程结束的时间比较

图9 进程等待的时间比较

从这些图可以看出，改进前后进程本身执行的时间并没有受到影响.而改进后的进程结束的时间和等待的时间趋向平衡，也就是说优先级低但执行时间很短的进程可以占用到CPU的机会提前了，而优先级高但执行时间很长的进程也不总占着CPU而让其他进程得不到运行，这就成功体现了进程间调度的公平性.所以，对于Minix的多级队列调度算法的改进是可行的.

6 结束语

Minix作为一种适用于小型PC机和嵌入式系统的操作系统，市场潜力非常巨大，特别是Minix 3采用了微内核的设计理念使得操作系统变得更加可靠.通过不断提升Minix的性能和可靠性并吸收Linux中一些成功的经验与技术来促进Minix在市场上的发展.Minix 3的内核代码非常短小精炼，对于国产操作系统的自主研发有很大的帮助.Minix进程调度算法的改进中用到的一些方法也对以后操作系统的发展有一定的推动作用.

［1］TANENBAUM A S,WOODHULL A S.Operating Systems Design and Implementation［M］.3th ed.Prentice Hall,2006:56-57.

［2］BOVET D P,CESATI M.Understanding the Linux Kernel［M］.3th ed.Sebastopol:O’Reilly Media,2005:77-78.

［3］朱永华，沈熠，刘玲.Linux内核完全公平调度器改进的研究［J］.计算机工程与应用，2014，50（21）：59-62.

［4］杜慧江，王云光.Linux内核2.6.24的CFS调度器分析［J］.计算机应用与软件，2010，27（2）：166-168.

［5］曹越，顾乃杰，任开新，等.一种面向多核系统的Linux任务调度算法［J］.计算机工程，2015（2）：36-40.

［6］LOVE R.Linux Kernel Development［M］.2th ed.Novell Press,2005:102-103.

［7］LOVE R.Linux Kernel Development［M］.3th ed.Sebastopol:O’Reilly,2010:111-112.

An Improved Algorithm of Minix Process Scheduling

CHEN Liangqiang1,QIAN Zhenjiang1,2
(1.School of Computer Science and Engineering,Changshu Institute of Technology,Changshu 215500; 2.Department of Computer Science and Technology,Nanjing University,Nanjing210023,China)

In order to improve the performance of Minix process scheduling,an improved algorithm of Minix process scheduling is proposed by studying the algorithm of Linux process scheduling and drawing on some good ideas.For the disadvantage of the fixed time slice in Minix multi-level queue scheduling algorithm,the dynamic change of the time slice based on the priority of the process makes Minix scheduler in scheduling process much fairer.

Minix;process scheduling;fairness

TP316

A

1008-2794（2017）02-0043-06

2016-08-31

国家自然科学基金项目“小型操作系统内核的轻量级形式化设计和验证方法研究”（61402057）

钱振江，副教授，博士，研究方向：操作系统安全、形式化验证和嵌入式系统，E-mail：qianzj@cslg.cn.