📔【操作系统】锁的实现

更多面试题总结请看：🗂【面试题】技术面试题汇总

互斥锁的实现

1. 禁止中断

进入临界区前禁止中断，离开之前恢复中断。这样任何中断都不会发生，包括时钟中断，也就是说 CPU 不会被切换到其他线程。

优点是实现简单。缺点有很多：

1. 给用户禁止中断的权利很危险，如果用户进程死循环，操作系统可能永远无法获取控制权
2. 只适用于单 CPU 的场景，其他 CPU 上运行的线程仍然可以访问临界资源，因为不同 CPU 有自己的时钟中断器
3. 关中断可能造成某些中断信号丢失，比如磁盘读取完成
4. 效率很低，屏蔽中断的指令执行起来比其他指令要慢

因此这种方法只适用于 OS 自己在访问某些数据结构、需要保证原子性的时候。

2. TSL 指令

锁住内存总线，使得当一个进程使用内存时另一个进程不能访问内存，即使是另一个 CPU 也不能访问。这种方法只是弥补了“禁止中断”法在多 CPU 系统下的问题。

3. 自旋锁 Spinlock

用一个忙标志 flag 表示锁是否被占用，当 flag = 0 时表示锁空闲，当一个线程成功将 flag 从 0 变为 1 时，表示该线程获得锁。具体实现上，线程将在 while 循环中尝试通过 TAS（Test And Set）等硬件原子指令获取锁。

TAS 指令和下面的 C 代码作用一样：

int TestAndSet(int *old_ptr, int new) {
  int old = *old_ptr; // fetch old value at old_ptr
  *old_prt = new;     // store `new` into old_ptr
  return old;         // return the old value
}

以下是一个用 TAS 实现的临界区代码示例：

lock = False;  // 共享状态

线程一：                              线程二（完全相同）：
1: while TestAndSet(lock, 1) == 1:   5: while TestAndSet(lock, 1) == 1:
2:   spin-wait, do nothing           6:   spin-wait, do nothing
3: # critical section                7: # critical section
4: lock = False                      8: lock = False

这种持续观察一个变量直到它发生改变的过程叫“自旋”；通过原子操作实现的锁叫自旋锁。除了 Test And Set，还可以用 Compare And Swap、Load-Link And Store-Conditional 等原子指令实现上述自旋锁。

还有一个指令是 Fetch And Add，这个指令的作用是将某个地址的值加一，然后返回该地址的旧值。C 语言表示如下：

int FetchAndAdd(int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

可以用两个共享变量 ticket 和 turn 结合 FetchAndAdd 来实现一个互斥锁：

typedef struct __lock_t {
    int ticket;
    int turn;
} lock_t;

void lock_init(lock_t *lock) {
    lock->ticket = 0;
    lock->turn = 0;
}

void lock(lock_t * lock) {
    int myturn = FetchAndAdd(&lock->ticket);
    while (lock->turn != myturn)
        ; // spin
}

void unlock(lock_t * lock) {
    lock->turn = lock->turn + 1;
}

这条指令和其他指令的重要区别是：它能保证所有线程的调度，不会出现饥饿的情况。一旦某个线程取得了它自己的 ticket，它就一定会在将来某个时刻取得锁并进入临界区，其他指令则没有这种保证。

自旋锁的优点是避免了操作系统重新调度和上下文切换的开销，所以非常有效，操作系统内核经常使用自旋锁。缺点是在单处理器的场景下，如果锁已经被另一个线程持有，那么当前线程在尝试加锁时需要将整个时间片空转完毕。除非发生上下文切换，否则它是不可能获取到锁的。自旋锁可能会导致饥饿（取决于实现）。

因此，自旋锁适用于线程持有锁的时间很短的场景。线程持有锁的时间越长，则持有锁的线程被 OS 调度程序中断的风险越大，其他线程空转浪费时间片的概率也越大。

最后，自旋锁的性能在多处理器的场景下性能要比单处理器更好（假设线程均匀分布在多个 CPU 上）。比如线程 A 在 CPU 1 上，线程 B 在 CPU 2 上。如果线程 A 持有锁并很快释放，那么线程 B 很可能在自旋的时候就能直接获取到这个锁，这样不会浪费整个时钟周期。

4. 互斥锁 Mutex

互斥锁需要操作系统的帮助。当一个线程访问其他线程持有的锁时，会被 OS 调度为阻塞状态（休眠），直到锁被释放后，再唤醒一个休眠的线程。

互斥锁的开销主要体现在线程的重新调度和上下文切换上，获取锁的开销是比较大的。因此 mutex 适用于线程持有锁时间比较长的场景。

如果线程持有锁的时间比较短，使用 mutex 会因为频繁的线程切换而导致效率变差。设想一个极端场景：假设现在有 100 个线程，线程 1 持有锁。此时切换到下一个线程，后者会因为无法获取锁而休眠，这样很有可能线程 2 ～ 100 都陷入休眠。这时又切换回线程 1，线程 1 很快就释放了锁，于是又唤醒一个新的线程。这样一番折腾下来，大部分时间都花在了用户态到内核态的切换（系统调用）、重新调度（移到阻塞队列）和上下文切换（线程切换）上了，还不如使用自旋锁的效率高。

5. 自适应锁 Adaptive Mutex

先执行 spinlock 操作，不断持续尝试获取锁；如果尝试多次还是获取不到，就执行 mutex 操作，让线程进入睡眠。还有的叫法是两阶段锁（Two-Phase Lock）、混合锁（Hybrid Mutex）。

glibc 的 futex 就是用这种机制（linux）。

对比 Mutex 和 Spinlock

	Spinlock	Mutex
机制	不断循环尝试获取锁，需要配合抢占式调度器（能够发生上下文切换）	如果获取不到锁就休眠，直到锁被释放后再唤醒
实现层面	用户进程和操作系统均可实现	操作系统提供系统调用，因为需要调度
适用场景	线程持有锁的时间短	线程持有锁的时间长
缺点	获取不到锁时空转，浪费 CPU	重新调度、上下文切换的开销

选用 spinlock 还是 mutex，就是看「线程不断空转多个时间片，直到获取到锁」和「使线程睡眠 + 唤醒线程 + 相关系统调用」哪个开销更小。

🗂 技术面试题汇总

---

参考资料：

• 浅谈 Mutex (Lock)
• Spinlock - Wikipedia