H5W3
当前位置:H5W3 > java > 正文

【Java】一段代码,两倍时差,直击并发编程伪共享

一段代码,两倍时差,直击并发编程伪共享

大道七哥发布于 今天 07:11

一、前言

【闲话开篇】:这段时间项目接近尾声,我终于闲了一点,又拿起了早先未看完的书《JAVA高并发程序设计》。看到其中介绍《无锁的缓存框架:Disruptor》时,接触到了一个概念——伪共享(false sharing),说是会影响并发程序的执行性能,被很多人描述成无声的性能杀手,突然感觉到了自己知识的匮乏,罪过啊。
原文解析

伪共享(false sharing),究竟是怎样一回事呢?不急,我们先倒杯水边喝边回顾,以前上学时丢下的计算机组成原理相关知识点。伪共享

二、概念解析

CPU 缓存(三级)

CPU 缓存(Cache Memory)是位于CPU与内存之间的临时存储器,它的容量比内存小很多,但是交换速度却比内存要快得多。CPU和主内存之间有好几级缓存,CPU缓存可以分为一级缓存,二级缓存,部分高端CPU还具有三级缓存。每一级缓存中所储存的全部数据都是下一级缓存的一部分,越靠近 CPU 的缓存越快也越小。

高速缓存的出现主要是为了解决CPU运算速度与内存读写速度不匹配的矛盾,因为CPU运算速度要比内存读写速度快很多,这样会使 CPU 花费很长时间等待数据到来或把数据写入内存。在缓存中的数据是内存中的一小部分,但这一小部分是短时间内CPU即将访问的,当CPU调用大量数据时,就可避开内存直接从缓存中调用,从而加快读取速度。

如果我们的程序正在多次对同一数据块做相同的运算,那么在执行运算的时候把它加载到离 CPU 很近的缓存中就能大大的提高程序运行速度。

我们以L1、L2、L3分别表示一级缓存、二级缓存、三级缓存,按照数据读取顺序和与CPU结合的紧密程度,速度是L1 >L2 > L3 >主存,容量是L1< L2< L3< 主存。

L1 缓存很小但是很快,并且紧靠着在使用它的 CPU 内核,L2 大一些,也慢一些,并且仍然只能被一个单独的 CPU 核使用,L3 更大,更慢,并且被单个插槽上的所有 CPU 核共享,最后是主存,由全部插槽上的所有 CPU 核共享。拥有三级缓存的的 CPU,到三级缓存时能够达到95%的命中率,只有不到5%的数据需要从内存中查询。
三级缓存示意图:伪共享

缓存行

缓存行 (Cache Line) 是 CPU 缓存中的最小单位,CPU 缓存由若干缓存行组成,一个缓存行的大小通常是 64 字节(备注:取决于 CPU,本文基于64字节,其他长度的如32字节等本文不作讨论),并且它有效地引用主内存中的一块地址。一个 Java 的 long 类型是 8 字节,因此在一个缓存行中可以存 8 个 long 类型的变量。
所以,如果你访问一个 long 数组,当数组中的一个值被加载到缓存中,它会额外加载另外 7 个,以致你能非常快地遍历这个数组。事实上,你可以非常快速的遍历在连续的内存块中分配的任意数据结构。而如果你在数据结构中的项在内存中不是彼此相邻的(如链表),你将得不到缓存加载所带来的优势,并且在这些数据结构中的每一项都可能会出现缓存未命中的情况。

MESI 协议

MESI 协议是基于Invalidate的高速缓存一致性协议,并且是支持回写高速缓存的最常用协议之一。

缓存行状态

CPU 的缓存是以缓存行(cache line)为单位的,MESI协议描述了多核处理器中一个缓存行的状态。(现在主流的处理器都是用它来保证缓存的相干性和内存的相干性。)

在MESI协议中,每个缓存行有4个状态,分别是:
M(修改,Modified):本地处理器已经修改缓存行,即是脏行,它的内容与内存中的内容不一样,并且此 cache 只有本地一个拷贝(专有)
E(专有,Exclusive):缓存行内容和内存中的一样,而且其它处理器都没有这行数据
S(共享,Shared):缓存行内容和内存中的一样, 有可能其它处理器也存在此缓存行的拷贝
I(无效,Invalid):缓存行失效, 不能使用

