操作系统

当前位置:金沙棋牌 > 操作系统 > 校招面试,cgroup原理简析

校招面试,cgroup原理简析

来源:http://www.logblo.com 作者:金沙棋牌 时间:2019-11-05 18:52

在抽象模型中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_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.     //这两个函数都是重点,我们以下分析  
  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同一时候会添加(由于他们是单调的),那么睡眠进程醒来后,在红黑树中的位置会更靠左。由于其键值变得更小了。注意底层使用的是红黑树结构)

本文由金沙棋牌发布于操作系统,转载请注明出处:校招面试,cgroup原理简析

关键词: