为什么LinuxCFS调度器没有带来惊艳的碾压效果

任何范畴，革命性的碾压式移风易俗并不是没有，可是概率极低，人们遍及的傲慢在于，总是以为自己所置身的环境正在发生着某种碾压式的改造，但其实，终究大概率不过是一场平凡。

作者| dog250

责编 | 刘静

出品 | CSDN博客

凡是懂Linux内核的，都知道Linux内核的CFS进程调度算法，不管是从2.6.23将其初引进时的论文，仍是各类源码剖析，文章，以及Linux内核专门的图书，都给人这样一种感觉，即CFS调度器是革命性的，它将彻底改动进程调度算法。预期中，人们等待它会带来令人冷艳的作用。

可是这是幻觉。

人们期望CFS速胜，可是剖析来剖析去，却仅仅在某些方面比O(1)调度器略微好一点点。乃至在某些方面比不上陈旧的4.4BSD调度器。可是人们却仍然对其趋之若鹜，特别是源码剖析，汗牛塞屋！

为什么CFS对其他调度算法没有带来碾压的作用呢？

首要，在实在国际，碾压是不存在的，人与人，事与事已然被放在了同一个重量级队伍比较，其之间的不同没有幻想的那么大，底子就不在谁碾压谁。不能被小说电视剧电影遮盖了，此外，徐晓冬大摆拳暴打雷雷也不算数，由于他们本就不是一个队伍。

任何范畴，革命性的碾压式移风易俗并不是没有，可是概率极低，人们遍及的傲慢在于，总是以为自己所置身的环境正在发生着某种碾压式的改造，但其实，终究大概率不过是一场平凡。

任何范畴，革命性的碾压式移风易俗并不是没有，可是概率极低，人们遍及的傲慢在于，总是以为自己所置身的环境正在发生着某种碾压式的改造，但其实，终究大概率不过是一场平凡。

终究就呈现了角力，相持。

其次，咱们应该看到，CFS调度器声称它会给交互式进程带来福音，在这方面CFS的确比O(1)做得好，可是冷艳的作用来自于粉丝的认同。Linux体系交互进程原本就不多，Linux更多地被装在服务器，而在服务器看来，吞吐是要比交互呼应愈加重要的。

那么以交互为主的Android体系呢？咱们知道，Android也是选用了CFS调度器，也有一些事BFS，为什么相同没有带来冷艳的作用呢？

我供认，2008年前后呈现CFS时还没有Android，比及Android呈现时，其选用的Linux内核现已默认了CFS调度器，咱们看下Android版别，Linux内核版别以及发行时刻的联系：

Linux内核在2.6.23就选用了CFS调度器。所以一个原因便是没有比较。Android体系上，CFS没有时机和O(1)做比较。

其他，即使回移一个O(1)调度器到Android体系去和CFS做AB，在我看来，CFS相同不会冷艳，原因很简略，Android体系几乎都是交互进程，却前台进程永久只需一个，你几乎感触不到进程的切换卡顿，换句话说，即使CFS对待交互式进程比O(1)好太多，你也感触不到，由于关于手机，平板而言，你切换APP的时刻远远大于进程切换的时刻粒度。

那么，CFS究竟好在哪里？

简略点说，CFS的含义在于，在一个稠浊着许多核算型进程和IO交互进程的体系中，CFS调度器对待IO交互进程要比O(1)调度器愈加友善和公正。了解这一点至关重要。

其实，CFS调度器的理念非常陈旧，就说在业界，CFS的思维早就被应用在了磁盘IO调度，数据包调度等范畴，乃至最最陈旧的SRV3以及4.3BSD UNIX体系的进程调度中早就有了CFS的身影，能够说，Linux仅仅运用CFS调度器，而不是规划了CFS调度器！

就以4.3BSD调度器为例，咱们看一下其调度原理。

4.3BSD选用了1秒抢占制，每间隔1秒，会对整个体系进程进行优先级排序，然后找到优先级最高的投入运转，非常简略的一个思维，现在看看它是怎样核算优先级的。

首要，每一个进程j均具有一个CPU滴答的度量值Cj，每一个时钟滴答，当时在运转的进程的CPU度量值C会递加：

