调度器

  调度器的主要工作就是选择就绪的进程来执行。目前Linux支持的调度器有五种：stop scheduler、Deadline scheduler、RT scheduler、CFS scheduler、Idle scheduler。

调度类

  从Linux2.6.23开始，Linux引入scheduling class的概念，目的是为了将调度器模块化。这样提高了扩展性，添加一个新的调度器也变得简单起来。
  调度器的抽象基类为struct sched_class；

/** 调度器基类* linux中主要包含stop_sched_class、dl_sched_class、rt_sched_class、fair_sched_class以及idle_sched_class等调度类。* 每一个进程都对应一种调度策略，每一种调度策略又对应一种调度类（每一个调度类可以对应多个调度策略）。* 每一个进程创建之后，总是要选择一种调度策略。针对不同的调度策略，选择的调度类也是不一样的。*/ 
struct sched_class {const struct sched_class *next; // 操作系统中有多个调度类, 按照调度优先级排成一个链表, 即优先级高的调度类先执行。next指针指向下一个调度类（比自己低一个优先级）#ifdef CONFIG_UCLAMP_TASKint uclamp_enabled;
#endif/* * 将待运行的任务加入到执行队列（per-cpu rq）中, 即将调度实体(进程)存放在红黑树中, 并对nr_running变量加1。* 典型的场景就是内核里的唤醒函数，将被唤醒的任务插入rq，然后设置任务状态为TASK_RUNNING。* 对CFS调度器来说，则是将任务插入红黑树，并对nr_running变量加1。*/void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);/* * 从执行队列（per-cpu rq）当中删除进程, 并对nr_running变量减1。* 典型的场景就是任务调度引起阻塞的内核函数，把任务状态设置为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE，* 然后调用schedule函数，最终触发dequeue_task的操作。对于CFS调度器来说，就是将不在运行状态的任务从红黑树中移除，然后nr_running减1。*/void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);/* * 处于运行态的任务申请主动让出CPU执行权限,实际上此函数执行先出队后入队,在这种情况它直接将调度实体存放在红黑树的最右端。* 典型的场景就是处于运行态的应用调用sched_yield（系统调用），直接让出CPU。此时sched_yield先调用yield_task申请让出CPU，然后调用schedule切换上下文。* 对CFS调度器来说，如果nr_running是1,则直接返回，最终schedule函数也不会产生上下文切换。否则，任务被标记skip状态。* 调度器在红黑树上选择待运行任务时肯定跳过该任务。之后，因为schedule函数被调用，pick_next_task最终被调用。* 其代码会红黑树中最左侧选择一个任务，然后把要放弃运行的任务放回红黑树，然后调用上下文切换函数来做上下文切换。*/void (*yield_task)   (struct rq *rq);bool (*yield_to_task)(struct rq *rq, struct task_struct *p, bool preempt);/* * 当一个进程被唤醒或者创建的时候，需要检查当前进程时候可以抢占当前cpu上正在运行的进程，如果可以抢占需要标记TIF_NEED_RESCHED flag。*/void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);/* * 选择下一个最适合调度的任务，将其从rq移除。并且如果前一个任务还保持在运行态，即没有从rq移除，则将当前的任务重新放回到rq。* linux调度核心在选择下一个和时的task运行的时候，会按照优先级的顺序遍历调度类的pick_next_task函数。因此SCHED_FIFO调度策略的实时进程永远比SCHED_NORMAL调度策略的普通进程优先运行。* 内核schedule函数利用它来完成调度时任务的选择。对CFS调度器而言，大多数情况下，下一个调度任务是从红黑树的最左侧节点选择并移除。* 如果前一个任务是其它调度类，则调用该调度类的put_prev_task方法将前一个任务做正确的安置处理。* 但如果前一个任务也属于CFS调度类的话，为了效率，跳过调度类标准方法put_prev_task，但核心逻辑仍然是put_prev_task_fair的主要部分。*/struct task_struct *(*pick_next_task)(struct rq *rq);/* 将前一个正在CPU上运行的任务从CPU上拿下。如果任务还在运行态则将任务放回rq，否则，根据调度类要求做简单处理。* 如果将要被拿下的任务属于CFS调度类，则使用CFS调度类的具体实现put_prev_task_fair。* 此时，如果任务还是TASK_RUNNING状态，则被重新插入的哦红黑树的最右侧。* 如果这个任务不是TASK_RUNNING状态，则已经从红黑树移除过了，只需要修改CFS当前任务指针cfs_rq->curr即可。*/void (*put_prev_task)(struct rq *rq, struct task_struct *p);/*  将进程从运行队列删除，并作为当前运行实体 */void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);#ifdef CONFIG_SMPint (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);/** 为给定的任务选择一个rq，返回rq所属的CPU号。* 典型的使用场景是唤醒，fork/exec进程时，给进程选择一个rq，这也给调度器一个CPU负载均衡的机会。* 对CFS调度器而言，主要是根据传入的参数要求找到符合亲和性要求的最空闲CPU所属的rq。*/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中的亲和力 ; 用于改变进程的执行CPU，即改变进程执行时所占用的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/** */void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);  // 周期性调度void (*task_fork)(struct task_struct *p);void (*task_dead)(struct task_struct *p);/** The switched_from() call is allowed to drop rq->lock, therefore we* cannot assume the switched_from/switched_to pair is serliazed by* rq->lock. They are however serialized by p->pi_lock.*/void (*switched_from)(struct rq *this_rq, struct task_struct *task);void (*switched_to)  (struct rq *this_rq, struct task_struct *task);void (*prio_changed) (struct rq *this_rq, struct task_struct *task,int oldprio);unsigned int (*get_rr_interval)(struct rq *rq,struct task_struct *task);void (*update_curr)(struct rq *rq);#define TASK_SET_GROUP		0
#define TASK_MOVE_GROUP		1#ifdef CONFIG_FAIR_GROUP_SCHEDvoid (*task_change_group)(struct task_struct *p, int type);
#endif
};

