锁 | 海音的日程档案

锁的基本思想
- 锁(Lock) 是一个变量，具有类型，使用时需要声明某种类型的锁变量(Lock variable)
- 这个锁变量（简称锁）会保存自己当前的状态：
  - 它的状态可以是可用的(available/unlocked/free)，就代表没有线程持有锁
  - 它的状态可以是被占用的(acquired/locked/held)，表示有一个线程持有锁，正处于临界区
  - 它也可以存储其他的信息，例如现在是哪个线程持有它、请求锁的线程队列等
- 锁拥有两个主要接口：lock() 和unlock()
  - lock()
    - 线程调用lock()会尝试获取锁
    - 当没有其他线程持有锁（锁是可用的） 时，那么该线程会获得锁，进入临界区，此时该线程被称为锁的持有者(Owner)
    - 若锁被另一线程持有，该调用就不会返回
  - unlock()
    - 锁的持有者调用unlock()后，锁就被释放了
    - 若等待队列中有别的线程，那么这个线程会收到通知，可能会接手锁
    - 如果等待队列中没有别的线程，锁就变为可用的
- 锁为程序员提供了最小程度的调度控制，让除了操作系统之外，程序员也可以拥有一些控制权
Pthread锁
- POSIX库将锁称为互斥锁(Mutex)，用于提供线程之间的互斥
评价锁
- 评价锁有两个标准：
  - 能否提供互斥(mutual exclusion)，阻止多个线程进入临界区
  - 是否具有公平性(fairness)，当锁可用时，是否每个竞争线程都有公平的机会抢到锁，避免有竞争该锁的线程遭受饥饿(starve)
  - 性能(performance) 如何，即使用锁需要增加的时间开销
控制中断
- 一个比较简单的实现锁的方式，就是在临界区关闭中断，这是为单处理器系统开发的解决方案
- 它的问题也很多
  - 一个贪婪的程序可能会从一开始就调用lock()，这样就可以独占处理器
  - 不支持多处理器，一个处理器的中断是关闭了，如果另一个处理器上的线程想要访问临界区呢
  - 关闭中断导致中断丢失，假设磁盘完成了某个操作，操作系统却因为不能中断而错失这一消息，那OS应该如何唤醒等待读取的进程
  - 效率低，这种方法在硬件上效率太低了
自旋锁
- 当一个线程处于临界区时，另一个线程调用lock()，就会一直等待锁，也就是自旋等待(spin-wait)，直到锁被释放
- 若中断发生的时机不好，会导致两个线程都将锁的状态置1（占有）
- 由于等待的线程会一直自旋，所以在下一次上下文切换发生前的这段时间会被浪费掉
- 我们需要硬件支持才能实现可用的自旋锁(Spin lock)
测试并设置指令（原子交换）
- 测试并设置指令(TAS, Test-and-Set) 是一个硬件原语。它主要用于解决多线程/多处理器环境下的互斥问题（防止多个进程同时修改同一数据）。TAS是一个原子操作，TAS也被称为原子交换(atomic exchange)
- TAS会原子地执行以下两个操作：
  1. 获取锁的状态
  2. 更新锁的状态
- 通过这样一个合并成的原子操作，就可以测试旧值，同时赋予新值，这可以让自旋锁拥有正确性，在多CPU系统上性能不错，但不保证公平性
比较并交换
- 比较并交换(CAE, Compare-and-Exchange，或CAS, Compare-and-Swap) 是另一个硬件原语
- CAE会原子地执行以下两个操作：
  1. 检查锁的状态与自己预期的锁的状态是否相同
  2. 若相同，则更新锁的状态，否则什么都不做
- CAE实际上更优于TAS，这与无等待同步(wait-free synchronization) 相关

锁的基本思想

lock()

unlock()

Pthread锁

评价锁

控制中断

自旋锁

测试并设置指令（原子交换）

比较并交换