本文档基于linux3.14 ，linux内核调度详解

1、概述

1.1、调度策略

定义位于
linux/include/uapi/linux/sched.h中

#define SCHED_NORMAL0
#define SCHED_FIFO1
#define SCHED_RR2
#define SCHED_BATCH3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE5
#define SCHED_DEADLINE6

SCHED_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调度类。

1.2、调度类

定义调度类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:改变进程优先级

1.3、调度触发

调度的触发主要有两种方式，一种是本地定时中断触发调用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()时（多次调用系统只会在最后一次调用时会调度）

à在中断上下文中，从中断处理函数返回到可抢占的上下文时

1.4、__schedule的实现

分析_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

2、 CFS调度

该部分代码位于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调用。他可能引起进程切换。这就驱动了运行时抢占

2.1、调度实体

/*
一个调度实体（红黑树的一个节点），其包含一组或一个指定的进程，包含一个自己的运行队列，一个父亲指针，一个指向需要调度的队列
*/
struct sched_entity {
   /*权重，在数组prio_to_weight[]包含优先级转权重的数值*/
struct load_weightload;/* for load-balancing */
   /*实体在红黑树对应的节点信息*/
struct rb_noderun_node;
   /*实体所在的进程组*/
struct list_headgroup_node;
   /*实体是否处于红黑树运行队列中*/
unsigned inton_rq;
 
    /*开始运行时间*/
u64exec_start;
    /*总运行时间*/
u64sum_exec_runtime;
    /*
    虚拟运行时间，在时间中断或者任务状态发生改变时会更新
    其会不停的增长，增长速度与load权重成反比，load越高，增长速度越慢，就越可能处于红黑树最左边被调度
    每次时钟中断都会修改其值
    具体见calc_delta_fair()函数
    */
u64vruntime;
    /*进程在切换进cpu时的sum_exec_runtime值*/
u64prev_sum_exec_runtime;
    /*此调度实体中进程移到其他cpu组的数量*/
u64nr_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_avgavg;
#endif
};

其中几个重要的变量

每一个进程的task_struct中都嵌入了sched_entry对象，所以进程是可调度的实体，但是可调度的实体不一定是进程，也可能是进程组。

2.2、CFS调度

Tcik 中断，主要会更新调度信息，然后调整当前进程在红黑树中的位置。调整完成以后如果当前进程不再是最左边的叶子，就标记为Need_resched标志，中断返回时就会调用scheduler()完成切换、否则当前进程继续占用CPU。从这里可以看出CFS抛弃了传统时间片概念。Tick中断只需要更新红黑树。

红黑树键值即为vruntime，该值通过调用update_curr函数进行更新。这个值为64位的变量，会一直递增，__enqueue_entity中会将vruntime作为键值将要入队的实体插入到红黑树中。__pick_first_entity会将红黑树中最左侧即vruntime最小的实体取出。