在架空模型中vruntime决定了经过被调度的先后顺序,在实际模型中决定被调度的先后顺序的参数是由函数entity_key决定的。 
 
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct
sched_entity *se)
{
    return se->vruntime – cfs_rq->min_vruntime;
}
enqueue_task_fair—->enqueue_entity—->__enqueue_entity—->entity_key决定插入就绪队列的地方。

一、概述

本篇来探讨下cgroup对cpu的限量机制,前文提到过cgroup也是经过进程调度子系统来完毕限制cpu的目标,因而须求驾驭下进程调度子系统.

全盘公平调度CFS

CFS(Completely Fair Scheduler)试图根据对 CPU 时间的 “最大必要(gravest
need)” 运行职分;这有助于保证每个进程可以得到对 CPU 的公道共享。

万般进度分为40个等级,每个阶段对应一个权重值,权重值用一个平头来标示。权重值定义在数组prio_to_weight[40]中;普通进度的权重值最大为88761,最小为15。默许情况下,普通进度的权重值为1024(由NICE_0_LOAD指定)。weight是由进程的静态优先级static_prio决定的,静态优先级越高(static_prio值越小)weight值越大。普通进程的默认nice值为0,即默许静态优先级为120,它的weight值为prio_to_weight[20],即1024。因此NICE_0_LOAD的值就
为1024。

先是简介一下非同儿戏的统筹思路,
CFS思路非凡easy。就是基于各样进度的权重分配执行时间(权重怎么来的背后再说)。
经过的履行时间计算公式为:
分配给进程的施行时间 = 调度周期 * 进程权重 / 全部经过权重之和  
(公式1)
调度周期极度好精通。就是将一切地处TASK_RUNNING态进度都调度三遍的大运,
大概一样相当于O(1)调度算法中推行队列和过期队列切换一遍的时间
(我对O(1)调度算法看得不是相当熟,如有错误还望各位大虾提出)。
举个样例。比方仅仅有七个进度A, B,权重分别为1和2,
调度周期设为30ms,那么分配给A的CPU时间为
30ms * (1/(1+2)) = 10ms
而B的CPU时间为
 
30ms * (2/(1+2)) = 20ms
那就是说在那30ms中A将进行10ms。B将进行20ms。
相提并论怎么呈现吗?它们的执行时间并不同阿?
骨子里公平是体近来此外一个量地点。叫做virtual
runtime(vruntime)。它记录着进度已经施行的岁月,
然则并非直接记录,而是要按照进度的权重将推行时间放大或者减少一个百分比。
俺们来看下从事实上执行时间到vruntime的折算公式
vruntime = 实际执行时间 * 1024 / 进度权重。 (公式2)
为了不把大家搞晕。那里自己直接写1024。实际上它等于nice为0的历程的权重,代码中是NICE_0_LOAD。
也就是说。全部经过都以nice为0的进度的权重1024用作条件。总结自己的vruntime添加速度。
还以上边AB多少个进度为例。B的权重是A的2倍,那么B的vruntime添加快度唯有有A的一半。

因为是介绍cgroup的篇章,因而只介绍进度调度中与cgroup密切关联的一部分,详细已毕的经过调度完毕可参照进度调度的连带资料.

CFS初探

CFS
调度程序行使安抚(appeasement)策略确保公平性。当某个任务进入运行队列后,将记录当前时光,当某个进度等待
CPU
时,将对这一个历程的 wait_runtime 值加一个数,这么些数取决于运行队列当前的长河数。当执行那一个统计时,也将考虑不一致义务的先期级值。
将以此义务调度到 CPU
后,它的 wait_runtime 值开端递减,当以此值递减到其余职分成为红黑树的最左侧职务时,当前义务将被侵吞。通过那种措施,CFS
努力落到实处一种理想 状态,即 wait_runtime 值为 0!

CFS
维护任务运行时(相对于运行队列级时钟,称为 fair_clock(cfs_rq->fair_clock)),它在某个实际时间的有的内运行,由此,对于单个职务可以依据优质的速度运行。

譬如说,假若具有 4
个可运行的职分,那么 fair_clock 将按照实际时间进度的四分之一日增。每个任务将设法跟上那个速度。这是由分时多职务处理的量子化特性决定的。也就是说,在别的一个时光段内唯有一个任务可以运作;因而,
其余进度在时间上的亏欠将增大(wait_runtime)。因而,一旦某个义务进入调度,它将全力赶上它所欠下的小时(并且要比所欠时间多一些,因为在追赶时间之间,fair_clock 不会停下计时)。

粒度和推迟怎么样关联?

事关粒度和延期的简便等式为: 

gran = (lat/nr) – (lat/nr/nr)

其中 gran = 粒度,

lat = 延迟,而 

nr = 运行中的职务数。

加权职务引入了先期级。假如我们有五个职责:其中一个义务占用 CPU
的时间量是另一个任务的两倍,比例为 2:1。执行数学转换后,对于权重为 0.5
的天职,时间流逝的进度是原先的两倍。我们根据 fair_clock 对树进行排队。

请留意,CFS 没有动用时间片(time slices),至少,没有先行使用。CFS
中的时间片有着可变的尺寸并且动态确定。

vruntime行走速度:
   
系统确定:默认权重值(1024)对应的进度的vruntime行走时间与实际运作时刻runtime是1:1的关联。由于vruntime的行进速度和权重值成反比,那么任何进度的vruntime行走速度都由此以下五个参数统计得到:1、该进程的权重值2、默许进程的权重值。
    例如权重为3096的历程的vruntime行走速度为:1024/3096 * (wall
clock)。
    “真实时钟速度”即为runtime(即 wall clock)行走的进度。

现行大家把公式2中的实际施行时间用公式1来替换。可以赢得那样一个结果:
vruntime = (调度周期 * 进程权重 /
全体进度总权重) * 1024 / 进度权重=调度周期 * 1024 / 全体进程总权重
探望哪些模样没有?没错,尽管经过的权重差异,不过它们的vruntime拉长速度应该是一模一样的(这里所说的增加速度一样,是从宏观上来看的。从上一篇小说能够看出来。而在上一篇小说中说vruntime的增量差别,是从公式分析获得的,算是局地分析,在公式2中,如若实际施行时间都是一样。格外通晓权重小的进步的多。权紧要的增高的小,我个人觉得正是虚拟时钟的留存。转换了思维。才有了这么些CFS,事实上仍然基于权重来决定一个历程在一个调用周期内举行了多久,然则虚拟时钟决定了怎么调度这一个进程,那就是思想),与权重非亲非故。
好,既然全体历程的vruntime拉长速度宏观上看应该是一律时候推进的。
那就是说就可见用这一个vruntime来挑选执行的进度。哪个人的vruntime值较小就证实它已经占用cpu的年华较短,
遇到了“有失公正”对待,由此下一个推行进度就是它。

本文分为多个部分,首先介绍进度调度中的调度算法,在该基础上引入组调度,最终结合前面小说(cgroup原理简析:vfs文件系统)来表明上层通过echo
pid >> tasks, echo n >
cpu.shares等操作影响调度器对经过的调度,从而决定进程对cpu的行使,(内核源码版本3.10)

运行时调优选项

引入了重点的 sysctls 来在运行时对调度程序开展调优(以 ns 结尾的称号以阿秒为单位):

sched_latency_ns:针对 CPU 密集型任务进行目的抢占延迟(Targeted
preemption latency)。

sched_batch_wakeup_granularity_ns:针对 SCHED_BATCH 的唤醒(Wake-up)粒度。

sched_wakeup_granularity_ns:针对 SCHED_OTHER 的唤醒粒度。

sched_compat_yield:由于 CFS
举行了转移,严重信赖 sched_yield() 的作为的应用程序可以要求差别的习性,由此推荐启用 sysctls。

sched_child_runs_first:child
在 fork 之后展开调度;此为默许设置。倘诺设置为 0,那么先调度 parent。

sched_min_granularity_ns:针对 CPU 密集型职责执行最低级别抢占粒度。

sched_features:包蕴各个与调节相关的特性的信息。

sched_stat_granularity_ns:收集调度程序总计信息的粒度。

澳门金沙国际 1

系统中运行时参数的典型值

   
进程执行实施时期周期性调度器周期性地启动,其负责更新一些巢倾卵破数据,并不担负进程之间的切换:
   
timer_tick()—->update_process_times—->schedule_tick()
   
schedule_tick—->task_tick_fair—->entity_tick()—->update_curr()
    update_curr()函数完结相关数据的立异。
        update_curr()—->delta_exec = (unsigned long)(now –
curr->exec_start)
                              |–>__update_curr()
                              |–>curr_exec_start = now;
   
update_curr()函数只负责总结delta_exec以及更新exec_start。别的工作由__update_curr()函数达成:
        1、更新当前历程的实际上运作时刻(抽象模型中的runtime)。
        2、更新当前经过的虚拟时间vruntime。
        3、更新cfs_rq->min_vruntime。
          
在时下经过和下一个就要被调度的长河中挑选vruntime较小的值。然后用该值和cfs_rq->min_vruntime比较,如果比min_vruntime大,则更新cfs_rq为的min_vruntime为所求出的值。

如此那般既能公平选用经过,又能确保高优先级进程
收获较多的执行时间。
那就是CFS的要紧思想了。


新的调度程序调试接口

新调度程序附带了一个万分棒的调节接口,还提供了运行时计算音信,分别在
kernel/sched_debug.c 和 kernel/sched_stats.h
中贯彻。要提供调度程序的运行时信息和调试新闻,必要将一部分文件添加到 proc
pseudo 文件系统:

/proc/sched_debug:展现运行时调度程序可调优选项的此时此刻值、CFS
统计音信和持有可用 CPU 的运行队列信息。当读取那么些 proc
文件时,将调用 sched_debug_show() 函数并在 sched_debug.c 中定义。

/proc/schedstat:为具有有关的 CPU 彰显特定于运作队列的总结新闻以及 SMP
系统中一定于域的统计音信。kernel/sched_stats.h
中定义的 show_schedstat() 函数将处理 proc 条目中的读操作。

/proc/[PID]/sched:突显与连锁调度实体有关的新闻。在读取那一个文件时,将调用
kernel/sched_debug.c 中定义的 proc_sched_show_task() 函数

考虑下当创立新进程或者经过唤醒时,vruntime在真正模型中的处理形式:
I、新建进度
   
进程的ideal_time长度和weight成正比,vruntime行走速度与weight值成反比。由此当每个进度在period时间内,都履行了友好相应的ideal_time长时间,那么他们的vruntime的增量相等。而nice为0的经过的vruntime行走速度等于runtime行走速度,所以每个进程都运作它自己相应的ideal_runtime时间,别的进度的vruntime增量都非常nice值为0的经过的ideal_runtime。要是开头景况下,它们的有着进程的vruntime值都等于0,那么当一个经过运行完runtime的岁月为ideal_time,那么它的vruntime将为最大,只要任何进度的运作总时间尚未达成各自对应的ideal_runtime值,那么它平昔排在进度队列的终极。

再补充一下权重的来源,权重跟进度nice值之间有各种相应的关系,可以透过全局数组prio_to_weight来转换,
nice值越大,权重越低

1.经过调度

CFS内部原理

Linux 内的富有职责都由称为 task_struct
的天职结构意味着。该社团(以及任何连锁内容)完整地叙述了职分并包涵了职务的眼前情状、其堆栈、进度标识、优先级(静态和动态)等等。可以在
./linux/include/linux/sched.h 中找到这一个内容以及相关社团。
不过因为不是负有职分都是可运行的,在 task_struct 中不会发觉其余与 CFS
相关的字段。 相反,会创制一个名为 sched_entity 的新社团来跟踪调度音信。

澳门金沙国际 2

职责和红黑树的布局层次关系

