注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

火车的家

Put first thing first

 
 
 

日志

 
 

2012.11.23 [转] linux CFS 完全公平调度器  

2012-11-23 10:04:04|  分类: linux kernel |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

link 本文取自这篇文章的 3.3节,在原文基础上做了修改。

CFS 是最终被内核采纳的调度器。它不再跟踪进程的睡眠时间,也不再企图区分交互式进程。它将所有的进程都统一对待,这就是公平的含义。CFS的算法和实现都相当简单,众多的测试表明其性能也非常优越。

假设runqueue中有n个进程,当前系统运行了10ms。在“完全理想的多任务处理器”中,10ms应该平分给n个进 程(不考虑各个进程的nice值),因此当前进程应得的时间是(10/n)ms,但是它却运行了10ms。所以CFS将惩罚当前进程,使其它进程能够在下 次调度时尽可能取代当前进程。最终实现所有进程的公平调度。下面将介绍CFS实现的一些重要部分,以便深入地理解CFS的工作原理。

CFS如何实现pick next

CFS 使用红黑树选取下一个被调度进程。所有状态为RUNABLE的进程都被插入红黑树。在每个调度点,CFS调度器都会选择红黑树的最左边的叶子节点作为下一个将获得cpu的进程。

tick中断

在CFS中,tick中断首先更新调度信息。然后调整当前进程在红黑树中的位置。调整完成后如果发现当前进程不再是最左边 的叶子,就标记need_resched标志,中断返回时就会调用scheduler()完成进程切换。否则当前进程继续占用CPU。从这里可以看到 CFS抛弃了传统的时间片概念。Tick中断只需更新红黑树,以前的所有调度器都在tick中断中递减时间片,当时间片或者配额被用完时才触发优先级调整 并重新调度。

红黑树键值计算

理解CFS的关键就是了解红黑树键值的计算方法。该键值由三个因子计算而得:一是进程已经占用的CPU时间;二是当前进程的nice值;三是当前的cpu负载。

进程已经占用的CPU时间对键值的影响最大,其实很大程度上我们在理解CFS时可以简单地认为键值就等于进程已占用的 CPU时间。因此该值越大,键值越大,从而使得当前进程向红黑树的右侧移动。另外CFS规定,nice值为1的进程比nice值为0的进程多获得10%的 CPU时间。在计算键值时也考虑到这个因素,因此nice值越大,键值也越大。

CFS为每个进程都维护两个重要变量:fair_clock和wait_runtime。在本文中,我们将为每个进程维护的变量称为进程级变量,为每个CPU维护的称作CPU级变量,为每个runqueue维护的称为runqueue级变量。

进程插入红黑树的键值即为 fair_clock – wait_runtime。

fair_clock从其字面含义上讲就是一个进程应获得的CPU时间,即等于进程已占用的CPU时间除以当前 runqueue中的进程总数;wait_runtime是进程的等待时间。它们的差值代表了一个进程的公平程度。该值越大,代表当前进程相对于其它进程 越不公平。

对于交互式任务,wait_runtime长时间得不到更新,因此它能拥有更高的红黑树键值,更靠近红黑树的左边。从而得到快速响应。

红黑树是平衡树,调度器每次总最左边读出一个叶子节点,该读取操作的时间复杂度是O(LgN)。

调度器管理器

为了支持实时进程,CFS提供了调度器模块管理器。各种不同的调度器算法都可以作为一个模块注册到该管理器中。不同的进程 可以选择使用不同的调度器模块。2.6.23中,CFS实现了两个调度算法,CFS算法模块和实时调度模块。对应实时进程,将使用实时调度模块。对应普通 进程则使用CFS算法。Ingo Molnar还邀请Con Kolivas可以将RSDL/SD写成一个调度算法模块。

CFS源代码分析

Sched.c中scheduler_tick()函数会被时钟中断直接调用。它首先更新runqueue级变量 clock;然后调用CFS的tick处理函数task_tick_fair()。task_tick_fair在sched_fair.c中。它主要的 工作是调用entity_tick()

函数entiry_tick源代码如下:

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) 
{
struct sched_entity *next;

dequeue_entity(cfs_rq, curr, 0);
enqueue_entity(cfs_rq, curr, 0);

next = __pick_next_entity(cfs_rq);
if (next == curr)
return;

__check_preempt_curr_fair(cfs_rq, next, curr, sched_granularity(cfs_rq));
}
首先调用dequeue_entity()函数将当前进程从红黑树中删除,再调用enqueue_entity()重新插 入。这两个动作就调整了当前进程在红黑树中的位置。_pick_next_entity()返回红黑树中最左边的节点,如果不再是当前进程,就调用 _check_preempt_curr_fair。该函数设置调度标志,当中断返回时就会调用schedule()进行调度。

