linux调度器之主调度器框架

winzenghua

进程是操作系统提供的最古老，最重要的抽象之一，它对开发人员和操作人员隐藏了两个基本的硬件资源：处理器和存储器。进程的重要性在于它营造出个数不受物理处理器限制的虚拟处理器并为每个虚拟处理器配备了独立的，容量不受物理内存大小限制的内存空间。这些虚拟处理器为应用程序模拟出一个和物理处理器几乎相同的环境：每个虚拟处理器都拥有独立的，与物理处理器一样的寄存器集合；每个虚拟处理器可以使用同样的地址访问到的却是各自的存储单元；更重要的是，这么多虚拟处理器可以同时并发运行各自的程序，哪怕实际上只存在一个物理处理器。这就是本章讨论的重点：进程调度。
1.1 进程状态

虽然在很多操作系统里进程的状态多达五六，甚至八九种，但是从调度器的角度，进程的状态只有三种：阻塞态，就绪态和运行态。
处于阻塞态的进程不参与进程调度，事实上调度器在分配处理器时间时根本不知道阻塞态进程的存在。阻塞态进程要想参与调度，必须有一个‘第三方’将其提交给调度器，不然这个进程就是一个虽然存在但再也无法运行的‘植物人’。比如一个进程调用sleep()函数休眠一段时间，该进程就从当前运行进入阻塞态，从此不再受调度器的调遣，不再有机会占据处理器。等到指定的休眠时间到达，操作系统的定时器模块作为‘第三方’，将该进程提交给调度器，使其再度参与调度，又有机会成为当前运行进程。
与阻塞态不受调度器控制不同，就绪态和运行态进程都处于调度器的管辖之下。处于就绪态的进程本该运行于处理器上，可是调度器为了平衡众多进程对处理器时间的需求，让该进程暂时停下来听候调遣而安排其它进程在处理器上运行。就绪进程和阻塞进程共同点是都没有占用处理器，区别是阻塞态进程即使在处理器空闲时也不能运行，而就绪进程处于‘预备役’状态，只要处理器空闲或‘时机成熟’马上能运行于处理器上。就绪进程在调度器的队列里排队等候调遣，不同调度算法有各自的排队方式，如linux的完全公平(CFS)算法使用基于虚拟运行时间的红黑树，实时(RT)算法为每个调度优先级设置一条先入先出的队列。
运行态进程又叫当前进程，就是当前正在处理器上运行的进程。由于它占用了宝贵的处理器时间，在很多调度算法里当前进程都是重点监控对象，它的运行时间受到严密监视。一旦发现运行时间超标就会将其从‘现役’转为‘预备役’，进入就绪态，把处理器让给其它就绪进程（当然必须有其它就绪进程存在）。linux对当前进程运行时间的监控是在操作系统的tick中断里完成的，间隔从10毫秒到1毫秒不等。即使是这样的周期CFS算法的设计者还觉得不够精确，又设置了精度为纳秒级的高精度定时器(hrtimer)来监控当前进程，保证其占用的处理器时间严格符合预先给予的配额。
进程的三种基本状态在linux里并不直观。阻塞态有很多表达方式用以表示更精细的状态，比如常用的TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。当前进程的状态表示为TASK_RUNNING，可是就绪进程的状态也是用TASK_RUNNING表示。这不会造成混淆，因为当前运行进程是有专门变量记录的，而就绪进程则统一排列在运行队列中。在linux里TASK_RUNNING的值是0，其它状态值都非0。为运行态和就绪态设置相同值的一个好处是调度器可以很简单地判断一个进程是否能还能继续参与调度：只要状态非0的进程就是应该进入阻塞态的进程，调度器发现这样的进程就将其从调度器脱离开，不再竞争处理器。
1.2 Linux调度器相关文件

调度器是Linux内核中变化较多的模块，功能和性能随着应用的拓展不断增强，代码结构也随着需求的变化持续重构和优化。下表列出了本章将要涉及的，与调度器相关的源代码所在的文件。由于变化较大，可能随着内核版本的持续升级很快表中内容就与最新版本不符合了。

文件名	作用
linux_2.6.34-rc6/kernel/sched.c	该文件是调度器主体，包含调度器初始化，主调度器框架，调度器相关的API，各个具体调度算法也就是调度类的公共函数，用以支持分组调度的处理器子系统。
linux_2.6.34-rc6/kernel/sched_fair.c	该文件实现完全公平调度(CFS)算法和多处理器的负载平衡，与CFS调度类对应
linux_2.6.34-rc6/kernel/sched_rt.c	该文件实现实时调度(RT)算法，与RT调度类对应
linux_2.6.34-rc6/kernel/sched_idletask.c	该文件实现空闲(idle)任务调度，与idle调度类对应
linux_2.6.34-rc6/kernel/sched_cpupri.c	该文件跟踪系统中所有处理器上当前运行进程的优先级，用于实时调度算法的处理器选择
linux_2.6.34-rc6/kernel/sched.h	该文件是调度器最主要的头文件，比较重要的数据结构包括进程控制块(PCB)task_struct，调度项sched_entity的定义
linux_2.6.34-rc6/kernel/sched_feature.h	该文件包含存放调度器性能的参数和默认值

