时间记账

所有的调度器都必须对进程运行时间做记账。多数Unix系统，正如我们前面所说，分配一个时间片给每一个进程。那么当每次系统时钟节拍发生时，时间片都会被减少一个节拍周期。当一个进程的时间片被减少到0时，它就会被另一个尚未减到0的时间片可运行进程抢占。

vruntime变量存放进程的虚拟运行时间，该运行时间（花在运行上的时间和）的计算是经过了所有可运行进程总数的标准化（或者说是被加权的)。虚拟时间是以ns为单位的，所以vruntime和定时器节拍不再相关。虚拟运行时间可以帮助我们逼近CFS模型所追求的“理想多任务处理器”。如果我们真有这样一个理想的处理器，那么我们就不再需要 vruntime了。因为优先级相同的所有进程的虚拟运行时都是相同的——所有任务都将接收到相等的处理器份额。但是因为处理器无法实现完美的多任务，它必须依次运行每个任务。因此CFS使用vruntime变量来P录一个程序到底运行了多长时间以及它还应该再运行多久（关于CFS请参考这一篇文章）

进程选择（rbt）专门会讲 后面发

调度器入口

进程调度的主要入口点是函数schedule()，它定义在文件 kernel/sched.c中。它正是内核其他部分用于调用进程调度器的入口﹔选择哪个进程可以运行，何时将其投入运行。Schedule()通常都需要和一个具体的调度类相关联，也就是说，它会找到一个最高优先级的调度类–─后者需要有自己的可运行队列，然后问后者谁才是下一个该运行的进程。知道了这个背景，就不会吃惊schedule()函数为何实现得如此简单。该函数中唯一重要的事情是（要连这个都没有，那这个函数真是乏味得不用介绍啦)，它会调用pick_next_task()(也定义在文件kernelsched.c中)。pick_next_task()会以优先级为序，从高到低，依次检查每一个调度类，并且从最高优先级的调度类中，选择最高优先级的进程

注意该函数开始部分的优化。因为CFS是普通进程的调度类，而系统运行的绝大多数进程都是普通进程，因此这里有一个小技巧用来加速选择下一个CFS提供的进程，前提是所有可运行进程数量等于CFS类对应的可运行进程数（这样就说明所有的可运行进程都是CFS类的)。
该函数的核心是for()循环，它以优先级为序，从最高的优先级类开始，遍历了每一个调度类。每-一-个调度类都实现了pick_next_task()函数，它会返回指向下一个可运行进程的指针，或.者没有时返回NULL。我们会从第一个返回非NULL值的类中选择下一个可运行进程。CFS中pick_next_task()实现会调用pick_next_entity()，而该函数会再来调用我们前面内容中讨论过的pick_next entity)函数。

睡眠和唤醒

休眠（被阻塞）的进程处于一个特殊的不可执行状态。这点非常重要，如果没有这种特殊状态的话，调度程序就可能选出一个本不愿意被执行的进程，更糟糕的是，休眠就必须以轮询的方式实现了。进程休眠有多种原因，但肯定都是为了等待一些事件。事件可能是一段时间从文件IO读更多数据，或者是某个硬件事件。一个进程还有可能在尝试获取一个已被占用的内核信号量时被迫进入休眠（这部分在第9章中加以讨论)。休眠的一个常见原因就是文件UO——如进程对一个文件执行了read()操作，而这需要从磁盘里读取。还有，进程在获取键盘输入的时候也需要等待。无论哪种情况，内核的操作都相同:进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule()选择和执行一个其他进程。唤醒的过程刚好相反﹔进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中。

1.等待队列

休眠通过等待队列进行处理。等待队列是由等待某些事件发生的进程组成的简单链表。内核用wake_queue_head_t来代表等待队列。等待队列可以通过DECLARE_WAITQUEUE(O)静态创建，也可以由init_waitqueue_head()动态创建。进程把自己放入等待队列中并设置成不可执行状态。当与等待队列相关的事件发生的时候，队列上的进程会被唤醒。为了避免产生竞争条件，休眠和唤醒的实现不能有纰漏。

2.怎么把自己加入等待队列

1)调用宏DEFINE_WAITO创建一个等待队列的项。

2）调用add_wait_queue()把自己加入到队列中。该队列会在进程等待的条件满足时唤醒它。当然我们必须在其他地方撰写相关代码，在事件发生时，对等待队列执行wake_upO操作。

3）调用prepare_to_wait()方法将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。而且该函数如果有必要的话会将进程加回到等待队列，这是在接下来的循环遍历中所需要的。

4）如果状态被设置为TASK_INTERRUPTIBLE，则信号唤醒进程。这就是所谓的伪唤醒(唤醒不是因为事件的发生)，因此检查并处理信号。

5)当进程被唤醒的时候，它会再次检查条件是否为真。如果是，它就退出循环﹔如果不是，它再次调用schedule(并一直重复这步操作）–-关于休眠有一点需要注意，存在虚假的唤醒。有时候进程被唤醒并不是因为它所等待的条件达成了才需要用一个循环处理来保证它等待的条件真正达成。

6)当条件满足后，进程将自己设置为TASK_RUNNING并调用finish_wait)方法把自己移出等待队列。

