sui_rust/ch02/s4_lockfree.rs
1//! 第二章：Rust核心概念
2//! 2.3 Lockfree
3//!
4
5/**
6
7 ### 并发编程注重的三点：
8
9 1. 原子性。保证操作是原子的。
10 2. 可见性。保证数据是同步的。
11 3. 顺序性。保证操作的顺序是正确的。
12
13 方法：
14
15 - 同步锁
16 - 无锁编程
17
18
19 ### 思考：锁带来的问题？
20
21 1. 性能。引入无锁编程可以最大化减少线程上下文切换，线程等待。
22 2. 死锁。引入无锁编程就不会产生死锁。
23
24 无锁编程性能并不是总是优于锁同步。
25
26 无锁编程依赖于原子类型，使用原子类型还需要深入了解一些概念。
27
28
29 ### 理解无锁并发的关键在于理解计算机组成
30
31 ```text
32 +------+ +------+ +------+
33 | core | | core | | core |
34 +---+--+ +---+--+ +---+--+
35 | | |
36 +lv1+--+ +-lv1--+ +lv1---+
37 |cache | |cache | | cache|
38 +---+--+ +---+--+ +---+--+
39 | | |
40 +lv2---+ +lv2---+ +lv2---+
41 | cache| | cache| | cache|
42 +---+--+ +---+--+ +---+--+
43 | | |
44 +-----------------------+
45 |
46 +---------------+--------------+
47 | lv3 cache |
48 +---------------+--------------+
49 |
50 |
51 +---------------+--------------+
52 | main memory |
53 +------------------------------+
54
55 ```
56
57 ### 缓存一致性问题
58
59 思考：下面代码最终执行后 x 和 y 的状态上什么？
60
61 ``` text
62 // THREAD 1
63
64 if unsafe { *x == 1 } {
65 unsafe { *y += 1 }
66 }
67
68 // THREAD 2
69 unsafe {
70 *y = 10;
71 *x = 1;
72 }
73 ```
74
75 最终结果实际取决于下面几个问题：
76
77 1. THREAD 1 和 THREAD 2 运行顺序是什么？ （使用锁同步可以保证“喂给” CPU 的指令锁有顺序性的）
78 2. 每一个 CPU 使用的高速缓存的状态 （要保证缓存一致性）
79 3. CPU 指令重排（乱序执行，为了更好的利用流水线，达到性能极致）
80 4. 编译器指令重排 （调整指令顺序，使其对 CPU 更友好）
81
82
83 > 高速缓存通过 M(Modified)E(Exclusive)S(Shared)I(Invalid) 协议来保持同步。MESI的有趣之处在于，每个高速缓存行都在维护自己的内存地址状态机。
84 > 一个 CPU 通过 IPC (Inter-Processor-Communication) 向 另一个 CPU 来发送消息，比如，「独占内存地址」、「修改内存数据」等。
85 > 这里要注意，CPU 并不是做来某些操作马上发出消息或者是收到消息马上就执行相应操作的。也就是说，CPU 通信的这些消息都是异步的。
86 > 如果 CPU 多核之间用同步通信的话，性能上无法接受。比如一个 CPU 要等待其他 CPU 来确认信息，或从其他 CPU 获取最新数据等。
87 > 所以，为了让 CPU 核之间可以高性能地同步信息（保证cpu乱序执行指令的同时，还要保证程序正确性），就引入了内存屏障的技术。
88
89
90 ### 内存屏障
91
92 内存屏障允许开发者在编写代码等时候在需要等地方加入它。
93
94 内存屏障分为：
95
96 1. 读屏障（Load Memory Barrier）。任何「读屏障」前的「读操作」都会先于「读屏障」后的「读操作」完成。
97 2. 写屏障（Store Memory Barrier）。任何「写屏障」前的「写操作」都会先于「写屏障」后的「写操作」完成。
98 3. 全屏障。同时包含读屏障和写屏障的作用。
99
100 load，代表从内存读数据。store，代表向内存写数据。
101
102 现代 CPU 架构中一般分为四种内存屏障：
103
104 1. Load-Load: 等价于上面介绍的「读屏障」。任何「该屏障」前的「读操作」都会先于「该屏障」后的「读操作」完成。
105 2. Load-Store: 任何「该屏障」前的「读操作」都会先于「该屏障后」的「写操作」完成。
106 3. Store-Load: 任何「该屏障」前的「写操作」都会先于「该屏障后」的「读操作」完成。
107 4. Store-Store: 等价于上面介绍的「写屏障」。任何「该屏障」前的「写操作」都会先于「该屏障」后的「写操作」完成。
108
109
110 开发者通过内存屏障，告诉 CPU/编译器 内存屏障前后指令的顺序关系，这样 CPU/编译器 就不会重排这些指令，从而保证原子指令的顺序性。
111
112 ### 内存模型
113
114 这么多内存屏障，什么时候该使用哪种，需要由开发者来指定。这道理和 Unsafe Rust 类似，编译器无法检查的安全性，交给开发者。
115
116 这就是语言提供内存模型的原因。Cpp 和 Rust 语言都提供了原子（Atomic）类型，并且这些原子类型都是可以指定内存顺序（告诉CPU使用哪种内存屏障）
117
118 Rust 目前并没有正式的内存顺序模型，但是它在语义和行为上和 Cpp 一致。
119
120 由此引申出内存屏障都两种语义：
121
122 1. acquire（获取）语义。Load 之后的读写操作无法被重排至 Load 之前。即 相当于Load-Load和Load-Store屏障。
123 2. release（释放）语义。Store 之前的读写操作无法被重排至 Store 之后。即 相当于Load-Store和Store-Store屏障。
124
125
126 ### 原子操作
127
128 Rust 标准库中定义的原子类型：[std::sync::atomic: https://doc.rust-lang.org/stable/std/sync/atomic/index.html](https://doc.rust-lang.org/stable/std/sync/atomic/index.html)
129 其中`// std::sync::atomic::Ordering`定义了 Rust 支持的内存顺序，官方文档指出，当前和 Cpp20 的内存顺序是一致的。
130
131
132 ```rust
133 // std::sync::atomic::Ordering
134
135 pub enum Ordering {
136 Relaxed,
137 Release,
138 Acquire,
139 AcqRel,
140 SeqCst,
141 }
142 ```
143
144 注意，Rust 当前并没有公开 cpp 里面包含对 consume 语义。
145
146 内存顺序说明：
147
148 - Relaxed，表示原子类型只保证原子操作即可，没有内存顺序（不指定内存屏障）
149 - Release，
150 - 表示使用 Release 语义。
151 - 当前线程内的所有写操作，对于其他对这个原子变量进行 acquire 的线程可见
152 - Acquire，
153 - 表示使用 Acquire 语义。
154 - acquire 可以保证读到所有在 release 前发生的写入。
155 - AcqRel，
156 - 表示对读取和写入施加 acquire-release 语义，无法被重排。
157 - 可以看见其他线程施加 release 语义的所有写入，同时自己的 release 结束后所有写入对其他施加 acquire 语义的线程可见。
158 - SeqCst，
159 - 如果是读取就是 acquire 语义，如果是写入就是 release 语义，如果是读取+写入就是 acquire-release 语义。
160 - 所有线程都能以相同的顺序看到所有顺序一致的操作。
161
162 不同对内存顺序，对应不同对内存屏障，进一步，也代表了不同的性能。
163 在竞争条件比较激烈的情况下，Relaxed 性能是最好的，因为它不需要任何内存屏障，这就意味着CPU之间不需要进行一致性同步。
164 相对而言，SeqCst 就是性能最差的那个了，因为它需要 CPU 同步所有指令。
165 但是 Relaxed 因为没有内存屏障，所以可能会有指令重排带来带风险。
166 所以，Rust 标准库也提供了` std::sync::atomic::compiler_fence`和` std::sync::atomic::fence`两个函数，来帮助解决在原子指令使用 Relaxed 内存顺序的情况下编译器或CPU指令重排的问题。
167
168 示例：[https://doc.rust-lang.org/stable/std/sync/atomic/fn.compiler_fence.html](https://doc.rust-lang.org/stable/std/sync/atomic/fn.compiler_fence.html)
169
170 原子类型提供的方法，基于硬件原子指令 (x均为std::atomic) ：
171
172 - `load`，返回x的值。
173 - `store`，把x设为n，什么都不返回。
174 - `swap`，把x设为n，返回设定之前的值。
175 - `compare_and_swap`，经典cas操作。
176 - `compare_exchange.
177 - `compare_exchange_weak
178 - `fetch_add(n), fetch_sub(n)`，原子地做x += n, x-= n，返回修改之前的值。
179
180
181 使用原子类型需要注意的是：
182
183 - Store操作，可选内存顺序：Relaxed, Release, SeqCst。否则panic。
184 - Load操作，可选内存顺序：Relaxed, Acquire, SeqCst。否则panic。
185 - Read-modify-write(读-改-写)操作，可选如下顺序：Relaxed, Acquire, Release, AcqRel, SeqCst。
186 - 所有操作的默认顺序都是 SeqCst。
187
188 ```rust
189 // 实现一个简单的自旋锁（spinlock）
190
191 use std::sync::Arc;
192 use std::sync::atomic::{AtomicUsize, Ordering};
193 use std::{thread, time};
194
195 fn main() {
196 let spinlock = Arc::new(AtomicUsize::new(1));
197
198 let spinlock_clone = Arc::clone(&spinlock);
199 let thread = thread::spawn(move|| {
200 // lock
201 spinlock_clone.store(1, Ordering::SeqCst);
202 // do something
203 let t = time::Duration::from_secs(3);
204 std::thread::sleep(t);
205 // unlock
206 spinlock_clone.store(0, Ordering::SeqCst);
207 });
208
209 // Wait for the other thread to release the lock
210 while spinlock.load(Ordering::SeqCst) != 0 {}
211
212 if let Err(panic) = thread.join() {
213 println!("Thread had an error: {:?}", panic);
214 }
215 }
216
217 ```
218
219 利用 AtomicBool 实现一个 轻量级的锁 ：
220
221 ```rust
222 use std::sync::atomic::Ordering;
223 use core::sync::atomic::AtomicBool;
224
225 struct LightLock(AtomicBool);
226
227 impl LightLock {
228 pub fn new() -> LightLock {
229 LightLock(AtomicBool::new(false))
230 }
231
232 pub fn try_lock<'a>(&'a self) -> Option<LightGuard<'a>> {
233 let was_locked = self.0.swap(true, Ordering::Acquire);
234 if was_locked {
235 None
236 } else {
237 Some(LightGuard { lock: self })
238 }
239 }
240 }
241
242 struct LightGuard<'a> {
243 lock: &'a LightLock,
244 }
245
246 impl<'a> Drop for LightGuard<'a> {
247 fn drop(&mut self) {
248 self.lock.0.store(false, Ordering::Release);
249 }
250 }
251 ```
252
253 ### ABA 问题：
254
255 任何无 GC 的语言在无锁编程的时候都要考虑此问题。
256
257 试想一个连续压栈（push）和 出栈（pop）的并发操作。假设这两个操作都是由 cas 原语实现的。
258
259 > 具体来说，假如有两个线程 T1 和 T2，操作初始栈为「a->b->c」的栈结构。
260 > 当 T1 把 a 从栈内弹出，此时发生线程调度，
261 > 切换到 T2 ，T2 弹出 a 和 b，把 a 再 push 到栈里，此时 T2 的栈为 「a->c」。
262 > 然后线程切回 T1 ，T1 看到栈顶（a）的地址和它之前获得的 a 地址相同，然后将 栈顶设置为 b （a.next），然而 b 早就被释放来。
263
264 这就是 ABA 问题。ABA 问题本质是内存回收问题。当 b 被弹出当时候，要保障它当内存不能被立即重用。
265
266 解决该问题的思路有多种：引用计数、分代回收（Epoch Based Reclamation）和 险象指针（Hazard pointer）。
267
268 注意：ABA 问题一般是发生在 X86 架构上 cas 原子操作的时候。ARM 架构已经从根源上解决了 ABA 问题。
269
270 - 分代回收示例：[https://github.com/crossbeam-rs/crossbeam/blob/master/crossbeam-epoch/examples/sanitize.rs](https://github.com/crossbeam-rs/crossbeam/blob/master/crossbeam-epoch/examples/sanitize.rs)
271 - 险象指针示例：
272 - [https://github.com/solotzg/rs-lockfree/blob/master/src/hazard_pointer.rs](https://github.com/solotzg/rs-lockfree/blob/master/src/hazard_pointer.rs)
273 - [https://github.com/redox-os/conc/blob/master/src/sync/treiber.rs](https://github.com/redox-os/conc/blob/master/src/sync/treiber.rs)
274
275
276
277*/
278pub fn memory_reordering() {}