Algoritma Bakeri Lamport: Algoritma Bakeri Lamport

Kaedah penyegerakan yang dipanggil kaedah Lamport's Bakery menyelesaikan masalah bahagian kritikal dalam sistem pengkomputeran selari. Apabila berbilang proses perlu menggunakan sumber yang dikongsi secara serentak tetapi hanya satu proses boleh melakukannya, ini dipanggil masalah bahagian kritikal. Untuk mengelakkan konflik dan menjamin ketepatan sistem, cabarannya adalah untuk memastikan setiap proses menggunakan sumber dengan cara yang saling eksklusif.

Pseudokod algoritma pembakar Lamport

Berikut ialah kod pseudo untuk algoritma pembakar Lamport -

• Memulakan tatasusunan (dipanggil "pilih") saiz N, dengan N ialah jumlah bilangan proses, kepada semua sifar.

• Memulakan tatasusunan, dipanggil nombor, bersaiz N, semua sifar.

• Setiap proses saya akan melaksanakan kod berikut apabila ia mahu memasuki bahagian kritikal -

  • Tetapkan pilihan[i] = 1

  • Tetapkan nombor[i] = maks(nombor[0], nombor[1], ..., nombor[N-1]) + 1

  • Tetapkan pilihan[i] = 0

  • Untuk setiap proses lain j, ulangi sehingga (nombor[j] == 0) atau (nombor[i], i)

  • Masukkan bahagian utama

• Setiap proses saya akan melaksanakan kod berikut apabila meninggalkan bahagian kritikal -

  • Tetapkan nombor[i] = 0

Kod Algoritma Pembakar Lamport

Berikut ialah coretan kod yang menerangkan algoritma pembakar Lamport dalam tindakan. Kami akan menggunakan C++ sebagai bahasa pelaksanaan dalam contoh ini.

#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;
}

Output

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
.............

Kelebihan algoritma pembakar Lamport

Kelebihan algoritma baking Lamport disenaraikan di bawah -

• Kesaksamaan dipastikan dengan menyediakan token berbeza kepada proses atau rangkaian yang meminta akses kepada sumber yang dikongsi.

• Mengedarkan token mengikut nilai yang ditentukan menghalang kebuluran.

• Gunakan strategi berasaskan token yang mudah dan mudah difahami serta dilaksanakan.

• Cekap dan tidak memerlukan struktur data yang kompleks atau interaksi antara proses.

• Ia menyediakan pengecualian bersama tanpa bantuan perkakasan atau perkakasan khusus.

• Ia mempunyai pelbagai aplikasi dan kebolehsuaian yang kuat Ia boleh digunakan pada pelbagai senario yang berbeza untuk memastikan kesaksamaan dan pengecualian bersama dalam pengiraan serentak.

• Alat berguna untuk jurutera perisian yang bekerja pada sistem teragih atau selari.

Kelemahan algoritma pembakar Lamport

• Tunggu Sibuk - Algoritma ini memanggil tunggu sibuk, yang boleh membawa kepada ketidakcekapan dan penggunaan CPU yang tinggi, terutamanya apabila terdapat sejumlah besar proses atau rangkaian bersaing untuk mendapatkan akses kepada sumber kongsi yang sama.

• Lapar - Walaupun algoritma memastikan keadilan, tiada perlindungan. Kadangkala, proses atau utas mungkin dihentikan berulang kali, yang menghalangnya daripada mendapatkan token dan mengakses sumber.

• Overhead - Algoritma ini memerlukan lebih banyak memori dan masa pemprosesan untuk menentukan jujukan token kerana ia perlu menyimpan maklumat keadaan untuk setiap proses atau utas.

• Kerumitan - Aplikasi algoritma mungkin sukar kerana ia mesti mengendalikan keadaan perlumbaan dan kebuntuan dengan berhati-hati, dan mungkin menggunakan mekanisme penyegerakan seperti mutex atau semaphore.

  李>

Kesimpulan

Algoritma yang saling eksklusif yang dipanggil algoritma penaik Lamport memastikan proses atau benang individu boleh menggunakan sumber yang dikongsi tanpa mengganggu antara satu sama lain. Ia adalah algoritma mudah yang menghalang kebuluran dan memastikan keadilan.

Algoritma berfungsi dengan memberikan token kepada setiap proses atau urutan yang membuat permintaan akses sumber, dan kemudian membandingkan nilai token ini untuk menentukan susunan ia diberikan. Sumber tersedia terlebih dahulu untuk operasi dengan token paling sedikit.

Atas ialah kandungan terperinci Algoritma Bakeri Lamport: Algoritma Bakeri Lamport. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!