IT攻城狮小明
0%

《趣谈linux操作系统》小结(十一) - 进程调度

发表于 分类于 Valine：

进程分为实时进程和普通进程。 实时进程需要立刻执行返回结果，普通进程没有这个需求。

task_struct中有策略信息和优先级信息

1
2
3
4
5
6
7
8
9
10
11
12
13

unsigned int policy;
int prio, static_prio, normal_prio;
unsigned int rt_priority;

// policy 取值如下
#define SCHED_NORMAL    0
#define SCHED_FIFO    1
#define SCHED_RR    2
#define SCHED_BATCH    3
#define SCHED_IDLE    5
#define SCHED_DEADLINE    6

对于实时进程，优先级的范围是 0～99；对于普通进程，优先级的范围是 100～139。数值越小，优先级越高。

实时调度策略

对于调度策略，其中 SCHED_FIFO、SCHED_RR、SCHED_DEADLINE 是实时进程的调度策略。

  • SCHED_FIFO 就是交了相同钱的，先来先服务，但是有的加钱多，可以分配更高的优先级，也就是说，高优先级的进程可以抢占低优先级的进程，而相同优先级的进程，我们遵循先来先得。
  • SCHED_RR 轮流调度算法，采用时间片，相同优先级的任务当用完时间片会被放到队列尾部，以保证公平性，而高优先级的任务也是可以抢占低优先级的任务。
  • SCHED_DEADLINE，是按照任务的 deadline 进行调度的。当产生一个调度点的时候，DL 调度器总是选择其 deadline 距离当前时间点最近的那个任务，并调度它执行。

普通调度策略

  • SCHED_NORMAL 是普通的进程
  • SCHED_BATCH 是后台进程，几乎不需要和前端进行交互。这类项目可以默默执行，不要影响需要交互的进程，可以降低它的优先级。
  • SCHED_IDLE 是特别空闲的时候才跑的进程

调度策略的实现者， 调度类

1
2

const struct sched_class *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 就是空闲进程的调度策略。

下面是普通进程的调度

完全公平调度算法 CFS

计算根据进程的优先级分配不同的权重，然后计算每个进程的运行时间值。 对比运行的实际值，小的就优先运行。保证每个进程都可以运行到。

调度队列与调度实体

进程调度实体涉及的成员

1
2
3
struct sched_entity se;
struct sched_rt_entity rt;
struct sched_dl_entity dl;

CFS不同的进程通过把调度的实体挂在红黑树上实现快速的调度。所有可运行的进程通过不断地插入操作最终都存储在以运行时间vruntime为顺序的红黑树中，vruntime 最小的在树的左侧，vruntime 最多的在树的右侧。 CFS 调度策略会选择红黑树最左边的叶子节点作为下一个将获得 CPU 的任务。

每个cpu都有自己的 struct rq 结构，其用于描述在此 CPU 上所运行的所有进程，其包括一个实时进程队列 rt_rq 和一个 CFS 运行队列 cfs_rq。在调度时，调度器首先会先去实时进程队列找是否有实时进程需要运行，如果没有才会去 CFS 运行队列找是否有进程需要运行。

图片替换文本

实现不同进程的调度，是通过按优先级从高到低来遍历调度类的方法来实现的。为了确保进程不被饿死，还需要动态更新进程的优先级，保证长时间未运行的进程随着时间变长而提升优先级，使之可以更快的被调用到。rt_sched_class 先被调用，它会在 rt_rq 上找下一个任务，只有找不到的时候，才轮到 fair_sched_class 被调用，它会在 cfs_rq 上找下一个任务。这样保证了实时任务的优先级永远大于普通任务。

图片替换文本

行动，才不会被动!

欢迎关注个人公众号 微信 -> 搜索 -> fishmwei，沟通交流。