Linux学习总结—Linux调度器分析

四、Linux调度器分析
1．Linux2.6调度器的特性
2.6 调度系统从设计之初就把开发重点放在更好满足实时性和多处理机并行性上，并且基本实现了它的设计目标。新调度系统的特性概括为如下几点：
继承和发扬 2.4 版调度器的特点：
交互式作业优先
轻载条件下调度/唤醒的高性能
公平共享
基于优先级调度
高 CPU 使用率
SMP 高效亲和
实时调度和 cpu 绑定等调度手段
在此基础之上的新特性：
O(1)调度算法，调度器开销恒定（与当前系统负载无关），实时性能更好
高可扩展性，锁粒度大幅度减小
新设计的 SMP 亲和方法
优化计算密集型的批处理作业的调度
重载条件下调度器工作更平滑
子进程先于父进程运行等其他改进
 
2．新的数据结构 runqueue
2.4 的就绪队列是一个简单的以 runqueue_head 为头的双向链表，在 2.6 中，就绪队列定义为一个复杂得多的数据结构 struct runqueue，并且，尤为关键的是，每一个 CPU 都将维护一个自己的就绪队列，--这将大大减小竞争。
1) prio_array_t *active, *expired, arrays[2]
runqueue 中最关键的数据结构。每个 CPU 的就绪队列按时间片是否用完分为两部分，分别通过 active 指针和 expired 指针访问，active 指向时间片没用完、当前可被调度的就绪进程，expired 指向时间片已用完的就绪进程。每一类就绪进程都用一个 struct prio_array 的结构表示：
struct prio_array {
                    int nr_active;                 /* 本进程组中的进程数 */
                    struct list_head queue[MAX_PRIO];    /* 以优先级为索引的 HASH 表，见下 */
                    unsigned long bitmap[BITMAP_SIZE]; /* 加速以上 HASH 表访问的位图，见下 */
};

 
图1：active、expired 数组示例

