原子

  “在古希腊文中,原子就是不可再分的含义“。在程序设计的内涵下,『原子』性表示一个操作的中间状态对外的不可见性,体现在内存修改的中间状态不可见,体现在 CPU 指令的不可中断。原子操作是并发环境的基础,是互斥锁实现的必要条件。这里说的并发环境,是指多个执行序列,共享了某些状态,运行在单个或多个 CPU 核心之上。为了说明哪些操作是原子的,哪些不是,以一个对整型计数器的递增操作为例。考虑下面三种实现,为了『清晰』,使用 GCC inline assembly 呈现:

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
#include <stdint.h>
#include <sched.h>
 
volatile uint32_t counter = 0;
 
#define INCR(n) non_atomic_incr((n))
 
void
non_atomic_incr(volatile uint32_t *n)
{
  asm volatile ("mov %0, %%eax\n\t"
                "add $1, %%eax\n\t"
                "mov %%eax, %0" : "+m"(*n) :: "eax", "memory", "cc");
}
 
void
ump_atomic_incr(volatile uint32_t *n)
{
  asm volatile ("incl %0\n\t" : "+m"(*n) :: "memory");
}
 
void
smp_atomic_incr(volatile uint32_t *n)
{
  asm volatile ("lock; incl %0\n\t" : "+m"(*n) :: "memory");
}
 
void*
thread(void*)
{
#ifdef BINDING
  cpu_set_t cpuset;
  CPU_ZERO(&cpuset);
  CPU_SET(0, &cpuset);
  //~ bind threads to specific processor
  sched_setaffinity(0, sizeof(cpu_set_t), &cpuset);
#endif
  int i = 0;
  while (i++ < 1000000) {
    INCR(&counter);
  }
}
 
int
main()
{
  pthread_t t1, t2;
  pthread_create(&t1, NULL, thread, NULL);
  pthread_create(&t2, NULL, thread, NULL);
  pthread_join(t1, NULL);
  pthread_join(t2, NULL);
  fprintf(stderr, "%u\n", counter);
  return 0;
}

  程序中,两个线程,分别对初值为 0 的全局变量 counter 递增 1000000 次,改变 INCR 宏调用不同实现的递增函数。在一台 64i7 双核 4 线程 CPU 上面测试。

  显而易见,non_atomic_incr 不是原子的,因为递增操作使用了 3 条指令。

  ump_atomic_incr 比较有趣:没有定义 BINDING 宏时非原子,定义了 BINDING 宏时,两个线程运行在同一个 CPU 核心上,为原子操作。因为 ump_atomic_incr 的递增只有一条指令,而『指令的执行』是原子的,不会因调度而中断。因此,当两个线程运行在同一个核心上,指令执行的原子性就保证了递增操作的原子性。另外,由于 incl 指令是一个 RMWReadModifyWrite) 操作,指令执行包括三个阶段:读内存,修改变量,写内存。如果两个线程运行在不同的 CPU 核心,不同的核心在访问内存时,就会对内存总线的使用发起见缝插针式的竞争,从而就可能看到其他核心对内存修改的中间状态。

  下面言论只针对现代 Intel 64(X86-64) 架构,参考于 《Intel Developer Manual V3A》。CPU 访内指令可以分为三类:只读,只写,读写。如果写操作或者读操作的操作数不大于处理器字长(通常就是总线宽度),且该操作数对齐于其自然边界,这个写操作就只需要一次访存,是原子的。由于读写操作需要多次访问内存,CPU 默认不保证其原子性,但是引入一个被称作 lock 的指令前缀(smp_atomic_incr)。lock 前缀只能用于访存指令,该指令执行期间,内存总线会被锁定,直至指令执行结束。但是,冠以 lock 前缀的访存指令并不一定每次都锁总线:如果操作数已经存在于 Cache 中,就没有必要访问内存,也就没有必要锁定总线。

