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

WBOY

发布时间：2023-08-25 20:45:17

2087人浏览过

来源于tutorialspoint

转载

一种称为 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 < N; j++) {
         if (number[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 << "Process " << i << " enters the critical section." << endl;
      // perform critical section operations here

      // Step 4: Exit the critical section
      number[i] = 0;
      cout << "Process " << i << " exits the critical section." << endl;
      // perform remainder section operations here
   }
}

int main() {
   // create threads for each process
   thread t[N];
   for (int i = 0; i < N; i++) {
      t[i] = thread(process, i);
   }

   // join threads
   for (int i = 0; i < N; i++) {
      t[i].join();
   }
   return 0;
}

输出

Process 0 enters the critical section.
Process 0 exits the critical section.
Process 1 enters the critical section.
Process 1 exits the critical section.
Process 2 enters the critical section.
Process 2 exits the critical section.
Process 3 enters the critical section.
Process 3 exits the critical section.
Process 0 enters the critical section.
Process 0 exits the critical section.
Process 1 enters the critical section.
Process 1 exits the critical section.
Process 4 enters the critical section.
Process 4Process  exits the critical section.2
.............