Linux进程调度

进程调度概览

多任务

多任务操作系统就是能同时运行多个进程的操作系统：

• 在单处理器上，这会产生多个进程在同时运行的幻觉
• 在多处理器上，这会使多个进程在不同的处理器上真正并行地运行

抢占式多任务：

• 由调度程序来决定什么时候停止一个任务的运行，以便其他任务能够得到执行的机会
• 像所有 Unix 的变体和许多其他现代操作系统一样，Linux 提供了抢占式的多任务模式

什么是调度

操作系统最重要的职责之一就是对系统资源进行管理，而调度管理的资源就是 CPU。

对于共享型的事物有两种管理方法：一种是空间分割管理，一种是时间分割管理。由于 CPU 自身的特性，对于单个 CPU，我们只能进行时间分割管理。调度就是在可运行任务之间分配有限的处理器时间资源。

注：在 Linux 内核中，调度的对象是进程。事实上，从 Linux 内核的角度来说并没有线程的概念，只有某些共享特定资源的进程。因此，我们只提“进程调度”。

为什么要调度

为了更好地支持多任务：

• 充分利用 CPU 资源，提高任务吞吐
• 保证调度的公平性，为各个任务提供良好的运行体验

简单来说，调度器需要做出如下决策：

• 接下来将哪个进程投入运行
• 进程执行多长时间

Linux 调度程序演进

传统调度器：v1.0 - v2.4

从 1991 年 Linux 的第 1 版 (v0.01) 到后来的 2.4 内核系列，Linux 的调度程序都相当简陋，设计近乎原始。这一阶段的调度器和传统的 UNIX 调度器逻辑是一样的，多数时候具备以下特征：

• 全局只有一个运行队列
• 按照动态优先级决定进程的调度顺序，动态优先级根据进程的睡眠时间进行计算
• 按照静态优先级分配进程的时间片大小，当所有进程的时间片都耗尽之后才会进入下一轮调度周期
• 每次选择下一个运行进程时都需要遍历整个队列，算法复杂度是 O(n)，后期的版本也被称为 O(n) 调度器

从方案的设计理念上来说，后期的 O(n) 调度器和 1991 年 0.01 版本内核的调度器并没有多大的区别[2]。以下是 0.01 版本的调度器代码，其中的注释现在看来蛮有趣的。

/*
 *  'schedule()' is the scheduler function. This is GOOD CODE! There
 * probably won't be any reason to change this, as it should work well
 * in all circumstances (ie gives IO-bound processes good response etc).
 * The one thing you might take a look at is the signal-handler code here.
 *
 *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
 * tasks can run. It can not be killed, and it cannot sleep. The 'state'
 * information in task[0] is never used.
 */
void schedule(void)
{
    int i,next,c;
    struct task_struct ** p;

/* check alarm, wake up any interruptible tasks that have got a signal */

    for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
        if (*p) {
            // 如果目前的时钟节拍数已经超过了进程被设置的唤醒时刻的值
            if ((*p)->alarm && (*p)->alarm < jiffies) {
                    (*p)->signal |= (1<<(SIGALRM-1));
                    (*p)->alarm = 0;
                }
            // 唤醒任何收到过信号（或者阻塞超时）且可被中断的进程
            if ((*p)->signal && (*p)->state==TASK_INTERRUPTIBLE)
                (*p)->state=TASK_RUNNING;
        }

/* this is the scheduler proper: */

    while (1) {
        c = -1;
        next = 0;
        i = NR_TASKS;
        p = &task[NR_TASKS];
        while (--i) {
            if (!*--p)
                continue;
            // 找出可运行进程中时间片最大的那一个
            if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
                c = (*p)->counter, next = i;
        }
        // 如果队列中有可运行且时间片未用完的进程，或者没有任何可运行进程，则跳出循环
        if (c) break;
        // 执行到这里说明队列中有可运行的进程，但是时间片都用完了，此时需要重新调整所有进程的时间片
        for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
            if (*p)
                (*p)->counter = ((*p)->counter >> 1) +
                        (*p)->priority; // (*p)->counter并不全是0，因为队列中有非可运行的进程
    }
    switch_to(next);
}

这一版本的调度器在多处理器环境上且有众多可运行进程时难以胜任。

O(1) 调度器：v2.5 - v2.6.22

在 2.5 系列的内核中，调度程序做了大手术，开始采用一种叫做 O(1) 调度器的新调度程序。它解决了先前版本 Linux 调度程序的许多不足，引入了许多强大的新特性和性能特征。