互斥锁

  很多时候,我们的共享数据都大于一个字长,更新操作也不是一条指令就可以完成的。更多时候,我们还需要保证一组共享数据的一系列更新的原子性。这时候就用到了锁。锁提供了一种同步机制,实现临界区的互斥访问(通过 lock/unlock),维护共享状态的一致性及基于共享数据的操作的原子性。
  如何实现锁机制呢?首先,锁本身也是一个共享数据,对锁的状态的更新也应该是安全的,否则临界区的安全就无从谈起,这就需要用到上面描述的原子操作。然后,翻翻课本,实现同步机制需要满足几个条件:

  • 空闲让进,如果锁没有被占用,lock 就应该成功;
  • 忙则等待,如果锁已经被占用,lock 调用方就需要等待(忙等/休眠);
  • 有限等待,无限等待就是通常所说的『死锁』了;
  • 让权等待,不要占着茅坑不拉屎。

  对于锁的实现者,我们只要满足前两个条件就行了,其他的交给用户来处理。下面是一个自选锁的简单实现(有问题,后面讲):

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
//~ exchange `*x`with `v` and return the old value
char inline 
xchg(volatile char *x, char v)
{
  asm volatile ("xchgb %b0, %1\n\t" //~ the lock prefix is implicit for `xchg`
                : "+r"(v) : "m"(*x) : "memory");
  return v;
}
 
struct spinlock_t
{
  volatile char lock;
};
 
void
spinlock_init(struct spinlock_t *lock)
{
  lock->lock = 0;
}
 
void
spinlock_lock(struct spinlock_t *lock)
{
  //if (!lock->lock) { 
    while (xchg(&lock->lock, 1)) ;
  //}
}
 
void
spinlock_unlock(struct spinlock_t *lock)
{
  lock->lock = 0;
}

内存屏障

  说到内存屏障(Memory Barrier),就不得不提内存模型(Memory Model),但内存模型的话题太大太复杂,我仍处在初级的探索阶段,没有能力做过多的展开。笼统地讲,内存模型主要是针对多处理器环境之上的内存访问顺序、处理器间内存状态修改的可见性做了说明和限制。每个处理器架构都有自己的内存模型,属于硬件级别的内存模型。另外,很多语言(Java 5+C++11Go)在不同硬件内存模型的基础上抽象出了一致的内存模型,属于软件级别的内存模型。总之,内存模型是一个相当抽象的概念,一般来讲,只有在多处理环境做 lock-free 编程的时候才需要考虑到。理解抽象的东西,最好的方法就是通过大量接地气的具体例子,眼见为实,反复把玩,获得感性的认识,在此基础上联系抽象概念,这样才能建立系统的认知框架。
  怎样才算具体呢,首先要有一段可以运行的代码,有明确的测试目的,当然,还要有一台知道 CPU 型号的计算机。下面就通过一个活生生的例子来说明内存屏障的必要性,使用的仍然是 X86-64 架构的 Intel Core(TM) i7-3520

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
#define mb() asm volatile ("mfence\n\t":::"memory")
__thread int threadID;
int counter = 0;
 
class Peterson
{
public:
  Peterson() {
    _victim = 0;
    _interested[0] = false;
    _interested[1] = false;
  }
  void lock() {
    int me = threadID;
    int he = 1 - me;
    _interested[me] = true;
    _victim = me;
    //mb();
    while (_interested[he] && _victim == me) ;
  }
  void unlock() {
    int me = threadID;
    _interested[me] = false;
  }
 
private:
  bool _interested[2];
  int _victim;
};
 
void*
thread(void *arg)
{
  threadID = (int)(long)arg;
  int i = 0;
  while (i++ < 1000000) {
    mtx.lock();
    ++counter;
    mtx.unlock();
  }
}
 
int
main()
{
  pthread_t t1, t2;
  pthread_create(&t1, NULL, thread, (void*)0);
  pthread_create(&t2, NULL, thread, (void*)1);
  pthread_join(t1, NULL);
  pthread_join(t2, NULL);
  fprintf(stderr, "counter: %d\n", counter);
  return 0;
}

  class Peterson 实现了一个互斥锁,是 Peterson 算法的一个 C++ 实现,仅适用于两个线程的同步操作,其正确性由 Gary L. Peterson 老先生的人品来保证。运行此程序:

