1 进程状态模型
在操作系统中，进程的状态模型一般可以用进程五状态模型来概括，其他模型只是在五状态模型上的增删。
1.1 state域状态
对于Linux内核而言，进程的状态描述沿用了五状态模型，进程状态在进程描述符（task_struct）的state域（类似于C++类中成员变量的概念）中进行描述，该域有五种状态标志：
（1）TASK_RUNNING：被标记为该值的进程是可运行的，包括正在运行和在运行队列中等待执行的进程。对应进程五状态模型中的运行和就绪两种状态。
（2）TASK_INTERRUPTIBLE：被标记为该值的进程是被阻塞的，即进程在某些条件的满足后，才能投入运行，对应进程无状态模型中的阻塞状态。
（3）TASK_UNINTERRUPTIBLE：被标记为该值的进程同样是被阻塞的，但是和被标记为TASK_INTERRUPTIBLE的进程不同，被标记为该值的进程是不可中断的，对外部信号不会做任何响应。所以该值标记的进程必须是在等待时不受干扰，或者等待时间很快发生时才使用。 该状态同样对应于进程无状态模型中的阻塞状态。
（4）__TASK_TRACED：被标记为该值的进程是被其他进程跟踪的。在五状态模型中没有对应的状态。
（5）__TASK_STOPPED：被标记为该值的进程是停止执行的，进程没有投入运行，也不能投入运行。在五状态模型中没有对应的状态。虽然该状态可以勉强归为退出态，但是这种描述并不准确。
需要注意的是，在Linux操作系统上使用ps命令查看进程状态时，往往看到的进程状态为以下几种：
（1）D ：不可中断的深度睡眠，一般由IO引起，同步IO在做读或写操作时，此进程不能做其它事情，只能等待，这时进程处于这种状态，如果程序采用异步IO，这种状态应该就很少见到了
（2）R：进程处于运行或就绪状态
（3）S： 可接收信号的睡眠状态
（4）T：被ctrl+z中断或被trace
（5）W：2.6的系统版本之后已不在使用
（6）X：进程已经完全死掉，此状态不可见
（7）Z： 进程已经终止，但是其父进程尚未对其进行处理
这些通过ps命令可以查询到的标志位，其实都是内核进程状态的一种反映，他们和内核进程的state域不能混为一谈。
2 Linux进程调度
2.1 进程种类和调度算法演变
编写高效的进程调度程序就需要对进程的种类有所了解，进程由于其执行操作类别执行时间等被分为了两种类型，一种为I/O消耗型，另一种为处理器消耗型（有时又被称为I/O密集型和处理器密集型）。所谓I/O消耗型指进程的大部分时间都用来提交和等待I/O请求，所以进程经常需要运行，但是由于I/O的原因，又会经常被阻塞，但是运行时间很短；而处理器消耗型则是指进程把大部分时间用在代码的执行上。
但是实际上进程的类型时复杂的，进程有时候可能会同时拥有I/O消耗型和处理器消耗型的特性；而又有一些进程在一段时间内是I/O消耗型，而在另外一段时间又是处理器消耗型。所以调度程序需要能动态地对进程进行合法的调度，来提高系统运行的效率。
调度程序的目标一般有两个,进程响应速度和最大系统利用率，这两个目标其实是互相矛盾的，所以进程调度程序需要在二者之中取得平衡。为了追求更高的性能，进程调度程序在Linux内核的2.5版本中引入了O(1)调度器来取代之前的调度程序，为了提高系统的响应性，内核开发者又在2.6版本时，引入了反转楼梯最后期限调度算法（Rotating Staircase Deadline Scheduler）(RSDL)，RSDL后来又演变为“完全公平调度算法”，简称CFS，并在2.6.23内核版本中取代了O(1)调度算法。
2.2 传统进程调度算法
进程调度算法一般来说可以分为两种，优先级调度算法和时间片调度算法，这两种调度算法大多数操作系统都进行结合使用。优先级调度根据进程价值和进程对处理器需求来对进程的优先级进行划分，高优先级先执行，低优先级后执行，然后不断轮转。而时间片调度算法则是为每一个可执行的进程分配一个时间片（有时也被称为量子或者处理器片），这个时间片就是在一段时间内可供进程执行的时间（更专业的说法是时间片表示的是进程在被抢占前所能持续运行的时间），当进程时间片用完之后，就会从处理器中换出，而另外一个时间片没有用完的进程就会被换入处理器中开始执行。Linux操作系统中的CFS也使用了优先级和时间片这两个概念，但是其实现方式有其特殊之处。
Linux内核规定了两种优先级，第一种为nice值，第二种为实时优先级（该值的设置意味这进程为实时进程，先不进行分析）。nice值的范围在-20到+19之间，默认为0，nice值越大优先级越低。在传统的Unix或者在CFS（完全公平调度算法）之前，nice值和时间片的映射关系为简单映射，例如nice值为0时，对应的时间片为100ms，nice为+19时就对应5ms，所以nice直接决定了时间片的大小（又被称为绝对时间片分配，或者nice值对时间片进行算数加权）。
2.3 传统调度算法主要问题
（1）进程切换过于频繁：假设nice为0的时间片为100ms，那么nice值为+19的时间片就为5ms，毫无疑问，当两个nice值为19的进程存在时，系统每过5ms就要进行一次进程调度，导致进程切换十分频繁，大量时间被进程切换所消耗。
（2）nice值的不同导致时间片大小相差过大：假设nice值为0时的时间片为100ms，那么nice值为18的时间片为10ms，nice值为19的时间片为5ms，而18和19nice值仅仅只是相差1，但是时间片却相差了两倍，这明显是不合理的。
（3）最小时间片无法实现：由于系统限制，要求所有时间片必须为定时器节拍的整数倍（先行记下再说），那么就导致最小时间片也是定时器节拍的整数倍；系统定时器限制了两个时间片的差异；时间片会随着定时器节拍改变。（这个和后面的定时器有关，但是这一点的确是CFS被采用的主要原因）
（4）无法进行公平调度：为了使有些进程能够更快地投入运行，该进程的优先级可能会被提高，即使该进程时间片用尽，这样就会导致时间片分配的问题，使得某些进程可以获得更多处理器时间，损害其他进程的利益。
2.4 CFS完全公平调度算法
完全公平调度算法CFS将进程获取的处理器时间进行了重新的划分，时间片和nice值之间的关系不再是绝对的，而是一种相对的划分方式。CFS希望进程调度的效果和一个具有理想完美多任务处理器的系统相同。在这种系统中，若有n个进程，那么每个进程将被分配到1/n的处理器时间。CFS就是在这样的理想模型下，考虑了在现实中进程的切换的代价所设计的。CFS允许每个进程运行一段时间、循环轮转、选择运行最少的进程最为下一个运行进程，然后将nice值的概念重新定义，不在像之前一样，将nice值和时间片进行绝对映射，而是将nice值作为进程获得处理器运行比的权重，越高的nice值获得的处理器运行比权重越低。每个进程都按照权重，获取自身在全部可运行进程所占比例的时间片运行。
为了更加精确计算框出时间的可运行时间，CFS又引入了目标延迟——完美多任务中的无限小调度周期近似值。为了更直观的说明问题，可以使用代数式来进行表达。假设目标延迟为T，系统中有三个nice值分别为0，+10，+15的进程，而nice值0所对应的权重值为Q_0，nice值10对应的权重值为Q_10，nice值15对应的权重值为Q_15,那么三个进程时间片就分别为如下所示：
t_0=Q_0/(Q_0+Q_10+Q_15 ) T
t_10=Q_10/(Q_0+Q_10+Q_15 ) T
t_15=Q_15/(Q_0+Q_10+Q_15 ) T
！注意，在CFS中所指的时间片一般都是进程在目标延迟内的可运行时间，而有一些书里会提到"CFS不再有时间片概念"（例如《Linux内核设计与实现》），其实是指绝对时间片的分配
这样的划分方式又重新引入了一个问题，那就是当可运行的任务数量趋于无限时，每个进程所获得的处理器使用比和时间片都会趋于0，这样将会导致系统不断进行进程切换，造成系统资源的巨大损耗。为了解决这个问题，CFS特意引入了另外一个概念——最小粒度，最小粒度为每个进程可以获得的时间片最小值，这个值在默认情况下为1ms。采用最小粒度之后，即便有可运行进程数量趋于无限，每个进程也能获得最小粒度的执行时间。
CFS对于nice值的重新定义，解决了之前绝对映射的问题。
首先，当只有两个nice值相同但是都很大的进程在系统中运行时，其所占据的时间片都为目标延迟的二分之一，而不是之前很小的值，这样就解决了两个高nice值进程运行导致的进程频繁切换问题；
其次，当只有两个高nice值，但是两个nice值并不相同的进程在系统中运行时，由于将nice值原来和时间片的绝对映射改为了相对映射，所以不会出现nice值相差很小，但是时间片倍数相差的情况；
然后，引入处理器使用比的方法，解决分配绝对时间片引发的时间片会随着时钟节拍修改的问题，进程运行的时间片也不再是一个绝对值；
最后，对时间片分配方式进行了重新设计，处理器使用比的分配不会出现固定的进程切换频率问题，更好地进行公平调度。
但是在采用CFS的系统中，如果出现大量可运行进程，由于最小粒度的存在，将会导致一个问题，那么就是nice值的大小，对于进程所获取到的时间片大小没有影响，所有进程的时间片都将为最小粒度，导致进程调度公平性问题。这一问题的出现本质上是为了保证系统进程不会出现频繁切换所做出的必要牺牲，这是一个进程调度程序设计过程中的取舍，而且在设计中也尽量去规避这个问题，所以当系统中可运行进程数量在只有几百个时（通常情况下系统中的可运行进程数目），CFS的公平性是可以可以保证的。
2.5 CFS进程选择
进程选择（选择下一个执行的进程）是进程调度中另一个重要的方面。在CFS中其实现方法如下：
首先，CFS为每一个进程维护了一个实际运行时间和理想运行时间
其次，周期性地按照权重对进程的实际运行时间进行计算（和CFS时间片计算相同）
最后，在进行进程选择的时候，比较实际运行时间和理想运行时间，选择二者相差最大的进程投入运行
可以注意到，CFS通过实际运行时间和理想运行时间来进行进程选择。这样做的好处就是可以将I/O消耗型进程和处理器消耗型进程进行区分调度。一般来说I/O消耗型进程追求响应速度，而处理器消耗型进程追求系统利用率。
从CFS中的进程选择设计中可以看出，若每一个进程都拥有一个理想运行时间，那么由于I/O消耗型进程一直在等待I/O事件的完成所以其实际运行时间必然很小，而处理器消耗型进程一直运行，所以其实际运行时间很大，所以在CFS调度算法在面对都可运行的I/O消耗型进程和处理器消耗型进程时，会更加倾向于去调用I/O消耗型进程，因此解决了系统反应速度的问题。
这是个人在阅读《Linux内核设计与实现》时候的一点心得，里面加入了一些自己关于操作系统的理解，对自己的现有的知识进行梳理，如有错误敬请指正。
