Lamports Bäckereialgorithmus: Lamports Bäckereialgorithmus

Eine Synchronisationsmethode namens Lamports Bakery-Methode löst das Problem der kritischen Abschnitte in parallelen Computersystemen. Wenn mehrere Prozesse gleichzeitig eine gemeinsam genutzte Ressource nutzen müssen, dies aber nur ein Prozess tun kann, spricht man von einem kritischen Abschnittsproblem. Um Konflikte zu vermeiden und die Systemgenauigkeit zu gewährleisten, besteht die Herausforderung darin, sicherzustellen, dass jeder Prozess Ressourcen auf eine sich gegenseitig ausschließende Weise nutzt.

Pseudocode des Lamport-Backalgorithmus

Hier ist der Pseudocode für Lamports Backalgorithmus -

• Initialisieren Sie ein Array (genannt „select“) der Größe N, wobei N die Gesamtzahl der Prozesse ist, vollständig auf Nullen.

• Initialisieren Sie ein Array namens Zahlen der Größe N, alles Nullen.

• Bei jedem Prozess führe ich den folgenden Code aus, wenn er in den kritischen Abschnitt gelangen möchte -

  • Auswahl festlegen[i] = 1

  • Setze Zahl[i] = max(Zahl[0], Zahl[1], ..., Zahl[N-1]) + 1

  • Auswahl[i] = 0

  festlegen

  • Für jeden anderen Prozess j wiederholen, bis (Zahl[j] == 0) oder (Zahl[i], i)

  • Geben Sie den Schlüsselteil ein

• Bei jedem Prozess führe ich den folgenden Code aus, wenn ich den kritischen Abschnitt verlasse -

  • Nummer[i] = 0

  einstellen

Lamport-Backalgorithmus-Code

Hier ist ein Codeausschnitt, der den Backalgorithmus von Lamport in Aktion erklärt. In diesem Beispiel verwenden wir C++ als Implementierungssprache.

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

Ausgabe

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

Vorteile des Lamport-Backalgorithmus

Die Vorteile des Lamport-Backalgorithmus sind unten aufgeführt -

• Fairness wird durch die Bereitstellung unterschiedlicher Token für Prozesse oder Threads gewährleistet, die Zugriff auf gemeinsam genutzte Ressourcen anfordern.

• Die Verteilung der Token nach vorgegebenen Werten verhindert Hungersnöte.

• Verwenden Sie tokenbasierte Strategien, die einfach und leicht zu verstehen und auszuführen sind.

• Effizient und erfordert keine komplexen Datenstrukturen oder Interaktionen zwischen Prozessen.

• Es bietet gegenseitigen Ausschluss ohne spezielle Hardware oder Hardware-Hilfe.

• Es verfügt über ein breites Anwendungsspektrum und eine starke Anpassungsfähigkeit. Es kann auf eine Vielzahl verschiedener Szenarien angewendet werden, um Fairness und gegenseitigen Ausschluss gleichzeitiger Berechnungen sicherzustellen.

• Ein nützliches Tool für Softwareentwickler, die an verteilten oder parallelen Systemen arbeiten.

Nachteile des Lamport-Backalgorithmus

• Busy Wait – Dieser Algorithmus ruft Busy Wait auf, was zu Ineffizienz und hoher CPU-Auslastung führen kann, insbesondere wenn eine große Anzahl von Prozessen oder Threads um den Zugriff auf dieselbe gemeinsam genutzte Ressource konkurrieren.

• Hunger - Obwohl der Algorithmus für Gerechtigkeit sorgt, gibt es keine Schutzmaßnahmen. Gelegentlich kann es vorkommen, dass ein Prozess oder Thread wiederholt gestoppt wird, wodurch verhindert wird, dass er ein Token erhält und auf Ressourcen zugreift.

• Overhead – Dieser Algorithmus benötigt mehr Speicher und Verarbeitungszeit, um die Token-Sequenz zu bestimmen, da er Statusinformationen für jeden Prozess oder Thread speichern muss.

• Komplexität – Die Anwendung des Algorithmus kann schwierig sein, da er sorgfältig mit Race Conditions und Deadlocks umgehen muss und möglicherweise Synchronisierungsmechanismen wie Mutexe oder Semaphoren verwendet.

  李>

Fazit

Ein sich gegenseitig ausschließender Algorithmus namens Lamports Backalgorithmus stellt sicher, dass einzelne Prozesse oder Threads gemeinsame Ressourcen nutzen können, ohne sich gegenseitig zu stören. Es ist ein einfacher Algorithmus, der Hungersnöte verhindert und für Gerechtigkeit sorgt.

Der Algorithmus funktioniert, indem er jedem Prozess oder Thread, der eine Ressourcenzugriffsanforderung stellt, ein Token zuweist und dann die Werte dieser Token vergleicht, um die Reihenfolge zu bestimmen, in der sie vergeben wurden. Die Ressource steht zuerst den Vorgängen mit den wenigsten Token zur Verfügung.

Das obige ist der detaillierte Inhalt vonLamports Bäckereialgorithmus: Lamports Bäckereialgorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!