• 每个 CPU 一个运行队列
• 定义 0~139 的优先级范围，并划分 0~99 为实时进程，100~139 为普通进程
• 把运行队列分成了两个链表数组，时间片未耗尽的进程放在活动数组，时间片用完的进程放在过期数组，当所有进程的时间片耗尽时交换两个数组，重新分配时间片
• 两个链表数组都使用动态优先级排序，并用一个 bitmap 标记链表是否非空，这样每次调度时只需取出活动数组中优先级最高的非空链表中的第一个进程即可，时间复杂度为 O(1)
  [图片]
• 引入内核抢占，避免处于内核态的进程长时间占用 CPU
• 普通任务用完时间片时其优先级会根据自身的交互性被重新计算，交互性则根据过去一段时间任务的行为而判定

O(1) 调度器虽然在拥有数以十计的多处理器的环境下尚能表现出近乎完美的性能和可扩展性，但是时间证明该调度算法对于调度那些响应时间敏感的程序却有一些先天不足。因此，O(1) 调度程序对于大服务器的工作负载很理想，但是在有很多交互程序要运行的桌面系统上则表现不佳。

RSDL 调度器：未合入

此前的调度器版本有一个重要的特征：区分 I/O 密集型与 CPU 密集型的进程。为了提升交互性程序的响应速度，调度器会努力识别并奖励交互式任务。尽管 O(1) 调度器在算法上做了很多改进，但本质上还是在提升“猜中”一个进程为交互式任务的概率，总有用户举出在特殊场景下交互式任务响应太慢的例子。而且，用户进程总有办法伪装自己是交互性程序。

后来，大家尝试抛弃“评估任务的交互性”这种思路，RSDL（Rotating Staircase Deadline Scheduler）便是这样的一种方案，该方案由 Con Kolivas 于 2007 年提出。RSDL 方案废除了动态优先级，不再区分 I/O 密集型进程和 CPU 密集型进程。

同 O(1) 调度器一样，RSDL 会在每个调度周期根据任务的优先级划分固定的 CPU 时间，并且为每一个优先级维护一个任务列表。但在任务运行过程中，任务会随着时间片的耗尽而下滑到下一个优先级的任务列表中，任务本身的优先级不变，整个过程就像下楼梯一样。所有任务的运行时间耗尽后，调度器再开启下一轮调度。

由于遭到主流内核社区的反对——后者认为该方案太过倾向于桌面系统，Kolivas 的工作最终没有合入到内核主线中。

CFS 调度器：v2.6.23 至今

虽然 Kolivas 的工作没有得到主流内核社区的认可，但是 O(1) 调度器的发明人 Ingo Molnar，同时也是内核调度策略的关键维护者，基于 Kolivas “楼梯调度”算法设计中的公平性概念提出了新的解决方案——完全公平调度器（Completely Fair Scheduler）。CFS 调度器于 2007 年初期被合入内核 2.6.23 版本，成为内核的默认调度器并被沿用至今，我们将在后面详细介绍它。

Linux 进程调度框架

注：以下引用的代码基于 v2.6.34

调度类

Linux 调度器是以模块化方式提供的，这样可以允许不同类型的进程针对性地选择调度算法，这种模块化的结构被称为调度类（Scheduler Class）。一个调度类可以有不同的调度策略，比如实时调度类支持 SCHED_FIFO 和 SCHED_RR 两种调度策略。CFS 是一个针对普通进程的调度类，它支持的调度策略为SCHED_NORMAL。每个 CPU 都有自己的运行队列，类型为 struct rq。这个数据结构中有一些子队列，每个调度类会和一个子队列关联。

kernel/sched.c

static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

// 精简后的runqueue数据结构
struct rq
{
    raw_spinlock_t lock;
    
    unsigned long nr_running;
    
    // cfs调度类关联的子队列，存放普通进程，它是一棵红黑树
    struct cfs_rq cfs;
    // rt调度类关联的子队列，存放实时进程
    struct rt_rq rt;
    
    // idle调度类是内核用的，只有一个进程，不需要队列
    struct task_struct *idle;
}

调度器入口

内核调度器的入口是一个名为 schedule() 的函数，该函数会调用 pick_next_task() 来选择下一个要运行的进程。调度器需要先和一个具体的调度类相关联，然后由后者去挑选下一个该运行的进程。

kernel/sched.c

static inline struct task_struct *
pick_next_task(struct rq *rq)
{
    const struct sched_class *class;
    struct task_struct *p;

    // 优化：考虑到通常情况下rq中的所有进程都是普通进程
    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;
         
        // 这里不会出现NULL，因为有最低优先级的idle调度类
        class = class->next;
    }
}

进程选择

我们以 CFS 调度类为例，该调度类的 pick_next_task 方法（代码虽然用 C 语言编写，但采用了面向对象的风格）最终会调用 __pick_next_entity 函数来选出下一个可运行的进程。

kernel/sched.fair.c

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