树的根通过 rb_root 元素通过 cfs_rq 结构(在 ./kernel/sched.c
中)引用。红黑树的纸牌不含有新闻,不过里面节点代表一个或多少个可运行的职分。红黑树的各个节点都由
rb_node 表示,它只包蕴子引用和父对象的颜料。 rb_node 包含在
sched_entity
结构中,该协会包蕴rb_node引用、负载权重以及各个计算数据。最首要的是,sched_entity
包涵 vruntime(64 位字段),它表示义务运行的时间量,并作为红黑树的目录。
最终,task_struct 位于顶端,它完整地叙述任务并包涵 sched_entity 结构。

就 CFS 部分而言,调度函数至极不难。 在 ./kernel/sched.c 中,通用
schedule() 函数,它会先抢占当前运行义务(除非它经过 yield()
代码先抢占自己)。注意 CFS
没有当真的时光切片概念用于抢占,因为抢占时间是可变的。当前运行义务(现在被并吞的职分)通过对
put_prev_task
调用(通过调度类)再次回到到红黑树。当schedule函数初步确定下一个要调度的职分时,它会调用
pick_next_task函数。此函数也是通用的(在./kernel/sched.c
中),但它会经过调度器类调用 CFS 调度器。

CFS调度算法的中坚是选项具有最小vruntine的职责。运行队列接纳红黑树情势存放,其中节点的键值便是可运行进程的虚拟运行时刻。CFS调度器选用待运行的下一个历程,是独具进程中vruntime最小的非凡,他对应的便是在树中最左侧的叶子节点。完结采取的函数为pick_next_task_fair,CFS
中的 pick_next_task 函数可以在
./kernel/sched_fair.c(称为pick_next_task_fair())中找到。
此函数只是从红黑树中收获最左端的任务并重回相关sched_entity。通过此引用,一个粗略的
task_of()调用确定重返的task_struct
引用。通用调度器最终为此任务提供处理器。

static struct task_struct *pick_next_task_fair(struct rq *rq)

{

struct task_struct *p;

struct cfs_rq *cfs_rq = &rq->cfs;

struct sched_entity *se;

if (unlikely(!cfs_rq->nr_running))

return NULL;

do {/*此循环为了考虑组调度*/

se = pick_next_entity(cfs_rq);

set_next_entity(cfs_rq, se);/*安装为近期运行进度*/

cfs_rq = group_cfs_rq(se);

} while (cfs_rq);

p = task_of(se);

hrtick_start_fair(rq, p);

return p;

}

精神工作调用__pick_next_entity完成。

/*函数本身并不会遍历数找到最左叶子节点(即就是具有进度中vruntime最小的卓殊),因为该值已经缓存在rb_leftmost字段中*/

static struct sched_entity *__pick_next_entity(struct cfs_rq
*cfs_rq)

{

/*rb_leftmost为保留的红黑树的最右边的节点*/

struct rb_node *left = cfs_rq->rb_leftmost;

if (!left)

return NULL;

return rb_entry(left, struct sched_entity, run_node);

}

    对于新历程,task_fork_fair()->place_entity(cfs_rq, se,
1),其intial参数为1。新历程的vruntime值被设置为min_vruntime+sched_vslice(cfs_rq,
se),
sched_vslice()函数可计算出nice值为0的经过的ideal_runtime。其作用是将新加盟的长河的记号为“它在period长日子内一度运行它对应的ideal_time长期”,那么新加盟进程在答辩上(所有进度都施行它对应的ideal_runtime时间,没有暴发睡眠、进程终止等特殊情形)唯有拭目以待period之后才能被调度。
    sched_vslice(cfs_rq,
se)—->calc_delta_fair(sched_slice(cfs_rq, se), se),
sched_slice()统计新建进度的ideal_runtime,calc_delta_fair()将ideal_runtime转换成vruntime。

以下来分析代码。网上一度有相当多cfs的稿子。由此我打算换一个措施来写,接纳多少个点来开展情景分析,
包含进度创制时。进度被唤醒,主动调度(schedule),时钟中断。

大家领会linux下的进度会有种种状态,已就绪状态的进度在就绪队列中(struct
rq),当cpu须求加载新职务时,调度器会从稳妥队列中拔取一个最优的历程加载执行.

重大的 CFS 数据结构

对此每个 CPU,CFS 使用按时间排序的红黑(red-black)树。

红黑树是一种自平衡二叉搜索树,那种数据结构可用于落成关周详组。对于每个运行中的进度,在红黑树上都有一个节点。红黑树上位于最左侧的进程表示将拓展下一次调度的经过。红黑树相比较复杂,但它的操作具有优异的最差情形(worst-case)运行时,并且在实际操作中充足迅猛:它可以在 O(log
n)
 时间内搜寻、插入和删除
,其中 n 表示树元素的多寡。叶节点意义不大并且不带有数据。为节本省存,有时利用单个哨兵(sentinel)节点执行所有叶节点的角色。内部节点到叶节点的拥有引用都针对哨兵节点。

该树方法可以卓绝运转的来由在于:

1.红黑树可以一直维持平衡。

2.是因为红黑树是二叉树,查找操作的时日复杂度为对数。可是,除了最左边查找以外,很难执行此外查找,并且最左边的节点指针始终被缓存。

3.对此半数以上操作,红黑树的履行时间为 O(log
n)
,而之前的调度程序通过所有稳定优先级的事先级数组使用 O(1)O(log
n)
 行为具备可测量的延迟,可是对于较大的天职数非亲非故首要。Molnar
在品味那种树方法时,首先对那一点展开了测试。

4.红黑树可因而内部存储已毕 —
即不须要动用外部分配即可对数据结构举行有限协助。

让我们精晓一下落到实处这种新调度程序的部分重点数据结构。

II、睡眠进度被提醒
   
将经过的vruntime值设置为cfs_rq->min_vruntime值,然后再展开一下补偿:将vruntime减去与sysctl_sched_latencyd相关的一个数值。进度进入睡眠景况时cfs_rq->min_vruntime就不止或等于该进度的vruntime值,它在睡觉过程中vruntime值是不改动的,不过cfs_rq->min_vruntime的值却是单调增添的,进度醒来后补充的量由sysctl_sched_latency给出,不管进度遭到的有失公平待遇大仍旧小,一律只补充这么多。

介绍代码之前先介绍一下CFS相关的布局
率先个是调度实体sched_entity,它意味着一个调度单位。在组调度关闭的时候可以把他等同为进度。
每个task_struct中都有一个sched_entity,进度的vruntime和权重都保留在这一个布局中。
那就是说整个的sched_entity怎么协会在联名呢?红黑树。全部的sched_entity以vruntime为key
(实际上是以vruntime-min_vruntime为单位,难道是谨防溢出?反正结果是一样的)插入到红黑树中,
一致时候缓存树的最左側节点。也就是vruntime最小的节点,那样可以飞速选中vruntime最小的进程。
小心仅仅有等待CPU的就绪态进度在那棵树上,睡眠进度和正在推行的进程都不在树上。
我从ibm developer works上偷过来一张图来体现一下它们的关联:
汗。图片上传功效被关闭了。先盗链一个过来。别怪我没品哈。。。

那么调度器依据规则来选出这几个最优的长河呢?那又引出了经过优先级的定义,简单的话,linux将经过分为一般进度和实时进程八个大类,用一个数值范围0-139来代表优先级,值越小优先级越高,其中0-99意味着实时进程,100-139(对运用户层nice值-20-19)表示平时进程,实时进程的预先级总是凌驾一般进度.

struct task_struct 的变化

CFS 去掉了 struct prio_array,并引入调度实体(scheduling
entity)和调度类 (scheduling classes),分别由 struct
sched_entity 和 struct
sched_class 定义。因此,task_struct 包括关于 sched_entity 和 sched_class 那三种结构的新闻:

struct task_struct {

/* Defined in 2.6.23:/usr/include/linux/sched.h */….

–  struct prio_array *array;

+  struct sched_entity se;

+  struct sched_class *sched_class;  

 ….   ….

};

真正模型总括:
   
a)进度在就绪队列中用键值key来排序,它并未保留在其余变量中,而是在须要时由函数entity_key()计算得出。它分外
        key = task->vruntime – cfs_rq->min_vruntime
   
b)各类进度有例外的重点(优先等级),越主要的进程权重值weight(task.se.load.weight)越大。
   
c)每个进度vruntime行走的快慢和weight值成反比。权重值为1024(NICE_0_LOAD)的经过vruntime行走速度和runtime相同。
   
d)每个进度每一遍得到CPU使用权最多执行与该进度对应的ideal_runtime长期。该时间长短和weight值成正比,它没有用变量来保存,而是须求运用sched_slice()函数总结得出。
   
e)ideal_runtime总结的尺度是period,它也尚无用变量来保存,而是由__sched_period()计算得出。

 

今非昔比优先级档次的经过当然要运用不一样的调度策略,普通进度使用完全公平调度(cfs),实时进度使用实时调度(rt),那里根本完结上运用了一个好像面向对象的章程,抽象出一个调度类(struct
sched_class)评释同一的钩函数,完全公平调度实例(fair_sched_class)和实时调度实例(rt_sched_class)各自完毕那一个钩子.

struct sched_entity

运作实体结构为sched_entity,该社团包括了总体的新闻,用于落到实处对单个职责或义务组的调度。它可用于完结组调度。调度实体可能与经过没有涉及。所有的调度器都必须对进程运行时刻做记账。CFS不再有时间片的概念,可是她也不可能不保证每个进度运行的小运记账,因为他索要确保每个进程只在公正分配给她的电脑时间内运行。CFS使用调度器实体结构来最终运行记账。

澳门金沙国际 3

sched_entity 结构体简介

兑现记账功用,由系统定时器周期调用

static void update_curr(struct cfs_rq *cfs_rq)

{

struct sched_entity *curr = cfs_rq->curr;

u64 now = rq_of(cfs_rq)->clock;/*now计时器*/

unsigned long delta_exec;

if (unlikely(!curr))

return;

/*

* Get the amount of time the current task was running

* since the last time we changed load (this cannot

* overflow on 32 bits):

*/

/*赢得从最后一回修改负载后当前职分所占据的运作总时间*/

/*即总计当前进度的实践时间*/

delta_exec = (unsigned long)(now – curr->exec_start);

if (!delta_exec)/*倘若此次没有实施过,不用再行更新了*/

return;

/*根据近日可运行进程总数对运行时刻开展加权测算*/

__update_curr(cfs_rq, curr, delta_exec);

curr->exec_start = now;/*将exec_start属性置为now*/

if (entity_is_task(curr)) {/*上面为关于组调度的,暂时不分析了*/

struct task_struct *curtask = task_of(curr);

trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);

cpuacct_charge(curtask, delta_exec);

account_group_exec_runtime(curtask, delta_exec);

}

}

 

澳门金沙国际 4

对应的,就绪队列里也就分为多个子队列,一个保安普通进度,称之为cfs队列(cfs_rq),一个掩护实时进度,称之为rt队列(rt_rq).

struct sched_class

该调度类类似于一个模块链,支持内核调度程序工作。每个调度程序模块须要贯彻 struct
sched_class提议的一组函数。

澳门金沙国际 5

sched_class 结构体简介

函数作用表明:

enqueue_task:当某个任务进入可运行处境时,该函数将赢得调用。它将调度实体(进度)放入红黑树中,并对 nr_running 变量加
1。

dequeue_task:当某个任务退出可运行状态时调用该函数,它将从红黑树中去掉对应的调度实体,并从 nr_running 变量中减
1。

yield_task:在 compat_yield
sysctl 关闭的情况下,该函数实际上执行先出队后入队;在那种场馆下,它将调度实体放在红黑树的最右端。

check_preempt_curr:该函数将检查当前运行的职务是或不是被霸占。在实质上抢占正在运转的天职以前,CFS
调度程序模块将举行公平性测试。这将使得唤醒式(wakeup)抢占。

pick_next_task:该函数拔取接下去要运行的最合适的长河。

load_balance:每个调度程序模块完成四个函数,load_balance_start() 和load_balance_next(),使用那三个函数达成一个迭代器,在模块的 load_balance 例程中调用。内核调度程序采用那种艺术达成由调度模块管理的长河的负载平衡。

