调度器以及CFS调度器

发表评论
161 views

调度器

Liux 内核中用来安排调度进程的执行模块成为调度scheduler ，它可以切换进程状态（process status) 比如 执行，可中断睡眠，不可中断睡眠，退出，暂停等。

调度器的作用相当于CPU 中央处理器的管理员，主要负责完成做两件事情： 1. 选择某些就绪进程来执行 2. 打断某些执行的进程让他们变为就绪状态

调度

安装某种调度的算法设计，从进程的就绪队列当中选取进程分配CPU ,主要是协调对cpu等等相关资源使用，进程调度的目的：最大限度利用CPU时间 ,如果调度器支持就绪状态切换到执行状态，同时支持执行状态切换到就绪状态，那么该调度器为抢占式调度器

调度类sched_struct 结构体源码分析

struct sched_class{
    const struct sched_class *next;
#ifdef CONFIG_UCLAMP_TASK
    int uclamp_enabled;
#endif
//将进程加入到执行队列当中，放到是红黑树当中，并对nr_running 变量自动加1
    void (*enqueue_task)(struct rq *rq,struct task_struct *p,int flags);
//从执行队列当中删除进程，并对nr_running 变量自动减1
    void (*dequeue_task)(struct rq *rq,struct task_struct *p,int flags);
//放弃cpu 执行，执行先出队后入队，它将调度实体存放在此红黑树的最右端 
    void (*yield_task)(struct rq *rq);
    bool(*yield_to_task)(struct rq *rq,struct task_struct *p,bool preempt);
    //专门用于检查当前进程是否可被新进程抢占
    Void(*check_preempt_curr)(struct rq *rq,struct task_struct *p,int flags);
    //选择下一个要运行的进程
    struct task_struct *(*pick_next_task)(struct rq *rq);
    //将进程施加到运行队列当中
    void (*put_prev_task)(struct rq *rq,struct task_struct *p);

    #ifdef CONFIG_SMP
        //为进程选择一个适合的CPU
        int (*select_task_rq)(struct task_struct *p,int task_cpu,int sd_flag,int flags);
        //迁移任务到另外一个cpu
        void(*migrate_task_rq)(struct task_struct *p,int new_cpu);
        //专门用于唤醒进程
        Void(*task_woken)(struct rq *this_rq,struct task_struct *task);
        // 修改进程在cpu的亲和力
        void（*set_cpus_allowed)(struct task_struct *p,const struct cpumask *newmask);
         //启动/禁止运行队列
         void (*rq_online)(struct rq *rq);
         void (*rq_offline)(struct rq *rq);

    #endif

}

调度器可分为： stop_sched_class,dl_sched_class,rt_sched_class,fair_sched_class 及 idle_sched_class stop_sched_class->停机调度类 dl_sched_class->限期调度类 rt_sched_class->实时调度类 fair_sched_class->公平调度类 idle_sched_class->空闲调度类

这5种调度类的优先级从高到低依次为：停机调度类，限期调度类，实时调度类，公平调度类，空闲调度类。 停机调度类：优先级是最高的调度类，停机进程是优先级最高的进程，可以抢占所有其他进程，其他进程不可能抢占停机进程。 限期调度类：最早使用优先算法，使用红黑树把进程按照绝对截止期限从小到大排序，每次调度时选择绝对截止期限最小的进程。 实时调度类: 为每个调度优先级维护一个队列。 公平调度类：使用完全公平调度算法，完全公平调度算法引入虚拟运行时间的相关概念，虚拟运行时间=实际运行时间*nice0 对应的权重/进程的权重。 空闲调度类：每个cpu上有一个空闲线程即0号线程，空闲调度类优先级最低，仅仅当没有其他进程可以调度的时候才会调度空闲线程。

优先级

task_struct 结构体中采用三个成员表示进程的优先级：prio 和normal_prio表示动态优先级，static_prio 表示进程的静态优先级 内核将任务优先级划分，实时优先级范围是0 到MAX_RT_PRIO-1(即99)，而普通进程的静态优先级范围是从MAX_RT_PRIO到jMAX_PRIO-1（即100到139）

