在摩尔定律失效的情况下，CPU开始通过多核来提高性能，但这带来了一系列的问题，本系列的文章将介绍这些问题、在X86下目前的解决方案、以及我们应该如何更好的使用CPU。

一、CPU访问内存的流程

三级Cache Hierarchy

L1i Cache: Level1 Instruction Cache，CPU指令缓存；
L1d CacheL Level1 Data Cache，数据缓存；
L1i 与 L1d共用一个L2 Cache；
L3 Cache被所有的cores共享，并通过总线与内存进行数据交互。

如果使用了超线程(HA)技术，那么一个物理Core上可以有两个逻辑线程(HThread)，这两个逻辑线程共用所处物理核的资源-L1、L2Cache、ALU、FPU：

而在操作系统视角看来，这两个逻辑线程即为两个Core(Processor)

因此多核CPU的Cache Hierarchy可以概括为：

缓存加载流程

那么Cache是如何被填充的呢？是否L1 Cache中存在的数据，L2需要再存储一份？
设计多级cache可以有很多种方式，可以根据一个Cache的内容是否同时存在于其他级Cache来分类，即Cache inclusion policy(多级Cache的包含策略)。

Inclusive Multilevel Cache：如果较低级别cache中的所有cacheline也存在于较高级别cache中，则称较高级别cache包含（inclusive）较低级别cache；这是最常见的多级Cache的形式。
如果较高级别的cache仅包含较低级别的cache中不存在的cacheline，则称较高级别的cache不包含（exclusive ）较低级别的cache。

PS：CPU Cache加载的基本单位是CacheLine，i7为64bytes。

对于Inclusive的形式，CPU读写Cache的流程为：

(a) 时刻为初始状态，L1、L2Cache中都没有CacheLine
CPU 读取变量X，Read Miss，CPU处于Memory Install状态，因为是Inclusive的形式，因此CacheLine从主存需要同时被linefill到L1和L2中，如(b)所示；
接着CPU读取变量Y，同样Read Miss，CPU处于Memory Install状态，Y被同时加载到L1、L2，状态如(c)所示；
接着CPU将X Evict(驱逐)出L1、此时只需要将L1中的X移除即可，L2的仍然可以保留，因此L2 inclusion L1，状态如(d)所示；
接着CPU将Y Evict(驱逐)出L2，此时先将L2中的Y移除，接着需要向L1发送invalidation，最后将L1中Y移除，因为不能出现L1有Y而L2没有的情况，状态如(e)所示。

对于Exclusive的形式，CPU读写Cache的流程为：

(a) 时刻为初始状态，L1、L2Cache中都没有CacheLine
CPU 读取变量X，Read Miss，CPU处于Memory Install状态，因为是Inclusive的形式，因此CacheLine从主存只需要被linefill到L1中，如(b)所示；
接着CPU读取变量Y，同样Read Miss，CPU处于Memory Install状态，Y只需要加载到L1，状态如(c)所示；
接着CPU将X Evict(驱逐)出L1、此时只需要将L1中的X移除到L2中即可(这是 L2 linefill的唯一方式。)，状态如(d)所示；
最后考虑如果此时再读取X，此时L1 Miss，那么需要将L2的CacheLine移动到L2中去。

对比

上面只考虑了CPU本身的读写，没有考虑L3、CPU之间相互的内存访问的；

对于exclusive的场景，如果CPU1访问L3没有获取到某个CacheLine，因为L3中没有的，其他CPU的L1、L2中可能存在，那么CPU1需要尝试访问其他CPU进行CacheLine获取，而对于inclusive的场景，CPU只需要依次访问自身的L1、L2与共享的L3，L3中没有的CacheLine，其他CPU的L1、L2则无需继续访问。

所以Inclusive的优缺点为：

优点：CPU访问数据的效率高，对于硬件的要求不高(CPU之间不需要额外的通信链路)
缺点：浪费珍惜的Cache空间，特别是在L1、L2、L3大小相差不大的情况下。

相反，exclusive的优缺点与Inclusive相反，CPU访问效率低，但是节约Cache空间。

Cache Coherence (缓存一致性)

因为L1、L2是物理核私有的，而在一个物理核上修改的内存数据往往会先写到Write Buffer中，所以其他核不能直接感知到内存数据的更新，所以需要实现一套多核缓存一致的协议——MESI，并衍生出内存读写屏障，X|Y(Load|Store)的排列组合，这里因为篇幅关系，不展开叙述，可以参考synchronized与volatile是如何保证原子、可见、有序的？（博客重写计划Ⅰ） – 掘金 (juejin.cn)这篇文章。

CPU访问流程

CPU都是通过虚拟内存地址进行内存访问，而内存只有物理地址的概念，因此需要通过MMU进行虚拟地址->物理地址的翻译，翻译依据操作系统在内存中为每个进程存储的页表(PageTable)，页表存储着映射关系，映射的粒度为Page，而如下图所示，访问内存对于CPU而言是很浪费cycle的

CPU需要处于Memory Stall状态等待内存数据加载到Cache再到寄存器中，所以操作系统对页表进行了内存缓存-即TLB；

因此MMU会首先访问TLB，TLB Miss后依据当前进程号去内存中依据虚拟地址查询对应的PageTable，然后再将对应的映射关系回写到TLB中。
拿到虚拟地址对应的物理地址后，CPU会依据物理地址找到对应的CacheLine(Cache Hit)，如果Cache中没有，则CPU还是需要处于Memory Stall状态等待数据页从内存中加载到Cache中再进行查询，同样也会浪费很多时钟Cycle，因此如果Cache命中率高，CPU处在Memory Stall的状态短，那么每个时钟周期中，CPU能够执行的指令便越多，CPU的利用率就越好。

操作系统如何为进程(线程)分配CPU资源

线程为存储着执行状态的指令序列，操作系统对于多个处于可运行状态的线程会依据调度算法进行CPU资源的分配。

Linux经历了O(n)->O(1)->CFS的调度器演进过程，这里主要介绍一下目前Linux在使用的CFS调度器；

CFS（完全公平调度器）是Linux内核2.6.23版本开始采用的进程调度器，它的主要设计目标是在一个调度周期（sched_latency_ns）中保证每个就绪进程(线程)至少有机会运行一次，换一种说法就是每个进程等待CPU的时间最长不超过这个调度周期；

它的基本原理是这样的：每个进程的累计运行时间保存在自己的vruntime字段里，哪个进程的vruntime最小就获得本轮运行的权利，由于进程的优先级即nice值不同，nice值越小(weight越大)，优先级越高，vruntime增长的越慢，因此最小的概率越大，总体得到时间片便越多；进程k的weight在一轮sched_latency_ns中获取到的时间片总长度计算公式如下：