并发问题与同步

多线程带来了并发问题。

一个经典的并发问题例子

全局变量 $x=10$，两个线程均令 $x$ 自增。

Thread 1

func increment() {
    global x
    x++
}

Thread 2

func increment() {
    global x
    x++
}

$x$ 可能是 11 或 12。

「自增」不是原子操作 (atomic operation)，它实际上由三个操作组成。
- mov x, tmp
- add $0x1, tmp
- mov tmp, x
不可控的线程调度 (uncontrolled scheduling)
线程共享地址空间，包括数据段中的全局变量 $x$

以上的例子就是一个典型的竞态条件 (race condition)：执行结果依赖于不可控的事件出现顺序，即竞争 (race)。在多线程进程中，当多个线程并发地访问或修改一个共享资源时，往往就会有竞态条件。

含有竞态条件的程序被称为不明确程序 (indeterminate program)，它的输出是不确定的。

因此，访问或修改特定共享资源的代码块，即关键区 (critical section)，必须被保护起来。

All or Nothing!

解决方法之一：将自增操作原子化 (transaction)，使其不能在中途被中断。

解决方法之二：关键区必须被互斥 (mutual exclusion) 访问，即同一时刻最多只能有一个线程进入关键区。进入之后，关键区将被该线程「锁住」，其他线程需要等待。

这也被称为串行访问 (serialized access)。

互斥本质上是一种同步 (synchronization) 机制：一个线程可能需要等待另一个线程完成某个任务后才能继续执行。OS 和硬件如何为同步提供支持？

接下来将会介绍三种同步原语 (synchronization primitives)：互斥锁，条件变量与信号标。