1
2
3
4
5
6
7
8
9
10
11
$ g++ peterson.cpp -pthread
$ ./a.out 
counter: 1999980
$ ./a.out 
counter: 1999986
$ ./a.out 
counter: 2000000
$ ./a.out 
counter: 1999946
$ ./a.out 
counter: 1999911

  可以看到,大部分情况下,程序结果是错误的。
  在解释错误原因之前,要先讲一下『执行乱序』(Out of Order Execution)。程序指令的实际执行和 C++ 代码的书写顺序可能是不一致的,主要体现在两个阶段:编译和运行。
  在编译阶段,编译器可能对程序进行优化,在不影响程序运行结果(单线程角度)的情况下,调整语句的顺序,从而影响最终生成的二进制代码。在多线程环境,如果编译器对(未加锁保护的)共享变量的访问做了顺序调整,就可能造成程序结果不符合预期。有两种方式应对这种情况:禁止编译优化,编译器会老老实实地生成代码;
  显式地在特定位置加入『指示』,告诉编译器在调整指令顺序时不要跨越这个位置(即屏障),这种方式不会生成任何可执行的指令。GCC 中这个指示是一个不包含任何指令的内联汇编语句 asm volatile(“”:::”memory”)

  在运行阶段,程序指令已经确定,CPU 根据程序计数器(PC)『顺序』加载和执行代码。但现代处理器由于引入了指令流水和 Cache,为了最大化处理速度,减少由于 Cache Miss 造成的执行流阻塞,在保证正确性(单处理器角度)的前提下,允许后加载的指令先执行(Memory Barriers: a Hardware View for Software Hackers)。这也是为什么这种乱序被称作 Memory Reordering,而不是 Instruction Reordering 的原因。这种乱序执行,对于单处理器是没有任何问题的。但在多处理环境下,对多线程间的共享数据的乱序访问,就可能出现内存可见性带来的逻辑问题。之前也做过一个相关的、简单但没有多少实际意义的测试,见这里

  现在回到 Peterson 程序上来。程序运行结果不符合预期,那一定是两个线程同时进入了临界区。在 Peterson 算法正确性可以保证的前提下,是什么造成『忙则等待』被打破呢?不错,乱序执行(变量的更新只有单纯的读和写,原子性可以保证)。那么乱序是因为编译优化造成的吗?不是,为什么不是呢?因为我们没有让编译器进行优化,这一点可以通过分析汇编代码加以验证(略)。那么就是指令执行时发生乱序了。哪些操作乱序了呢?一定是共享变量(废话)。线程共享的变量有三个,两个 _interested[0],还有 _victim。至于是哪些操作发生了乱序,在不了解程序运行的 CPU 所使用的内存模型的情况下,是无法定位的。现在简单地给出来:是 _interested[me] 的写操作和 _intersted[he] 的读操作发生了乱序,即读操作在写操作之前完成了。

  修复的方式,就是使用『内存屏障』。内存屏障提供了一些指令,每种指令都有自己的语义,可以杜绝一种类型的乱序。内存屏障的种类因 CPU 架构的不同而不同,基本上,如果一个架构允许某种乱序,这种乱序可能带来问题,那么它就必须提供相应的指令,防止这种乱序。乱序种类越多,说明该架构越容易发生乱序,这种架构的内存模型就是一种 Weak(Relaxed) Memory Model;反之,说明该架构相对地是一种 Strong(Strict) Memory Model。如果抽象地讲内存屏障的种类,篇幅太大,难以展开,那么就以 X86-64 架构为例。这是一种相对更加 Strong 的内存模型,它只允许一种乱序:读操作可以在前面的写操作完成之前完成,即『写读』乱序。其他类型,例如『写写』『读写』『读读』形式的乱序都是不会发生的:

  • Loads are not reordered with other loads.
  • Stores are not reordered with other stores.
  • Stores are not reordered with older loads.
  • Loads may be reordered with older writes to different locations but not with older writes to the same location.
  • In a multiprocessor system, memory ordering obeys causality (memory ordering respects transitive visibility).
  • In a multiprocessor system, stores to the same location have a total order.
  • In a multiprocessor system, locked instructions have a total order.
  • Loads and stores are not reordered with locked instructions.

  X86-64 提供三个指令做内存屏障:

  • sfence,是一个单向屏障。在执行 sfence 指令之前,sfence 之前的所有 store 指令都已经完成,而不关心 load 指令,以及 sfence 之后的 store 指令。
  • lfence,也是一个单向屏障。在执行 lfence 之前,lfence 之前的所有 load 指令都已经完成,而不关心 store 指令,以及 lfence 之后的 load 指令。
  • mfence,是一个全能屏障,Full Barrier。执行 mfence 之前,mfence 之前所有的 loadstore 都已经完成,而且 mfence 之后的所有 loadstore 都没有发生。
  • 另外,lock 前缀的访存指令相当于 Full Barrierxchg 已隐式加 lock 前缀。

  考虑 Peterson 算法中的『写读』乱序,lfencesfence 都是不合适的。只能使用 mfence 指令,也就是代码中被注释掉的 mb() 宏。加入该指令之后,该程序就『暂时』是安全的了。
  至此,X86-64 中的内存屏障似乎讲完了,咱们来看一个更加实际的例子,看它是不是安全的。

