Linux内核的进程调度原理及改进算法研究

Research for Process Schedule Fundamental and Improved Algorithm of Linux Kernel

随着Linux在嵌入式操作系统领域的广泛应用，对Linux实时性能增强的研究也越来越多。通过对LinUX进程调度依据和进程调度过程的分析，提出了一种改进的Linux进程调度算法。该算法改造了进程调度队列数据结构，去掉了进程调度选择时的遍历步骤，更改为直接得到待选最高优先级进程，同时，该算法改统一的时间片重新分配策略为分散的时间片重算策略。通过Linux进程调度算法与改进算法的时间复杂度对比分析，改进算法将Linux调度算法O（n）级的时间复杂度降低为O（1）级时间复杂度，因此能够更好地满足实时操作系统时间可测度以及低延迟等要求。

With Linux broad application in the domain of embedded operating system, more and more researches are aimed at improving the real time performance of it. Through analyzing the schedule basis and the schedule procedure of Linux＇s process, this paper presents an improved algorithm for the process schedule of Linux. The proposed algorithm rebuilds the data structure of the scheduling queue, replaces the traverse step by a straight computing step for choosing the process with highest priority, and changes the uniform strategy into a dispersed recalculated strategy for time slice distributing. By comparing the primary algorithm with the improved algorithm, the latter reduces the time complexity from O（n） to O （ 1 ）, and satisfies the needs of common real time operating system better.