鼠眼再看Linux调度器［1］ 【转】

一、回顾。

上次鼠眼初看Linux调度器时已有一年有余的光景了。这一年多的时间里，Linux内核中许多地方发生了重要的变化，比如引进了KVM等。相对而言，任务调度这部分变动算是非常小了：其中比较显著的就是增加了优先级继承支持。但若仅有这些变动的话，从量上还不足以撑起这样一篇文章。

在LKML（Linux Kernel Mail List）上，前阵子有过几个回合关于任务调度的热烈讨论：CFS vs RSDL/SD。CFS，即“完全公平调度”，这种方法彻底以时间和系统负载作为参照，完全抛弃了原有调度方案中的双优先级数组、甚至时间片的概念。RSDL/SD是我们上次介绍的Staircase调度的演化版本。我们以介绍CFS的工作过程为主，不对两者妄加评论。两者都在快速发展过程中，尤其是CFS，在4月中旬发布出第一个版本后，经过许多大侠的助力，已日趋稳定，截止到5月中旬它就有十多个版本的迭代了，当然，这也是Linux开发模型中的尽早发布特点所导致的一个必然现象。

如果功利一点，从实用的角度上看，只分析学习已经纳入正式内核的代码是最经济的，因为它最有可能是为工作所用。但是，如果从学习积累的角度上看，更早地参与到某项技术本身的开发过程中，或者退一步说只是关注某项新技术的从幼小到成熟的成长过程，将更有利于我们彻底掌握它。我以为CFS和RSDL都是值得我们关注的目标。但本文只关注CFS的实现，因为看起来它比RDSL/SD更有前途一些。

我想有必要重申一下为什么是“鼠眼看X”？我的本意是文章中不会有太深的技术内容，尽量使“知其所以然/阅读难度”的比值大些。再有，在简化代码时我只保留与主功能逻辑直接相关的部分，但是我只删代码而不修改原有代码，这样既有利于抓住核心环节缩减篇幅，又不妨碍有兴趣的读者顺着这些线索亲自“咀嚼”代码。

OK，这次“再看”的文章，内容包括2.6.21.1内核中任务调度的实时扩展，模块化调度功能的支持，和关于CFS v15/2.6.21.1上调度的一些探讨。

在切入正题之前，容俺先向各位说声抱歉：上次＜＜鼠眼看Linux调度器＞＞内有处错误：“linuxthreads线程库实现的是N对1模型”。实际上，它实现的也是N对N的线程模型，我也是后来分析了C库这部分代码才知道的，这又一次充分证明了“道听途说”不可信，实践才能出真知呀！

二、实时扩展。

“温故以知新”，我们先简单复习一下以前Linux调度器内部是如何工作的：Linux在调度任务时主要依靠两个优先级参数：1、静态优先级。“静态”得名于内核从不主动修改它，对于普通任务它被初始化为优先级中值120（最小100，最大140），只有通过系统调用才会修改它。内核在计算时间片、判断任务的交互性、计算动态优先级时都要直接或间接地使用到它，可以将它看成任务的“本性”；2、动态优先级。Linux任务是不能直接接触到这种优先级的，内核根据任务的平均休眠时间判断其交互特征进而计算出动态优先级。交互性强的任务会得到更高的优先级。特别提醒一下：此前内核也是支持一定的实时特征的，主要支持设施有三个：SCHED_FIFO和SCHED_RR调度策略和抢占式调度。

首先，现在任务默认的时间片轮转调度和优先级调度混合的调度策略，已经从“SCHED_OTHER”更名为“SCHED_NORMAL”，但没有策略本身没有发生什么本质变化。呵呵，它总算有了一个名正言顺的名份。“静态优先级”的处理也没有发生什么变化。它的处理流程几乎和我们上次介绍的一模一样，但在动态优先级的处理上有了一些改进，主要是源于一种叫做“优先级继承（PI）协议”的机制。