当一个1秒的时刻区间ii曩昔之后，Cj被重置，该进程jj的优先级选用下面的公式核算：

能够核算，在一个满足长的时刻段内，两个进程运转的总时刻比例，将和它们的base_Priobase_Prio优先级的比例持平。

4.3BSD的优先级公正调度是CPU滴答驱动的。

现在看Linux的CFS，CFS选用随时抢占制。每一个进程j均带着一个虚拟时钟VCj，每一个时钟滴答，当时进程k的VCk会从头核算，一起调度器挑选VC最小的进程运转，核算方法非常简略：

可见， Linux的CFS几乎便是4.3BSD进程调度的自驱无级变速版别！

假如你想了解CFS的精华，上面的便是了。换成言语描绘，CFS的精华便是 “n个进程的体系，恣意长的时刻周期TT，每一个进程运转T/n的时刻！”

当然，在实际和完成中，会有80%的代码处理20%的剩下问题，比方怎样奖赏睡觉太久的进程等等，可是这些都不是精华。

综上，咱们总结了：

实际国际很难碾压同级其他人或事。

许多的Linux服务器不需求照料交互进程，CFS优势无法凸显。

许多的Android体系没有和O(1)同台竞技的时机。

许多的Android体系交互进程很难感知进程调度这件事。

CFS调度思维古已有之。

所以不管从概念仍是从作用，Linux CFS调度器均没有带来令人眼前一亮的哇塞作用。可是还缺陷什么。嗯，技能上的解说。

剖析和解说任何一个机制之前，必定要先问，这个机制的方针是什么，它要处理什么问题，这样才有含义。而不能仅仅是了解了它是怎样作业的。

那么Linux CFS调度器被选用，它的方针是处理什么问题的呢？它肯定是针对O(1)算法的一个问题而被引进并替代O(1)，该问题或许并非什么臭名远扬，可是的确是一枚钉子，有必要拔除。

O(1)调度器的实质问题在于进程的优先级和进程可运转的时刻片进行了强映射！

也便是说，给定一个进程优先级，就会核算出一个时刻片与之对应，咱们疏忽奖惩相关的动态优先级，看一下原始O(1)算法中一个进程时刻片的核算：

#definebase_TIMESLICE(p) (MIN_TIMESLICE + /

((MAX_TIMESLICE - MIN_TIMESLICE) * /

(MAX_PRIO-1- (p)->static_prio) / (MAX_USER_PRIO-1)))

staticinlineunsignedinttask_timeslice(task_t*p)

{

returnbase_TIMESLICE(p);

}

直观念显现：

针对上述问题，2.6内核的O(1)O(1)引进了双斜率来处理：

staticunsignedinttask_timeslice(task_t*p)

