Linux进程调度算法分析.docx

Linux进程调度算法分析
摘要：基于X86平台Linux2.6.26内核进程调度部分代码，刨析Linux进程调度算法，对算法的原理，实现和复杂度进行了分析并提出了算法改进措施。
1.Linux进程调度概述
Linux系统支持用户态进程和内核线程，需要说明的是，Linux没有提供用户态线程支持，实现用户态线程需要引入第三方线程库。
操作系统进程调度是整个操作系统理论的核心，在设计进程调动机制需要考虑的具体问题主要有：
1）调度的时机：在什么情况下，什么时候进行调度。
2）调度的“政策”（policy）：根据什么准则挑选下一个进入运行的进程。
3）调度的方式：是“可剥夺”（preemptive）还是“不可剥夺”（nonpreemptive）。
图1.2.1给出了Linux进程状态转换关系：
图1Linux进程状态转换图
Linux进程调度分为自愿调度和强制调度两种。
1）在内核空间，一个进程可以通过schedule()启动一次调度，也可以在调用schedule()之前，将本进程状态设置为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE，暂时放弃运行而进入睡眠。这通常发生在来自用户空间的系统调用被阻塞。在用户空间，用户进程可以通过系统调用nanosleep()达到目的。
2）调度还可以是非自愿的。在一定条件下，内核会强制性剥夺当前进程运行而调度其他进程进入运行。
Linux调度政策基础是时间片轮转+优先级抢占的结合，为了满足不同应用的需要，内核提供了三种调度方法：
1）SCHED_FIFO实时调度策略，先到先服务
2）SCHED_RR实时调度策略，时间片轮转
3）SCHED_NORMAL分时调度策略（在2.6内核以前为SCHED_OTHER）。用户进程可以通过系统调用sched_setscheduler（）设定自己的调度策略。SCHED_FIFO和SCHED_RR的区别是，前者只有在就绪队列中有优先级更高的进程，或进程被阻塞，或自愿调用阻塞原语（如sleep_on_interruptible）的情况下，才会放弃CPU，而如果调度策略是后者，当前进程与就绪队列里其他进程按RoundRobin方式共享CPU。
2.Linux进程调度原理
基本的操作系统进程调度算法包括先来先服务（firstcomefirstserve），时间片轮转（roundrobin），多级反馈轮转法（roundrobinwithmultiplefeedback），优先级法（静态优先级法/动态优先级法），短作业优先法（shortestjobfirst），最高响应比优先法（highestresponse_rationext）。不同调度算法应用场合不同，某些调度算法可能仅具有研究价值，实际中鲜有应用；而某些调度算法需要互补以完成设计需求。但是，无论哪种进程调度算法，都要面对以下实际问题：
1）调度器对实时进程的响应；
2）调度器的调度开销，以及系统进程负载对调度的影响；
3）在SMP环境下，当前CPU调度对其他CPU的影响；
Linux2.6.x内核进程调度算法为解决上述问题，设计了全新的数据结构和调度算法，但其基本策路仍是以优先级为基础的抢占式调度，与2.6以前内核版本不同，内核抢占可能发生在内核态（因此，2.6版本的内核代码必须考虑到重入问题）。
2.6版本的内核调度也是几度变迁，其基本思想是1）提高实时进程调度相应比2）普通进程调度体现“完全公平这个思想”。从2.6早期版本SD（StaircaseSchedule）调度器，到2.6.23版本的RSDL（TheRotatingStaircaseDeadlineSchedule）调度器，再至2.6.26版本CFS（CompleteFairSchedule）调度器，调度机制不断完善。2.6.26内核进程调度吸收了前期版本的精华，通过全新设计数据结构和算法，为实时进程（SCHED_FIFO/SCHED_RR）提供O（1）时间复杂度的调度算法，同时，为了兼顾“完全公平”这一设计思路，设计了CFS调度器，为普通进程提供满足公平性为原则的O（lgn）时间复杂度的调度算法。因此，准确地说，2.6.23以后的版本进程调度是基于O（1）+O（lgn）时间复杂度的调度。基于这两部分的设计和Linux内核代码实现将在本文给与介绍。
2.1基于实时进程调度
Linux2.4内核维护双向循环队列runqueue，一旦调度时机触发，内核重新计算当前队列中所有进程运行权值，并从中挑选出权值最高的进程作为当前进程投入运行。其弊端是显而易见的：
1）调度时机触发，重新计算runqueue中每个进程运行权值，复杂度为O(n)，且调度性能与内核负载相关。
2）runqueue同时管理着实时进程与非实时进程（普通进程），内核通