万字长文，锤它！揭秘Linux进程调度器

547次阅读  |  发布于2年以前

说个大事儿

各位吴彦祖&刘亦菲，大家好！

经过深入思考，本号主决定花1-2年时间强更一个系列，暂且叫它《面霸导论》吧！

《面霸导论》有几大块内容：

今天这篇是《面霸导论》第一弹，文章是需要反复琢磨的，今天先来搞一下进程调度。

嘟嘟嘟！抓紧上车了！

准备知识

想深入理解操作系统的进程调度，需要先获得一些准备知识，这样后面就不懵圈啦：

调度的概念

科技源自生活，调度系统绝对不是计算机领域的专利，现实生活中调度无处不在：

“调度是为了解决资源和需求之间的不匹配问题，现实往往是资源少&需求多，计算机领域也是如此。

在操作系统中CPU资源是有限的，需要使用CPU的进程数量是不确定的，并且大部分情况下进程数量远大于CPU数量，如何解决不匹配问题就是进程调度核心：

操作系统分类

操作系统的种类非常多，本身上是硬件层和应用层之间的中间层，对上与应用程序进行交互，对下实现硬件资源的管理。

“批处理是指用户将一批作业提交给操作系统后就不再干预，由操作系统控制它们自动运行，这种采用批量处理作业任务的操作系统称为批处理操作系统，不具有交互性，用户无法干预任务的运行。

“实时系统最大的特点在于计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错，强实时系统一般应用在航空航天、导弹导航制导、核工业等领域。

“分时系统将计算机系统资源（比如CPU）进行时间上的分割，每个时间段称为一个时间片，每个用户依次轮流使用时间片，由于时间间隔很短，每个用户的感觉就像他独占计算机一样，从而有效增加资源的使用率，提高用户交互体验。

Linux属于分时系统，是互联网服务器的主流操作系统，重点研究它就行！

进程分类

根据进程运行时的状态，可以分为：

“在进程占用CPU期间频繁有IO操作，出现IO阻塞等待情况，比如负责监听socket的进程，真正使用CPU进行计算的时间并不多。

“在进程占用CPU期间基本都在进行计算，很少进行IO操作，期间对CPU的真实使用率很高。

进程调度器需要根据进程是IO密集型还是CPU密集型会采用不同的策略。

在调度器中往往需要对IO密集型进程进行奖励来提高其调度优先级，对CPU密集型进程进行惩罚降低其调度优先级。

对进程的奖惩策略是调度器的一项核心工作，希望大家务必理解：

“交互进程往往伴随较多的IO操作，同时也是响应时间敏感的任务，鼠标点一下半天没响应，想想就很糟糕，因此属于高优先级进程。

“非交互进程往往是纯CPU计算，用户是无感知的，所以对响应时间的要求并没有那么高，属于低优先级进程。

进程优先级

根据进程的重要性，可以分为：

“在操作系统中有很多进程，实时进程是相对重要的，需要保证其CPU占用优先级，普通进程并不需要额外照顾。

实时进程和普通进程的进程优先级不同，调度器都会根据优先级来确定进程的CPU优先权和运行时间。

在Linux中影响优先级的两个因素：Nice谦让值和Priority权重值。

PR值由内核来确定，用户可以修改Nice谦让值，进而干预PR值：

nice值也被称为谦让值，数值越大越谦让，会哭的孩子有奶吃，总谦让优先级肯定低了：

非抢占和抢占式

根据进程任务在占用CPU时，使用权是否会被夺取分为：

“进程任务一旦占用CPU只有当任务完成或者因为某些原因主动释放CPU，除上述两种情况外不能被其他进程夺走

“进程任务占用CPU期间可以被其他进程夺走，具体由操作系统调度器决定下一个占用CPU的进程

Linux采用抢占式调度，其可以提高CPU利用率、降低进程的响应时间等，同时也增加了切换进程时的开销，各有利弊。

调度器设计思路

设计目标

有两个指标需要重视：

“进程任务从开始排队等待获取CPU资源直到任务完成的时间差，就像超市排队结账时从开始排队到结算完成离开的时间差。

