【NJU OS】05 并发控制：互斥

共享内存上的互斥

在共享内存上实现互斥

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

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

自旋锁(Spin Lock)

x86 原子操作：LOCK 指令前缀

用 xchg 实现互斥

实现互斥：自旋锁

• 并发编程：千万小心
  • 做详尽的测试
  • 尽可能地证明 (model-checker.py 和 spinlock.py)
• 原子指令的模型
  • 保证之前的 store 都写入内存
  • 保证 load/store 不与原子指令乱序

原子指令的诞生：Bus Lock (80486)

Lock 指令的现代实现

在 L1 cache 层保持一致性 (ring/mesh bus)

• 相当于每个 cache line 有分别的锁
• store(x) 进入 L1 缓存即保证对其他处理器可见
  • 但要小心 store buffer 和乱序执行

L1 cache line 根据状态进行协调

• M (Modified), 脏值
• E (Exclusive), 独占访问
• S (Shared), 只读共享
• I (Invalid), 不拥有 cache line

互斥锁 (Mutex Lock)

自旋锁的缺陷

性能问题 (0)

• 自旋 (共享变量) 会触发处理器间的缓存同步，延迟增加

性能问题 (1)

• 除了进入临界区的线程，其他处理器上的线程都在空转
• 争抢锁的处理器越多，利用率越低

性能问题 (2)

• 获得自旋锁的线程可能被操作系统切换出去
  • 操作系统不 “感知” 线程在做什么
  • (但为什么不能呢？)
• 实现 100% 的资源浪费

自旋锁的使用场景

• 临界区几乎不 “拥堵”
• 持有自旋锁时禁止执行流切换

使用场景：操作系统内核的并发数据结构 (短临界区)

• 操作系统可以关闭中断和抢占
  • 保证锁的持有者在很短的时间内可以释放锁
• (如果是虚拟机呢…😂)
  • PAUSE 指令会触发 VM Exit
• 但依旧很难做好

实现线程 + 长临界区的互斥

“让” 不是 C 语言代码可以做到的 (C 代码只能计算)

把锁的实现放到操作系统里就好啦！

• syscall(SYSCALL_lock, &lk);
  • 试图获得 lk，但如果失败，就切换到其他线程
• syscall(SYSCALL_unlock, &lk);
  • 释放 lk，如果有等待锁的线程就唤醒

Futex = Spin + Mutex

Futex: Fast Userspace muTexes

• Fast path: 一条原子指令，上锁成功立即返回
• Slow path: 上锁失败，执行系统调用睡眠
  • 性能优化的最常见技巧
    • 看 average (frequent) case 而不是 worst case

总结

• 软件不够，硬件来凑 (自旋锁)
• 用户不够，内核来凑 (互斥锁)
  • 找到你依赖的假设，并大胆地打破它
• Fast/slow paths: 性能优化的重要途径