在新的 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_tasks[this_cpu()] 的作用。
5) int best_expired_prio
记录 expired 就绪进程组中的最高优先级（数值最小）。该变量在进程进入 expired 队列的时候保存（schedule_tick()），用途见 "expired_timestamp"的解释）。
6) unsigned long expired_timestamp
当新一轮的时间片递减开始后，这一变量记录着最早发生的进程耗完时间片事件的时间（jiffies 的绝对值，在 schedule_tick() 中赋），它用来表征 expired 中就绪进程的最长等待时间。它的使用体现在 EXPIRED_STARVING(rq) 宏上。
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_load[NR_CPUS]
记录进行负载平衡时各个 CPU 上的负载状态（此时就绪队列中的 nr_running 值），以便分析负载情况（见"调度器相关的负载平衡"）。
14) atomic_t *node_nr_running; int prev_node_load[MAX_NUMNODES]
这两个属性仅在 NUMA 体系结构下有效，记录各个 NUMA 节点上的就绪进程数和上一次负载平衡操作时的负载情况（见"NUMA 结构下的调度"）。
15) task_t *migration_thread
指向本 CPU 的迁移进程。每个 CPU 都有一个核心线程用于执行进程迁移操作（见"调度器相关的负载平衡"）。
16) struct list_head migration_queue
需要进行迁移的进程列表（见"调度器相关的负载平衡"）。
3．改进后的 task_struct
2.6 版的内核仍然用 task_struct 来表征进程，尽管对线程进行了优化，但线程的内核表示仍然与进程相同。随着调度器的改进，task_struct 的内容也有了改进，交互式进程优先支持、内核抢占支持等新特性，在 task_struct 中都有所体现。在 task_struct 中，有的属性是新增加的，有的属性的值的含义发生了变化，而有的属性仅仅是改了一下名字。
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))
可见，核心将 100~139 的优先级映射到 200ms~10ms 的时间片上去，优先级数值越大，则分配的时间片越小。
和 2.4 中进程的缺省时间片比较，当 nice 为 0 时，2.6 的基准值 100ms 要大于 2.4 的 60ms。
2) time_slice 的变化
进程的 time_slice 值代表进程的运行时间片剩余大小，在进程创建时与父进程平分时间片，在运行过程中递减，一旦归 0，则按 static_prio 值重新赋予上述基准值，并请求调度。时间片的递减和重置在时钟中断中进行（sched_tick()），除此之外，time_slice 值的变化主要在创建进程和进程退出过程中：
a) 进程创建
为了防止进程通过反复 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 时，该宏返回恒假）；
·         该进程已经耗掉的时间片（时间片基准值减去剩余时间片）正好是运行粒度的整数倍；
·         剩余时间片不小于运行粒度
5．优化了的优先级计算方法
在 2.4 内核中，优先级的计算和候选进程的选择集中在调度器中进行，无法保证调度器的执行时间，这一点在前面介绍 runqueue 数据结构的时候已经提及。2.6 内核中候选进程是直接从已按算法排序的优先级队列数组中选取出来的，而优先级的计算则分散到多处进行。这一节分成两个部分对这种新的优先级计算方法进行描述，一部分是优先级计算过程，一部分是优先级计算（以及进程入队）的时机。
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() 是其中复杂度最高的，它通过计算进程的等待时间（或者是在休眠中等待，或者是在就绪队列中等待）对优先级的影响来重置优先级。
7．更精确的交互式进程优先
交互式进程优先策略的实际效果在 2.4 内核中受到广泛批评，在 2.6 内核中，这一点得到了很大改进，总体来说，内核有四处对交互式进程的优先考虑：
1) sleep_avg
2) interactive_credit
3) TASK_INTERACTIVE()
4) 就绪等待时间的奖励
8．调度器
有了以上的准备工作之后，现在我们可以看看调度器的主流程了。
2.6 的 schedule()函数要更加简单一些，减少了锁操作，优先级计算也拿到调度器外进行了。为减少进程在 cpu 间跳跃，2.4 中将被切换下来的进程重新调度到另一个 cpu 上的动作也省略了。调度器的基本流程仍然可以概括为相同的五步：
·         清理当前运行中的进程（prev）
·         选择下一个投入运行的进程（next）
·         设置新进程的运行环境
·         执行进程上下文切换
·         后期整理
2.6 的调度器工作流程保留了很多 2.4 系统中的动作，进程切换的细节也与 2.4 基本相同（由 context_switch() 开始）。按照调度器对各个数据结构的影响来分析调度器的工作流程，同时，2.6 的调度器中还增加了对负载平衡和内核抢占运行的支持。
1) 相关锁
主要是因为就绪队列分布到各个 cpu 上了，2.6 调度器中仅涉及两个锁的操作：就绪队列锁 runqueue::lock，全局核心锁 kernel_flag。对就绪队列锁的操作保证了就绪队列的操作唯一性，核心锁的意义与 2.4 中相同：调度器在执行切换之前应将核心锁解开（release_kernel_lock()），完成调度后恢复锁状态（reacquire_kernel_lock()）。进程的锁状态依然保存在task_struct::lock_depth属性中。
因为调度器中没有任何全局的锁操作，2.6 调度器本身的运行障碍几乎不存在了。
2) prev
调度器主要影响 prev 进程的两个属性：
·         sleep_avg 减去了本进程的运行时间（详见"进程平均等待时间 sleep_avg"的"被切换下来的进程"）；
·         timestamp 更新为当前时间，记录被切换下去的时间，用于计算进程等待时间。
prev被切换下来后，即使修改了 sleep_avg，它在就绪队列中的位置也不会改变，它将一直以此优先级参加调度直至发生状态改变（比如休眠）。
3) next
在前面介绍 runqueue 数据结构的时候，我们已经分析了 active/expired 两个按优先级排序的就绪进程队列的功能，2.6 的调度器对候选进程的定位有三种可能：
·         active 就绪队列中优先级最高且等待时间最久的进程；
·         当前 runqueue 中没有就绪进程了，则启动负载平衡从别的 cpu 上转移进程，再进行挑选（详见"调度器相关的负载平衡"）；
·         如果仍然没有就绪进程，则将本 cpu 的 IDLE 进程设为候选。
在挑选出 next 之后，如果发现 next 是从 TASK_INTERRUPTIBLE 休眠中醒来后第一次被调度到（activated>0），调度器将根据 next 在就绪队列上等待的时长重新调整进程的优先级（并存入就绪队列中新的位置，详见"进程平均等待时间 sleep_avg"）。
除了 sleep_avg 和 prio 的更新外，next 的 timestamp 也更新为当前时间，用于下一次被切换下来时计算运行时长。
4) 外环境
这里说的外环境指的是调度器对除参与调度的进程以及所在就绪队列以外的环境的影响，主要包括切换计数处理和 cpu 状态的更新（qsctr）。
9．调度器对内核抢占运行的支持
在2.4 系统中，在核心态运行的任何进程，只有当它调用 schedule() 主动放弃控制时，调度器才有机会选择其他进程运行，因此我们说 Linux 2.4 的内核是不可抢占运行的。缺乏这一支持，核心就无法保证实时任务的及时响应，因此也就满足不了实时系统（即使是软实时）的要求。
2.6 内核实现了抢占运行，没有锁保护的任何代码段都有可能被中断，它的实现，对于调度技术来说，主要就是增加了调度器运行的时机。我们知道，在 2.4 内核里，调度器有两种启动方式：主动式和被动式，其中被动方式启动调度器只能是在控制从核心态返回用户态的时候，因此才有内核不可抢占的特点。2.6 中，调度器的启动方式仍然可分为主动式和被动式两种，所不同的是被动启动调度器的条件放宽了很多。它的修改主要在 entry.S 中。
现在，无论是返回用户态还是返回核心态，都有可能检查 NEED_RESCHED 的状态；返回核心态时，只要 preempt_count 为 0，即当前进程目前允许抢占，就会根据 NEED_RESCHED 状态选择调用 schedule()。在核心中，因为至少时钟中断是不断发生的，因此，只要有进程设置了当前进程的 NEED_RESCHED 标志，当前进程马上就有可能被抢占，而无论它是否愿意放弃 cpu，即使是核心进程也是如此。
调度器的工作时机
除核心应用主动调用调度器之外，核心还在应用不完全感知的情况下在以下三种时机中启动调度器工作：
从中断或系统调用中返回；
进程重新允许抢占（preempt_enable()调用preempt_schedule()）；
主动进入休眠（例如wait_event_interruptible()接口）
 

