调度策略与调度类

在 Linux 里面，进程大概可以分成两种:

  • 实时进程, 尽快返回结果
  • 普通进程

在 task_struct 中，有一个成员变量，我们叫调度策略 (policy):

  • 不同的策略有不同的算法
  1. unsigned int policy;
  4. #define SCHED_NORMAL    0
  5. #define SCHED_FIFO    1
  6. #define SCHED_RR    2
  7. #define SCHED_BATCH    3
  8. #define SCHED_IDLE    5
  9. #define SCHED_DEADLINE    6

优先级 (priority):

  1. int prio, static_prio, normal_prio;
  2. unsigned int rt_priority;
  • 对于实时进程，优先级的范围是 0～99；
  • 对于普通进程，优先级的范围是 100～139
  • 数值越小，优先级越高。

实时调度策略

  • SCHED_FIFO, 同优先级采用先进先出
  • SCHED_RR, 同优先级采用轮流调度算法 (时间片)
  • SCHED_DEADLINE, 选择 deadline 最近的

普通调度策略

  • SCHED_NORMAL, 普通线程平均分配
  • SCHED_BATCH, 后台进程降低优先级
  • SCHED_IDLE, 特别空闲的时候才跑

调度类

  1. const struct sched_class *sched_class;

几种实现:

  • stop_sched_class 优先级最高的任务会使用这种策略，会中断所有其他线程，且不会被其他任务打断；
  • dl_sched_class 就对应上面的 deadline 调度策略；
  • rt_sched_class 就对应 RR 算法或者 FIFO 算法的调度策略，具体调度策略由进程的 task_struct->policy 指定；
  • fair_sched_class 就是普通进程的调度策略；
  • idle_sched_class 就是空闲进程的调度策略。

完全公平调度算法

Linux 中实现了 CFS 调度算法.

  • 进程运行时间

调度队列与调度实体

能够平衡查询和更新速度的是树，在这里使用的是红黑树。
**
所有可运行的进程通过不断地插入操作最终都存储在以时间为顺序的红黑树中，vruntime 最小的在树的左侧，vruntime 最多的在树的右侧。 CFS 调度策略会选择红黑树最左边的叶子节点作为下一个将获得 CPU 的任务。

在调度时，调度器首先会先去实时进程队列找是否有实时进程需要运行，如果没有才会去 CFS 运行队列找是否有进程需要运行。

image.png

调度类是如何工作的？

可以看到，这里面有一个 for_each_class 循环，沿着上面的顺序，依次调用每个调度类的方法。

  1. /*
  2.  * Pick up the highest-prio task:
  3.  */
  4. static inline struct task_struct *
  5. pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
  6. {
  7.   const struct sched_class *class;
  8.   struct task_struct *p;
  9. ......
  10.   for_each_class(class) {
  11.     p = class->pick_next_task(rq, prev, rf);
  12.     if (p) {
  13.       if (unlikely(p == RETRY_TASK))
  14.         goto again;
  15.       return p;
  16.     }
  17.   }
  18. }

这就说明，调度的时候是从优先级最高的调度类到优先级低的调度类，依次执行。而对于每种调度类，有自己的实现，例如，CFS 就有 fair_sched_class。

这样整个运行的场景就串起来了，在每个 CPU 上都有一个队列 rq，这个队列里面包含多个子队列，例如 rt_rq 和 cfs_rq，不同的队列有不同的实现方式，cfs_rq 就是用红黑树实现的。

下面我们仔细看一下 sched_class 定义的与调度有关的函数:

  • enqueue_task 向就绪队列中添加一个进程，当某个进程进入可运行状态时，调用这个函数；
  • dequeue_task 将一个进程从就绪队列中删除；
  • pick_next_task 选择接下来要运行的进程；
  • put_prev_task 用另一个进程代替当前运行的进程；
  • set_curr_task 用于修改调度策略；
  • task_tick 每次周期性时钟到的时候，这个函数被调用，可能触发调度。

总结

一个 CPU 上有一个队列，CFS 的队列是一棵红黑树，树的每一个节点都是一个 sched_entity，每个 sched_entity 都属于一个 task_struct，task_struct 里面有指针指向这个进程属于哪个调度类。

image.png