[操作系统]7. 并发控制：互斥

[supergem3000]

7. 并发控制：互斥 (jyywiki.cn)

互斥问题：定义与假设

互斥（mutual exclusion），互相排斥，实现一个数据结构lock_t和lock/unlock API。 一把 “排他性” 的锁：

• 如果某个线程持有锁，则其他线程的 lock 不能返回 (Safety)
• 在多个线程执行 lock 时，至少有一个可以返回 (Liveness)
• 能正确处理处理器乱序、宽松内存模型和编译优化（额外要注意的点） 实现互斥的基本假设：允许使用不管一切麻烦事的原子指令。
• 包含一个原子指令。指令的执行不能被打断。
• 包含一个compiler barrier。无论何种优化都不可越过此函数。
• 包含一个memory fence。保证处理器在stop-the-world前所有对内存的store都生效，即对resume-the-world之后的load可见。 联想：并发编程三大特性，原子性、有序性、可见性。

  自旋锁：用xchg实现互斥

  xchg: exchange，瞬间将两个值交换

在厕所门口放一个桌子（共享变量），初始放着🔑。 自旋锁（Spin Lock）：

• 想上厕所的同学（一条xchg指令）：把自己手里的东西和桌子上的东西交换。如果拿到🔑则进入厕所，否则重复。
• 出厕所的同学：把🔑放到桌上。

  
  int table = YES;

void lock() { retry: int got = xchg(&table, NOPE); if (got == NOPE) goto retry; assert(got == YES); }

void unlock() { xchg(&table, YES); }

> 1. 如果释放锁之前线程crash了，或者自己写的代码在中间return了没释放，会怎样？死锁。有什么避免方式吗？举例：对象初始化获取锁，析构时释放锁。[c++经验之谈一：RAII原理介绍 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/34660259#%E4%BB%80%E4%B9%88%E6%98%AFraii)
> 2. unlock为什么不是`table = YES`？要保证在任何编译优化、任何内存模型都正确，exchange最安全。在x86中`table = YES`应该是正确的。
# 在操作系统上实现互斥
自旋锁的缺陷：
- 性能问题1：除了进入临界区的线程，其他处理器上的线程都在空转。
- 性能问题2：持有自旋锁的线程可能被操作系统切换出去，实现100%的资源浪费。（操作系统不感知线程在做什么）

Scalability（可伸缩性）：性能的新维度。
> 同一份计算任务，时间和空间会随处理器数量的增长而变化。

自旋锁的使用场景：
- 临界区几乎不”拥堵“
- 持有自旋锁时禁止执行流切换。
具体场景：操作系统内核的并发数据结果（短临界区）。几乎是唯一使用场景。

线程+长临界区的互斥：
得不到锁时希望把资源”让“出去，不浪费CPU。”让“操作不是C语言程序可以做到的，但可以通过系统调用，让操作系统做这些事情。
- `syscall(SYSCALL_lock, &lock)`：试图获得lock，如果失败，就切换到其他线程。
- `syscall(SYSCALL_unlock, &lock)`：释放lock，如果有等待锁的线程就唤醒。
此时操作系统等于管理员，操作系统使用自旋锁确保自己交出lock的过程是原子的。

# 关于互斥的一些分析
自旋锁 (线程直接共享 locked)
- 更快的 fast path：xchg 成功 → 立即进入临界区，开销很小
- 更慢的 slow path：xchg 失败 → 浪费 CPU 自旋等待
互斥锁 (通过系统调用访问 locked)
- 更经济的 slow path：上锁失败线程不再占用 CPU
- 更慢的 fast path：即便上锁成功也需要进出内核 (syscall)
> 今天操作系统锁的实现，还有其他优化。使得锁在在不拥堵的时候，上锁不需要进入操作系统内核，上锁失败时才进入内核。