10．调度器相关的负载平衡
在 2.4 内核中，进程p被切换下来之后，如果还有 cpu 空闲，或者该 cpu 上运行的进程优先级比自己低，那么 p 就会被调度到那个 cpu 上运行，核心正是用这种办法来实现负载的平衡。
简单是这种负载平衡方式最大的优点，但它的缺点也比较明显：进程迁移比较频繁，交互式进程（或高优先级的进程）可能还会在 cpu 之间不断"跳跃"。即使是在 SMP 的环境中，进程迁移也是有代价的，2.4 系统的使用经验表明，这种负载平衡方式弊大于利，解决这一"SMP亲和"的问题是 2.6 系统设计的目标之一。
2.6 调度系统采用相对集中的负载平衡方案，分为"推"和"拉"两类操作：
1) "拉"
当某个 cpu 负载过轻而另一个 cpu 负载较重时，系统会从重载 cpu 上"拉"进程过来，这个"拉"的负载平衡操作实现在 load_balance() 函数中。
load_balance() 有两种调用方式，分别用于当前 cpu 不空闲和空闲两种状态，我们称之为"忙平衡"和"空闲平衡"：
a) 忙平衡
无论当前 cpu 是否繁忙或空闲，时钟中断（rebalance_tick()函数中）每隔一段时间（BUSY_REBALANCE_TICK）都会启动一次 load_balance() 平衡负载，这种平衡称为"忙平衡"。
Linux 2.6 倾向于尽可能不做负载平衡，因此在判断是否应该"拉"的时候做了很多限制：
·         系统最繁忙的 cpu 的负载超过当前 cpu 负载的 25% 时才进行负载平衡；
·         当前 cpu 的负载取当前真实负载和上一次执行负载平衡时的负载的较大值，平滑负载凹值；
·         各 cpu 的负载情况取当前真实负载和上一次执行负载平衡时的负载的较小值，平滑负载峰值；
·         对源、目的两个就绪队列加锁之后，再确认一次源就绪队列负载没有减小，否则取消负载平衡动作；
·         源就绪队列中以下三类进程参与负载情况计算，但不做实际迁移：
o        正在运行的进程
o        不允许迁移到本 cpu 的进程（根据 cpu_allowed 属性）
o        进程所在 cpu 上一次调度事件发生的时间（runqueue::timestamp_last_tick，在时钟中断中取值）与进程被切换下来的时间（task_struct::timestamp）之差小于某个阀值（cache_decay_ticks的nanosecond值），--该进程还比较活跃，cache 中的信息还不够凉。
负载的历史信息为了避免竞争，调度器将全系统各个 CPU 进行负载平衡时的负载情况（就绪进程个数）保存在本 cpu 就绪队列的 prev_cpu_load 数组的对应元素中，在计算当前负载时会参考这一历史信息。

找到最繁忙的 cpu（源 cpu）之后，确定需要迁移的进程数为源 cpu 负载与本 cpu 负载之差的一半（都经过了上述历史信息平滑），然后按照从 expired 队列到 active 队列、从低优先级进程到高优先级进程的顺序进行迁移。但实际上真正执行迁移的进程往往少于计划迁移的进程，因为上述三类"不做实际迁移"的情况的进程不参与迁移。
b) 空闲平衡
空闲状态下的负载平衡有两个调用时机：
·         在调度器中，本 cpu 的就绪队列为空；
·         在时钟中断中，本 cpu 的就绪队列为空，且当前绝对时间（jiffies 值）是 IDLE_REBALANCE_TICK 的倍数（也就是说每隔 IDLE_REBALANCE_TICK 执行一次）。
此时 load_balance() 的动作比较简单：寻找当前真实负载最大的 cpu（runqueue::nr_running 最大），将其中"最适合"（见下）的一个就绪进程迁移到当前 cpu 上来。
"空闲平衡"的候选进程的标准和"忙平衡"类似，但因为空闲平衡仅"拉"一个进程过来，动作要小得多，且执行频率相对较高（IDLE_REBALANCE_TICK 是BUSY_REBALANCE_TICK 的 200 倍），所以没有考虑负载的历史情况和负载差，候选的迁移进程也没有考虑 Cache 活跃程度。
计算最繁忙 cpu 算法中的问题
实际上有可能成为平衡源的 cpu 的负载至少应该比当前 cpu 的负载要大，因此 find_busiest_queue() 函数中 max_load 的初值如果是 nr_running，且同时保证 load 最少为 1，那么计算会稍少一点。

