调度器完成以下任务：

• 时钟中断(或类似的定时器)时间内刷新进程的时间片，设置进程调度标志
• 系统调用返回或中断完成时检查调度标志

schedule函数

内核代码中完成进程调度的函数为schedule()，该函数中包含以下调用：

由A进程进入schedule函数，从函数出来将变成B进程，A进程调用schedule相当于放弃cpu资源，进程从R状态变成S等其他状态都会经过schedule。在vmcore中，我们可以看到S状态进程进入S状态前最后一个调用的函数为schedule：

进程可以是“被调度”，而有的进程或线程主动调用schedule，放弃cpu，例如ksoftirqd内核线程。

进程优先级

早期的调度算法根据进程优先级计算进程运行的时间片、选择被调度的进程。对于普通进程(normal process)而言，nice表示其优先级，nice的取值范围为-20~19，nice值越大优先级越低；对于实时进程(real time process)而言，优先级的取值范围为0～99，同样值越大优先级越低。

内核代码中nice取值范围对应100~139，MAX_RT_PRIO宏定义了实时进程优先级与nice取值的分界点，实时进程的优先级比普通进程优先级高。

通过top、ps等命令我们可以查到进程的优先级，以下为top命令输出的下半部分，进程信息的查询结果：

其中(PR列值+100)指示进程优先级，以上输出中，java进程优先级为120，为普通进程；had进程优先级为2，为实时进程。RT表示该进程为实时进程，并且优先级为0。

可以使用renice命令设置普通进程的优先级：

调度算法

从最初的遍历O(n)算法，到2.5版kernel的O(1)算法，再到2.6版kernel的CFS(completely fair scheduler)，调度算法被不断地改进。

O(1)调度算法使得调度器选择下一个执行进程的时间变为常量，不随可运行进程数量变化，但其有以下缺点：

1. 动态调整进程优先级的算法很复杂，不易于代码维护
2. 不“偏袒”交互型程序，假如响应鼠标移动的进程与某后台进程有同一优先级，在鼠标被移动时，另一进程可能更先获得调度，这使得鼠标移动响应慢或有重影

因而应用于服务器，O(1)调度算法表现尚可，在交互性更强的桌面应用方面就强差人意。

CFS解决了以上O(1)算法问题，它的核心数据结构为红黑树，该红黑树的key为进程的虚拟运行时间(vruntime)。每次调度时选择具有最小vruntime的进程执行，即红黑树最左边的结点相应的进程。

CFS调度算法中，交互型的进程将获得更大的权重、更多被执行的机会。假如现在有一个vruntime为1ms的交互型进程，另有一个vruntime为10ms的cpu消耗型进程，调度器连续调度交互型进程10次，再调度vruntime为10ms的cpu消耗型进程。Android中使用的调度方法亦为CFS。

之前的调度算法中，nice优先级决定进程的时间片大小，在CFS中，nice与进程权重关联，权重大的进程获得的运行时间就长。prio_to_weight数组定义了nice与权重的对应关系，该数组在中定义。

调度策略

kernel提供了5种调度策略，针对普通进程，有以下3种：

这3种调度策略对应的进程，按CFS方式调度，优先级依次降低。

针对实时进程，有以下2种：

FIFO即先到先服务，具备该调度策略的进程将一直运行，直至其被I/O请求挂起或被具有更高优先级的实时进程抢占。

RR即轮叫调度(Round Robin)，除设定了进程运行的最大时间片外，其他调度方式与FIFO相同。

因实时进程的优先级比普通进程的优先级都要高，具备以上调度策略的进程变为可运行状态时，都将抢占以CFS方式调度的普通进程。

CFS调度算法相关的代码在sched_fair.c中，实时进程相关的调度算法在sched_rt.c中定义。

与进程调度策略相关的函数调用有以下两个，分别用于获取、设置进程调度策略：

以下程序示例使用sched_setscheduler调用，将程序自身的优先级设置为最高的实时优先级：

执行程序之后，我们在top中可以看到

设置实时进程的优先级只能通过函数调用，不像设置nice值，可使用renice命令。

负载均衡

对于多核cpu，kernel的调度器还需要解决另一个问题：如何在多核间做到负载平衡。若一个核忙于跑程序，而其他核是空闲的，那么就失去了多核存在的意义。

对于对称多处理(symmetric multiprocessing,SMP)架构的cpu，同一物理cpu中，多核间可共享cache，物理cpu之间则不能。因而在同一物理cpu多核间移动进程，相比物理cpu间移动进程，开销要小。

migration内核线程完成平衡多核工作负载的工作，migration以以下方式拉起：

1. 时钟中断处理函数timer_interrupt调用scheduler_tick函数
2. 在scheduler_tick中，trigger_load_balance函数被调用
3. 若满足调整cpu负载条件，trigger_load_balance通过raise_softirq调用产生一个软中断
4. 后续软中断得到处理， migration线程被拉起，完成负载平衡工作

另外我们可以通过taskset命令设置某进程在某个特定cpu上执行，并且不参与负载平衡调度：

以上命令设置sched_test在0号cpu上运行，使用top我们可以看到执行的效果：

Reference: Chapter 4 - Process Scheduling,  Linux kernel development.3rd.Edition