Linux 2.6 调度系统分析

1．前言Linux的市场非常广阔，从桌面工作站到低端服务器，它都是任何商用操作系统的有力竞争对手。目前，Linux正全力进军嵌入式系统和高端服务器系统领域，但它的技术缺陷限制了它的竞争力：缺乏对实时任务的支持，多处理机可扩展性差。在2.4内核中，造成这两个弱项的关键原因之一就是调度器设计上的缺陷。2.6调度系统从设计之初就把开发重点放在更好满足实时性和多处理机并行性上，并且基本实现了它的设计目标。主要设计者，传奇式人物IngoMolnar将新调度系统的特性概括为如下几点：继承和发扬2.4版调度器的特点：o交互式作业优先o轻载条件下调度/唤醒的高性能o公平共享o基于优先级调度o高CPU使用率oSMP高效亲和o实时调度和cpu绑定等调度手段在此基础之上的新特性：oO(1)调度算法，调度器开销恒定（与当前系统负载无关），实时性能更好o高可扩展性，锁粒度大幅度减小o新设计的SMP亲和方法o优化计算密集型的批处理作业的调度o重载条件下调度器工作更平滑o子进程先于父进程运行等其他改进在2.5.x的试验版本中，新的调度器的开发一直受到广泛关注，实测证明它的确使系统性能得到很大改善。本文就从新设计的数据结构开始，围绕2.6对于2.4所作的改进，对2.6调度系统的原理和实现细节进行分析。2.6调度器设计相当复杂，文中还存在很多需要继续研究的地方，特别是各个调度参数的设定，随着核心版本的升级，可能还会继续修正。回页首2．新的数据结构runqueue我们知道，在2.4内核中，就绪进程队列是一个全局数据结构，调度器对它的所有操作都会因全局自旋锁而导致系统各个处理机之间的等待，使得就绪队列成为一个明显的瓶颈。2.4的就绪队列是一个简单的以runqueue_head为头的双向链表，在2.6中，就绪队列定义为一个复杂得多的数据结构structrunqueue，并且，尤为关键的是，每一个CPU都将维护一个自己的就绪队列，--这将大大减小竞争。O(1)算法中很多关键技术都与runqueue有关，所以，我们对调度器的分析就先从runqueue结构开始。1)prio_array_t*active,*expired,arrays[2]runqueue中最关键的数据结构。每个CPU的就绪队列按时间片是否用完分为两部分，分别通过active指针和expired指针访问，active指向时间片没用完、当前可被调度的就绪进程，expired指向时间片已用完的就绪进程。每一类就绪进程都用一个structprio_array的结构表示：structprio_array{intnr_active;/*本进程组中的进程数*/structlist_headqueue[MAX_PRIO];/*以优先级为索引的HASH表，见下*/unsignedlongbitmap[BITMAP_SIZE];/*加速以上HASH表访问的位图，见下*/};图1：active、expired数组示例图中的task并不是task_struct结构指针，而是task_struct::run_list，这是一个小技巧，详见下文run_list的解释。在2.4版的内核里，查找最佳候选就绪进程的过程是在调度器schedule()中进行的，每一次调度都要进行一次（在for循环中调用goodness()），这种查找过程与当前就绪进程的个数相关，因此，查找所耗费的时间是O(n)级的，n是当前就绪进程个数。正因为如此，调度动作的执行时间就和当前系统负载相关，无法给定一个上限，这与实时性的要求相违背。在新的O(1)调度中，这一查找过程分解为n步，每一步所耗费的时间都是O(1)量级的。prio_array中包含一个就绪队列数组，数组的索引是进程的优先级（共140级，详见下static_prio属性的说明），相同优先级的进程放置在相应数组元素的链表queue中。调度时直接给出就绪队列active中具有最高优先级的链表中的第一项作为候选进程（参见调度器），而优先级的计算过程则分布到各个进程的执行过程中进行（见优化了的优先级计算方法）。为了加速寻找存在就绪进程的链表，2.6核心又建立了一个位映射数组来对应每一个优先级链表，如果该优先级链表非空，则对应位为1，否则为0。核心还要求每个体系结构都构造一个sched_find_first_bit()函数来执行这一搜索操作，快速定位第一个非空的就绪进程链表。采用这种将集中计算过程分散进行的算法，保证了调度器运行的时间上限，同时在内存中保留更加丰富的信息的做法也加速了候选进程的定位过程。这一变化简单而又高效，是2.6内核中的亮点之一。arrays二元数组是两类就绪队列的容器，active和expired分别指向其中一个。active中的进程一旦用完了自己的时间片，就被转移到expired中，并设置好新的初始时间片；而当active为空时，则表示当前所有进程的时间片都消耗完了，此时，active和expired进行一次对调，重新开始下一轮的时间片递减过程（参见调度器）。回忆一下2.4调度系统，进程时间片的计算是比较耗时的，在早期内核版本中，一旦时间片耗尽，就在时钟中断中重新计算时间片，后来为了提高效率，减小时钟中断的处理时间，2.4调度系统在所有就绪进程的时间片都耗完以后在调度器中一次性重算。这又是一个O(n)量级的过程。为了保证O(1)的调度器执行时间，2.6的时间片计算在各个进程耗尽时间片时单独进行，而通过以上所述简单的对调来完成时间片的轮转（参见调度器）。这又是2.6调度系统的一个亮点。2)spinlock_tlockrunqueue的自旋锁，当需要对runqueue进行操作时，仍然应该锁定，但这个锁定操作只影响一个CPU上的就绪队列，因此，竞争发生的概率要小多了。3)task_t*curr本CPU正在运行的进程。4)tast_t*idle指向本CPU的idle进程，相当于2.4中init_tasks[this_cpu()]的作用。5)intbest_expired_prio记录expired就绪进程组中的最高优先级（数值最小）。该变量在进程进入expired队列的时候保存（schedule_tick()），用途见expired_timestamp的解释）。6)unsignedlongexpired_timestamp当新一轮的时间片递减开始后，这一变量记录着最早发生的进程耗完时间片事件的时间（jiffies的绝对值，在schedule_tick()中赋），它用来表征expired中就绪进程的最长等待时间。它的使用体现在EXPIRED_STARVING(rq)宏上。上面已经提到，每个CPU上维护了两个就绪队列，active和expired。一般情况下，时间片结束的进程应该从active队列转移到expired队列中（schedule_tick()），但如果该进程是交互式进程，调度器就会让其保持在active队列上以提高它的响应速度。这种措施不应该让其他就绪进程等待过长时间，也就是说，如果expired队列中的进程已经等待了足够长时间了，即使是交互式进程也应该转移到expired队列上来，排空active。这个阀值就体现在EXPIRED_STARVING(rq)上：在expired_timestamp和STARVATION_LIMIT都不等于0的前提下，如果以下两个条件都满足，则EXPIRED_STARVING()返回真：（当前绝对时间-expired_timestamp）=（STARVATION_LIMIT*队列中所有就绪进程总数+1），也就是说expired队列中至少有一个进程已经等待了足够长的时间；正在运行的进程的静态优先级比expired队列中最高优先级要低（best_expired_prio，数值要大），此时当然应该尽快排空active切换到expired上来。7)structmm_struct*prev_mm保存进程切换后被调度下来的进程（称之为prev）的active_mm结构指针。因为在2.6中prev的active_mm是在进程切换完成之后释放的（mmdrop()），而此时prev的active_mm项可能为NULL，所以有必要在runqueue中预先保留。8)unsignedlongnr_running本CPU上的就绪进程数，该数值是active和expired两个队列中进程数的总和，是说明本CPU负载情况的重要参数（详见调度器相关的负载平衡）。9)unsignedlongnr_switches记录了本CPU上自调度器运行以来发生的进程切换的次数。10)unsignedlongnr_uninterruptible记录本CPU尚处于TASK_UNINTERRUPTIBLE状态的进程数，和负载信息有关。11)atomic_tnr_iowait记录本CPU因等待IO而处于休眠状态的进程数。12)unsignedlongtimestamp_last_tick本就绪队列最近一次发生调度事件的时间，在负载平衡的时候会用到（见调度器相关的负载平衡）。13)intprev_cpu_load[NR_CPUS]记录进行负载平衡时各个CPU上的负载状态（此时就绪队列中的nr_running值），以便分析负载情况（见调度器相关的负载平衡）。14)atomic_t*node_nr_running;intprev_node_load[MAX_NUMNODES]这两个属性仅在NUMA体系结构下有效，记录各个NUMA节点上的就绪进程数和上一次负载平衡操作时的负载情况（见NUMA结构下的调度）。15)task_t*migration_thread指向本CPU的迁移进程。每个CPU都有一个核心线程用于执行进程迁移操作（见调度器相关的负载平衡）。16)structlist_headmigration_queue需要进行迁移的进程列表（见调度器相关的负载平衡）。调度系统代码结构绝大多数调度系统的实现代码，包括runqueue结构的定义，都在[kernel/sched.c]文件中，这样做的目的是将所有调度系统的代码集中起来，便于更新和替换。除非特别注明，本文所引代码和函数实现均位于[kernel/sched.c]中。回页首3．改进后的task_struct2.6版的内核仍然用task_struct来表征进程，尽管对线程进行了优化，但线程的内核表示仍然与进程相同。随着调度器的改进，task_struct的内容也有了改进，交互式进程优先支持、内核抢占支持等新特性，在task_struct中都有所体现。在task_struct中，有的属性是新增加的，有的属性的值的含义发生了变化，而有的属性仅仅是改了一下名字。1)state进程的状态仍然用state表示，不同的是，2.6里的状态常量重新定义了，以方便位操作：/*节选自[include/linux/sched.h]*/#defineTASK_RUNNING0#defineTASK_INTERRUPTIBLE1#defineTASK_UNINTERRUPTIBLE2#defineTASK_STOPPED4#defineTASK_ZOMBIE8#defineTASK_DEAD16新增加的TASK_DEAD指的是已经退出且不需要父进程来回收的进程。2)timestamp进程发生调度事件的时间（单位是nanosecond，见下）。包括以下几类：被唤醒的时间（在activate_task()中设置）；被切换下来的时间（schedule()）；被切换上去的时间（schedule()）；负载平衡相关的赋值（见调度器相关的负载平衡）。从这个值与当前时间的差值中可以分别获得在就绪队列中等待运行的时长、运行时长等与优先级计算相关的信息（见优化了的优先级计算方法）。两种时间单位系统的时间是以nanosecond（十亿分之一秒）为单位的，但这一数值粒度过细，大部分核心应用仅能取得它的绝对值，感知不到它的精度。时间相关的核心应用通常围绕时钟中断进行，在Linux2