Linux任务调度(3)

演进过程

首先，再次回顾下下Linux进程调度器的一个发展历史：

v0.01~v2.4.x: the very first scheduler，复杂度O(n)
v2.6.0~v2.6.22: O(1) scheduler，复杂度O(1)
v2.6.23~: Completely Fair Scheduler (CFS)，复杂度O(log(n))

前一篇文章中我们介绍了v0.01版本中的调度器实现，复杂度为O(n)，在v0.01内核实现中写死了最多可调度的任务数量，只能算作是一个toy！随着从v0.01~v2.4.x版本中的优化，能调度的任务数量也上来了，但是复杂度还是O(n)。

O(1)调度器简介

为了解决此前调度器调度一个进程复杂度为O(n)的问题，O(1)调度器就这么来了。

O(1)调度器，也被称为“常数时间调度器”，是为了解决Linux中早期调度算法的局限性而引入的。其目标是提高调度器的效率和可扩展性，特别是对于具有大量进程的系统。

传统的调度算法，如轮转调度（roundrobin）或基于优先级的调度器，其时间复杂度随着进程数量的增加呈线性增长。这意味着随着进程数量的增加，调度开销也会增加，导致性能下降。

O(1)调度器旨在提供常数时间的调度，无论进程数量如何。O(1)调度器显著减少了调度开销，并提高了整体系统性能。它成为Linux内核的默认调度器多年，直到后续版本中被完全公平调度器（CFS）取代。

重点攻坚问题

O(1)调度器并不只是解决从O(n)到O(1)这一个问题，它还涉及到其他一些很有价值和挑战的问题：

实现完全的O(1)调度：新调度器中的每个算法都能在常数时间内完成，无论运行的进程数量如何。
实现完美的SMP可扩展性：每个处理器都有自己的锁和独立的运行队列。
实现改进的SMP亲和性：尝试将任务分组到特定的CPU上，并继续在那里运行它们。只有在运行队列大小不平衡时才将任务从一个CPU迁移到另一个CPU。
提供良好的交互性能：即使在系统负载较大的情况下，系统也应立即响应并调度交互式任务。
提供公平性：任何进程都不应在合理的时间内被剥夺时间片。同样，任何进程都不应获得不公平的高时间片。
针对只有一个或两个可运行进程的常见情况进行优化，同时能够很好地适应具有多个处理器且每个处理器上有许多进程的情况。

The Big Picture

下图简要展示了O(1)调度器的核心数据结构，以及调度一个任务执行时大致的工作过程。

1）本质上O(1)调度器也是一个支持多优先级的多级反馈队列，结构组织上也是从高优先级到低优先级，每个优先级都有一个队列，其中保存该优先级的任务。2）调度时从高优先级到低优先级队列逐个检查，优先调度高优先级进程来执行，保证公平性。3）同时通过优先级确定其时间片，时间片执行完后就继续调度其他低优先级进程继续执行，避免饿死。4）不同进程的交互性不一样，调度器会给予不同的奖励和惩罚，表现就是动态优先级的差异，根据动态优先级计算出的时间片长短的差异。

工作原理剖析

如何调度1个任务

1、O(1)调度器会为每个CPU创建一个运行队列（分active和expired）和单独的spinlock（尽量减少操作时锁竞争）。

2、每个运行队列都会根据优先级组织成多级队列的形式，每个优先级从高到低都有对应的一个保存任务的queue，保存属于该优先级级别的进程。

3、而进程启动时都有设置静态优先级（nice值），调度器将其放入对应优先级的队列中。在运行过程中调度器也会根据进程优先级、是否是交互程序、执行时间、睡眠时间等计算其动态优先级。调整优先级后将其放入对应优先级的任务队列中。

4、当一个进程的状态发生变化时，如开始执行IO操作从Task_RUNNING变为TASK_UNINTERRUPTIBLE状态时，或者说它的优先级发生变化时，调度器会根据其优先级将其放入相应的运行队列中。