set_curr_task:当义务修改其调度类或改动其职务组时,将调用这几个函数。

task_tick:该函数经常调用自 time tick
函数;它恐怕引起进度切换。那将使得运行时(running)抢占。

task_new:内核调度程序为调度模块提供了管住新职务启动的机遇。CFS
调度模块使用它举行组调度,而用于实时职责的调度模块则不会选取那一个函数。

进程的先期等级控制了其权重值,task_struct中与先期级相关数据成员:
   
a)static_prio,指普通进度的静态优先级(实时进程没用该参数),值越小则优先级越高。静态优先级是经过启动时分配的预先级。它可以用nice()或者sched_setscheduler()系统调用更改,否则在运行时期一向维持一定。

 

其余,固然调度器最后调度的靶子是经过,但在此间用一个调度实体(struct
sched_linux内核CFS进程调度策略,CPU调度种类二。entity||struct sched_rt_entity)表示一个要被调度的对象.
对此一般的历程调度来说,一个调度实体对象内嵌在task_struct中,对于组调度(cgroup)来说,其内嵌在task_group中.

运转队列中CFS 有关的字段

对此每个运行队列,都提供了一种结构来保存有关红黑树的音讯。

struct cfs_rq {

struct load_weight load;/*运作负载*/

unsigned long nr_running;/*运转过程个数*/

u64 exec_clock;

u64 min_vruntime;/*保留的细小运行时刻*/

struct rb_root tasks_timeline;/*运行队列树根*/

struct rb_node *rb_leftmost;/*保留的红黑树最左侧的

节点,这么些为最小运行时刻的节点,当进度

选用下一个来运行时,间接选拔那个*/

struct list_head tasks;

struct list_head *balance_iterator;

/*

* ‘curr’ points to currently running entity on this cfs_rq.

* It is set to NULL otherwise (i.e when none are currently running).

*/

struct sched_entity *curr, *next, *last;

unsigned int nr_spread_over;

#ifdef CONFIG_FAIR_GROUP_SCHED

struct rq *rq; /* cpu runqueue to which this cfs_rq is attached */

/*

* leaf cfs_rqs are those that hold tasks (lowest schedulable entity
in

* a hierarchy). Non-leaf lrqs hold other higher schedulable entities

* (like users, containers etc.)

*

* leaf_cfs_rq_list ties together list of leaf cfs_rq’s in a cpu.
This

* list is used during load balance.

*/

struct list_head leaf_cfs_rq_list;

struct task_group *tg; /* group that “owns” this runqueue */

#ifdef CONFIG_SMP

/*

* the part of load.weight contributed by tasks

*/

unsigned long task_weight;

/*

*  h_load = weight * f(tg)

*

* Where f(tg) is the recursive weight fraction assigned to

* this group.

*/

unsigned long h_load;

/*

* this cpu’s part of tg->shares

*/

unsigned long shares;

/*

* load.weight at the time we set shares

*/

澳门金沙国际,unsigned long rq_weight;

#endif

#endif

};

      
注意:关于a),注意本文的尾声添加的注释。

 

cfs队列用红黑树社团调度实体,cfs调度算法总是挑三拣四最右边的调度实体.

   
b)rt_priority,表示实时进程的优先级(普通进程没用该参数),它的值介于[0~99]之间。rt_priority的值越大其事先级越高。
   
c)normal_prio,由于static_prio和rt_priority与先期级的关联性不雷同,因而用normal_prio统一下“单位”,统一成:normal_prio值越小则进度优先级越高。因而,normal_prio也足以领会为:统一了单位的“静态”优先级。
   
d)prio,在系统中拔取prio判断进度优先级,prio是经过的动态优先级,其表示经过的有用优先级。对于实时进度来说,有效优先级prio就相当于它的normal_prio。普通进程可以临时升高优先级,通过转移prio完结,动态优先级的狠抓不影响进度的静态优先级。父进度的动态优先级不会遗传给子进程,子进度的动态优先级prio开头化为父进程的静态优先级。

 

rt队列的构造是看似rt_queue[100][list]诸如此类的结构,那里99对应实时经过的0-99个优先级,二维是链表,也就是根据实时进度的优先级,将经过挂载相应的list上.

内核 2.6.24 中的变化

新本子中不再追赶全局时钟(fair_clock),任务之间将并行追赶。将引入每个任务(调度实体)的钟表 vruntime(wall_time/task_weight),并且将接纳类似的平均时间开首化新职责的时钟。其余主要改变将影响重大数据结构。下边体现了 struct
sched_entity 中的预期变动:

澳门金沙国际 6

2.6.24 版本中 sched_entity 结构的预料变动

澳门金沙国际 7

2.6.24 版本中 cfs_rq 结构的预想变动

澳门金沙国际 8

2.6.24版本中新加上的 task_group 结构

各类职责都盯住它的运行时,并按照该值对任务展开排队。那意味着运行最少的任务将身处树的最左边。同样,通过对时间加权划分优先级。每个职责在底下的时光段内力求取得确切调度:

sched_period = (nr_running > sched_nr_latency) ?
sysctl_sched_latency : ((nr_running * sysctl_sched_latency) /
sched_nr_latency)

其中 sched_nr_latency = (sysctl_sched_latency /
sysctl_sched_min_granularity)。那表示,当可运行职务数领先 latency_nr 时,将线性延长调度周期。sched_fair.c
中定义的 sched_slice() 是展开这几个计算的地点。由此,借使每个可运行职务局行与 sched_slice() 等价的岁月,那么将消费的小时为 sched_period,每个职分将运行与其权重成比例的时间量。其它,在任何时刻,CFS
都答应超前运行 sched_period,因为最终执行调度的义务将在这一个期限内再度运行。

由此,当一个新职务变为可运行情形时,对其岗位有严俊的须求。在具有其余义务运行以前,此任务不可能运作;否则,将损坏对这几个职责作出的应允。但是,由于该任务真正进行了排队,对运行队列的额外权重将减少其它具有任务的岁月片,在 sched_priod 的终极释放一点岗位,刚好满意新任务的急需。这几个新的职务就被放在这一个地点。

注:

现在開始分情景解析CFS。

rt调度算法总是先选优先级最高的调度实体.

优先级和CFS

CFS 不直接运用优先级而是将其用作允许职责执行的年月的衰减全面。
低优先级职责具有更高的衰减周密,而高优先级职责具有较低的衰减周到。
那象征与高优先级任务比较,低优先级义务允许任务履行的时间消耗得更快。
这是一个美妙的化解方案,可以避免维护按优先级调度的运行队列。

鉴于在一些意况下需求暂时升高进程的优先级,因而不但必要静态优先级和常常优先级,还需求动态优先级prio;

 

那边先贴出那个概念的struct,图1来得了她们之间的关系.

CFS 组调度

设想一个两用户示例,用户 A 和用户 B 在一台机器上运行作业。用户 A
唯有七个作业正在运行,而用户 B 正在运作 48 个作业。组调度使 CFS
可以对用户 A 和用户 B 进行公平调度,而不是对系统中运行的 50
个作业进展公平调度。每个用户各具有 50% 的 CPU 使用。用户 B 使用自己 50%
的 CPU 分配运行他的 48 个作业,而不会占有属于用户 A 的此外 50% 的 CPU
分配。

CFS 调度模块(在 kernel/sched_fair.c
中贯彻)用于以下调度策略:SCHED_NORMAL、SCHED_BATCH 和 SCHED_IDLE。对于 SCHED_RR 和 SCHED_FIFO 策略,将运用实时调度模块(该模块在
kernel/sched_rt.c 中实现)。

CFS 另一个有趣的地点是组调度 概念(在 2.6.24
内核中引入)。组调度是另一种为调度带来公平性的不二法门,更加是在拍卖爆发很多其余任务的职务时。
若是一个爆发了不少职务的服务器要并行化进入的连年(HTTP服务器的典型架构)。不是有所职责都会被合并公平对待,CFS
引入了组来处理那种作为。发生任务的服务器进度在一切组中(在一个层次结构中)共享它们的虚构运行时,而单个职责保持其和谐独自的虚拟运行时。这样单个职分会收取与组几乎相同的调度时间。我们会发觉
/proc
接口用于管理进程层次结构,让大家对组的形成格局有完全的操纵。使用此布局,我们得以跨用户、跨进度或其变体分配公平性。

参照《深入Linux内核架构》p70-76、
p_288-290;

二、创造进程 

struct rq {
    unsigned int nr_running;    //就绪进程的总数目
    struct load_weight load;    //当前队列的总负荷
    struct cfs_rq cfs;          //完全公平队列
    struct rt_rq rt;            //实时队列
    struct task_struct *curr, *idle, *stop; //curr指向当前正在执行的task,
    u64 clock;                  //该队列自身的时钟(实际时间,调度算法还有个虚拟时间的概念)
    ...
};

调度类和域

与 CFS
一起引入的是调度类概念。每个职务都属于一个调度类,那决定了任务将如何调度。
调度类定义一个通用函数集(通过sched_class),函数集定义调度器的表现。例如,每个调度器提供一种艺术,
添加要调度的职责、调出要运行的下一个职分、提需求调度器等等。每个调度器类都在一对三番五次接的列表中相互相连,使类可以迭代(例如,要启用给定处理器的剥夺)。一般结构如下图所示。注意,将职分函数加入队列或退出队列只需从一定调度结构中参与或移除任务。
函数 pick_next_task 拔取要实践的下一个任务(取决于调度类的具体策略)。

澳门金沙国际 9

调度类视图

而是并非忘了调度类是义务结构自身的一局地,那一点简化了职务的操作,无论其调度类具体哪些促成。例如,
以下函数用 ./kernel/sched.c 中的新职分抢占当前运行职分(其中 curr
定义了眼前运作职务, rq 代表 CFS 红黑树而 p 是下一个要调度的任务):

static inline void check_preempt( struct rq *rq, struct task_struct
*p ){ 

 rq->curr->sched_class->check_preempt_curr( rq, p );

}

即使此义务正接纳公平调度类,则 check_preempt_curr()
将解析为check_preempt_wakeup()。 我们能够在
./kernel/sched_rt.c,/kernel/sched_fair.c 和 ./kernel/sched_idle.c
中查阅这么些关乎。

调度类是调度爆发变化的另一个幽默的地点,可是随着调度域的增多,功效也在扩展。
那些域允许你出于负载平衡和隔离的目标将一个或多少个总结机按层次关系分组。
一个或三个电脑可以共享调度策略(并在其时期保持负载平衡)或已毕独立的调度策略从而故意隔离任务。

        
linux内核的优先级继承协议(pip)

先是个情景选为进度创立时CFS相关变量的初步化。
俺们领会。Linux创造进度使用fork或者clone或者vfork等连串调用,终于都会到do_fork。

妥善队列,每个cpu对应一个就绪队列,前面为描述方便,假定系统cpu核数为1.
 

2.6.24 中的组调度有哪些改变

在 2.6.24
中,大家将可以对调度程序开展调优,从而完成对用户或组的公平性,而不是职责公平性。可以将任务进展分组,形成四个实体,调度程序将一律对待那些实体,继而公平对待实体中的任务。要启用那一个特点,在编译内核时索要选拔 CONFIG_FAIR_GROUP_SCHED。目前,只有 SCHED_NORMAL 和SCHED_BATCH 职分可以举行分组。

可以利用五个独立的法子对职务拓展分组,它们各自根据:

1.用户 ID。

2.cgroup pseudo
文件系统:那个选项使管理员能够依照须要创制组。有关越来越多细节,阅读内核源文档目录中的
cgroups.txt 文件。

3.根本配置参数 CONFIG_FAIR_USER_SCHED 和 CONFIG_FAIR_CGROUP_SCHED 可协理你举办精选。

由此引入调度类并因而升高调度统计新闻来简化调试,那些新的调度程序更为壮大了调度功用。

         进度优先级翻盘难点的化解  

假如没有安装CLONE_STOPPED,则会进入wake_up_new_task函数,我们看看这几个函数的严重性部分