c) pull_task()
"拉"进程的具体动作在这个函数中实现。进程从源就绪队列迁移到目的就绪队列之后，pull_task() 更新了进程的 timestamp 属性，使其能继续说明进程相对于本 cpu 的被切换下来的时间。如果被拉来的进程的优先级比本 cpu 上正在运行的进程优先级要高，就置当前进程的 NEED_RESCHED 位等待调度。
2) "推"
a) migration_thread()
与"拉"相对应，2.6 的负载平衡系统还有一个"推"的过程，执行"推"的主体是一个名为 migration_thread() 的核心进程。该进程在系统启动时自动加载（每个 cpu 一个），并将自己设为 SCHED_FIFO 的实时进程，然后检查 runqueue::migration_queue 中是否有请求等待处理，如果没有，就在 TASK_INTERRUPTIBLE 中休眠，直至被唤醒后再次检查。
migration_queue 仅在 set_cpu_allowed() 中添加，当进程（比如通过 APM 关闭某 CPU 时）调用 set_cpu_allowed() 改变当前可用 cpu，从而使某进程不适于继续在当前 cpu 上运行时，就会构造一个迁移请求数据结构 migration_req_t，将其植入进程所在 cpu 就绪队列的 migration_queue 中，然后唤醒该就绪队列的迁移 daemon（记录在 runqueue::migration_thread 属性中），将该进程迁移到合适的cpu上去（参见"新的数据结构 runqueue"）。
在目前的实现中，目的 cpu 的选择和负载无关，而是"any_online_cpu(req->task->cpus_allowed)"，也就是按 CPU 编号顺序的第一个 allowed 的CPU。所以，和 load_balance() 与调度器、负载平衡策略密切相关不同，migration_thread() 应该说仅仅是一个 CPU 绑定以及 CPU 电源管理等功能的一个接口。
b) move_task_away()
实际迁移的动作在 move_task_away() 函数中实现，进程进入目的就绪队列之后，它的 timestamp 被更新为目的 cpu 就绪队列的 timestamp_last_tick，说明本进程是刚开始（在目的 cpu 上）等待。因为"推"的操作是在本地读远地写（与 pull_task() 正相反），因此，在启动远地 cpu 的调度时需要与远地的操作同步，还可能要通过 IPI（Inter-Processor Interrupt）通知目的 cpu，所有这些操作实现在 resched_task()函数中。
两个 runqueue 的锁同步
在迁移进程时会牵涉到两个 cpu 上的就绪队列，通常在操作之前需要对两个就绪队列都加锁，为了避免死锁，内核提供了一套保证加锁顺序的double_rq_lock()/double_rq_unlock() 函数。这套函数并没有操作 IRQ，因此开关中断的动作需要用户自己做。
这套函数在 move_task_away() 中采用了，而 pull_task() 中使用的是 double_lock_balance()，但原理与 double_rq_lock()/double_rq_unlock() 相同。

 
11． NUMA结构下的调度
在 Linux 调度器看来，NUMA 与 SMP 之间主要的不同在于 NUMA 下的 cpu 被组织到一个个节点中了。不同的体系结构，每个节点所包含的 cpu 数是不同的，例如 2.6 的 i386 平台下，NUMAQ 结构每个节点上可配置 16 个 cpu，SUMMIT 结构可配置 32 个 cpu。 NUMA 结构正式体现在 Linux 内核中是从 2.6 开始的，在此之前，Linux 利用已有的"不连续内存"（Discontiguous memory，CONFIG_DISCONTIGMEM）体系结构来支持 NUMA。除了内存分配上的特殊处理以外，以往的内核在调度系统中是等同于 SMP 看待的。2.6 的调度器除了单个 cpu 的负载，还考虑了 NUMA 下各个节点的负载情况。
NUMA 结构在新内核中有两处特殊处理，一处是在做负载平衡时对各NUMA节点进行均衡，另一处是在系统执行新程序（do_execve()）时从负载最轻的节点中选择执行cpu：
1) balance_node()
节点间的平衡作为 rebalance_tick() 函数中的一部分在 load_balance() 之前启动（此时的 load_balance() 的工作集是节点内的 cpu，也就是说，NUMA下不是单纯平衡全系统的 cpu 负载，而是先平衡节点间负载，再平衡节点内负载），同样分为"忙平衡"和"空闲平衡"两步，执行间隔分别为IDLE_NODE_REBALANCE_TICK（当前实现中是 IDLE_REBALANCE_TICK 的 5 倍）和 BUSY_NODE_REBALANCE_TICK（实现为 BUSY_NODE_REBALANCE_TICK 的 2 倍）。
balance_node() 先调用 find_busiest_node() 找到系统中最繁忙的节点，然后在该节点和本 cpu 组成的 cpu 集合中进行 load_balance()。寻找最繁忙节点的算法涉及到几个数据结构：
·         node_nr_running[MAX_NUMNODES]，以节点号为索引记录了每个节点上的就绪进程个数，也就是那个节点上的实时负载。这个数组是一个全局数据结构，需要通过 atomic 系列函数访问。
·         runqueue::prev_node_load[MAX_NUMNODES]，就绪队列数据结构中记录的系统各个节点上一次负载平衡操作时的负载情况，它按照以下公式修正：
当前负载=上一次的负载/2 + 10*当前实时负载/节点cpu数
采用这种计算方式可以平滑负载峰值，也可以考虑到节点cpu数不一致的情况。
·         NODE_THRESHOLD，负载的权值，定义为 125，被选中的最繁忙的节点的负载必须超过当前节点负载的 125/100，也就是负载差超过 25%。
2) sched_balance_exec()
当 execve() 系统调用加载另一个程序投入运行时，核心将在全系统中寻找负载最轻的一个节点中负载最轻的一个 cpu（sched_best_cpu()），然后调用sched_migrate_task() 将这个进程迁移到选定的 cpu 上去。这一操作通过 do_execve() 调用 sched_balance_exec() 来实现。
sched_best_cpu() 的选择标准如下：
·         如果当前cpu就绪进程个数不超过2，则不做迁移；
·         计算节点负载时，使用（10*当前实时负载/节点cpu数）的算法，不考虑负载的历史情况；
·         计算节点内cpu的负载时，使用就绪进程的实际个数作为负载指标，不考虑负载的历史情况。
和"忙平衡"与"空闲平衡"采用不同负载评价标准一样，sched_balance_exec() 采用了与 balance_node() 不一样的（更简单的）评价标准。
sched_migrate_task() 借用了 migration_thread 服务进程来完成迁移，实际操作时将进程的 cpu_allowed 暂设为仅能在目的 cpu 上运行，唤醒migration_thread 将进程迁移到目的 cpu 之后再恢复 cpu_allowed 属性。
12．调度器的实时性能
1) 2.6 对于实时应用的加强
2.6 内核调度系统有两点新特性对实时应用至关重要：内核抢占和 O(1) 调度，这两点都保证实时进程能在可预计的时间内得到响应。这种"限时响应"的特点符合软实时（soft realtime）的要求，离"立即响应"的硬实时（hard realtime）还有一定距离。并且，2.6 调度系统仍然没有提供除 cpu 以外的其他资源的剥夺运行，因此，它的实时性并没有得到根本改观。
2) 实时进程的优先级
2.4 系统中，实时进程的优先级通过 rt_priority 属性表示，与非实时进程不同。2.6 在静态优先级之外引入了动态优先级属性，并用它同时表示实时进程和非实时进程的优先级。
从上面的分析我们看到，进程的静态优先级是计算进程初始时间片的基础，动态优先级则决定了进程的实际调度优先顺序。无论是实时进程还是非实时进程，静态优先级都通过 set_user_nice() 来设置和改变，缺省值都是 120（MAX_PRIO-20），也就是说，实时进程的时间片和非实时进程在一个量程内。
可区分实时进程和非实时进程的地方有两处：调度策略 policy（SCHED_RR或SCHED_FIFO）和动态优先级 prio（小于 MAX_USER_RT_PRIO），实际使用上后者作为检验标准。实时进程的动态优先级在 setscheduler() 中设置（相当于 rt_priority），并且不随进程的运行而改变，所以实时进程总是严格按照设置的优先级进行排序，这一点和非实时进程动态优先级含义不同。可以认为，实时进程的静态优先级仅用于计算时间片，而动态优先级则相当于静态优先级。
3) 实时调度
2.4中SCHED_RR和SCHED_FIFO两种实时调度策略在2.6中未作改变，两类实时进程都会保持在active就绪队列中运行，只是因为2.6内核是可抢占的，实时进程（特别是核心级的实时进程）能更迅速地对环境的变化（比如出现更高优先级进程）做出反应。
13．调度器初始化分析sched_init()
sched_init()在CPU初始化、启动内存初始化完成之后，在中断、定时器等初始化之前由启动CPU调用。sched_init()的工作是：
1)        初始化每个CPU的运行队列rq的数据，SMP调度相关的数据；
2)        调用set_load_weight()设置初始Task的负载；
3)        如果配置了CONFIG_SMP，则开始调度均衡的中断SCHED_SOFTIRQ；
4)        增加init_mm的引用计数；
5)        调用enter_lazy_tlb()，对所有CPU，只是简单的将cpu_tlbstate状态设为TLBSTATE_LAZY；
6)        调用init_idle()初始化idle内核线程，idle进程0即使系统所有进程的父进程；
 