“进程任务从开始排队等待获取CPU资源直到开始使用CPU的时间差，就像超市排队结账时从开始排队到轮到结算的时间差。

综合来说：

只有做到这几点，调度器才可能在周转时间和响应时间上得到一个良好的表现。

设计实现

要实现一个调度器，主要包括两个核心部分：

算法更多是一种思想，调度器基于某种调度算法进行工程化实现，捋清楚二者的关系对于后续内容的理解将大有裨益。

本章重点

调度算法

调度算法也经历了从简单到复杂的演进，到目前为止也没有哪种调度算法是万能的，抛开场景来评判调度算法优劣并不明智。

以下介绍的主要是调度算法的思想，工程上使用的调度算法往往是其中一种或者几种的变形，更加复杂。

先来先服务FCFS

先来先服务First Come First Service可以说是最早最简单的调度算法，哪个进程先来就先让它占用CPU，释放CPU之后第二个进程再使用，依次类推。

在FCFS中优先被调度的进程如果耗时很长，后续进程都必须要等待这个大CPU消耗的进程，最终导致周转时间直线拉升，也就是护航效应。

最短任务优先SJF

最短任务优先Shortest Job First的思想是当多个进程同时出现时，优先安排执行时间最短的任务，然后是执行时间次短，以此类推。

SJF可以解决FCFS中同时到达进程执行时间不一致带来的护航效应问题：

相比于FCFS可能的执行顺序是A->C->B来说，周转时间和响应时间都得到很大的改善。

SJF的算法思想有些理想化，但并非一无是处，升级改进下也有用武之地：

抢占式最短任务优先PSJF

SJF算法最具启发的地方在于优先调度执行时间短的任务来解决护航效应，但是该算法属于非抢占式调度，对于先后到达且执行时间差别较大的场景也束手无策。

当向SJF算法增加抢占调度时能力就大大增强了，这就是PSJF( Preemptive Shortest Job First )算法。

抢占机制有效削弱了护航效应，周转时间和响应时间都降低了许多，但是还远不够完美。

PSJF算法对于进程A来说却不友好，进程A在被抢占之后只能等待B和C运行完成后，此时如果再来短任务DEF都会抢占A，就会产生饥饿效应。

PSJF算法是基于对任务运行时间长短来进行调度的，但在调度前任务的运行时间是未知的，因此首要问题是通过历史数据来预测运行时间。

时间片轮转RR

时间片轮转RR(Round-Robin)将CPU执行时间按照时钟脉冲进行切割称为时间切片Time-Slice，一个时间切片是时钟周期的数倍，时钟周期和CPU的主频呈倒数关系。

“比如 CPU的主频是1000hz，则时钟周期TimeClick=1ms， Time Slice = n*Time Click，时间切片可以是2ms/4ms/10ms等。

在一个时间片内CPU分配给一个进程，时间片耗尽则调度选择下一个进程，如此循环。

进程往往需要多个循环获取多次时间片才能完成任务，因此需要操作系统记录上一次的数据，等进程下一次被分配时间片时再拿出来，这就是传说中的上下文Context。

进程上下文被存储和拿出的过程被称为上下文切换Context Switch，上下文切换是比较消耗资源的，因此时间片的划分就显得很重要：

RR算法在保障了多个进程都能占用CPU，属于公平策略的一种，但是RR算法将原本可以一次运行完的任务切分成多个部分来完成，从而拉升了周转时间。

RR算法也非银弹，但是响应时间和公平性得到了有效保障，是个非常有意义的算法模型。

多级反馈队列MLFQ

多级反馈队列( Multi-Level Feedback Queue )尝试去同时解决响应时间和周转时间两个问题，具体做法：

上述是MLFQ算法的基本规则，在实际应用中仍然会有一些问题：

针对上述问题MLFQ还需增加几个补丁：

MLFQ的算法思想在1962年被提出，其作者也获得了图灵奖，可谓是影响深远。

在朴素MLFQ算法基础上出现一些变种，通过工程实现和经验配置最终被使用到操作系统中，成为真正的工业级进程调度器。

