第四章 进程调度

本章节讨论进程调度器，进程调度器是内核的子系统用于管理进程工作。 进程调度器将有限的处理器资源分配给系统的各个进程。它负责优化系统，并且让用户觉得所有的进程是在系统上同时运行的。

为了更好的利用处理器资源，我们假设系统中运行着多个进程，并且这些进程一直处于运行状态。如果系统中进程的数量超过了处理器的数量，那么某一时刻一定有一些进程不处于运行状态。这些进程等待运行，进程调度室必须决定下一刻哪些进程能够得到调度，在处理器上运行。

多任务

多任务操作系统能够同时运行多个进程，而不是只有一个。

  • 在单处理器机器上，给人的感觉就像多个进程同时运行(并行)。
  • 在多处理器机器上，多任务系统可以让多进程在不同的处理器上并行运行(需要注意并发和并行的区别)。

无论是单处理器还是多处理器，多任务系统都可以让进程阻塞或者睡眠。尽管这些进程还在内存中，但是是不了运行的。这些进程利用内核等待某些事件的到来。(键盘输入，网络数据，或者仅仅是等待固定的时间)

多任务处理器分为两类:

  • 协同式
  • 抢占式

抢占式多任务

linux和其他unix分支以及大多数的现代操作系统一样，都实现了基于抢占的多任务系统。在抢占式多任务中，调度器决定什么时候进程会终止运行以及新的进程开始运行。

  • 抢占: 无意识的挂起一个正在运行的进程
  • 进程时间片: 进程在被抢占前所能够运行的时间是提前分配好的
    • 通过管理时间片使得调度器能够做出全局的调度决定，这样可以防止某个进程独占处理器
    • 现在大多数的操作系统，时间片是通过某个函数动态计算的，并且可以通过系统配置
    • linux特有的”fair”调度器本质上不直接分配时间片，但是这种做法获得了意想不到的效果

协同式多任务

在协同式的多任务系统中，一个进程不会停止除非自己主动让出处理。这种主动让出处理器的行为叫做yielding，但是操作系统不能强制进程这么做。 这种做法的缺点是显而易见的:

  • 调度器不能做出全局的决定: 进程应该运行多长时间
  • 进程独占处理的时间可能超出用户的预期
  • 一个被挂起的进程不主动让出处理器可能会导致整个系统瘫痪

linux的进程调度器

从Linux在1991的第一个版本到后面的2.4内核版本，linux的进程调度器都是比较简单的。它的工作方式很容易理解，但是在多处理器或者多进程的场景下可扩展性和性能斗比较差。

在2.5内核版本汇总，O(1)调度器解决了之前调度器性能差的缺点，并且提供了一些强大的特性。通过一个时间复杂度为常量的时间片计算算法以及每个处理器有自己的运行队列，弥补了之前调度器的局限

但是o(1)调度器在调度低延迟（交互式）应用方面有一些致命的缺陷。因此尽管O(1)调度器对于缺少交互式进程的大型服务器是理想的选择，但是却不适合桌面系统。

从2.6内核版本开始，内核研发者引入了一些新的进程调度器，旨在解决O(1)调度在交互进程调度方面的性能问题。这些调度器中最显著的当属Rotating Staircase Deadline ，它介绍了公平调度的概念，这个概念来自排队理论。在内核2.6.23版本中，内核开发者鼓励人们使用Completely Fair Scheduler(CFS) 代替O(1)调度器。

这个章节讨论一些调度器设计的基础知识，并且会介绍这些知识是如何应用在CFS调度器中的。同时也会介绍O(1)调度器因为它的实现是经典的unix进程调度模型。

策略

策略是调度器的行为，用来决定什么时候哪个进程需要运行(原文是Policy is the behavior of the scheduler that determines what runs when. 感觉翻译的不是很准确!!)

IO密集型进程

进程可以划分为IO密集型和处理器（计算）密集型。

  • IO密集型进程花费大量的时间在提交IO请求和等待IO请求完成上。这样的进程只有很小的一段时间处于运行状态，因为大部分时间处于阻塞在IO的状态上。
    • I/O是一个统称，表示了任何的可能会引发阻塞的资源，比如键盘输入或者网络I/O，而不仅仅狭义的指磁盘I/0。多数的GUI应用程序都是I/O密集型的，即使这些程序不从磁盘读取任何数据，它们花费大量的时间用于等待用户通过鼠标或者键盘进行交互。
  • 计算密集型花费大量的时间用于执行代码。它们倾向于一直运行直到它们完成所有的计算，不会经常的阻塞在I/O上。系统不需要经常调度这些进程，但是需要在每次调度的时候多分配一些时间片。
    • 计算密集型的进程包括：一个执行死循环的程序，ssh-keygen(加密的程序), 或者MATLAB(可能同于大量矩阵运算)

