Linux进程调度算法分析

1、linux进程调度算法分析摘要：基于x86平台linux2.6.26内核进程调度部分代码，刨析linux进程调度算法，对 算法的原理，实现和复杂度进行了分析并提出了算法改进措施。1. linux进程调度概述linux系统支持用户态进程和内核线程，需婆说明的是,linux没有提供用户态线程支持， 实现用户态线程需要引入第三方线程库。操作系统进程调度是整个操作系统理论的核心，在设计进程调动机制需要考虑的具体问 题主要有：1) 调度的时札 在什么情况下，什么时候进行调度。2) 调度的“政策” (policy)：根据什么准则挑选下一个进入运行的进程。3) 调度的方式：是"可杀ij夺”(pre

2、emptive)还是"不可剥夺” (nonpreemptive)o图1.2.1给出了 linux进程状态转换关系：图1 linux进程状态转换图linux进程调度分为自愿调度和强制调度两种。1) 在内核空间，一个进程可以通过schedule。启动一诙调度，也可以在调用schedule!) 之前，将本进程状:态设置为tasknterruptible或task_uninterruptible,暂时放弃运行 而进入睡眠。这通常发生在来口用户空间的系统调用被阻塞。在用户空间，用户进程可以通 过系统调用nanosleep()达到目的。2) 调度还可以是非h愿的。在一定条件下，内核会强制性剥夺当

3、前进程运行而调度其 他进程进入运行。linux调度政策菇础是时间片轮转+优先级抢山的结合，为了满足不同应川的需要，内核 提供了三种调度方法：1) sched_fif0实时调度策略，先到先服务2) sched_rr实时调度策略，时间片轮转3) sched_normal分吋调度策略(在2.6内核以前为sched_other)。用户进程可以 通过系统调用sched_setscheduler ()设定自己的调度策略。sched_fif0和sched_rr的区 别是，前者只有在就绪队列屮有优先级更高的进程，或进程被阻塞，或自愿调用阻塞原语(如 sleep_onjnterruptible)的情况下,才会放

4、弃cpu,而如果调度策略是后者,当前进程与就 绪队列里其他进程按round robin方式共享cpu-2. linux进程调度原理基本的操作系统进程调度算法包扌舌先來先服务(first come first serve),时间片轮转 (round robin)，多级反馈轮转法(round robin with multiple feedback),优先级法(静态优 先级法/动态优先级法)，煎作业优先法(shortest job first),最高响应比优先法(highest response_ratio next)o不同调度算法应用场合不同，某些调度算法可能仅具有研究价值，实 际中鲜有应用；而

5、某些调度算法需要互补以完成设计需求。但是，无论哪种进程调度算法, 都要面对以下实际问题：1) 调度器对实时进程的响应；2) 调度器的调度开销，以及系统进程负载对调度的影响；3) 在smp环境下，当前cpu调度对其他cpu的影响；unux2.6.x内核进程调度算法为解决上述问题，设计了全新的数据结构和调度算法，但 具基本策路仍是以优先级为基础的抢占式调度，与2.6以前内核版本不同，内核抢占可能发 生在内核态(因此2.6版本的内核代码必须考虑到重入问题)。2.6版木的内核调度也是几度变迁，其基本思想是1)捉高实时进程调度相应比2)普通 进程调度体现“完全公平这个思想”。从2.6早期版本sd (st

6、aircase schedule)调度器,到 2.6.23 版本的 rsdl (the rotating staircase deadline schedule)调度器,再至 2.6.26 版本 cfs (complete fair schedule)调度器，调度机制不断完善。2.6.26内核进程调度吸收了前期版 木的精华，通过全新设计数据结构和算法，为实时进程(sched_fifo/sched_rr)提供0(1) 时间复杂度的调度算法，同时，为了兼顾“完全公平”这一设计思路，设计了 cfs调度器, 为普通进程提供满足公平性为原则的0 (1卯)时间复杂度的调度算法。因此，准确地说， 2.6.2

7、3以后的版木进程调度是基于0 (1) +0 (ign)时间复杂度的调度。基于这两部分的设 计和linux内核代码实现将在木文给与介绍。2.1基于实时进程调度linux2.4内核维护双向循环队列runqueue, 一旦调度时机触发，内核重新计算当前队列 中所有进程运行权值，并从中挑选出权值最高的进程作为当前进程投入运行。其弊端是显而 易见的：1) 调度时机触发，重新计算runqueue中每个进程运行权值，复杂度为0(n),且调度性能与 内核负载相关。2) runqueue同时管理着实时进程与非实时进程(普通进程)，内核通过进程属性，如实时 或非实时、实时进程优先级、川户进程或内核线程相关因索来计