struct cfs_rq {  //删减版
    struct load_weight load;  //该队列的总权重
    unsigned int nr_running, h_nr_running;  //该队列中的任务数
    u64 min_vruntime;    //一个虚拟时间,后面细说
    struct rb_root tasks_timeline;  //该cfs队列的红黑树,所有的进程用它来组织
    struct rb_node *rb_leftmost;  //指向红黑树最左边的一个节点,也就是下次将被调度器装载的
    struct sched_entity *curr, *next, *last, *skip; //curr指向当前正在执行的进程
    struct rq *rq;          //自己所属的rq
    struct task_group *tg;  //该cfs队列所属的task_group(task_group是实现cgroup的基础,后面再说)
    ...
};

其他调度器

继续探究调度,您将发现正在开发中的调度器将会突破质量和增加性的尽头。Con
Kolivas 没有被他的 Linux 经验羁绊,他开发出了另一个 Linux
调度器,其缩写为:BFS。该调度器据说在 NUMA
系统以及运动设备上装有更好的性质, 并且被引入了 Android
操作系统的一款衍生产品中。

        为了在Linux中运用Priority
Inheritance
Protocol协议来化解先行级反转难题,Linux中引入实时互斥量rt_mutex,在task_struc结构体中也引入了pi_waiters链表,须求留意的流程为:

[cpp] view
plaincopy

cfs就绪队列,用红黑树组织,那里有一个虚拟时间(vruntime)的定义,来确保在确保高优先级进度占用更加多cpu的前提下,保险拥有进度被正义的调度.

展望

对此 Linux 技术而言,惟一不变的就是原则性的生成。今天,CFS 是 2.6 Linux
调度器;
前天说不定就会是另一个新的调度器或一套可以被静态或动态调用的调度器。
CFS、RSDL 以及基础背后的经过中还有好多机密等待我们去探讨。

         rt_mutex_slowlock() —->
__rt_mutex_slowlock() —->

  1. /* 
  2.  * wake_up_new_task – wake up a newly created task for the first time. 
  3.  * 
  4.  * This function will do some initial scheduler statistics housekeeping 
  5.  * that must be done for every newly created context, then puts the task 
  6.  * on the runqueue and wakes it. 
  7.  */  
  8. void wake_up_new_task(struct task_struct *p, unsigned long clone_flags)  
  9. {  
  10.     …..  
  11.     if (!p->sched_class->task_new || !current->se.on_rq) {  
  12.         activate_task(rq, p, 0);  
  13.     } else {  
  14.         /* 
  15.          * Let the scheduling class do new task startup 
  16.          * management (if any): 
  17.          */  
  18.         p->sched_class->task_new(rq, p);  
  19.         inc_nr_running(rq);  
  20.     }  
  21.     check_preempt_curr(rq, p, 0);  
  22.     …..  
  23. }  
struct rt_prio_array {  //实时队列用这个二位链表组织进程
    DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1);  
    struct list_head queue[MAX_RT_PRIO];    // MAX_RT_PRIO=100 上面解释过了
};

struct rt_rq {
    struct rt_prio_array active;    //组织所有就绪进程
    unsigned int rt_nr_running;     //就绪进程数目
    int rt_throttled;               //禁止调度标记
    u64 rt_time;                    //当前队列累计运行时间
    u64 rt_runtime;                 //当前队列最大运行时间
    unsigned long rt_nr_boosted;
    struct rq *rq;                  //所属rq
    struct task_group *tg;          //所属cgroup
    ...
};

                
task_blocks_on_rt_mutex() —-> 
__rt_mutex_adjust_prio()

 上边极度if语句我不精晓哪些状态下会为真。我測试了一晃。在地点八个分支各加一个计数器,
想见为实在意况只有有2次(我毫无依据的推測是idle进度和init进程),而猜度为假的景色有近万次。
由此我们唯有看之下的分段,要是哪位前辈知道真相的话还望告诉我一声,杰出谢谢。

 

                                                                  
|–> rt_mutex_adjust_prio_chain()

再以下就是检測是或不是可以形成抢占,借使新历程可以抢占当前历程则举行进度切换。

实时就绪队列,用二维链表社团.
因为实时进程优先级总是凌驾普通进程,又不使用完全公平算法,极端气象下实时进程一贯占着cpu,普通进度等不到cpu资源.
为此完毕用rt_time,rt_runtime用来界定实时进度占用cpu资源,例如rt_time =
100 rt_runtime = 95,那八个变量对应cgroup下的cpu.rt_period_us,
cpu.rt_runtime_us.
那么该rq下,所有的实时进度只能占用cpu资源的95%,剩下的%5的资源留给普通进度使用.

         
__rt_mutex_adjust_prio调整了现阶段抱有锁的历程的动态优先级(继承自等待队列中享有进程的万丈优先级),rt_mutex_adjust_prio_chain()若是被调动的动态优先级的历程也在等待某个资源,那么也要链式地调动相应进程的动态优先级。

大家一个一个函数来看
p->sched_class->task_new相应的函数是task_new_fair:

struct sched_entity {
    struct load_weight load;    //该调度实体的权重(cfs算法的关键 >> cgroup限制cpu的关键)
    struct rb_node run_node;    //树节点,用于在红黑树上组织排序
    u64 exec_start;             //调度器上次更新这个实例的时间(实际时间)
    u64 sum_exec_runtime;       //自进程启动起来,运行的总时间(实际时间)
    u64 vruntime;               //该调度实体运行的虚拟时间
    u64 prev_sum_exec_runtime;  //进程在上次被撤销cpu时,运行的总时间(实际时间)
    struct sched_entity *parent;//父调度实体
    struct cfs_rq *cfs_rq;      //自己所属cfs就绪队列
    struct cfs_rq *my_q;        //子cfs队列,组调度时使用,如果该调度实体代表普通进程,该字段为NULL
    ...
};

至于Priority
Inversion可以参见《Operating System Concepts》9_ed p217-218
                                                                                                                      

[cpp] view
plaincopy

一般性进度使用完全公平算法来保管队列中的进程都可取得公正的调度机会,同时兼顾高优先级的经过占用更加多的cpu资源.

  1. /* 
  2.  * Share the fairness runtime between parent and child, thus the 
  3.  * total amount of pressure for CPU stays equal – new tasks 
  4.  * get a chance to run but frequent forkers are not allowed to 
  5.  * monopolize the CPU. Note: the parent runqueue is locked, 
  6.  * the child is not running yet. 
  7.  */  
  8. static void task_new_fair(struct rq *rq, struct task_struct *p)  
  9. {  
  10.     struct cfs_rq *cfs_rq = task_cfs_rq(p);  
  11.     struct sched_entity *se = &p->se, *curr = cfs_rq->curr;  
  12.     int this_cpu = smp_processor_id();  
  13.     sched_info_queued(p);  
  14.     update_curr(cfs_rq);  
  15.     place_entity(cfs_rq, se, 1);  
  16.     /* ‘curr’ will be NULL if the child belongs to a different group */  
  17.     if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&  
  18.             curr && curr->vruntime < se->vruntime) {  
  19.         /* 
  20.          * Upon rescheduling, sched_class::put_prev_task() will place 
  21.          * ‘current’ within the tree based on its new key value. 
  22.          */  
  23.         swap(curr->vruntime, se->vruntime);  
  24.         resched_task(rq->curr);  
  25.     }  
  26.     enqueue_task_fair(rq, p, 0);  
  27. }  
struct sched_rt_entity {
    struct list_head run_list;  //链表节点,用于组织实时进程
    struct sched_rt_entity  *parent;  //父调度实体  
    struct rt_rq        *rt_rq; //自己所属rt就绪队列
    struct rt_rq        *my_q;  //子rt队列,组调度时使用,如果该调度实体代表普通进程,该字段为NULL
    ...
};

 这里有三个根本的函数,update_curr,place_entity。

实时进度的调度算法是很简短的,优先级高的可实时抢占优先级低的进程,直到进度自己屏弃cpu,否则可”一贯”运行.(加了引号的直接)

当中update_curr在那里可以忽视。它是翻新进程的部分随时间变化的新闻。我们松手后边再看,
place_entity是翻新新进程的vruntime值。以便把他插入红黑树。
新进程的vruntime确定之后有一个推测,满意上边多少个原则时,沟通父子进度的vruntime:
1.sysctl设置了子进度优先执行
2.fork出的子进程与父进度在同一个cpu上
3.父进程不为空(那个规格为啥会时有暴发暂不明确,难道是fork第三个经过的时候?)
4.父进度的vruntime小于子进程的vruntime
多少个尺码都还比較好精晓,说下第八个,由于CFS总是挑三拣四vruntime最小的经过执行,
从而必须有限帮衬子进程vruntime比父进度小,小编没有直接把子进度的vruntime设置为较小的值,
而是採用沟通的格局,可以防止通过fork新进程来大量据为己有cpu时间,立即还要讲到。

struct sched_class {
    const struct sched_class *next; //sched_class指针,用于将cfs类 rt类 idle类串起来
    // 全是函数指针,不同的类去各自实现,由调度器统一调用,
    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);
    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 (*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 (*task_move_group) (struct task_struct *p, int on_rq);
};

最后,调用enqueue_task_fair将新进程插入CFS红黑树中

struct
sched_class只是向调度器注明了一组函数,具体的兑现是由逐一调度类(cfs
rt)落成.宗旨调度器只关心在怎么样机会调用那多少个函数指针,不关切具体完结.
图1

以下大家看下place_entity是怎么总括新历程的vruntime的。

澳门金沙国际 10
如图1,体现了逐条社团之间的涉嫌,注意标注出来的调度组.

[cpp] view
plaincopy

为了聚焦,下边啄磨时不考虑有新进度入队,或者就绪队列的子机因为等待其余资源(IO)出队等状态,只以周期性调度(系统每个一段时间爆发一回tick中断,此时系统有机遇更新一些计算变量,同时总计当前历程是或不是早已运行了足足长日子,要求调度)为例表达调度器的行为.
大家清楚实时进度是会抢占普通进度的,所以当有实时进度进入就绪队列时,普通进度很快就会被撤除cpu,让给实时进程,因而实时进度和一般进度的侵夺都是在实时进程入队时实时触发的,所以周期性调度不用考虑那种情况.
那么情状就变简单了,周期调度只需调用当前task的sched_class.task_tick就可以了,如若task是实时进度,相当于调用实时进程的调度类的task_tick达成,当task是不以为奇进度时同理.

  1. static void  
  2. place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)  
  3. {  
  4.     u64 vruntime = cfs_rq->min_vruntime;  
  5.     /* 
  6.      * The ‘current’ period is already promised to the current tasks, 
  7.      * however the extra weight of the new task will slow them down a 
  8.      * little, place the new task so that it fits in the slot that 
  9.      * stays open at the end. 
  10.      */  
  11.     if (initial && sched_feat(START_DEBIT))  
  12.         vruntime += sched_vslice(cfs_rq, se);  
  13.     if (!initial) {  
  14.         //先不看那里,  
  15.     }  
  16.     se->vruntime = vruntime;  
  17. }  

——cfs调度算法
一齐公平调度算法的主要利益是它能够有限接济高优先级的进程占用愈多的cpu时间,当时又能确保拥有进程公平的得到调度机会.
下边也涉嫌了虚拟时间的概念(vruntime),高优先级的历程取得了更加多的cpu时间(实际时间runtime),但从虚拟时间(vruntime)的维度来说,种种进程跑的vruntime是一致长的.
怎么了然?待我举个不是很形象的板栗:
大家把A B
C四个进程比为多少个太婆,把调度器视为一个红领巾,红领巾的靶子是同时把多少个太婆一起扶到马路对面(完全公平嘛).
澳门金沙国际 11

 
此处是持筹握算过程的初始vruntime。