I/O密集型和计算密集型相互之间是不排斥的，一个进程可能同时处于这两种状态:

  • X Window server既是计算密集型也是I/0密集型
  • word processor(文本处理器？)是I/O密集型的，但是在某一段时间有可能变为计算密集型

系统的调度策略试图满足两个看似矛盾的目标:

  • 更快的进程响应（低延迟）
  • 最大的系统利用率（高吞吐）

相对于计算密集型程序，系统更倾向于I/O密集型程序

调度器需要使用复杂的算法决定哪个进程是最值得调度的，而不是将高优先级进程和低优先级平等对待，丧失公平性。

  • unix系统的调度策略更倾向于I/O密集型进程，这样可以提供更好的响应时间
  • linux，旨在提供更好的交互和更好的桌面性能，因此相比于计算密集型更倾向于I/0密集型。

进程优先级

基于进程优先级的调度是常用的调度算法，这种算法不仅仅在Linux上实现。这种算法决定了高优先级的进程先于低优先级的进程运行，同优先级的进程通过round-robin进行调度。在某些系统上，高优先级的进程获得更多的时间片。有高优先级以及剩余时间片的进程通常情况优先运行。

nice值和实时优先级

linux内核实现了两类优先级:

  • nice值(-20到+19的整数，默认为0)是所有unix系统标准的优先级区间:
    • 拥有低nice值得进程拥有更高的优先级，并且占有更多的处理器资源。
    • 在Linux系统中，nice值影响时间片的分配比例。在其他类unix系统中（比如Mac OSX），nice值影响固定时间片的分配。
    • 通过ps -el 命令可以看到各个进程的nic值。
  • 实时优先级（可配的值，默认区间为0到99）
    • 高实时优先级的进程意味着更高的优先级
    • 所有实时进程的优先级都高于普通进程
    • linux按照unix的标准(尤其是POSIX.1b)来实现的实时优先级
    • 通过ps -eo state,uid,pid,ppid,rtprio,time,comm 命令来查看进程以及进程对应的优先级。”-“代表进程不是实时进程。

时间片

时间片表示进程在被抢占前可以运行的时间。

  • 一个过长的时间片会导致系统的交互变差
  • 一个过短的时间片会导致过多的时间浪费在进程切换上

I/O密集型和计算密集型之间的冲突:

  • I/O密集型不需要过多的时间片，尽管他们需要经常运行
  • 计算密集型需要更长的时间片（用来保持缓存的热度）

linux的时间片

linux的CFS调度器不直接分配时间片给进程，而是分配给进程相应比例的处理器资源。进程分配的处理器时间是一个系统负载有关的函数。所分派的比例进一步被各个进程的nice值影响。nice起了权重的作用，用来该表进程所占用的处理器比例。拥有高nice值得进程会获得较低的权重，相应的也获得较低的处理器比例。

在使用CFS的情况下，决定一个进程是否应该立刻运行的条件是这个新的进程消费了多少处理器比例。如果当前进程遇到了一个消费比例更低的进程，则需要立刻让出处理器。

调度策略实例

假设有两个可运行的进程: 一个时文本编辑器(I/O密集型)和一个视频编码器(计算密集型) 理想状态下调度器会给文本编辑器更高的处理器占用比，因为它是交互性的。我们希望可以达到如下两个目标:  1. 我们希望文本编辑器有大量的处理器时间可供使用，这不是因为它需要这么多资源，而是我们希望在它需要处理器资源的时候能够有可用的处理器资源。

  1. 我们希望在文本编辑器被唤醒的时候能够抢占视频编码器。这可以为文本编辑器提供更好的响应时间。

上面的两个目标是如何实现的

  1. linux保证文本编辑器拥有一定比例的处理器资源，而不是分配固定的时间片给进程。如果只有两个进程，并且进程的nice值相同，那么保证了每个进程占用了处理的50%。因为文本编辑器更多的时间处于阻塞状态，所以使用的比例远不到50%。相反视频处理器允许使用超过50%，这样可以使得它尽快的完成编码工作。
  2. 当文本编辑器被唤醒的时候，CPS注意到文本编辑器被分配了50%的处理器资源，但是使用的却远不到。为了尽量保持所有的进程公平分享处理器，所以它会挂起视频编码器，让文本编辑器运行。

linux调度算法

调度类型

linux的调度器是模块化的，启动不同的算法来调度不同类型的进程。这些模块被称作scheduler classes。调度器的基础代码在kernel/sched.c中，它按照优先级遍历各个scheduler class。有可运行进程的最高优先级的scheduler class胜出，由它来选择出接下来运行的进程。

CFS调度器是scheduler class的一种，用于普通进程，在linux中称作SCHED_NORMAL。CFS定义在kernel/sched_fair.c中。这一小节的其他内容会讨论CFS算法。

unix系统中的进程调度

为了讨论公平调度，我们首先需要介绍下传统的unix系统是如何进行进程调度的。

