运行队列
进程调度的最基本数据结构就是运行队列（struct runqueue 定义在<kernel/sched.c>）。运行队列是对应于CPU核的可运行进程的列表。也就是说一个CPU的核心对应一个运行队列。每个进程在同一时刻只能处于一个运行队列里。
有时候必须对运行队列中的信息进行更改，因此必须对其进行加锁，确保在同一时间不会有不同的修改操作，已造成不可预知的后果。当前CPU的核企图给其他CPU核的运行队列上锁的情况偶尔也会发生，这在以后会看到。最通常的给运行队列上锁的技术是task_rq_lock()和task_rq_unlock()函数。强调一下，常见的spin_lock()函数用于防止多个任务同时对某个运行队列进行操作。
优先队列
我们看到，在runqueue结构的定义中，有这么两个prio_array_t结构指针，分别是活动队列(active)和过气队列(expired)。活动队列是所有时间片还剩余的进程的集合。而过气队列，则是那些已耗尽时间片的进程的集合。如下图：
它们是调度算法中最关键的数据结构，在进入调度算法之前，先了解一下prio_array_t这个结构。该结构实际上是struct prio_array结构的别名：
nr_active是当前优先队列中可运行的进程数。MAX_PROI的值为140,用于表示系统中的每个优先级(因为两个Linux使用的优先级映射后的值正好是[0,140])。BITMAP_SIZE的值是5，因为我们用bitmap中的每一位来对应一个系统优先级，共140个优先级所以需要140位来表示。考虑到unsigned long通常为32位长，所以需要5个这样的数据才足够140位(实际上为5 * 32 = 160 位)。到这里我们能看出明显的对应关系，bitmap和queue的容量刚好都能对应于每个优先级。这样的对应关系的作用是什么？
初始化时，bitmap中的每一位都置位0，当某进程变可运行的时候(也就是说它的状态变成TASK_RUNNING)，其优先级对应于bitmap中的位置1。这样就简化了搜寻的工作量——要找到当前可运行的最高优先级的进程，只需要找到bitmap中第一个为1的位。因为优先级数目是固定的，所以搜寻工作的时间复杂度不会受到当前进程数目的影响。
在Linux中，我们通过调用sched_find_first_bit()函数来找到第一个为1的位。某些机器也提供了特别的指令来完成这一工作，比如在x86上的bsfl指令。所以在运行于x86的系统上，此工作的耗时仅为一条指令的时间。
名为queue的struct list_head结构的数组大小，是我们之前提到过的MAX_PROI。该数组中的项是一个可运行进程的列表，每一项都与相应的优先级对应，因此每项中包含的列表，实际上就是当前优先队列中，对应优先级的所有可运行进程的列表。因此找到下一个执行任务的工作就相当于在选出相应列表的下一个元素。
时间片再分配
Linux的算法很简单，根据之前的划分，在一个进程耗尽时间片时，会让将其移入过气队列尾部。在移入过气队列前，根据动态优先级等因素重新计算它的时间片大小(稍后讲解)。因为runqueue中的active和expired实际上是指针，所有当所有活动队列中的进程耗尽时间片，我们只需要简单地交换两个指针的值即可。
void schedule(void)
在开始前，可以稍微了解一下SMP（对称多处理器）这个概念。调度程序定义在<kernel/sched.c>中。当执行调度时，我们先找到Bitmap中首个为1的位，也就是寻找优先级最高的可执行进程：
然后进行一系列检测，如当前进程与待运行进程是否相同等等，若检测全都通过，则执行context_switch()函数进行进程间的切换:
计算优先级和时间片
优先级
每个进程诞生时都被分配了Nice值，存储在进程描述符中的static_prio中，被称为静态优先级。静态优先级不可被用户随意修改。但是调度程序是建立在动态优先级上的，动态优先级存储在进程描述符的prio成员中，其值是静态优先级和进程交互性的函数。具体的是调用effective_prio()函数来计算进程的动态优先级。
在effective_prio()用到了两个关键的宏，分别是:
#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
#define CURRENT_BONUS(p) \
(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
MAX_SLEEP_AVG)
由这两个宏得知，若进程的交互性越良好，其bonus值就越大，最后它的动态优先级就越高(prio值越低)。那么操作系统如何度量一个进程的交互性呢？
在LInux中就是通过计算进程的休眠时间。若进程花费大多数时间用于休眠，则为I/O密集型，反之则是CPU密集型，交互性就比较差。在进程描述符中有专门的成员来保存进程休眠的时间——sleep_avg，取值区间为[0,MAX_SLEEP_AVG(1000000ms)]。当一个进程由休眠状态变为可执行，系统就会计算其休眠时间，增加到sleep_avg上。反之，sleep_avg也会减去其运行时长。
因此，如果一个交互性差的进程，花费大量的时间片用于休眠(当进程休眠时，也耗费时间片)，就是说进程描述符中的sleep_avg值比较大，也就不会在动态优先级上得到很高的奖励。除了奖励，也会有惩罚，比如对那些CPU密集型的进程。这个机制提供了很高的响应速度，一个新建的交互性进程在短时间内就能达到很高的优先级。
时间片
时间片的计算依赖于静态优先级。
当新进程创建时，父子进程将平分父进程的剩余时间片。
当进程的时间片耗尽时，起吊用task_timeslice()进行再计算。优先级越高，则时间片越长。优先级越低，时间片越短。+19对应为5毫秒，0对应100毫秒，-20对应MAX_TIMESLICE，也就是800毫秒。这里不做叙述。
再插入
如果某进程交互性足够强，那么当其耗费时间片时，不会被插入到过气队列，而是再插入到活动队列。这个动作时调用scheduler_tick()来完成的。注意：scheduler_tick()与schedule()是两个独立的函数，至于有何关系，暂不明了。
如果过气队列存在长时间未被调度的进程，或是当前进程不满足交互性要求，则不执行再插入动作。Nice值为19或-20的进程永远不可能在插入。因为前者优先级太低，而后者则会一直被再插入到活动队列，占据CPU。
进程休眠
阻塞和休眠是同义词。如果没有这种状态，调度算法将会选择一个并不想运行的进程。进程的休眠可能处于很多原因，被动或者主动的。被动的如接收到休眠信号，主动的包括等待文件的输入输出等等。但是不管怎么样，欲休眠进程的行为几乎总是一致的——将自己标记为休眠状态，并且将自己置入等待队列(wait queue)，从运行队列(runqueue)中移除，然后调用schedule()进行切换。当唤醒时，动作几乎相反。
在Linux内核设计与实现 进程管理1: 基本数据结构，我们提到进程的四种状态(基于Linux2.6)。而其中与休眠相关的是TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE，其中的区别可翻阅前文得知。
之前我们提到过的等待队列(wait queue)和运行队列(runqueue)相呼应，其实质上是所有正在休眠中，等待某一事件发生的所有进程构成的队列。在内核中，通常用wake_queue_head_t数据结构来表示。我们可以用DECLARE_WAITQUEUE()静态地创建等待队列，也可以动态地创建，通过init_waitqueue_head()函数。
存在某些可能，使睡眠动作在等待的事件发生之后，导致进程无限休眠下去。因此在内核中，关于休眠的相关函数变得些许复杂。
进程唤醒
唤醒进程通过调用wait_up()，这个函数将给定等待队列中的所有进程唤醒(所以我们有理由认为:将等待同一事件的进程，都置于某个等待对队列中是一个明智的选择)。这个函数又调用try_to_wake_up()将进程状态设置为TASK_RUNNING。调用activate_task()将该任务加入运行队列中，同时置nead_resched(下文提及)为1，如果该进程的优先级高于当前进程的话。
非常重要的一点是，系统中存在假唤醒。也就是说一个任务很有可能在它所等待的事件未发生时唤醒，也许是因为信号或者什么缘故。所以我们必须如同图 sleep.1中那样，通过循环来确保那个事件确实发生了。
