CPU高速缓存与反置页表&调度的科普

虽然我喜欢分级页表，但是反置页表才是更加自然的方式。之所以叫做 反置 页表，大概是因为它颠倒我们常规理解的寻址：

• 根据地址拿到数据，在MMU意义上就是根据虚拟地址拿到物理地址。

而反置页表将上述问题转换成了：

• 给出一个虚拟地址，试问有没有哪个物理页面映射了它，如果有，找出来。

嗯，是个问句，那么就难免牵扯进去诸如搜索的操作了。

由于描述全部物理内存全系统一张表就足够，最不济的方式就是把这一张表遍历搜索一遍呗。于是就会出现一些论调，比如虽然反置页表效率太低，不太适合硬件实现等等。

但是且慢，其实我们早就已经在跟类似反置页表的机制打交道了，那就是 CPU高速缓存 。你可以质疑反置页表的实现尚有缺陷，但是质疑反置页表的本质，便无遗是在质疑CPU高速缓存机制本身。

CPU高速缓存(以虚拟地址高速缓存为例)解决的问题可以归纳为：

• 给出一个虚拟地址，试问高速缓存里是否已经缓存了它的数据，如果有，找出来。

这便就是反置页表要解决的问题。完全一致啊！

下面的问题是，如何把CPU高速缓存的那套实现机制，借鉴给反置页表。

显然，直接照搬是困难的，因为它们虽然机制完全类似，但是却是处理其大小具有数量级差异的地址空间，这本身就是一个大的问题。

硬件并行查找128K是容易实现的，但是硬件并行查找128G便不是了。这里不展开细节了，关于这个话题可以参考一本非常不错的书：
《现代体系结构上的UNIX系统：内核程序员的对称多处理和缓存技术》
它在douban上的链接：
https://book.douban.com/subject/26290762/
这本书是我2015年11月份去鹅厂上班前读的，没有读完，后来工作内容与此无关了，就没有继续，现在又翻到了它，索性接着读下去吧。

对了，反置页表类似于该书第4章描述的 带有进程键值的虚拟高速缓存(进程切换不用flush的那种…) ，进程键值也就是进程的PID了。

另外还有一个Tip就是， 反置页表不能使用高速缓存的组相联机制，但是却非常类似全相联 ，Why？

因为组相联完全依赖内存访问的时间局部性和空间局部性，这一点亘古不变，然而，物理内存向虚拟内存的映射却不满足这种局部性，或者说不完全满足。

物理内存管理要解决的问题除了局部性带来的访问效率问题之外，还要解决空间利用率问题，即碎片问题，此外，物理内存全部进程共享，所以还需要在所有进程之间满足公平性需求：

1. 局部性需求。
2. 碎片最小化需求。
3. 公平性需求。

以Linux内核的伙伴系统为例，它就是为此而准备的，而局部性问题则由伙伴系统上层的slab/slub机制来保证。

也就是说，物理页面的分配并不一定按照CPU的MMU期望或者说至少理解的那样去进行，中间隔了好几个抽象层。所以说：

• 任意物理页表可以映射给任意进程的任意虚拟地址。

这不就是全相联嘛。

如果就此结束本文，那就真的显得连吹水都不是了，所以，接下来还是要吹水的。

再说说反置页表的实现，几乎可以肯定不能用CPU高速缓存的实现方案，因为地址空间差异太大，过于昂贵。如果纯软件化，那效率又过于低下，如何来权衡？

这里不谈TLB，那是另一个话题。

这里介绍一个思路，用TCAM加以改造。

既然不用CPU高速缓存的方案，那么用路由表的方案总可以，因为路由表条目的数量级和物理页面条目数的数量级相当。

2015年写过一篇关于此的文章：
硬件路由转发原理浅析 https://blog.csdn.net/dog250/article/details/46952233
就是这个思路。

反置页表就说到这了。下面说说CPU高速缓存和调度之间的合离。

