经典互斥问题：面包店算法

经典互斥问题：面包店算法

介绍

面包店算法是在多线程环境下无锁的互斥算法，能够保证在多线程的环境下，临界区同时至多只有一个线程进入。虽然算法回看起来并不难，但却是图灵奖得主 Lamport 最骄傲的成果之一。

面包店算法要解决的本质是一个互斥问题，其是由 Dijkstra 提出的，另一个图灵奖得主。在计算机发展过程中，有相当多人尝试解决互斥问题。所以我们先要搞清楚什么是互斥问题，为什么这个问题难以解决，以及怎么解决，了解这个算法的本质问题，才能帮我们更好地学习该算法，而不是知道仅仅知道算法的流程而已。

本文不区分线程和进程的概念，在并发编程中，线程之间和进程之间的竞争关系本质上是一样的

互斥问题

互斥问题说来也简单，多个线程如何保证同时只有一个线程进入互斥区执行代码，这是一个保证并发编程有序可控的根本问题。一个资源只有一个线程一个线程有序地占有，才能保证代码行为是可预期和可控的，如果胡乱占有资源和执行代码，显而易见结果就会乱套。

所以互斥问题（Mutual exlusion），也叫 Dijkstra’s concurrent programming problem 有以下几个要求：

任何时间至多有一个线程进入互斥区（忙则等待原则）
每个线程最后都会进入互斥区（有限等待原则）
每个线程最后都能停在非互斥区（空闲让进原则）
不能对每个线程的占有时间做任何假设

为什么互斥问题难？

对于互斥问题，一定有一个最小原子性的前提，否则无法讨论互斥。原子性代表一个操作是不可分割的，要么全部执行成功，要么全部不执行。

假设在单核的环境中，最小的原子性是每条指令，在指令执行过程中是不会被中断的，所以每条指令是原子的，不会出现一个指令执行一半之后去执行另一个指令。（这里的指令指的是 CPU 指令集中的指令，而不是程序指令，一条 high-level 的程序指令可能被拆分成多个 CPU 指令）

一个并发编程最简单的示例就是并发累加，多个线程对同一个变量执行 i += 1 的程序指令，但最后结果可能出人意料。

一个简单的示例代码如下：其主要内容为创建 10000 个线程，每个对全局变量 number 执行 10000 次自加加法

#include <thread>
#include <vector>
#include <iostream>

using namespace std;

int number = 0;

void add() {
    for(int i = 0; i < 10000; i++) {
        number += 1;
    }
}

int main() {
    vector<thread*> threads;
    for(int i = 0; i < 10000; i++) {
        thread* th = new thread(add);
        threads.push_back(th);
    }

    for(auto th : threads) {
        th->join();
    }
    // result: 100000000? Probably not
    cout << number << endl;

    return 0;
}

这是因为 i += 1 的操作并不是原子的，在执行该操作时，程序指令会被拆分成多个 CPU 指令，在多个线程交错执行 CPU 指令时，结果就可能产生错误。（错误产生具有随机性，对于加法这种简单操作，通常要有比较大的并发量才有较大概率看到）

假如加法的原子性都不能保证，就很难设计出一个方法，能够保证同时只有一个线程在操作数据。而这只是在单核 CPU 的环境下，在多核 CPU 的环境下，还引入了缓存一致性等更复杂的问题，就需要更底层的硬件来支持原子性，但是本文只从软件的层面讨论。

除此之外，并发编程还有以下几个难点：

进程或线程执行时间不确定，程序存在随机性，调试和正确性保证存在困难
当互斥条件复杂时，死锁就很容易出现
同步和调度，当执行命令之间存在依赖性，例如 A 必须先于 B 执行，对并发编程进行同步语义保证也存在困难

Dijkstra 的解法

该算法默认数组赋值和读取之间原子性的，也就是说读取数组某一个元素，不会读到只写了一半的数据。由于标志位的位长度小于一个寄存器长度，所以该原子性是得到保证的。

Dijkstra 通过两个标志数组来实现互斥访问，其主要流程是：