在这里详细讨论“优先级继承协议”的来龙去脉是不可能的，在文章最后我列出一些参考材料供有兴趣的读者深入阅读。这里只简单介绍一下它的概念。试想有这样两个任务：低优先级任务L、和高优先级的任务H，而且两个任务都需要访问一块共享的临界区（资源）。正常情况下，任务H是要比任务L优先执行的。为了保持临界区内数据的完整性，需要在两者之间进行同步，最常用的手段就是使用信号量。通俗地说，临界区它就好像一间单人密室，同时只允许有一个人身处其中，而进去的人会关上门。这样外人只有在里面没有人时才有可能打开门进入密室。再假定任务L首先成功拿到了信号量，如果任务L在释放信号量之前由于某种原因进入休眠状态，而此时任务H若试图获取信号量，就只能也休眠过去等待任务L释放信号量了。这样，就形成了一条畸形的依赖链：高优先级的任务H通过信号量等候低优先级任务L的运行一段时间后才有可能继续。再试想，如果有更多的任务和信号量参与到其中这将是一个何等糟糕的情形。事实上，“依赖链”有可能演变成为“依赖树”、“依赖图”，甚至形成“依赖环”。这种现象有个文绉绉的学名，“优先级反转”。“优先级反转”当然不是世界末日，问题的核心在于临界区（资源）访问的排它性。基本的解决方案有四种：临界区的无锁访问算法，临界区的不可抢占访问协议、优先级继承协议、优先级顶置（Priority Ceiling）协议：

临界区的无锁访问算法。这种方法回避了资源访问的排它性，干脆就把资源同步机制给跳过去了。但很遗憾，它只能用在有限的特殊情况下，即使是这样它还有实现复杂等限制。如此看来，无锁访问肯定不是“瑞士军刀”了。

临界区的不可抢占访问协议，它可能是最简单的资源控制协议了。如果是这种方法，上面的任务L在获得信号量之后，释放信号量之前的时间间隔里是不能休眠的。这样，也就不会给任务H中间试图取得信号量机会了。本质上，这样的访问就是原子性的了。这个方法虽然简单的，但是也有致命的缺陷－－打击面过宽：此时它也剥夺了与该信号量无关的其他所有任务的运行机会，这可不是一个好消息，并且，也不适用于多处理器的情况，这在连PC计算也日趋并行化的今天就更是与现实格格不入了。

优先级继承协议，这是四个解决方案最为复杂的一种，应用于以上例子，在任务L获取信号量再因故休眠之后，如果任务H也试图获取相同的信号量，任务H仍然也要休眠。但不同的是任务L的动态优先级需要调整为任务H的动态优先级。这样，任务L就会以“高姿态”更快地再次得到处理器资源，完成对该资源的访问，从而给任务H快速复苏的可能。当任务H不再等待任务L所占有的资源时，任务L还要恢复原始的优先级。乍一听起来这似乎并不困难，是不是？但是不要高兴的太早，试想象一下有多个任务参与进来的情形，更复杂地，再加入多个信号量时的情形呢？你可能已经猜到了，优先级继承过程必须是可传递的！稍后回过头来再次分析优先级继承时，你就知道了，这恐怕也不是一个什么好消息～

优先级顶置协议，有时也称“回避阻塞（Avoidance Blocking）”，本质上这是一种将临界区（资源）优先级化的方法。在具体实现时，往往优先级化的是代表资源出现的某种同步机制，例如信号量。某任务在获得该资源后，它的优先级就提升到该资源的优先级上。它与“优先级继承协议”的最根本的区别在于，它不是贪心的，作为一个副作用，它的效果可能差于“优先级继承协议”－－可能延长引起不必要的休眠时间。但是，它可以做到“优先级继承协议”所不能的：避免死锁。

　　OK，回到“优先级继承协议”的讨论上。我们想想如果自己实现优先级继承协议需要哪些工作？嗯，肯定需要在信号量上加一个等待队列，它保存有等待获取该信号量的任务们。我们在继承和恢复优先级时是一个台阶式的调整过程：“当权”的资源占用者总是以等待者中的最高优先级运行，下一届“当权者”就以剩余等待者的最高优先级运行。嗯，看起来，我们更需要一个按优先级排好序，而不是按休眠时间排序的链表。这个特征还有一个推论：实现“优先级继承协议”不单单是调度算法自身的问题，还需要相应资源同步机制的配合。这样，内核中的新同步工具rt_mutex就出场了。而rt_mutex的成员wait_list，就是我们所需的按优先级排序的等待队列。