状态转换

在 MESI 协议中,每个Cache的Cache控制器不仅知道自己的读写操作,而且也监听其它Cache的读写操作。每个Cache line所处的状态根据本核和其它核的读写操作在4个状态间进行迁移。MESI 协议状态迁移图如下:伪共享


初始:一开始时,缓存行没有加载任何数据,所以它处于 I 状态。
本地写(Local Write):如果本地处理器写数据至处于 I 状态的缓存行,则缓存行的状态变成 M。
本地读(Local Read):如果本地处理器读取处于I状态的缓存行,很明显此缓存没有数据给它。此时分两种情况:
(1)其它处理器的缓存里也没有此行数据,则从内存加载数据到此缓存行后,再将它设成 E 状态,表示只有我
一家有这条数据,其它处理器都没有
(2)其它处理器的缓存有此行数据,则将此缓存行的状态设为 S 状态。(备注:如果处于M状态的缓存行,再
由本地处理器写入/读出,状态是不会改变的)
远程读(Remote Read):假设我们有两个处理器 c1 和 c2,如果 c2 需要读另外一个处理器 c1 的缓存行内容,
c1 需要把它缓存行的内容通过内存控制器 (Memory Controller) 发送给 c2,c2 接到后将相应的缓存行状
态设为 S。在设置之前,内存也得从总线上得到这份数据并保存。
远程写(Remote Write):其实确切地说不是远程写,而是c2得到c1的数据后,不是为了读,而是为了写。也算是
本地写,只是 c1 也拥有这份数据的拷贝,这该怎么办呢?c2 将发出一个 RFO (Request For Owner) 请求,
它需要拥有这行数据的权限,其它处理器的相应缓存行设为I,除了它自已,谁不能动这行数据。这保证了数据
的安全,同时处理 RFO 请求以及设置I的过程将给写操作带来很大的性能消耗。

伪共享

了解了上述一些概念之后,咱们提出一个疑问?如果有多个线程操作不同的成员变量,但它们是相同的<font color=’red’>缓存行</font>,这个时候会发生什么?伪共享

没错,<font color=’red’>伪共享</font>(False Sharing)问题就发生了!咱们来看一张经典的CPU 缓存行示意图:伪共享

注释:一个运行在处理器 core1上的线程想要更新变量 X 的值,同时另外一个运行在处理器 core2 上的线程想要更新变量 Y 的值。
但是,这两个频繁改动的变量都处于同一条缓存行。两个线程就会轮番发送 RFO (Request For Owner) 消息,占得此缓存行的拥有
权。当 core1 取得了拥有权开始更新 X,则 core2 对应的缓存行需要设为 I 状态(失效态)。当 core2 取得了拥有权开始更新 Y,
则core1    对应的缓存行需要设为 I 状态(失效态)。轮番夺取拥有权不但带来大量的 RFO 消息,而且如果某个线程需要读此行数据时,
L1 和 L2 缓存上都是失效数据,只有L3缓存上是同步好的数据。从前面的内容我们知道,读L3的数据会影响性能,更坏的情况是跨槽
读取,L3 都出现缓存未命中,只能从主存上加载。

举例说明:

咱们以Java里面的ArrayBlockingQueue为例采用生产消费模型说明,ArrayBlockingQueue有三个成员变量:

    - takeIndex:需要被取走的元素下标
- putIndex:可被元素插入的位置的下标
- count:队列中元素的数量

这三个变量很容易放到一个缓存行中,但是修改并没有太多的关联。所以每次修改,都会使之前缓存的数据失效,从而不能完全达到共享的效果。伪共享

当生产者线程put一个元素到ArrayBlockingQueue时,putIndex会修改,从而导致消费者线程的缓存中的缓存行无效,需要向上重新读取,这种无法充分使用缓存行特性的现象,称为伪共享。

看到此处,我们可以自行总结,关于伪共享给出一个<font color=’red’>非标准的定义</font>:
CPU 缓存系统中是以缓存行为单位存储的,当多线程修改互相独立的变量时,如果这些变量共享同一个缓存行,就会无意中影响彼此的性能,这就是伪共享。

三、程序模拟