Linux进程调度器

Linux的进程调度器是不断演进的，先后出现过三种里程碑式的调度器：

O(n)属于早期版本在pick next过程是需要遍历进程任务队列来实现，O(1)版本性能上有较大提升可以实现O(1)复杂度的pick next过程。

CFS调度器可以说是一种O(logn)调度器，但是其算法思想相比前两种有些不同，并且设计实现上也更加轻量，一直被Linux内核沿用至今。

调度器设计核心

要理解这些复杂的调度器设计，我们必须要有一个核心主线，再去理解精髓。

调度器需要解决的关键问题：

事实上，调度器在设计实现上考虑的问题还有很多，篇幅所限只列举几个公共问题。

O(n) 调度器

O(n)调度器采用一个全局队列runqueue作为核心数据结构，具备以下特点：

在Linux中进程使用task_struct结构体来表示，其中有个counter表示进程剩余的CPU时间片：

struct task_struct {
    long counter;
    long nice;
    unsigned long policy;
    int processor;
    unsigned long cpus_runnable, cpus_allowed;
}

counter值在调度周期开始时被赋值，随着调度的进行递减，直至counter=0表示无可用CPU时间，等待下一个调度周期。

O(n)调度器中调度权重是在goodness函数中完成计算的：

static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
{
        int weight;
        weight = -1;
        /*进程可以设置调度策略为SCHED_YIELD即“礼让”策略，这时候它的权值为-1,权值相当低*/
        if (p->policy & SCHED_YIELD)
                goto out;

        /*
         * Non-RT process - normal case first.
         */

        /*对于调度策略为SCHED_OTHER的进程，没有实时性要求，它的权值仅仅取决于
         * 时间片的剩余和它的nice值，数值上nice越小，则优先级越高，总的权值 = 时间片剩余 + (20 - nice)
         * */
        if (p->policy == SCHED_OTHER) {
                /*
                 * Give the process a first-approximation goodness value
                 * according to the number of clock-ticks it has left.
                 *
                 * Don't do any other calculations if the time slice is
                 * over..
                 */
                weight = p->counter;
                if (!weight)
                        goto out;

#ifdef CONFIG_SMP
                /* Give a largish advantage to the same processor...   */
                /* (this is equivalent to penalizing other processors) */
                if (p->processor == this_cpu)
                        weight += PROC_CHANGE_PENALTY;
#endif

                /* .. and a slight advantage to the current MM */
                if (p->mm == this_mm || !p->mm)
                        weight += 1;
                weight += 20 - p->nice;
                goto out;
        }

        /*
         *对于实时进程，也就是SCHED_FIFO或者SCHED_RR调度策略，
         *具有一个实时优先级，总的权值仅仅取决于该实时优先级，
         *总的权值 = 1000 + 实时优先级。
         * */
        weight = 1000 + p->rt_priority;
out:
        return weight;
}

从代码可以看到：

#if HZ < 200
#define TICK_SCALE(x)        ((x) >> 2)
#elif HZ < 400
#define TICK_SCALE(x)        ((x) >> 1)
#elif HZ < 800
#define TICK_SCALE(x)        (x)
#elif HZ < 1600
#define TICK_SCALE(x)        ((x) << 1)
#else
#define TICK_SCALE(x)        ((x) << 2)
#endif

#define NICE_TO_TICKS(nice)        (TICK_SCALE(20-(nice))+1)

NICE_TO_TICKS是个宏函数，根据不同的调度频率HZ有对应的TICK_SCALE宏定义，这样就解决了不同优先级的进程的时间片分配问题。

O(n)调度器对实时进程和普通进程采用不同的调度策略：

在runqueue中搜索下一个合适的进程是基于动态优先级来实现的，动态优先级最高的就是下一个被执行的进程。

O(n)调度器设计和实现上存在一些问题，但是其中的很多思想为后续调度器设计指明了方向，意义深远。

O(1)调度器

O(n)调度器在linux内核中大约使用了4年，在Linux 2.6.0采纳了Red Hat公司Ingo Molnar设计的O(1)调度算法，该调度算法的核心思想基于Corbato等人提出的多级反馈队列算法。

O(1)调度器引入了多个队列，并且增加了负载均衡机制，对新出现的进行任务分配到合适的cpu-runqueue中：

为了实现O(1)复杂度的pick-next算法，内核实现代码量增加了一倍多，其有以下几个特点：

struct runqueue {
        spinlock_t lock;
        unsigned long nr_running;
        unsigned long long nr_switches;
        unsigned long expired_timestamp, nr_uninterruptible;
        unsigned long long timestamp_last_tick;
        task_t *curr, *idle;
        struct mm_struct *prev_mm;
        prio_array_t *active, *expired, arrays[2];
        int best_expired_prio;
        atomic_t nr_iowait;
        ......
};

prio_array_t结构体的定义：

#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
typedef struct prio_array prio_array_t;
struct prio_array {
        unsigned int nr_active;
        unsigned long bitmap[BITMAP_SIZE];
        struct list_head queue[MAX_PRIO];
};

O(1)调度器对pick-next的实现：

idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);

array = rq->active;
if (unlikely(!array->nr_active)) {
        /*
         * Switch the active and expired arrays.
         */
        rq->active = rq->expired;
        rq->expired = array;
        array = rq->active;
        rq->expired_timestamp = 0;
        rq->best_expired_prio = MAX_PRIO;
}

O(1)和O(n)调度器确定进程优先级的方法不一样，O(1)借助了sleep_avg变量记录进程的睡眠时间，来识别IO密集型进程，计算bonus值来调整优先级：

#define NICE_TO_PRIO(nice)        (MAX_RT_PRIO + (nice) + 20)
#define NS_TO_JIFFIES(TIME)        ((TIME) / (1000000000 / HZ))
#define CURRENT_BONUS(p) \
        (NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
                MAX_SLEEP_AVG)

static int effective_prio(task_t *p)
{
        int bonus, prio;

        if (rt_task(p))
                return p->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;
}

O(1)调度器为了实现复杂场景IO密集型任务的识别，做了大量的工作仍然无法到达100%的准确，但不可否认O(1)调度器是一款非常优秀的产品。

CFS调度器

O(1)调度器本质上是MLFQ算法的思想，随着时间的推移也暴露除了很多问题，主要集中在O(1)调度器对进程交互性的判断上积重难返。

无论是O(n)还是O(1)都需要去根据进程的运行状况判断它属于IO密集型还是CPU密集型，再做优先级奖励和惩罚，这种推测本身就会有误差，而且场景越复杂判断难度越大。

是继续优化进程交互性算法，还是另辟蹊径呢？一直困扰着Linux社区的大神们。

Con Kolivas和RSDL调度器

在CFS出现之前，不得不提一位有态度&有实力的麻醉师Con Kolivas，同时也是linux内核开发者，他在进程调度领域有自己独到的见解。

Con Kolivas针对O(1)调度器存在的维护和优化问题，提出了楼梯调度算法（Staircase Deadline Scheduler）和 基于公平策略RSDL调度器(The Rotating Staircase Deadline Schedule)，遗憾的是Linux之父并没有采纳RDSL调度器。

对此Con Kolivas感到很愤怒，离开了Linux内核开发社区，但是事实上从后面CFS调度器几个版本的修订来看，Con Kolivas的大方向是正确的，离开之后的Con Kolivas又开发了BFS(Brain Fuck Scheduler)来对抗CFS调度器。

“没错，BFS调度器译为脑残调度器，可见Con Kolivas的愤怒和不满。

Linux之父选择了CFS调度器，它借鉴了Con Kolivas的楼梯调度算法和RSDL调度器的经验，由匈牙利人Ingo Molnar所提出和实现，并在Linux kernel 2.6.23之后取代O(1)调度器，名震江湖。

CFS调度器

在2.6.23内核中引入scheduling class的概念，将调度器模块化，系统中可以有多种调度器，使用不同策略调度不同类型的进程：

这样一来，CFS调度器就不关心实时进程了，专注于普通进程就可以了。

