Linux桌面GUI系统的调度器应该怎么做才不卡顿呢？

本文来谈谈关于操作系统进程调度器的基因方面的东西。

先来看看UNIX/Linux的进程调度器的来龙去脉。

关于太古老的故事，我就长话短说，主要是留下个 UNIX进程调度器从何开始 的印象，这样方便我们理解为什么Linux的进程调度器会是现在的这个效果。

最初，计算机不是分时系统，那时的计算机只能每次运行一个程序，一直到该程序运行结束，中间不能中断。如果谁想利用一台计算机做点事情，那么就必须排队，是的，就像景区游乐设施排队的那种，有时候自己的程序明明只需要执行5分钟，排队可能要排一天，因为有太多的人需要用这台计算机运行5分钟左右的程序了，当然，也有运行8分钟程序的，可能还有运行半小时的，都有。

人们拿着打在孔卡上的程序等待…

优化措施当然是不言而喻，这里面没什么哲学思想，就是普通的套路。让程序自己排队，而不是人拿着程序排队。如此优化之所以可行，有个前提，那就是 程序会自己运行到结束输出结果，程序的逻辑都是编程的人在编程阶段就确定好了的 ，程序运行期间不需要人的干涉。批处理程序就是那时产生的。

程序自己会排队之后，随着程序可能会越来越大，执行时间越来越长，程序之间的运行时间差异变得巨大，这时便有了 程序调度 的需求！比如，让短的程序先执行完，避免它等待太久。

插播一句，我们在大型超市买单结账的地方也总是会看到很多不同的收银台，比如小件物品通道，大宗购物通道等等，这就是调度。

分时系统是如何出现的，这里不细说，反正它就是出现了，时间被分成了很细很细的时间槽，每一个程序占据一个时间槽，用完了时间片就执行下一个程序。在大家把程序都录入系统中后，计算机启动，按照某个调度策略，决定优先执行哪个程序，然后下一个时间槽切换到哪个程序，如此一直到所有程序结束，拿结果，关机。

就这样，历史一直发展到UNIX的出现，进程的概念被抽象了出来， 进程调度系统 作为现代UNIX操作系统的一个独立的子系统正式出现。携带着分时批处理系统的程序调度的基因 ， 携带着分时批处理系统的程序调度的基因 。

…

嗯，UNIX的 基于优先级时间片轮转的抢占式调度器 影响了几乎所有的操作系统的调度器的设计，包括Windows！

我们先看什么是进程优先级。

进程优先级描述了一个进程在 调度时刻的紧急程度 ，一定要强调 “在调度时刻” 这个修饰语，不然在一个进程运行过程中，另一个进程以更高优先级出现，如果不调度的话，即便是更高的优先级也不会有任何作用。

再看时间片，时间片最初的含义是一个进程在 一轮调度周期 所运行的时间，一轮调度周期的意思是 把系统中所有的进程都轮转调度一遍的事件 。

如果每一个进程的时间片都是相同的，那么它将平滑掉优先级的意义，优先级将变得仅仅影响进程第一次运行的先后顺序，后面的调度轮次中，进程优先级将起不到任何标识差异的作用。

