本文由Scarb发表于金甲虫的博客,转载请注明出处

JMM

存储器的层次结构

L3 及以下为CPU共享,L2及以上为CPU内部

硬件层数据一致性:MESI协议^MESI

MESI(Modified Exclusive Shared Or Invalid)(也称为伊利诺斯协议,是因为该协议由伊利诺斯州立大学提出)是一种广泛使用的支持写回策略的缓存一致性协议。

MESI协议中的状态

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修改了该缓存行)。

MESI状态转换图

状态之间的相互转换关系也可以使用下表进行表示。

M E S I
M X X X
E X X X
S X X
I


操作

在一个典型系统中,可能会有几个缓存(在多核系统中,每个核心都会有自己的缓存)共享主存总线,每个相应的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状态的缓存不需要使用总线事务。

缓存行cache line

读取缓存以cache line为基本单位

多数实现为64Bytes

伪共享:位于同一缓存行的两个不同数据,被两个不同CPU锁定,产生互相影响的问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
private static class Padding {
public volatile long p1, p2, p3, p4, p5, p6, p7; // 缓存行对齐
}

private static class T extends Padding {
public volatile long x = 0L;
}

public static T[] arr = new T[2];

static {
arr[0] = new T();
arr[1] = new T();
}

public static void main(String[] args) throws Exception {
Thread t1 = new Thread(()->{
for (long i = 0; i < 1000_0000L; i++) {
arr[0].x = i;
}
});

Thread t2 = new Thread(()->{
for (long i = 0; i < 1000_0000L; i++) {
arr[1].x = i;
}
});

final long start = System.nanoTime();
t1.start();
t2.start();
t1.join();
t2.join();
System.out.println((System.nanoTime() - start)/100_0000);
}

执行顺序:乱序执行

CPU为了提高指令执行效率,会在一条指令执行过程中,同时执行另一条指令(如去内存读数据,内存速度比CPU慢100倍),前提是两条指令没有依赖关系。

  • 合并写:写操作也可以进行合并
    • CPU有高速缓存WCBuffer,只有4 byte,每次以4 byte的单位写入和读取。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public final class WriteCombining {
private static final int ITERATIONS = Integer.MAX_VALUE;
private static final int ITEMS = 1 << 24;
private static final int MASK = ITEMS - 1;

private static final byte[] arrayA = new byte[ITEMS];
private static final byte[] arrayB = new byte[ITEMS];
private static final byte[] arrayC = new byte[ITEMS];
private static final byte[] arrayD = new byte[ITEMS];
private static final byte[] arrayE = new byte[ITEMS];
private static final byte[] arrayF = new byte[ITEMS];

public static void main(final String[] args) {
for (int i = 1; i <= 3; i++) {
System.out.println(i + " SingleLoop duration (ns) = " + runCaseOne());
System.out.println(i + " SplitLoop duration (ns) = " + runCaseTwo());
}
}

public static long runCaseOne() {
long start = System.nanoTime();
int i = ITERATIONS;

while (--i != 0) {
int slot = i & MASK;
byte b = (byte) i;
arrayA[slot] = b;
arrayB[slot] = b;
arrayC[slot] = b;
arrayD[slot] = b;
arrayE[slot] = b;
arrayF[slot] = b;
}
return System.nanoTime() - start;
}

public static long runCaseTwo() {
long start = System.nanoTime();
int i = ITERATIONS;
while (--i != 0) {
int slot = i & MASK;
byte b = (byte) i;
arrayA[slot] = b;
arrayB[slot] = b;
arrayC[slot] = b;
}
i = ITERATIONS;
while (--i != 0) {
int slot = i & MASK;
byte b = (byte) i;
arrayD[slot] = b;
arrayE[slot] = b;
arrayF[slot] = b;
}
return System.nanoTime() - start;
}
}
1
2
3
4
5
6
1 SingleLoop duration (ns) = 5103254700
1 SplitLoop duration (ns) = 4202560900
2 SingleLoop duration (ns) = 5056313000
2 SplitLoop duration (ns) = 4192870200
3 SingleLoop duration (ns) = 5049474100
3 SplitLoop duration (ns) = 4335775100

有序性保障

CPU内存屏障

Intel CPU

  • sfence:save fence,在sfence指令前的操作当必须在sfence指令后的操作前完成
  • lfence:load fence,在lfence指令前的操作当必须在lfence指令后的操作前完成
  • mfence:在mfence指令前的读写操作当必须在mfence指令后的读写操作前完成
  • 原子指令,如x86上的“lock …”指令是一个Full Barrier,执行时会锁住内存子系统来确保执行顺序,甚至跨多个CPU。Software Locks通常使用了内存屏障或原子指令来实现变量可见性和保持程序顺序

JVM级别规范(JSR133)

XX屏障:屏障两边的操作顺序

  • LoadLoad屏障
  • StoreStore屏障
  • LoadStore屏障
  • StoreLoad屏障