点击左上方蓝色“一口Linux”，选择“设为星标”
本文档基于linux3.14 ，linux内核调度详解
定义位于
linux/include/uapi/linux/sched.h中
#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE 5
#define SCHED_DEADLINE 6SCHED_NORMAL：普通的分时进程，使用的fair_sched_class调度类
SCHED_FIFO：先进先出的实时进程。当调用程序把CPU分配给进程的时候，它把该进程描述符保留在运行队列链表的当前位置。此调度策略的进程一旦使用CPU则一直运行。如果没有其他可运行的更高优先级实时进程，进程就继续使用CPU，想用多久就用多久，即使还有其他具有相同优先级的实时进程处于可运行状态。使用的是rt_sched_class调度类。
SCHED_RR：时间片轮转的实时进程。当调度程序把CPU分配给进程的时候，它把该进程的描述符放在运行队列链表的末尾。这种策略保证对所有具有相同优先级的SCHED_RR实时进程进行公平分配CPU时间，使用的rt_sched_class调度类
SCHED_BATCH：是SCHED_NORMAL的分化版本。采用分时策略，根据动态优先级，分配CPU资源。在有实时进程的时候，实时进程优先调度。但针对吞吐量优化，除了不能抢占外与常规进程一样，允许任务运行更长时间，更好使用高速缓存，适合于成批处理的工作，使用的fair_shed_class调度类
SCHED_IDLE：优先级最低，在系统空闲时运行，使用的是idle_sched_class调度类，给0号进程使用
SCHED_DEADLINE：新支持的实时进程调度策略，针对突发型计算，并且对延迟和完成时间敏感的任务使用，基于EDF（earliest deadline first）,使用的是dl_sched_class调度类。
定义调度类struct sched class
struct sched_class {
const struct sched_class *next;
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
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
int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
void (*migrate_task_rq)(struct task_struct *p, int next_cpu);
void (*pre_schedule) (struct rq *this_rq, struct task_struct *task);
void (*post_schedule) (struct rq *this_rq);
void (*task_waking) (struct task_struct *task);
void (*task_woken) (struct rq *this_rq, struct task_struct *task);
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 (*set_curr_task) (struct rq *rq);
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);
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);
#ifdef CONFIG_FAIR_GROUP_SCHED
void (*task_move_group) (struct task_struct *p, int on_rq);
#endif
};Next:指向下一个调度类,用于在函数pick_next_task、check_preempt_curr、set_rq_online、set_rq_offline用于遍历整个调度类根据调度类的优先级选择调度类。优先级为stop_sched_class->dl_sched_class->rt_sched_class->fair_sched_class->idle_sc*hed_class
enqueue_task:将任务加入到调度类中
dequeue_task:将任务从调度类中移除
yield_task/ yield_to_task:主动放弃CPU
check_preempt_curr:检查当前进程是否可被强占
pick_next_task:从调度类中选出下一个要运行的进程
put_prev_task:将进程放回到调度类中
select_task_rq:为进程选择一个合适的cpu的运行队列
migrate_task_rq:迁移到另外的cpu运行队列
pre_schedule:调度以前调用
post_schedule:通知调度器完成切换
task_waking、task_woken:用于进程唤醒
set_cpus_allowed:修改进程cpu亲和力affinity
rq_online:启动运行队列
rq_offline:关闭运行队列
set_curr_task:当进程改变调度类或者进程组时被调用
task_tick:将会引起进程切换，驱动运行running强占。由time_tick调用
task_fork:进程创建时调用，不同调度策略的进程初始化不一样
task_dead:进程结束时调用
switched_from、switched_to:进程改变调度器时使用
prio_changed:改变进程优先级
调度的触发主要有两种方式，一种是本地定时中断触发调用scheduler_tick函数，然后使用当前运行进程的调度类中的task_tick，另外一种则是主动调用schedule，不管是哪一种最终都会调用到__schedule函数，该函数调用pick_netx_task，通过rq->nr_running ==rq->cfs.h_nr_running判断出如果当前运行队列中的进程都在cfs调度器中，则直接调用cfs的调度类（内核代码里面这一判断使用了likely说明大部分情况都是满足该条件的）。如果运行队列不都在cfs中，则通过优先级stop_sched_class->dl_sched_class->rt_sched_class->fair_sched_class->idle_sched_class遍历选出下一个需要运行的进程。然后进程任务切换。
处于TASK_RUNNING状态的进程才会被进程调度器选择，其他状态不会进入调度器。系统发生调度的时机如下：
à调用cond_resched()时
à显式调用schedule()时
à从中断上下文返回时
当内核开启抢占时，会多出几个调度时机如下：
à在系统调用或者中断上下文中调用preemt_enable()时（多次调用系统只会在最后一次调用时会调度）
à在中断上下文中，从中断处理函数返回到可抢占的上下文时
分析_schedule的实现有利于理解调度类的实体如果在
static void __sched __schedule(void)
{
struct task_struct *prev, *next;
unsigned long *switch_count;
struct rq *rq;
int cpu;
need_resched:
/*关闭抢占*/
preempt_disable();
/*获取当前CPU*/
cpu = smp_processor_id();
/*取得当前cpu的运行队列rq*/
rq = cpu_rq(cpu);
/*更新全局状态，标识当前CPU发生上下文切换*/
rcu_note_context_switch(cpu);
prev = rq->curr; /*当前运行的进程存入Prev中*/
schedule_debug(prev);
if (sched_feat(HRTICK)) //取消为当前进程运行的hrtimer
hrtick_clear(rq);
/*
* Make sure that signal_pending_state()->signal_pending() below
* can't be reordered with __set_current_state(TASK_INTERRUPTIBLE)
* done by the caller to avoid the race with signal_wake_up().
*/
smp_mb__before_spinlock(); //内存屏障
raw_spin_lock_irq(&rq->lock); //上锁该队列
switch_count = &prev->nivcsw; //记录当前进程切换次数
if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) { //当前进程非运行状态，并且非内核抢占
if (unlikely(signal_pending_state(prev->state, prev))) { //当前进程有信号待处理，设置进程为就绪态
prev->state = TASK_RUNNING; //设置为RUNNING
} else {
deactivate_task(rq, prev, DEQUEUE_SLEEP); //将其从队列中删除
prev->on_rq = 0; //将在运行队列中变量置为0
/*
* If a worker went to sleep, notify and ask workqueue
* whether it wants to wake up a task to maintain
* concurrency.
*/
if (prev->flags & PF_WQ_WORKER) { //判断是否是工作队列进程
struct task_struct *to_wakeup;
to_wakeup = wq_worker_sleeping(prev, cpu); //如果有工作队列进程唤醒则尝试唤醒
if (to_wakeup)
try_to_wake_up_local(to_wakeup);
}
}
switch_count = &prev->nvcsw;
}
pre_schedule(rq, prev); //通知调度器，即将发生进程切换
if (unlikely(!rq->nr_running))
idle_balance(cpu, rq);
put_prev_task(rq, prev); //通知调度器，即将用另一个进程替换当前进程
next = pick_next_task(rq); //挑选一个优先级高的任务，使用调度类的方法
clear_tsk_need_resched(prev); //清空TIF_NEED_RESCHED标志
clear_preempt_need_resched(); //清空PREEMPT_NEED_RESCHED标志
rq->skip_clock_update = 0;
if (likely(prev != next)) { //如果如果选出的进程和当前进程不是同一个进程
rq->nr_switches++; //队列切换次数更新
rq->curr = next; //将当前进程换成刚才挑选的进程
++*switch_count; //进程切换次数更新
context_switch(rq, prev, next); /* unlocks the rq */ /*进程上下文切换 */
/*
* The context switch have flipped the stack from under us
* and restored the local variables which were saved when
* this task called schedule() in the past. prev == current
* is still correct, but it can be moved to another cpu/rq.
*/
/*上下文切换以后当前运行CPU也可能会改变，需要从新获取当前运行进程的运行队列*/
cpu = smp_processor_id();
rq = cpu_rq(cpu);
} else
raw_spin_unlock_irq(&rq->lock); //解锁该队列
post_schedule(rq); //通知调度器，完成了进程切换
sched_preempt_enable_no_resched(); //开启内核抢占
if (need_resched()) //如果该进程被其他进程设置了TIF_NEED_RESCHED,则需要重新调度
goto need_resched;
}其中有几个重要的与调度器密切相关的函数：
pre_scheduleà prev->sched_class->pre_schedule 在调度以前调用
put_prev_taskàprev->sched_class->put_prev_task 将前一个进程调度以前放回调度器中
pick_next_taskà class->pick_next_task从调度器中选出下一个需要运行的进程
post_scheduleà rq->curr->sched_class->post_scheduleCFS中为NULL
该部分代码位于linux/kernel/sched/fair.c中
定义了const struct
sched_classfair_sched_class，这个是CFS的调度类定义的对象。其中基本包含了CFS调度的所有实现。
CFS实现三个调度策略：
1> SCHED_NORMAL这个调度策略是被常规任务使用
2> SCHED_BATCH 这个策略不像常规的任务那样频繁的抢占，以牺牲交互性为代价下，因而允许任务运行更长的时间以更好的利用缓存，这种策略适合批处理
3> SCHED_IDLE 这是nice值甚至比19还弱，但是为了避免陷入优先级导致问题，这个问题将会死锁这个调度器，因而这不是一个真正空闲定时调度器
CFS调度类：
n enqueue_task(…) 当任务进入runnable状态，这个回调将把这个任务的调度实体（entity）放入红黑树并且增加nr_running变量的值
n dequeue_task(…) 当任务不再是runnable状态，这个回调将会把这个任务的调度实体从红黑树中取出，并且减少nr_running变量的值
n yield_task(…) 除非compat_yield sysctl是打开的，这个回调函数基本上就是一个dequeue后跟一个enqueue，这那种情况下，他将任务的调度实体放入红黑树的最右端
n check_preempt_curr(…) 这个回调函数是检查一个任务进入runnable状态是否应该抢占当前运行的任务
n pick_next_task(…) 这个回调函数选出下一个最合适运行的任务
n set_curr_task(…) 当任务改变他的调度类或者改变他的任务组，将调用该回调函数
n task_tick(…) 这个回调函数大多数是被time tick调用。他可能引起进程切换。这就驱动了运行时抢占
/*
一个调度实体（红黑树的一个节点），其包含一组或一个指定的进程，包含一个自己的运行队列，一个父亲指针，一个指向需要调度的队列
*/
struct sched_entity {
/*权重，在数组prio_to_weight[]包含优先级转权重的数值*/
struct load_weight load; /* for load-balancing */
/*实体在红黑树对应的节点信息*/
struct rb_node run_node;
/*实体所在的进程组*/
struct list_head group_node;
/*实体是否处于红黑树运行队列中*/
unsigned int on_rq;
/*开始运行时间*/
u64 exec_start;
/*总运行时间*/
u64 sum_exec_runtime;
/*
虚拟运行时间，在时间中断或者任务状态发生改变时会更新
其会不停的增长，增长速度与load权重成反比，load越高，增长速度越慢，就越可能处于红黑树最左边被调度
每次时钟中断都会修改其值
具体见calc_delta_fair()函数
*/
u64 vruntime;
/*进程在切换进cpu时的sum_exec_runtime值*/
u64 prev_sum_exec_runtime;
/*此调度实体中进程移到其他cpu组的数量*/
u64 nr_migrations;
#ifdef CONFIG_SCHEDSTATS
/*用于统计一些数据*/
struct sched_statistics statistics;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
/*
父亲调度实体指针，如果是进程则指向其运行队列的调度实体，如果是进程组则指向其上一个进程组的调度实体
在set_task_rq函数中设置
*/
struct sched_entity *parent;
/* rq on which this entity is (to be) queued: */
/*实体所处红黑树运行队列*/
struct cfs_rq *cfs_rq;
/* rq "owned" by this entity/group: */
/*实体的红黑树运行队列，如果为NULL表明其是一个进程，若非NULL表明其是调度组*/
struct cfs_rq *my_q;
#endif
#ifdef CONFIG_SMP
/* Per-entity load-tracking */
struct sched_avg avg;
#endif
};其中几个重要的变量
字段 | 描述 |
load | 指定了权重, 决定了各个实体占队列总负荷的比重, 计算负荷权重是调度器的一项重任, 因为CFS所需的虚拟时钟的速度最终依赖于负荷, 权重通过优先级转换而成，是vruntime计算的关键 |
Run_node | 调度实体在红黑树对应的结点信息, 使得调度实体可以在红黑树上排序 |
Sum_exec_runtime | 记录程序运行所消耗的CPU时间, 以用于完全公平调度器CFS |
On_rq | 调度实体是否在就绪队列上接受检查, 表明是否处于CFS红黑树运行队列中，需要明确一个观点就是，CFS运行队列里面包含有一个红黑树，但这个红黑树并不是CFS运行队列的全部，因为红黑树仅仅是用于选择出下一个调度程序的算法。很简单的一个例子，普通程序运行时，其并不在红黑树中，但是还是处于CFS运行队列中，其on_rq为真。只有准备退出、即将睡眠等待和转为实时进程的进程其CFS运行队列的on_rq为假 |
vruntime | 虚拟运行时间，调度的关键，其计算公式：一次调度间隔的虚拟运行时间 = 实际运行时间 * (NICE_0_LOAD / 权重)。可以看出跟实际运行时间和权重有关，红黑树就是以此作为排序的标准，优先级越高的进程在运行时其vruntime增长的越慢，其可运行时间相对就长，而且也越有可能处于红黑树的最左结点，调度器每次都选择最左边的结点为下一个调度进程。注意其值为单调递增，在每个调度器的时钟中断时当前进程的虚拟运行时间都会累加。单纯的说就是进程们都在比谁的vruntime最小，最小的将被调度 |
Cfs_rq | 此调度实体所处于的CFS运行队列 |
My_q | 如果此调度实体代表的是一个进程组，那么此调度实体就包含有一个自己的CFS运行队列，其CFS运行队列中存放的是此进程组中的进程，这些进程就不会在其他CFS运行队列的红黑树中被包含(包括顶层红黑树也不会包含他们，他们只属于这个进程组的红黑树) |
Sum_exec_runtime |
|
每一个进程的task_struct中都嵌入了sched_entry对象，所以进程是可调度的实体，但是可调度的实体不一定是进程，也可能是进程组。
Tcik 中断，主要会更新调度信息，然后调整当前进程在红黑树中的位置。调整完成以后如果当前进程不再是最左边的叶子，就标记为Need_resched标志，中断返回时就会调用scheduler()完成切换、否则当前进程继续占用CPU。从这里可以看出CFS抛弃了传统时间片概念。Tick中断只需要更新红黑树。
红黑树键值即为vruntime，该值通过调用update_curr函数进行更新。这个值为64位的变量，会一直递增，__enqueue_entity中会将vruntime作为键值将要入队的实体插入到红黑树中。__pick_first_entity会将红黑树中最左侧即vruntime最小的实体取出。
end
一口Linux
关注，回复【1024】海量Linux资料赠送
精彩文章合集
文章推荐
