Linux内核中的进程

多任务系统可以分为：非抢占式和抢占式。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状态的进程如果接收到一个信号，会被提前唤醒并响应该信号。两种状态的进程位于同一个等待队列上，等待某些事情，不能够运行。

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

等待队列的使用

static DECLARE_WAIT_QUEUE_HEAD(button_waitq);  //定义等待队列头

wait_event_interruptible(button_waitq, ev_press);              //休眠

wake_up_interruptible(&button_waitq);                  //唤醒

抢占和上下文切换

上下文切换就是从一个可执行进程切换到另一个可执行进程。Schedule函数主要完成两个工作：其一，把虚拟内存从上一个进程映射切换到新进程中。其二，从上一个进程的处理器状态切换到新进程的处理器状态。

内核必须知道在什么时候调用schedule函数，如何仅靠用户程序代码显式地调用schedule，它们可能就会永远的执行下去，所以内核中提供了一个need_resched标志来表明是否需要重新执行一次调度，该标志对于内核来讲是一个信息，它表示有其他进程应当被运行了，要尽快调用调度程序。

用户抢占

内核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule函数被调用，此时就会发生用户抢占。用户抢占在如下情况时产生：其一，从系统调用返回用户空间时。其二，从中断处理程序返回用户空间时。

内核抢占

在2.6版内核中，内核引入抢占能力，只要重新调度是安全的，即只要没有持有锁，内核就可以在任何时候抢占正在执行的任务。为了支持内核抢占，在每个进程的thread_info引入preempt_count计数器，当做一把锁来使用。内核抢占在如下情况时产生：其一，中断处理程序正在执行，且返回内核空间之前。其二，内核代码再一次具有可抢占性的时候。其三，如果内核中的任务显式地调用schedule函数。其四，如果内核中的任务阻塞（这样会调用schedule函数）。