进程调度策略和优先级

stop_sched_class

• 优先级最高的调度类，可以抢占其他所有的进程，但不能被其他进程抢占。用于执行一些特别紧急的进程。
• 每个CPU只有一个stop线程，所以没有具体的调度策略和优先级，内核提供了一些接口可以向这些进程push work。
• 主要用于负载均衡机制中的进程迁移、softlockup、cpu hotplug、rcu
     softlockup：一种会引发系统在内核态中一直循环超过20秒，导致其他任务没有机会得到运行的BUG。
     cpu hotplug：cpu热插拔，是cpu电源管理的一部分，支持系统在负载比较低的时候，拔掉一个cpu，从而省下cpu的静态功耗，并在系统需要时，重新将cpu插上。
     rcu：

dl_sched_class

• 使用红黑树，把进程按照绝对截至期限进行排序，选择最小进程进行调度运行，属于硬实时。适用于对调度时间有明确要求的进程。
• 由于该调度类用的是进程设置的三个调度参数（运行周期、运行时间、截至日期）作为调度依据，用不到优先级，为了和其余调度类有优先级之分，该类调度器的进程优先级被设为-1。
• 用于调度有严格时间要求的实时进程，如视频编码等。
• 也遵循时间片轮转，当前进程在一个分配的时间片内未执行完，会从运行队列中删除，下一个运行周期开始的时候又添加进来。

rt_sched_class

• 实时调度器，为每个优先级维护一个队列，属于软实时，适用于只要可运行就希望立马能运行的进程。
• 优先级为0～99，数字越大优先级越高。
• 实时调度类分为两个调度策略：
     SCHED_RR: 时间片轮转，进程用完时间片后加入优先级对应运行队列的尾部，把优先级让给同优先级的其他进程。
     SCHED_FIFO：先进先出调度，没有时间片。没有更高优先级的情况下，只能等待主动让出CPU。

fair_sched_class

• 完全公平调度器，采用完全公平调度算法，引入虚拟运行时间概念。给普通进程使用。优先级为100～139.该调度类包含两种调度策略：
     SCHED_NORMAL：使进程选择CFS调度器来调度运行
     SCHED_BATCH：批量处理，希望减少调度次数，每次调度能执行的时间长点。

idle_sched_class

• 空闲调度器，每个CPU都会有一个idle线程，当没有其他进程可以调度时，调度运行idle线程。
• 在内核启动的时候就创建了每个cpu的idle线程（即0号线程），属于最低优先级的线程。
• 调度策略：
     SCHED_IDLE：优先级特别低的进程，能分到的cpu时间比例很低，但也总能分到。