linux 2.6之后内核的进程调度算法是CFS：完全公平调度算法。
1.策略
1.1 I/O消耗性和处理器消耗型的进程
调度策略通常要在两个矛盾的目标中间寻找平衡：进程响应迅速和最大系统利用率了。
1.2 进程优先级
linux采用了两种不同的优先级范围。第一种是用nice值，范围从-20到+19，默认值为0；越大的nice值意味着更低的优先级。相比高nice值的进程，低nice值的进程可以获得更多的处理器时间。nice值也代表时间片的比例。可以通过ps -ef查看系统中的进程列表，结果中标记NI的一列就是进程对应的nice值。
第二种是实时优先级，其值是可配置的，默认情况下它的变化范围从0到99。与nice相反，越高的实时优先级数值意味着进程优先级越高。对应的Linux下是PTPRIO。
1.3 时间片
时间片是一个数值，代表进程在被抢占前所能持续运行的时间。时间片过长会导致系统对交互的响应表现欠佳，让人觉得系统无法并发执行应用程序；时间片太短会明显增大进程切换带来的处理器耗时，因为会有相当一部分系统时间用在进程切换上。
linux下的CFS调度器并没有直接分配时间片到进程，它是将处理器的使用比划分给了进程。
2.linux调度算法
2.1 调度器类
linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。
这种模块化结构被称为调度器类，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序。
完全公平调度（CFS）是一个针对普通进程的调度类。
2.2 公平调度
CFS的出发点基于一个简单的理念：进程调度的效果应如同系统具备一个理想中的完美多任务处理器。在这种系统中，每个进程将能获得1/n的处理器时间--n是指可运行进程的数量。
CFS的做法是允许每个进程运行一段时间，循环轮转，选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了，CFS在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片。nice值在CFS中被作为进程获得的处理器运行比的权重：越高的nice值进程获得更低的处理器使用权重，这是相对默认nice值进程的进程而言的；同理低nice值。
每个进程都按其权重在全部可运行进程中所占比例的“时间片”来运行，为了计算准确的时间片，CFS为完美多任务中的无限小调度周期的近似值设立了一个目标。而这个目标被称作“目标延迟”，越小的调度周期将带来教好的交互性，同时也更接近完美的多任务。但必须承受更高的切换代价和更差的系统总吞吐能力。一个目标延迟代表一次循环：所有进程都循环一次。
当可运行任务数量趋于无限时，它们各自所获得的处理器使用比和时间比将趋于0.这样无疑造成了不可接受的切换消耗。CFS为此引入每个进程获得的时间片底线，也称为最小粒度。
总结来说，任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值和相对差值决定的。nice值对时间片的作用不再是算数加权，而是几何加权。任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比。
3.linux调度的实现
vruntime变量存放进程的虚拟运行时间，该运行时间的计算是经历过了所有可运行进程总数的标准化。CFS使用vruntime变量来记录一个程序到底运行了多久时间以及它还应该再运行多久。
CFS试图利用一个简单的规则去均衡进程的虚拟运行时间：当CFS需要选择下一个运行进程时，它会挑一个具有最小vruntime的进程。其内部实现为红黑树，键值为vruntime。
3.1调度器入口
进程调度的主要入口点是函数schedule()，该函数中唯一重要的事情是调用pick_next_task()。
pick_next_task()会以优先级为序，从高到低，依次检查每一个调度类，并且从最高优先级的调度类中，选择最高优先级的进程。
3.2 睡眠和唤醒
休眠时，内核操作：进程把自己标记成休眠状态，从可执行红黑树中移除，放入等待队列，然后调用schedule()选择和执行一个其他进程。唤醒的过程刚好相反：进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中。
休眠有两种相关的进程状态：TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。它们的唯一区别是处于TASK_UNINTERRUPTIBLE的进程会忽略信号，而处于TASK_INTERRUPTIBLE状态的进程如果接收一个信号，会被提前唤醒并响应该信号。两种状态的进程位于同一个等待队列上，等待某些事件，不能运行。
- 等待队列
休眠通过等待队列进行处理。等待队列是由等待某些事件发生的进程组成的简单链表。内核用wakequeuehead_t来代表等待队列。休眠过程：
DEFINE_WAIT(wait);
add_wait_queue(q, &wait);
while(!condition) { /*condition为我们在等待的事件*/
prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE);
if(signal_pending(current))
/*处理信号*/
schedule();
}
find_wait(&q, &wait);
（1）调用DEFINE_WAIT()创建一个等待队列的项。
（2）调用add_wait_queue()把自己加入到队列中。该队列会在进程等待的条件满足时唤醒它，当然我们必须在其他地方撰写相关代码，在事件发生时，对等待队列执行wake_up()操作。
（3）调用prepare_to_wait()方法将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。而且该函数如果有必要的话会将进程加回到等待队列，这是在接下来循环遍历中所需要的。
（4）如果状态被设置为TASK_INTERRUPTIBLE，则信号唤醒进程。这就是所谓的伪唤醒，因此检查并处理信号。
（5）当进程被唤醒的时候，它会再次检查条件是否为真。如果是，它就退出循环；如果不是，再次调用schedule()并一直重复这步操作。
（6）当条件满足后，进程将自己设置为TASK_RUNNING并调用finish_wait()方法把自己移除等待队列。
2.唤醒
唤醒操作通过函数wake_up进行。
4.抢占和上下文切换
上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由context_switch()负责处理。每当一个新的进程被选出来准备投入运行的时候，schedule()就会调用该函数。它完成两项工作：
- 调用switch_mm()，该函数负责把虚拟内存从上一个进程切换到新进程。
- 调用switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。
内核必须知道什么时候调用schedule()。内核提供了一个need_resched标志来表明是否需要重新执行一次调度。在2.6以后的版本，它被移到thread_info结构体里，用一个特别的标志变量的一位来表示。
4.1 用户态抢占
用户态抢占发生在：
- 从系统调用返回用户空间时。
- 从中断处理程序返回用户空间时。
4.2 内核态抢占
只要没有持有锁，内核就可以进行抢占。锁是非抢占区的标志。
内核抢占发生在：
- 中断处理程序正在执行，且返回内核空间之前。
- 内核代码再一次具有可抢占性的时候。
- 如果内核中的任务显示调用schedule()。
- 如果内核中的任务阻塞（这样同样会调用schedule()）。
5.实时调度策略
linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR。而普通的，非实时的调度策略是SCHED_NORMAL。
SCHED_FIFO实现了一种简单的，先入先出的调度算法：不使用时间片。处于可运行状态的SCHED_FIFO级的进程会比任何SCHED_NORMAL级的进程都先得到调度。
SCHED_RR 与SCHED_FIFO大体相同，只是SCHED_FIFO级的进程在耗尽事先分配给它的时间片后就不能再继续执行了。
这两种实时算法实现的都是静态优先级。内核不为实时进程计算动态优先级。
linux的实时调度算法提供了一种软实时的工作方式：内核调度进程，尽力使进程在它的限定时间到来前运行，但内核不保证总能满足这些进程的要求。相反，硬实时满足。
6.与调度相关的函数调用
linux提供了一个系统调用族，用于管理与调度程序相关的参数。