MuQSS调度器之设计文档（一）

MuQSS调度器之设计文档

准备分析Multiple queue skiplist scheduler调度器的实现。此篇是第一篇。

本文翻译自sched-MuQSS.txt文档。
很多还没搞懂，需要去分析下代码。涉及很多操作系统基础知识，无奈学过确忘得差不多，最好根据代码在一起分析温习下操作系统架构知识。

MuQSS作者ck的博客地址

MuQSS-多队列跳表调度器

MuQSS是由原先的BFS调度器通过每个cpu拥有一个8级的跳表队列的变化衍生而来，且具有更细粒度的锁，方便扩展。

目标

MuQSS调度器的设计目标是替换过去的复杂的CPU进程调度器，而实现一种更为简单的调度设计。MuQSS主要针对桌面交互系统，提升调度性能，并且很人性化的没有搞很难理解的启发式的和调优按钮，没有办法去建模和预测调整一个工作负载会对另一个产生负面影响，但是还是很好扩展到多CPU和多进程。

设计概述

BFS中，所有CPUs之间共享一个队列，这意味着每个CPU在寻找下一个运行进程时，需要遍历整个队列，而不管CPU从哪里来？这导致了BFS肯定会有延迟，而且延迟和CPU以及进程的数量有关系。同时，单个队列，意味着不同CPU之间访问队列需要锁竞争，当CPU核数超过16核后，竞争损耗就很大了。此外，查找队列的O(n)算法随着进程数增加，损耗也很大。

MuQSS是BFS的进化，per-CPU的队列，用skiplist代替linked list。

BFS选用单个runqueue的初衷：当有多个runqueues时，不论是per-CPU对应一个队列还是其他情况，都会面临一个问题，那就是多个队列间，需要保证调度公平性以及低延迟的话，需要很复杂的交互同步。

MuQSS通过给skip lists优先级排序的方法，并且新颖的在每个runqueue在选择earliest deadline task时使用了无锁检查（lockless examination)来解决multiple runqueues的弊端。MuQSS调度器并没有均衡系统（balancing system），通过选择下一个进程的调度决策以及选择唤醒CPU的决策来达到均衡的效果。

As a further evolution of the design, MuQSS normally configures sharing of runqueues in a logical fashion for when CPU resources are shared for improved latency and throughput. By default it shares runqueues and locks between multicore siblings. Optionally it can be configured to run with sharing of SMT siblings only, all SMP packages or no sharing at all. Additionally it can
be selected at boot time

设计细节

定制的跳表实现

为了避免构造和拆解skiplist结构的开销，MuQSS使用的跳表的变体：使用8个level的静态数组而不是动态的建立和拆除跳表结构，这样每个队列O(logN)最大至64k个任务，对于SMP系统，有x个CPU，则扩展到x 64k个逻辑数量。

任务插入队列

MuQSS将任务插入per-CPU的队列时间复杂度是O(logN)，插入是有序的，按照任务的静态优先级来确定virtual deadline，然后插入时按virtual deadline排序插入。

niffies

Niffies是个单调递增的纳秒级计数器，Linux内核中的jiffies是毫秒级。每个队列基于TSC高精度定时器来维护其自己的Niffies变量，这将在多个CPUs都被锁住时，维持公平的同步机制时使用。

virtual deadline

虚拟期限时间，这是保证系统低延迟、公平调度的关键点，很好的融合了“nice”等级的机制。其中一个可以调优的参数是**“rr_interval"，或者叫”round robin interval"**，该值是两个相同策略（SCHED_OTHER或者SCHED_NORMAL）的且具有相同nice值的进程将会被运行的最大时间，或者换个说法，就是两个相同nice值的进程之间的运行最大延迟时间。

当一个进程需要获取CPU时间时，它会被分配一个rr_interval以及virtual_deadline，其中virtual_deadline计算：

virtual_deadline = niffies + (prio_ratio * rr_interval)

其中，prio_ratio是和nice值为-20的基础有关的值，nice值每增加1，prio_ratio增加10%。deadline是虚拟的，通常用于来确定谁将是下一个运行的进程。

有三种情况会触发如何选择下一个进程：

• 时间片耗尽。当一个进程的time_slice用完了，将会被调度，然后time_slice会被重新填充，deadline按照上面的公式进行重新计算。
• 进程睡眠sleep。当一个进程不需要CPU的时候，其time_slice和deadline不会被改变，当其下次被调度时再恢复使用。
• 进程抢占。一个更高优先级的新进程抢占当前正在运行的进程。

上面的第一和第二种情况下，选择下一个进程的评判依据：谁的virtual_deadline更earlier，谁就是下一个运行的进程。

