Lecture 11. 互斥锁问题（22 页）

线程虽然可以快速高效率的创建以实现并行，但是各个线程之间需要做好协调，尤其是资源的分配。

互斥锁问题（mutual exclusion problem） 是指：有可能在一个系统当中，有一个资源只能同时被一个线程使用，而每个线程都需要使用这个资源才能完成整个系统的任务。这就要做好分配。就比方说，两个火车都要经过一段特别窄的重合的铁轨（这段路是一个山洞），才能走到各自的终点：

然而火车司机是不能预知另外一辆货车在哪里的，所以需要外部（管理局、操作系统）的规划。

火车司机问题 Andes Train Problem

https://www.uio.no/studier/emner/matnat/ifi/INF5510/v16/lecture-f1/andes-trains.pdf

最初方案：用小石头

在入口放一个碗。
司机进入山洞之前，必须先检查一下，碗里有没有小石头。
- 如果没有石头，就找个小石头扔碗里，然后进山。
  - 火车开到出口之后，下车回到入口把石头扔掉，然后再走回去继续开车
- 如果有石头，就停下来小憩（siesta），直到石头没了，再开进去

但是这个方案问题很大！

有一辆车可能永远都进不去，比如如果先进去的那个忘了回去扔石头？？？？？？
而且还会导致撞车（为啥？？？）

对应到代码，相当于，两个司机都是：

int flag = 0; // 初始，空的碗，两个线程共享这个变量
while (flag) { /* wait */ }
flag = 1;
// 进山
// 出山
flag = 0;

第二版方案：修改石头规则

A 司机，必须是碗里没石头才进去。到出口停下，再走回入口放一块小石头进去。
B 司机，必须是碗里有石头才进去。到出口停下，再走回入口扔掉那个石头。

由于两个司机都会提前减速，这样在出口的位置，就不会撞车了！（为啥？？？？）

但是还是有问题！B 本来想一天跑两趟，A 想要一天跑一趟。但是依据这个原则，必须等 A 跑完两趟，B 才能跑第二趟。所以 B 很不满意！

对应到代码，相当于：

int turn = 0;

void Driver1() {
  while (turn == 0) { /* wait */ }
  // 进山
  // 出山
  turn = 0;
}

void Driver2() {
  while (turn == 1) { /* wait */ }
  // 进山
  // 出山
  turn = 1;
}

第三版方案：用两个碗

两个碗分别表示 A 和 B 想要进山洞。

司机到山洞口，往自己的碗里扔石头，表示自己想要过去，同时检查另一个碗有没有石头
- 如果没有，那就进山，到出口减速，回来拿走石头
- 如果有，那就等着让另一个人先过。然后睡觉，睡醒再扔进去石头，循环

然后死锁了：两个人同时来到了山洞洞口，都特别谦让，想让另外一个人先过。于是两个司机谁都过不去了。

对应到代码相当于：

bool flags = {false, false};

void Driver1() {
  flag[0] = true;
  while (flag[1]) { /* wait */ }
  // 进山
  // 出山
  flag[0] = false;
}

void Driver2() {
  flag[1] = true;
  while (flag[0]) { /* wait */ }
  // 进山
  // 出山
  flag[1] = false;
}

第四版方案：再改成一个碗

只有一个碗，碗里初始状态有一个石头。
如果司机要过山，那就把石头扔掉；到出口再回来放进去石头
- 如果没石头，就等

这个方案解决了之前的问题。但是这跟第一版啥区别？？？？？？

不过这个方法在实际中可行，在软件中不可行。因为在实际中石头只能同时被一个人操作，但是在软件中，两个线程都可以操作石头。

对应代码相当于，两个司机都是：

int flag = 1;
while (!flag) { /* wait */ }
flag = 0;
// 进山
// 出山
flag = 1;