cfs调度算法跟上边红领巾的事例是近似的,可以把红领巾扶老外祖母走过的里程想象为vruntime,一个周期后,他对ABC都是持平的,扶她们走的路途都一律(vruntime时长),大家假诺A曾外祖母腿脚极其不变(A优先级高),那么即使扶A和扶BC走过的里程一样长,可是因为A慢呀,所以肯定扶A要花更长的小时(实际时间).
从而cfs调度算法的绝密就是,优先级高的进程vruntime增加的慢,ABC多个进度可能都跑了10vruntime,但是BC花了10个runtime,而A(优先级高)缺花了20runtime.

它以cfs队列的min_vruntime为基准,再加上进度在一次调度周期中所拉长的vruntime。
此间并非计算进度应该实施的小时。而是先把经过的早已推行时间设为一个较大的值。
可是该进度鲜明还不曾执行过呀,为啥要这么做吗?
即使新历程都能取得最小的vruntime(min_vruntime),那么新进度会首先个被调度执行。
那般程序猿就能透过不断的fork新进度来让自己的程序从来占领CPU。那明确是不创建的,
那跟曾经采取时间片的根本中父子进度要平均父进度的时间片是一个道理。

怎么落实吗?

再解释下min_vruntime,那是每一个cfs队列一个的变量,它一般小于等于一体就绪态进度
的细小vruntime。也有例外。比方对睡觉进程展开时间补偿会招致vruntime小于min_vruntime。

runtime = period * (se->load.weight / cfs_rq->load.weight) 公式1

至于sched_vslice计算细节暂且不细看,大体上说就是把概述中付出的三个公式结合起来例如以下:
sched_vslice = (调度周期 * 进度权重 / 全体经过总权重) * NICE_0_LOAD
/ 进度权重
也就是算出进程应分配的实际上cpu时间,再把它转载为vruntime。
把那么些vruntime加在进程上从此,就一定于认为新进度在这一轮调度中一度实施过了。

period为一个调度周期,那里不关切它怎么样计算,se->load.weight越大,该调度实体在一个调度周期内取得的实际时间越长.

好了。到那边又可以回来wake_up_new_task(希望您还没晕,能想起回去:-)),
看看check_preempt_curr(rq, p,
0);那么些函数就径直调用了check_preempt_wakeup

vruntime = runtime * (orig_load_value / se->load.weight) 公式2

[cpp] view
plaincopy

将orig_load_value是个常量(1024),不言而喻,进程的优先级越高(se->load.weight越大),在runtime相同时其vruntime变化的越慢.
咱俩将公式1率领公式2可得公式3:

  1. /* 
  2.  * Preempt the current task with a newly woken task if needed: 
  3.  */我略去了部分不太重大的代码  
  4. static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int sync)  
  5. {  
  6.     struct task_struct *curr = rq->curr;  
  7.     struct sched_entity *se = &curr->se, *pse = &p->se; //se是方今经过。pse是新历程  
  8.     /* 
  9.      * Only set the backward buddy when the current task is still on the 
  10.      * rq. This can happen when a wakeup gets interleaved with schedule on 
  11.      * the ->pre_schedule() or idle_balance() point, either of which can 
  12.      * drop the rq lock. 
  13.      * 
  14.      * Also, during early boot the idle thread is in the fair class, for 
  15.      * obvious reasons its a bad idea to schedule back to the idle thread. 
  16.      */  
  17.     if (sched_feat(LAST_BUDDY) && likely(se->on_rq && curr != rq->idle))  
  18.         set_last_buddy(se);  
  19.     set_next_buddy(pse);  
  20.     while (se) {  
  21.         if (wakeup_preempt_entity(se, pse) == 1) {  
  22.             resched_task(curr);  
  23.             break;  
  24.         }  
  25.         se = parent_entity(se);  
  26.         pse = parent_entity(pse);  
  27.     }  
  28. }  
vruntime  = period * orig_load_value / cfs_rq->load.weight  公式3

 
首先对于last和next四个字段给予证实。
要是那多个字段不为NULL,那么last指向近期被调度出去的进程,next指向被调度上cpu的经过。
比如A正在推行,被B抢占。那么last指向A。next指向B。

由此可见,进度的vruntime和优先级没有提到,那样就高达了根据事先级分配实际时间,相同的vruntime突显公平.

那多个指针有啥样用吧?
当CFS在调度点选拔下一个推行进度时,会先行照应那两个进程。我们前面会合到,那里唯有要铭记在心。

上面cfs_rq.min_vruntime总是保存当前cfs队列种种调度实体中幽微的vruntime(不是太严苛,不影响).
而红黑树各种sched_entity排序的key为(sched_entity->vruntime –
cfs_rq.min_vruntime),那样优先级越高,相同实际时间的sched_entity->vruntime越小.
对应红黑树的key越小,越靠近红黑树右侧,cfs调度算法就是选用红黑树最右侧的sched_entity给cpu装载.

<
这多个指针仅仅使用三遍。就是在上头那几个函数退出后,重回用户空间时会触发schedule,
在那里拔取下一个调度进度时会优先选项next,次优先选项last。选取完后。就会清空那多个指针。
这么设计的原委是,在地点的函数中检測结果是力所能及抢占并不表示曾经抢占,而单单是安装了调度标志,
在最终触发schedule时抢占进度B并不一定是到头来被调度的长河(为何?由于大家猜测是或不是能抢占
的依据是抢占进度B比举行进度A的vruntime小,但红黑树中或许有比抢占进度B的vruntime更小的进度C,
这么在调度时就会当选vruntime最小的C,而不是侵夺进度B)。不过我们当然期待优先调度B,
是因为大家就是为着履行B才设置了调度标志,所以那边用一个next指针指向B,以便给她个后门走,
假诺B实在不争气,vruntime太大。就依旧继续执行被侵夺进度A比較合理,由此last指向被并吞进度。
那是一个比next小一些的后门,倘诺next近便的小路败北,就让被侵吞进程A也走两次后门,
假定被霸占进度A也不争气。vruntime也太大,仅仅好从红黑树中挑一个vruntime最小的了。
随便它们活动是还是不是中标,一旦选出下一个经过,就随即清空那多少个指针,不可以老开着那个后门吧。
须求专注的是,schedule中清空那三个指针仅仅在2.6.29及之后的基石才有。在此之前的木本没有那句话。

从头撸代码,当tick中断暴发时,焦点调度器调用cfs的task_tick函数task_tick_fair:

下一场调用wakeup_preempt_entity检測是不是满意抢占条件。如若满足(再次来到值为1)
则对现阶段历程设置TIF_NEED_RESCHED标志。在退出系统调用时会触发schedule函数举行进度切换,
本条函数前面再说。

static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &curr->se;

    for_each_sched_entity(se) {     //组调度
        cfs_rq = cfs_rq_of(se);
        entity_tick(cfs_rq, se, queued);    //在entity_tick中更新cfs队列,当前调度实体时间相关的统计,并判断是否需要调度
    }
    ....
}

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
    ...
    update_curr(cfs_rq);    // 更新调度实体,cfs队列统计信息
    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, curr);   // 判断是否需要调度
    ...
}

我们看看wakeup_preempt_entity(se,
pse)。到底怎么猜想后者是或不是可以抢占前者

entity_tick函数紧要的操作就是两局地,首先调用update_curr()去更新sched_entity
cfs的runtimevruntime等信息.
继之再调用check_preempt_tick()函数检查该cfs是还是不是需求重新调度,看下这多少个函数.

[cpp] view
plaincopy

static void update_curr(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_of(cfs_rq)->clock_task;    // 获取当前时间,这里是实际时间
    unsigned long delta_exec;

    if (unlikely(!curr))
        return;
    delta_exec = (unsigned long)(now - curr->exec_start); // 计算自上个周期到当前时间的差值,也就是该调度实体的增量runtime
    if (!delta_exec)
        return;

    __update_curr(cfs_rq, curr, delta_exec);        //真正的更新函数
    curr->exec_start = now;    // exec_start更新成now,用于下次计算
    ...
    account_cfs_rq_runtime(cfs_rq, delta_exec);     //和cpu.cfs_quota_us  cpu.cfs_period_us相关
}

static inline void __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,unsigned long delta_exec)
{
    unsigned long delta_exec_weighted;
    curr->sum_exec_runtime += delta_exec;   //sum_exec_runtime保存该调度实体累计的运行时间runtime
    delta_exec_weighted = calc_delta_fair(delta_exec, curr);    //用runtime(delta_exec)根据公式2算出vruntime(delta_exec_weighted)
    curr->vruntime += delta_exec_weighted;  //累加vruntime
    update_min_vruntime(cfs_rq);    //更新该cfs的min_vruntime
}
  1. /* 
  2.  * Should ‘se’ preempt ‘curr’. 
  3.  * 
  4.  *             |s1 
  5.  *        |s2 
  6.  *   |s3 
  7.  *         g 
  8.  *      |<—>|c 
  9.  * 
  10.  *  w(c, s1) = -1 
  11.  *  w(c, s2) =  0 
  12.  *  w(c, s3) =  1 
  13.  * 
  14.  */  
  15. static int  
  16. wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)  
  17. {  
  18.     s64 gran, vdiff = curr->vruntime – se->vruntime;  
  19.     if (vdiff <= 0)  
  20.         return -1;  
  21.     gran = wakeup_gran(curr);  
  22.     if (vdiff > gran)  
  23.         return 1;  
  24.     return 0;  
  25. }  

这几行代码照旧相比清楚的,依据runtime
公式2算出vruntime,然后累加该sched_entity的vruntime.
因为该sched_entity的vruntime增添了,所以此前封存的cfs_rq->min_vruntime可能失效了,update_min_vruntime()函数负责检查并更新.
同理,该sched_entity的vruntime也许不是该cfs红黑树中幽微的了,由此地方调用了check_preempt_tick()简单是或不是须要重新调度.
看下check_preempt_tick():

那么些函数重临-1意味着新进度vruntime大于当前进度,当然无法抢占。
再次回到0表示即使新历程vruntime比当下进度小。不过没有小到调度粒度,一般也无法抢占
回来1象征新进度vruntime比近期经过小的当先了调度粒度,能够抢占。
调度粒度是如何概念吗?这些也万分好驾驭,仅仅是必须对前方的定义作出一些调整,
面前说每一遍都简单选取vruntime最小的历程调度,事实上也不完全是这么。
要是进度A和B的vruntime分外相近。那么A先举行了一个tick。vruntime比B大了,
B又推行一个tick,vruntime又比A大了。又切换来A。那样就会在AB间频仍切换。对品质影响分外大。
从而一旦当前经过的时光没实用完,就只是有当有经过的vruntime比当下进程小超过调度粒度时。
才干举办进程切换。

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    unsigned long ideal_runtime, delta_exec;
    struct sched_entity *se;
    s64 delta;

    ideal_runtime = sched_slice(cfs_rq, curr);  //根据该sched_entity的权重以及公式1计算出期在本调度周期最大可运行的runtime
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;  //该周期已经运行的runtime
    if (delta_exec > ideal_runtime) {       // 超过了,则调用resched_task设置重新调度标记,(cgroup中的cpu.cfs_quota_us, cpu.cfs_period_us)
        resched_task(rq_of(cfs_rq)->curr);
        return;
    }


    if (delta_exec < sysctl_sched_min_granularity)
        return;

    se = __pick_first_entity(cfs_rq);       // 选取当前红黑树最左端的sched_entity
    delta = curr->vruntime - se->vruntime;  // 两个sched_entity的vruntime比较

    if (delta < 0)
        return;

    if (delta > ideal_runtime)      //这里是个BUG,vruntime不能和runtime比啊,改为 if (delta > calc_delta_fair(ideal_runtime, curr))
        resched_task(rq_of(cfs_rq)->curr);
}

函数方面凝视中那一个图就是以此意思,大家看下:
横坐标表示vruntime。s1 s2
s3各自代表新进度,c表示近期经过,g表示调度粒度。
s3肯定能抢占c。而s1不可以抢占c。
s2即便vruntime比c小。可是在调度粒度之内,是还是不是能抢占要看情状,像昨日如此的风貌就不可以抢占。