当进程 $i$ 希望进入临界区时，会设置其互斥区状态，让其他线程可见。
并开始检查当前或上一个在互斥区的线程号是哪个
1. 如果是自己，则进行最后的竞争检查，满足则进入互斥区，不满足则重新重新检查上一个互斥区的线程号是谁
2. 如果不是自己，则设置竞争标志，并等待其他线程退出互斥区。如果等待的线程退出了互斥区，则将上一个进入互斥区的线程号设为自己，再进行最后的检查

该算法可以用 C 语言表达如下：N 代表线程数

// k 表示当前或上一个在互斥区执行代码的线程号
// 所以竞争条件只可能发生在 i 和 k 之间，将多个线程之间的竞争简化为两个
int k = 0;
bool not_in_critical_section[N] = {true};
bool race_flag[N] = {false};

void race(int i) {
	// 线程 i 尝试进入互斥区，将互斥区 flag 置为 false
	not_in_critical_section[i] = false;
	bool waiting = true;
	while(waiting) {
		if(k != i) {// 当前或上一个在互斥区的线程号不是自己
			do {
				// 将竞争 flag 设为 false，因为有可能从 else 分支再回来
				race_flag[i] = false;
				if(not_in_critical_section[k]) {
					// 代表 k 已经退出互斥区，线程 i 可以*尝试*进入互斥区
					k = i;
				}
			} while(k != i);
		} else { // 线程 i 尝试进入互斥区
			race_flag[i] = true; // 设为竞争状态，进行最后的检查
            bool race_condition = false;
			for (int j = 0; j < N; j++){
				// 只有线程 i 的 race_flag 是 true 才代表可以进入互斥区
				// 代表此时不存在竞争问题
				if (j != i && race_flag[j]){
                    race_condition = true;
					break;
				}
			}
            if(!race_condition) {
                waiting = false; // 可以进入临界区
            }
		}
	}
	// 临界区开始
	// ...
	// 临界区结束
	race_flag[i] = false;
	not_in_critical_section[i] = true;
}

初步理解有可能存在困难，我们可以进行反推来理解这个代码。

我们已知能够进入互斥区的唯一条件是将 waiting 设置为 false，而该操作必须满足前提 k == i，否则无法进入该分支。那么我们可以考虑，要使 k == i，则必须满足线程 $k$ 已经退出互斥区，然后将 $k$ 设为自身。在并发情况下，就有可能让多个线程都进入到 else 分支中，将 waiting 设为 false，例如两个线程同时进行 not_in_critical_section[k] 的判断，且同时通过了，然后依次将 $k$ 设为自身，并进入 else 条件，将 waiting 设为 false，此时这两个线程就会一起进入互斥区，从而不满足互斥的要求。

所以需要第二个标志来判断，当前有几个线程尝试进入互斥区，是否可能存在竞争。所以引入了 race_flag 数组，该数组默认为 false，设为 true 代表已经通过互斥检查，并且准备进入互斥区，只有发现只有一个线程准备进入互斥区时，才会允许进入，否则仍然拒绝，返回到互斥检查。

由于同时出现通过互斥检查并准备进入互斥区的概率很小，所以引入该标志，也不会带来多大的性能问题。

Knuth 的优化

Knuth 提到 Dijkstra 的算法有可能存在 Starvation 问题，也就是有可能存在一个线程一直进不到互斥区。假设存在两个线程 $i$ 和 $j$ ，线程 $i$ 从检查互斥条件、进入互斥区、离开互斥区、再进入互斥条件检查的这个循环时间 $L_i$ ，有可能刚好等于线程 $j$ 检查互斥条件的时间。

换句话说，线程 $i$ 不断进入互斥区，将 $k$ 设为 $i$ ，并且 not_in_critical_section[i] 在绝大部分的时间都为 false，在那极少为 true 的时间里，刚好线程 $j$ 又错开了，导致线程 $j$ 无法将 $k$ 设为 $j$ 进入不了互斥区。

但是产生这种 Starvation 的条件比较苛刻，相同的时间，显然线程 $i$ 占有的 CPU 时间片更多，因为执行了更多的指令，这说明该系统的线程调度存在一些其他机制，使得线程 $i$ 的优先级更高，可以占有更多的时间片。

但是这种情况在现代通用计算机中出现概率很小，大部分线程/进程调用方案通常不会导致这样的问题，所以这种问题只可能发生在高度定制化的系统之中。但是如何解决 Starvation 问题也值得看一看。

