CFS进程调度_学习笔记

CFS，linux独特而神奇的进程调度算法，《Linux内核设计与实现》一书用了整整一章的篇幅来介绍这个算法，下面对CFS做简单整理

掌握思想

CFS的出发点是基于一个简单的理念：进程调度的效果应该如同系统具备一个理想中的完美多任务处理器。在这种系统中，每个进程将能获得1/n的处理时间。

这其实跟我们在操作系统课上所学的名目众多的调度算法还是有一些不同的，乍一看，好像CFS抛弃了极为重要的优先级，甚至也抛弃了最为基础的时间片，这看起来太不寻常了。

其实不是，所谓优先级的本质，在一定程度上也就是为了协调I/O消耗型和CPU消耗型两种进程的，即所谓的操作系统调度准则：

• 面向用户准则：
  • 周转时间短（从提交作业开始到作业完成为止这段时间） 带权周转时间=周转时间/系统为其服务时间
  • 响应时间快（用户提交请求开始到系统首次相应）
  • 截止时间保证（任务必须开始执行的最迟时间或必须完成的最迟时间）
  • 优先权准则
• 面向系统的准则：
  • 系统吞吐量高
  • 处理机利用率好
  • 各类资源平衡利用

其中面向用户准则当中有一条就是为了保证更好的用户交互性，而CFS正是为了这一点的。抛弃了进程间绝对的静态的优先级比较，CFS中为每一种进程分配完全公平的处理器时间，这样，CPU消耗型和I/O消耗型被分配了相同的处理器时间，而CPU消耗型的处理器时间用的较多，这样正好，但同时又保证了，I/O消耗型的进程虽然不常运行，但是一旦其相运行，那么由于其已经运行的时间比分配给他的处理器时间要低不少，那么一般情况下他就会抢占CPU消耗型的进程，从而保证了较好的用户交互性，这点上有点像动态时间片分配或者多级反馈队列的意思。

同时，CFS解决了UNIX中基于nice值的时间片分配算法中，由于低nice值的进程拥有较长的时间片，并且时间片是比较固定的而导致的一系列问题（进程调度的效果过分依赖nice值），而且CFS分离了nice值到时间片的映射与定时器节拍，CFS完全摒弃了时间片而是分配给进程一个处理器使用比重。通过这种方式，CFS保证了进程调度中能够有恒定的公平性，而将切换频率置于不断变动中。

了解实现

时间记账

代替时间片的家伙，是时间记账，CFS通过一个结构体来实现时间记账：

struct sched_entity {
 struct load_weight load; /* for load-balancing */
 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;
 u64 last_wakeup;
 u64 avg_overlap;
 u64 nr_migrations;
 u64 start_runtime;
 u64 avg_wakeup;
 u64 avg_running;
};

调度器的实体作为一个名为se的成员变量，潜入在进程描述符struct task_struct内。

具体的调度类：

static const struct sched_class fair_sched_class = {
 .next = &idle_sched_class,/*下一个为idle进程*/
 .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,
 .get_rr_interval = get_rr_interval_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
 .moved_group = moved_group_fair,
#endif
};

记账功能的实现：

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;
  /*获得从最后一次修改负载后当前任务所占用的运行总时间*/
 /*即计算当前进程的执行时间*/
 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);
 }
}

进程选择

CFS的进程选择是通过红黑树的辅助来完成的，主要函数有enqueueentity()、enqueue_entity()、dequeue_entity()、_ dequeue_entity()、rb_erase()等函数

 dengueue_entity():
static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
{
 /*
  * Update run-time statistics of the 'current'.
  */
 update_curr(cfs_rq);

 update_stats_dequeue(cfs_rq, se);
 if (sleep) {
#ifdef CONFIG_SCHEDSTATS
  if (entity_is_task(se)) {
   struct task_struct *tsk = task_of(se);

   if (tsk->state & TASK_INTERRUPTIBLE)
    se->sleep_start = rq_of(cfs_rq)->clock;
   if (tsk->state & TASK_UNINTERRUPTIBLE)
    se->block_start = rq_of(cfs_rq)->clock;
  }
#endif
 }

 clear_buddies(cfs_rq, se);

 if (se != cfs_rq->curr)
  __dequeue_entity(cfs_rq, se);
 account_entity_dequeue(cfs_rq, se);
 update_min_vruntime(cfs_rq);
}

__ dengueue_entity():
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
 if (cfs_rq->rb_leftmost == &se->run_node) {
  struct rb_node *next_node;

  next_node = rb_next(&se->run_node);
  cfs_rq->rb_leftmost = next_node;
 }

 rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}

engueue_entity():
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
 struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
 struct rb_node *parent = NULL;
 struct sched_entity *entry;
 s64 key = entity_key(cfs_rq, se);
 int leftmost = 1;

 /*
  * Find the right place in the rbtree:
  */
 while (*link) {
  parent = *link;
  entry = rb_entry(parent, struct sched_entity, run_node);
  /*
   * We dont care about collisions. Nodes with
   * the same key stay together.
   *//*key为被插入进程的vruntime*/
  if (key < entity_key(cfs_rq, entry)) {
   link = &parent->rb_left;
  } else {
   link = &parent->rb_right;
   leftmost = 0;
  }
 }

 /*
  * Maintain a cache of leftmost tree entries (it is frequently
  * used):
  */
 if (leftmost)
  cfs_rq->rb_leftmost = &se->run_node;

 rb_link_node(&se->run_node, parent, link);
 rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
}