函数enqueue_entity()的源码如下:

enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup) 
{
/*
* Update the fair clock.
*/
update_curr(cfs_rq);
if (wakeup)
  enqueue_sleeper(cfs_rq, se);
update_stats_enqueue(cfs_rq, se);
__enqueue_entity(cfs_rq, se);
}
它的第一个工作是更新调度信息。然后将进程插入红黑树中。其中update_curr()函数是核心。完成调度信息的更新。
static void update_curr(struct cfs_rq *cfs_rq) 
{
struct sched_entity *curr = cfs_rq_curr(cfs_rq);
unsigned long delta_exec;
if (unlikely(!curr))
return;

delta_exec = (unsigned long)(rq_of(cfs_rq)->clock - curr->exec_start);
curr->delta_exec += delta_exec;
if (unlikely(curr->delta_exec > sysctl_sched_stat_granularity)) {
__update_curr(cfs_rq, curr);
curr->delta_exec = 0;
}

curr->exec_start = rq_of(cfs_rq)->clock;
}
该函数首先统计当前进程所获得的CPU时间,rq_of(cfs_rq)->clock值在tick中断中被更 新,curr->exec_start就是当前进程开始获得CPU时的时间戳。两值相减就是当前进程所获得的CPU时间。将该变量存入 curr->delta_exec中。然后调用__update_curr()
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr) 
{
unsigned long delta, delta_exec, delta_fair, delta_mine;
struct load_weight *lw = &cfs_rq-load;
unsigned long load = lw->weight;
delta_exec = curr->delta_exec;
schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
curr->sum_exec_runtime += delta_exec;
cfs_rq->exec_clock += delta_exec;
if (unlikely(!load))
return;
delta_fair = calc_delta_fair(delta_exec, lw);
delta_mine = calc_delta_mine(delta_exec, curr->load.weight, lw);
if (cfs_rq->sleeper_bonus > sysctl_sched_min_granularity) {
delta = min((u64)delta_mine, cfs_rq->sleeper_bonus);
delta = min(delta, (unsigned long)(
(long)sysctl_sched_runtime_limit - curr->wait_runtime));
cfs_rq->sleeper_bonus -= delta;
delta_mine -= delta;
}
cfs_rq->fair_clock += delta_fair;
add_wait_runtime(cfs_rq, curr, delta_mine - delta_exec);
}
__update_curr()的主要工作就是更新前面提到的fair_clock和wait_runtime。这两个值 的差值就是后面进程插入红黑树的键值。变量Delta_exec保存了前面获得的当前进程所占用的CPU时间。函数calc_delta_fair()根 据cpu负载(保存在lw变量中),对delta_exec进行修正,然后将结果保存到delta_fair变量中,随后将fair_clock增加 delta_fair。函数calc_delta_mine()根据nice值(保存在curr->load.weight中)和cpu负载修正 delta_exec,将结果保存在delta_mine中。根据源代码中的注释,delta_mine就表示当前进程应该获得的CPU时间。

随后将delta_fair加给fair_clock而将delta_mine-delta_exec加给 wait_runtime。函数add_wait_runtime中两次将wait_runtime减去delta_mine-delta_exec。由 于calc_delt_xx()函数对delta_exec仅做了较小的修改,为了讨论方便,我们可以忽略它们对delta_exec的修改。最终的结果 可以近似看成fair_clock增加了一倍的delta_exec,而wait_runtime减小了两倍的delta_exec。因此键值 fair_clock-wait_runtime最终增加了一倍的delta_exec值。键值增加,使得当前进程再次插入红黑树中就向右移动了。

CFS小结

以上的讨论看出CFS对以前的调度器进行了很大改动。用红黑树代替优先级数组;用完全公平的策略代替动态优先级策略;引入 了模块管理器;它修改了原来Linux2.6.0调度器模块70%的代码。结构更简单灵活,算法适应性更高。相比于RSDL,虽然都基于完全公平的原理, 但是它们的实现完全不同。相比之下,CFS更加清晰简单,有更好的扩展性。

CFS还有一个重要特点,即调度粒度小。CFS之前的调度器中,除了进程调用了某些阻塞函数而主动参与调度之外,每个进程 都只有在用完了时间片或者属于自己的时间配额之后才被抢占。而CFS则在每次tick都进行检查,如果当前进程不再处于红黑树的左边,就被抢占。在高负载 的服务器上,通过调整调度粒度能够获得更好的调度性能。

  评论这张
 
阅读(662)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017