对于SMP系统在init()—>smp_init()之后，再调用sched_init_smp()初始化CPU本身相关的调度域
和组等数据。 

、Linux进程切换深入分析
#define CLONE_KERNEL     (CLONE_FS | CLONE_FILES | CLONE_SIGHAND)
创建内核线程时使用的CLONE标志。
1．#define unlikely(x)      __builtin_expect(!!(x), 0)
编译器优化，实际返回值x是整型表达式，0表示并不预期该事件发生，也就是说x为0的可能性很小，这是为了让编译器对下面得语句进行优化。
2．进程内核态堆栈结构：
进程是动态实体，进程描述符是存放在动态内存中的。在一块进程内存区上，Linux存放了两个数据结构：指向task_struct得thread_info和内核态的进程栈。大小一般2页8K，这要求页面帧对齐2的13次幂，在X86上编译时可以配置大小为4K。thread_info在内存区开始处，内核栈从内存尾向下增长。在C语言中可以用union结构表示：
图1. 8K内核栈和进程描述符task_struct及thread_info的相互关系
 
union thread_union {
        struct thread_info thread_info;
        unsigned long stack[2048]; /* 1024 for 4KB stacks */
    };
 
CPU的esp寄存器用于执行堆栈的顶部指针，当从用户态转向内核态时，进程内核栈总是空的，所以esp就会执行堆栈底部。
使用alloc_thread_info 和free_thread_info用于分配和释放一个存放thread_info结构和内核堆栈的内存区。
内核通过当前esp指针可以很方便的得到thread_info结构的地址。current_thread_info(void)的原理即如下：
movl $0xffff2000,%ecx /* or 0xfffff000 for 4KB stacks */
   andl %esp,%ecx
movl %ecx,p
thread_info中task指针是第一个，所以current宏相当于current_thread_info( )->task，从而也就得到task指针。
 
每个进程有自己独立得进程空间，所有进程共享CPU寄存器。进程继续执行时必须装入寄存器恢复得数据集称为硬件上下文环境。在Linux中部分硬件上下文存放在进程描述符中，部分存放到内核态堆栈里。
 
3. 进程切换堆栈原理：
每个进程有自己独立得进程空间，所有进程共享CPU寄存器。进程继续执行时必须装入寄存器恢复得数据集称为硬件上下文环境。在Linux中部分硬件上下文存放在进程描述符中，部分存放到内核态堆栈里。
80x86体系支持在进程TSS段跳转时自动执行进程硬件上下文切换。Linux使用软件方法实现。软件方式效率差不多，当更灵活，可以控制流程，留下优化空间。
80x86用TSS段保存硬件上下文内容，每个CPU有一个TSS段。从用户态到内核态切换时，从TSS中取出内核栈地址。用户态进程访问I/O端口时，TSS中的I/O访问位图可以验证权限。tss_struct描述了TSS格式，init_tss存放初始TSS内容，每次进程切换，内核更新TSS中的某些字段，以反映当前运行进程的权限等级。每个进程有个反映任务CPU状态的thread_struct结构变量thread，除eax、ecx等通用寄存器内容保存在内核态堆栈中，其他大部分寄存器都保存在次结构中。该结构一部分对应于tss_struct中的内容，进程切换时把thread中某些内容更新到tss_struct中就可以反映当前任务的运行CPU环境。
struct tss_struct {
    unsigned short    back_link,__blh;
    unsigned long esp0;
    unsigned short    ss0,__ss0h;
    unsigned long esp1;
    unsigned short    ss1,__ss1h;   /* ss1 is used to cache MSR_IA32_SYSENTER_CS */
    unsigned long esp2;
    unsigned short    ss2,__ss2h;
    unsigned long __cr3;
    unsigned long eip;
    unsigned long eflags;
    unsigned long eax,ecx,edx,ebx;
    unsigned long esp;
    unsigned long ebp;
    unsigned long esi;
    unsigned long edi;
    unsigned short    es, __esh;
    unsigned short    cs, __csh;
    unsigned short    ss, __ssh;
    unsigned short    ds, __dsh;
    unsigned short    fs, __fsh;
    unsigned short    gs, __gsh;
    unsigned short    ldt, __ldth;
    unsigned short    trace, io_bitmap_base;
    /*
     * The extra 1 is there because the CPU will access an
     * additional byte beyond the end of the IO permission
     * bitmap. The extra byte must be all 1 bits, and must
     * be within the limit.
     */
    unsigned long io_bitmap[IO_BITMAP_LONGS + 1];
    /*
     * Cache the current maximum and the last task that used the bitmap:
     */
    unsigned long io_bitmap_max;
    struct thread_struct *io_bitmap_owner;
    /*
     * pads the TSS to be cacheline-aligned (size is 0x100)
     */
    unsigned long __cacheline_filler[35];
    /*
     * .. and then another 0x100 bytes for emergency kernel stack
     */
    unsigned long stack[64];
} __attribute__((packed));
 
