Linux 2.6 调度系统分析.doc

1 前言Linux 的市场非常广阔，从桌面工作站到低端服务器，它都是任何商用操作系统的有力竞争对手。目前，Linux 正全力进军嵌入式系统和高端服务器系统领域，但它的技术缺陷限制了它的竞争力：缺乏对实时任务的支持，多处理机可扩展性差。在 2.4 内核中，造成这两个弱项的关键原因之一就是调度器设计上的缺陷。2.6 调度系统从设计之初就把开发重点放在更好满足实时性和多处理机并行性上，并且基本实现了它的设计目标。主要设计者，传奇式人物 Ingo Molnar 将新调度系统的特性概括为如下几点： 继承和发扬 2.4 版调度器的特点： o 交互式作业优先 o 轻载条件下调度/唤醒的高性能 o 公平共享 o 基于优先级调度 o 高 CPU 使用率 o SMP 高效亲和 o 实时调度和 cpu 绑定等调度手段 在此基础之上的新特性： o O(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 中，就绪队列定义为一个复杂得多的数据结构 struct runqueue，并且，尤为关键的是，每一个 CPU 都将维护一个自己的就绪队列，-这将大大减小竞争。O(1)算法中很多关键技术都与 runqueue 有关，所以，我们对调度器的分析就先从 runqueue 结构开始。1) prio_array_t *active, *expired, arrays2 runqueue 中最关键的数据结构。每个 CPU 的就绪队列按时间片是否用完分为两部分，分别通过 active 指针和 expired 指针访问，active 指向时间片没用完、当前可被调度的就绪进程，expired 指向时间片已用完的就绪进程。每一类就绪进程都用一个 struct prio_array 的结构表示：struct prio_array int nr_active;/* 本进程组中的进程数 */struct list_head queueMAX_PRIO;/* 以优先级为索引的 HASH 表，见下 */unsigned long bitmapBITMAP_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_t lock runqueue 的自旋锁，当需要对 runqueue 进行操作时，仍然应该锁定，但这个锁定操作只影响一个 CPU 上的就绪队列，因此，竞争发生的概率要小多了。3) task_t *curr 本 CPU 正在运行的进程。4) tast_t *idle 指向本 CPU 的 idle 进程，相当于 2.4 中 init_tasksthis_cpu() 的作用。5) int best_expired_prio 记录 expired 就绪进程组中的最高优先级（数值最小）。该变量在进程进入 expired 队列的时候保存（schedule_tick()），用途见 expired_timestamp的解释）。6) unsigned long expired_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) struct mm_struct *prev_mm 保存进程切换后被调度下来的进程（称之为 prev）的 active_mm 结构指针。因为在 2.6 中 prev 的 active_mm 是在进程切换完成之后释放的（mmdrop()），而此时 prev 的 active_mm 项可能为 NULL，所以有必要在 runqueue 中预先保留。8) unsigned long nr_running 本 CPU 上的就绪进程数，该数值是 active 和 expired 两个队列中进程数的总和，是说明本 CPU 负载情况的重要参数（详见调度器相关的负载平衡）。9) unsigned long nr_switches 记录了本 CPU 上自调度器运行以来发生的进程切换的次数。10) unsigned long nr_uninterruptible 记录本 CPU 尚处于 TASK_UNINTERRUPTIBLE 状态的进程数，和负载信息有关。11) atomic_t nr_iowait 记录本 CPU 因等待 IO 而处于休眠状态的进程数。12) unsigned long timestamp_last_tick 本就绪队列最近一次发生调度事件的时间，在负载平衡的时候会用到（见调度器相关的负载平衡）。13) int prev_cpu_loadNR_CPUS 记录进行负载平衡时各个 CPU 上的负载状态（此时就绪队列中的 nr_running 值），以便分析负载情况（见调度器相关的负载平衡）。14) atomic_t *node_nr_running; int prev_node_loadMAX_NUMNODES 这两个属性仅在 NUMA 体系结构下有效，记录各个 NUMA 节点上的就绪进程数和上一次负载平衡操作时的负载情况（见NUMA 结构下的调度）。15) task_t *migration_thread 指向本 CPU 的迁移进程。每个 CPU 都有一个核心线程用于执行进程迁移操作（见调度器相关的负载平衡）。16) struct list_head migration_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 */#define TASK_RUNNING0#define TASK_INTERRUPTIBLE1#define TASK_UNINTERRUPTIBLE2#define TASK_STOPPED4#define TASK_ZOMBIE8#define TASK_DEAD16新增加的TASK_DEAD指的是已经退出且不需要父进程来回收的进程。2) timestamp进程发生调度事件的时间（单位是 nanosecond，见下）。包括以下几类： 被唤醒的时间（在 activate_task() 中设置）； 被切换下来的时间（schedule()）； 被切换上去的时间（schedule()）； 负载平衡相关的赋值（见调度器相关的负载平衡）。 从这个值与当前时间的差值中可以分别获得在就绪队列中等待运行的时长、运行时长等与优先级计算相关的信息（见优化了的优先级计算方法）。两种时间单位 系统的时间是以 nanosecond（十亿分之一秒）为单位的，但这一数值粒度过细，大部分核心应用仅能取得它的绝对值，感知不到它的精度。 时间相关的核心应用通常围绕时钟中断进行，在 Linux 2.6 中，系统时钟每 1 毫秒中断一次（时钟频率，用 HZ 宏表示，定义为 1000，即每秒中断 1000 次，-2.4 中定义为 100，很多应用程序也仍然沿用 100 的时钟频率），这个时间单位称为一个 jiffie。很多核心应用都是以 jiffies 作为时间单位，例如进程的运行时间片。 jiffies 与绝对时间之间的转换公式如下： nanosecond=jiffies*1000000 核心用两个宏来完成两种时间单位的互换：JIFFIES_TO_NS()、NS_TO_JIFFIES()，很多时间宏也有两种形式，例如 NS_MAX_SLEEP_AVG 和 MAX_SLEEP_AVG。 3) prio优先级，相当于 2.4 中 goodness() 的计算结果，在 0MAX_PRIO-1 之间取值（MAX_PRIO 定义为 140），其中 0MAX_RT_PRIO-1 （MAX_RT_PRIO 定义为100）属于实时进程范围，MAX_RT_PRIOMX_PRIO-1 属于非实时进程。数值越大，表示进程优先级越小。2.6 中，动态优先级不再统一在调度器中计算和比较，而是独立计算，并存储在进程的 task_struct 中，再通过上面描述的 priority_array 结构自动排序。prio 的计算和很多因素相关，在优化了的优先级计算方法中会详细讨论。4) static_prio静态优先级，与 2.4 的 nice 值意义相同，但转换到与 prio 相同的取值区间。nice 值沿用 Linux 的传统，在 -20 到 19 之间变动，数值越大，进程的优先级越小。nice 是用户可维护的，但仅影响非实时进程的优先级。2.6 内核中不再存储 nice 值，而代之以 static_prio。进程初始时间片的大小仅决定于进程的静态优先级，这一点不论是实时进程还是非实时进程都一样，不过实时进程的static_prio 不参与优先级计算。nice 与 static_prio 之间的关系如下： static_prio = MAX_RT_PRIO + nice + 20 内核定义了两个宏用来完成这一转换：PRIO_TO_NICE()、NICE_TO_PRIO()。5) activated表示进程因什么原因进入就绪态，这一原因会影响到调度优先级的计算。activated 有四个值： -1，进程从 TASK_UNINTERRUPTIBLE 状态被唤醒； 0，缺省值，进程原本就处于就绪态； 1，进程从 TASK_INTERRUPTIBLE 状态被唤醒，且不在中断上下文中； 2，进程从 TASK_INTERRUPTIBLE 状态被唤醒，且在中断上下文中。 activated 初值为 0，在两个地方修改，一是在 schedule() 中，被恢复为 0，另一个就是 activate_task()，这个函数由 try_to_wake_up() 函数调用，用于激活休眠进程： 如果是中断服务程序调用的 activate_task()，也就是说进程由中断激活，则该进程最有可能是交互式的，因此，置 activated=2；否则置activated=1。 如果进程是从 TASK_UNINTERRUPTIBLE 状态中被唤醒的，则 activated=-1（在try_to_wake_up()函数中）。 activated 变量的具体含义和使用见优化了的优先级计算方式。 6) sleep_avg进程的平均等待时间（以 nanosecond 为单位），在 0 到 NS_MAX_SLEEP_AVG 之间取值，初值为 0，相当于进程等待时间与运行时间的差值。sleep_avg 所代表的含义比较丰富，既可用于评价该进程的交互程度，又可用于表示该进程需要运行的紧迫性。这个值是动态优先级计算的关键因子，sleep_avg 越大，计算出来的进程优先级也越高（数值越小）。在下文进程平均等待时间 sleep_avg 中会详细分析 sleep_avg 的变化过程。7) interactive_credit这个变量记录了本进程的交互程度，在 -CREDIT_LIMIT 到 CREDIT_LIMIT+1 之间取值。进程被创建出来时，初值为 0，而后根据不同的条件加 1 减 1，一旦超过 CREDIT_LIMIT（只可能等于 CREDIT_LIMIT+1），它就不会再降下来，表示进程已经通过了交互式测试，被认为是交互式进程了。interactive_credit具体的变化过程在更精确的交互式进程优先中会详细描述。8) nvcsw/nivcsw/cnvcsw/cnivcsw进程切换计数。9) time_slice 进程的时间片余额，相当于 2.4 的 counter，但不再直接影响进程的动态优先级。在新的运行时间片表现中专门分析了 time_slice 的行为。10) first_time_slice 0 或 1，表示是否是第一次拥有时间片（刚创建的进程）。这一变量用来判断进程结束时是否应当将自己的剩余时间片返还给父进程（见新的运行时间片表现）。11) run_list 前面提到，优先级数组 prio_array 结构中按顺序排列了各个优先级下的所有进程，但实际上数组中每一个元素都是 list_head 结构，以它为表头的链表中的每一个元素也是 list_head，其中链接的就是 task_struct 中的 run_list 成员。这是一个节省空间、加速访问的小技巧：调度器在 prio_array 中找到相应的 run_list，然后通过 run_list 在 task_struct 中的固定偏移量找到对应的 task_struct（参见 enqueue_task()、dequeue_task() 和 list.h 中的操作）。12) array记录当前 CPU 的活跃就绪队列（runqueue:active）。13) thread_info当前进程的一些运行环境信息，其中有两个结构成员与调度关系紧密： preempt_count：初值为 0 的非负计数器，大于 0 表示核心不宜被抢占； flags：其中有一个 TIF_NEED_RESCHED 位，相当于 2.4 中的 need_resched 属性，如果当前运行中的进程此位为 1，则表示应该尽快启动调度器。 在 2.4 中，每个进程的 task_struct 都位于该进程核心栈的顶端（低址部分），内核可以通过栈寄存器 ESP 轻松访问到当前进程的 task_struct。在 2.6 中，仍然需要频繁访问这个名为 current 的数据结构，但现在，进程核心栈顶保存的是其中的 thread_info 属性，而不是完整的 task_struct 了。这样做的好处是仅将最关键的、访问最频繁的运行环境保存在核心栈里（仍然是两个页大小），而将 task_struct 大部分内容通过 thread_info:task 指针保存在栈外，以方便扩充。thread_info 的分配方式和访问方式与 2.4 中的 task_struct 完全相同，现在的 current 需要这样来访问：/* 节选自include/asm-i386/current.h */static inline struct task_struct * get_current(void)return current_thread_info()-task;#define current get_current()其中current_thread_info()定义为：/* 节选自include/asm-i386/thread_info.h */static inline struct thread_info *current_thread_info(void)struct thread_info *ti;_asm_(andl %esp,%0; :=r (ti) : 0 (8191UL);return ti;图2：现在的current回页首4 新的运行时间片表现2.6 中，time_slice 变量代替了 2.4 中的 counter 变量来表示进程剩余运行时间片。time_slice 尽管拥有和 counter 相同的含义，但在内核中的表现行为已经大相径庭，下面分三个方面讨论新的运行时间片表现：1) time_slice 基准值和 counter 类似，进程的缺省时间片与进程的静态优先级（在 2.4 中是 nice 值）相关，使用如下公式得出：MIN_TIMESLICE + (MAX_TIMESLICE - MIN_TIMESLICE) * (MAX_PRIO-1 - (p)-static_prio) / (MAX_USER_PRIO-1)代入各个宏的值后，结果如图所示：可见，核心将 100139 的优先级映射到 200ms10ms 的时间片上去，优先级数值越大，则分配的时间片越小。和 2.4 中进程的缺省时间片比较，当 nice 为 0 时，2.6 的基准值 100ms 要大于 2.4 的 60ms。进程的平均时间片 核心定义进程的平均时间片 AVG_TIMESLICE 为 nice 值为 0 的时间片长度，根据上述公式计算所得大约是 102ms。这一数值将作为进程运行时间的一个基准值参与优先级计算。 2) time_slice 的变化进程的 time_slice 值代表进程的运行时间片剩余大小，在进程创建时与父进程平分时间片，在运行过程中递减，一旦归 0，则按 static_prio 值重新赋予上述基准值，并请求调度。时间片的递减和重置在时钟中断中进行（sched_tick()），除此之外，time_slice 值的变化主要在创建进程和进程退出过程中：a) 进程创建 和 2.4 类似，为了防止进程通过反复 fork 来偷取时间片，子进程被创建时并不分配自己的时间片，而是与父进程平分父进程的剩余时间片。也就是说，fork 结束后，两者时间片之和与原先父进程的时间片相等。 b) 进程退出 进程退出时（sched_exit()），根据 first_time_slice 的值判断自己是否从未重新分配过时间片，如果是，则将自己的剩余时间片返还给父进程（保证不超过 MAX_TIMESLICE）。这个动作使进程不会因创建短期子进程而受到惩罚（与不至于因创建子进程而受到奖励相对应）。如果进程已经用完了从父进程那分得的时间片，就没有必要返还了（这一点在 2.4 中没有考虑）。 3) time_slice 对调度的影响在 2.4 中，进程剩余时间片是除 nice 值以外对动态优先级影响最大的因素，并且休眠次数多的进程，它的时间片会不断叠加，从而算出的优先级也更大，调度器正是用这种方式来体现对交互式进程的优先策略。但实际上休眠次数多并不表示该进程就是交互式的，只能说明它是 IO 密集型的，因此，这种方法精度很低，有时因为误将频繁访问磁盘的数据库应用当作交互式进程，反而造成真正的用户终端响应迟缓。2.6 的调度器以时间片是否耗尽为标准将就绪进程分成 active、expired 两大类，分别对应不同的就绪队列，前者相对于后者拥有绝对的调度优先权-仅当active 进程时间片都耗尽，expired 进程才有机会运行。但在 active 中挑选进程时，调度器不再将进程剩余时间片作为影响调度优先级的一个因素，并且为了满足内核可剥夺的要求，时间片太长的非实时交互式进程还会被人为地分成好几段（每一段称为一个运行粒度，定义见下）运行，每一段运行结束后，它都从 cpu 上被剥夺下来，放置到对应的 active 就绪队列的末尾，为其他具有同等优先级的进程提供运行的机会。这一操作在 schedule_tick() 对时间片递减之后进行。此时，即使进程的时间片没耗完，只要该进程同时满足以下四个条件，它就会被强制从 cpu 上剥夺下来，重新入队等候下一次调度： 进程当前在 active 就绪队列中； 该进程是交互式进程（TASK_INTERACTIVE()返回真，见更精确的交互式进程优先,nice 大于 12 时，该宏返回恒假）； 该进程已经耗掉的时间片（时间片基准值减去剩余时间片）正好是运行粒度的整数倍； 剩余时间片不小于运行粒度 运行粒度的定义运行粒度 TIMESLICE_GRANULARITY 被定义为与进程的 sleep_avg 和系统总 CPU 数相关的宏。因为 sleep_avg 实际上代表着进程的非运行时间与运行时间的差值，与交互程度判断关系密切，所以，运行粒度的定义说明了内核的以下两个调度策略： 进程交互程度越高，运行粒度越小，这是交互式进程的运行特点所允许的；与之对应，CPU-bound 的进程为了避免 Cache 刷新，不应该分片； 系统 CPU 数越多，运行粒度越大。 回页首5 优化了的优先级计算方法在 2.4 内核中，优先级的计算和候选进程的选择集中在调度器中进行，无法保证调度器的执行时间，这一点在前面介绍 runqueue 数据结构的时候已经提及。2.6 内核中候选进程是直接从已按算法排序的优先级队列数组中选取出来的，而优先级的计算则分散到多处进行。这一节分成两个部分对这种新的优先级计算方法进行描述，一部分是优先级计算过程，一部分是优先级计算（以及进程入队）的时机。1) 优先级计算过程动态优先级的计算主要由 effect_prio() 函数完成，该函数实现相当简单，从中可见非实时进程的优先级仅决定于静态优先级（static_prio）和进程的sleep_avg 值两个因素，而实时进程的优先级实际上是在 setscheduler() 中设置的（详见调度系统的实时性能，以下仅考虑非实时进程），且一经设定就不再改变。相比较而言，2.4 的 goodness() 函数甚至要更加复杂,它考虑的 CPU Cache 失效开销和内存切换的开销这里都已经不再考虑。2.6 的动态优先级算法的实现关键在 sleep_avg 变量上，在 effective_prio() 中，sleep_avg 的范围是 0MAX_SLEEP_AVG，经过以下公式转换后变成-MAX_BONUS/2MAX_BONUS/2 之间的 bonus：(NS_TO_JIFFIES(p)-sleep_avg) * MAX_BONUS / MAX_SLEEP_AVG) - MAX_BONUS/2如下图所示：再用这个 bonus 去减静态优先级就得到进程的动态优先级（并限制在 MAX_RT_PRIO和MAX_PRIO 之间），bonus 越小，动态优先级数值越大，优先级越低。也就是说，sleep_avg 越大，优先级也越高。MAX_BONUS 定义为 MAX_USER_PRIO*PRIO_BONUS_RATIO/100，也就是说，sleep_avg 对动态优先级的影响仅在静态优先级的用户优先级区（100140）的1/4区间（5）之内，相对而言，静态优先级，也就是用户指定的 nice 值在优先级计算的比重要大得多。这也是 2.6 调度系统中变化比较大的一个地方，调度器倾向于更多地由用户自行设计进程的执行优先级。sleep_avg 反映了调度系统的两个策略：交互式进程优先和分时系统的公平共享，在下一节中我们还要专门分析。2) 优先级计算时机优先级的计算不再集中在调度器选择候选进程的时候进行了，只要进程状态发生改变，核心就有可能计算并设置进程的动态优先级：a) 创建进程 在wake_up_forked_process()中，子进程继承了父进程的动态优先级，并添加到父进程所在的就绪队列中。如果父进程不在任何就绪队列中（例如它是 IDLE 进程），那么就通过 effect_prio() 函数计算出子进程的优先级，而后根据计算结果将子进程放置到相应的就绪队列中。b) 唤醒休眠进程 核心调用 recalc_task_prio() 设置从休眠状态中醒来的进程的动态优先级，再根据优先级放置到相应就绪队列中。c) 调度到从 TASK_INTERRUPTIBLE 状态中被唤醒的进程 实际上此时调度器已经选定了候选进程，但考虑到这一类型的进程很有可能是交互式进程，因此此时仍然调用 recalc_task_prio() 对该进程的优先级进行修正（详见进程平均等待时间 sleep_avg），修正的结果将在下一次调度时体现。d) 进程因时间片相关的原因被剥夺 cpu 在 schedule_tick() 中（由时钟中断启动），进程可能因两种原因被剥夺 cpu，一是时间片耗尽，一是因时间片过长而分段。这两种情况都会调用effect_prio() 重新计算优先级，重新入队。e) 其它时机 这些其它时机包括 IDLE 进程初始化（init_idle()）、负载平衡（move_task_away()，详见调度器相关的负载平衡）以及修改 nice 值（set_user_nice()）、修改调度策略（setscheduler()）等主动要求改变优先级的情况。由上可见，2.6 中动态优先级的计算过程在各个进程运行过程中进行，避免了类似 2.4 系统中就绪进程很多时计算过程耗时过长，从而无法预计进程的响应时间的问题。同时，影响动态优先级的因素集中反映在 sleep_avg 变量上。回页首6 进程平均等待时间 sleep_avg进程的 sleep_avg 值是决定进程动态优先级的关键，也是进程交互程度评价的关键，它的设计是 2.6 调度系统中最为复杂的一个环节，可以说，2.6 调度系统的性能改进，很大一部分应该归功于 sleep_avg 的设计。这一节，我们将专门针对 sleep_avg 的变化和它对调度的影响进行分析。内核中主要有四个地方会对 sleep_avg 进行修改：休眠进程被唤醒时（activate_task()调用 recalc_task_prio() 函数）、TASK_INTERRUPTIBLE 状态的进程被唤醒后第一次调度到（schedule()中调用 recalc_task_prio()）、进程从 CPU 上被剥夺下来（schedule()函数中）、进程创建和进程退出，其中recalc_task_prio() 是其中复杂度最高的，它通过计算进程的等待时间（或者是在休眠中等待，或者是在就绪队列中等待）对优先级的影响来重置优先级。1) 休眠进程被唤醒时此时 activate_task() 以唤醒的时间作为参数调用 recalc_task_prio()，计算休眠等待的时间对优先级的影响。在 recalc_task_prio() 中，sleep_avg 可能有四种赋值，并最终都限制在 NS_MAX_SLEEP_AVG 以内：a) 不变 从 TASK_UNINTERRUPTIBLE 状态中被唤醒（activated=-1）、交互程度不够高（!HIGH_CREDIT(p)）的用户进程(p-mm!=NULL)），如果它的 sleep_avg 已经不小于 INTERACTIVE_SLEEP(p) 了，则它的 sleep_avg 不会因本次等待而改变。b) INTERACTIVE_SLEEP(p) 从 TASK_UNINTERRUPTIBLE 状态中被唤醒（activated=-1）、交互程度不够高（!HIGH_CREDIT(p)）的用户进程(p-mm!=NULL)），如果它的 sleep_avg 没有达到 INTERACTIVE_SLEEP(p)，但如果加上本次休眠时间 sleep_time 就达到了，则它的 sleep_avg 就等于 INTERACTIVE_SLEEP(p)。c) MAX_SLEEP_AVG-AVG_TIMESLICE 用户进程(p-mm!=NULL)，如果不是从 TASK_UNINTERRUPTIBLE 休眠中被唤醒的（p-activated!=-1），且本次等待的时间（sleep_time）已经超过了 INTERACTIVE_SLEEP(p)，则它的 sleep_avg 置为 JIFFIES_TO_NS(MAX_SLEEP_AVG-AVG_TIMESLICE)。d) sleep_avg+sleep_time 如果不满足上面所有情况，则将 sleep_time 叠加到 sleep_avg 上。此时，sleep_time 要经过两次修正：i. 根据 sleep_avg 的值进行修正，sleep_avg 越大，修正后的 sleep_time 越小：sleep_time = sleep_time * MAX_BONUS * (1-NS_TO_JIFFIES(sleep_avg)/MAX_SLEEP_AVG)ii. 如果进程交互程度很低（LOW_CREDIT()返回真，见更精确的交互式进程优先），则将 sleep_time 限制在进程的基准时间片以内，以此作为对 cpu-bound 的进程的优先级惩罚。总的来说，本次等待时间越长，sleep_avg 就应该更大，但核心排除了两种情况： 从 TASK_UNINTERRUPTIBLE 状态醒来的进程，尤其是那些休眠时间比较长的进程，很有可能是等待某种资源而休眠，它们不应该受到等待时间的优先级奖励，它的 sleep_avg 被限制在 INTERACTIVE_SLEEP(p) 范围内（或不超过太多）（INTERACTIVE_SLEEP(p) 的含义见后），-这一限制对已经认定为是交互式的进程无效。 不是从 TASK_UNITERRUPTIBLE 状态中醒来的进程，如果本次等待时间过长，也不应该受到等待时间的优先级奖励。 INTERACTIVE_SLEEP(p) 与 nice 的关系 NS_TO_JIFFIES(INTERACTIVE_SLEEP(p)=TASK_NICE(p)*MAX_SLEEP_AVG/40+ (INTERACTIVE_DELTA+1+MAX_BONUS/2)*MAX_SLEEP_AVG/MAX_BONUS -1- 这个宏与进程 nice 值成正比，说明优先级越低的进程，允许它在交互式休眠状态下的时间越长。 2) TASK_INTERRUPTIBLE 状态的进程被唤醒后第一次被调度到时调度器挑选出候选进程之后，如果发现它是从 TASK_INTERRUPTIBLE 休眠中醒来后第一次被调度到（activated0），调度器将根据它在就绪队列上等待的时长调用 recalc_task_prio() 重新调整进程的 sleep_avg。recalc_task_prio() 调整的过程与休眠进程被唤醒时的情况是一模一样的，所不同的是，此时作为等待时间 sleep_time 参与计算的不是进程的休眠时间，而是进程在就绪队列上等待调度的时间。并且，如果进程不是被中断唤醒的（activated=1），sleep_time 还将受到约束（delta=delta*ON_RUNQUEUE_WEIGHT/100），因为此时该进程不是交互式进程的可能性很大。从上面对 recalc_task_prio() 的分析可知，sleep_time 减小一般来说就意味着优先级会相应降低，所以，这一奖励说明调度器在进一步减小进程的响应时间，尤其是交互式进程。3) 被切换下来的进程前面说过，sleep_avg 是进程的平均等待时间，recalc_task_prio() 计算了等待时间，在 schedule() 中，被切换下来的进程的 sleep_avg 需要减去进程本次运行的时间 run_time（并保证结果不小于 0），这就是对平均的体现：等待得越久，sleep_avg 越大，进程越容易被调度到；而运行得越久，sleep_avg 越小，进程越不容易调度到。run_time 可以用系统当前时间与进程 timestamp（上一次被调度运行的时间）的差值表示，但不能超过 NS_MAX_SLEEP_AVG。对于交互式进程（HIGHT_CREDIT(p) 为真，见更精确的交互式进程优先），run_time 还要根据 sleep_avg 的值进行调整：run_time = run_time / (sleep_avg*MAX_BONUS/MAX_SLEEP_AVG)这样调整的结果是交互式进程的 run_time 小于实际运行时间，sleep_avg 越大，则 run_time 减小得越多，因此被切换下来的进程最后计算所得的 sleep_avg 也就越大，动态优先级也随之变大。交互式进程可以借此获得更多被执行的机会。4) fork 后在 wake_up_forked_process() 中，父进程的 sleep_avg 要乘以 PARENT_PENALTY/100，而子进程的 sleep_avg 则乘以 CHILD_PENALTY/100。实际上PARENT_PENALTY 为 100，CHILD_PENALTY 等于 95，也就是说父进程的 sleep_avg 不会变，而子进程从父进程处继承过来的 sleep_avg 会减小 5%，因此子进程最后的优先级会比父进程稍低（但子进程仍然会置于与父进程相同的就绪队列上，位置在父进程之前-也就是前言所说子进程先于父进程运行）。5) 进程退出时一个进程结束运行时，如果它的交互程度比父进程低（sleep_avg 较小），那么核心将在 sched_exit() 中对其父进程的 sleep_avg 进行调整，调整公式如下（以 child_sleep_avg 表示子进程的 sleep_avg）：sleep_avg= sleep_avg*EXIT_WEIGHT/(EXIT_WEIGHT+1) + child_sleep_avg/(EXIT_WEIGHT+1)其中 EXIT_WEIGHT 等于 3，所以父进程的 sleep_avg 将减少自身 sleep_avg 的 1/4，再补偿子进程 sleep_avg 的 1/4，优先级也将随之有所下降，子进程的交互程度与父进程相差越大，则优先级的惩罚也越明显。利用进程平均等待时间来衡量进程的优先级，使得宏观上相同静态优先级的所有进程的等待时间和运行时间的比值趋向一致，反映了 Linux 要求各进程分时共享 cpu 的公平性。另一方面，sleep_avg 还是进程交互式程度的衡量标准。回页首7 更精确的交互式进程优先交互式进程优先策略的实际效果在 2.4 内核中受到广泛批评，在 2.6 内核中，这一点得到了很大改进，总体来说，内核有四处对交互式进程的优先考虑：1) sleep_avg上文已经详细分析了 sleep_avg 对进程优先级的影响，从中可以看出，交互式进程因为休眠次数多、时间长，它们的 sleep_avg 也会相应地更大一些，所以计算出来的优先级也会相应高一些。2) interactive_credit系统引入了一个 interactive_credit 的进程属性（见改进后的 task_struct），用来表征该进程是否是交互式进程：只要 interactive_credit 超过了 CREDIT_LIMIT 的阀值（HIGH_CREDIT()返回真），该进程就被认为是交互式进程。interactive_credit 的初始值为 0，在两种情况下它会加 1，这两种场合都在 recalc_task_prio() 函数中： 用户进程(p-mm!=NULL)，如果不是从 TASK_UNINTERRUPTIBLE 休眠中被唤醒的（p-activated!=-1），且等待的时间（包括在休眠中等待和在就绪队列中等待，）超过了一定限度（sleep_timeINTERACTIVE_SLEEP(p)）； 除以上情况外，sleep_avg 经过 sleep_time 调整后，如果大于 NS_MAX_SLEEP_AVG。 无论哪种情况，一旦 interactive_credit 超过（大于）CREDIT_LIMIT 了，它都不再增加，因此 interactive_credit 最大值就是 CREDIT_LIMIT+1。interactive_credit 的递减发生在 schedule() 函数中。当调度器用运行时间修正被切换下来的进程的 sleep_avg 之后，如果 sleep_avg 小于等于 0，且interactive_credit 在 -CREDIT_LIMIT 和 CREDIT_LIMIT 之间（-100=interactive_credit=100），则 interactive_cre