程序用四个线程修改一数组不同元素的内容,元素类型为 VolatileLong,包含一个长整型成员 value 和 6 个没用到的长整型成员,value 设为 volatile 是为了让 value 的修改对所有线程都可见。主要代码如下:

public class FalseShare implements Runnable {
public static int NUM_THREADS = 4;
public final static long ITERATIONS = 500L * 1000L * 1000L;
private final int arrayIndex;
private static VolatileLong[] longs;
public static long SUM_TIME = 0l;
public FalseShare(final int arrayIndex) {
this.arrayIndex = arrayIndex;
}
private static void exeTest() throws InterruptedException {
Thread[] threads = new Thread[NUM_THREADS];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(new FalseShare(i));
}
for (Thread t : threads) {
t.start();
}
for (Thread t : threads) {
t.join();
}
}
public void run() {
long i = ITERATIONS + 1;
while (0 != --i) {
longs[arrayIndex].value = i;
}
}
public final static class VolatileLong {
public volatile long value = 0L;
//        public long p1, p2, p3, p4, p5, p6;     //缓存行填充
}
public static void main(final String[] args) throws Exception {
for (int j = 0; j < 10; j++) {
System.out.println("第" + j + "次...");
longs = new VolatileLong[NUM_THREADS];
for (int i = 0; i < longs.length; i++) {
longs[i] = new VolatileLong();
}
long start = System.nanoTime();
exeTest();
long end = System.nanoTime();
SUM_TIME += end - start;
}
System.out.println("平均耗时:" + SUM_TIME / 10);
}
}

第一次执行:

//        public long p1, p2, p3, p4, p5, p6;     //缓存行填充

第二次执行:

          public long p1, p2, p3, p4, p5, p6;     //缓存行填充

程序每次运行,循环10次,取平均耗时,耗时结果如下:

第一次:
平均耗时:28305116160
第二次:
平均耗时:14071204270

四、伪共享避免

1.缓存行填充(让不同线程操作的对象处于不同的缓存行)

2.使用编译指示,来强制每一个变量对齐(略)

五、总结

伪共享

java并发编程
阅读 82发布于 今天 07:11
本作品系原创,采用《署名-非商业性使用-禁止演绎 4.0 国际》许可协议
avatar

大道七哥

一个用灵魂写代码的段子手

11 声望
0 粉丝

0 条评论
得票时间

avatar

大道七哥

一个用灵魂写代码的段子手

11 声望
0 粉丝

宣传栏

一、前言

【闲话开篇】:这段时间项目接近尾声,我终于闲了一点,又拿起了早先未看完的书《JAVA高并发程序设计》。看到其中介绍《无锁的缓存框架:Disruptor》时,接触到了一个概念——伪共享(false sharing),说是会影响并发程序的执行性能,被很多人描述成无声的性能杀手,突然感觉到了自己知识的匮乏,罪过啊。
原文解析

伪共享(false sharing),究竟是怎样一回事呢?不急,我们先倒杯水边喝边回顾,以前上学时丢下的计算机组成原理相关知识点。伪共享

二、概念解析

CPU 缓存(三级)

CPU 缓存(Cache Memory)是位于CPU与内存之间的临时存储器,它的容量比内存小很多,但是交换速度却比内存要快得多。CPU和主内存之间有好几级缓存,CPU缓存可以分为一级缓存,二级缓存,部分高端CPU还具有三级缓存。每一级缓存中所储存的全部数据都是下一级缓存的一部分,越靠近 CPU 的缓存越快也越小。

高速缓存的出现主要是为了解决CPU运算速度与内存读写速度不匹配的矛盾,因为CPU运算速度要比内存读写速度快很多,这样会使 CPU 花费很长时间等待数据到来或把数据写入内存。在缓存中的数据是内存中的一小部分,但这一小部分是短时间内CPU即将访问的,当CPU调用大量数据时,就可避开内存直接从缓存中调用,从而加快读取速度。

如果我们的程序正在多次对同一数据块做相同的运算,那么在执行运算的时候把它加载到离 CPU 很近的缓存中就能大大的提高程序运行速度。

我们以L1、L2、L3分别表示一级缓存、二级缓存、三级缓存,按照数据读取顺序和与CPU结合的紧密程度,速度是L1 >L2 > L3 >主存,容量是L1< L2< L3< 主存。