3.唤醒

唤醒操作通过函数wake_up()进行，它会唤醒指定的等待队列上的所有进程。它调用函数try_to_wake_up()，该函数负责将进程设置为TASK_RUNNING状态，调用enqueue_task)将此进程放入红黑树中，如果被唤醒的进程优先级比当前正在执行的进程的优先级高，还要设置need_resched标志。通常哪段代码促使等待条件达成，它就要负责随后调用wake_up()函数。举例来说,当磁盘数据到来时，VFS就要负责对等待队列调用wake_up(，以便唤醒队列中等待这些数据的进程。

切换上下进程

 内核必须知道在什么时候调用schedule()。如果仅靠用户程序代码显式地调用schedule()，它们可能就会永远地执行下去。相反，内核提供了一个need_resched标志来表明是否需要重新执行一次调度（见表4-1)。当某个进程应该被抢占时，scheduler_tick()就会设置这个标志﹔当一个优先级高的进程进入可执行状态的时候，try_to_wake_up()也会设置这个标志，内核检查该标志，确认其被设置，调用schedule()来切换到一个新的进程。该标志对于内核来讲是一个信息，它表示有其他进程应当被运行了，要尽快调用调度程序。

用户抢占

·从系统调返回用户空间时。

·从中断处理程序返回用户空间时。

内核抢占

为了支持内核抢占所做的第一处变动，就是为每个进程的thread_info 引入preempt_count计数器。该计数器初始值为0，每当使用锁的时候数值加1，释放锁的时候数值减1。当数值为0的时候，内核就可执行抢占。从中断返回内核空间的时候，内核会检查need_resched和preempt_count的值。如果need_resched被设置，并且preempt_count为0的话，这说明有一个更为重要的任务需要执行并且可以安全地抢占，此时，调度程序就会被调用。如果preempt_count不为0,说明当前任务持有锁，所以抢占是不安全的。这时，内核就会像通常那样直接从中断返回当前执行进程。如果当前进程持有的所有的锁都被释放了，preempt_count就会重新为0。此时，释放锁的代码会检查need_resched是否被设置。如果是的话，就会调用调度程序。有些内核代码需要允许或禁止内核抢占，

如果内核中的进程被阻塞了，或它显式地调用了schedule()，内核抢占也会显式地发生。这种形式的内核抢占从来都是受支持的，因为根本无须额外的逻辑来保证内核可以安全地被抢占。如果代码显式地调用了schedule)，那么它应该清楚自己是可以安全地被抢占的。

内核抢占

中断处理程序正在执行，且返回内核空间之前。

·内核代码再一次具有可抢占性的时候。

·如果内核中的任务显式地调用schedule(）

·如果内核中的任务阻塞(这同样也会导致调用schedule())

实时调度

Linux 提供了两种实时调度策略:SCHED_FIFO和SCHED_RR。而普通的、非实时的调度策略是SCHED_NORMAL。借助调度类的框架，这些实时策略并不被完全公平调度器来管理,而是被一个特殊的实时调度器管理。具体的实现定义在文件kerne/sched_rt.c.中，在接下来的内容中我们将讨论实时调度策略和算法。

SCHED_FIFO实现了一种简单的、先入先出的调度算法:它不使用时间片。处于可运行状态的SCHED_FIFO级的进程会比任何SCHED_NORMAL级的进程都先得到调度。一旦一个SCHED_FIFO级进程处于可执行状态，就会一直执行，直到它自己受阻塞或显式地释放处理器为止﹔它不基于时间片，可以一直执行下去。只有更高优先级的SCHED_FIFO或者SCHED_RR任务才能抢占SCHED_FIFO任务。如果有两个或者更多的同优先级的SCHED_FIFO级进程，它们会轮流执行，但是依然只有在它们愿意让出处理器时才会退出。只要有SCHED_FIFO级进程在执行，其他级别较低的进程就只能等待它变为不可运行态后才有机会执行。

SCHED_RR与SCHED_FIFO大体相同，只是SCHED_RR级的进程在耗尽事先分配给它的时间后就不能再继续执行了。也就是说，SCHED_RR是带有时间片的SCHED_FIFO———一这是一种实时轮流调度算法。当SCHED_RR任务耗尽它的时间片时，在同一优先级的其他实时进程被轮流调度。时间片只用来重新调度同一优先级的进程。对于SCHED_FIFO进程，高优先级总是立即抢占低优先级，但低优先级进程决不能抢占SCHED_RR任务，即使它的时间片耗尽。

实时优先级范围从О到MAX_RT_PRIO减1。默认情况下，MAX_RT_PRIO为100——所以默认的实时优先级范围是从О到99。SCHED_NORMAL级进程的nice值共享了这个取值空间;它的取值范围是从MAX_RT_PRIO到(MAX_RT_PRIO+ 40)。也就是说，在默认情况下，nice值从—20到+19直接对应的是从100到139的实时优先级范围。