// k 表示所要进行竞争的线程号
// 竞争条件只发生在 i 和 k 之间，将多个线程之间的竞争简化为两个
int k = 0;
int control[N] = {0};

void race(int i) {
	// 线程 i 尝试进入互斥区
	bool race_condition = true;
	while(race_condition) {
		bool mutual_exclusion_check = true;
		// 将自身状态设为 1
		control[i] = 1;
		while(mutual_exclusion_check) {
			// 检查其他线程状态
			int startIdx = k;
			for (int j = N - 1; j >= 0; j--) {
				// 从 k 开始往前数
				int idx = (startIdx + j) % N;
				if(idx == i) {
					mutual_exclusion_check = false;
					break;
				}
				if(control[idx] != 0) {
					break;
				}
			}
		}
		// 将自身状态设为 2
		control[i] = 2;
		bool race_flag = true;
		// 检查是否有竞争，只有线程 i 的状态处于 2 才允许进入互斥区
		for(int j = 0; j < N; j++) {
			if (j != i && control[j] == 2) {
				race_flag = false;
				break;
			}
		}
		if(race_flag) {
			race_condition = false;
		}
	}
	k = i;
	// 互斥区开始
	// ...
	// 互斥区结束

	// 将 k 偏移一位
	if(i == 0) {
		k = N - 1;
	} else {
		k = i - 1;
	}
	
	control[i] = 0;
}

Knuth 的算法，实际上大体上和 Dijkstra 的算法差不多，基本逻辑基本一致，只不过标志位的方法不一样，Knuth 的算法使用数字来标记，而 Dijkstra 用两个 bool 数组来标志，本质上是一样的。

相比 Dijkstra 不一样的是其对 k 的赋值，在 Dijkstra 的算法中，仅仅是将 k = i，相当于各个线程是抢占式的，有可能导致饥饿问题。举个例子是线程 $i$ 进入互斥区之后，如果马上再抢占，是不用再去检查互斥条件的（等待线程 $k$ 退出互斥区），因为 k == i，可以直接进入 else 条件。

而 Knuth 的算法，k 的赋值是偏移的，也就是说在当前线程执行完毕后，会主动将进入互斥区的机会交给别人，自己再进行抢占仍然需要等待互斥条件满足。

Knuth 为了做到这一点，首先是对 k 的赋值进行了偏移，其次是对互斥条件的检查进行了优先级设定。首先观察 k 的偏移方式，k 是递减的，也就是说，优先级是转移给线程号更低的线程。在 k 递减过程中，会形成一个环，互斥条件检查的遍历有一些特殊，实际上就是为了在 k 形成的环中遍历。

该代码循环嵌套有点多，可以进行抽离简化，如下：

int k = 0;
int control[N] = {0};

bool check_mutual_exclusion(int i) {
	int startIdx = k;
	for (int j = N - 1; j >= 0; j--) {
		// 从 k 开始往前数
		int idx = (startIdx + j) % N;
		if(idx == i) {
			return true;
		}
		if(control[idx] != 0) {
			break;
		}
	}
	return false;
}

bool check_race(int i) {
	for(int j = 0; j < N; j++) {
		if (j != i && control[j] == 2) {
			return true;
		}
	}
	return false;
}

void race(int i) {
	// 线程 i 尝试进入互斥区
	bool race_condition = true;
	while(race_condition) {
		// 将自身状态设为 1
		control[i] = 1;
		// 检查互斥条件
		while(check_mutual_exclusion(i));
		// 将自身状态设为 2
		control[i] = 2;
		// 检查是否有竞争
		if(check_race(i)) {
			race_condition = false;
		}
	}
	k = i;
	// 互斥区开始
	// ...
	// 互斥区结束

	// 将 k 偏移一位
	if(i == 0) {
		k = N - 1;
	} else {
		k = i - 1;
	}
	control[i] = 0;
}

最后解释一下为什么是这样检查互斥条件，假设有线程 $i, j; i<j<k$ ，假如线程 $j$ 先进行互斥条件检查，那么线程 $i$ 必须等待线程 $j$ 拿到执行权，进入互斥区退出之后才可能进入互斥区。因为线程 $j$ 检查互斥条件是从 $k$ 往前遍历，是递减的，所以如果 control[j] == 1，线程 $i$ 一定会遍历到 $j$ ，从而不满足条件。

