调度程序没有太复杂的原理。大限度地利用处理器时间的原则是，只要有可执行进程，那么就总会有进程执行。但是只要系统中可运行的进程数目比处理器个数多，就注定某一给定时刻会有一些进程不能执行。
4.1 多任务
linux提供了抢占式的多任务处理模式，由调度程序来决定什么时候停止一个进程的运行，以便其他进程能够得到执行的机会。这个强制的挂起动作就叫做抢占。进程在被抢占之前能够运行的时间都是预先设置好的，叫进程的时间片。
在非抢占模式下，除非进程自己主动停止运行，否则他会一直执行。
4.2 linux的进程调度
4.3 策略
4.3.1 I/O消耗型和处理器消耗型的进程。
进程可以被分为I/O消耗型和处理器消耗型。前者指进程的大部分时间用来提交I/O请求或是等待I/O请求。因此这样的进程经常处于可运行状态，但通常都是运行短短一会儿，因为它在等待更多的I/O请求时总会阻塞。相反处理器耗费型进程把时间大多用在执行代码上。除非被抢占，否则他们通常都是一致不停的运行。对于这类进程，调度策略往往是尽量降低他们的调度频率，而延长其运行时间。
4.3.2 优先级进程
调度算法中最基本的一类就是基于优先级的调度。通常的做法是优先级高的进程先运行，低的后运行，优先级高的进程使用的时间片也较长。调度程序总是选择时间片未用尽而且优先级高的进程运行。用户和系统都可以通过设置进程的优先级来影响系统的调度。
linux采用两种不同的优先级范围1、nice值，越低优先级越高；第二种是实时优先级，其值可配置，默认情况下变化从0——99.越大优先级也越高。任何实时进程优先级都高于普通进程。实时优先级和nice值处于互不相交的两个范畴。
4.3.3 时间片
时间片是一个数值，它表明进程在被抢占前能持续运行的时间。调度策略必须规定一个默认的时间片：时间片过长——交互相应不佳；过短——明显增大进程切换带来的处理器耗时，进程运行的时间片过短。I/O消耗型不需要很长的时间片，处理器消耗型希望时间片越长越好。
Linux中使用新的CFS调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比。如果消耗的使用比比当前进程小，则新进程立刻投入运行，抢占当前进程。否则将推迟其运行。
4.3.4 调度策略的活动
以文本编辑器和视频解码器来举例。对文本编辑器而言，第一我们希望系统给它更多的处理器时间，这并非因为他需要更多的处理器时间，而是因为我们希望它能在我们需要的时候总是能立刻等到处理器资源，响应我们的要求抢占视频解码器。这样才能保证文本编辑器具有很好的交互性能，响应用户输入。
一旦文本编辑器被唤醒，CFS注意到给它的处理器使用比是50%，但是其实它用了很少。特别是，CFS发现文本编辑器比视频解码器用的少很多。这种情况下为了让所有进程公平分享处理器，它会立刻抢占视频解码程序让文本编辑器立刻投入运行。文本编辑器运行后，立即处理了用户的点击输入后，又一次进入睡眠等待用户的下一次输入。因为文本编辑器并没有消费掉承诺的50%的处理器使用比，因此情况依旧，CFS总是会毫不犹豫的让文本编辑器在需要时投入运行，而让视频处理程序只能在剩下的时刻运行。
4.4 Linux调度算法
4.4.1 调度器类
linux调度器是以模块的方式提供的，这样做的目的是允许不同类型的进程可以有针对性的选择调度算法。
4.4.2 Unix系统中的进程调度
在Unix系统上，优先级以nice值形式输出给用户空间，这会引起一些问题：
1、若要将nice值映射到时间片，就必然要将nice单位值对应到处理器的绝对时间。但这样做将导致进程切换无法最优化进行。优先级高时间片多低则少，无法解决I/O消耗型与处理器消耗型进程之间的矛盾。
2、相对nice值，把进程的nice值-1所带来的效果取决于其nice的初始值。
3、如果执行nice值到时间片的映射，需要分配一个绝对的时间片，这个要求意味着时间片必须是定时节拍器的整数倍
4、调度器为了进程能更快的投入运行，而去对新要唤醒的进程提升优先级，打破了公平原则，获得更多的处理器时间，损害其他进程的利益。
4.4.3 公平调度
进程调度的效果应该如同系统具备一个理想中的完美多任务处理器。这种系统中，每个进程将能获得1/n的处理器时间——n是指可运行进程的数量。
CFS的做法是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配每个进程时间片的做法。
nice值在CFS中被作为进程获取处理器比重的权重。CFS为完美多任务中的无限小调度周期的近似值设立了一个目标。这个目标称作：目标延迟，越小的调度周期将带来越好的交互性，同时也更接近完美的多任务。但是你必须承受更高的切换代价和更差的系统吞吐能力。
CFS引入了每个进程获得时间片的底线，这个底线成为最小粒度。
4.5 Linux调度的实现
1、时间记账
2、进程选择
3、调度器入库
4、睡眠和唤醒
4.5.1 时间记账
1、调度器实体结构 sched_entity 调度器实体结构作为名为se的成员变量，嵌入在进程描述符struct task_struct内。
2、虚拟实时
vruntime变量存放进程的虚拟运行时间，该运行时间的计算是经过了所有可运行进程总数的标准化（或者说是被加权的）。虚拟时间是以ns为单位的，所以vruntime与定时器节拍不再相关。
update_curr()是有系统定时器周期性调用的，无论在进程处于可运行状态还是被堵塞处于不可运行状态。vruntime可以准确的测量给定进程的运行时间。
4.5.2 进程选择
当CFS需要选择下一个运行程序时，它会挑一个具有最小vruntime的进程。CFS使用红黑树来组织可运行进程队列，并利用其迅速找到最小vruntime值的进程。
4.5.3 调度器入口
进程调度的主要入口点是函数schedule（）。schedule（）通常都需要和一个具体的调度类相关联，它会找到一个高优先级的调度类，然后问后者谁是下一个该运行的进程。schedule（）函数会调用pick_next_task()。
4.5.4 睡眠和唤醒
休眠的进程处于一个特殊的不可执行的状态。如果没有这种特殊状态的话，调度程序就可能选出一个本不愿意被执行的进程，更糟糕的是，休眠就必须以轮询的方式实现了。
1、等待队列
休眠通过等待队列进行处理。等待队列是由等待某些事件发生的进程组成的简单链表。内核用wake_queue_head_t来代表等待队列
2、唤醒
4.6 抢占和上下文切换
上下文切换，也就是从一个可执行进程切换到另一个可执行进程。由定义在kernel/sched.c中的context_switch()函数负责处理。每当一个新的进程被选出来准备投入运行的时候，schedule（）就会调用该函数。它完成两项基本工作：
1、调用asm/mmu_context.h中的switch_mm(),该函数负责把虚拟内存从上一个进程映射到新进程中。
2、调用switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息，还有其他任何与体系结构相关的状态信息，都必须以每个进程为对象进行管理和保存。
内核必须知道在什么时候调用schedule（）函数。内核提供了一个need_resched标志来表明是偶需要重调度。当某个进程被抢占时，scheduler_tick()就会设置这个标志；当一个优先级高的进程进入可执行状态时，try_to_wake_up()也会设置这个标志，内核检查该标志，调用schedule（）切换到新进程。
用于访问和操作need_resched的函数
set_tsk_need_resched();
clear_tsk_need_resched()；
need_resched（）检查need_resched标志，被设置返回真。
在返回用户空间以及从中断返回的时候，内核也会检查need_resched标志。如果已经被设置，则内核会在继续执行之前调用调度程序。
每个进程都含有一个need_resched标志，这是因为访问进程描述符内的数值要比访问一个全局变量快（因为current宏速度很快并且描述符通常都在高速缓存中）。
4.6.1 用户抢占
内核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule（）被调用，此时就会发生用户抢占。
用户抢占在以下情况下发生：
1、从系统调用返回
2、从中断处理程序返回用户空间
4.6.2 内核抢占
每个进程的thread_info引入了preempt_count计数器。该计数器初始值为0，当使用锁的时候其值+1，释放锁时-1.当数值为0的时候内核可抢占。从中断返回内核空间的时候，内核会检查need_resched和preempt，如果符合条件则调度程序会被调用。
如果内核中的进程被阻塞了或者内核显式的调用的schedule（），内核抢占也会发生。
内核抢占发生在：
1、中断处理程序正在执行
2、内核代码再一次具有可抢占性的时候。
3、显示调用schedule
4、内核任务阻塞
4.7 实时调度策略
linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR
SCHED_FIFO：简单的先进先出，不使用时间片，会比任何SCHED_NORMAL级别的进程优先得到调度。SHCED_FIFO会一直处于执行状态，直到自己阻塞或释放处理器，只有高优先级的FIFO或者RR可以抢占其任务。
SCHED_RR：与FIFO大体相同，RR进程在耗尽实现分配的时间后就不能再执行了。
Linux的实时调度算法提供了一种软实时的工作方式。软实时的含义是，内核调度进程，尽力使得进程在它限定的时间到来前运行，但内核不保证完全满足这种要求，硬实时保证在一定条件下，可以满足任何调度的要求。
实时优先级范围从0到99，SCHED_NORMAL级进程的nice值共享了这个取值空间，默认情况下，nice值从-20到19对应从100——139的的实时优先级范围。
4.8 与调度相关的系统调用
nice（）设置nice值
sched_setscheduler()；设置进程的调度策略
sched_getscheduler();
sched_setparam(); 设置进程的实时优先级
sched_getparm()；
sched_get_priority_max()； 获取实时优先级的大值
sched_get_priority_min()；
sched_rr_get_interval(); 获取进程的时间片值
sched_setaffinity()； 设置进程的处理器亲和力
sched_getaffinity（）；
sched_yield()； 暂时让出处理器，通过将进程从活动队列中移到过期队列中实现的。由此产生的效果不仅抢占了该进程并将其放入过期队列，这样保证一段时间内它都不会执行了。