struct thread_struct {
/* cached TLS descriptors. */
struct desc_struct tls_array[GDT_ENTRY_TLS_ENTRIES];
unsigned long esp0;
unsigned long sysenter_cs;
unsigned long eip;
unsigned long esp;
unsigned long fs;
unsigned long gs;
/* Hardware debugging registers */
unsigned long debugreg[8]; /* %%db0-7 debug registers */
/* fault info */
unsigned long cr2, trap_no, error_code;
/* floating point info */
union i387_union i387;
/* virtual 86 mode info */
struct vm86_struct __user * vm86_info;
unsigned long     screen_bitmap;
unsigned long     v86flags, v86mask, saved_esp0;
unsigned int      saved_fs, saved_gs;
/* IO permissions */
unsigned long *io_bitmap_ptr;
    unsigned long iopl;
/* max allowed port in the bitmap, in bytes: */
unsigned long io_bitmap_max;
};
 
4．进程切换流程解析switch_to
进程切换本质上两步：
1)      进程页表PGD切换；
2)      内核态堆栈和硬件上下文切换（包括CPU寄存器）；
   上面两步通过context_switch()实现，它通过调用switch_mm()切换进程空间，switch_to切换内核上下文环境。
 
首先看看context_switch()做了些什么：
1)        进程描述符中active_mm执行进程使用的地址空间，mm执行进程拥有的地址空间，对于普通进程它们相同。对于内核线程，它的mm总为NULL。所以context_switch()首先判断if (!next->mm)即next为内核线程，则使用prev的进程地址空间：
if (!next->mm) {    next->active_mm = prev->active_mm;    atomic_inc(&prev->active_mm->mm_count);    enter_lazy_tlb(prev->active_mm, next);}2)        否则，如果next是普通进程，则用next进程空间替换prev的地址空间：
    switch_mm(oldmm, mm, next);
3)        如果prev是内核线程或者正在退出，则设置prev->active_mm 和runqueue的 prev_mm为NULL：
if (!prev->mm) {
      prev->active_mm = NULL;
      WARN_ON(rq->prev_mm);
      rq->prev_mm = oldmm;
 }
 
下面看看switch_mm()如何切换进程空间：
1)        获取cpu逻辑号。
2)        清除cpu_vm_mask位标志。cpu_clear(cpu, prev->cpu_vm_mask)
3)        设置cpu_tlbstate状态。per_cpu(cpu_tlbstate, cpu).state = TLBSTATE_OK
4)        设置cpu_tlbstate的active_mm为next。per_cpu(cpu_tlbstate, cpu).active_mm = next
5)        设置next的cpu_vm_mask标志。cpu_set(cpu, next->cpu_vm_mask)
6)        装载next的pgd页表到cr3寄存器。load_cr3(next->pgd)
7)      如果next的LDT描述符改变，则加载next的LDT描述符。
if (unlikely(prev->context.ldt != next->context.ldt))
           load_LDT_nolock(&next->context);
 
最后，switch_to进行内核堆栈和CPU环境切换操作：
#define switch_to(prev,next,last) do {               \
    unsigned long esi,edi;                    \
    asm volatile("pushfl\n\t"       /* Save flags */ \
            "pushl %%ebp\n\t"                 \
            "movl %%esp,%0\n\t" /* save ESP */       \
            "movl %5,%%esp\n\t" /* restore ESP */ \
            "movl $1f,%1\n\t"      /* save EIP */       \
            "pushl %6\n\t"      /* restore EIP */ \
            "jmp __switch_to\n"           \
            "1:\t"                     \
            "popl %%ebp\n\t"                  \
            "popfl"                    \
            :"=m" (prev->thread.esp),"=m" (prev->thread.eip), \
             "=a" (last),"=S" (esi),"=D" (edi)          \
            :"m" (next->thread.esp),"m" (next->thread.eip), \
             "2" (prev), "d" (next));            \
} while (0)
 
流程描述，prev是进程A的task结构，next是进程B的task结构，last是进程C的结构：
1)      保存prev和next指针的值到eax和edx：
movl prev, %eaxmovl next, %edx
2)      保存eflags 和 ebp 寄存器内容到prev内核态堆栈中：
pushfl
pushl %ebp
 
3)      将esp内容保存到prev->thread.esp中，该字段执行prev内核堆栈的top地址。
movl %esp,484(%eax)
 
4)      将next->thread.esp加载到esp中，现在开始，esp执行next的内核堆栈，进程切换完成。
movl 484(%edx), %esp
 
5)      保存下面Label 1到prev->thread.eip指针中，当prev进程恢复运行时，从该位置开始运行。
movl $1f, 480(%eax)
 
6)      将next->thread.eip的指针内容压到next的内核态堆栈中，通常它的内容也是Label 1。
pushl 480(%edx)
 
7)      跳转到__switch_to（）C函数执行。
jmp __switch_to
 
8)      被替换的进程A继续执行，它在Label 1处，首先是恢复eflags和ebp寄存器内容。注意这里是发生在调度器选择prev在CPU上运行后，次数esp已经执行了prev的内核堆栈。
1:
      popl %ebp
   popfl
 
9)      将eax内容保存到last任务结构中。这里eax是被进程A切换下来的进程C的task结构指针。
movl %eax, last
 