check_preempt_tick也是相比较清晰的,首先该sched_entity占用cpu的莫过于时间无法当先根据其权值算出的份额.
附带,如果红黑树最左边的sched_entity的vruntime更小(delta >
ideal_runtime *(orig_load_value /
se->load.weight)参见公式2),那么发起调度.
那里不直接判断delta > 0,应该是为着防患频仍调度吧,cfs调度算法甘休.

到此处,创制进度时的调度相关代码就介绍完了。

——实时调度算法,
实时调度算法原理上没啥好说的,直接看代码吧.

 

static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
{
    struct sched_rt_entity *rt_se = &p->rt;

    update_curr_rt(rq);     // 更新runtime统计,并判断实时进程占用份额达到限制的话,设置调度标记

    if (p->policy != SCHED_RR)  // 如果不是SCHED_RR调度策略,直接返回
        return;

    if (--p->rt.time_slice)     // 每次tick中断-1
        return;

    p->rt.time_slice = sched_rr_timeslice;  // p->rt.time_slice 自减为0,该调度了,给起重新赋值后放入队列末尾

    for_each_sched_rt_entity(rt_se) {
        if (rt_se->run_list.prev != rt_se->run_list.next) {
            requeue_task_rt(rq, p, 0);          // 挂到对列尾,
            set_tsk_need_resched(p);        // 设置调度标记
            return;
        }
    }
}

static void update_curr_rt(struct rq *rq)
{
    struct task_struct *curr = rq->curr;
    struct sched_rt_entity *rt_se = &curr->rt;
    struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
    u64 delta_exec;

    delta_exec = rq->clock_task - curr->se.exec_start;  //增量runtime

    curr->se.sum_exec_runtime += delta_exec;    //task_struct累加

    curr->se.exec_start = rq->clock_task;   //置为当前时间,用以下次计算差值


    for_each_sched_rt_entity(rt_se) {
        rt_rq = rt_rq_of_se(rt_se);
        if (sched_rt_runtime(rt_rq) != RUNTIME_INF) {   //组调度?
            rt_rq->rt_time += delta_exec;   // 当前rt_rq的rt_time累加
            if (sched_rt_runtime_exceeded(rt_rq))   //该rt_rq运行时间是否超出限制
                resched_task(curr);     //是就调度,
        }
    }
}

 

sched_rt_runtime_exceeded里的判定涉及到了用户层通过cgroup限制实时经过的cpu份额(cpu.rt_period_us,
cpu.rt_runtime_us).看下:

 

static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
{
    u64 runtime = sched_rt_runtime(rt_rq);

    if (rt_rq->rt_throttled)
        return rt_rq_throttled(rt_rq);

    if (runtime >= sched_rt_period(rt_rq))
        return 0;

    balance_runtime(rt_rq);     //去其他核上借点时间,不深究了,(cpu.rt_runtime_us / cpu.rt_period_us * cpus才是真正的最大份额)
    runtime = sched_rt_runtime(rt_rq);  //获取本周期最大执行时间
    if (runtime == RUNTIME_INF)
        return 0;

    if (rt_rq->rt_time > runtime) {     //当前运行时间已经超出,需要让出cpu
        struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);

        /*
         * Don't actually throttle groups that have no runtime assigned
         * but accrue some time due to boosting.
         */
        if (likely(rt_b->rt_runtime)) {

            rt_rq->rt_throttled = 1;    //设置该rt_throttled为1,当新的周期开始时,rt_throttled重新被置0

        } else {
            rt_rq->rt_time = 0;
        }

        if (rt_rq_throttled(rt_rq)) {
            sched_rt_rq_dequeue(rt_rq); //将该rt_rq --> task_group(后面说) --> sched_rt_entity出队
            return 1;
        }
    }

    return 0;
}

三、唤醒进度
咱们再看看唤醒进程时的CFS动作。看下函数try_to_wake_up。卓殊长的函数,仅仅留几行代码

到此实时调度也停止了,上面看下组调度.

2.组调度
地方商量时一向用调度实体来代表经过的,那是因为,一个调度实体可能对应一个task_struct,也恐怕对应一个task_group,看下struct:

struct task_struct {
    int on_rq;
    int prio, static_prio, normal_prio;
    unsigned int rt_priority;   
    const struct sched_class *sched_class;  //调度类
    struct sched_entity se;     // cfs调度实体
    struct sched_rt_entity rt;  //rt调度实体
    struct task_group *sched_task_group;
    ...
}

struct task_group {
    struct cgroup_subsys_state css;

    struct sched_entity **se;   //cfs调度实体
    struct cfs_rq **cfs_rq;     //子cfs队列
    unsigned long shares;       //

    atomic_t load_weight;       //

    struct sched_rt_entity **rt_se; // rt调度实体
    struct rt_rq **rt_rq;       //子rt队列

    struct rt_bandwidth rt_bandwidth;   //存储cpu.rt_period_us, cpu.rt_runtime_us
    struct cfs_bandwidth cfs_bandwidth; //存储cpu.cfs_quota_us, cpu.cfs_period_us
};

可见task_group和task_struct中都内嵌了调度实体,与膝下差其他是,task_group并不是最终的运作单位,它只是表示本group中的所有task在上层分配总的cpu资源,
图2展示了task_group和任何几个社团的关系.
图2
澳门金沙国际 12
结缘图1来看,调度算法在选到一个entity时,假如对应的是一个group,那么就在该cgroup的子rq中另行选拔,知道选中一个着实进度,结合代码吧:

static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &curr->se;

    for_each_sched_entity(se) {     //组调度
        cfs_rq = cfs_rq_of(se);
        entity_tick(cfs_rq, se, queued);    //在entity_tick中更新cfs队列,当前调度实体时间相关的统计,并判断是否需要调度
    }
    ....
}

#define for_each_sched_entity(se) \
        for (; se; se = se->parent)

那是上边的代码,展开for_each_sched_entity宏
履新计算音讯时是循环的,假如该调度实体是普通进程,那么se->parent为NULL,如若是某个group下的进度,那么循环发展更新父group.

static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    struct task_struct *p;
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;

    if (!cfs_rq->nr_running)
        return NULL;

    do {        //循环处理
        se = pick_next_entity(cfs_rq);
        set_next_entity(cfs_rq, se);
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);

    p = task_of(se);
    if (hrtick_enabled(rq))
        hrtick_start_fair(rq, p);

    return p;
}

调度器选用下一个装载的长河时,pick_next_entity选出最左侧的sched_entity,假若对应的是一个group,那么就从该cgroup的
sub cfs_rq继续选,知道选到一个经过,
实时组调度也是相仿的,有分其他是,实时group的权重,是该group下权重最大的经过的权重,因为实时进度优先级高的抢占优先级低的呀.
上边结合下后边小说(cgroup原理简析:vfs文件系统)来说下通过echo

[cpp] view
plaincopy

cgroup的决定文件是怎么界定该cgroup下的经过的吧.

eg: echo 2048 >> cpu.shares
vfs调用过成上篇文章说过了,不再另行,直接到cpu_shares_write_u64,cpu_shares_write_u64只是包裹,实际工作的是sched_group_set_shares()函数.

int sched_group_set_shares(struct task_group *tg, unsigned long shares)
{
    ....
    tg->shares = shares;            //将shares赋值到tg->shares
    for_each_possible_cpu(i) {      //一个cgroup在每个cpu上都有一个调度实体,
        struct rq *rq = cpu_rq(i);
        struct sched_entity *se;
        se = tg->se[i];
        for_each_sched_entity(se)
            update_cfs_shares(group_cfs_rq(se));    
    }
    ...
    return 0;
}
进到update_cfs_shares()函数:
static void update_cfs_shares(struct cfs_rq *cfs_rq)
{
    struct task_group *tg;
    struct sched_entity *se;
    long shares;

    tg = cfs_rq->tg;
    se = tg->se[cpu_of(rq_of(cfs_rq))];
    if (!se || throttled_hierarchy(cfs_rq))
        return;
#ifndef CONFIG_SMP
    if (likely(se->load.weight == tg->shares))
        return;
#endif
    shares = calc_cfs_shares(cfs_rq, tg);       //可以理解为shares = tg->share

    reweight_entity(cfs_rq_of(se), se, shares); //设置该task_group对应的sched_entity的load.weight
}
一些简单的判断,最终调用reweight_entity设置weight,
static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, unsigned long weight)
{
    ...
    update_load_set(&se->load, weight);
    ...
}
static inline void update_load_set(struct load_weight *lw, unsigned long w)
{
    lw->weight = w;
    lw->inv_weight = 0;
}

echo 2048 >>
cpu.shares就是设置cgroup->task_group->sched_entity.load.weight对应的值.
重组公式1,改变了weight就最终影响到了该sched_entity占cpu的实在时间.
注意该sched_entity不是某个进度的,而是task_group(cgroup)的,所以最终结果是:该cgroup下的进度占用cpu之和非凡该sched_entity.load.weight结合公式1算出来的cpu时间.

eg: echo 1000000 >> cpu.rt_period_us   echo 950000 >>
cpu.rt_period_us
那边以实时进程看下,cpu.cfs_quota_us 
cpu.cfs_period_us也是近似,不再看了.
vfs–>cpu_rt_period_write_uint,这一个函数封装sched_group_set_rt_period()函数.

static int sched_group_set_rt_period(struct task_group *tg, long rt_period_us)
{
    u64 rt_runtime, rt_period;

    rt_period = (u64)rt_period_us * NSEC_PER_USEC;  //计算新的period
    rt_runtime = tg->rt_bandwidth.rt_runtime;       //原有的quota

    if (rt_period == 0)
        return -EINVAL;

    return tg_set_rt_bandwidth(tg, rt_period, rt_runtime);  //设置
}


vfs-->cpu_rt_runtime_write,这个函数封装sched_group_set_rt_runtime()函数,
static int sched_group_set_rt_runtime(struct task_group *tg, long rt_runtime_us)
{
    u64 rt_runtime, rt_period;

    rt_period = ktime_to_ns(tg->rt_bandwidth.rt_period);    //原有的period
    rt_runtime = (u64)rt_runtime_us * NSEC_PER_USEC;        //新的quota
    if (rt_runtime_us < 0)
        rt_runtime = RUNTIME_INF;

    return tg_set_rt_bandwidth(tg, rt_period, rt_runtime);  //设置
}

可见设置cpu.rt_period_us,cpu.rt_period_us时,都是除了新设的值,再取另外一个原有的值,一起调用tg_set_rt_bandwidth设置.
static int tg_set_rt_bandwidth(struct task_group *tg, u64 rt_period, u64 rt_runtime)
{
    ...
    tg->rt_bandwidth.rt_period = ns_to_ktime(rt_period);    //设置,将quota period存到task_group里
    tg->rt_bandwidth.rt_runtime = rt_runtime;

    for_each_possible_cpu(i) {
        struct rt_rq *rt_rq = tg->rt_rq[i];

        raw_spin_lock(&rt_rq->rt_runtime_lock);
        rt_rq->rt_runtime = rt_runtime;         //同步设置每个rt_rq->rt_runtime
        raw_spin_unlock(&rt_rq->rt_runtime_lock);
    }
    raw_spin_unlock_irq(&tg->rt_bandwidth.rt_runtime_lock);
unlock:
    read_unlock(&tasklist_lock);
    mutex_unlock(&rt_constraints_mutex);

    return err;
}
  1. /*** 
  2.  * try_to_wake_up – wake up a thread 
  3.  * @p: the to-be-woken-up thread 
  4.  * @state: the mask of task states that can be woken 
  5.  * @sync: do a synchronous wakeup? 
  6.  * 
  7.  * Put it on the run-queue if it’s not already there. The “current” 
  8.  * thread is always on the run-queue (except when the actual 
  9.  * re-schedule is in progress), and as such you’re allowed to do 
  10.  * the simpler “current->state = TASK_RUNNING” to mark yourself 
  11.  * runnable without the overhead of this. 
  12.  * 
  13.  * returns failure only if the task is already active. 
  14.  */  
  15. static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)  
  16. {  
  17.     int cpu, orig_cpu, this_cpu, success = 0;  
  18.     unsigned long flags;  
  19.     struct rq *rq;  
  20.     rq = task_rq_lock(p, &flags);  
  21.     if (p->se.on_rq)  
  22.         goto out_running;  
  23.     update_rq_clock(rq);  
  24.     activate_task(rq, p, 1);  
  25.     success = 1;  
  26. out_running:  
  27.     check_preempt_curr(rq, p, sync);  
  28.     p->state = TASK_RUNNING;  
  29. out:  
  30.     current->se.last_wakeup = current->se.sum_exec_runtime;  
  31.     task_rq_unlock(rq, &flags);  
  32.     return success;  
  33. }  