但是只有上述信号量上的一个链表还不够。想像这种情况：一个任务同时持有多个信号量的情形。此时信号量持有者的正确行为肯定是使用各信号量中优先级最高的等待者的优先级运行。这样，就形成了等待者跨信号量竞争最高优先级的局面。虽然这仍然是一个优先级排序的问题，但这个链表应该设置在任务结构上了。我们有两个选择：是链接信号量，还是直接链接每个信号量的最高优先级等待者。Linux选择了后者，这便是task_struct（它代表一个Linux任务）中新成员pi_waiters的出处了。

链表wait_list或pi_waiters，它们的共性都是按优先级排序。内核为此抽象出了一个新的数据结构：plist。plist的实现还是非常直接的，它的API也故意地设计成与Linux双链表相似，比如检查链表是否为空的API名字就是plist_head_empty()。这里不再详细解释它的实现，如果你想看看它的实现，下面是几点可能有用的提示：与标准Linux双链表不同，plist是区分链表头和一般链表结点的；第二，plist其实是两个双链表的组合，目的是为了在遍历优先级时减少处理重复优先级所浪费的时间；最后，优先级是按从高至低排序的。

OK，虽然有些线性表实现的操作我们可以做到O(logn)时间复杂度，但设计者们在这里采用了非常直接的实现方案，它们仍是O(n)时间复杂度。上面说到“优先级继承”有一个“传递性”的特征，若有大量任务参与到“优先级反转”，就有可能会造成严重的性能问题。为此，内核在调整优先级链的时候，施加了一个实现限制：最大优先级链长度（运行时可配置，默认为1024）；再有，经过精心设计，内核在处理优先级继承时最多只会同时使用两把内核（自旋）锁。

无论是什么时候，数据结构始终都是程序的灵魂。我们还是从task_struct结构有关成员说起吧：

task_struct->prio

task_struct->static_prio

它们分别是任务的动态优先级和静态优先级。

粗略地说，Linux上有140个优先级可供任务使用，数值越小的优先级，优先级越高。100以下的优先级被用于实时任务，即使用调度策略SCHED_FIFO和SCHED_RR的任务。这样，它们始终会比普通策略（SCHED_NORMAL和SCHED_BATCH）要优先一些。

动态优先级在数值可能不同于静态优先级，可能的原因有：

1、内核根据任务的平均休眠时间判断其交互特征进而得出动态优先级。这个工作是由recalc_task_prio()函数完成的。

2、由于优先级继承的原因，它们通过rt_mutex阻塞了更高优先级的任务而得到提升，但只适用于优先级值小于100的实时任务。优先级继承过程本身是由__rt_mutex_adjust_prio()完成。

task_struct->normal_prio

我们已经知道：“优先级继承协议”可能会临时提升任务的优先级。但提升完后应该立即返回到其应有的优先级上。这个成员保存的正是这个“应有的优先级”，即，没有优先级继承影响时的优先级，我们姑且称之为“常规动态优先级”。

task_struct->rt_priority

对于实时任务（具有策略SCHED_FIFO和SCHED_RR），即使是动态优先级，内核也是不作主动调整的。具体的调整方案完全由系统调用sched_setscheduler()控制，rt_priority保存的就是这个系统调用设置的优先级参数，它与实时任务的动态优先级成线性对应关系。其取值范围是0至99。

OK，该是看看代码的时间了，沿用我们上次看代码的方式：

static int effective_prio(struct task_struct *p)
{
1>p->normal_prio = normal_prio(p);
2>if (!rt_prio(p->prio))
return p->normal_prio;
3>return p->prio;
}


1. 调用normal_prio()，计算常规动态优先级。

