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 <iostream>
#include <atomic>
#include <thread>

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

atomic<bool> entering[N] = {false}; 
// to keep track of which process is currently trying to enter critical section
atomic<int> 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
.............

Lamport 烘焙算法的优点

下面列出了 Lamport 烘焙算法的优点 -

• 通过向请求访问共享资源的进程或线程提供不同的令牌，可以确保公平性。

• 根据指定值分配代币可以防止饥饿。

• 使用基于代币的策略，简单易懂，易于理解和执行。

• 高效，不需要复杂的数据结构或进程间交互。

• 无需专门的硬件或硬件帮助，它就可以提供互斥。

• 适用范围广，适应性强，可以应用于多种不同的场景，保证并发计算的公平性和互斥性。

• 对于在分布式或并行系统上工作的软件工程师来说是一个有用的工具。

Lamport 烘焙算法的缺点

• 忙等待 - 该算法调用忙等待，这可能导致效率低下和 CPU 利用率高，特别是当有大量进程或线程争夺访问同一共享资源时。

• 饥饿 - 尽管算法确保正义，但没有任何保障措施。进程或线程偶尔可能会被重复停止，这会阻止其获取令牌并访问资源。

• 开销 - 该算法需要更多内存和处理时间来确定令牌序列，因为它需要存储每个进程或线程的状态信息。

• 复杂性 - 由于算法必须仔细处理竞争条件和死锁，并且可能使用互斥体或信号量等同步机制，因此其应用可能很困难。

  李>

结论

一种称为 Lamport 烘焙算法的互斥算法可确保各个进程或线程可以利用共享资源而不会相互干扰。这是一种简单的算法，可以防止饥饿并确保正义。

该算法的工作原理是向发出资源访问请求的每个进程或线程分配令牌，然后比较这些令牌的值以确定它们的给出顺序。该资源首先可供具有最少令牌的操作使用。

以上是Lamport's Bakery Algorithm：Lamport面包店算法的详细内容。更多信息请关注PHP中文网其他相关文章！