并发
如果两件事情在逻辑上同时发生了, 那么我们就说它们并发了.
在Linux上很容易用POSIX API创建新的执行流(线程), 可以利用 strace top man 等工具观察具体创建的原理 跑起来的效果和参数含义
并发Bug
并发带来的问题是指令原子性的破坏. 例如语句 a = a + 1;
可能会被编译为多条指令, 而中断到来的时刻是任意的,
甚至多条指令是并行执行的(显然在逻辑上并发)
原子性是重要的多线程程序性质, 一般的库函数都能看到 MT-Safe 这样的描述.
互斥
为了保证一段代码的原子性, 引入互斥锁的概念. 经典的互斥锁利用硬件提供的原子操作机制可以实现目标代码的串行化(所有线程至多一个在当前时刻执行这段代码)
被原子化的代码叫做 Critical Section
编译优化
GCC 的编译优化是基于单线程假设的,
因此在多线程下可能会行为不一致(回忆volatile)
甚至会出现指令的重排(编译器级别)导致的原子性丧失/语义不一致.
然而CPU也是动态多发射的, 类似的指令乱序仍然可能发生. 这使得某些关于指令顺序的假设会改变(翻阅TSO内存模型). 注意到内存的读/写相对运算指令而言是副作用指令, 因此这也意味着两段程序的 observable behaviour 会与顺序执行的单线程程序不一样. 具体如何需要看 ISA 手册.
软件和硬件支持
编译器指令 barrier, 硬件指令 fence 都可以一定程度上保证可观测行为与预期一致.
Model Checking
为了说明并发程序的正确性(证明某段程序的性质) 可以使用 Model Checking 工具来建模, 本质是画状态机+设计谓词.
锁
用户程序眼中的锁就是两个有特殊语义的API
typedef struct {
...
} lock_t;
void lock(lock_t *lk);
void unlock(lock_t *lk);对于同一把锁 lk, 多个调用 lock(&lk)
的线程只能有一个返回, 其余都将等待直至持有锁的线程调用
unlock(&lk).
硬件支持
利用 x86 提供的 lock xchg 指令即可原子地读和写
risc-v 则是提供了 load-reserved/store-conditional 的操作. 注意到一次原子操作可以拆解成load-exec-store三个步骤, risc-v 认为只有 load/store 是重要的. 每次 load 完都将对内存地址打上标记, 所有修改/访问了改地址的操作都将清除标记. 若 store 时标记仍然留着(说明没有别的操作修改过这个地址) 那么直接修改, 否则重新load-exec-store
关中断
对于单线程系统而言, 只需要关掉中断即可终止所有的并发执行流.
然而并非所有中断都可以忽略, 并且长时间关中断将失去中断本身带来的好处(IO性能)
自旋锁
有了原子指令就可以原子地 compare_and_swap()
来实现互斥锁了, 所有没得到锁的线程都将 while(1)
等待(即自旋)
优点是简单, 缺点:
- 浪费 CPU
- 获得锁的线程可能被操作系统休眠(即最trivial的实现中, 操作系统无法感知锁的持有)
这就引入了Scalability的概念, 即我们希望算法的效率能够随着硬件的增加而增加(至少不会减少). 很显然自旋锁的 Scalability 不是太好
睡眠锁
为了让操作系统能感知锁的持有, 可以把锁的两个API换成两个系统调用,
对于不成功的lock()直接睡眠, unlock()
则唤醒等待当前锁的线程.
需要注意操作系统自身需要用自旋锁来保证共享数据结构操作的原子性.
实际上就是把锁集中管理起来.
Futex
先自旋, 再睡眠(我全都要)
条件变量
支持两种操作的抽象数据类型: wait() 和
signal()
可以看成是一个管道(广播), wait()
操作将本线程挂起直至条件变量被广播. signal()
则会向所有等待着该条件变量的线程广播并唤醒
这是一个共享的数据结构, 很显然要锁保护(RTFM)
信号量
支持两种操作的抽象数据类型: P() 和 V()(也叫
wait() 和 signal())
可以看成一个容器, 所有的 wait() 都将先检查是否有空余,
然后进入临界区并占有容器中的一个位置.
当信号量被初始化为 1 时, 这就是一个互斥锁了.
应对并发Bug
防御性措施
多加Assertion
LockOrdering
不同的获取锁的顺序将带来死锁, 可以给锁定一个acquire顺序 但事实上很难实现这一点, 因为很多锁并不是透明可见的...
Lockdep 这样的工具可以观察锁的执行序列来判断是否会出现顺序问题(Debug工具)
读写锁
单纯的一把大锁很难实现高效, 因此考虑如下读写模型:
某个共享区有数据, 有若干线程(读和写)将进入操作共享数据
- 多个读线程在没有写线程时可以同时进入
- 任何时刻, 至多一个写线程可以写
这样可以保证读线程的并行, 但不恰当的处理将导致写线程饥饿
RCU机制
针对单链表, Read-Copy-Update 机制可以实现读和写的并行化, 避免了写线程的饥饿
本质是观察到单链表的插入和删除都只涉及至多一个指针的修改, 那么写线程可以预先写好内容, 然后原子地修改一个指针
这里巧妙之处在于把确认没有其余线程正在访问旧的数据延迟到了这些线程离开单链表.
注意到所有写线程修改之后进入单链表的读线程都将读到新的内容, 因此只需要等待所有在修改之前进入单链表的读线程全部离开单链表时即可回收旧的节点.