假设没有高速缓存，现代多核系统上的调度要容易太多。就是一个简单的多处理器空间分配问题：

• 单处理器调度
  合理安排一个进程在什么时间点投入运行的问题。
• 多处理器调度
  假设处理器无穷多个，那便是合理安排一个进程在哪个处理器上运行的问题。如果有限多个处理器，且进程数量多于处理器数量，那便掺和一些单处理器调度的策略，但是无遗，单处理器调度策略总体上的作用弱很多，核心还是进程/处理器的空间映射问题，换句话说，多处理器的调度其实类似 内存分配问题 。

正是有了高速缓存，才让多核的概念从多处理器中剥离了出来(当然，除了高速缓存，还有运算单元共享，流水线等因素)，并且以缓存的细节示区别。高速缓存的组织方式，极大地影响了进程调度的策略。

多核架构一般可以按照核，处理器，封装等分为三个或者多个层次，比如下面的二级结构：

{(CPU1​,CPU2​),(CPU3​,CPU4​)}
我们说

C

P

U

1

CPU_1

CPU1​和

C

P

U

2

CPU_2

CPU2​是同一个处理器的两个核心，同样

C

P

U

3

CPU_3

CPU3​和

C

P

U

4

CPU_4

CPU4​是另一个处理的两个核心。

按照内存访问局部性以及成本/效率权衡而普适的 分层存储原则 ，一般的缓存是如下组织的：

• 同一个处理器的每一个核心独享非常小但很高效的一级缓存。
• 同一个处理器的所有核心共享一个稍微大一点但慢一点点的二级缓存。
• 同一个封装的多个处理器的所有核心共享一个再大一点再慢一点点的三级缓存。
• …

由于以上复杂但清晰的高速缓存组织，考虑到命中高速缓存的巨大收益，多核系统的进程，特别是线程调度就不得不尽量满足以下的约束：

• 尽量减少高速缓存的失效刷新。
• 尽量让进程/线程利用之前的高速缓存。

于是，调度策略就比较明确了：

• 同一个进程的多个线程尽量调度在同一个处理器，同一个封装。
• 尽量减少进程/线程的迁移，特别是不要迁移单独的一个线程到远方。
• …(削峰填谷)

以上的策略要是真较真起来，可以写一本书，但是我这里恰恰要说的是，过于仅仅关注上述的策略，那便是舍本逐末，反客为主了。

描述结论，上述的 最大化高速缓存利用率 只是自上而下的 用户视角 下的最佳调度策略，还有一个自下而上的 系统视角 ，这个视角下认为的最佳调度策略乃是 最大化CPU利用率，即吞吐率最优 。换句话说，无论是要最大化缓存利用率，还是最大化吞吐，都只是问题，而非调度本身，所以它们都是要解决的，但解决方案并非就是调度策略或者说调度算法，调度是一个总体上的方案，而不是为了解决某个特定的问题。

我想Linux内核也许就是过于关注最大化高速缓存利用率了，所以才忽略了负载均衡算法中除了和高速缓存相关的策略之外的所有一切。才有了下面的这篇文章：
http://www.ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf

最后推荐一本神书，看完了收获很大：
《电信运作教程：IT从业者案头必备技术宝典(原书第二版)》
douban链接是：
https://book.douban.com/subject/1828105/
没啥评价，应该现在也买不到了。看了目录，你可能会说，这些早就已经过时了…确实，早就过时了，这本书出版时，2.5G/3G都还是未来，更别说跟现在比了。我是在2007年底读此书的，当时刚毕业没多久，一腔热血投入到了VoIP，NGN软交换中，直到现在，没事还会扫两眼Asterisk的动态…

这么多年了，昨天收拾书，找到了这本，夜深的时候又过了一遍，恍若昨日！然而，过了十几年了，这本书中提到的一些底层设施，底层技术，以及组织这些基础设施的方法，运营商的策略，万变不离其宗。强烈推荐！

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