多任务系统

多任务操作系统是能同时并发的交互执行多个进程的操作系统。多任务系统分为两种：非抢占式多任务（cooperative multitasking）和抢占式多任务操作系统（preemptive multitasking）。

非抢占式操作系统

非抢占式操作系统，除非进程自己主动停止运行，否则他会一直执行，进程主动挂起自己的操作叫做让步（yielding）。这种机制，调度程序无法对每个进程执行时间做出同一规定，可能造成超出预期的错误。

抢占式操作系统

Linux内核采用的就是抢占的多任务模式。这种模式由调度程序来决定一个进程运行时长，以便其他进程能够得到运行机会。这种强制挂起的动作就叫抢占（preemption）。进程能够运行的时长通过进程的时间片轮（timeslice）预先设定好。时间片轮就是分配给每个可执行程序的处理器时间段，有效管理时间片能使调度程序从程序全局角度做出调度决定。

完全公平调度（CFS）

Linux从2.6.23内核版本采用完全公平内核调度算法。 第二期 进程调度 - 图1系统调度策略主要平衡进程响应迅速和系统最大吞吐量之间的矛盾。Linux为了保证交互式应用和桌面系统程序的性能，所以对进程响应做优化，更倾向于优先调度I/O消耗型进程。

调度器

Linux调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性的选择调度算法。这种模块叫做调度器类，每一个调度器都有一个优先级，内核调度程序会按照调度器优先级遍历调度类，拥有一个可执行进程的最高优先级的调度器胜出，去选择下面要执行的进程。
CFS是针对普通进程的调度类，在Linux中称为SCHED_NORMAL。 第二期 进程调度 - 图2

Linux实现

1. 时间记账

  1. static void update_curr(struct cfs_rq *cfs_rq)
  2. {
  3.     struct sched_entity *curr = cfs_rq->curr;
  4.     u64 now = rq_of(cfs_rq)->clock_task;
  5.     unsigned long delta_exec;
  7.     if (unlikely(!curr))
  8.         return;
  10.     /*
  11.      * Get the amount of time the current task was running
  12.      * since the last time we changed load (this cannot
  13.      * overflow on 32 bits):
  14.      */
  15.     delta_exec = (unsigned long)(now - curr->exec_start);
  16.     if (!delta_exec)
  17.         return;
  19.     __update_curr(cfs_rq, curr, delta_exec);
  20.     curr->exec_start = now;
  22.     if (entity_is_task(curr)) {
  23.         struct task_struct *curtask = task_of(curr);
  25.         trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
  26.         cpuacct_charge(curtask, delta_exec);
  27.         account_group_exec_runtime(curtask, delta_exec);
  28.     }
  29. }
  31. static inline void
  32. __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
  33.           unsigned long delta_exec)
  34. {
  35.     unsigned long delta_exec_weighted;
  37.     schedstat_set(curr->statistics.exec_max,
  38.               max((u64)delta_exec, curr->statistics.exec_max));
  40.     curr->sum_exec_runtime += delta_exec;
  41.     schedstat_add(cfs_rq, exec_clock, delta_exec);
  42.     delta_exec_weighted = calc_delta_fair(delta_exec, curr);
  44.     curr->vruntime += delta_exec_weighted;
  45.     update_min_vruntime(cfs_rq);
  47. #if defined CONFIG_SMP && defined CONFIG_FAIR_GROUP_SCHED
  48.     cfs_rq->load_unacc_exec_time += delta_exec;
  49. #endif
  50. }
  • 计算当前程序执行update_curr的时间间隔 delta_exec；
  • 更新exec_start；
  • 更新总运行时长 sum_exec_runtime；
  • 根据进程权重，计算 delta_exec_weighted并更新到 curr->vruntime;

  • 更新min_vruntime, min_vruntime记录CFS运行队列上vruntime最小值，新创建进程的vruntime初始化为处理器可运行队列所有进程的最小vruntime（每个处理器都维护一个min_vruntime字段），这样可以防止（如果新进程vruntime置为0的话）老进程被饿死。min_vruntime保存单调递增特性。

    2. 进程选择

    CFS使用红黑树来组织可运行进程队列，并利用器迅速找到最小vruntime值的进程。
    红黑树的排序过程是同一个就绪队列所有进程按照其键值se->vruntime->cfs_rq->min_vruntime进行排序。键值较小的进程，在CFS红黑树中排序位置越靠左，因此也能更快的被调度：

  • 在程序运行时，进程vruntime稳定增加，它在红黑树中总是向右移动；

  • 越重要进程vruntime增长速度越慢（权重越低），因此被调度的机会就要越大；

  • 如果进程Sleep，则其vruntime保持不变，由于其他进程vruntime增加，因此它在红黑树中位置更靠左，下次被调度的机会增加。

    3. 调度器入口（schedule）

    1. static inline struct task_struct *
    2. pick_next_task(struct rq *rq)
    3. {
    4.   const struct sched_class *class;
    5.   struct task_struct *p;
    7.   /*
    8.    * Optimization: we know that if all tasks are in
    9.    * the fair class we can call that function directly:
    10.    */
    11.   if (likely(rq->nr_running == rq->cfs.nr_running)) {
    12.       p = fair_sched_class.pick_next_task(rq);
    13.       if (likely(p))
    14.           return p;
    15.   }
    17.   for_each_class(class) {
    18.       p = class->pick_next_task(rq);
    19.       if (p)
    20.           return p;
    21.   }
    23.   BUG(); /* the idle class will always have a runnable task */
    24. }

    4. 抢占与上下文切换

    进程上下文：它描述了进程的现有状态，进程上下文是进程执行活动全过程的静态描述，上下文信息包括指向可执行文件的指针、栈、内存（数据段和堆）、进程状态、优先级、程序I/O状态、权限、调度信息、审计信息、文件描述符、关于事件和信号的信息、寄存器组等。

上下文切换： 从一个可执行程序切换到另一个可执行进程，它完成两项基本工作：

  • 调用switch_mm（），负责把虚拟内存从上一个进程切换到新进程中；
  • 调用switch_to（），负责从上一个进程处理器状态切换到新进程处理器状态。这包括保存、恢复栈信息和寄存器信息，还有其他与体系结构相关的状态信息，都必须以每个进程为对象进行管理和保存。

抢占发生时间：只要没有持有锁，内核抢占就是安全的，因此每个进程thread_info引入preempt_count计数器记录锁的占用情况；使用锁的时候数值加一，释放锁的时候，计数减一。

实时调度策略

SCHED_NORMAL（CFS）调度普通的、非实时的进程。Linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR。
SCHED_FIFO 实现的一种简单的、先入先出的调度算法：他不使用时间片、处于可运行状态的SCHED_FIFO级的进程比SCHED_NORMAL级进程优先得到调度，一旦进程处于可执行状态，就会一直执行，直到它自己受阻塞或者显式释放处理器为止。只有更高级别的SCHED_FIFO或者SCHED_RR任务才能抢占SCHED_FIFO任务。
SCHED_RR 与SCHED_FIFO大体相同，只是带有时间片的SCHED_FIFO。