L1 缓存很小但是很快,并且紧靠着在使用它的 CPU 内核,L2 大一些,也慢一些,并且仍然只能被一个单独的 CPU 核使用,L3 更大,更慢,并且被单个插槽上的所有 CPU 核共享,最后是主存,由全部插槽上的所有 CPU 核共享。拥有三级缓存的的 CPU,到三级缓存时能够达到95%的命中率,只有不到5%的数据需要从内存中查询。
三级缓存示意图:伪共享

缓存行

缓存行 (Cache Line) 是 CPU 缓存中的最小单位,CPU 缓存由若干缓存行组成,一个缓存行的大小通常是 64 字节(备注:取决于 CPU,本文基于64字节,其他长度的如32字节等本文不作讨论),并且它有效地引用主内存中的一块地址。一个 Java 的 long 类型是 8 字节,因此在一个缓存行中可以存 8 个 long 类型的变量。
所以,如果你访问一个 long 数组,当数组中的一个值被加载到缓存中,它会额外加载另外 7 个,以致你能非常快地遍历这个数组。事实上,你可以非常快速的遍历在连续的内存块中分配的任意数据结构。而如果你在数据结构中的项在内存中不是彼此相邻的(如链表),你将得不到缓存加载所带来的优势,并且在这些数据结构中的每一项都可能会出现缓存未命中的情况。

MESI 协议

MESI 协议是基于Invalidate的高速缓存一致性协议,并且是支持回写高速缓存的最常用协议之一。

缓存行状态

CPU 的缓存是以缓存行(cache line)为单位的,MESI协议描述了多核处理器中一个缓存行的状态。(现在主流的处理器都是用它来保证缓存的相干性和内存的相干性。)

在MESI协议中,每个缓存行有4个状态,分别是:
M(修改,Modified):本地处理器已经修改缓存行,即是脏行,它的内容与内存中的内容不一样,并且此 cache 只有本地一个拷贝(专有)
E(专有,Exclusive):缓存行内容和内存中的一样,而且其它处理器都没有这行数据
S(共享,Shared):缓存行内容和内存中的一样, 有可能其它处理器也存在此缓存行的拷贝
I(无效,Invalid):缓存行失效, 不能使用

状态转换

在 MESI 协议中,每个Cache的Cache控制器不仅知道自己的读写操作,而且也监听其它Cache的读写操作。每个Cache line所处的状态根据本核和其它核的读写操作在4个状态间进行迁移。MESI 协议状态迁移图如下:伪共享


初始:一开始时,缓存行没有加载任何数据,所以它处于 I 状态。
本地写(Local Write):如果本地处理器写数据至处于 I 状态的缓存行,则缓存行的状态变成 M。
本地读(Local Read):如果本地处理器读取处于I状态的缓存行,很明显此缓存没有数据给它。此时分两种情况:
(1)其它处理器的缓存里也没有此行数据,则从内存加载数据到此缓存行后,再将它设成 E 状态,表示只有我
一家有这条数据,其它处理器都没有
(2)其它处理器的缓存有此行数据,则将此缓存行的状态设为 S 状态。(备注:如果处于M状态的缓存行,再
由本地处理器写入/读出,状态是不会改变的)
远程读(Remote Read):假设我们有两个处理器 c1 和 c2,如果 c2 需要读另外一个处理器 c1 的缓存行内容,
c1 需要把它缓存行的内容通过内存控制器 (Memory Controller) 发送给 c2,c2 接到后将相应的缓存行状
态设为 S。在设置之前,内存也得从总线上得到这份数据并保存。
远程写(Remote Write):其实确切地说不是远程写,而是c2得到c1的数据后,不是为了读,而是为了写。也算是
本地写,只是 c1 也拥有这份数据的拷贝,这该怎么办呢?c2 将发出一个 RFO (Request For Owner) 请求,
它需要拥有这行数据的权限,其它处理器的相应缓存行设为I,除了它自已,谁不能动这行数据。这保证了数据
的安全,同时处理 RFO 请求以及设置I的过程将给写操作带来很大的性能消耗。

伪共享

了解了上述一些概念之后,咱们提出一个疑问?如果有多个线程操作不同的成员变量,但它们是相同的<font color=’red’>缓存行</font>,这个时候会发生什么?伪共享

