08_并发底层

对象头

指令i = 1

定位变量

写缓冲器

7 修改数据a=4，flag=M

线程1

2

写缓冲器高速缓存无效队列

CPU 3

k2

4

e=k2

BUS总线

tag

硬件组件

k1

4、回复ACK

发消息

内存地址解码

1

monitorexit指令

找到cache entry

e = k2

Load屏障

cache-line

cache entry

(k1->) k2

查询数据的时候，会先从写缓冲器里查，因为有可能刚修改的值在这里，然后才会从高速缓存里查，这个就是存储转发

实例变量

entryList等待锁列表

HashMap陷入死循环的原由

高速缓存

bucket

a=3

代码块

N

直接把消息放入无效队列，就返回ack给那个写处理器，之后从无效队列里取出来消息，过期本地缓存即可

e.next

M

禁止读操作和读写操作之间发生指令重排序LoadLoad屏障 + LoadStore屏障

3

执行refresh处理器缓存的操作，把别的处理器修改过的最新值加载到自己高速缓存里来

E

Mark Word（包含hashCode、锁数据、GC数据，等等）

高速缓存（拉链散列表）

next = k2

硬件MESI协议原理（3）优化性能后的更新

CPU 0

ObjectMonitor（C++）

硬件MESI协议原理（1）缓存未命中

指令a = i + 1

S

tag指向了这个缓存数据在主内存中的数据的地址flag标识了缓存行的状态cache line中包含多个变量的值

指令重排序

4 发消息

嗅探

异步更新

k4

k3

flag

synchronized底层（内存屏障保证了可见性&有序性）

2、嗅探到invalidate消息

CAS就是讲flag改为E

3 让处理器发送read消息到总线

定位

wait操作

2、加入无效队列

I

如果定位到一个高速缓存中的数据且flag标志着有效，则缓存命中

CPU 1

5

Mark Word

也有可能是把数据此时强制写回到主内存中，具体看底层硬件实现

next

MyObject类信息

null -> k1

1、写入a=4

处理器

主内存

monitor

3、标记a的flag=I

.java

newTable[i] = k1

Class Metadata Address（包含了指向类的元数据的指针）

lock对象

6 返回数据

其他处理器此时这条数据的状态都是I了，那如果要读的话，全部都需要重新发送read消息，从主内存（或者是其他处理器）来加载，这个具体怎么实现要看底层的硬件了，都有可能的（参考原理1）

3、收到所有cpu的ack

synchronized(this)

Y

无效队列

_count锁计数器

1、发送invalidate消息

acquire屏障

JIT动态编译为了加速程序的执行速度，可能会将IO等耗时操作放到load操作后面

e=k1

内存重排序

可见性问题：Store屏障 + Load屏障如果加了Store屏障之后，就会强制性要求你对一个写操作必须阻塞等待到其他的处理器返回invalidate ack之后，对数据加锁，然后修改数据到高速缓存中，必须在写数据之后，强制执行flush操作他的效果，要求一个写操作必须刷到高速缓存（或者主内存），不能停留在写缓冲里如果加了Load屏障之后，在从高速缓存中读取数据的时候，如果发现无效队列里有一个invalidate消息，此时会立马强制根据那个invalidate消息把自己本地高速缓存的数据，设置为I（过期），然后就可以强制从其他处理器的高速缓存中加载最新的值了这就是refresh操作

MESI协议中划分为：（1）invalid：无效的，标记为I，当前cache entry无效，里面的数据不能使用（2）shared：共享的，标记为S，当前cache entry有效，里面的数据在各个处理器中都有各自的副本，但是这些副本的值跟主内存的值是一样的，各个处理器就是并发的在读而已（3）exclusive：独占的，标记为E，当前处理器对这个数据独占了，只有他可以有这个副本，其他的处理器都不能包含这个副本（4）modified：修改过的，标记为M，只能有一个处理器对共享数据更新，所以只有更新数据的处理器的cache entry，才是exclusive状态，表明当前线程更新了这个数据，这个副本的数据跟主内存是不一样的

线程2

.class

index

7 存入高速缓存

4种重排（LoadLoad、StoreStore、LoadStore、StoreLoad）

执行flush处理器缓存的操作，把当前处理器更新的变量值，都刷新到高速缓存（或者主内存）里去

指令重排几个节点

e

javac编译

CAS加锁

处理器写数据的时候直接写入缓冲器，不需要同步阻塞等待其他处理器的invalidate ack返回

next = k3

class metadataaddress

动态编译优化重排

k2.next = k1

2 查找缓存

6、修改flag=E

JIT

store屏障

异步过期

原数据结构

waitSet线程等待列表

newTable[i] = k2

加锁成功

是否命中

e = k3

k2.next = null

3、同步返回ACK

offset

禁止写操作和读写操作之间发生重排序StoreLoad屏障 + StoreStore屏障

正如上图所示，硬件优化后虽然提升的性能，但同时也成为引发可见性和有序性根本原因1、可见性：执行i=1 store操作时，直接进入写缓冲器，并没有修改高速缓存，所以在执行 a = i+1 时，无法获取到 i 的值。

CPU 2

1处理指令

在独占期间，别的处理器就不能修改数据了，因为别的处理器此时发出invalidate消息，这个处理器0是不会返回invalidate ack消息的，除非他先修改完再说

硬件MESI协议原理（4）优化性能后导致的表面上的可见性和有序性问题

synchronized底层（保证原子性）

5

首先我们要明白，多线程扩容hashmap，操作的table是共享变量.在此前提下，我们对table进行多线程扩容，很可能造成死循环。进一步说，是当多线程在扩容时，通过“头插法”对链表结构进行rehash，线程1将Node倒排，线程2依然读取的是原数据结构的正排序，倒排的情况下是k2.next 指向k1 ，而正排序的k1.next 指向k2 。 最终导致形成“环形队列”，我们在get(k5)的时候，hashmap会遍历链表，当遍历到环形队列时，会进入死循环 k2.next-->k1  k1.next-->k2并且多线程扩容时，还会造成数据丢失，因为如果采用线程2扩容后的table，那么k3就会丢失了。

5、收到所有cpu的ack

monitorenter指令

_owner指针持有锁线程

int a = 0;int c = 1;线程1：a = 1;int b = c;2、有序性问题：可能先执行了b = c的load操作，然后再执行a = 1的store操作，因为store先入了写缓冲器

synchronized原子性：通过objectMonitor，加锁释放锁保证原子性可见性：通过load屏障和store屏障，加锁refresh数据，释放锁flush数据。有序性：通过acquie和release屏障，保证代码块内部和外部的指令不能重排。

flag是I？

release屏障

指令乱序机制：再次优化指令执行顺序推测执行：可能提前执行if中的指令，之后再if判断

硬件MESI协议原理（2）更新flag=S数据