2. rt_prio()其实就是检查任务的优先级是不是小于100。如果不满足这个检查条件，就表明这个任务不是实时任务，直接返回刚才计算好的常规动态优先级，也即，如果不是实时任务就不能利用“优先级继承协议”。

3. 如果是实时任务，就是直接返回其真正的动态优先级p->prio。不作任何修改。那么这个优先级又是怎么设置的呢？答案是要么由上述的sched_setscheduler()调整，要么就是通过优先级继承协议调整的。

static inline int normal_prio(struct task_struct *p)
{
int prio;

1>if (has_rt_policy(p))
prio = MAX_RT_PRIO-1 – p->rt_priority;
else
2>prio = __normal_prio(p);
return prio;
}

1. has_rt_policy(p)，是检查任务p是不是实时任务的另一种方法。如果是，就按99 – p->rt_priority的公式计算动态优先级：rt_priority值越大，实时任务的优先级越高。
2. 否则，就调用__normal_prio()计算真正的常规动态优先级。

static inline int __normal_prio(struct task_struct *p)
{
int bonus, prio;

bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;

prio = p->static_prio - bonus;
if (prio < MAX_RT_PRIO)
prio = MAX_RT_PRIO;
if (prio > MAX_PRIO-1)
prio = MAX_PRIO-1;
return prio;
}

上次一同看过Linux调度器的朋友，可能对这个函数有些眼熟。对了，它与以前的effective_prio()不差分毫。为了叙述上的完整性，我再简单叙述一下此中原委。上文提到这样两个线索：内核会根据任务的平均休眠时间判断得出动态优先级；在计算动态优先级时内核还要使用静态优先级作为依据。这里计算得出的bonus变量值，保存的就是根据平均休眠时间得出的动态优先级与静态优先级之间的差值，其值在-5和+5之间。prio，就是真正的常规动态优先级了。函数返回之前两个条件语句做了一些必要的边界值检查。

static void __rt_mutex_adjust_prio(struct task_struct *task)
{
1>int prio = rt_mutex_getprio(task);

2>if (task->prio != prio)
rt_mutex_setprio(task, prio);
}

在内核需要对一个任务进行优先级继承调整时，就会调用rt_mutex_adjust_prio()，但是它只是__rt_mutex_adjust_prio()的一个wrapper，真正的工作是由后者完成的。那么，内核都在哪些情况下调用了rt_mutex_adjust_prio()呢？只有两种情况，对rt_mutex进行加锁和解锁时。我们可以知道，一个高优先级任务在对rt_mutex加锁而不成进入休眠时，它可能会导致该rt_mutex的持有者任务的优先级提升。反之，rt_mutex的持有者任务在释放它时，也可能因为它被提升过优先级的缘故而需要恢复原优先级。所以，rt_mutex_adjust_prio()的工作其实应该有两种：要么优先级提升（boosting），要么降级（unboosting）。再来看代码：

1. rt_mutex_getprio() 即返回适合任务的优先级：若有优先级继承发生，就是返回提升过的优先级。否则，返回“常规动态优先级”。

2. 如果这个优先级与现有优先级不同，就设置调用rt_mutex_setprio()新优先级。再次注意，这里只对两者进行了不等比较，而没有进行大小比较。

int rt_mutex_getprio(struct task_struct *task)
{
1>if (likely(!task_has_pi_waiters(task)))
return task->normal_prio;

2>return min(task_top_pi_waiter(task)->pi_list_entry.prio,
task->normal_prio);
}

1. 函数task_has_pi_waiters(task)的实现很直接，就是“return !plist_head_empty(&task->pi_waiters);”。即判断是否有其他任务等待task所持有的rt_mutex。如果没有，那就根本不存在优先级继承的可能，便直接返回“常规动态优先级”了。

2. 理解这个返回语句需要一些背景，但几乎所有需要的知识点我们都涉及到了。首先，内核管理优先级时是数值越小，优先级越高，因而这里的min()调用，实际上是找出哪个优先级更高些。task_top_pi_waiter(task)的内部实现其实就是取等待队列task->pi_waiters中第一个任务。也就是持有最高优先级的等待任务。因为这个等待队列是按优先级从高到底排好顺序的，我们只需要得到第一个任务就足够了。所以，这条语句实际上是在比较可能的继承优先级和“常规动态优先级”，我们当然不希望优先级继承还会使rt_mutex持有任务的优先级削弱。所以，只返回较高（数值较小）的那个。


