0%

《操作系统》伪共享

CPU多级缓存

为了解决计算机系统中主内存与 CPU 之间运行速度差问题,会在 CPU 与主内存之间添加一级或者多级高速缓冲存储器(Cache)。这个 Cache 一般是被集成到 CPU 内部的, 所以也叫 CPU Cache

缓存行(Cache Line)

下面代码可以查看本机的缓存行大小

1
2
3
4
5
6
7
8
9
10
package main

import (
"github.com/intel-go/cpuid"
"fmt"
)

func main() {
fmt.Printf("%d bytes\n", cpuid.CacheLineSize)
}

Cache Line中有B(B=64)个字节用来存储数据,即每个Cache Line能存储64个字节的数据,每个Cache Line又额外包含一个有效位(valid bit)、t个标记位(tag bit),其中valid bit用来表示该缓存行是否有效;

tag bit用来协助寻址,唯一标识存储在CacheLine中的块;而Cache Line里的64个字节其实是对应内存地址中的数据拷贝。

根据Cache的结构,我们可以推算出每一级Cache的大小为B×E×S。

伪共享

CPU 访问某个变量时,首先会去看 CPU Cache 内是否有该变量,如果有则直接从中获取,否则就去主内存里面获取该变量,然后把该变量所在内存区域的一个 Cache 行大小的内存复制到 Cache 中。

由于存放到 Cache行的是内存块而不是单个变量,所以可能会把多个变量存放到一个Cache行中。

当多个线程同时修改一个缓存行里面的多个变量时,根据MESI大法(MESI协议实现了多个处理器中Cache的分布式强一致性),同时只能有一个线程操作缓存行,所以相比将每个变量放到单独的缓存行,性能会有所下降,这就是伪共享

但是单线程访问时将数组元素放入一个或者多个缓存行对代码执行是有利的,因为数据都在缓存中,代码执行会更快

下面再次图解说明:

数据X、Y、Z被加载到同一Cache Line中,线程A在Core1修改X,线程B在Core2上修改Y。

根据MESI大法,假设是Core1是第一个发起操作的CPU核,Core1上的L1 Cache Line由S(共享)状态变成M(修改,脏数据)状态,然后告知其他的CPU核,图例则是Core2,引用同一地址的Cache Line已经无效了;

当Core2发起写操作时,首先导致Core1将X写回主存,Cache Line状态由M变为I(无效),而后才是Core2从主存重新读取该地址内容,Cache Line状态由I变成E(独占),最后进行修改Y操作, Cache Line从E变成M。

可见多个线程操作在同一Cache Line上的不同数据,相互竞争同一Cache Line,导致线程彼此牵制影响,变成了串行程序,降低了并发性。

此时我们则需要将共享在多线程间的数据进行隔离,使他们不在同一个Cache Line上,从而提升多线程的性能。

伪共享解决办法

一般都是通过字节填充的方式来避免该问题,也就是创建一个变量时使用填充字段填充该变量所在的缓存行,这样就避免了将多个变量存放在同一个缓存行中

下面代码中,开启两个协程,分别对一个结构体变量中的两个相邻的数据成员进行n次原子自增操作。如果将padding去掉,运行速度将慢了好几倍

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
package main

import (
"fmt"
"sync"
"sync/atomic"
"time"
)

type Foo struct {
a uint64
//_ [56]byte
b uint64
//_ [56]byte
}

func main() {
foo := Foo{}
var wg sync.WaitGroup
t := time.Now()

wg.Add(1)
go func() {
for i := 0; i < 1000 * 1000; i++ {
atomic.AddUint64(&foo.a, 1)
}
wg.Done()
}()

wg.Add(1)
go func() {
for i := 0; i < 1000 * 1000; i++ {
atomic.AddUint64(&foo.b, 1)
}
wg.Done()
}()

wg.Wait()

fmt.Println(time.Now().Sub(t))
}

实测结果是:

无padding:42.378666ms
有padding:6.137713ms

可以看到伪共享的负面效果惊人




微信关注我,及时接收最新技术文章