5、调度器寻找下一个可执行的进程时，始终首先从高优先级队列开始检查是否有可运行的进程，从而体现公平性。为了高效地识别出可运行的最高优先级的可运行进程，O(1)调度器使用位图（bitmap）来跟踪每个优先级对应的任务队列的状态。位图bitmap[priorityLevel]==true指示运行队列中某个特定优先级级别的任务列表中是否包含任何可运行的进程。这使得调度器能够快速识别出哪个高级别的队列中具有可运行的进程。

ps：对位图进行查找从而找到对应的最高优先级的队列的这个操作，可以通过一些特殊的指令来加速，比如：x86 bsfl, PPC cntlzw，其他架构下也有对应的指令。

6、确定了最高优先级运行队列后，调度器选择该运行队列中的第一个进程，并安排其执行。每个队列都有一个指向第一个进程的队首指针，可以迅速确定可运行的第一个进程。被调度的进程，会从运行队列中移除，并且调度器更新位图以反映运行队列状态的变化。

7、通过使用这种方法，O(1)调度器实现了常数时间的调度操作。无论系统中的进程或任务数量如何，找到最高优先级任务和调度任务的时间复杂度保持不变。这使得高效且可扩展的调度成为现实，使其适用于具有大量进程的系统。

任务在队列中移动

O(1)调度器使用的runqueue是个支持优先级的多级任务队列，本质上还是个多级反馈队列。意味着其优先级会被调整，任务会在多个队列中移来移去，这也是为了解决公平性、交互性方面的问题。

1、如果一个进程P刚开始处于最高优先级队列中，它的时间片为T，如果P被调度了，其执行一段时间后，假设时钟中断来，调度器需要检查是否应该调度另一个进程时。

如果发现P仍然是当前最高优先级的进程，且其时间片没有用完，那么会继续执行P；
如果发现有更高优先级的进程等着被调度，且支持抢占的话，那么P可能会被抢占；

2、实际上P在执行的过程中，它的优先级是会被动态调整的，比如它做了些IO类的操作：

执行IO密集型操作，恢复后时间片T没耗光，内核会认为这是一个响应式任务，会奖励它，优先级会被调高；
执行IO密集型操作，恢复后时间片T耗光，会认为这不是一个响应式任务，会惩罚它，优先级被调低或者没变化；
执行CPU密集型操作，会认为这不是一个响应式任务，会惩罚它，优先级被调低或者没变化；

3、当其优先级调整后，它就会被移动到对应优先级的任务队列中，等待下一轮被调度。

避免进程被饿死

当某个进程的时间片耗尽时，它会被从active移动到expire中。active、expire是数据结构完全相同的多级运行队列，间下面的prio_array，加入到新队列之前会重新设定它的优先级、时间片，但是expire中的不会参与调度。当active中没有可调度的进程时，就会将active、expire直接交换，这样又开始了下一轮的调度。

struct runqueue {
        spinlock_t          lock;   /* spin lock that protects this runqueue */
        unsigned long       nr_running;         /* number of runnable tasks */
        unsigned long       nr_switches;        /* context switch count */
        unsigned long       expired_timestamp;    /* time of last array swap */
        unsigned long       nr_uninterruptible;   /* uninterruptible tasks */
        unsigned long long  timestamp_last_tick;  /* last scheduler tick */
        struct task_struct  *curr;                /* currently running task */
        struct task_struct  *idle;           /* this processor's idle task */
        struct mm_struct    *prev_mm;        /* mm_struct of last ran task */
        struct prio_array   *active;         /* active priority array */
        struct prio_array   *expired;        /* the expired priority array */
        struct prio_array   arrays[2];       /* the actual priority arrays */
        struct task_struct  *migration_thread; /* migration thread */
        struct list_head    migration_queue;   /* migration queue*/
        atomic_t            nr_iowait; /* number of tasks waiting on I/O */
};

struct prio_array {
        int               nr_active;         /* number of tasks in the queues */
        unsigned long     bitmap[BITMAP_SIZE];  /* priority bitmap */
        struct list_head  queue[MAX_PRIO];      /* priority queues */
};

