操作系统(四) - 旧游无处不堪寻

前面几篇我们介绍了 CPU 的虚拟化和内存的虚拟化，本篇我们在来介绍一下操作系统中另一个重要的部分 —— 并发。

并发术语

竞态条件(race condition)是指出现在多个执行线程大致同时进入临界区，执行线程试图更新共享的数据结构，导致了错误结果。

多个线程可能导致竞争状态的代码片段称为临界区(critical section)。临界区是访问共享变量(共享资源)的代码片段。

为了避免多线程访问共享变量产生的问题，需要硬件提供一些有用的指令，可以在这些指令上构建一个通用的集合，即所谓的同步原语(synchronization primitive)。通过使用这些硬件同步原语，加上操作系统的帮助，就可以以同步和受控的方式访问临界区，从而可靠地产生正确的结果。

将一系列动作原子化(atomic)背后的想法可以简单用一个短语表达: 全部或没有。即要么组合在一起的所有活动都发生了，要么都没有发生，不会看到中间状态。有时，将许多行为组合为单个原子动作称为事务(transaction)。

锁(Lock)

并发编程的一个最基本问题: 我们希望原子式执行一系列指令，但由于单处理器上的中断(或者多个线程在多处理器上并发执行)，无法做到，因此产生锁这一概念来解决本问题。在临界区周围的代码中加锁，保证临界区能够像单条原子指令一样执行。我们需要注意，不要再临界区都使用同一个大锁(粗粒度的锁策略)，通常会用不同的锁保护不同的数据和结构，从而允许更多的线程进入临界区，增加并发能力。

锁的实现

我们需要硬件和操作系统的支持来实现一个可用的锁。各种计算机体系结构的指令集都增加了一些不同的硬件原语，同时操作系统经过发展完善，也实现成熟复杂的锁库。

test-and-set

我们可以通过硬件支持的 test-and-set 来实现可用的自旋锁，这是最简单的一种锁。

typedef struct __lock_t {
  int flag;
} lock_t;

void init(lock_t *lock) {
  // 0: lock is available, 1: lock is held
  lock->flag = 0;
}

void lock(lock_t *lock) {
  while (TestAndSet(&lock->flag, 1) == 1)
    ; // spin-wait (do nothing)
}

void unlock(lock_t *lock) {
  lock->flag = 0;
}

队列

基于硬件的锁简单而且有效，但是，这些解决方案在某些场景下的自旋会效率低下。如何让锁不会不必要地自旋，浪费 CPU 时间，只有硬件支持是不够的，我们还需要操作系统支持。

Linux 提供了 futex，每个 futex 都关联一个特定的物理内存位置，也有一个事先建好的内核队列。调用者通过 futex 调用来睡眠或者唤醒。调用 futex_wait(address, expected) 时，如果 address 处的值等于 expected，就会让调线程睡眠。否则，调用立刻返回。调用 futex_wake(address) 唤醒等待队列中的一个线程。

两阶段锁

两阶段锁意识到自旋可能很有用，尤其是在很快就要释放锁的场景。因此，两阶段锁的第一阶段会先自旋一段时间，希望它可以获取锁。但是，如果第一个自旋阶段没有获得锁，第二阶段调用者会睡眠，直到锁可用。Linux 锁就是这种锁，不过只自旋一次，更常见的方式是在循环中自旋固定的次数，然后使用 futex 睡眠。