1
2
3
4
5
6
7
8
9
//~ global
Message *msg_to_send = NULL;
bool ready = false;
//~ producer thread
msg_to_send = produce_message();
ready = true;
//~ consumer thread
while (!ready) ;
consume_message(msg_to_send);

  显然不是安全的,因为 producer 中的两个写操作和 consumer 中的两个读操作都可能会乱序,造成 consumer 拿到的 msg_to_send 为空。解决方法是分别添加『写写』『读读』屏障。但是在 X86-64 下,代码是安全的。
  现在回头看看之前实现的自旋锁,如果这样使用,有问题吗?

1
2
3
4
5
spinlock_t lock;
spinlock_init(&lock);
spinlock_lock(&lock);
//~ critical section
spinlock_unlock(&lock);

  看起来似乎没有。但如果发生乱序,临界区内的数据访问穿过 lock/unlock 操作,在临界区外『就/才』可见呢?于是,需要有另外两种语义的内存屏障,即 acquirerelease。具有 acquire 语义的内存屏障,保证其后的读写不会提前到屏障之前;具有 release 语义的屏障,保证之前的读写已经生效/可见。这两种内存屏障都是单向的,即允许临界区外的读写进入到临界区内。具体到 X86-64 架构,考虑前面描述的内存模型,读操作就具有 acquire 语义,而写操作具有 release 语义,所以这个自旋锁实现在 X86-64 下是正确的。

总结

  内存屏障只是解决问题的一种方式,其背后是各式各样内存模型的庞然大物,隐藏着辛酸和无奈。现代编程语言都已经或者开始重视这个问题,在语言层面定义统一的内存模型,减轻程序员的痛苦。比如 Java 中的 volatile 关键字具有 read-acquirewrite-release 语义;C++11 开始的 std::atomic 也提供 acquire/release 语义,还有秉承 C++ 哲学的 relaxed store
  一般来讲,在所有共享内存的更新操作上面显式使用同步机制,无论是语言本身还是程序库,都可以不考虑内存模型带来的问题(内存映射的 IO 操作除外)。但是,编写无锁代码时,对内存模型的理解和内存屏障的使用是无法逾越的必修课。

Tags: ,.
你好!除了代码,此处没有多少原创之物,皆为本人搜集、整理、总结之记录与心得,欢迎转载分享!转载时请尽量注明出处,将不胜感激。祝你健康、快乐!
Home

RFC: Request For Comments. Orz..

You must be logged in to post a comment.