这个办法也避免了高优先级进程把低优先级进程饿死的问题，因为高优先级进程不管其优先级多高，它们的时间片总会有用完的时刻，这个时刻一到，active中低优先级的进程就可以被调度了。而当active中没有可调度进程时，active、expire交换，又触发了下一轮全新的调度。

ps：active、expire交换的实现方式，这样做和只维护一个active、等所有进程时间片为0时逐个重新计算优先级、时间片相比，效率更高……读写指针交换其实是一种常见的写法了，比如配置reload时。

负载均衡问题

每个CPU都有一个独立的运行队列，调度器会在合适的时候做些负载均衡的操作，以使得各个CPU的运行队列相对平衡。这里的迁移也是有要求的，会考虑CPU affinity、cache、任务优先级、任务状态等来决定应该迁移哪些进程。一般会先从最忙的一个CPU的runqueue中拿一部分到当前CPU的runqueue中，什么叫忙呢？某个CPU的runqueue比当前这个CPU runqueue的任务数量多25%+，就认为存在不平衡，需要迁移一部分过来，但是迁移也要满足上面说的条件，不然收益不见得高。

动、静优先级

前面提到为了改善交互性（interactivity），调度器会对交互式任务进行奖励，而对非交互式任务不进行奖励或者还要惩罚。先抛个问题，怎么识别一个任务是不是具有交互性的任务呢？

让我们先区分下静态优先级和动态优先级：

进程有一个初始优先级，称为nice值，它就是静态优先级。这个值的范围是从20到+19，默认值为零。19是最低优先级，20是最高优先级。这个值存储在进程的task_struct的static_prio成员中，这个变量被称为静态优先级，因为它不会从用户指定的值改变。
调度器则根据存储在prio中的动态优先级来做出决策。动态优先级是根据“静态优先级”和“任务的交互性” 计算得出的。

度量任务交互性

这个“交互性”的度量是一个很关键的步骤，那么怎么度量呢？能准确反映一个任务是I/O密集型还是处理器密集型，一个指示性的指标就是任务的睡眠时间：

如果一个任务大部分时间都在睡眠，那么它是I/O密集型的。
如果一个任务在可运行状态的时间比睡眠时间更长，那么它肯定不是交互式的。
ps: 这一点可以推广到极端情况：几乎所有时间都在睡眠的任务完全是I/O密集型的，而几乎所有时间都在可运行状态的任务完全是处理器密集型的。

Linux O(1)调度器会持续跟踪进程在睡眠状态和可运行状态下的时间消耗，这个值记录在task_struct的sleep_avg成员中。进而根据task_struct中存储的sleep_avg值来计算进程的交互性。

当一个进程从睡眠状态唤醒时，sleep_avg值会增加；
而进程在可运行、运行状态下，每次定时器滴答时，sleep_avg值会减少。

所以这个度量指标既考虑了进程的睡眠时间，也考虑了进程的执行时间，它的最终值偏大则说明具有交互性，反之则不具有交互性。较高的sleep_avg值表示进程更多时间处于睡眠状态，表明它更可能是I/O密集型和交互式的。相反，较低的sleep_avg值表示进程更多时间处于可运行状态，表明它更可能是处理器密集型和不太交互式的。

计算动态优先级

effective_prio()函数根据sleep_avg值在-5到+5之间进行加减操作，计算出动态优先级。

effective_prio()，该方法从任务的nice值开始，根据任务的交互性计算出一个范围在-5到+5之间的奖励或惩罚。例如，一个非常交互式的任务，其nice值为10，可以具有动态优先级为5。相反，一个稍微占用处理器的任务，其nice值为10，可以具有动态优先级为12。在某种理论上的I/O与处理器使用的平衡点上，只有稍微交互的任务不会获得奖励或惩罚，它们的动态优先级等于它们的nice值。

