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

　　1、概述

　　1.1、调度策略

　　定义位于

　　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、调度类

　　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的实现有利于理解调度类的实体如果在

　　其中有几个重要的与调度器密切相关的函数：

　　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、调度实体

　　其中几个重要的变量

　　每一个进程的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最小的实体取出。

　　更多信息可以来这里获取==>>电子技术应用-AET<<