检查竞争仍然和 Dijkstra 一样，有可能存在这样一个顺序，导致两个线程进入互斥区。假设线程 $i$ 先进行互斥条件检查（此时线程 $j$ 还没进入，所以 control[j] == 0），那么线程 $i$ 自然满足条件，可以通过互斥检查，此时线程 $j$ 进入，因为 $i<j$ ，所以在检查过程中，还没遇到 control[i] == 1，就已经满足 idx == i 的判断，从而进入互斥区。

综上，所以需要进行两次检查。

面包店算法 Bakery Algorithm

了解基本的互斥算法之后，就来到杀手锏级别的算法了。

Bakery Algorithm 相比上述算法来说非常简单，仿佛是天然就存在的一个算法，而 Lamport 发现了它。上述算法假设了一些原子性前提，例如不会读到写到一半的值，但该算法对原子性的假设只有写入是原子性的，而读是没有原子性要求的。这可以实现一些跨机器的互斥。

设想这样一个场景，在面包店里，如何保证收银员一次只服务一个顾客——排队。那么基于什么排队呢，我们对进入面包店的顾客每人发一个号码，该号码是保证递增的就行，最后在收银时，按从小到大的顺序进行收银。

基于这么一个简单的想法，我们就可以更严格地定义这个算法。首先我们定义一个数组 choosing 用来表示顾客在取号，再定义一个 number 数组，来表示顾客所取到的号。

bool choosing[N] = {false};
int number[N] = {0};

int max(int number[], int size) {
	int max_number = 0;
	for(int i = 0; i < size; i++) {
		if(number[i] > max_number) {
			max_number = number[i];
		}
	}
	return max_number;
}

void race(int i) {
	choosing[i] = true;
	number[i] = 1 + max(number, N);
	choosing[i] = false;
	for(int j = 0; j < N; j++) {
		// 如果有人在取号，则等他取完
		while(choosing[j]);
		while(number[j] != 0 && (
				// 如果存在所取的号比 i 更小的，则等待它进入互斥区并退出
				(number[j] < number[i]) ||
				// 如果存在所取的号和 i 一样的，那么线程号更低的优先进入互斥区
				(number[i] == number[j] && j < i)));
	}
	// 互斥区开始
	// ...
	// 互斥区结束
	number[i] = 0;
}

虽然只有短短几行代码，但是仍然有很多细节。在所取的号中，是有可能存在多个线程取得号一样的，取号是递增但并不是严格递增。这是因为有可能有两个线程同时在执行 max(number)，他们互相不知道对方的号，因为 max(number) 还没执行完毕，这两个线程的号都是 0，还没赋值，所以可能一起执行完毕，此时他们的号就会是一样的。

为了让号一样的仍然有序进入互斥区，Bakery Algorithm 的做法是让线程号更低的更优先（线程号是线程本身的 ID 号，不同于所叫到的号，不要混淆）。所以在第二个循环中的条件，需要好好理解，第一个条件 number[j] != 0 显然只需要等待有叫号的线程，没叫号的线程代表不准备进入互斥区，所以不需要和他们竞争。

原文的判断条件是 number[j] != 0 && (number[j], j) < (number[i], i)

(number[j], j) < (number[i], i) 可以等价为两个条件，满足其一值就为真

number[j] < number[i]：如果存在线程 $j$ ，其叫到的号比线程 $i$ 小，其值为真
number[j] == number[i] && j < i：如果线程 $j,i$ 叫到的号相同，且线程号 $j<i$ ，其值为真，换句话说，如果存在一个叫到的号和自己相同，且其线程号比自己小，该条件判断为真

在满足判断是为真的情况下，循环不会退出，所以该循环的意义就是等待上述条件判断值为假时退出循环，进入临界区。

相比上述的算法，该算法一是解决了互斥问题，二是解决了饥饿问题，因为是按号顺序进入互斥区，所以不会存在某一个线程一直进入互斥区，导致饥饿问题。