5．__switch_to深入分析
__switch_to参数是存放在eax和edx中的内容，这通过
#define fastcall __attribute__((regparm(3)))告诉gcc编译器。
1)      获取tss_struct tss、prev_p和next_p的thread_struct结构prev和next、当前CPU逻辑ID。
2)      调用__unlazy_fpu(prev_p)根据条件标志选择是否保存prev_p的FPU, MMX, 和XMM寄存器内容。
3)      load_esp0(tss, next)将next的堆栈地址存放到tss中：tss->esp0 = thread->esp0。
4)      savesegment(gs, prev->gs)保存gs寄存器到prev->gs，fs已经在栈入口保存，es和ds在内核态下不需要保存。
5)      load_TLS(next, cpu)从next的tls_array 缓存中加载线程的Thread-Local Storage描述符。TLS在GDT表中位置6、7、8。
cpu_gdt_table[cpu][6] = next_p->thread.tls_array[0];
cpu_gdt_table[cpu][7] = next_p->thread.tls_array[1];
    cpu_gdt_table[cpu][8] = next_p->thread.tls_array[2];
6)      如果当前特权级别是0并且prev->iopl != next->iopl则恢复IOPL设置set_iopl_mask(next->iopl)。
7)      根据thread_info的TIF标志_TIF_WORK_CTXSW和TIF_IO_BITMAP判断是否需要处理debug寄存器和IO位图：__switch_to_xtra(next_p, tss);
l        只有当next_p挂起时即if (test_tsk_thread_flag(next_p, TIF_DEBUG))使用了debug寄存器才需要恢复set_debugreg(next->debugreg[i], i)。只有调试器需要监控prev的状态时，prev_p->thread.debugreg数组的内容才会被修改。Debug寄存器dr0～dr7，dr4和dr5不用。
l         当prev_p或者next_p定义了自己的I/O访问位图时，必须更新TSS的I/O bitmap。
if (prev_p->thread.io_bitmap_ptr || next_p->thread.io_bitmap_ptr)          handle_io_bitmap(&next_p->thread, &init_tss[cpu]);
进程的I/O访问位图存放在io_bitmap_ptr指针里，通常进程很少修改IO位图，只有当前时间片中访问IO端口才会把实际的IO位图加载到TSS中。
ü         当next_p没有自定义位图时：
tss->io_bitmap_base = INVALID_IO_BITMAP_OFFSET; 返回
ü         如果next == tss->io_bitmap_owner则设置有效的偏移量：tss->io_bitmap_base = IO_BITMAP_OFFSET; 返回
ü         否则tss->io_bitmap_base = INVALID_IO_BITMAP_OFFSET_LAZY;
  只有第二种情况tss->io_bitmap_base设置的是有效的io_bitmap偏移量，对于其他两种情况，当用户进程访问I/O端口时将会触发"General protection "的异常，do_general_protection( )异常处理函数根据io_bitmap的值处理异常：如果是0x8000(INVALID_IO_BITMAP_OFFSET)则发送SIGSEGV信号给用户进程；如果是0x9000(INVALID_IO_BITMAP_OFFSET_LAZY)则拷贝进程的thread中的io_bitmap_ptr内容到io_bitmap中，并设置io_bitmap_base为正确的偏移量(104)。
 
8)      disable_tsc(prev_p, next_p)设置cr4中的TSC Disable位。
9)      arch_leave_lazy_cpu_mode()设置CPU的lazy模式。
10) 如果next_p->fpu_counter > 5则恢复next_p的FPU寄存器内容：
math_state_restore()。FPU寄存器存放在next_p->thread->i387中，i387是i387_union的union结构：
union i387_union {
struct i387_fsave_struct fsave;
struct i387_fxsave_struct   fxsave;
struct i387_soft_struct soft;
};
struct i387_fxsave_struct {
unsigned short    cwd;
unsigned short    swd;
unsigned short    twd;
unsigned short    fop;
long   fip;
long   fcs;
long   foo;
long   fos;
long   mxcsr;
long   mxcsr_mask;
long   st_space[32]; /* 8*16 bytes for each FP-reg = 128 bytes */
long   xmm_space[32];    /* 8*16 bytes for each XMM-reg = 128 bytes */
long   padding[56];
} __attribute__ ((aligned (16)));
 
11) 如果需要，则从next->gs中恢复gs寄存器内容。
if (prev->gs | next->gs)
         loadsegment(gs, next->gs);
二、Linux实时调度schedule
1．概述
三种调度策略：SCHED_FIFO，SCHED_RR和SCHED_NORMAL。
FIFO实时调度算法当调度器将CPU指定给某个进程时，它把该进程放到运行队列首；除非有更高优先级的进程，否则该进程将一直占用CPU。
Round Robin实时进程调度把CPU指定给某进程，把它放到运行队列尾。时间片运行完再选择其他进程调度。这样保证了同优先级的公平竞争CPU。
SCHED_NORMAL是普通的基于运行时间和等待时间等，动态调整进程优先级的一种调度策略。
实时进程优先级1～100，普通101～139。
2．实时进程调度的时机
1)      该进程被更高优先级的进程抢占；
2)      进程执行一个阻塞操作，被放到睡眠队列，状态为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE；
3)      进程被终止(状态为TASK_STOPPED 或TASK_TRACED)，或者进程被杀死(状态为EXIT_ZOMBIE 或 EXIT_DEAD)
4)      进程调用sched_yield()主动放弃CPU；
5)      RR实时进程用完了CPU分配的时间片；
 
3．调度器相关函数
1)      scheduler_tick( )
更新当前进程的运行时间片tick值，在update_process_times( )中调用，判断进程的时间片是否用完。
 
2)      try_to_wake_up( )
唤醒一个睡眠的进程并把它的状态设为TASK_RUNNING，插入到运行队列中。
 
3)      recalc_task_prio( )
更新进程的睡眠时间和动态优先级，SCHED_NORMAL调度。
 
4)      schedule( )
进程调度
 
5)      load_balance()
SMP系统的负载均衡。
 
4．schedule( )函数
进程调度有两种方式：直接调用和延迟调用。
直接调用schedule，当前进程资源不可用时会直接调用调度器，这种情况下，内核线程进行如下处理：
1)      将current插入到合适的等待队列中；
2)      将current状态变为TASK_INTERRUPTIBLE 或TASK_UNINTERRUPTIBLE
3)      调用schedule();
4)      检查资源是否可用，如果不可用，转到第2）步；
5)      一旦资源可用，从等待队列中移除current进程；
 
