- 论坛徽章:
- 0
|
总结了篇关于cfs调度器的文档
喜欢pdf的可以查看档案~
CFS 调度器
--wxc200
大家好哈，
兄弟最近在学习调度器，有点儿心得，更多得是迷惑，写出心得来与大家分享，贴出迷惑来请大家解答。呵呵
linux自2.6.23后引入了一种新的调度器，叫'Completely Fair Scheduler'（wiki）.是由Ingo Molnar在很短的时间内写的。他与的cfs代码是对之前另一种调度器 "O(1) scheduler" 的替换.
先扯一下o(1)调度.
先看wiki的解释:
"An O(1) scheduler is a kernel scheduling design that can schedule processes within a constant amount of time, regardless of how many processes are running on the operating system (OS)."
Understanding Linux Kernel(3th) 这本书chapter 7讲的进程调度,7.2节提到"Scheduling Algorithm",说2.6 对进程的选择是constant time,兼顾了批处理和交互式进程.进程分类,实时进程(又分为SCHED_FIFL AND SCHED_RR)和普通进程.
最主要的问题是这些进程怎么组织的,简单看下结构:
没办法传图片,请参照附件"数组".
它有两个数 组,active里面是has time-slice 的,expired数组是out-of-slice。简单的说，一个普通的进程被调度运行后，放在active里，当其时间片用光后，可能就要移到 expired数组里了。说“可能”是因为有的进程就不移走。比如交互式进程。
说白了,就是把所有的process按照优先级挂在链表上,从里面按照优先级高低选择第一个不为空的进程运行.
普通进程的优先级是100~139,实时进程要更低,这符合调度的算法.
我有点等不及了,咱们直接奔cfs吧~
另外有点就是,引入hrtimer之后,进程调度还是在tick中断完成的.每个tick都会检查进程是否应该调度,当然,主动让cpu(即调用scheduler().)的就不算了吧...
hrtimer那部分东东等咱们聊完了cfs再说，那个主要是在原有的时间管理layer上新添加了“时间事件”，把时间中断以事件的方式注册。精确度由之前的hz提升到了ns（需要硬件支持）。。。
cfs
Documentation/scheduler/sched-design-CFS.txt 介绍了cfs相关东西，也可以在线看.
我按照我的理解来“添油加醋”地翻译下。
1 概括
“80% of CFS's design can be summed up in a single sentence: CFS basically models
an "ideal, precise multi-tasking CPU" on real hardware.”
""Ideal multi-tasking CPU" is a (non-existent  ) CPU that has 100% physical
power and which can run each task at precise equal speed, in parallel, each at
1/nr_running speed. For example: if there are 2 tasks running, then it runs
each at 50% physical power --- i.e., actually in parallel.
"
模 拟了个理想的，多任务cpu.假如有n个进程，那么每个进程 的执行速度是1/n,,即所有的任务都是并行执行的。我认为就算是有并行执行的cpu，速度也不应该完全平均，按照优先级再分比较划算。比如2个进 程，a,b，a 的优先级是b的两 倍，那么就照着速度比a:b = 2:1呗~
“On real hardware, we can run only a single task at once, so we have to
introduce the concept of "virtual runtime." The virtual runtime of a task
specifies when its next timeslice would start execution on the ideal
multi-tasking CPU described above. In practice, the virtual runtime of a task
is its actual runtime normalized to the total number of running tasks. ”
当然没有这种cpu,故引进了个新概念"virtual runtime",这个概念真是折磨人好久。我曾经在clf上发帖子问过，有个兄弟回复还是不错的。后面看过代码后，我的理解是：1） 红黑树结点排列的值 2） 每次task run time转换的一个值 .
先看上文颜色部分，我真是很难翻译它~ 照字面理解，是实际运行时间与任务数量的一个比值？ 我举个例子来说明它是怎么计算 的吧。。
在 __update_curr(）这个函数里，会更新当前任务的运行时间信息。假如一个任务a自上次调度到这次调度时间间隔为delta,那么它的 vrumtime的增量是按照这个公式：delta * NICE_0_LOAD / a->se.load。假如把NICE_0_LOAD / a->se.load作为一个比值p的话，我们可以这么描述p的变化：优先级越高，p越小。这个load是与nice值 相关的，有一个静态的数组，我后面在代码里会介绍。
所以，一堆进行都运行了一段时间delta，那么它们的vrumtime就遵循上面的公式。很明显，优先级最大的进程vrumtime增量最小。。。
2 操作细节
cfs就是通过追踪这个vruntime来进行任务调度的。它总是选 vruntime最小的进程来运行。
3 红黑树。
红黑树这个数据结构在内核里用得还不少嘛，不过俺不太懂。哪位兄弟给扫扫盲？ hrtimer里也用到了red-black-tree。这里把进程的vruntime用rb-tree来存储。
4 一些feature
cfs has no time-slice concept.o(1)有的，cfs没有“明显”得用，它偷偷摸摸地用。呵呵 翻译完这几段咱再说这个。文档里面那个接口估计是用来调整“最小粒度”的。用于“桌面”和“服务器“两 种不同的调度。后者可能不太希望频繁的调度，浪费时间。前者则希望面面俱到--”不患寡妇而患不均也“
5 调度policy
SCHED_FIFO/_RR are implemented in sched_rt.c and are as specified by POSIX. 实时进程调度
实时调度和普通进程调度。
6 调度的类。
调度哭可以模块化注册，所以你可以选择实时调度或者是cfs调度。不错！
sched_fair.c文件实现了cfs调度的所以classes
7 组调度。
不光是普通进程，组调度也实现了。。这个是后来一个patch加的。
×××××××××××××××××××××××××××××××××××
上面 是对着内核的一篇文档，简要地说了几部分 。。。在正式进行我们的hack之前，先唠叨几句，算是个总结和感性的认识吧~吼吼
关于实时进程的调度，这一次先不分析，它和o1差不多，还保持着优先级数组的做法，那是”上流社会“玩儿的游戏，后面再折腾它。”普通大众“们玩儿的就是cfs了。
cfs调度，我写两 部分，一部分是普通进程的调度，没有组的概念。一部分是组的调度。我个人觉得组得调度比较难理解~ 这几天一直在思考。。。今天下午好像豁然开朗了。。。画了个草图，到后面我做出这张图来，大家看看对不对 
咱们先说普通进程的调度
关于普通进程的组织，应该有这么一种印象。
有一个队列，叫cfs_rq,里面维护了个红黑树。每一个task_struct has a se,称为调度实体。它就代表了一个被调度的进程，里面有此进程的一些信息，比如前面提到的vruntime.
一个进程创建的时候，就会被放置在这个红黑树里。它自己的位置是由它的vruntime值 来决定的。在每个tick中断的时候，会更新进程的信息，并检查这个红黑树，判断某些进程是不是要被替换掉。
现在我们来想象下面一个例程。
进 程a被创建了，sched_fork()会做一些新创建进程调度方面的初始化。然后应该尝试把此进程放到队列里啊，让它被调度。 set_task_cpu()做了这部分工作。然后这个进程如果不是实时进程，就让它跟cfs的类绑定在一块儿，这样下面用到调度的一些方法，就会到 cfs相关的类去找喽~ 这时候如果抢占打开了，会去调度一次，以让新创建的进程有机会被调度一次。或者在下一个tick的时候，会检查已经红黑树，以确认这个进程是不是调度。（注：上面红色这句有点胡扯的嫌疑，请明白人指点）
比如在每个tick中断的时候，会去红黑树里面找vruntime最小的那个（红黑树最左边的叶子）去调度。那么这个调度过程，所有用到的方法，就是上面提到的cfs的类给实现的。
最后，大家再对rb-tree里面的任务结点有个感性的认识吧：
优先级高的进程，总是靠左，以有最大调度机会。比如说有n个进程，那么在一段时间内，应该把n个进程都运行一遍。这儿有两三个问题，一段时间是多久？每个进程有多少时间去运行呢？每个进程分到的运行时间跟vruntime有什么关系呢？
一段时间，与运行着的进程数目有关。进程越多，时间越长。每个进程并不是平均分配这些时间的。按照我的理解，分到这个时间越多的进程，后面vruntime增长得越慢。
上面 这几句话，我可是晕了近一个星期才明白的。不知道跟大家的理解一致么？
本 来我错误得理解是这样的，完全公平调度么，当然所有的进程有同样的运行时间。如果是这样，那么rb-tree就没用了。因为每个结点都一样的值。所以，请 大家有这样一种概念：两 个进程，a优先级特别低，b特高。假如现在有n个正被调度的进程，它们都被调度一遍的时间是delta，那么b会占很高的时间，a 很低的时间。运行完成后，b还是在很靠左的地方呆着，而a一定往最靠右的地方。。。。哎，表述不清啊，，最好画个图。。。这样就为了让b得到更常的运行时 间。。。而其vruntime仍然很小（可以参照上封邮件里面那个计算vruntime的公式）
好了
我们开始真正的代码旅行吧。
1 几个重要的数据结构
1）task_struct : 大家都知道这个。
struct task_struct {
...
int prio, static_prio, normal_prio; 进程的优先级
unsigned int rt_priority;实时进程的优先级
const struct sched_class *sched_class; 调度类，一堆函数指针，实现调度
struct sched_entity se;调度实体 一个进程对应一个调度实体，，
struct sched_rt_entity rt;
....
}
2) sched_class 调度相关的函数指针。
struct sched_class {
...
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup); 入列
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);出列
void (*yield_task) (struct rq *rq);
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int sync);检查当前进程可否被新进程抢占
struct task_struct * (*pick_next_task) (struct rq *rq); 选择下一个进程运行
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
#ifdef CONFIG_SMP
int (*select_task_rq)(struct task_struct *p, int sync);
....
#ifdef CONFIG_FAIR_GROUP_SCHED 请格外留意此宏。。。。跟组调度相关的，，暂时不管它，后面跟组相关的调度再回来看它。
void (*moved_group) (struct task_struct *p);
#endif
};
3） 调度实体
struct sched_entity {
struct load_weight load; /* for load-balancing */ nice对应的load值
struct rb_node run_node; 红黑树结点
struct list_head group_node;
unsigned int on_rq; 这个是什么呢？不知道
u64 exec_start; 上次开始调度时的运行时间
u64 sum_exec_runtime; 总运行时间
u64 vruntime;呵呵 都知道了
u64 prev_sum_exec_runtime; 上次调度总运行时间
...
#ifdef CONFIG_FAIR_GROUP_SCHED 如果是组调度的话，就多了些部分。
struct sched_entity *parent;
/* rq on which this entity is (to be) queued: */
struct cfs_rq *cfs_rq;
/* rq "owned" by this entity/group: */
struct cfs_rq *my_q;
#endif
}
4)cfs 运行队列
/* CFS-related fields in a runqueue */
struct cfs_rq {
struct load_weight load;
unsigned long nr_running;
u64 exec_clock;
u64 min_vruntime;
5)大boss，运行队列
struct rq {
,...
unsigned long nr_running;
#define CPU_LOAD_IDX_MAX 5
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
...
struct cfs_rq cfs;
..
struct task_struct *curr, *idle;
}
6）调度相关类
/*
* All the scheduling class methods:
*/
static const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.check_preempt_curr = check_preempt_wakeup,
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
#ifdef CONFIG_SMP
.select_task_rq = select_task_rq_fair,
.load_balance = load_balance_fair,
.move_one_task = move_one_task_fair,
#endif
.set_curr_task = set_curr_task_fair,
.task_tick = task_tick_fair,
.task_new = task_new_fair,
.prio_changed = prio_changed_fair,
.switched_to = switched_to_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
.moved_group = moved_group_fair,
#endif
};
2 吃代码
上面几个结构体的关系还是很好理解的，它们的关系我本来想画个图表示下的，觉得有点麻烦，何况也不难，我就不画了。。直接进代码了哈~
在进行之前呢，先介绍两 篇文章，是一个网友写的。之前和他聊cfs，后来我迷糊了，他没迷糊，就写了这篇文章。。。还不错。
Linux进程管理之CFS调度器分析
Linux进程管理之CFS组调度分析
大家的理解差不多，他写得很条理，为了防止雷同，雷着大家了，我不会引用它里面的文字的。我就在边读代码的过程中边把自己的体验和疑惑贴出来，大家一同讨论吧~ 错误，一定要指出我的错误啊~呵呵
咱们先从新创建的一个进程说起吧。
1) kernel/fork.c里,fork routine,do_fork() will create a new process,if its state is running,it will
call wake_up_new_task() to wake up the newly created process FOR THE FIRST TIME.
do_fork(){
...
if (unlikely(clone_flags & CLONE_STOPPED)) {
...
} else {
wake_up_new_task(p, clone_flags);
}
...
}
2) 这个函数做什么呢？
void wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
{
unsigned long flags;
struct rq *rq;
rq = task_rq_lock(p, &flags);顺序操作运行队列
BUG_ON(p->state != TASK_RUNNING);
update_rq_clock(rq);
p->prio = effective_prio(p); 计算priority,,普通进程的priority就是static priority
if (!p->sched_class->task_new || !current->se.on_rq) {如果条件不满足，直接入列，但请注意active_task()的最后参数0，不唤醒
activate_task(rq, p, 0);
} else {
/*
* Let the scheduling class do new task startup
* management (if any):
*/
p->sched_class->task_new(rq, p);调用完全公平类里面的task_new做些初始化的操作。
inc_nr_running(rq);增加运行队列的运行进程数目
}
trace_sched_wakeup_new(rq, p);
check_preempt_curr(rq, p, 0); 可不可以抢占当前进程？
#ifdef CONFIG_SMP
if (p->sched_class->task_wake_up)
p->sched_class->task_wake_up(rq, p);
#endif
task_rq_unlock(rq, &flags);
}
3) 先看task_new()吧，它会掉到fair_sched_class类里的task_new_fair.
static void task_new_fair(struct rq *rq, struct task_struct *p)
{
struct cfs_rq *cfs_rq = task_cfs_rq(p);
struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
int this_cpu = smp_processor_id();
sched_info_queued(p);
update_curr(cfs_rq); 更新cfs的一些信息
place_entity(cfs_rq, se, 1);初始化se在cfs里的信息，包括vruntime
/* 'curr' will be NULL if the child belongs to a different group */
if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
curr && curr->vruntime < se->vruntime) {
/*
* Upon rescheduling, sched_class::put_prev_task() will place
* 'current' within the tree based on its new key value.
*/
swap(curr->vruntime, se->vruntime);
resched_task(rq->curr);
}
enqueue_task_fair(rq, p, 0); 放进队列里面
}
4) 我们先看update_curr()吧
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_of(cfs_rq)->clock;
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);计算自上次调度此进程到这次又调度，经过的时间
这个时间比较鬼异，是多久呢？假如在运行队列里的n个进程之一的a,再一次被调度到时，这个delta_exec是多大呢？ 如果中途有进程退出或睡眠，
那么运行队列会动态更新的，所以这个delta_exec的变化曲线是什么样子的难说。
__update_curr(cfs_rq, curr, delta_exec); 把刚计算出来的运行时间作为参数传进去，它做什么事情呢？
curr->exec_start = now;呵呵，更新完了立刻打个时间戳。
if (entity_is_task(curr)) { 这个条件比较有趣，我喜欢。跟过去发现是这样定义的：
"/* An entity is a task if it doesn't "own" a runqueue */
#define entity_is_task(se) (!se->my_q) " 如果是组调度，调度实体可能代表一个组，不单单是一个task。就是看看有没有my_q这个指针了，
即有没有它control的cfs_rq
如果是task,条件满足，
struct task_struct *curtask = task_of(curr);
cpuacct_charge(curtask, delta_exec);
account_group_exec_runtime(curtask, delta_exec); 这两 个不管了，看不懂
}
} |
评分
-
查看全部评分
|
免费注册
发表于 2009-03-02 14:52
发表于 2009-03-02 15:05
