高并发（一）

高速缓存和主存的关系  二级缓存会比一级缓存更大 但是会更慢

我们为什么需要缓存？

因为CPU的处理速度太快 快到内存跟不上 这样在处理的周期内 常常我们的CPU需要等待主存 耗费时间 所以缓存出现了 缓存是为了缓解CPU和内存之间的速度不匹配的问题

他的结构是cpu->cache->memory

CPU缓存到底有什么意义？

因为缓存不可能会包含主存所有的数据，那我们的缓存有什么意义呢

1)时间局部性：如果某个数据被访问，那么再不久的将来它很有可能被再次访问

2)空间局部性：如果某个数据被访问，那么他的相邻的数据也可能被访问

cpu多级缓存-缓存一致性(MESI)

用于保证多个CPUI cache之间缓存共享数据的一直性

当程序在运行过程中，会将运算需要的数据从主存复制一份到CPU的高速缓存当中，那么CPU进行计算时就可以直接从它的高速缓存读取数据和向其中写入数据，当运算结束之后，再将高速缓存中的数据刷新到主存当中

个简单的例子，比如下面的这段代码：

i = i+1;

当线程执行这个语句时，会先从主存当中读取i的值，然后复制一份到高速缓存当中，然后CPU执行指令对i进行加1操作，然后将数据写入高速缓存，最后将高速缓存中i最新的值刷新到主存当中

这个代码在单线程中运行是没有任何问题的，但是在多线程中运行就会有问题了。在多核CPU中，每条线程可能运行于不同的CPU中，因此每个线程运行时有自己的高速缓存（对单核CPU来说，其实也会出现这种问题，只不过是以线程调度的形式来分别执行的）。本文我们以多核CPU为例

比如同时有2个线程执行这段代码，假如初始时i的值为0，那么我们希望两个线程执行完之后i的值变为2 但是事实会是这样吗？

　　可能存在下面一种情况：初始时，两个线程分别读取i的值存入各自所在的CPU的高速缓存当中，然后线程1进行加1操作，然后把i的最新值1写入到内存(主存)。此时线程2的高速缓存当中i的值还是0，进行加1操作之后，i的值为1，然后线程2把i的值写入内存(主存)

　　最终结果i的值是1，而不是2。这就是著名的缓存一致性问题。通常称这种被多个线程访问的变量为共享变量

　　 也就是说，如果一个变量在多个CPU中都存在缓存（一般在多线程编程时才会出现），那么就可能存在缓存不一致的问题

CPU中每个缓存行（caceh line)使用4种状态进行标记（使用额外的两位(bit)表示):

M: 被修改（Modified)

该缓存行只被缓存在该CPU的缓存中，并且是被修改过的（dirty),即与主存中的数据不一致，该缓存行中的内存需要在未来的某个时间点（允许其它CPU读取请主存中相应内存之前）写回（write back）主存。

当被写回主存之后，该缓存行的状态会变成独享（exclusive)状态。

E: 独享的（Exclusive)

该缓存行只被缓存在该CPU的缓存中，它是未被修改过的（clean)，与主存中数据一致。该状态可以在任何时刻当有其它CPU读取该内存时变成共享状态（shared)。

同样地，当CPU修改该缓存行中内容时，该状态可以变成Modified状态。

S: 共享的（Shared)

该状态意味着该缓存行可能被多个CPU缓存，并且各个缓存中的数据与主存数据一致（clean)，当有一个CPU修改该缓存行中，

其它CPU中该缓存行可以被作废（变成无效状态（Invalid））。

I: 无效的（Invalid）

该缓存是无效的（可能有其它CPU修改了该缓存行）。

local read 读取本地缓存的数据

local write 将数据写到本地的缓存中

remote read 去读内存中的数据

remote write 将数据写回到主存中

四种状态和四种操作 对应出16种关系

操作：

在一个典型系统中，可能会有几个缓存（在多核系统中，每个核心都会有自己的缓存）共享主存总线，每个相应的CPU会发出读写请求，而缓存的目的是为了减少CPU读写共享

主存的次数

一个缓存除在Invalid状态外都可以满足cpu的读请求，一个invalid的缓存行必须从主存中读取（变成S或者 E状态）来满足该CPU的读请求

一个写请求只有在该缓存行是M或者E状态时才能被执行，如果缓存行处于S状态，必须先将其它缓存中该缓存行变成Invalid状态（也既是不允许不同CPU同时修改同一缓存行，

即使修改该缓存行中不同位置的数据也不允许）。该操作经常作用广播的方式来完成，例如：RequestFor Ownership (RFO)

缓存可以随时将一个非M状态的缓存行作废，或者变成Invalid状态，而一个M状态的缓存行必须先被写回主存

一个处于M状态的缓存行必须时刻监听所有试图读该缓存行相对就主存的操作，这种操作必须在缓存将该缓存行写回主存并将状态变成S状态之前被延迟执行。

一个处于S状态的缓存行也必须监听其它缓存使该缓存行无效或者独享该缓存行的请求，并将该缓存行变成无效（Invalid）

一个处于E状态的缓存行也必须监听其它缓存读主存中该缓存行的操作，一旦有这种操作，该缓存行需要变成S状态

对于M和E状态而言总是精确的，他们在和该缓存行的真正状态是一致的。而S状态可能是非一致的，如果一个缓存将处于S状态的缓存行作废了，而另一个缓存实际上可能已经

独享了该缓存行，但是该缓存却不会将该缓存行升迁为E状态，这是因为其它缓存不会广播他们作废掉该缓存行的通知，同样由于缓存并没有保存该缓存行的copy的数量，

因此（即使有这种通知）也没有办法确定自己是否已经独享了该缓存行

从上面的意义看来E状态是一种投机性的优化：如果一个CPU想修改一个处于S状态的缓存行，总线事务需要将所有该缓存行的copy变成invalid状态，而修改E状态的缓存不需要

使用总线事务

CPU多级缓存-乱序执行优化

处理器为提高运算速度而做出违背代码原有顺序的优化

例如：计算a*b的值 a = 10; b = 200; result = a*b

单核时候，在CPU乱序执行优化的时候可能变成 b = 200; a = 10; result = a*b

单核处理器时代处理器能够保证处理器做出的优化不会影响结果，但是多核时代就会造成乱序，使最终结果错误