一.应用场景展示——多线程计数
1.全局原子操作计数的数据流图
核心问题就是不同CPU如何在同一时刻看到同样的全局变量值。
2.每线程自增计数的数据流图
二.cache原理和实现
1. cache geometry
size : 包含的cache line个数
way :每set相连way数
2. cache核心是一个硬件hash表
举例说明一下:
该cache是一个2路(2 ways)16组(16 sets)相连,大小为16 * 2 = 32 cache line的cache。
对应的硬件hash表如下:
三.数据同步电信号是什么?
MESI —— 内存缓存一致性性协议
注意,MESI协议只能保证并发编程中的可见性,并未解决原子性和有序性的问题,所以只靠MESI协议是无法完全解决多线程中的所有问题。
1. cache line的四种状态
M : "modified"E : "exclusive"S : "shared"I : "invalid"
MESI 存在“modified”,“exclusive”,“shared”和“invalid”四种状态,协议可以在一个指定的缓存行中应用这四种状态。因此,协议在每一个缓存行中维护一个两位的状态标记,这个标记附着在缓存行的物理地址和数据后面。
(1)modify状态
(2)exclusive状态
(3)shared状态
(4)invalid状态
2. MESI的消息类型
MESI的六种消息大致分为两类:请求消息和响应消息
cpu接收响应消息的顺序决定了->其他cpu感知到的当前线程的执行顺序
(1)read:(请求消息)
cpu发送read消息请求需要读取数据的物理地址。
(2)read response:(响应消息)
"read response"消息包含先前“read”消息请求的数据。此“read response”消息可能由内存或其他缓存之一提供。
(3)invalidate:(请求消息)
“invalidate”消息包含要作废的缓存行的物理地址。所有其他缓存都必须从其缓存中删除相应的数据并进行响应。
(4)invalidate acknowledge:(响应消息)
接收到“invalidate”消息的CPU必须在从其缓存中删除指定的数据后以“invalidate acknowledge”消息响应。
(5)read invalidate:(请求消息)
“read invalidate”消息包含要读取的缓存行的物理地址,同时指示其他缓存删除数据。“read invalidate”消息需要“read response”和一组“invalidate acknowledge”消息作为应答。
(6)writeback
“writeback”消息包含要写回内存的地址和数据(也可能是沿途“窥探”到其他cpu的缓存中)。此消息允许缓存根据需要弹出处于“修改”状态的行,以便为其他数据腾出空间。
3. cache line在四种状态之间的转换
(1) M和E状态转换
Transition (a):缓存行被写回到物理内存,但是CPU仍然将它保留在缓存中,并在以后修改它。这个转换需要一个“写回”消息。Transition (b):CPU将数据写到缓存行,该缓存行目前处于排它访问。不需要发送或者接收任何消息。(2) M和I状态转换
Transition (c):CPU收到一个“读使无效”消息,相应的缓存行已经被修改。CPU必须使无效本地副本,然后响应“读响应”和 “使无效应答”消息,同时发送数据给请求的CPU(注意,这个数据是M状态的cache数据),并标示它的本地副本不再有效(本地副本已经通过读响应发送给请求的CPU了)。Transition (d):CPU进行一个原子读—修改—写操作,相应的数据没有在它的缓存中。它发送一个“读使无效”消息,通过“读响应”消息接收数据。一旦它接收到一个完整的“使无效应答”响应集合,CPU就完成此转换。(3) M和S状态转换
Transition (e):CPU进行一个原子读—修改—写操作,相应的数据在缓存中是只读的。它必须发送一个“使无效”消息,并等待“使无效应答”响应集合以完成此转换。Transition (f):其他某些CPU读取缓存行,其数据由本CPU提供,本CPU包含一个只读副本。数据只读的原因,可能是由于数据已经回写到内存中。这个转换开始于接收到一个“读”消息,最终本CPU响应了一个“读响应” 消息。(4) E和S状态转换
Transition (g):其他CPU读取数据,并且数据是从本CPU的缓存或者物理内存中提供的。无论哪种情况,本CPU都会保留一个只读副本。这个事务开始于接收到一个“读”消息,最终本CPU响应一个“读响应”消息。Transition (h):当前CPU很快将要写入一些数据到缓存行,于是发送一个“使无效”消息。直到它接收到所有“使无效应答”消息后,CPU才完成转换。可选的,所有其他CPU通过“写回”消息将缓存行的数据换出(可能是为其他缓存行腾出空间)。这样,当前CPU就是最后一个缓存该数据的CPU。(5) E和I状态转换
Transition (i):其他某些CPU进行了一个原子读—修改—写操作,相应的缓存行仅仅被本CPU持有。本CPU将缓存行变成无效状态。这个转换开始于接收到“读使无效”消息,最终本CPU响应一个“读响应”消息以及一个“使无效应答”消息。Transition (j):本CPU保存一个数据到缓存行,但是数据还没有在它的缓存行中。因此发送一个“读使无效”消息。直到它接收到“读响应”消息以及所有“使无效应答”消息后,才完成事务。缓存行可能会很快转换到“修改”状态,这是在存储完成后由Transition (b)完成的。(6) S和I状态转换
Transition (k):本CPU装载一个数据,但是数据还没有在缓存行中。CPU发送一个“读”消息,当它接收到相应的“读响应”消息后完成转换。Transition (l):其他CPU存储一个数据到缓存行,但是该缓存行处于只读状态(因为其他CPU也持有该缓存行)。这个转换开始于接收到一个“使无效”消息,当前CPU最终响应一个“使无效应答”消息。4. 一个简单示例
(1).MESI协议只对汇编指令中执行加锁操作的变量有效,表现到C/C++中为使用voliate关键字定义变量或使用加锁操作
(2).对于汇编指令中执行加锁操作的变量,MESI协议在以下两种情况中也会失效:
a、CPU不支持缓存一致性协议。
b、该变量超过一个缓存行的大小,缓存一致性协议是针对单个缓存行进行加锁,此时,缓存一致性协议无法再对该变量进行加锁,只能改用总线加锁的方式。
MESI工作原理实例展示:
(1)、CPU1从内存中将变量a加载到缓存中,并将变量a的状态改为E(独享),并通过总线嗅探机制对内存中变量a的操作进行嗅探
(2)、此时,CPU2读取变量a,总线嗅探机制会将CPU1中的变量a的状态置为S(共享),并将变量a加载到CPU2的缓存中,状态为S
(3)、CPU1对变量a进行修改操作,此时CPU1中的变量a会被置为M(修改)状态,而CPU2中的变量a会被通知,改为I(无效)状态,此时CPU2中的变量a做的任何修改都不会被写回内存中(高并发情况下可能出现两个CPU同时修改变量a,并同时向总线发出将各自的缓存行更改为M状态的情况,此时总线会采用相应的裁决机制进行裁决,将其中一个置为M状态,另一个置为I状态,且I状态的缓存行修改无效)
(4)、CPU1将修改后的数据写回内存,并将变量a置为E(独占)状态
(5)、此时,CPU2通过总线嗅探机制得知变量a已被修改,会重新去内存中加载变量a,同时CPU1和CPU2中的变量a都改为S状态
在上述过程第3步中,CPU2的变量a被置为I(无效)状态后,只是保证变量a的修改不会被写回内存,但CPU2有可能会在CPU1将变量a置为E(独占)状态之前重新读取内存中的变量a,这个取决于汇编指令是否要求CPU2重新加载内存。