1.3 Linux主调度器

尽管代码已经‘几易其稿’，调度器几个主要API依旧保持着‘原生态’的形式在内核各处广泛调用，其中就包括主调度器schedule()。这个函数既没有参数也没有返回值，简单到了极致，却是整个调度器的奠基石，最基本的进程上下文切换就发生在这个函数中。该函数主要用在三个地方：
自主调度
这是内核进程主动发起的调度，表明当前进程由于种种原因需要撤离调度器，不再参与处理器的竞争而转入阻塞态。一个直观的例子就是调用sleep(timeout)函数使当前进程休眠指定时间后再次唤醒，类似于以下程序：
set_current_state(TASK_UNINTERRUPTIBLE);
设置唤醒定时器;
schedule();
第一行将当前进程设置为不响应信号的阻塞态，前面说过，在linux里只要状态不为TASK_RUNNING的进程都是阻塞态进程。第二行设置睡眠多长时间后将本进程唤醒。接下来调用schedule()函数发现当前进程状态已经设置为阻塞态就将当前进程切换出处理器并脱离调度器，然后从运行队列中取出下一个适合运行的进程继续运行。处于阻塞态的进程不会‘自然醒’，要想再次运行起来必须由‘第三方’将其唤醒，这个‘第三方’包括中断处理程序或其‘下半部’处理或其它进程。
用户态抢占
这是运行于用户态的进程被动剥夺处理器的一种方式。当前运行于用户态的进程P由于系统调用或中断发生进入了内核态。待到从内核态返回用户态时，如果它设置了标志TIF_NEED_RESCHED，说明在运行队列里有更适合运行的进程在排队等待，需要重新评估并切换当前进程，可是由于条件限制这个评估和切换没有立刻执行，只好推迟到从内核态返回到用户态时再执行，这时需要调用一次schedule()函数挑选一个合适的进程来替换当前进程P。与自主调度不同，通常在调用schedule()时候P的状态依旧为TASK_RUNNING，所以P让出处理器后不会进入阻塞态，而是在运行队列中等待下一次被调度。经过一番任务切换，P总是有机会占据处理器，回到用户态继续运行。这个过程从宏观上看就是运行于用户态的进程被另外一个进程剥夺了处理器。
为什么不在需要的时候直接调用schedule()切换进程，而要先设这么个标志等到以后再做进程切换？原因有二：一是在有些情况下不允许进程调度，比如在中断上下文中。在linux里中断象寄生虫一样附着于被它打断的进程（宿主进程）之上：它没有自己独立的类似于进程控制块的实体，直接使用宿主进程的栈和内存空间，所以中断是不可调度的，即使要强行调度也是宿主进程的调度，而不是中断本身的调度。换一个角度说，在中断里无论怎样做进程切换也无法切换到宿主进程上，因为中断本质上就是宿主进程的延伸，只不过是运行于内核态罢了。而假如中断是个和宿主进程一样可调度的实体，那么只要宿主进程处于就绪状态，从中断里总是有机会切换到宿主进程上。总而言之，在中断里调用schedule()，不但中断处理程序被阻塞了，还造成了一个副作用就是同时也阻塞了宿主进程，这样对宿主进程来说是不公平的。另一个不能调用schedule()的地方是与中断紧密联系的中断‘下半部’处理，原因和中断处理程序是一样的。可是中断处理程序或‘下半部’往往又是整个系统特别是事件驱动系统的‘动力源’，需要唤醒休眠等待的进程对中断事件做进一步处理。所以中断处理程序中只好将需要唤醒的进程添加到运行队列里，然后设置当前进程的TIF_NEED_RESCHED标志好在中断推出时执行调度。这样既防止了在中断中切换进程上下文，又实现了进程抢占式调度。二是在多处理器时，如果唤醒的进程在另一个处理器上，那在本处理器上调用schedule()是没有用的，因为它不能操作其它处理器上的运行队列。通常采用迂回的做法：先设置被唤醒进程的TIF_NEED_RESCHED标志，然后向该进程所在的处理器发送中断。处理器在中断返回处就会调用schedule()（或preempt_schedule_irq()如果中断发生在内核态）运行被唤醒的进程。
内核态抢占
这是运行于内核态的进程被动剥夺处理器的方式。早期的linux版本不支持内核态下的抢占式调度，进程在内核态下的切换完全依赖于上面提到的进程自主调度完成。这样可以简化内核设计，不需要保护许多全局变量和资源，但缺点是调度延时大，无法做到实时调度。经过一番‘实时化’改造，目前的内核已经是真正的抢占式内核，进程在内核态下运行时随时会被其它进程打断。实现抢占式内核最根本的修改是中断结束时，如果返回的是内核空间也执行一次schedule()（同样也要检查TIF_NEED_RESCHED标志）。而以前的非抢占式内核只有在用户态发生的中断在返回用户空间时才执行一次schedule()函数。中断随时可能发生，所以运行在内核态下的进程也随时会在中断返回时切换到其它进程，从而实现真正的内核抢占。
与用户态抢占不同，内核态抢占并非直接调用schedule()函数，而是对它的包装- preempt_schedule_irq()。在介绍schedule()之前， ‘抢鲜’介绍一下这个函数：
1 asmlinkage void __sched preempt_schedule_irq(void)
2 {
3 struct thread_info *ti = current_thread_info();
4
5 /* Catch callers which need to be fixed */
6 BUG_ON(ti->preempt_count || !irqs_disabled());
7
8 do {
9 add_preempt_count(PREEMPT_ACTIVE);
10 local_irq_enable();
11 schedule();
12 local_irq_disable();
13 sub_preempt_count(PREEMPT_ACTIVE);
14
15 /*
16 * Check again in case we missed a preemption opportunity
17 * between schedule and now.
18 */
19 barrier();
20 } while (need_resched());
21 }
代码片段 1.3‑1 preempt_schedule_irq()
这个函数里最值得注意的地方是在调用schedule()执行进程切换之前调用了add_preempt_count(PREEMPT_ACTIVE)。这个函数随后调用的schedule()上发生作用，通知它在执行进程上下文切换时，即使当前进程器将要进入阻塞态，即当前进程已经将运行状态设置为TASK_RUNNING以外的值也不要将当前进程从调度器上撤下来，这样做是为了防止在内核抢占时错误地将当前进程切入阻塞态。以前面sleep()函数为例，假如在执行完第一句set_current_state(TASK_INTERRUPTIBLE)之后被中断打断。执行完中断处理程序返回时发现TIF_NEED_RESCHED标志置上了就要执行内核抢占调度preempt_schedule_irq()。如果不运行add_preempt_count(PREEMPT_ACTIVE)就调用schedule()，由于当前进程状态已经是阻塞态TASK_INTERRUPTIBLE了，所以会把当前进程从调度器上撤下，不再运行，转而执行另一个进程。可糟糕的是该进程还没有来得及调用执行第2行设置唤醒定时器就被‘拉下马’了，从此就成为了‘植物人’，一直休眠下去了。而调用了add_preempt_count(PREEMPT_ACTIVE)后，当前进程不会从调度器上撤下来，最多交出处理器让别的进程运行，但自己依然位于运行队列中，总有一天会被调度上处理器继续执行设置唤醒定时器已经以后的操作。
介绍完前没的基础知识就言归正传，看看schedule()是怎样实现的。经过反复实践和千锤百炼，schedule()已经从调度的执行实体演化为抽象的调度框架。下面逐段分析这个重要函数。
1 /*
2 * schedule() is the main scheduler function.
3 */
4 asmlinkage void __sched schedule(void)
5 {
6 struct task_struct *prev, *next;
7 unsigned long *switch_count;
8 struct rq *rq;
9 int cpu;
10
11 need_resched:
12 preempt_disable();
13 cpu = smp_processor_id();
14 rq = cpu_rq(cpu);
15 rcu_sched_qs(cpu);
16 prev = rq->curr;
17 switch_count = &prev->nivcsw;
18
19 release_kernel_lock(prev);
20 need_resched_nonpreemptible:
21
22 schedule_debug(prev);
23
24 if (sched_feat(HRTICK))
25 hrtick_clear(rq);
26
27 raw_spin_lock_irq(&rq->lock);
28 update_rq_clock(rq);
29 clear_tsk_need_resched(prev);
30
31 if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
32 if (unlikely(signal_pending_state(prev->state, prev)))
33 prev->state = TASK_RUNNING;
34 else
35 deactivate_task(rq, prev, 1);
36 switch_count = &prev->nvcsw;
37 }
代码片段 1.3‑2 schedule()
第4行asmlinkage利用了gcc对C语言的扩展，告诉编译器从栈里而不是从寄存器中取整型参数，通常用来修饰系统调用，因为在执行具体的系统调用函数体以前，参数都保存在栈里。不过schedule()本身没有参数，这一修饰也就不起作用。__sched也是一种修饰，可以不关心。第12行禁止执行在schedule()的处理器上发生内核抢占，从此以后该处理器就归执行schedule()函数的进程独占，在这过程中不会切换到别的进程，直到该函数完成最终的进程切换。如果不做这一操作，导致执行schedule()的过程由于内核抢占式调度又会执行schedule()，使得函数中对全局数据如运行队列(rq)的操作发生错乱。第13行取出当前的处理器号，schedule()虽然不带参数，不代表它没有输入，当前的处理器号便是它的输入。第14行根据处理器号取出本处理器的运行队列。在多处理器环境下，每个处理器都有自己的运行队列来存放即将在该处理器上运行的所有就绪进程以及与调度有关的其它数据。第15行告知RCU模块处理器产生了一次进程切换。RCU是内核为多处理器无锁编程提供的机制，与进程调度无关。第16行得到当前进程的进程控制块(PCB)地址。从schedule()的角度，当前进程就是切换前的进程，所以用prev表示。第19行确保假如大内核锁被当前进程锁住的话就将其释放掉，这是大内核锁与自旋锁不一样的地方之一。通常情况下内核中当一个进程锁住了自旋锁后，就必须以最快的速度解锁，期间既不允许被其它进程抢占，更不允许调用schedule()函数切换到其它进程，否则不但会延长其它进程等待解锁的时间，还容易造成死锁。但大内核锁是个例外，尽管它的实现也是基于自旋锁，但正是由于有了第19行的自动解锁以及在后面对应的自动加锁，使得大内核锁的使用要比普通自旋锁灵活的多，锁定期间可以随意调用schedule()函数。第24-25行是对实时时钟计时特性的处理。假如没有开启该特性，调度器最小计时间隔就是操作系统‘滴答’时钟(tick)的周期，从10毫秒到1毫秒不等。但是Linux调度普通进程使用的完全公平调度(CFS)算法时间的计算单位是纳秒，tick时钟毫秒级的精度显得比较粗糙，会影响运行时隙分配。开启该特性允许调度算法使用处理器硬件提供的高精度(high-resolution)时钟来计时，使得调度算法分配的时间准确地得到体现。既然当前进程即将被切走，就不必再为当前进程计算运行时间了，所以在25行将这个时钟清除掉。然后就开始处理运行队列rq了，调度算法主要就是围绕运行队列rq展开的。第28行为当前时间拍个‘快照’记录在rq里，留待以后使用。第29行清除当前进程的TIF_NEED_RESCHED标志。该标志用来通知内核在从中断处理程序退出或从内核态返回用户态时产生一次进程调度。如今既然已经调用schedule()发起了调度，就可以将它清除了。
再接着往下看。第31行if判断条件：当前进程状态prev->state不为0说明当前进程将要进入某个阻塞态。对于schedule()而言，进程状态prev->state不是用来反映进程实际运行状态，而是表明一种意愿，即当前进程希望通过schedule()函数调用进入哪种状态。现在既然要进入阻塞态就必须从运行队列里‘踢’出去。可如前所述，仅仅想进入阻塞状态还不能将当前队列‘踢’出运行队列，还要看当前执行schedule()是不是因为内核抢占。如果当前进程抢占计数器preempt_count()的标志位PREEMPT_ACTIVE置1说明是在执行内核抢占式调度（见上节），不能将当前进程从运行队列里移除。否则就进入if下的语句块，可以考虑退出运行队列了。这时候还有很重要的事要考虑：需要行检查当前进程是否有待处理的信号没有处理。因为对于状态为TASK_INTERRUPTIBLE的进程，一收到信号就必须进入就绪态去抢占处理器执行信号处理程序(signal handle)。即使是处于TASK_INTERRUPTIBLE状态下，对于象SIGKILL这样‘致命’的信号量也是需要响应的。如果在32行不检查信号就进入阻塞态，该进程会因进入阻塞态而无法立刻运行信号处理程序，这样是绝对不允许的。细心的程序员会问，如果在32行执行完毕发现没有收到信号，于是就开始执行第35行：将进程从运行队列里‘踢’出去。就在这时候另一个处理器上的进程向当前进程发送了信号。可当前进程在32行以后不再检查信号状态，而是义无反顾地退出调度，进入了阻塞态。这样一来信号不是照样没法及时处理吗？事实上这种情况不会发生，这归功于自旋锁rq->lock。早在第27行该锁就锁住了，这以后如果其它进程向本进程发送信号，必然会唤醒本进程，将本进程加入其所在处理器的运行队列rq中，所以也要锁住自旋锁rq->lock。可该锁已经在27行被锁住，发信号的进程只好自旋等待解锁。所以上述场景并不存在，当前进程将要执行第35行时如果其它进程向本它发送信号，该信号是发不出来的，它阻塞在等待rq->lock。schedule()在切换当前进程上下文时会将rq->lock解锁，这时尽管当前进程已经离开运行队列进入阻塞态，但发信号的进程在获得rq->lock后随刻将已经休眠的进程其唤醒重新进入就绪态准备运行，所以还是能够及时处理信号。
<未完待续>