版权所有，转载请说明转自 http://my.csdn.net/weiqing1981127

多任务系统可以分为：非抢占式和抢占式。Linux提供抢占式多任务模式。进程在被抢占之前能够运行的时间叫进程的时间片，Linux独一无二的公平调度程序本身并没有采用时间片来达到公平调度。

Linux之前采用O(1)调度器，它对大服务器的工作负载很理想，但是对响应时间敏感的程序却有不足。在2.6.23内核版本中用完全公平调度算法（CFS）代替了O(1)调度算法。

进程可以被分为I/O消耗型和处理器消耗型。I/O消耗型指进程的大部分时间用来提交I/O请求或是等待I/O请求。处理器消耗型指进程把事件大多数用在执行代码上。调度策略通常在两个矛盾中寻找平衡：进程响应迅速和最大系统利用率。Linux更倾向于优先调度I/O消耗型进程。

调度程序总是选择时间片未用尽而且优先级最高的进程运行。

Linux采用两种不同的优先级范围。第一种是nice值，越大的nice值意味着更低的优先级。第二种是实时优先级，其值可以配置，越高的实时优先级数值意味着进程优先级越高。任何实时进程的优先级都高于普通进程。

CFS做法：允许每个进程运行一段时间，循环轮转，选择运行最少的进程作为下一个运行进程，而不再采用分配给每一个进程时间片的做法，CFS在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片。CFS引入每个进程获得的时间片底线（最小粒度）默认情况为1ms，绝对的nice值不再影响调度决策，任何进程所获得的处理器时间由它自己和其他所有可运行进程nice值的相对差决定。

Linux调度的实现：

时间记账

调度器实体结构是struct sched_entity，它嵌入在进程描述符struct task_struct中。虚拟时间以ns为单位，存在vruntime变量中，它和定时器节拍不再相关，vruntime变量可以准确测定进程的运行时间，而且可以知道谁应该是下一个被运行的进程。

进程选择

当CFS需要选择下一个运行进程时，它会挑一个具有最小vruntime的进程，这就是CFS调度算法的核心：选择具有最小的vruntime的任务。这里采用红黑树实现的。

调度器入口

进程调度的主要入口点是schedule函数，该函数会以优先级为序，从高到低，依次检查每一个调度器，并且从最高优先级的调度器中，选择最高优先级的进程。

睡眠和唤醒

对于睡眠，内核的操作是：进程把自己标记为休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule函数选择和执行一个其他进程。对于唤醒，正好相反，进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中。

休眠有两种进程状态：TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。它们唯一的区别在于处在TASK_UNINTERRUPTIBLE的进程会忽略信号，处于TASK_INTERRUPTIBLE状态的进程如果接收到一个信号，会被提前唤醒并响应该信号。两种状态的进程位于同一个等待队列上，等待某些事情，不能够运行。

关于休眠还需要注意一点：存在虚假的唤醒，所以有时候需要一个循环处理来保证进程被唤醒的条件真正大达成。

等待队列的使用