//在include/linux/sched/prio.h
#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO MAX_USER_RT_PRIO
#define MAX_PRIO (MAX_RT_PRIO + NICE_WIDTH)
#define DEFAULT_PRIO (MAX_RT_PRIO + NICE_WITDH/2)

进程分类： 实时进程（real-time process)： 优先级高，需要立即被执行的进程。 普通进程(normal process)： 优先级低，更长执行时间的的进程。 进程的优先级是一个0--139 的证书直接来表示，数字越小，优先级越高，0-99 留给实时进程，100-139 留给普通进程。

内核调度策略

linux 内核提供一些调度策略供用户应用程序来选择调度器，linux内核调度策略源码分析：

//在include/uapi/linux/sched.h
#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
#define SCHED_IDLE 5
#define SCHED _DEADLINE 6
#define SCHED_RESET_ON_FORK 0x40000000
  1. SCHED_NORMAL:普通进程调度策略，是task 选择CFS调度器来调度运行；
  2. SCHED_FIFO:实时进程调度策略，先进先出调度没有时间片，没有更高优先级的状态下，只有等待主动让出CPU;
  3. SCHED_RR:实时进程调度策略，时间片轮转，进程使用完时间片，加入优先级对应运行队列当中的尾部，把CPU 让给同等优先级的其他进程。
  4. SCHED_BATCH:普通进程调度策略，批量处理，使得task选择CFS调度器来调度运行；
  5. SCHED_IDLE:普通进程调度策略，使task以最低优先级选择CFS调度器来调度运行
  6. SCHED_DEADLINE:限期进程调度策略，使task 选择Deadline 调度器来调度运行。

备注：其中stop调度器和DLE-task调度器，仅使用于内核，用户没有办法进行选择。

CFS调度器

##基本原理 完全公平调度算法体现在对待每个进程都是公平的，让每个进程都运行一段相同的时间片，这就是基于时间片轮询调度算法 CFS定义了一个新调度模型，他给cfs_rq(cfs的run queue)中的每一个进程都设置一个虚拟始终virtual runtime(cruntime)如果一个进程得以运行，随着执行时间的不断增加，他的vruntime也将不断增加，没有得到执行的进程vruntimr将保持不变。 备注：进程描述符task_struct 结构中，有几个成员与调度相关，具体成员：prio,normal_prio,static_prio,rt_priority等。

### 实际运行时间 CFS(完全公平调度器 completely fair Scheduler )在实际当中必须会有进程优先级高或者进程优先级低，CFS调度引入权重，使用权重代表进程的优先级，各个进程按照权重比例分配CPU时间。 假设有2个进程x和y,x 权重为1024，y权重为2048，x获得cpu时间比例为33.3%，y获得比例为66.7% 在引入权重之后分配给进程的时间计算如下： 实际运行时间=调度*进程权重/所有进程权重之和。

虚拟运行时间 = 实际运行时间NICE_0_LOAD/进程权重 = （调度周期进程权重/所有进程权重之后）nice_0_load/进程权重=调度周期1024/所有进程总权重。

在一个调度周期里面，所有进程的虚拟运行时间是相通的，所以在进程调度，只需要找到虚拟运行时间最小的进程调度运行即可。

### 调度子系统各个组件模块 调度器通过各个组件模块以及一系列数据结构，来排序和管理系统总的进程。 调用schedule()函数来完成进程的选择和切换 周期性调度器：根据频率自动调用scheduler_tick函数，作用根据进程运行时间触发调度。 上下文切换：主要做两个事情（切换地址空间，切换寄存器和栈空间）

### CFS 调度器类 CFS类调度类在linux 内核源码关键： enqueue_task_fair ：当任务进入可运行状态时，用此函数将调度实体存放到红黑树，完成入队操作 dequeue_task_fair: 当任务退出可运行状态时，用此函数将调度实体从红黑树中移除，完成出队操作

CFS调度器就绪队列内核

cfs_rq:跟踪就绪队列信息以及管理就绪态调度实体，并维护一直按照虚拟时间排序的红黑树。 struct rb_root_cached tasks_timeline->rb_root 是红黑树的根，tasks_timeline->rb_leftmost 指向红黑树中最左边的调度实体，即虚拟时间最小的调度实体。