{

if(p->static_prio

returnSCALE_PRIO(DEF_TIMESLICE*4, p->static_prio);

else

returnSCALE_PRIO(DEF_TIMESLICE, p->static_prio);

}

直观图示如下：

形似问题处理了，可是假如单单抓住上图的某一个优先级子区间来看，仍是会有问题，这便是相对优先级的问题。咱们看到，高优先级的时刻片是缓慢增减的，而低优先级的时刻片却是猛然增减，相同都是相差相同优先级的进程，其优先级散布影响了它们的时刻片分配。

原本是治瘸子，成果腿好了，可是胳臂坏了。

实质上来讲，这都源自于下面两个原因：

固定的优先级映射到固定的时刻片。

相对优先级和肯定优先级稠浊。

那么这个问题怎样处理？

优先级和时刻片原本便是两个概念，二者中心还得有个变量沟通才能够。优先级高仅仅阐明该进程能运转的久一些，可是究竟久多少，并不是仅仅优先级就能决议的，还要归纳考虑，换句话间隔来说，假如只需一个进程，那么即使它优先级再低，它也能够永久运转，假如体系中有许多的进程，即使再高优先级的进程也要让出一些时刻给其它进程。

所以，考虑到体系中整体的进程状况，将优先级转换为权重，将时刻片转换为比例，CFS便是了。终究的坐标系应该是权重占比/时刻片坐标系而不是权重(或许优先级)/时刻片。应该是这个滑润的姿态：

看来，Linux CFS仅仅为了处理O(1)O(1)中一个“静态优先级/时刻片映射”问题的，那么可想而知，它又能带来什么冷艳作用呢？这儿还有个“可是”，这个O(1)O(1)调度器的问题其实在核算密集型的看护进程看来，并不是问题，反而是功德，究竟高优先级进程能够无条件持续运转好久而不切换。这关于吞吐率的进步，cache运用都是有优点的。无非也就侵扰了交互进程呗，又有何妨。

当然，运用调优CFS的时分，不免也要遇到IO睡觉奖惩等剩下的工作去规划一些trick算法，这花费精力。

对了，还要设置你的内核为HZ1000哦，这样更能体现CFS的滑润性，就像它声称的那样。我难以幻想，出了Ubuntu，Suse等花哨的桌面发行版之外，还有哪个Linux需求翻开HZ1000，服务器用HZ250不挺好吗？

关于调度的论题根本就说完了，可是在进入下一步固有的喷子环节之前，还有两点要着重：

CFS的时刻片是动态的，是体系负载均衡以及其优先级的函数，这便能够把进程调度动态适应到体系最佳，以节约切换开支。

即使是到了多核年代，关于实时进程仍然像单核年代那般严厉遵从最优先调度。

我仍是想说，在调度器规划方面，大部分的人们重视点错了！

在CPU核数越来越多的年代，人们更应该关怀把进程调度到哪里CPU核上而不是某个CPU核要运转哪个进程。

单核年代一路走过来的Linux，开展迅猛，这无可厚非，可是成果一个操作体系内核的并不单单是技能，还有其他。这些当然程序员们很不爱听，程序员最烦非技能方面的东西了，程序员跟谁都比写代码，程序员特别喜爱喷领导不会写代码如此。

Linux在纯技能方面并不优异，Linux整体上优异的原因是由于有一群非代码不明志的程序员在让它变得越来越优异，另一方面还要归功于开源和社区。Linux的学习门槛极低，假如一个公司能不费吹灰之力招聘到一个Linux程序员的话，那它干嘛还要费力九牛二虎之力去招聘什么高端的BSD程序员呢？终究的成果便是，Linux用的人极多，想换也换不掉了。

但不管怎样也无法补偿Linux内核上的一些原则性过错。

Linux内核仍是以原始的主线为base，以讲Linux内核的书为例，经典的Robert Love的《Linux内核规划与完成》，以及《深化了解Linux内核》，在讲进程调度的时分，关于多核负载均衡的翰墨都是少之又少乃至没有，如此经典的作品把许多同好引向了那万劫不复的代码深渊。于是乎，漫山遍野的CFS源码剖析接连不断。

但其实，抛开这么一个再一般不过的Linux内核，现代操作体系进入了多核年代，其中心正是在cache运用上的改造，带来的改动便是进程调度和内存办理的改造。review一下Linux内核源码，这些改动早就现已体现了出来。

可悲的是，关于Linux内核的经典书本却再也没有更新，全部的从传统校园出来的喜爱看书学习的，仍然是抱着10年前的大部头在啃。

当然了，Linux内核作为一个代码来讲，它是普适的，所以社区很难看到且重视单单是多核的问题，社区重视的最多的是可维护性，而不是功能。Linux新特性在128MB内存的i386机器上跑没有问题，那便是OK的。只需不是80%以上的人遭受的新问题，社区是从不care的，一起，正由于如此，社区还会引进bug，这也是令人想叹气都不能叹气。

我的观点吧，社区仅仅一个全部以代码为绳尺的程序员社区，社区不会过于重视体系结构的开展和新特性，这些都是厂商的工作。

回到进程调度的论题，正由于Linux一直在重视调度算法自身以及其完成的代码，才会呈现The Linux Scheduler: a Decade of Wasted Cores，这篇非常中肯的paper：

http://www.ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf

相同，我一贯喷的TCP也是如此，人们重视TCP的完成代码自身，才会让它越来越杂乱，然后越来越软弱，或许你会说这便是进化，可是趁着万劫不复前，不是还有回炉的时机吗？还没有进化到有必要持续进化的境地吧。假如站在外面看且具有强制措施，估量早就没有废物TCP了吧。

浙江温州皮鞋湿，下雨进水不会胖。