Lamport's Bakery Algorithm：Lamport面包店算法

一种称为 Lamport's Bakery 方法的同步方法解决了并行计算系统中的临界区问题。当多个进程需要同时使用共享资源但只有一个进程可以这样做时，这称为临界区问题。为了避免冲突并保证系统的准确性，面临的挑战是确保每个进程以互斥的方式使用资源。

Lamport 烘焙算法的伪代码

这里是 Lamport 烘焙算法的伪代码 -

• 初始化一个大小为 N 的数组（称为“选择”），其中 N 是进程总数，该数组全部为零。

• 初始化一个数组，称为数字，大小为 N，全部为零。

• 每个进程 i 在想要进入临界区时都会执行以下代码 -

  • 设置选择[i] = 1

  • 设置 number[i] = max(number[0], number[1], ..., number[N-1]) + 1

  • 设置选择[i] = 0

  • 对于每个其他进程 j，重复直到 (number[j] == 0) 或 (number[i], i)

  • 进入关键部分

• 每个进程 i 在离开临界区时都会执行以下代码 -

  • 设置数字[i] = 0

兰波特烘焙算法代码

这里有一段代码解释了兰波特烘焙算法的实际应用。我们将使用 C++ 作为本示例中的实现语言。

#include
#include
#include

#define N 5
// total number of processes
using namespace std;

atomic entering[N] = {false};
// to keep track of which process is currently trying to enter critical section
atomic number[N] = {0};
// to hold the ticket number for each process

void process(int i) {
while (true) {
// Step 1: Get ticket number
entering[i] = true;
int max_number = 0;
for (int j = 0; j max_number) {
max_number = number[j];
}
}
number[i] = max_number + 1;
entering[i] = false;

// Step 2: Wait until it is this process's turn to enter the critical section
for (int j = 0; j < N; j++) {
while (entering[j]) {}
// wait until process j has finished choosing its ticket number
while ((number[j] != 0) && ((number[j] < number[i]) || ((number[j] == number[i]) && j < i))) {}
// busy wait until it is this process's turn to enter the critical section
}

// Step 3: Enter the critical section
cout