多任务系统可以分为:非抢占式和抢占式。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函数)。