Linux内核中几个比较有意思的解释(进程调度算法，页面调度算法，非线性工作集)

Linux内核中几个比较有意思的解释(进程调度算法，页面调度算法，非线性工作集)

1.O(1)调度器的时间计算公式与CFS调度器

Linux 2.6.23之前普遍采用了O(1)调度器，它是一种基于优先级的时间片调度算法，所谓的O(1)只是它的一些精巧的数据结构使然，在不考虑动态补偿/惩罚的情况下，只要优先级确定，那么时间片就是固定的。2.6.23以后的CFS呢，它是一种基于权重的非时间片调度算法，进程每次执行的时间并不是固定的，而是根据进程数在一个准固定周期内按照其权重比例的时间，依然以时间片为术语，CFS下，进程每次运行的时间与进程的总量有关。
即便在不考虑动态补偿/惩罚的前提下，O(1)依然面临双斜率问题，为了解释这个问题，我先给出进程优先级公式：
prio=MAX_RT_PRIO+nice+20
其中，MAX_RT_PRIO为100，nice为-20到19闭区间内的任意整数。接下来时间片的计算体现了双斜率：
如果prio小于120：time_slice=20*(140-prio)
如果prio大于等于120：time_slice=5*(140-prio)
可见，只要prio确定了，每个进程的时间片也就确定了，以120为分界，高优先级与低优先级的时间片计算是不同的，之所以这样是为了：既要体现高优先级的优势，又不过于削弱低优先级。通过O(1)的逻辑，我们可以算出，所有进程必须完成一轮的调度，即每一个进程必须有机会运行一次，因此“一轮调度”的时间随着进程数量的增加是增加了的。
我们现在看看CFS是怎么逆转这个结局的。CFS调度非常简单，没有太多的计算公式。依然不考虑动态补偿/惩罚，CFS完全按照权重，Linux内核将40个优先级映射了40个权重，为了简化讨论，我假设权重分别为1，1*1.2，1*1.2*1.2，1*1.2*1.2*1.2，....以1.2倍等比例增加，然后定义一个固定的调度周期或以任意一段时间slice内，一个进程运行的时间就是slice*(进程权重/权重和)，可见，如果进程数量增加，所有的进程集体平滑变慢，意思是每次运行的时间减少(时间片不再固定)，所谓的“完全公平”意味着权值大的进程其虚拟时钟步进比较慢，权值小的进程其虚拟时钟步进比较快，CFS在每一个调度点(比如时钟tick，wake up，fork等)选择虚拟时钟最小的进程运行，这是相对于O(1)来讲更加平滑的一种方式，因此体现了一种延迟公平，至于吞吐，还是按照权重来的，而权重映射到了优先级。而O(1)更多的是吞吐公平。
总结来讲，就是O(1)为每个进程计算固定的时间片，而CFS则是在相同的时间段内计算每个进程运行的时间比例，可见二者基点不同，甚至是完全相反的。
现在，我们给出评价。CFS更加平滑，非常适合交互式进程，因为交互进程是饥饿敏感的，但是它们不经常占有CPU，然而一旦需要CPU，必须马上让其予取予求。对于有高吞吐需求的服务进程，CFS并不适合，这种进程的需求是一旦占据CPU，则尽可能让其运行久一些，固定时间片的O(1)更加适合。按照惯常的分类法，I/O密集型的进程多属于交互(可能还有存储类)的，这种进程由I/O驱动，应该满足其任何时刻的CPU需求，因为它们不会占据太久，然而对于CPU密集型进程，得到CPU的机会应该比I/O密集应用少，因为它们一旦获得CPU，就要长期占据。总的来讲，对于桌面客户端，CFS更适合，对于服务器，O(1)更加适合。
本文没有谈及另外两种调度器，也就是Windows调度器以及Linux BFS调度器，前者基于动态优先级提升/恢复，适合桌面应用，后者基于优先级分类O(n)算法，不考虑众核和NUMA扩展，更适合移动终端。

2.缺页中断的Major和Other