CFS的运行队列布局是放在红黑树里面的，而这颗红黑树的排序方式是按照运行实体的vruntime来的。

CFS调度算法的核心是选择具有最小vruntine的任务。运行队列采用红黑树方式存放，其中节点的键值便是可运行进程的虚拟运行时间。CFS调度器选取待运行的下一个进程，是所有进程中vruntime最小的那个，他对应的便是在树中最左侧的叶子节点。实现选择的函数为pick_next_task_fair

vruntime标准化

随着系统的不断运行，进程的vruntime不断增长。如果溢出了怎么办呢？

cfs给cfs_rq也设置了一个vruntime（cfs_rq->min_vruntime），这个时钟有两个特性： 1)单调递增； 2)如果满足第1点，让它等于cfs_rq中最小的虚拟时钟。

（cfs_rq->min_vruntime一般情况下总是等于队列中最小的vruntime，不过下面会提到进程睡眠唤醒的情况，这时新唤醒的进程的vruntime可能小于cfs_rq->min_vruntime。而cfs_rq->min_vruntime并不会因此而减小，依然保持单调递增。）

选择进程时，总是以进程的vruntime与cfs_rq->min_vruntime之差来作为判断依据的。而这个差值基本上是不可能溢出的。这个差值被称作normalized vruntime（标准化的虚拟时钟）。

有了这个normalized vruntime，在进程enqueue/dequeue、或者是在cfs_rq间迁移、等情况下，进程的vruntime就有了统一的描述。

当进程dequeue时，其vruntime -= cfs_rq->min_vruntime。而当它再次enqueue时，vruntime += cfs_rq->min_vruntime（注意，两个cfs_rq可能不是同一个）。

调度器入口

CFS的调度器入口主要是schedule()函数

• 清除TIF_NEED_SCHED
• 判断一下当前进程应该被继续设置为TASK_RUNNING状态，如果不是的话就把它从运行队列中删除
• 看一下当前运行队列是否还有可运行进程，没有的话，调用idle_balance(cpu, rq)平衡负载
• 把当前进程放回运行队列，并设置当前进程的指针为空。
• 选择下一个进程作为当前进程
• 判断如果当前进程不等于选择的进程的话，就进行进程切换，执行swtich_to

睡眠和唤醒

linux的调度器一直认为，应该对交互式进程（也就是睡眠多的进程）给予奖励。区别于其他的情况，如果进程因为睡眠而dequeue，这时vruntime继续保持原值，并不做normalize。那么，等它被唤醒的时候，vruntime仍旧是一个较小的值，相当于得到了奖励。

但是，如果只是简单的不做normalize，睡眠进程由于得不到运行，其虚拟时钟不增长，那么一个进程就可以在漫长的睡眠之后，进行报复性的满载运行。这显然是不合理的。所以，进程在被唤醒之后，需要对其vruntime进行修正。

vruntime=max(vruntime, cfs_rq->min_vruntime - thresh)。

即，分两种情况：

1、如果进程只是短暂睡眠，其vruntime > cfs_rq->min_vruntime - thresh，则vruntime保持原样； 2、长时间睡眠，其vruntime <= cfs_rq->min_vruntime - thresh，则vruntime修改为cfs_rq->min_vruntime - thresh。

这里的thresh可以认为等于一个调度延迟。

抢占与上下文切换

如果只是靠每个进程主动放弃CPU，这是相当不明智的做法，所以，内核使用need_resched标志（在每个进程对应的thread_info结构体内）来表示进程是否需要被调度。当一个进程的时间片耗尽，或者有更高优先级的进程进入可执行队列，当前运行的进程对应的need_reched标志会被设置。

在内核即将要返回用户空间的时候，如果need_resched标志被设置，内核会在继续执行原来的进程之前调用调度程序，此时就会发生用户抢占。

要注意，用户抢占是发生在即将返回用户空间前，内核调用调度程序，重新选择一个更加合适的进程来运行（如高优先级），当然也可以是原来的程序。

总的来说，在以下情况下会发生用户抢占：

1、从系统调用返回用户空间。 2、从中断处理程序返回用户空间。

用户抢占并不是2.6内核的新特征，它只是一种进程调度的策略。内核返回用户空间后，每个进程有独立的4G虚拟空间，这时的进程调度并不会出现内核资源的争夺。

内核抢占

内核抢占是2.6内核的新特征，在之前的内核中，调度程序是不能调度正在运行在内核中的进程，即使时间片已经用完，只有在进程返回用户空间或者阻塞，才能进行进程的调度。在2.6内核中，内核提供了为高优先级进程抢占正在内核运行的进程的机会。但是，对于多个同时运行的进程，内核空间的资源的共享的。所以，内核在抢占并且调度进程的时候，必须要保证调度是安全的。所谓的安全，就是不会因为新进程的调度导致一些共享资源的错乱，

内核进程可以调用函数来禁止内核抢占，在禁止这段时间内，抢占是不允许的，这样也是保护内核共享资源的一种方法。

所以，内核抢占发生在以下时候：

1、当终端处理程序将要执行完毕，返回内核空间之前。 2、执行在可以抢占的代码的时候。 3、内核进程让出CPU后，如阻塞。

参考

http://blog.csdn.net/zzsfqiuyigui/article/details/7867580
http://blog.xuite.net/ian11832/blogg/23745751
http://hi.baidu.com/_kouu/item/055bd19af9f6b9dc1f4271d1
http://blog.csdn.net/bullbat/article/details/7164953
http://blog.csdn.net/dog250/article/details/5302848
《linux内核设计与实现》 Robert Love 机械工业出版社