void rt_mutex_setprio(struct task_struct *p, int prio)
{
struct prio_array *array;
unsigned long flags;
struct rq *rq;
int oldprio;

1>rq = task_rq_lock(p, &flags);

oldprio = p->prio;
2>array = p->array;
if (array)
dequeue_task(p, array);
p->prio = prio;

if (array) {
/*
* If changing to an RT priority then queue it
* in the active array!
*/
3>if (rt_task(p))
array = rq->active;
enqueue_task(p, array);
/*
* Reschedule if we are currently running on this runqueue and
* our priority decreased, or if we are not currently running on
* this runqueue and our priority is higher than the current's
*/
4>if (task_running(rq, p)) {
if (p->prio > oldprio)
resched_task(rq->curr);
} else if (TASK_PREEMPTS_CURR(p, rq))
resched_task(rq->curr);
}
task_rq_unlock(rq, &flags);
}


严格地说，这个函数与rt_mutex关系并不大，其它任何原因想修改任务的优先级了，都可以使用这个函数。通过分析rt_mutex_setprio()可以窥探出Linux是如何组织任务的，为稍后将要介绍CFS调度作一些铺垫。我摘出四个关键点：

1. 在linux上，每个处理器（也包括超线程意义上的逻辑处理器）都对应到一个运行队列。这么安排既有性能上的考虑，也有功能上的原因：性能上，如果系统内所有的处理器都共享一个运行队列，看似简单却有极大的性能隐患。因为极有可能多个处理器需要同时或几乎同时在运行队列上插入／删除任务，此时，为了保证运行队列的完整性，就必须有某种全局同步机制强迫这些操作串行化，例如自旋锁。显而易见，这不是个好主意。功能上，分开对待每个处理器，在实现负载均衡时也非常自然，也利于进一步抽象。每个struct rq表示的就是一个运行队列／处理器。不过，由于支持抢占的原因，即使是每个处理器对应一个运行队列，仍然需要有同步机制保护其操作的一致性，但它所影响的却只限于一个处理器了。task_rq_lock()的作用就是获取指定任务所在的运行队列的访问权。在整个函数结束时，还调用了task_rq_unlock()来归还访问权。

2. dequeue_task()将任务从运行队列上摘掉。之所以要先摘掉，是因为Linux上每种任务优先级都有一个小运行队列。所以，改变了任务的动态优先级就应该将它移动到其它小运行队列中去。概念上，rq其实是对应了这样一套小运行队列。但实际情况更为复杂，rq其实是包括了两套这样的小运行队列。任务结构task_struct->array就保存了这个任务处哪套小运行队列上。

3. 上述两套子运行队列，一个叫做活动队列（rq->active）；另一个叫做过期（expired）队列。调度器只会从活动队列中摘取任务，并且适时切换两者。经过这个分支的处理，enqueue_task()就优先将实时任务放入到活动队列，从而缩短它的实际等待时间。这样，运行队列实际分三层：处理器运行队列 -> 活动/过期队列 -> 每优先级运行队列。

4. 其实这条分支语句之上的注释已经将道理写的很明白了，我简单地翻译一下：如果这个任务正在这个运行队列上运转，并且我们是在削弱它的优先级的话，就给其他可能的任务机会占用处理器（即所谓的reschedule）；如果这个任务的优先级高于运行队列上当前任务，就让其让出处理器。