所有进程的虚拟地址空间共享一个限量的物理内存，势必需要按需调页，这种做法之所以可行是因为每一个时间点，CPU们只需要少量的物理页面获得映射。现在的问题是，考虑如果出现缺页-页表项中的“存在位”为0，从哪里获得新的page。答案很简单，当然是从代价最小的地方获取page。
我们此时必须考虑缺页时所需page的类型，大致可以分为3类：
1).完全的地址缺页，即该地址曾经没有映射过物理页面。
2).该地址曾经映射过页面，但是被换出到交换空间了。
3).该地址曾经映射的page属于一个文件系统的文件，但是已经解除了映射。
针对以上3种情况，所谓的“代价最小”拥有不同的策略。
首先看1)，这个很简单，直接从伙伴系统分配page即可，当然分配单独一个page所付出的代价相当小，因为伙伴系统之上有一个per cpu的page pool，这个pool的分配不需要任何lock。现在我们看看这个代价小是否足够小，看来是的，但是并不绝对。对于读操作来讲，假设之前有一个page映射于该缺页虚拟地址，后来解除了映射，我们知道此时该page的部分数据已经cache到了CPU cache line中，当再次需要读该page但是缺页时，我们希望获得原先的那个page，愿景是好的，可是我们怎么追踪这个page呢？追踪这个page和缺页进程的关系的代价是否抵消保持cache热度的收益呢？事实上，这很难，因为你要考虑到共享内存的情况，这是一个多对一的双向关系，也就是一个多对多的关系。然而Linux的内存子系统并没有什么都不做，而是它基于一种概率行为将释放到per cpu的page pool的行为分为了cold release和hot release，hot release将page添加到pool的队头，反之到队尾，而per cpu page pool的分配行为是队头分配，如果足够幸运，也许进程可以获得刚刚被解除映射的那个做过读操作的page。内核是怎么保证一个进程是足够幸运的呢？这个很形而上但却也实用，内核采用了一个准LRU算法防止了page在进程之间颠簸，局部性保证了在进程内部一个page被访问后的一段时间内再被访问的几率很大。
再看2)，内核里面运行着一个page回收交换的守护内核线程，发现一个不常被访问要被回收的page是脏page时，内核线程并不是直接启动IO将其写入交换空间，而是暂时先将其排入一个swap cache，也就是给了一个page一次不需要IO而被再次使用的机会，做这样的策略其背后还是局部性原理。当缺页发生时，首先会在swap cache里面寻找，如果找到就不需要进行IO了。做这个策略的现实意义是巨大的，在分级存储原理我们可以知道，内存访问和磁盘IO的时间差了几个数量级，所以不到必须要做，是不会刷swap cache到swap分区的。
最后我们看3)，和2)类似，但是这个涉及到了filesystem的文件page cache，由radix树组织，这个树和page回收是无关的，所谓刷掉一个属于文件的page指的是仅仅将该page解除页表项映射，实际上它完全可能还在文件的radix树中，在发生缺页的时候，如果在radix树中找到了该page，那么只需建立一个映射即可，无需再进行磁盘IO。
综上，我们可以知道，只要不进行磁盘IO就尽量不要，只要不进行磁盘IO的缺页处理就是Minor，进行了IO的则是Major，一个名称而已。如今的内核将Minor进行了细分，但是这并不是重点，因此统一称为Other。
在此不得不提的是LRU算法，一般而言，几乎所有的操作系统都采用了准LRU而不是标准的LRU，这是因为标准LRU只是理论上的，实际实现起来不现实，并不是说硬件消耗巨大，更多是因为“它的效果并不比准LRU好甚至更糟糕”，标准的LRU是一个栈式管理系统，空间局部性诚然重要，然而考虑到循环的话，在循环边界将会面对空间局部性的对立极端，这就是列维长跳！！列维短跳是符合空间局部性的，但是列维长跳是空间局部性的对立。顺便说一句，整个人类社会的任何行为都符合列维长跳原则，如果把量变看做列维短跳，那么质变就是列维长跳，这是根本原则，马克思说过的。
Linux内核采用双时钟二次机会算法模拟了LRU算法，效果非常好。

3.进程地址空间的非线性映射与工作集

Linux内核采用vma来表示进程地址空间中的一段，至于这一段映射了什么vma自己管理，对上层只是提供地址空间的一段连续的虚拟内存。
一般而言，一个文件的一部分对应一个vma，如果需要映射一个文件的不同部分，就需要不同的vma，如果足够幸运，这几个vma可以紧紧挨在一起，但是在两次映射之间，一些别的映射占据了hole，那么就不好玩了，因此需要一种针对文件“重新布局”的方式，下面的图示展示了这个想法：

 

 

但是仅仅针对文件做这个解释难免有点不尽兴。操作系统中有一个工作集的概念，这个概念也是依托局部性原理。工作集就是将不同的内容映射到一个固定的虚拟地址空间窗口，如果CPU的cache line是依据虚拟地址寻址的，那么时间空间局部性将会发挥很大的作用，在这个过程中，TLB也会发挥作用。基于虚拟地址的工作集是虚拟地址空间和物理内存之间的真正隔离。
本质上来讲，非线性映射并不一定要针对文件，它要做的就是“将不同的内容映射到相同的虚拟地址区段”。