8、算运行权值count,灵活性 低，且不便于理解和维护。从linux2.6早期版本开始，内核进程对实时进程调度重新设计了 0 (1)调度器 sd/rsdl, rsdl调度器是在sd调度器基础上的改进。linux2.6.26内核在早期2.6内核基础上 简化了 rsdl调度器，把就绪进程队列和过期进程队列合并为就绪队列。下面结合内核代码， 给与实时进程0 (1)调度器的实现邙艮于篇幅，本文给出核心数据结构关键成员的注释)。 1)就绪进程队歹【j structrqstructrq /* i/* runqueue lock: */spinlock_t lock;/*就绪队列屮进程个数*/ unsigne

9、d long nr_running;/*/*普通进程就绪队列*/structcfs_rqcfs;/*实吋进程就绪队列*/ structrt_rqrt;/*/*就绪队列工作时间*/u64 clock;* /* used by load_balanee */ structtask_struct *migration_thread; structlist_headmigratio n_ queue;内核为系统中每个cpu维护独立的structrq数据结构，在smp环境下，cpu z间互不 彫响。实时进程调度的核心数据结构是structrt_rq,定义如卜：2）实吋进程就绪队列structrt_rqs

10、tructrt_rq /*实时进程优先级队列*/structrt_prio_array active;/*实时进程个数*/unsigned long rt_nr_running;/* . */*实时进程队列工作时间*/u64 rt_time;/*. */;rt_rq屮关键的数据结构在于prio_array_active,定义如下：3）优先级队列 structrt_prio_arraystructrt_prio_array /*优先级位图*/declare_bitmap（bitmap/ max_rt_prio+1）;/*优先级队列*/structlist_head queuemax_rt_pri

11、o;；4）进程运行信息结构schedjnfostructsched_info /* cumulative counters */unsigned long pcount;/* # of times run on thiscpu */unsigned long longcpu_time, /* time spent on the cpu */run_delay; /* time spent waiting on a runqueue */* timestamps */unsigned long ionglast_arrival,/* when we last ran on a cpu */las

12、t_queued;/* when we were last queued to run */；schedjnfo维护进程运行时的实时信息，代码作者的注释已比较详细，该结构数据在schedule 进程切换发主时被更新。structrt_prio_array成员bitmap是进程优先级队列位图，其人小是max_rt_prio + 1,如呆某 优先级就绪进程队列不空，那么bitmap相应的位置1,否则为0。queue为进程优先级队列 数组，每个进程优先级队列用双端循环链表来描述。内核寻找优先级最高的任务需要两个简 单的bsfs汇编指令，查询优先级队列位图，然后从优先级队列数组中取出对应的优先级队 列

13、的对头所指向的进程，即为下一个投入运行的进程。当进程用完了口己的时间片后，被加 入active数组优先级队列的末尾，调度任务从当前实时任务优先级队列屮取出队首任务投入 运行。实时进程调度核心数据结构z间的关系如图2：2.2棊于普通进程调度linux2.6.23内核进程调度支持cfs调度器，它从rsdl/sd'p吸取了完全公平的思想， 不再跟踪进程的睡眠吋间，也不再企图区分交互式进程。它将所有的进程(普通进程)都统 一对待，这就是公平的含义。cfs调度器使用红黑树管理就绪进程，所冇状态为 task_running的进程都被插入红黑树。在每个调度点，cfs调度器都会选择红黑树的最左 边的叶

14、子节点作为下一个将获得cpu的进程。山于红黑树是平衡树，因此采用cfs调度器 调度时间复杂度是o(lgn)o在cfs中,tick中断首先更新调度信息。然后调整当前进程在红 黑树屮的位置。调整完成示如果发现当前进程不再是最左边的叶了，就标记needesched 标志，中断返回时就会调用scheduler。完成进程切换。否则当前进程继续占用cpu。从这里 可以看到cfs调度器带来的两点变换：1)抛弃了传统的时间片概念，进程运行权值的计算 分散到tick中断发生时。tick中断只需更新红黑树，以前的所有调度器都在tick中断中递减 时间片，当时间片或者配额被用完时才触发优先级调整并重新调度(参见函数

15、update_curr() 调用时机)。2) cfs为内核抢占调度提供完美支持。理解cfs的关键就是了解红黑树键值的计算方法。该键值由三个因子计算而得：一是进程己 经占用的cpu时间；二是当前进程的nice值：三是当前的cpu负载。cfs调度器维护cpu 级变量min_vruntime；同时'，每个进程维护进程级变量vruntime。其中，min_vruntime二max (min_vruntime, vruntime),即调度前min_vruntime的数值和备选进程运行时间权值的大者。 进程插入红黑树的键值为vruntime-min.vruntimeo它们的差值代表了一个进程的公平程度。 该值越大，代表当前进程相对于其它进程越不公平。因此该值越大，键值越大，从而使得当 前进程向红黑树的右侧移动，越晚被选中。以上,介绍了 linux2.6.26内核两种主流调度器,2.6.26内核还为idle进程提供了专门的调度 器(idle_sched_class)0需要指出的是，进程调度首先选择实时进程调度器，即进程总是以 保证实吋进程最髙运行权限，如來系统中没有实时进程，那么才会选择cfs调度器