组成方面说的实时调度算法,设置了rt_rq->rt_runtime相当于设置了实时进度在各样周期占用的cpu的最大比例.

eg: echo pid >> tasks
其一操作分为两部。首先改变进程所属的cgroup,在此之前曾经说过了.其次调用各种子系统的attach钩子函数,那里相当于改变进度所在的运行队列。
简短来说就是改变多少个指针的值。让进程与原先的就绪队列断开。跑在cgroup的就绪队列中。
如有错误,请指正。

 
update_rq_clock就是革新cfs_rq的时钟,保持与系统时间共同。
重点是activate_task,它将经过伸张红黑树而且对vruntime做一些调动。
然后用check_preempt_curr检查是还是不是构成并吞条件。要是可以抢占则设置TIF_NEED_RESCHED标识。

由于check_preempt_curr讲过了,大家仅仅顺着以下的各种走一次
   activate_task
–>enqueue_task
–>enqueue_task_fair
–>enqueue_entity
–>place_entity

[cpp] view
plaincopy

  1. static void activate_task(struct rq *rq, struct task_struct *p, int wakeup)  
  2. {  
  3.     if (task_contributes_to_load(p))  
  4.         rq->nr_uninterruptible–;  
  5.     enqueue_task(rq, p, wakeup);  
  6.     inc_nr_running(rq); //执行队列上的妥善义务多了一个  
  7. }  
  8. static void enqueue_task(struct rq *rq, struct task_struct *p, int wakeup)  
  9. {  
  10.     sched_info_queued(p);  
  11.     p->sched_class->enqueue_task(rq, p, wakeup);  
  12.     p->se.on_rq = 1;  //被唤醒的职务会将on_rq设为1  
  13. }  
  14. /* 
  15.  * The enqueue_task method is called before nr_running is 
  16.  * increased. Here we update the fair scheduling stats and 
  17.  * then put the task into the rbtree: 
  18.  */  
  19. static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)  
  20. {  
  21.     struct cfs_rq *cfs_rq;  
  22.     struct sched_entity *se = &p->se;  
  23.     for_each_sched_entity(se) {  
  24.         if (se->on_rq)  
  25.             break;  
  26.         cfs_rq = cfs_rq_of(se);  
  27.         enqueue_entity(cfs_rq, se, wakeup);  
  28.         wakeup = 1;  
  29.     }  
  30.     hrtick_update(rq);  
  31. }  
  32. static void  
  33. enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)  
  34. {  
  35.     /* 
  36.      * Update run-time statistics of the ‘current’. 
  37.      */  
  38.     update_curr(cfs_rq);  
  39.     account_entity_enqueue(cfs_rq, se);  
  40.     if (wakeup) {  
  41.         place_entity(cfs_rq, se, 0);  
  42.         enqueue_sleeper(cfs_rq, se);  
  43.     }  
  44.     update_stats_enqueue(cfs_rq, se);  
  45.     check_spread(cfs_rq, se);  
  46.     if (se != cfs_rq->curr)  
  47.         __enqueue_entity(cfs_rq, se);  //把进度伸张CFS红黑树  
  48. }  

 
此间还必要再看三次place_entity,后面固然看过四遍,不过第多个參数不等同。
当參数3为0的时候走的是还有一条路子,我们看下

[cpp] view
plaincopy

  1. static void  
  2. place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)  
  3. {  
  4.     u64 vruntime = cfs_rq->min_vruntime;  
  5.     /* 
  6.      * The ‘current’ period is already promised to the current tasks, 
  7.      * however the extra weight of the new task will slow them down a 
  8.      * little, place the new task so that it fits in the slot that 
  9.      * stays open at the end. 
  10.      */  
  11.     if (initial && sched_feat(START_DEBIT))  
  12.         vruntime += sched_vslice(cfs_rq, se);  
  13.     if (!initial) {  
  14.         /* sleeps upto a single latency don’t count. */  
  15.         if (sched_feat(NEW_FAIR_SLEEPERS)) {  
  16.             unsigned long thresh = sysctl_sched_latency;  
  17.             /* 
  18.              * convert the sleeper threshold into virtual time 
  19.              */  
  20.             if (sched_feat(NORMALIZED_SLEEPER))  
  21.                 thresh = calc_delta_fair(thresh, se);  
  22.             vruntime -= thresh;  
  23.         }  
  24.         /* ensure we never gain time by being placed backwards. */  
  25.         vruntime = max_vruntime(se->vruntime, vruntime);  
  26.     }  
  27.     se->vruntime = vruntime;  
  28. }  

 
initial分歧时候两条路子有何样两样呢?路径1是新创设职责的时候对其vruntime举行初阶化,将它身处红黑树右端。
而以下这条路是提示睡眠职务时的代码,大家考虑一个义务睡眠了尤其长日子,它的vruntime就一贯不会更新,
如此当它醒来时vruntime会远远小于执行队列上的不论什么一个义务,于是它会长久占有CPU,那分明是不创设的。
就此那要对唤醒义务的vruntime进行部分调整,咱们可以见到。那里是用min_vruntime减去一个thresh,
其一thresh的估摸进度就是将sysctl_sched_latency换算成进度的vruntime,而那一个sysctl_sched_latency
就是默许的调度周期。单核CPU上一般为20ms。之所以要减去一个值是为着对睡觉进度做一个互补,
能让它醒来时可以高效的到CPU。
个人感觉这么些设计很领会,曾经O(1)调度器有一个复杂的公式(到近来本人也没能记住),
用来不同交互式进程和CPU密集型进度,详情请參考ULK等书。而现在CFS无须再接纳万分复杂的公式了。
单单如若常睡眠的长河,它被唤醒时必定会有十分小的vruntime。可以即时执行,省却了尤其多独特情形的处理。
无异于时候还要小心那句凝视 ensure we never gain time by being placed
backwards。
当然那里是给由于长日子睡觉而vruntime远远小于min_vruntime的进度补偿的,可是多少进度仅仅睡眠极度短期,
如此在它復苏后vruntime依然出乎min_vruntime,不能让进程经过睡眠拿到额外的实践时间。所以最终选用
总结出的补充时间与经过原本vruntime中的较大者。

到这里,place_entity就讲完了。

不过我有一个标题,为何总计thresh要用整个调度周期换算成vruntime?
个人感觉应该用(调度周期 * 进度权重 /
全体历程总权重)再折算成vruntime才合情合理阿,用所有调度周期
是否互补太多了?

 

 

四、进度调度schedule

以下看下主动调度代码schedule。

[cpp] view
plaincopy

  1. /* 
  2.  * schedule() is the main scheduler function. 
  3.  */  
  4. asmlinkage void __sched schedule(void)  
  5. {  
  6.     struct task_struct *prev, *next;  
  7.     unsigned long *switch_count;  
  8.     struct rq *rq;  
  9.     int cpu;  
  10. need_resched:  
  11.     preempt_disable(); //在那之中被侵夺可能现亡故障。先禁止它!  
  12.     cpu = smp_processor_id();  
  13.     rq = cpu_rq(cpu);  
  14.     rcu_qsctr_inc(cpu);  
  15.     prev = rq->curr;  
  16.     switch_count = &prev->nivcsw;  
  17.     release_kernel_lock(prev);  
  18. need_resched_nonpreemptible:  
  19.     spin_lock_irq(&rq->lock);  
  20.     update_rq_clock(rq);  
  21.     clear_tsk_need_resched(prev); //清除须要调度的位  
  22.     //state==0是TASK_RUNNING,不等于0就是准备睡眠,正常景况下应该将它移出执行队列  
  23.     //然而还要检查下是还是不是有信号过来。如果有信号而且经过处于可间歇睡眠就提醒它  
  24.     //注意对于需要上床的长河。那里调用deactive_task将其移出队列而且on_rq也被清零  
  25.     //这个deactivate_task函数就不看了,相当easy  
  26.     if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {  
  27.         if (unlikely(signal_pending_state(prev->state, prev)))  
  28.             prev->state = TASK_RUNNING;  
  29.         else  
  30.             deactivate_task(rq, prev, 1);  
  31.         switch_count = &prev->nvcsw;  
  32.     }  
  33.     if (unlikely(!rq->nr_running))  
  34.         idle_balance(cpu, rq);  
  35.     //那五个函数都是任重(英文名:rèn zhòng)而道远,我们以下分析  
  36.     prev->sched_class->put_prev_task(rq, prev);  
  37.     next = pick_next_task(rq, prev);  
  38.     if (likely(prev != next)) {  
  39.         sched_info_switch(prev, next);  
  40.         rq->nr_switches++;  
  41.         rq->curr = next;  
  42.         ++*switch_count;  
  43.         //落成进度切换,不讲了,跟CFS没关系  
  44.         context_switch(rq, prev, next); /* unlocks the rq */  
  45.         /* 
  46.          * the context switch might have flipped the stack from under 
  47.          * us, hence refresh the local variables. 
  48.          */  
  49.         cpu = smp_processor_id();  
  50.         rq = cpu_rq(cpu);  
  51.     } else  
  52.         spin_unlock_irq(&rq->lock);  
  53.     if (unlikely(reacquire_kernel_lock(current) < 0))  
  54.         goto need_resched_nonpreemptible;  
  55.     preempt_enable_no_resched();  
  56.     //那里新进程也可能有TIF_NEED_RESCHED标志,即使新历程也务必调度则再调度三次  
  57.     if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))  
  58.         goto need_resched;  
  59. }  

 

首先看put_prev_task,它等于put_prev_task_fair,后者基本上就是直接调用put_prev_entity

[cpp] view
plaincopy

  1. static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)  
  2. {  
  3.     /* 
  4.      * If still on the runqueue then deactivate_task() 
  5.      * was not called and update_curr() has to be done: 
  6.      */  
  7.     //记得那里的on_rq吗?在schedule函数中要是进度景况不是TASK_RUNNING,  
  8.     //那么会调用deactivate_task将prev移出执行队列,on_rq清零。因而那里也是只是有当  
  9.     //prev进度如故在执行态的时候才须求更新vruntime等音信。  
  10.     //要是prev进程由于被侵占或者出于时日到了而被调度出去则on_rq仍然为1  
  11.     if (prev->on_rq)  
  12.         update_curr(cfs_rq);  
  13.     check_spread(cfs_rq, prev);  
  14.     //那里也如出一辙,仅仅有当prev进度仍在实践情形的时候才需要更新vruntime音信  
  15.     //实际上正在cpu上执行的历程是不在红黑树中的,仅仅有在伺机CPU的长河才在红黑树  
  16.     //因而那里将调度出的进度再次增添红黑树。

    on_rq并不表示在红黑树中,而是意味着在实施情状

      

  17.     if (prev->on_rq) {  

  18.         update_stats_wait_start(cfs_rq, prev);  
  19.         /* Put ‘current’ back into the tree. */  
  20.         //那么些函数也不跟进去了,就是把经过以(vruntime-min_vruntime)为key扩大到红黑树中  
  21.         __enqueue_entity(cfs_rq, prev);  
  22.     }  
  23.     //没有当前进度了。那几个当前经过将在pick_next_task中更新  
  24.     cfs_rq->curr = NULL;  
  25. }  

 

再回到schedule中看看pick_next_task函数。基本上也就是直接调用pick_next_task_fair

