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