写在前面
本文是针对南大蒋炎岩老师 OS 课程：多处理器编程：从入门到放弃 的个人总结，一些概念参照了以下链接：
- 【高并发】解密诡异并发问题的第一个幕后黑手——可见性问题
- 【高并发】解密导致并发问题的第二个幕后黑手——原子性问题
- 【高并发】解密导致并发问题的第三个幕后黑手——有序性问题
原子性
原子性指一个或多个操作，在执行时不会被中断，保证全部操作一次执行完成。
很经典的原子性问题就是银行、支付宝等转账操作。而这里列举《操作系统导论》第 26 章的 homework。
这里有x86.py做模拟器，looping-race-nolock.s程序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| # assumes %bx has loop count in it
.main
.top
# critical section
mov 2000, %ax # get 'value' at address 2000
add $1, %ax # increment it
mov %ax, 2000 # store it back
# see if we're still looping
sub $1, %bx
test $0, %bx
jgt .top # greater
halt # exit
|
整个程序流程是，向%ax中写入内存2000记录的值，%ax = *(2000)，然后执行%ax = %ax + 1，再写入内存*(2000) = %ax；紧接着%bx = %bx - 1，执行判断%bx > 0，成立的话回到.top，否则退出。
首先看看双线程执行且线程执行完成后中断，发生的情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| $ ./x86.py -p looping-race-nolock.s -t 2 -R ax,bx -M 2000 -a bx=1 -c -i 100
2000 ax bx Thread 0 Thread 1
0 0 1
0 0 1 1000 mov 2000, %ax
0 1 1 1001 add $1, %ax
1 1 1 1002 mov %ax, 2000
1 1 0 1003 sub $1, %bx
1 1 0 1004 test $0, %bx
1 1 0 1005 jgt .top
1 1 0 1006 halt
1 0 1 ----- Halt;Switch ----- ----- Halt;Switch -----
1 1 1 1000 mov 2000, %ax
1 2 1 1001 add $1, %ax
2 2 1 1002 mov %ax, 2000
2 2 0 1003 sub $1, %bx
2 2 0 1004 test $0, %bx
2 2 0 1005 jgt .top
2 2 0 1006 halt
-----------------------------------------------------------------------
|
这里模拟的命令是：以双线程执行程序looping-race-nolock.s，追踪寄存器%ax和%bx，追踪内存2000，设置两个线程的%bx = 1，中断频率为 100。可以看到最终*(2000) = 2，这也是正确的结果。
接下来调整中断频率为 1、2、3 和 4，看看有什么不同。
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| # -i 1
2000 ax bx Thread 0 Thread 1
0 0 1
0 0 1 1000 mov 2000, %ax
0 0 1 ------ Interrupt ------ ------ Interrupt ------
0 0 1 1000 mov 2000, %ax
0 0 1 ------ Interrupt ------ ------ Interrupt ------
0 1 1 1001 add $1, %ax
0 0 1 ------ Interrupt ------ ------ Interrupt ------
0 1 1 1001 add $1, %ax
0 1 1 ------ Interrupt ------ ------ Interrupt ------
1 1 1 1002 mov %ax, 2000
1 1 1 ------ Interrupt ------ ------ Interrupt ------
1 1 1 1002 mov %ax, 2000
1 1 1 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1003 sub $1, %bx
1 1 1 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1003 sub $1, %bx
1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1004 test $0, %bx
1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1004 test $0, %bx
1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1005 jgt .top
1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1005 jgt .top
1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1006 halt
1 1 0 ----- Halt;Switch ----- ----- Halt;Switch -----
1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1006 halt
----------------------------------------------------------------------
# -i 2
2000 ax bx Thread 0 Thread 1
0 0 1
0 0 1 1000 mov 2000, %ax
0 1 1 1001 add $1, %ax
0 0 1 ------ Interrupt ------ ------ Interrupt ------
0 0 1 1000 mov 2000, %ax
0 1 1 1001 add $1, %ax
0 1 1 ------ Interrupt ------ ------ Interrupt ------
1 1 1 1002 mov %ax, 2000
1 1 0 1003 sub $1, %bx
1 1 1 ------ Interrupt ------ ------ Interrupt ------
1 1 1 1002 mov %ax, 2000
1 1 0 1003 sub $1, %bx
1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1004 test $0, %bx
1 1 0 1005 jgt .top
1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1004 test $0, %bx
1 1 0 1005 jgt .top
1 1 0 ------ Interrupt ------ ------ Interrupt ------
1 1 0 1006 halt
1 1 0 ----- Halt;Switch ----- ----- Halt;Switch -----
1 1 0 1006 halt
----------------------------------------------------------------------
# -i 3
2000 ax bx Thread 0 Thread 1
0 0 1
0 0 1 1000 mov 2000, %ax
0 1 1 1001 add $1, %ax
1 1 1 1002 mov %ax, 2000
1 0 1 ------ Interrupt ------ ------ Interrupt ------
1 1 1 1000 mov 2000, %ax
1 2 1 1001 add $1, %ax
2 2 1 1002 mov %ax, 2000
2 1 1 ------ Interrupt ------ ------ Interrupt ------
2 1 0 1003 sub $1, %bx
2 1 0 1004 test $0, %bx
2 1 0 1005 jgt .top
2 2 1 ------ Interrupt ------ ------ Interrupt ------
2 2 0 1003 sub $1, %bx
2 2 0 1004 test $0, %bx
2 2 0 1005 jgt .top
2 1 0 ------ Interrupt ------ ------ Interrupt ------
2 1 0 1006 halt
2 2 0 ----- Halt;Switch ----- ----- Halt;Switch -----
2 2 0 1006 halt
----------------------------------------------------------------------
# -i 4
2000 ax bx Thread 0 Thread 1
0 0 1
0 0 1 1000 mov 2000, %ax
0 1 1 1001 add $1, %ax
1 1 1 1002 mov %ax, 2000
1 1 0 1003 sub $1, %bx
1 0 1 ------ Interrupt ------ ------ Interrupt ------
1 1 1 1000 mov 2000, %ax
1 2 1 1001 add $1, %ax
2 2 1 1002 mov %ax, 2000
2 2 0 1003 sub $1, %bx
2 1 0 ------ Interrupt ------ ------ Interrupt ------
2 1 0 1004 test $0, %bx
2 1 0 1005 jgt .top
2 1 0 1006 halt
2 2 0 ----- Halt;Switch ----- ----- Halt;Switch -----
2 2 0 1004 test $0, %bx
2 2 0 ------ Interrupt ------ ------ Interrupt ------
2 2 0 1005 jgt .top
2 2 0 1006 halt
----------------------------------------------------------------------
|
可以看到，当中断频率为 1 和 2 时，*(2000) = 1；当中断频率为 3 和 4 时，*(2000) = 2。
在中断频率为 1 和 2 时，对内存2000的读取修改写入三步操作，被中断了，这就导致数据修改不是原子操作，触发了原子问题，先后写入的值产生了覆盖，而不是累加。
1
2
3
4
5
6
7
8
9
10
| Thread 0 Thread 1
1000 mov 2000, %ax
1001 add $1, %ax
------ Interrupt ------ ------ Interrupt ------
1000 mov 2000, %ax
1001 add $1, %ax
------ Interrupt ------ ------ Interrupt ------
1002 mov %ax, 2000
1003 sub $1, %bx
|
当中断频率为 3 和 4 时，则没有这个问题，在发生中断前，三步操作全部完成，可以看作原子操作，没有触发原子问题。
1
2
3
4
5
6
7
8
9
10
| Thread 0 Thread 1
1000 mov 2000, %ax
1001 add $1, %ax
1002 mov %ax, 2000
------ Interrupt ------ ------ Interrupt ------
1000 mov 2000, %ax
1001 add $1, %ax
1002 mov %ax, 2000
------ Interrupt ------ ------ Interrupt ------
|
这个中断其实就是进程调度时的算法，比如时间片算法，产生了线程切换，就有可能造成原子性问题。而这里是通过模拟器模拟了线程切换。
可见性
可见性指一个线程对共享变量的修改，另一个线程能够立刻看到。
对于同一个进程中的线程 A 和 B，如果线程 A 修改了共享变量，那么线程 B 在读取使用这个共享变量时，得到的一定是修改后的值。共享变量指当前进程中的全局变量、堆区数据等。
这里的可见性问题不与原子性问题交杂，即数据读写一定是原子操作的。
对于写入内存的数据，产生可见性问题的原因一般来说是 CPU cache。cache 在读取内存数据供 CPU 使用时，可能存在一个『时间差』，导致数据不同的问题。
在单核 CPU 中，不存在可见性问题。单核 CPU 使用一个 cache，线程在切换时都可以读取到修改的数据。
但是在多核 CPU 有，存在多个 cache，于是乎会有一个时间差问题。比如 cache1 和 cache2 都读取了同一个内存地址的共享变量。线程 A 读取 cache1 的数据并做修改后，发生中断调用线程 B，但是线程 B 此时使用的是 cache2 中未修改的数据，这时候就会发生可见性问题。
有序性
有序性指按照代码既定的顺序执行。
编译器不会对系统调用做优化，但是会根据内存使用情况，按照单线程的方式，对代码执行顺序进行优化。比如有变量x，分别赋值为 1、2 和 3，编译器会直接优化赋值为 3，跳过中间两步。
在单线程的情况下，这些调整不会对程序结果造成影响，反而会优化代码执行；但是在多线程的情况下，调整代码执行顺序可能会造成出乎意料的结果，影响程序执行。
这里有一个 双线程求和代码，按照程序来看，最终结果应该是sum = 2*N = 200000000。接下来看一看开启优化后会出现什么情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| #include "thread.h"
#define N 100000000
long sum = 0;
void Tsum() {
for (int i = 0; i < N; i++) {
sum++;
}
}
int main() {
create(Tsum);
create(Tsum);
join();
printf("sum = %ld\n", sum);
}
|
先看一下不同优化下代码执行情况。不优化时sum的值是随机的，而O1和O2优化后sum的值是固定的。
1
2
3
4
5
6
7
8
| $ gcc -Wall -lpthread -Og sum.c && ./a.out
sum = 104326055
$ gcc -Wall -lpthread -O1 sum.c && ./a.out
sum = 100000000
$ gcc -Wall -lpthread -O2 sum.c && ./a.out
sum = 200000000
|
首先是O1优化，得到如下汇编代码。%rdx = 100000001，%rax++并赋值给%rcx，多次循环后，%rcx = 100000000，%rax = 100000001，此时%rax == %rdx跳出循环，将%rcx赋值得到sum = 100000000。关键就在于优化后最后一步直接赋值sum = %rcx，相当于双线程最终执行两次赋值操作，sum最终还是100000000。
1
2
3
4
5
6
7
8
9
10
11
| $ gcc -Wall -lpthread -c -O1 sum.c && objdump -d sum.o
0000000000000016 <Tsum>:
16: 48 8b 15 00 00 00 00 mov 0x0(%rip),%rdx # 1d <Tsum+0x7>
1d: 48 8d 42 01 lea 0x1(%rdx),%rax
21: 48 81 c2 01 e1 f5 05 add $0x5f5e101,%rdx
28: 48 89 c1 mov %rax,%rcx
2b: 48 83 c0 01 add $0x1,%rax
2f: 48 39 d0 cmp %rdx,%rax
32: 75 f4 jne 28 <Tsum+0x12>
34: 48 89 0d 00 00 00 00 mov %rcx,0x0(%rip) # 3b <Tsum+0x25>
3b: c3 ret
|
然后是O2优化，得到如下汇编代码。直接通过add给变量+100000000，也就是通过编译器优化成了一个原子操作，双线程操作后直接得到sum = 200000000的正确结果。
1
2
3
4
5
6
| $ gcc -Wall -lpthread -c -O2 sum.c && objdump -d sum.o
0000000000000020 <Tsum>:
20: 48 81 05 00 00 00 00 addq $0x5f5e100,0x0(%rip) # 2b <Tsum+0xb>
27: 00 e1 f5 05
2b: c3 ret
2c: 0f 1f 40 00 nopl 0x0(%rax)
|
由此可以看出，编译器在优化时不会考虑多线程的情况。上例开启O2优化执行了add的原子操作，得到正确答案。所以一般在写多线程代码时，可以考虑对源代码进行顺序编译，通过一些指令。