在设备驱动程序中也经常会检查TIF_NEED_RESCHED并调用schedule()。
 
延迟调用方式是通过设置current进程的TIF_NEED_RESCHED标志为1。当恢复用户态进程的执行前，会检查该标志并决定是否调用schedule()。延迟调度的情形有：
1)      在scheduler_tick()中如果current用完了时间片则设置该标志；
2)      在try_to_wake_up( )中唤醒一个进程并且该进程比当前运行进程优先级高。
3)      调用sched_setscheduler()时。
 
schedule()函数工作流程：
进程切换前的工作：
1)      禁止内核抢占，初始化局部变量prev，释放prev占有的大内核锁；
need_resched:
    preempt_disable();
    prev = current;
    release_kernel_lock(prev);
2)      读取调度TSC时间，计算调整run_time时间， 更新调度状态rq->sched_cnt参数，获取rq的spin锁：spin_lock_irq(&rq->lock)。
3)      检查prev状态：如果状态不是TASK_RUNNING且没有在内核态被抢占，则从运行队列中移除；但是如果prev状态是TASK_INTERRUPTIBLE并且拥有非阻塞挂起的信号，则把进程状态设为TASK_RUNNING不移出运行队列。
     if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
       switch_count = &prev->nvcsw;
       if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
              unlikely(signal_pending(prev))))
           prev->state = TASK_RUNNING;
       else {
           if (prev->state == TASK_UNINTERRUPTIBLE)
              rq->nr_uninterruptible++;
           deactivate_task(prev, rq);
       }
    }
4)      获取当前CPU逻辑号，如果当前运行队列为空，则调用idle_balance(cpu, rq)从其他CPU运行队列上拉进程到本地CPU的运行队列上。如果调整后，当前运行队列仍为空则next赋为idle进程，跳转到任务切换代码行去。
    if (unlikely(!rq->nr_running)) {
       idle_balance(cpu, rq);
       if (!rq->nr_running) {
           next = rq->idle;
           rq->expired_timestamp = 0;
           goto switch_tasks;
       }
    }
5)      如果runqueue中有进程，并且当前活得进程数为0，则交换active 和 expired队列指针。
    array = rq->active;
    if (unlikely(!array->nr_active)) {
       schedstat_inc(rq, sched_switch);
       rq->active = rq->expired;
       rq->expired = array;
       array = rq->active;
       rq->expired_timestamp = 0;
       rq->best_expired_prio = MAX_PRIO;
    }
 
6)      从运行队列的活动prio_array数据的位图中查找第一个位设置为1的索引，根据索引找到该优先级队列的第一个task。
idx = sched_find_first_bit(array->bitmap);
    queue = array->queue + idx;
    next = list_entry(queue->next, struct task_struct, run_list);
 
7)      如果next是普通进程，并且next->sleep_type是SLEEP_INTERACTIVE 或SLEEP_INTERRUPTED，则重新计算进程睡眠时间和进程优先级。
 
进程切换工作：
8)      更新sched_goidle，预期next结构数据，清除TIF_NEED_RESCHED标志，设置quiescent状态计数为1：rcu_data ->passed_quiesc = 1;
switch_tasks:
if (next == rq->idle)
    schedstat_inc(rq, sched_goidle);
prefetch(next);
prefetch_stack(next);
clear_tsk_need_resched(prev);
rcu_qsctr_inc(task_cpu(prev));
 
9)      更新prev进程运行时间戳prev->sleep_avg，prev->timestamp;
10) 调度信息切换到next，更新next;时间戳和运行队列信息：
sched_info_switch(prev, next);
if (likely(prev != next)) {
    next->timestamp = next->last_ran = now;
    rq->nr_switches++;
    rq->curr = next;
    ++*switch_count;
     ……
}
11) 进行进程切换，context_switch参见前面的分析，它进行进程空间和内核堆栈切换。prepare_lock_switch 功能是在定义了__ARCH_WANT_INTERRUPTS_ON_CTXSW情况下，在切换前开中断spin_unlock_irq(&rq->lock); barrier()是保证代码执行顺序不变。
     prepare_task_switch(rq, next);
    prev = context_switch(rq, prev, next);
    barrier();   
    finish_task_switch(this_rq(), prev);
 
 
进程切换后的工作：
进程切换context_switch语句之后的代码并不是由next进程立即执行的，而是由调度器选择prev进程继续执行的。次时prev变量指向的已经是被prev进程替换的其他进程的指针。
 
12) finish_task_switch()必须与prepare_task_switch配对使用，并主要锁的顺序。它所做的工作，finish_lock_switch调用local_irq_enable(),获取prev的状态和rq->prev_mm，如果mm非空，则调用mmdrop(mm)减少mm的引用计数，如果为0则释放进程页表和虚拟空间。如果prev_state为TASK_DEAD则释放进程的task结构。
 
struct mm_struct *mm = rq->prev_mm;
long prev_state;
 
rq->prev_mm = NULL;
prev_state = prev->state;
finish_arch_switch(prev);
finish_lock_switch(rq, prev);
if (mm)
    mmdrop(mm);
if (unlikely(prev_state == TASK_DEAD)) {
    kprobe_flush_task(prev);
    put_task_struct(prev);
}
 
13) 最后，if (unlikely(task->lock_depth >= 0))则重新获取大内核锁__reacquire_kernel_lock，否则goto need_resched_nonpreemptible; 允许抢占，如果TIF_NEED_RESCHED被设置，则跳转到need_resched重新进行调度。
prev = current;
if (unlikely(reacquire_kernel_lock(prev) < 0))
    goto need_resched_nonpreemptible;
preempt_enable_no_resched();
if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
    goto need_resched;

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/cxylaf/archive/2007/05/26/1626529.aspx