<aside> 📖 实现互斥的根本困难：不能同时读/写共享内存

• load (环顾四周) 的时候不能写，只能 “看一眼就把眼睛闭上”
  • 看到的东西马上就过时了
• store (改变物理世界状态) 的时候不能读，只能 “闭着眼睛动手”
  • 也不知道把什么改成了什么 </aside>

1. 自旋锁 Spin Lock

解决问题的两种方法：

1. 提出算法、解决问题 (Dekker/Peterson/...'s Protocols)
2. 改变假设 (软件不够，硬件来凑)

假设硬件能为我们提供一条 “瞬间完成” 的读 + 写指令。

• 请所有人闭上眼睛，看一眼 (load)，然后贴上标签 (store)
  • 如果多人同时请求，硬件选出一个 “胜者”
  • “败者” 要等 “胜者” 完成后才能继续执行

X86 原子操作：LOCK 指令前缀

Atomic exchange (load + store)

int xchg(volatile int *addr, int newval) {
  int result;
  asm volatile ("lock xchg %0, %1"
    : "+m"(*addr), "=a"(result) : "1"(newval));
  return result;
}

在此基础上，我们就可以实现自旋锁：

int locked = 0;
void lock() { while (xchg(&locked, 1)) ; }
void unlock() { xchg(&locked, 0); }

原子指令

原子指令的模型：

• 保证之前的 store 都写入内存
• 保证 load/store 不与原子指令乱序

现代的实现一般在 L1 cache 层保持一致性 (ring/mesh bus)

• 相当于每个 cache line 有分别的锁

• store(x) 进入 L1 缓存即保证对其他处理器可见

  但要小心 store buffer 和乱序执行

最早的原子指令：80486 的 Bus Lock

Load-Reserved/Store-Conditional (LR/SC)

常见原子操作的本质都是 load ⇒ exec ⇒ store 的序列

RISC-V 的实现方法：

• LR: 在内存上标记 reserved (盯上你了)，中断、其他处理器写入都会导致标记消除
• SC: 如果 “盯上” 未被解除，则写入

用 LR/SC 实现 CAS：