基于Linux的进程调度算法的改进与实现

随着Linux系统的逐渐推广,它被越来越多的计算机用户所了解和应用,各国政府都在鼓励和支持Linux在本国的发展。O(1)调度算法推出后,使调度器的时间复杂度从O(n)降到了O(1),又激起了人们对基于Linux的进程调度算法的研究。 本文首先对Linux系统进行了简要的介绍,介绍了国内外在调度算法方面的研究现状,分析了课题研究的背景和意义。然后介绍了进程管理的相关理论知识。 其次,详细研究了O(1)调度算法及其在Linux 2.6内核中的具体实现。O(1)调度器中增加了数据结构runqueue,就绪队列被分成active和expired,结合bitmap[]不必遍历整个就绪队列,查找next进程的时间复杂度降为O(1)。进程运行时间片的重新分配更及时;动态优先级的计算过程更简单,计算时机更分散;调度时机更宽松,提高了调度器的实时性能;调度流程更简单。也指出了,在O(1)调度器下,不同用户执行相同的程序,他们创建的进程将获得相同的运行时间片和周转时间。这样对高级别用户是不公平的。 最后,引入了用户级别的概念,证明了O(1)调度器的以上不足。提出了一种基于用户级别的进程调度策略,通过给不同用户指派不同的级别,使不同级别用户创建的进程的时间片不同,以此使他们的周转时间不同,高级别用户将获得比低级别用户更短的周转时间,使各级别的用户得到与其级别相适应的周转时间,更加体现进程调度的公平性原则;并且,一般情况下,该调度策略下0级用户的周转时间比在O(1)调度策略下短。 O(1)调度器的研究紧跟了调度算法研究领域的前沿;用户级别的引入、基于用户级别的进程调度策略的提出,开拓了进程调度研究的新思路,一定程度上促进了我国自主操作系统的研究和发展。