Mutual Exclusion

阿姆达尔定律¶

阿姆达尔定律（Amdahl's Law）：并行系统的加速比受限于其串行部分。
公式： \(S = \frac{1}{(1 - P) + \frac{P}{N}}\)
- \(S\)：加速比
- \(P\)：可并行化的程序部分比例
- \(N\)：处理器数量
公式理解：当 \(N\) 趋近于无穷大时，最大加速比为 \(\frac{1}{1 - P}\)。

Quiz¶

假设你的程序中 90% 的部分可以完美并行化。

使用 10 个处理器时，理论上的最大加速比是多少？
如果你想达到 5 倍的加速比，至少需要多少个处理器？
如果并行部分也有 10% 的额外同步开销，公式会如何变化？

互斥¶

概念¶

条件竞争（race condition）：多个线程同时访问共享资源，导致结果不可预测。
互斥（mutual exclusion）：多个线程在同一时间只能有一个访问共享资源。
临界区（critical section）：访问共享资源的代码片段。
死锁（deadlock）：多个线程互相等待对方释放资源。
饥饿（starvation）：某个线程长时间无法获得资源。

互斥的三个属性¶

Safety
- 定义：任一时刻，只有一个线程可以进入临界区。
- 本质：坏事永远不发生。
Liveness (Deadlock-free)
- 定义：如果有线程想进入临界区，最终总有一个线程能进入。
- 本质：好事总会发生。
Fairness (Starvation-free)
- 定义：如果有线程想进入临界区，这个线程最终一定能进入。
- 说明：无饥饿 ⇒ 无死锁；反之不成立。

Quiz¶

有 5 位哲学家，他们的一生都在思考和吃饭中度过。他们围坐在一张圆桌旁，桌子中间有一大盘米饭。然而，桌上只有 5 根筷子，摆放在每位哲学家之间。哲学家平时在思考。当一位哲学家饿了时，他会坐下来，试图拿起离他最近的两根筷子（左手一根，右手一根）。只有当他同时拿到两根筷子时，才能开始吃饭。吃完后，他放下筷子，继续思考。

请说明这个问题中存在哪些共享资源和临界区。
如果每位哲学家都先拿起左手边的筷子，会发生什么情况？这是否满足互斥的三个属性？
思考：如何设计一个解决哲学家就餐问题的算法，以避免死锁和饥饿？

双线程互斥算法¶

我们假设线程 ID 为 0 和 1。当前线程为 i，对方为 j = 1-i。

LockOne¶

// Thread i's code
public void lock() {
  flag[i] = true;       // 举手 (I'm interested)
  while (flag[j]) {}    // 等待 (Wait if the other is interested)
}
public void unlock() {
  flag[i] = false;      // 放下手
}

缺陷：满足 Safety，但不满足 Liveness 和 Fairness。如果两人同时举手，都在等对方放下，导致死锁。

LockTwo¶

// Thread i's code
public void lock() {
  victim = i;           // 谦让 (I'll wait)
  while (victim == i){} // 等待 (Wait if the other is the victim)
}
public void unlock() {
  // 什么都不做
}

缺陷：满足 Safety，但不满足 Liveness 和 Fairness。如果只有一个线程，它会自己把自己锁住，等待一个不存在的线程来修改 victim，导致死锁。

Peterson's Algorithm¶

// Thread i's code
public void lock() {
  flag[i] = true;       // Step 1: 举手 (I'm interested)
  victim = i;           // Step 2: 谦让 (I'll wait if necessary)

  // 只有当两个条件同时满足时，我才等待：
  // 1. flag[j] == true: 对方也想进
  // 2. victim == i:     我是那个最后进门导致冲突的“倒霉蛋”
  while (flag[j] && victim == i) {};
}
public void unlock() {
  flag[i] = false;      // 放下手
}

证明：反证法。如果 A 进去了，说明要么 flag[B] 是 false（B 不感兴趣），要么 victim 是 B（B 后让步了）。

Quiz¶

在 LockOne 算法中，如果我们将 flag[i] = true 移到 while 循环之后，会违反什么属性？
如果两个线程几乎同时执行 Peterson 算法的 lock()，谁会进入临界区？