现代进程调度器有两个通用的概念：进程优先级和时间片。拥有高优先级的进程会运行的更频繁，并且获得更多的时间片。在unix系统中，优先级以nice的形式呈现。这样做导致了几个问题:

  1. 将nice值映射为时间片需要知道每个nice值需要分配多少固定的时间片，这会导致优先级翻转的情况、
  2. 用相对的nice值会有不同的效果，这取决于初始值。
  3. 绝对的时间片必须是timer tick的整数倍，这会导致一些问题
  4. 在对交互式进程做了优化的基于优先级的调度器中处理被唤醒的进程可能会导致调度器给某个进程分配了不公平的处理器时间。

CFS采用的办法是激进的，它重新思考了时间片的分配方式: 不直接分配时间片，而是分配一定比例的处理器资源。

公平调度

CFS基于一个简单的概念: 假设系统有一个理想的，完美的多任务处理器，在这个基础上对进程调度进行建模。在这样的系统上，每个进程拥有1/n的处理器资源，n是当前可运行进程的数量，系统每隔非常小的一段时间(接近于无限小)调度一次进程，这样无论在任何可衡量的时间段内，每个进程都运行了基本上相同的时间。

以无限小的时间运行进程是低效的；挂起一个进程然后切换到另外一个进程是有代价的:进程切换的开销以及对缓存的影响。CFS给每个进程一段时间让其运行，然后选择下一个运行的最少的进程。CFS不是给进程分配时间片，而是通过和当前进程数相关联的的函数计算进程应该运行多长时间。CFS通过nice值衡量进程占用的处理器比例，而不是通过nice值计算时间片。

每个进程运行一段时间，这个时间是按照其权重除以所有进程权重总和后得到的比例分配的。CFS设置了一个接近”infinitely small”的值，这个值称作targeted latency。targeted latency越小，系统的交互性越好，越接近完美的多任务系统，但是进程切换的开销越大，系统的吞吐量越低。CFS给每个进程分配的时间设置了一个最低值，叫做minimum ranularty(默认为1ms)。即使可运行的进程数量接近于无数，那进程每次运行的时间至少可以达到1ms，保证不会出现过高的进程切换开销。

为了更好地理解nice值是如何影响处理器比例的，看一下下面的例子: 有两个可运行的进程，它们拥有不同的nice值。一个进程的nice值是默认的0，另一个nice值是5.在这种情况下，nice值为5的进程所占用的处理器比例为nice值为0的进程的1/3.也就是说如果我们设置targeted latency为20ms的话，两个进程分别可以获取到15ms和5ms的处理器时间。通常情况下，一个进程的nice值和其他进程的nice值之间的相对区别直接影响了其可以获得到的处理器比例。

注释1: stackoverflow上有人解释了targeted latency的作用。在targeted latancy时间内，每个进程至少需要被调度到一次。

注释2: 上面的例子中提到nice值为5的进程所能够拥有的处理器比例为nice值为0的进程的1/3，这需要参见下面的 nice值到权重的映射以及虚拟运行时间的计算。

linux的调度实现

CFS的实现在kernel/sched_fair.c中。下面的内容会讨论CFS的四个部分:

  • 时间统计
  • 进程选择
  • 调度入口
  • 睡眠和唤醒

时间统计

进度调度器需要统计各个进程的运行时间。在系统时钟的每次嘀嗒，进程的可用时间片会减少，减少的值为时钟周期。当时间片变为0的时候，系统挂起然后选择另一个时间片非0的可运行进程运行。

调度结构体

CFS没有时间片概念，但是它必须跟踪每个进程运行的时间。

CFS使用scheduler entity struct, struct sched_entity，定义在<linux/sched.h>(include/linux/sched.h#L1090)中，用于跟踪进程统计:

struct sched_entity {
    struct load_weight 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;
    u64 last_wakeup;
    u64 avg_overlap;
    u64 nr_migrations;
    u64 start_runtime;
    u64 avg_wakeup;

/* many stat variables elided, enabled only if CONFIG_SCHEDSTATS is set */
};

调度结构体嵌在进程的描述符中，struct task_struct中，对应的名字是se (include/linux/sched.h#L1188).

nice值到权重的映射

nice值到权重的映射定义在常量数组prio_to_weight(kernel/sched.c#L1362)中。权重的值约等于1024/(1.25)^(nice)。

static const int prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

虚拟运行时间

vruntime 用于存储进程的虚拟运行时间，这个值是进程的实际运行时间和总的进程数通过运算得到的。虚拟运行时间的单位是纳秒，因此和系统时钟解耦了。因为处理器不能完美的处理多任务，并且我们必须成功的运行每个进程，CFS使用vruntime 来衡量每个进程已经运行了多长时间以及每个进程还可以运行多长时间。

函数 update_curr()，定义在kernal/sched_fair.c(kernel/sched_fair.c#L518)中，用于管理统计信息:

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);
    if (!delta_exec)
        return;

    __update_curr(cfs_rq, curr, delta_exec);
    curr->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);
    }
}