不同nice值的进程之间获得CPU比例的不同大约可以这么衡量：

(prio_ration difference)^2

为何需要计算平方值？因为一个进程的deadline只有在time_slice耗尽的情况下才会被改变，所以，即使该进程正在执行，时间在流逝，但其deadline并没有变化，另外一个进程的deadline就在排队，只有当前正在运行的进程被调度了，该排队的进程才能获得CPU时间，这其中niffies值已经随着时间流逝而变大了。

任务查找

由于任务已经预先按序排好在skiplist中，所以查找下一个合适的运行进程的操作就变为找队列的第0层的第一个任务。为了维持多CPUs架构下较低的latency以及较好的fairness，MuQSS以cache locality order对每个队列进行检查，选择所有队列中最合适的进程来执行。The other runqueues are first examine lockless and then trylocked to minimise the potential lock contention if they are likely to have a suitable better task.

这段没看懂MuQSS是如何操作的，需要结合代码再分析分析：

In “interactive” mode, the default setting, MuQSS will look for the best deadline task across all CPUs, while in !interactive mode, it will only select a better deadline task from another CPU if it is more heavily laden than the current one。

MuQSS的查找时间复杂度：O(k)，这里的k是指CPU的数量k。

延迟latency

通过使用virtual deadline来管理控制进程调度顺序，每个队列的延迟被rr_interval保证了，其默认值是6ms。一个CPU密集型任务对CPU的等待将和正在运行的任务数量有关系，通常一个CPU上会有0-2个正在运行的任务，这意味延迟将会控制在7ms之下，这是人类感知限制内的时间。

Additionally, as newly woken tasks will have an early deadline from their previous runtime, the very tasks that are usually latency sensitive will have the shortest interval for activation, usually preempting any existing CPU bound tasks。

tickless expiry

MuQSS的一个特性就是与选择的时钟周期tick无关，其基于高精度时钟，该高精度时钟不依赖于tick赫兹频率而实现了亚毫秒级时钟。这就为MuQSS在低频率时钟系统上比如低于100HZ的系统上的运行奠定了基础，得益于高吞吐量和低功耗。另一个好处就是在full no hz系统上（nohz_full是只要CPU上有正在运行的进程，就关闭其时钟tick，而不是说等CPU变为空闲idle了再去关闭tick），可以不管CPU上有多少个正在运行的进程都可以关闭CPU tick，而不是像之前只有在CPU上有且只有一个可运行的进程时才能关闭tick。

该特性在正常桌面用户环境下并不推荐。

可扩展性和均衡

传统的负载均衡是在基于CPU选择唤醒进程以及根据架构、运算繁忙程度、特定的情况管理等设置一系列规则触发的均衡的综合均衡体现。MuQSS直接在进程唤醒以及选择下一个进程时进行平衡。在初始化时，MuQSS为每个逻辑CPU创建了CPUs的缓存一致性顺序表，当CPU繁忙时，就依赖次顺序表来进行CPU选择。另外，当CPU有以下几种情况繁忙时，MuQSS可以选择任意空闲CPU（如果它们可以选择的话）：

• 同一个线程，空闲或忙碌的缓存，空闲或忙碌的线程
• 其他核心、相同缓存、空闲或繁忙缓存、空闲线程。
• 相同节点，其他 CPU，空闲缓存，空闲线程。
• 相同节点，其他 CPU，繁忙缓存，空闲线程。
• 其他核心，相同的缓存，繁忙的线程。
• 相同节点，其他 CPU，繁忙线程。
• 其他节点、其他 CPU、空闲缓存、空闲线程。
• 其他节点、其他 CPU、繁忙缓存、空闲线程。
• 其他节点、其他 CPU、繁忙线程。

这里的Mux不知道指什么，需要分析下代码。

Mux is therefore SMT, MC and Numa aware without the need for extra intermittent balancing to maintain CPUs busy and make the most of cache coherency。

特性

由于MuQSS最初是为桌面用户而设计的调度器，因此设计了不需要调整、调优或者其他设置来获得性能提升。因此保留了尽可能少的调优参数和入口等。

3个调优参数，2个调度策略

调优参数
rr_interval
interactive
iso_cpu

调度策略
SCHED_ISO
SCHED_IDLEPRIO

这段说和cgroups相关的特性，我没看懂到底是支持还是不支持。看内容意思：does _not_ now feature is supoort for CGROUPS好像是不支持，但后面又说桌面系统上很多应用必须要系统支持cgroups，然后怎么就可以了的，没搞懂。

In addition to this, MuQSS also uses sub-tick accounting. What MuQSS does _not_ now feature is support for CGROUPS. The average user should neither need to know what these are, nor should they need to be using them to have good desktop behaviour. However since some applications refuse to work without cgroups, one can enable them with MuQSS as a stub and the filesystem will be created which will allow the applications to work.

