linux内核设计与实现读书笔记
进程的调度程序是保证进程能有效工作的一个内核子系统。调度程序负责决定将哪个进程投入运行，何时运行以及运行多少时间。简单的来说，调度程序就是在给一堆就绪的进程分配处理器的时间，调度程序是多任务操作系统的基础。调度程序的原则就是最大限度的使用cpu的资源，也就是说，当系统中只要有可运行的进程，就不能让cpu处于空闲的状态，如果系统中没有就绪的进程时，则cpu会运行一个idle进程。
1.多任务
多任务操作系统就是能够同时并发的交互执行多个进程的操作系统，需要注意这里是并发，而不是并行。如果你的计算机有两个或者两个以上的cpu那么，你的计算机就可以真正同时、并行的执行多个任务。多任务操作系统可以分为两类：抢占式多任务和非抢占式多任务。
抢占式多任务中，由调度程序来决定什么时候停止一个进程的执行，这种由调度程序强行停止一个进程执行的动作称为抢占(preemption)。进程在被抢占之前运行的时间是固定的，而且有一个专门的名字，叫做时间片(timeslice)。时间片实际上是分配给每个进程的处理器时间段。
而非抢占式多任务是由进程自己做出让步，在执行了一段时间之后，主动地让出cpu。进程主动挂起自己的操作称为让步(yielding)，如果某个进程悬挂起来并且拒不作出让步的话，可能会导致操作系统崩溃。
所以总述上面的两种情况，抢占式多任务就像“法律”，只要时间到了，就把你撤下来。而非抢占式却像“道德”一样，你要是有道德，执行了一会之后，你就自己撤下来，如果有的“人”占着茅坑不拉屎，那其他进程除了用“道德”谴责它，也没有其他的办法了。
2.linux进程调度
linux最初的进程调度程序是非常原始的，很难适应一些众多的可运行进程和多处理器环境。后来从linux2.5开始，对linux的进程调度程序做了大的调整，使用了称为O(1)的调度算法，这个算法引起算法行为而得名。O(1)调度算法虽然在数以十计的多处理器上能表现出近乎完美的特性和可扩展性，但是由于这个算法在调度交互进程的时候并没有表现出很理想的效果。所以在linux2.6的开发初期，提出了CFS算法，即完全公平调度算法。
3.策略
(1)IO消耗型进程和处理器消耗型进程
IO消耗型进程指的是进程的大部分时间是用来等待IO的操作，例如图形用户界面(GUI)程序就属于IO消耗型程序，这个程序需要不断的监听来自用户的输入。这样的进程经常处于可运行的状态，但是每次运行的时间都很短。
处理器消耗型进程是指进程的大部分时间用在执行代码上，比如大型的计算程序MATLAB就属于处理器消耗型进程。
还有一些应用程序虽然划分为IO消耗型进程，但是也有处理器消耗型进程的特征。例如，字处理程序，在大多数时间可能等待来自用户的输入，但是在某段时间该程序又可能粘住处理器疯狂的进行语法和拼写错误的检查。
调度程序需要在两个矛盾目标中寻找平衡————进程的迅速响应和高吞吐量。unix和linux为了获得良好的用户响应，因此都倾向于调度IO消耗型进程。
(2)进程优先级
调度算法中最基本的一种就是基于进程优先级的调度，这是一种根据进程的价值和其对处理器的时间需求来对进程分级的一种想法。通常的做法是优先级高的进程先执行，低的后运行，相同优先级的进程按轮转方式进行调度(一个接一个，重复进行)。在某些操作系统中，优先级高的进程的使用的时间片也长一些。调度程序总是选择优先级高的，并且时间片尚未用尽的进程。
linux系统采用了两种不同类别的优先级，第一种是使用nice值，范围是从-20到+19，值越大表示优先级越低。这个优先级适用于一般的进程。
另外，linux对实时进程采用实时优先级，值从0-99，值越大代表优先级越高。实时进程的优先级都高于普通进程，因此这两个进程优先级是处于两个互不相交的范围内。
(3)时间片
时间片是一个数值，他表示进程在被抢占前能够持续运行的时间。时间片过长会导致系统对交互的响应表现欠佳，时间片过短，却又明显增大进程切换带来的处理器时间消耗。所以IO消耗型进程和处理器消耗型进程的矛盾在这里又再次显现出来，IO消耗型进程不需要长的时间片，而处理器消耗型进程则希望时间片越长越好。
长时间片将导致系统的交互性表现欠佳，很多的操作系统都很重视这一点，因此将时间片设置的很短，如10ms。但是linux的CFS调度算法并没有直接分配时间片到进程，它是将处理器的使用比分给了进程，这样进程获得的处理器的时间是和系统负载密切相关的。这个比例还会受到nice值的影响，nice值作为权重将调整进程使用处理器时间的使用比。具有更高nice值(低优先级)的进程将被赋予低权重，从而丧失一小部分处理器的使用比，而具有低nice值(高优先级)的进程江北赋予高权重，从而获得更多的处理器使用比。
在多数的抢占式操作系统中，一个新就绪的进程能否立即执行(即抢占原来的进程)，完全取决于新进程的优先级和是否有时间片。而在linux中采用的CFS调度器，其抢占时机取决于新的进程消耗了多少处理器的使用比，如果新就绪的进程消耗的处理器使用比低于当前的进程，则新进程抢占当前进程，立即投入运行。