[cpp] view
plaincopy

  1. static struct task_struct *pick_next_task_fair(struct rq *rq)  
  2. {  
  3.     struct task_struct *p;  
  4.     struct cfs_rq *cfs_rq = &rq->cfs;  
  5.     struct sched_entity *se;  
  6.     if (unlikely(!cfs_rq->nr_running))  
  7.         return NULL;  
  8.     do {  
  9.         //那四个函数是关键,拔取下一个要运行的义务  
  10.         se = pick_next_entity(cfs_rq);  
  11.         set_next_entity(cfs_rq, se);  
  12.         cfs_rq = group_cfs_rq(se);  
  13.     } while (cfs_rq);  
  14.     p = task_of(se);  
  15.     hrtick_start_fair(rq, p);  
  16.     return p;  
  17. }  

 

重大看下pick_next_entity和set_next_entity

[cpp] view
plaincopy

  1. static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)  
  2. {  
  3.     //__pick_next_entity就是直接选拔红黑树缓存的最左结点,也就是vruntime最小的结点  
  4.     struct sched_entity *se = __pick_next_entity(cfs_rq);  
  5.     //以下的wakeup_preempt_entity已经讲过。忘记的同桌可以到上边看下  
  6.     //那里就是前方所说的预先照应next和last进度,仅仅有当__pick_next_entity选出来的经过  
  7.     //的vruntime比next和last都小领先调度粒度时才轮到它执行,否则就是next或者last  
  8.     if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, se) < 1)  
  9.         return cfs_rq->next;  
  10.     if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, se) < 1)  
  11.         return cfs_rq->last;  
  12.     return se;  
  13. }  
  14. static void  
  15. set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)  
  16. {  
  17.     /* ‘current’ is not kept within the tree. */  
  18.     //那里怎么动静下标准会为假?我以为刚唤醒的长河可能不在rq上  
  19.     //不过回到地方去看了下,唤醒的历程也通过activate_task将on_rq置1了  
  20.     //新创造的进度on_rq也被置1,那里怎么境况会为假,想不出去  
  21.     //那里我也測试了一晃。在尺度为真假的途径上各设置了一个计数器  
  22.     //当条件为真经过了临近五十万次的时候条件为假仅有一遍。  
  23.     //所以大家可以觉得大约都会一向进去if语句块执行  
  24.     if (se->on_rq) {  
  25.         /*那边凝视是否写错了?dequeued写成了enqueued? 
  26.          * Any task has to be enqueued before it get to execute on 
  27.          * a CPU. So account for the time it spent waiting on the 
  28.          * runqueue. 
  29.          */  
  30.         update_stats_wait_end(cfs_rq, se);  
  31.         //就是把结点从红黑树上取下来。

    面前说过,占用CPU的进程不在红黑树上

      

  32.         __dequeue_entity(cfs_rq, se);  

  33.     }  
  34.     update_stats_curr_start(cfs_rq, se);  
  35.     cfs_rq->curr = se;  //OK。在put_prev_entity中清空的curr在此处被更新  
  36.     //将进度执行总时间保存到prev_..中。那样经过这次调度的执行时间可以用以下公式计算:  
  37.     //进程这一次实施已占据CPU时间 =  sum_exec_runtime – prev_sum_exec_runtime  
  38.     //这里sum_exec_runtime会在每一趟时钟tick中立异  
  39.     se->prev_sum_exec_runtime = se->sum_exec_runtime;  
  40. }  

 
到此schedule函数也讲完了。

关于dequeue_task,dequeue_entity和__dequeue_entity三者差距
前双方差不太多。分歧的那部分自家也没看明确。。。重假如它们都会将on_rq清零。
本身以为是当进度要离开TASK_RUNNING状态时调用。那四个函数可以将经过取下执行队列。

而__dequeue_entity不会将on_rq清零,仅仅是将经过从红黑树上取下,
自我觉得一般用在进度将取得CPU的图景,那时必要将它从红黑树取下,可是还要保留在rq上。

 

 

五、时钟中断

接下去的景观就是时钟中断,时钟中断在time_init_hook中初步化,中断函数为timer_interrupt
根据例如以下途径
   timer_interrupt
–>do_timer_interrupt_hook
–>那里有一个回调函数,在自家机器上測试调用的是tick_handle_oneshot_broadcast
–>从tick_handle_oneshot_broadcast前边一部分经过怎么走的没搞通晓,有时光用kgdb跟踪一下
–>反正最后是到了tick_handle_periodic
–>tick_periodic
–>update_process_times
–>scheduler_tick 那里面跟CFS相关的显要就是翻新了cfs_rq的时钟
–>通过回调函数调到task_tick_fair,没作什么事,直接进入了entity_tick
–>entity_tick这几个函数看下

[cpp] view
plaincopy

  1. static void  
  2. entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)  
  3. {  
  4.     /* 
  5.      * Update run-time statistics of the ‘current’. 
  6.      */  
  7.     update_curr(cfs_rq);  
  8.     //….毫不相关代码  
  9.     if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))  
  10.         check_preempt_tick(cfs_rq, curr);  
  11. }  

entity_tick函数就是革新情状音信,然后检測是不是满意抢占条件。
后边大家直接忽略update_curr,那里非看不可一下了

[cpp] view
plaincopy

  1. static void update_curr(struct cfs_rq *cfs_rq)  
  2. {  
  3.     struct sched_entity *curr = cfs_rq->curr;  
  4.     u64 now = rq_of(cfs_rq)->clock; //这个clock刚刚在scheduler_tick中更新过  
  5.     unsigned long delta_exec;  
  6.     /* 
  7.      * Get the amount of time the current task was running 
  8.      * since the last time we changed load (this cannot 
  9.      * overflow on 32 bits): 
  10.      */  
  11.     //exec_start记录的是上四回调用update_curr的日子,大家用当下时间减去exec_start  
  12.     //就得到了从上次测算vruntime到前几天进程又推行的小运,用那几个时刻换算成vruntime  
  13.     //然后加到vruntime上,那所有是在__update_curr中得了的  
  14.     delta_exec = (unsigned long)(now – curr->exec_start);  
  15.     __update_curr(cfs_rq, curr, delta_exec);  
  16.     curr->exec_start = now;   
  17.     if (entity_is_task(curr)) {  
  18.         struct task_struct *curtask = task_of(curr);  
  19.         cpuacct_charge(curtask, delta_exec);  
  20.         account_group_exec_runtime(curtask, delta_exec);  
  21.     }  
  22. }  
  23. /* 
  24.  * Update the current task’s runtime statistics. Skip current tasks that 
  25.  * are not in our scheduling class. 
  26.  */  
  27. static inline void  
  28. __update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,  
  29.           unsigned long delta_exec)  
  30. {  
  31.     unsigned long delta_exec_weighted;  
  32.     //前面说的sum_exec_runtime就是在此地计算的,它等于进程从创造開始占用CPU的总时间  
  33.     curr->sum_exec_runtime += delta_exec;   
  34.     //以下变量的weighted表示这么些值是从执行时间考虑权重因素换算来的vruntime。再写一遍这一个公式  
  35.     //vruntime(delta_exec_weighted) = 实际执行时间(delta_exe) * 1024 / 进度权重  
  36.     delta_exec_weighted = calc_delta_fair(delta_exec, curr);  
  37.     //将进程刚刚施行的小运换算成vruntime后立马加到进程的vruntime上。  
  38.     curr->vruntime += delta_exec_weighted;  
  39.     //由于有经过的vruntime变了,因而cfs_rq的min_vruntime可能也要转移,更新它。  
  40.     //这几个函数简单,就不跟进去了,就是先取tmp = min(curr->vruntime,leftmost->vruntime)  
  41.     //然后cfs_rq->min_vruntime = max(tmp, cfs_rq->min_vruntime)  
  42.     update_min_vruntime(cfs_rq);  
  43. }   

OK。更新完CFS状态之后回到entity_tick中,那时要求检測是还是不是知足抢占条件。那里也是CFS的严重性之中的一个

[cpp] view
plaincopy

  1. static void  
  2. check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)  
  3. {  
  4.     unsigned long ideal_runtime, delta_exec;  
  5.     //这里sched_slice跟下边讲过的sched_vslice非常象,只是sched_vslice换算成了vruntime,  
  6.     //而那里那个就是实际时间,没有经过换算,重临值的就是此进度在一个调度周期中应该举行的小时  
  7.     ideal_runtime = sched_slice(cfs_rq, curr);  
  8.     //上面提到过那几个公式了,计算进程已占据的CPU时间。如若超越了应该占据的光阴(ideal_runtime)  
  9.     //则设置TIF_NEED_RESCHED标志,在剥离时钟中断的历程中会调用schedule函数进行进程切换  
  10.     delta_exec = curr->sum_exec_runtime – curr->prev_sum_exec_runtime;  
  11.     if (delta_exec > ideal_runtime)  
  12.         resched_task(rq_of(cfs_rq)->curr);  
  13. }  

 

 

 

 

附:一个小測试

看prio_to_weight数组,差距nice值的历程权重差别极度大。最大权重是微小权重的6000倍左右,
是或不是代表一旦同一时候有三个进程A和B在系统中实施。A的nice为-20,B的为19,那么A分配的实践时间
是B的6000倍啊?没错。我做了一个试行,先进行例如以下顺序,

[cpp] view
plaincopy

  1. int main()  
  2. {  
  3.     errno = 0;  
  4.     if(fork()) {  
  5.         setpriority(PRIO_PROCESS, 0, -20);  
  6.     } else {  
  7.         setpriority(PRIO_PROCESS, 0, 19);  
  8.     }     
  9.     if(errno) {  
  10.         printf(“failed/n”);  
  11.         exit(EXIT_FAILURE);  
  12.     }     
  13.     printf(“pid:%d/n”, getpid());  
  14.     while(1);  
  15.     return 0;  
  16. }  

 
下一场再插入例如以下模块

[cpp] view
plaincopy

  1. #define T1 (首个进度的pid)  
  2. #define T2 (第四个进度的pid)  
  3. static int __init sched_test_init(void)  
  4. {  
  5.     struct task_struct *p;   
  6.     for_each_process(p) {  
  7.         if(p->pid == T1 || p->pid == T2)   
  8.             printk(“%d runtime:%llu/n”, p->pid, p->se.sum_exec_runtime);  
  9.     }     
  10.     return -1; //再次回到-1防患模块真正插入,大家仅仅要求打印出地点的新闻就可见了。  
  11. }  

 
再dmesg查看结果,我測试过三遍。两次设置nice分别为0和6,那么权重之比为
1024 / 272 = 3.7647。结果进行时间之比为 146390068851 / 38892147894 =
3.7640
可知看出结果一定接近,
再有两遍设置nice分别为-20和19,权重之比为88761 / 15 = 5917.4000,
结果实施时间之比为187800781308 / 32603290 = 5760.1788。也卓殊类似。
可以看出,下面的权重与实践时间成正比的下结论是建立的。
骨子里,当自身执行一个nice为-20的顺序后,整个种类很卡,差一些儿成了幻灯片,
也注明nice值的不等带来的差距很明朗。

其它有一些值得一提,就算所有系统相当卡,然而对鼠标键盘的响应照旧不行快。
自己打字的时候差不多不会有如何延迟,那也证实。即使CFS没有经过复杂的经历公式区分
交互式进度。不过它的宏图思路使他天生地对交互式进度的响应可能比O(1)调度还要好。

(统计:1、在经过执行时,其vruntime稳定的拉长,它在红黑树中老是向右移动。由于越首要的长河vruntime添加越慢,由此他们向右移动的快慢也越慢。这样其被调度的机会要当先次要进度,那刚好是我们不能够不的。2、假若进度进入睡眠,则其vruntime保持不变,由于每一个连串min_vruntime同一时候会助长(由于她们是干燥的),那么睡眠进度醒来后,在红黑树中的地点会更靠左。由于其键值变得更小了。注意底层使用的是红黑树结构)

相关文章