前面提到，struct cfs_rq 这个子队列其实是一棵红黑树。这棵红黑树的节点是以一个名为 vruntime 的值进行排序的，CFS 会直接选出这棵树中最左边叶子节点所代表的进程，即 vruntime 最小的那个进程——这正是 CFS 调度算法的核心！该结果已经被缓存在了 cfs_rq 中。由于红黑树的删除和插入的时间复杂度都是O(log n)，当进程数目很大时，出队和入队维护红黑树的时间开销也不会太大。

kernel/sched.c

// 精简后的cfs_rq定义
struct cfs_rq
{
    struct load_weight load;
    unsigned long nr_running;

    u64 exec_clock;
    u64 min_vruntime;

    struct rb_root tasks_timeline;
    // 队列中缓存了红黑树最左边的叶子节点
    struct rb_node *rb_leftmost;

    struct list_head tasks;
    struct list_head *balance_iterator;

    /*
     * 'curr' points to currently running entity on this cfs_rq.
     * It is set to NULL otherwise (i.e when none are currently running).
     */
    struct sched_entity *curr, *next, *last;

    unsigned int nr_spread_over;
};

抢占

内核提供了一个 need_sched 标志来表明是否需要重新执行一次调度。如果某个进程应该被抢占，scheduler_tick() 就会设置这个标志，该函数由处理器的时钟中断驱动；当一个优先级更高的进程进入可执行状态的时候，try_to_wake_up() 也会设置这个标志。内核会在特定的时刻检查该标志，决定是否执行调度程序，这时才真正发生抢占动作。

用户抢占一直都被支持，因为安全性容易得到保证。用户抢占的动作在以下情况发生：

• 从系统调用返回用户空间时
• 从中断处理程序返回用户空间时

在 2.6 版本的内核中，Linux 引入了内核抢占能力，内核抢占在以下情况发生：

• 从中断处理程序返回内核空间时
• 内核代码持有的所有锁都被释放时

CFS 调度

传统 Unix 系统的进程调度

“进程优先级”和“时间片”是现代进程调度器中两个通用的概念。在 Unix 系统上，优先级以 nice 值的形式输出给用户空间，nice 值会映射到一个处理器的绝对时间。这听起来简单，但是在现实中却会导致许多反常的问题。

1. 进程切换无法最优化进行

假设我们为具有默认 nice 值 0 的进程分配 100ms 的时间片，再给 nice 值 20 的进程分配 5ms (高 nice 值对应低优先级)。如果系统中运行两个同等低优先级的进程，每个进程运行 5ms 就会切换到另外一个进程；如果系统中运行两个同等高优先级的进程，则每个进程运行 100ms 后会切换到另一个进程。这样的分配方式并不理想，即使是对于两个低优先级的进程，我们希望的是它们能各自获得 50% 的处理器时间，而非将太多的处理器时间花在进程的切换上。

2. 相对 nice 值导致运行时间占比差异巨大

假设 nice 值 0 和 1 分别映射到时间片 100ms 和 95ms（O(1)调度器确实这么干了），那么它们的时间差别不大。但是如果进程分别被赋予 18 和 19 的 nice 值，那么它们会分别被映射到 10ms 和 5ms 的时间片，这样会导致其中一个进程获得两倍于另一个进程的处理器时间！由于 nice 值相关的系统调用通常是在原值上增加或减少，因此 nice 值增减带来的效果极大地取决于 nice 的初始值。

3. 时间片必须能在内核的测试范围内

在多数操作系统上，这意味着时间片必须是定时器节拍的整数倍，这么做会引发几个问题：

• 最小时间片、两个时间片的差异必然是定时器节拍的整数倍
• 时间片会随着定时器节拍而改变

4. 基于优先级优化交互任务导致的风险

为了优化交互任务，基于优先级的调度器在唤醒某进程的时候如果认为该进程具有交互性，会通过提升该进程的动态优先级来使其尽快投入运行。这给了一些特殊的进程玩弄调度器的后门，它们可以把自己伪装成一个交互性的进程从而占用大量的处理器时间，打破公平原则。

上述问题的根本原因再在于：分配绝对的时间片引发的固定的切换频率，给公平性造成了很大的变数。上述问题可以通过对传统 Unix 调度器进行非结构性的改造来解决，但是 CFS 采用的方法是对时间片分配方式进行根本性的重新设计：摒弃原有的时间片的概念，而是分配给进程一个处理器使用比重。通过这种方式，CFS 确保了进程调度中能有恒定的公平性，而将切换频率置于不断变动中。

CFS 公平调度

理念

CFS 试图去模拟一个完美的多任务处理器：

“Ideal multi-tasking CPU” is a (non-existent

标签：sched,struct,weight,调度,Linux,进程,rq
From： https://www.cnblogs.com/rookie0080/p/17004663.html