update_curr() 计算当前进程的运行时间，并且存储在delta_exec中。然后传递运行时间给__update_curr()，该函数会将运行时间和当前进程数做一系列运算做加权处理。当前进程的vruntime会加上这个处理后的加权值:

/*
 * Update the current task's runtime statistics. Skip current tasks that
 * are not in our scheduling class.
 */
static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
          unsigned long delta_exec)
{
    unsigned long delta_exec_weighted;

    schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));

    curr->sum_exec_runtime += delta_exec;
    schedstat_add(cfs_rq, exec_clock, delta_exec);
    delta_exec_weighted = calc_delta_fair(delta_exec, curr);

    curr->vruntime += delta_exec_weighted;
    update_min_vruntime(cfs_rq);
}

update_curr() 方法被系统的定时器周期的调用。在这种情况下，vruntime代表了进程准确的运行时间并且用来表明哪个进程会被调度占用处理器。

calc_delta_fair函数

kernel/sched_fair.c#L431

/*
 * delta /= w
 */
static inline unsigned long
calc_delta_fair(unsigned long delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);

    return delta;
}

kernel/sched.c#L1300

/*
 * delta *= weight / lw
 */
static unsigned long
calc_delta_mine(unsigned long delta_exec, unsigned long weight,
        struct load_weight *lw)
{
    u64 tmp;

    if (!lw->inv_weight) {
        if (BITS_PER_LONG > 32 && unlikely(lw->weight >= WMULT_CONST))
            lw->inv_weight = 1;
        else
            lw->inv_weight = 1 + (WMULT_CONST-lw->weight/2)
                / (lw->weight+1);
    }

    tmp = (u64)delta_exec * weight;
    /*
     * Check whether we'd overflow the 64-bit multiplication:
     */
    if (unlikely(tmp > WMULT_CONST))
        tmp = SRR(SRR(tmp, WMULT_SHIFT/2) * lw->inv_weight,
            WMULT_SHIFT/2);
    else
        tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);

    return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX);
}

上面代码可以归纳为:

delta_exec_weighted = delta_exec * NICE_0_LOAD / se->load

Explanation of the calc_delta_mine function中有详细的探讨。

进程选择

CFS通过一个简单的规则来平衡各进程的虚拟运行时间: 当需要选择下一个运行的进程的时候，调度器选择vruntime最小的进程。

CFS使用红黑树来管理进程列表，并且高效的找到有最小vruntime的进程。红黑树在linux称为rbtree(include/linux/rbtree.h，lib/rbtree.c)，是一种自平衡的二叉搜索树。红黑树的搜索复杂度为O(logn)。

选择下一个任务

CFS选择的下一个可运行的进程，拥有最小的vruntime，在红黑树的最左节点。如果沿着红黑树的根节点，向下到左节点，然后一直沿着左节点向下走就可以找到最小vruntime的节点。CFS的进程选择算法可以总结为寻找红黑树最左节点的过程。

寻找下一个运行任务的函数为__pick_next_entity()，定义在kernel/sched_fair.c(kernel/sched_fair.c#L377):

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->rb_leftmost;

    if (!left)
        return NULL;

    return rb_entry(left, struct sched_entity, run_node);
}

可以看到__pick_next_entity()实际上并没有遍历树来寻找最左节点，因为最左节点缓存在rb_leftmost中，尽管遍历树的复杂度为O(logn)已经足够高效了。

函数返回的值就是下一个要运行的进程。如果函数返回NULL，表示没有可运行的进程，CFS会调度idle进程。

添加进程到红黑树

CFS添加进程到红黑树，并且缓存最左的节点，当一个进程变为可运行状态或者通过fork()刚刚被创建的时候。这个操作是通过enqueue_entity()完成de: kernel/sched_fair.c#L773

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    /*
     * Update the normalized vruntime before updating min_vruntime
     * through callig update_curr().
     */
    if (!(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATE))
        se->vruntime += cfs_rq->min_vruntime;

    /*
     * Update run-time statistics of the 'current'.
     */
    update_curr(cfs_rq);
    account_entity_enqueue(cfs_rq, se);

    if (flags & ENQUEUE_WAKEUP) {
        place_entity(cfs_rq, se, 0);
        enqueue_sleeper(cfs_rq, se);
    }

    update_stats_enqueue(cfs_rq, se);
    check_spread(cfs_rq, se);
    if (se != cfs_rq->curr)
        __enqueue_entity(cfs_rq, se);
}

这个方法更新了runtime和其它统计信息，然后调用__enqueue_entity()来完成繁重的插入和平衡二叉树工作。 kernel/sched_fair.c#L328

/*
 * Enqueue an entity into the rb-tree:
 */
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.
         */
        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);
}