没错,<font color=’red’>伪共享</font>(False Sharing)问题就发生了!咱们来看一张经典的CPU 缓存行示意图:伪共享

注释:一个运行在处理器 core1上的线程想要更新变量 X 的值,同时另外一个运行在处理器 core2 上的线程想要更新变量 Y 的值。
但是,这两个频繁改动的变量都处于同一条缓存行。两个线程就会轮番发送 RFO (Request For Owner) 消息,占得此缓存行的拥有
权。当 core1 取得了拥有权开始更新 X,则 core2 对应的缓存行需要设为 I 状态(失效态)。当 core2 取得了拥有权开始更新 Y,
则core1    对应的缓存行需要设为 I 状态(失效态)。轮番夺取拥有权不但带来大量的 RFO 消息,而且如果某个线程需要读此行数据时,
L1 和 L2 缓存上都是失效数据,只有L3缓存上是同步好的数据。从前面的内容我们知道,读L3的数据会影响性能,更坏的情况是跨槽
读取,L3 都出现缓存未命中,只能从主存上加载。

举例说明:

咱们以Java里面的ArrayBlockingQueue为例采用生产消费模型说明,ArrayBlockingQueue有三个成员变量:

    - takeIndex:需要被取走的元素下标
- putIndex:可被元素插入的位置的下标
- count:队列中元素的数量

这三个变量很容易放到一个缓存行中,但是修改并没有太多的关联。所以每次修改,都会使之前缓存的数据失效,从而不能完全达到共享的效果。伪共享

当生产者线程put一个元素到ArrayBlockingQueue时,putIndex会修改,从而导致消费者线程的缓存中的缓存行无效,需要向上重新读取,这种无法充分使用缓存行特性的现象,称为伪共享。

看到此处,我们可以自行总结,关于伪共享给出一个<font color=’red’>非标准的定义</font>:
CPU 缓存系统中是以缓存行为单位存储的,当多线程修改互相独立的变量时,如果这些变量共享同一个缓存行,就会无意中影响彼此的性能,这就是伪共享。

三、程序模拟

程序用四个线程修改一数组不同元素的内容,元素类型为 VolatileLong,包含一个长整型成员 value 和 6 个没用到的长整型成员,value 设为 volatile 是为了让 value 的修改对所有线程都可见。主要代码如下:

public class FalseShare implements Runnable {
public static int NUM_THREADS = 4;
public final static long ITERATIONS = 500L * 1000L * 1000L;
private final int arrayIndex;
private static VolatileLong[] longs;
public static long SUM_TIME = 0l;
public FalseShare(final int arrayIndex) {
this.arrayIndex = arrayIndex;
}
private static void exeTest() throws InterruptedException {
Thread[] threads = new Thread[NUM_THREADS];
for (int i = 0; i < threads.length; i++) {
threads[i] = new Thread(new FalseShare(i));
}
for (Thread t : threads) {
t.start();
}
for (Thread t : threads) {
t.join();
}
}
public void run() {
long i = ITERATIONS + 1;
while (0 != --i) {
longs[arrayIndex].value = i;
}
}
public final static class VolatileLong {
public volatile long value = 0L;
//        public long p1, p2, p3, p4, p5, p6;     //缓存行填充
}
public static void main(final String[] args) throws Exception {
for (int j = 0; j < 10; j++) {
System.out.println("第" + j + "次...");
longs = new VolatileLong[NUM_THREADS];
for (int i = 0; i < longs.length; i++) {
longs[i] = new VolatileLong();
}
long start = System.nanoTime();
exeTest();
long end = System.nanoTime();
SUM_TIME += end - start;
}
System.out.println("平均耗时:" + SUM_TIME / 10);
}
}

第一次执行:

//        public long p1, p2, p3, p4, p5, p6;     //缓存行填充

第二次执行:

          public long p1, p2, p3, p4, p5, p6;     //缓存行填充

程序每次运行,循环10次,取平均耗时,耗时结果如下:

第一次:
平均耗时:28305116160
第二次:
平均耗时:14071204270

四、伪共享避免

1.缓存行填充(让不同线程操作的对象处于不同的缓存行)

2.使用编译指示,来强制每一个变量对齐(略)

五、总结

伪共享

本文地址:H5W3 » 【Java】一段代码,两倍时差,直击并发编程伪共享

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址