rr_interval

/proc/sys/kernel/rr_interval

毫秒单位，默认值是6ms。合法范围值：1-1000ms。降低该值，会降低延迟，但会增加吞吐量的开销。增大该值，会提高吞吐量，但同时也会提高延迟

interactive

/proc/sys/kernel/interactive

布尔值，0或1，默认是1，打开的。关闭该值，则会关闭MuQSS的near-determinism机制，具体表现就是 在选择下一个进程early deadline任务是不去检查所有的CPUs，或者唤醒哪个CPU。

runqueue sharing

默认情况下，MuQSS在编译的时候就选择了在多核siblings之间队列资源共享（主要是跳表skiplist和锁locking）。初次编译时需要用户配置：

None		no sharing，不共享
SMT	simultaneous multithreading	只在同步多线程之间共享
MC	multicore	多核之间共享
SMP	symmetric multiprocessor	多处理器之间共享

也可以在boot的时候通过rqshare参数传参进去设置。

通常来说，更多系统范围内的共享会提高延迟

The options are:
none, smt, mc, smp

eg:
rqshare=mc

Isochronous scheduling

同步调度？这是个独有的调度策略，设计用来提供接近实时性能的非特权调度。

schedtool -I -e amarok

该命令会以SCHED_ISO调度策略去启动应用amarok。 SCHED_ISO的进程的优先级介于rt实时进程和normal普通进程之间，这样SCHED_ISO进程就可以抢占所有的SCHED_NORMAL进程。

当SCHED_ISO进程耗尽了既定分配的时间后，其会降为SCHED_NORMAL调度策略。那么，这个既定的时间是如何确定的呢？是根据每个CPU的可用时间按比例分配过来的，通过iso_cpu来控制比例分配参数：

/proc/sys/kernel/iso_cpu

默认设置比例是70%。这是根据近5秒内的CPU平均值算出来的。如果设置为100，则给所有的用户可以以SCHED_RR权限运行，设置为0则代表没有实时进程的能力了。

MuQSS的特性就是，当用户需要申请实时调度策略是，它会检查用户是否有权限获得SCHED_RR或SCHED_FIFO策略，如果没有，则分配给用SCHED_ISO策略。

idleprio scheduling

空闲调度，让CPU空闲运行。这个设计理念的背景是：让后台运行的超低优先级的任务对前台任务没有影响。这个非常适合分布式计算客户端如setiathome、folding、mprime等等，也适合视频解码等，不降低其他任务运行速度。为了避免该策略任务一直占用共享资源，如果系统检测到这些任务在等待I/O、阻塞于ram等，会调节其调度策略到SCHED_NORMAL。一旦一个进程的调度策略设置为IDLEPRIO，只要超级用户特权才可以将其设回SCHED_NORMAL策略。

可以通过schedtool命令设置任务使用SCHED_IDLEPRIO策略：

schedtool -D -e ./mprime

Subtick accounting

获得准确的CPU计数是很困难的。通常情况下，是通过时钟滴答来完成的。这是不准确的，因为时钟滴答HZ越来越慢。我们可以做到创建一个任务占用100%CPU，但在某个时间点进行调度切换，让CPU使用率记数为0%。这是一个安全漏洞问题，且意味着无法真正统计一个进程占用CPU的使用率是多少。Mux使用sub-tick计数，TSC高精度时钟，来记录任务真正的CPU使用率。因此MuQSS报告的任务CPU使用率比其自己统计的可能要准确。当比较MuQSS与其他调度器的throughput时，重在对比在特定的墙上时间内完成了多少任务，而不是比CPU使用率。

SMT aware nice

SMT，超线程技术，是现在处理器中的比较常见的特性。SMT有点是单个CPU上可以同时运行多个线程，但这也意味着这多个同时运行的线程是消耗的一个CPU的功耗，这比每个CPU都运行一个线程要慢的多。

尽管smart CPU selection（MuQSS中这么做的）会尽可能让每个任务都去拥有自己的CPU核心运行（在有可用的cpu情况下），但这就不能抵消在所有的cpu核都负载的情况下多了一个线程的时的减速。大多时候，这是无害的，但当一个niced任务和un-niced任务比如（nice19 vs nice0）同时运行时，不同nice值的任务将会获得相同的CPU算力。

MuQSS中有个配置参数SMP-NICE，可以选择性地使用与nice值匹配的比例辅助曲线，来根据nice值的差异分配CPU，当然这会带来一定的开销损耗。如果是非SMT机器上，配置了该选项，开销是最小的。