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中文網其他相關文章！