这个函数在while()循环中遍历树查找合适的插入位置。如果插入的节点小于遍历的节点，则会从当前遍历节点的左子节点开始寻找，否则向右寻找。如果向右寻找，哪怕只有一次，就可以判断出新的节点不会成为最新的最左节点，所以设置leftmost为0.如果一直向左寻找，leftmost保持1，并且产生新的leftmost节点，然后缓存到rb_leftmost中。当跳出循环的时候，方法在parent节点上调用rb_link_node()，使得新插入的节点为自己点。方法rb_insert_color()更新树的自平衡属性。

在二叉树中移除进程

当进程阻塞或者终止的是偶，CFS将进程从红黑树中移除: kernel/sched_fair.c#L815

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);
    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);

    /*
     * Normalize the entity after updating the min_vruntime because the
     * update can refer to the ->curr item and we need to reflect this
     * movement in our normalized position.
     */
    if (!sleep)
        se->vruntime -= cfs_rq->min_vruntime;
}

类似的，真实的工作由另一个方法完成，这个方法是__dequeue_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);
}

在红黑树中移除进程更简单一些，因为红黑树的实现提供了rb_erase()方法来完成所有工作。函数的其他部分用于更新rb_leftmost缓存。如果移除的进程是leftmost节点，那么函数会调用rb_next()来查找下一个节点，然后成为新的leftmost节点。

调度器入口