通过这种方式，根据sleep_avg值调整动态优先级，调度器可以给予交互式任务更高的优先级和更长的时间片，使其更具响应性。这种方法有助于平衡I/O密集型和处理器密集型任务的调度，确保系统的公平性和响应性。

ps：see https://web.cse.ohio-state.edu/~champion.17/2431/04-SchedulingLinux.pdf page12，这里提到计算动态优先级、时间片的时机是在进程的时间片用光之后，这个时候才会重新计算。

计算时间片大小

如何通过优先级计算时间片大小呢？

时间片的计算是简单的缩放操作，优先级越高的任务在每轮执行中获得的时间片越多。最高优先级任务（nice值为-20）获得的最大时间片为800毫秒。即使是最低优先级的任务（nice值为+19），也至少获得最小时间片MIN_TIMESLICE，它要么是5毫秒，要么是一个定时器滴答（参见第10章，定时器和时间管理），取两者中较大的值。具有默认优先级（nice值为零）的任务获得100毫秒的时间片。

时间片重新计算的时机，是在时间片用光后，在将其从active队列挪到expire队列之前，完成计算的。

ps：see https://web.cse.ohio-state.edu/~champion.17/2431/04-SchedulingLinux.pdf page12，这里提到计算动态优先级、时间片的时机是在进程的时间片用光之后，这个时候才会重新计算。另外，通过page11也可以了解到，进程的时间片大小是从优先级映射过来的。

多关照交互性任务

另外，调度器为交互式任务提供了一个额外的辅助功能，如果一个任务足够交互式，在它的时间片用尽时，它不会被插入到过期数组中，而是重新插入到活动数组中，这样它可以被调度地更加及时、频繁。

struct task_struct *task;
struct runqueue *rq;

task = current;
rq = this_rq();

if (!--task->time_slice) {
        if (!TASK_INTERACTIVE(task) || EXPIRED_STARVING(rq))
                enqueue_task(task, rq->expired);
        else
                enqueue_task(task, rq->active);
}

设计存在的问题

该方案并非尽善尽美，下面是被指出的最大的问题：

关于“交互性”的度量以及改善调度的代码，变的很复杂、很难理解，它是不是正常工作很难简单说yes or no；
不出意外地，这个调度器本身也很难建模，但是能建模这对于确信它是否能正确地工作很不可或缺。

本文小结

本文介绍了Linux O(1)调度器设计实现，该调度器作为更早期版本的替代方案，最终也被后来的CFS代替了。尽管如此，我们学习了解O(1)调度器的时候，还是可以学习到一些很有价值的设计考量。另外，通过了解O(1)调度器的设计实现，我们对调度中的一些至关重要的衡量指标也理解更深刻了。

作者也是go语言爱好者，我们也可以看到GMP调度中的一些设计应该也是借鉴了Linux内核调度器中的一些设计思路，比如work-stealing等。正所谓，大道至简，很多思路是相同的，能工模型、巧匠窃意！

后续我还会继续总结下Linux CFS调度器的设计实现，欢迎阅读交流！

参考文献

Linux O(1) scheduler, https://litux.nl/mirror/kerneldevelopment/0672327201/ch04lev1sec2.html
Scheduling in Linux: O(n), O(1) Scheduler,https://www.youtube.com/watch?v=vF3KKMI3_1s
Linux Scheduling, https://web.cse.ohio-state.edu/~champion.17/2431/04-SchedulingLinux.pdf
A Scheduling Story, https://ops-class.org/slides/2017-03-03-schedulingstory/

Edit this page on GitHub

Linux任务调度(3)

演进过程 ##

O(1)调度器简介 ##

重点攻坚问题 ##

The Big Picture ##

工作原理剖析 ##

如何调度1个任务 ##

任务在队列中移动 ##

避免进程被饿死 ##

负载均衡问题 ##

动、静优先级 ##

度量任务交互性 ##

计算动态优先级 ##

计算时间片大小 ##

多关照交互性任务 ##

设计存在的问题 ##

本文小结 ##

参考文献 ##