回过头来我们再来看看为什么需要 choosing 数组，假如一个线程在取号，为什么需要等他取完？

设想一个这样的场景，只有两个线程在竞争，线程 $i$ 和线程 $j$ 同时在取号，且取到了同样的号，线程 $i$ 已经取完号进入了循环，检查互斥条件，而线程 $j$ 比较慢，虽然已经算出来要取的号是多少了，但是还没进行赋值。

此时线程 $i$ 进入第二个 while 判断，注意此时线程 $j$ 还没赋值，此时它的号为 0，所以线程 $i$ 顺理成章地进入了互斥区。此时线程 $j$ 完成了赋值，进入互斥条件的判断，虽然线程 $j$ 看到了线程 $i$ 取到的号和自己一样，但是线程 $j$ 的线程号更小（ $j<i$ ），于是线程 $j$ 认为自己优先级更高，也顺理成章地进入了互斥区，这样就造成了同时有两个线程进入互斥区，所以需要 choosing 数组。

choosing 数组表示线程正在取号，只有当取完号，也就是确实将号写入到 number 数组了，其才会置为 false。在同样的场景下，线程 $i$ 就会等待线程 $j$ 取完号（第一个 while），然后才会进行检查第二个 while，然后发现线程 $j$ 的号和自己一样，但是 $j<i$ ，所以需要等待线程 $j$ 先进入互斥区。

所以也可以看出，Bakery Algorithm 对于优先级的原则是先来先服务 FCFS 的原则，但这并不一定符合所有调度场景的逻辑，所以基于 Bakery Algorithm，后续也衍生出了很多算法。

死锁问题

这些互斥算法都假设线程/进程是正常运行的，不会崩溃。假如是多进程的互斥，进程是有可能崩溃的，如果在互斥区崩溃或异常退出，导致一些标志位没有恢复，就会导致整个算法都无法进行下去，形成死锁。

这种假设在单机上是容易保证的，但拓展到多机集群，实际上是无法保证的，机器出现故障或通信线路出现故障是非常容易发生的，这样就衍生出后续的分布式系统的各种问题，所以 Dijkstra 和 Lamport 在并行系统上的研究开创了后续分布式系统的发展，这两位是鼻祖级别的人物。

分布式系统相关的内容是后话了，再回到互斥问题上，以上列举的算法，在假设线程都是正常运行的情况下是否可能存在死锁问题。

Dijkstra 的算法是容易证明的，在所有线程正常执行的情况下，在初始条件下，一定会有一个线程进入互斥区，因为 not_in_critical_section 初始值为 true，一定有一个线程会将 $k$ 设为 $i$ ，并进入互斥区。那么在线程 $i$ 正常退出互斥区的情况下，会将 not_in_critical_section[k] 设为 true，从而又保证了一定有一个线程会将 $k$ 设为 $i$ ，从而进入 race 检查。

那么死锁只可能发生在两个线程互相进行 race 检查，互相竞争最后谁也进不去，有可能出现这种情况吗？实际上 race 检查至多只会发生一次，进入 race 检查的前提是两个线程刚好先后将 $k$ 设为自己，然后进入 race 检查，而此时一定有一个线程会先退出 race 检查，进入到互斥检查，但此时 $k$ 已经无法被更改了，因为 not_in_critical_section[k] 已经是 false 了（假设线程 $i,j$ 竞争， $k$ 一定会被设为 $i,j$ 中的某一个值，从而使另一个线程无法满足 k == i 的条件进入 race 检查）

那么 Bakery Algorithm 呢？该算法比 Dijkstra 简单得多，证明也容易得多，在所有正常执行竞争的线程中，一定存在一个或多个叫号最小的线程，而这些线程中一定存在一个线程号最小的（线程号不可能相同），那么就存在这么一个唯一的线程可以进入互斥区。从而更新 number 数组，使后续的线程能够有序进入互斥区，所以不可能存在死锁问题。

Reference

[1] mutual exclusion 和面包店算法
[2] 深度探索分布式理论经典论文
[3] Solution of a Problem in Concurrent Programming Control
[4] A New Solution of Dijkstra’s Concurrent Programming Problem

文章作者: Yuan.

文章链接: /archives/bakery

微信扫一扫

评论 | 0条评论