调度器的入口在方法schedule()中，该方法定义在kernel/sched.c(kernel/sched.c#L3701)中。该方法调用进程调度器，并且决定哪个进程需要被调度然后运行这个进程。

schedule()对scheduler classes是通用的。它查找有可运行进程的最高优先级的调度器，然后使用该调度器查找下一个运行的进程。因此, schedule()的实现是比较简单的。该函数唯一比较重要的部分是调用pick_next_task*()方法，该方法定义在kernel/sched.c(kernel/sched.c#L3670)，该方法用于遍历每个scheduler class，从高优先级调度器中选择出最高优先级的进程。

/*
 * Pick up the highest-prio task:
 */
static inline struct task_struct *
pick_next_task(struct rq *rq)
{
    const struct sched_class *class;
    struct task_struct *p;

    /*
     * Optimization: we know that if all tasks are in
     * the fair class we can call that function directly:
     */
    if (likely(rq->nr_running == rq->cfs.nr_running)) {
        p = fair_sched_class.pick_next_task(rq);
        if (likely(p))
            return p;
    }

    class = sched_class_highest;
    for ( ; ; ) {
        p = class->pick_next_task(rq);
        if (p)
            return p;
        /*
         * Will never be NULL as the idle class always
         * returns a non-NULL p:
         */
        class = class->next;
    }
}

该函数的最开始位置有一个优化点。CFS是普通进程的调度器，并且系统大多数运行的都是普通进程，如果系统可运行的进程数和CFS可运行进程数相同，那么先从CFS中获取可运行进程作为优化，这样就不需要遍历所有调度器了。

pick_next_task的核心在for循环内，从最高优先级开始按照从高到低遍历每个调度器。每个调度器都实现了pick_next_task()方法，该方法返回了指向下一个运行进程的指针，如果没有可运行的进程该方法则返回NULL。第一个返回的非NULL的指针指向的进程作为下一个可运行进程。CFS实现的pick_next_task()方法叫做pick_next_entity()，该方法调用__pick_next_entity()。

fair_sched_class scheduler class

fair_sched_class是定义在kernel/sched_fair.c中的结构体。kernel/sched_fair.c被kernel/sched.c所引用，所以fair_sched_class在pick_next_task 中是可用的。

睡眠和唤醒

当进程睡眠的时候，处于一种特殊的非运行状态。 当进程遇到下面的情况时会进入到睡眠状态:

  • 睡眠固定的时间
  • 等待文件I/O
  • 等待其他硬件事件

一个进程可能被动进入到睡眠状态如果在内核中遇到竞争的信号量。

无论什么情况导致进程睡眠，内核对于睡眠的处理都是相同的。进程会做如下的处理:

  • 标记自己为sleeping
  • 把自己放到等待队列上
  • 把自己可运行的红黑树上移除
  • 调用schedule()方法选择一个新的进程来执行

当进程被唤醒的时候过程是相反的: 进程被设置为可运行，从等待队列移除，重新添加到可运行的红黑树中

下面的两个状态和睡眠相关:

  • TASK_INTERRUPTIBLE
  • TASK_UNINTERRUPTIBLE

这二者的唯一区别是TASK_UNINTERRUPTIBLE忽略信号，而处于TASK_INTERRUPTIBLE的进程可能提前被唤醒并且对信号做出响应。二者相同的是都位于等待队列中，等待事件的发生。

等待队列

睡眠是通过等待队列进行处理的。一个等待队列由等某个事件发生的进程组成。

等待对垒在内核中的结构为wake_queue_head_t。等待队列是通过DECLARE_WAITQUEUE静态创建或者通过init_waitqueue_head()动态创建。进程将他们自己放置到等待队列中并且标记自己为不可运行。当和等待队列关联的事件发生的时候，队列中的进程被唤醒。

正确的实现睡眠和唤醒，以及避免条件竞争是很重要的。否则，可能在condition变为true之后进入到睡眠，这样进程可能无限期的睡眠下去。因此，内核推荐的睡眠函数在实现上有一些复杂:

/* `q' is the wait queue we wish to sleep on */
DEFINE_WAIT(wait);

add_wait_queue(q, &wait);
while (!condition) { /* condition is the event that we are waiting for */
    prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE);
    if (signal_pending(current))
        /* handle signal */
    schedule();
}
finish_wait(&q, &wait);

进程执行下面的步骤来将自己添加到等待队列中:

  1. 通过宏DEFINE_WAIT()创建等待队列项
  2. 通过add_wait_queue将自己添加到等待队列中。当进程等待的事件到来时，队列会唤醒进程。当然，这需要调用wake_up方法
  3. 调用prepare_to_wait()方法将进程的状态设置为TASK_INTERRUPTIBLE或者TASK_UNINTERRUPTIBLE。在必要的情况下，这个方法也会将任务添加回等待队列。
  4. 当进程状态设置为TASK_INTERRUPTIBLE的时候，信号可以唤醒进程。这种情况叫做伪唤醒。
  5. 当进程被唤醒的时候，它重新检查状态是否是true。如果是，则退出循环。否则继续调用schedule()重复过程。
  6. 当状态为true的时候，进程设置自己的状态为TASK_RUNNING，然后通过finish_wait()将自己从等待队列中移除

如果在进程进入睡眠前，事件已经发生了，那么循环会立刻终止，进程则不会进入到睡眠状态。内核进场需要在循环体内处理其他任务。比如，在调用schedule()之前可能需要释放锁，然后继续获取锁来处理其他任务。

方法inotify_read()定义在fs/notify/inotify/inotify_user.c，主要用于读取inotify文件，是一个使用等待队列的例子:

static ssize_t inotify_read(struct file *file, char __user *buf,
                size_t count, loff_t *pos)
{
    struct fsnotify_group *group;
    struct fsnotify_event *kevent;
    char __user *start;
    int ret;
    DEFINE_WAIT(wait);

    start = buf;
    group = file->private_data;

    while (1) {
        prepare_to_wait(&group->notification_waitq, &wait, TASK_INTERRUPTIBLE);

        mutex_lock(&group->notification_mutex);
        kevent = get_one_event(group, count);
        mutex_unlock(&group->notification_mutex);

        if (kevent) {
            ret = PTR_ERR(kevent);
            if (IS_ERR(kevent))
                break;
            ret = copy_event_to_user(group, kevent, buf);
            fsnotify_put_event(kevent);
            if (ret < 0)
                break;
            buf += ret;
            count -= ret;
            continue;
        }

        ret = -EAGAIN;
        if (file->f_flags & O_NONBLOCK)
            break;
        ret = -EINTR;
        if (signal_pending(current))
            break;

        if (start != buf)
            break;

        schedule();
    }

    finish_wait(&group->notification_waitq, &wait);
    if (start != buf && ret != -EFAULT)
        ret = buf - start;
    return ret;
}

上面的函数有一些值得关注的地方:

  • 在while循环体内，检查条件是否发生，而不是在while自身检查，因为条件的检查比较复杂并且需要获取锁。
  • 循环通过关键词break终止

唤醒

wake_up() 方法唤醒某个等待队列中的所有进程。它主要做了下面几件事情:

  • 调用try_to_wake_up()，该方法将进程的状态设置为TASK_RUNNING
  • 调用enqueue_task()将任务添加到红黑树中
  • 如果被唤醒的进程的优先级高于当前执行任务的优先级，则设置need_resched标志位。使得事件发生的代码通常会调用wake_up()方法。
    • 比如，当从磁盘读取的数据到达的时候，VFS(虚拟文件系统)在等待这个数据的等待队列上调用wake_up()方法。

因为存在伪唤醒，所以一个进程被唤醒并不意味着一定存在事件发生。在循环中一定要处理睡眠，保证进程等待的事件实际上真的发生了。下面的图描述了进程的几个调度状态。 https://notes.shichao.io/lkd/figure_4.1_600.png

抢占和上下文切换

上下文切换(从一个进程切换到另一个进程)通过context_switch()方法处理，该方法定义在kernel/sched.c中。该方法被schedule()调用，当一个新的进程被选择运行的时候。它主要做了下面几件事情:

  • 调用switch_mm，来切换虚拟内存映射。该方法定义在<asm/mmu_context.h>中。
  • 调用switch_to方法，将处理器状态从之前的进程切换到现在的进程。这包括保存和恢复栈信息、寄存器和其他架构相关的状态。

need_resched

内核必须知道何时调用schedule()方法，如果仅仅是代码自行调用schedule()方法，那么用户态的进程可能永远执行下去。

内核提供了need_resched标准位用来表明需要进行重调度。

  • scheduler_tick()可能会设置该标志位
  • try_to_wake_up()可能会设置该标志位，如果被唤醒的进程优先级高于当前运行的进程的话。

内核会检查该标志位，如果被设置了，则调用schedule()方法切换到新的进程运行。这个标志位用于通知内核尽快的进行重调度因为有另外的进程渴望运行。

在从系统调用回到用户态或者从中断恢复的时候，会检查need_resched标志位。如果设置了，内核会调用进程调度器。

下面的表列出了访问或者修改need_resched的方法:

Function Purpose
set_tsk_need_resched() 设置某个进程的need_resched标志位
clear_tsk_need_resched() 清除某个进程的need_resched标志位
need_resched() 测试need_resched标志位；如果设置了则返回true；否则返回false

这个标志位是属于进程的，而不是简单的全局标志位，因为访问进程描述符里面的数据要比访问全局数据要快。因为历史原因在内核2.2版本之前，该标志位是全局的，在内核2.4版本之后该标志位位于task_struct中。在内核2.6版本中，该标志位被挪到了thread_info中，仅仅在所有标志位中占用一个bit。

用户抢占

当内核返回到用户空间之前，如果need_resched被设置，内核会调用进程调度器，这时候就发生了用户抢占。如果内核正在返回用户空间，它直到目前处于安全状态。换句话说，它可以继续执行当前的任务，或者切换到新的任务执行。

当内核准备从系统调用或者中断处理返回到用户空间的时候，need_resched标志位会被检查。如果该标志位被设置了，那么调度器会被调用然后选择出一个新的进程来运行。从系统调用或者从中断返回的返回路径和体系结构相关，通常在entry.S中实现。

总结下来，用户抢占发生在下面的两个情况:

  • 从系统调用返回到用户空间
  • 从中断处理返回到用户空间

内核抢占

在非抢占的内核汇总，内核代码通常一直执行直到执行完成。这是因为调度器通常不能调度一个正在运行内核代码的进程:内核代码是不可抢占的。内核代码会一直运行直到结束或者阻塞。

在linux内核2.6版本之后，linux内核变为完全可抢占的。在进程任意的位置都有可能发生抢占，只要内核的状态处于安全的重调度状态。

内核可以抢占一个进程只要内核没有持有锁。因为内核是多进程安全的，只要当前进程没有持有锁，那么正在运行的代码就是可重入的并且可以被抢占。

抢占计数器 preempt_count

为了支持内核抢占，抢占计数器被添加到thread_info中。这个计数器初始的时候是0，每当获得锁的时候都会加1.从中断回来的时候，如果是回到内核空间，那么内核会检查need_resched和preempt_count：

  • 如果need_resched被设置了并且preempt_count是0，同时有另一个优先级更高的进程需要运行，那么当前进程会被抢占。
  • 如果preempt_count不为0，那么表示当前进程持有锁了。重调度是不安全的。在这种况下，中断会照常返回继续执行当前的任务。

开启或者禁止内核抢占在某些情况下被内核代码用到。

明确的内核抢占

内核抢占也可能显示的发生，当内核代码遇到下面的情况时:L

  • 阻塞
  • 显示调用schedule()

这种类型的抢占通常情况下被支持的，因为不需要额外的逻辑保证内核处于安全的可抢占状态。这是基于显示调用schedule()的代码直到它目前处于安全的可调度的。

总结起来，内核抢占会发生在下面的情况:

  • 中断处理退出，回到内核空间之前
  • 当内核代码变得可抢占
  • 内核代码显示调用schedule()
  • 内核代码阻塞(简介调用schedule())

实时调度策略

Linux系统提供了两种实时调度策略:

  • SCHED_FIRO
  • SCHED_RR。通常情况下，非实时调度采用的是SCHED_NORMAL

在调度框架中，这些实时策略不是通过CFS来管理的，而是通过一个特殊的实时调度器来完成，这个调度器定义在kernel/sched_rt.c中。

SCHED_FIFO策略

该策略简单来说就是先进先出，而不参考时间片信息。

  • 一个可运行的SCHED_FIFO进程通常会比任何处于SCHED_NORMAL的进程先运行
  • 当一个SCHED_FIFO进程变得可运行的是哦户，它会一直运行直到阻塞或者显示让出处理器；它没有时间片，并且可以无限期的运行。
  • 只有更高优先的SCHED_FIFO或者SCHED_RR进程可以抢占一个SCHED_FIFO进程
  • 多个有相同优先级的SCHED_FIFO进程采用round-robin的方式进行调用，但是只有它们自己才能让出处理器
  • 如果一个SCHED_FIFO进程处于可运行状态，其他低优先级的进程都不能运行直到这个进程变得不可运行。

SCHED_RR策略

SCHED_RR 策略和SCHED_FIFO基本上一致，除了前者会一直运行直到时间片到期。也就是说，SCHED_RR是有时间片的SCHED_FIFO。它也是一个实时的，基于round-robin调度的算法。

  • 当一个SCHED_RR进程时间片技术的时候，任何和他相同优先级的进程会被调度，策略是round-robin。时间片只在相同优先级的进程中有用。
  • 和SCHED_FIRO相似，高优先级的进程通常可以抢占低优先级的进程。而低优先级的进程不可以抢占高优先级的进程，尽管它的时间片已经用完。

实时调度策略也实现了静态优先级。内核不为实时任务计算动态优先级。这保证了高优先级的进程通常能够抢占低优先级的进程。

硬实时和软实时

  • 软实时意味着内核尝试在时间截止时调度应用，但是不保证一定能够成功
  • 硬实时系统保证完成任何调度在指定的时间内。

linux提供了软实时策略。Linux不保证调度实时任务的能力。除了没有保证硬实时的设计外，linux的实时调度在性能方面还是不错的。在内核2.6版本中满足了严格时间限制的要求。

实时优先级从0到MAX_RT_PRIO -1 。默认的情况下是从0到99，因为MAX_RT_PRIO为100。这个优先级区间被SCHED_NORMAL进程共享，他们采用MAX_RT_PRIO到(MAX_RT_PRIO + 40)。因此默认情况下，-20到19的nice值被映射为100到139的优先级。

默认优先级:

  • 0到99：实时优先级
  • 100到139: 普通优先级

调度器相关的系统调用

linux提供了一系列的系统调用用来管理调度器参数，这些系统调用可以操作进程优先级，调度策略，操作系统亲和度或者将处理器让给其他进程。

下面的表是对这些系统调用简单的说明。

System Call Description
nice() Sets a process’s nice value
sched_setscheduler() Sets a process’s scheduling policy
sched_getscheduler() Gets a process’s scheduling policy
sched_setparam() Sets a process’s real-time priority
sched_getparam() Gets a process’s real-time priority
sched_get_priority_max() Gets the maximum real-time priority
sched_get_priority_min() Gets the minimum real-time priority
sched_rr_get_interval() Gets a process’s timeslice value
sched_setaffinity() Sets a process’s processor affinity
sched_getaffinity() Gets a process’s processor affinity
sched_yield() Temporarily yields the processo

调度策略和优先级相关的系统调用

  • sched_setscheduler()和sched_getscheduler()用来设置或者获取某个进程的调度策略和实时优先级。这两个方法的主要工作是读取task_sturct中的policy和rt_priority
  • sched_setparam()和sched_getparam()用于获取进程的实时优先级。这些系统调用对sched_param中的RT_PRIORITY进行编码。
  • sched_get_priority_max()和sched_get_priority_min()返回某个策略的最大和最小优先级。实时优先级的最大值为MAX_USER_RT_PRIO减一，最小的为1.
  • 对于普通的进程，函数nice()返回特定进程的静态优先级。
    • 只有管理员才能够设置负数，nice值越低优先级越高
    • nice()调用内核的set_user_nice()方法，后者用来设置静态优先级以及task_struct中的优先级

处理器亲和性系统调用

linux调度器强制处理器亲和性，这意味着除了通过将进程保持在同一个处理器上来提供soft affinity或者natural affinity，the scheduler enables a user to enforce “a task must remain on this subset of the available processors no matter what”.（这句话不知道怎么翻译。。。等真的理解了含义再做翻译）

硬亲和性存储在进程的task_struct``·的cpus_allowed```字段中。系统中的每个处理器在掩码中有一个bit。默认的，所有bit被设置，处理器可以在任何处理器上运行。下面的系统调用可以设置和获取掩码:

  • sched_setaffinity() 设置掩码中的一个或者多个bit
  • sched_getaffinity() 获取掩码 cpus_allowed

内核在下面的规则时强制使用硬亲和性:

  • 当一个进程刚创建的时候，它继承了父进程的掩码。因为父进程已经在一个允许的处理器上运行了，子进程也必须在某个允许的处理器上运行
  • 当一个处理器的掩码改变的时候，内核需要迁移所有线程将该进程放到另一个处理器上
  • 负载均衡器仅将进程放到一个允许的处理器上

因此只有当进程描述符中的cpus_allowed中对应位被置位的时候，进程才会在对应的处理上运行。

Yielding Processor Time

linux提供了系统调用sched_yield()允许进程主动的让出处理器给另一个进程。

  • sched_yield()将进程从活跃数组中删除，将其插入到过期数组中。这不仅仅可以抢占当前的进程，将其放到其优先级队列的尾部，而且还将其放到过期列表中，保证它在一段时间内不会运行。
    • 对于实时任务，从不过期，因此仅仅将其优先级队列的尾部。

之类的过期具体指的是什么含义？

总结

疑问和解决方案