文已过半，我想大家大概应该清楚了“优先级继承协议”对Linux调度器的影响。但为什么这个章节叫做“实时扩展”，而不是直接了当的“优先级继承协议的Linux实现”呢？首先，文不对题，因为本文的侧重介绍Linux调度器的，并没有介绍优先级继承协议实现细节。细心的读者也一定已经注意到，优先级继承这个功能只能在所谓的实时任务内使用（参见对effective_prio()的解释）。实际上rt_mutex中的rt正是realtime（实时）的缩写。那为什么控制“优先级反转”现象对于实时任务又如此重要呢？虽然还没有一个准确的定义刻划“实时”概念，但它绝不是说程序只要运行得越快就越好，甚至在有些情况下，过快地反应速度反而不是我们所期待的。既不能快，更不能慢的响应速度，我们实际上就是在要求有可预测的“响应时间”。一个实际系统内有各种各样的因素干扰能够可预测性，“优先级反转”尤其会使其更加恶化。所以，“优先级继承协议”在各种实时系统得到了广泛实现。最后，即使是有了“优先级继承协议”这样强悍的功能，标准的Linux仍然还不能提供公认的“硬实时特征”，现在似乎也只有RTAI／RT-Linux可以提供了这样的特性。RTAI也是一个稳步发展地开源软件，实现了EDF、RMS实时调度算法，它和其底层支持软件Adeos也都很有意思，非常值得研究学习。

三、模块化调度。

在软件工程上，“模块化”是实现“信息隐藏”的重要手段，已经获得广泛应用，不过它在调度器上可算是半个少见的例外。就是否和如何在Linux内核中加入模块化调度功能的支持，在社区内是个争论已久的话题。支持派的代表意见是提供这样的功能可以给用户选择它们所需的个性化调度器，提高系统的灵活性。反对派的意见是内核应该提供一个“十全十美”的内核，不应该将责任推卸到用户身上。退一步讲就是在如何加入这个功能上，社区内也是有分歧的，是提供运行时模块化功能还是仅编译开发时呢？这两种方法现在都有实现。

我们只简单介绍一下与CFS补丁密切相关的“调度类”功能，Ingo实现了两个“调度类”：一个sched_fair，一个sched_rt。前者实现了我们就要介绍的CFS（包括调度策略SCHED_NORMAL和SCHED_BATCH），后者实现了软实时调度（包括策略SCHED_RR和SCHED_FIFO）。这两个调度类静态（编译时）嵌入到调度核心代码里，有了它们以后，我们就不再需要在调度核心里掺杂具体的策略方面的内容了，但我们仍不能在运行时插入、删除调度类。因而从功能上看“调度类”的更多的是简化调度代码，并没有给最终用户带来多大的“实惠”。

我们只扫描一下“调度类”的数据结构，不再详细解释它的实现细节了：

struct sched_class {
void (*enqueue_task) (struct rq *rq, struct task_struct *p,
int wakeup, u64 now);
void (*dequeue_task) (struct rq *rq, struct task_struct *p,
int sleep, u64 now);
struct task_struct * (*pick_next_task) (struct rq *rq, u64 now);
void (*task_tick) (struct rq *rq, struct task_struct *p);
/* ...... */
};

我们只选取了四个有代表性功能的结构成员：

enqueue_task()/dequeue_task()

这两个方法用于将任务插入至运行队列，或者从运行队列中删除任务。如果我们要在一个调度类内实现现有的调度方法，那么这两个函数的工作就是操作优先级数组。注意，这里的方法定义并没有对“运行队列”本身做任何假定。调度类可以用任何它需要的方法实现运行级别，直观上看，一个线性数据结构就够了，但实际上CFS选择了红黑树。

pick_next_task()

当调度核心需要从运行队列中取出一个任务占用处理器时，就调用这个函数。调用时机有两个：一种是出于某种原因当前任务要让出处理器时，调度核心需要让另一个任务占用处理器；还有一种情况是支持处理器热插拔时，把要离线处理器上的任务全部迁移到可用处理器上时。

task_tick()

这个函数在每次定时器中断时调用。在现有调度实现中，这个功能扮演了重要的角色，包括更新时间片，对任务交互性的一些启发式处理。

“调度类”的实现并没有多少难解之处，它为不同的调度方法抽象出一个系列虚拟方法，调度只要填上相应的方法实现就OK了。整个处理流程也仍是我们以前介绍过的套路：以定时器中断和以运行队列为中心。

<待续>