于是，4.3BSD采用了1秒抢占制，强行插入 调度时刻 ，每间隔1秒的时间，用优先级来强制差异化(下图来自 https://blog.csdn.net/dog250/article/details/95729830)：

如此一来，优先级高的进程将会在多次间隔1秒的调度时刻获得更多的运行机会。

再往后，4.4BSD/SRV4 UNIX则采用了更加规整的方式来进行细粒度的优先级调度，采用了优先级阶梯下降的调度策略。标准的策略为：

说来说去，UNIX/Linux的所有调度器，均旨在 让优先级高的进程运行得更久一些！这便是分时批处理系统的调度器的基因！该基因一直被继承到了Linux 5.3！

该调度器基因来自于批处理分时系统的程序的性质以及此类系统的首要目标， 批处理系统的目标在于，最大化系统的吞吐率！

至于说UNIX/Linux各个系统版本的调度器之间的差异，无非是做了些许小的调整：

如何避免饥饿。

如何更加平滑。

如何根据进程的行为动态奖惩其时间片。

…此类无大事…

现在，终于到了说说抢占的时候了。

前面有所述，说起优先级，必然要给一个时间点，优先级才有实际的意义，而抢占正是发生在这个时间点，所谓的抢占就是在该时间点，高优先级的进程抢占掉正在运行的低优先级的进程获得CPU资源。

现在让我们看看UNIX/Linux系统中哪里会有这样的时间点。

我们发现，很少有这样的时间点，几乎没有。Why？

首先，UNIX直接始发于分时批处理系统，系统中的进程都是会 自己运行到结束 的，进程优先级在进程创建时就已经确定，调度完全按照优先级来决定一个调度周期内该进程能运行多久的时间，除了nice系统调用可以中途改变进程优先级外，进程的优先级几乎不变，那么除了新进程进入的fork系统调用以及时钟中断之外，没有任何其它地方会有进程调度的时机，也就是没有任何抢占的时刻，所以抢占是不必要的。

但是且慢。动态优先级呢？不是还有动态优先级吗？什么时候动态优先级会改变呢？

答案是在I/O中断中。本来I/O进程为了等待I/O完成就已经睡眠了，当I/O完成的中断到来时，为了让I/O进程尽快恢复执行处理数据，一般会暂时提高I/O完成进程的动态优先级，这个时刻就是一个调度的时刻，如果提高了优先级后的I/O进程比当前的进程的优先级高，那么抢占将在此刻发生。

无疑，这是一个非常棒的优化，但是发生抢占真的会有收益吗？要知道抢占的代价是刷掉当前进程的CPU cache，TLB信息等等，至少在X86平台是这样，这种代价仅仅换取I/O完成的进程赶紧执行，真的好吗？这非常有争议！

我们发现，大多数的Linux服务器都是把抢占给关掉的，以Linux CentOS 7.2为例：

可见，抢占更多的是噱头，代价巨大，华而不实。服务器的目标嘛，最大化吞吐率，至于不让I/O完成进程发生抢占的原因很简单，只要做切换这种额外的进程管理工作，就会占用CPU时间，同时刷cache，tlb会降低访存效率，这些就降低系统的总吞吐，让I/O完成进程至多再等一个调度周期呗。

可见，批处理分时系统的后代们，对CPU时间是多么地吝啬，不会花费哪怕几个微秒来做一些华而不实的事情，一切以最大化吞吐为目标，至于其它的，都是辅助。

现在看 桌面操作系统 ，这种是以人的操作为基本操作，以快速响应人的操作为目标，不管是鼠标的移动，还是键盘输入，或者移动窗口，均是I/O中断驱动，如果桌面操作系统直接使用传统UNIX/Linux调度器的话，UNIX/Linux天生对这类有关 响应度 的目标不敏感，或者说压根就不感兴趣，志不同不相为谋。

不说UNIX，只说Linux，作为UNIX-Like系统，它继承了批处理分时系统的全部基因，它本来就不是为桌面而生的。

也许你会反驳说，完成下面的三件事是不是就意味着Linux可以应对桌面了呢？

打开内核抢占。

打开HZ1000。

切换到CFS调度器。

很抱歉，非也。还是那句话，Linux根本就没有应对桌面场景的基因。

CFS只是让CPU分配时间的时候，更加均匀，平滑和公平，避免了饥饿问题，说实话，在提高I/O响应度方面，它其实并没有O(1) O(1)O(1)做得好。

对于O(1) O(1)O(1)调度器，根据进程的I/O睡眠情况动态调整其优先级以获得抢占当前进程的资格，这是该调度器中最最复杂的部分，这被称作 O(1) O(1)O(1)调度器的交互启发式算法 。该算法的目标是，在一个进程被唤醒的时候，根据其本次睡眠的时间以及睡眠的平均时间，为其计算一个新的优先级，以试图在可能的情况下抢占掉当前的进程。

简单review一下这个Linux内核史上最最复杂的启发式交互判断算法，不涉及细节，因为那样会让人迷失。

当一个进程从睡眠中被唤醒的时候，调度器根据该进程的睡眠时间会为其计算出一个 奖励值 ，根据该奖励值会提升或者降低该进程的优先级，以获得抢占的机会。

但是，这样的计算准确吗？我们指望它来提高桌面系统GUI的响应度来降低人能感受的延迟，可行吗？

假若我在拖拽一个窗口移除视线的遮挡，之后切换到另一个进程的窗口中用键盘打字，然后去调整音乐播放器的进度条，系统调度器凭什么能让所有这一切均流畅呢？换句话说，这些行为背后均伴随有I/O的完成，睡眠的结束，进程优先级的重新计算，CPU时间的奖励，但是，系统是如何排这几件事所在程序的进程优先级的呢？仅凭平均睡眠时间，够吗？

远远不够。

我们知道，优先级是一个在进程调度的时刻瞬时有效的值，系统没有办法对时间进行区分，以使得在I/O完成的当下时刻完成合适的抢占。换句话说， 事情的紧急程度是随着时间而不断变化的！在每一个确定的时刻，优先级的效果都是oneshot的。

没有人频繁操作机器，没有大量种类繁多不确定的I/O完成事件，需要反馈的事件并不多，所以抢占点也并不多，Linux在这种场景下，工作的很不错，可以说是异常优秀，能保证最大化吞吐。然而，桌面环境，频繁的GUI操作，频繁的人工输入和输出，正是相反的场景。

那么该怎么办？

具体来讲，如何可以实现 当点击鼠标，敲击键盘时，系统快速响应，当磁盘I/O结束时，系统可以稍微等一等，当…当… 只要是有外界事件传入，均要设置抢占点，在必要的时候发生抢占。抢占的概率因事件的不同而不同，延迟敏感的事件要更容易发生抢占，而延迟不敏感的事件则可以稍缓。

其实即便时Linux甚至老式UNIX系统一直都在这样做，只是未曾察觉而已。

考虑一下中断的处理，它的优先级就比普通进程的任何优先级都要高。Linux内核十分明确，中断的处理是可以抢占一切的，并且确实也发生了抢占，中断可以抢占任何进程的执行进入中断处理函数。

把中断优先级也看成一种 进程优先级 把中断处理看做一种进程，就看出其中的道道了。

两个思路訇然而出：

为什么不把和中断相关的进程处理和该中断关联，让中断返回后，该进程继续保持优高先级从而继续中断相关的后续呢？

其实Linux的softirq颇有这个意思，但是为什么不把这种事继续传递给更上层的应用程序进程呢？既然已经传递到下半部了，再上一层又何妨？

为什么不把类似拖拽窗口，键盘鼠标这种事件相关联的处理进程也看作是另一种中断呢？

继续下去就是，我们要把中断相关的优先级直接传递给进程，我们为try_to_wakeup函数增加一个参数，指示唤醒进程应该增加的优先级数值：

如何规定某个外设的I/O完成到底提升多少优先级呢？靠启发式算法吗？No！靠拍脑袋？No！

靠统计，靠额外的分析，甚至人体工学领域的分析，调查人眼，人耳的分辨率，手敲键盘的肉体敏感程序。

是的，在编码的时候根据这些额外的调查结论，直接指定唤醒进程的优先级增量，而不是靠什么非常容易误算的平均睡眠时间之类靠非常不靠谱的额外启发式算法来猜测。

现在的问题是，是不是只要是I/O完成，都需要用明确的优先级增量唤醒进程呢？并不是，而是只有在该进程是 前台窗口 进程时，也就是获得了键盘鼠标焦点的窗口处理进程才需要如此，否则，常规的就好，不是焦点窗口，操作者并不care，他也不会操作到非焦点窗口的进程，人只在乎当前前台窗口的反应是否流畅：

执国索因，问题是，如何确定focus字段的值呢？

也不难，就在窗口处理逻辑中设置就好。如果把整个窗口子系统放在内核态实现，当鼠标进入某个窗口并点击时，其处理进程获得焦点：

这样就OK咯。

事实上，Windows采用与此非常类似的做法：

Windows将睡眠事件和优先级增量进行对应

Windows在I/O完成事件后，用特定I/O事件对应的增量重设进程优先级，唤醒进程。

唤醒进程后，用新优先级实施抢占。

用等额时间片方式实施类似SRV4的优先级阶梯下降算法。

所以说，Windows内核的调度器是无条件随时抢占的。

Windows其实就是把窗口焦点得失事件作为像I/O事件一样作为中断一样的事件来处理的，同时，既然中断的概念被泛化，那么和纯硬件中断相反，泛化后的中断必须分层，这就有了IRQL的概念，任何一个时刻，Windows系统总是处在某一个中断级别：

PASSIVE_LEVEL-用户态进程运行级别的中断模拟

APC_LEVEL

DISPATCH_LEVEL

DIRQL-真正的硬件中断

在这一整套框架内，调度器内部的任何函数调用，都像在处理中断一般，每一个XX_LEVEL均会屏蔽其下的LEVEL的执行。每一类的中断，均有相关处理进程的优先级提升级别与之对应。将进程唤醒在那个优先级上运行，之后执行阶梯下降算法。

换句话说，Windows的进程动态优先级是I/O中断精确驱动，随时调整的，这个是和Linux采用启发式算法 微调 之间的最大之不同。

理解一个技术的机制原理非常容易，但是理解为什么会这样颇费工夫。

那么为什么Windows可以设计出和Linux截然不同的调度器，并且在应对桌面GUI处理方面绝佳呢？

这是和UNIX/Linux源自批处理分时系统的基因完全不同的UI基因使然。下面我们就稍微说一下这个与众不同的基因。

Windows诞生在个人计算机兴起的年代，彼时，大家都在购买，组装自己的 个人计算机电脑 。

所谓的个人计算机，字面意思无疑就是不能和大家共享的计算机，用户购买或者组装个人计算机的目的也不是去运行什么批处理数据分析，更多的是娱乐和处理日常！要知道比尔盖茨当时可是将安装Windows的PC机定位为20年后的大众消费品的，想象一下大众的需求就明白Windows善于做什么事了。

彼时的个人电脑，一直到现在，显示器，键盘鼠标都是必不可少的套件，主机甚至都能退而求其次。这些键盘鼠标显示器等外设，正是驱动进程优先级调整的主体，在这种软件架构下，操作系统无疑必须设计成那个样子。

最后，到了现在， 主机甚至消失了 ，当人们在说一体机，在谈Surface Pro的时候，看到更多是屏幕，而不是屏幕后面的那个已经被压缩成饼的主机。

对比Linux系统，除了初始安装时配置网络之外，是不需要显示器鼠标键盘的，甚至初始配置都可以不接显示器，很多网络启动，IPMI之类的都能搞定初始配置这件事，最终Linux服务器剩下的就是一台连着网线的主机，没有什么外设。这是和个人电脑截然相反的特征。

人们用这台个人电脑写文档，做报表，玩游戏，听音乐，聊天…无一不是靠频繁的I/O事件来驱动的，并且， 系统无法预测人的下一个动作是什么，是敲键盘呢，还是移动鼠标拖拽，或者直接砸了电脑？

个人电脑是需要 人不断用鼠标键盘绘图板操作的电脑 的，同时 用耳朵，用眼睛不断接收电脑的反馈，几乎没有人会用Windows电脑去做什么批处理，个人电脑概括起来，那就是 ：

人给电脑一个输入。

电脑快速响应并提供计算服务。

电脑快速展示输出。

所以说，在个人电脑看来，没有什么进程的固定优先级会发挥重要的作用，所有进程的优先级都是随着时间随时调整的，和I/O事件以及GUI事件关联动态优先级才是根本。

嗯，这就是Windows系统的基因。它的目标是短时延，操作者做什么，结果就要最快的速度反馈回来。

嗯，来挖一下根。回到20世纪80年代的DoS时期。

DoS时代，任何调度的需求都不会存在，因为不需要调度，DoS出生伊始就是单用户单任务的系统，这便是其根！当只有一个进程在跑的时候，调度的意义就从进程调度转化为 事件调度 了：

如果DoS跑了一个批处理进程，那么不管它，让它跑完。

如果DoS跑了一个交互进程，那么捕获交互事件并快速响应事件。

后来的Windows 3.1，Windows 95，基于NT4.0的Windows XP这些，虽说都是现代多任务操作系统，但是DoS的基因却被继承，调度事件而不是调度进程。后来的Windows系统最终无非也就是DoS系统的升级，加入了现代操作系统多进程多线程虚拟内存的特征。DoS系统最开始就是 要被人操作的！所以后续的Windows XX自然继承了原是基因。

再次反观Linux，哪有什么键盘鼠标前的操作者，哪有什么盯着显示器的操作者，一般而言，只要将其TCP 22端口打开，接上一根网线(或者Wifi)，远程SSH上去那是最正规的操作，由此而来，Linux系统最常见的I/O事件就是网卡I/O和磁盘I/O等单一的事件，问题是，这种事件是可以等的，可以简单计算，只要超过1000米的距离，数据的网络传输时延就能让主机的调度时延可以忽略不计。

反正我是不会用Linux来玩桌面环境，即便不得已装了一个Ubuntu，Suse，第一件事也是卸掉X，以腾出大量的磁盘空间。

如果真的想用Linux运行桌面环境，那么优化它的调度器便是首先要做的了。

方案就是， Linux按照Windows NT4.0+设计调度器 ，其桌面版GUI操作自然就会流畅很多。

Windows-来自DoS习俗，操作系统是给人操作的。

UNIX/Linux-来自分时批处理，操作系统是跑多任务的。

插播一段，关于Linux调度器，我为什么觉得2.6版本之前的O(n) O(n)O(n)调度器并没有那么糟糕？

是这样的。下面的这句话总结， 不要随便拿出O(n) O(n)O(n)这种度量算法好坏的标准来抨击穷举。因为好多所谓优良的算法在n nn很小的时候都很慢，而在大多数情况下n nn都很小。

正如CFS调度器并没有让人哇塞一样，O(n) O(n)O(n)调度器也不会被人嘘。

优化是一场精细的跷跷板游戏，大多数情况下都是顾此失彼的，时间并不一定能换等价值的空间，空间也不一定能换等价值的时间，总要有损耗的。你把查询换成了索引，以为用空间换了等价值时间，但是有没有想过更大的内存块造成更多的cache miss的代价，所以说，算法分析的O OO并非优化的唯一准绳，还有体系结构。

我一开始是不喜欢Windows的，我和David Miller有一点很类似，就是不喜欢定制化的东西，纯认可通用的东西，然而我并不懂Windows内核，所以一直都保持着对Windows鄙视的观点，最终，我发现，Windows系统显然是个针对个人的高定操作系统啊！

这几天晚上的时候，想看点操作系统方面的技术视频放松一下，优酷，爱奇艺，腾讯视频，哔哩哔哩上的搜索几乎全是鸿蒙的软文软视频，比较失望，无奈油管上结果也还是鸿蒙软视频，搜英文关键词除了Revolution OS(经典纪录片早就已经看过了，给一个bilibili链接：https://www.bilibili.com/video/av9512574/)那个其它的也一样涉及鸿蒙，对于技术人而言，这种Political topic已经对我造成了ddos。

所以，我决定没事时陆陆续续写一点操作系统底层的原理技术方面的随笔，由于是放松时写的，或者本身就是为了放松，所以会通俗化，毕竟我本身就不太会写技术文档和源码分析。

配上一双上好的皮鞋，浙江温州皮鞋湿，下雨进水不会胖！

---------------------

作者：dog250

原文：https://blog.csdn.net/dog250/article/details/96500186