Lamport's Bakery Algorithm：Lamport麵包店演算法-C++-PHP中文網

Lamport's Bakery Algorithm：Lamport麵包店演算法

WBOY

發布： 2023-08-25 20:45:17

轉載

1803 人瀏覽過

一種稱為 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
.............

登入後複製