CFS( Completely Fair Scheduler )完全公平调度器，从实现思想上和之前的O(1)/O(n)很不一样。

我的脑海里浮现了这幅漫画，我想右边的应该更好，按需分配&达成共赢。

这个世界怎么会有绝对的公平呢？为啥这个调度器敢说自己是完全公平呢？

这一切CFS是如何实现的呢？我们继续看！

优先级和权重

O(1)和O(n)都将CPU资源划分为时间片，采用了固定额度分配机制，在每个调度周期进程可使用的时间片是确定的，调度周期结束被重新分配。

CFS摒弃了固定时间片分配，采用动态时间片分配，本次调度中进程可占用的时间与进程总数、总CPU时间、进程权重等均有关系，每个调度周期的值都可能会不一样。

CFS调度器从进程优先级出发，它建立了优先级prio和权重weight之间的映射关系，把优先级转换为权重来参与后续的计算：

const int sched_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,
};

“普通进程的优先级范围是[100,139]，prio整体减小120就和代码左边的注释对上了，也就是nice值的范围[-20,19]，因此sched_prio=0相当于static_prio=120。

比如现有进程A sched_prio=0，进程B sched_prio=-5，通过sched_prio_to_weight的映射：

在CFS中引入sysctl_sched_latency(调度延迟)作为一个调度周期，真实的CPU时间表示为：

显然这样根据权重计算后的各个进程的运行时间是不等的，也就违背了"完全公平"思想，于是CFS引入了虚拟运行时间(virtual runtime)。

虚拟运行时间

每个进程的物理运行时间时肯定不能一样的，CFS调度器只要保证的就是进程的虚拟运行时间相等即可。

那虚拟运行时间该如何计算呢？

“virtual_time = wall_time * nice_0_weight/sched_prio_to_weigh

比如现有进程A sched_prio=0，进程B sched_prio=-5：

经过这样映射，A和B的虚拟时间就相等了。

上述公式涉及了除法和浮点数运算，因此需要转换成为乘法来保证数据准确性，再给出虚拟时间计算的变形等价公式：

“virtual_time = (wall_time * nice_0_weight * 2^32/sched_prio_to_weigh)>>32

“令 inv_weight = 2^32/sched_prio_to_weigh

“则 virtual_time = (wall_time * 1024 * inv_weight)>>32

由于sched_prio_to_weigh的值存储在数组中，inv_weight同样可以：

const u32 sched_prio_to_wmult[40] = {
/* -20 */     48388,     59856,     76040,     92818,    118348,
/* -15 */    147320,    184698,    229616,    287308,    360437,
/* -10 */    449829,    563644,    704093,    875809,   1099582,
/*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
/*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
/*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
/*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
/*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

经过一番计算，各个进程的虚拟运行时间一致了，似乎我们理解了"完全公平"的思想。

虚拟运行时间与优先级的衰减因子有关，也就是inv_weight随着nice值增大而增大，同时其作为分母也加速了低优先级进程的衰减。

“简言之：CFS将物理运行时间在不同优先级进程中发生了不同的通胀。

摒弃了固定时间片机制也是CFS的亮点，系统负载高时大家都少用一些CPU，系统负载低时大家都多用一些CPU，让调度器有了一定的自适应能力。

pick-next和红黑树

那么这些进程应该采用哪种数据结构来实现pick-next算法呢？

CFS调度器采用了红黑树来保存活跃进程任务，红黑树的增删查复杂度是O(logn)，但是CFS引入了一些额外的数据结构，可以免去遍历获得下一个最合适的进程。

红黑树的key是进程已经使用的虚拟运行时间，并且把虚拟时间数值最小的放到最左的叶子节点，这个节点就是下一个被pick的进程了。

前面已经论证了，每个进程的虚拟运行时间是一样的，数值越小表示被调度的越少，因此需要更偏爱一些，当虚拟运行时间耗尽则从红黑树中删除，下个调度周期开始后再添加到红黑树上。

本章重点

参考资料

Copyright© 2013-2020

All Rights Reserved 京ICP备2023019179号-8