Algorithme de boulangerie de Lamport : Algorithme de boulangerie de Lamport

Une méthode de synchronisation appelée méthode Lamport's Bakery résout le problème de section critique dans les systèmes informatiques parallèles. Lorsque plusieurs processus doivent utiliser une ressource partagée simultanément mais qu’un seul processus peut le faire, on parle de problème de section critique. Pour éviter les conflits et garantir l’exactitude du système, le défi est de s’assurer que chaque processus utilise les ressources de manière mutuellement exclusive.

Pseudocode de l'algorithme de cuisson de Lamport

Voici le pseudo code de l'algorithme de cuisson de Lamport -

• Initialisez un tableau (appelé "select") de taille N, où N est le nombre total de processus, avec tous des zéros.

• Initialisez un tableau, appelé nombres, de taille N, composé uniquement de zéros.

• Chaque processus, j'exécuterai le code suivant lorsqu'il voudra entrer dans la section critique -

  • Définir la sélection[i] = 1

  • Définir le numéro[i] = max(numéro[0], numéro[1], ..., numéro[N-1]) + 1

  • Définir la sélection[i] = 0

  • Pour tout autre processus j, répétez jusqu'à ce que (numéro[j] == 0) ou (numéro[i], i)

  • Entrez la partie clé

• Chaque processus, j'exécuterai le code suivant en quittant la section critique -

  • Définir le numéro[i] = 0

Code de l'algorithme de cuisson Lampport

Voici un extrait de code expliquant l'algorithme de cuisson de Lamport en action. Nous utiliserons C++ comme langage d’implémentation dans cet exemple.

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

Sortie

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

Avantages de l'algorithme de cuisson Lamport

Les avantages de l'algorithme de cuisson de Lamport sont répertoriés ci-dessous -

• L'équité est assurée en fournissant différents jetons aux processus ou aux threads demandant l'accès aux ressources partagées.

• Distribuer des jetons selon des valeurs spécifiées évite la famine.

• Utilisez des stratégies basées sur des jetons qui sont simples et faciles à comprendre et à exécuter.

• Efficace et ne nécessite pas de structures de données complexes ni d'interactions inter-processus.

• Il fournit une exclusion mutuelle sans matériel spécialisé ni aide matérielle.

• Il a un large éventail d'applications et une forte adaptabilité. Il peut être appliqué à une variété de scénarios différents pour garantir l'équité et l'exclusion mutuelle des calculs simultanés.

• Un outil utile pour les ingénieurs logiciels travaillant sur des systèmes distribués ou parallèles.

Inconvénients de l'algorithme de cuisson Lamport

• Busy Wait - Cet algorithme appelle une attente occupée, ce qui peut entraîner une inefficacité et une utilisation élevée du processeur, en particulier lorsqu'il existe un grand nombre de processus ou de threads en concurrence pour l'accès à la même ressource partagée.

• Faim - Bien que l'algorithme garantisse la justice, il n'y a aucune garantie. Parfois, un processus ou un thread peut être arrêté à plusieurs reprises, ce qui l'empêche d'obtenir un jeton et d'accéder aux ressources.

• Overhead - Cet algorithme nécessite plus de mémoire et de temps de traitement pour déterminer la séquence de jetons, car il doit stocker des informations d'état pour chaque processus ou thread.

• Complexité - L'application de l'algorithme peut être difficile car il doit gérer soigneusement les conditions de concurrence et les blocages, et peut utiliser des mécanismes de synchronisation tels que des mutex ou des sémaphores.

  李>

Conclusion

Un algorithme mutuellement exclusif appelé algorithme de cuisson de Lamport garantit que les processus ou threads individuels peuvent utiliser des ressources partagées sans interférer les uns avec les autres. Il s'agit d'un algorithme simple qui prévient la famine et garantit la justice.

L'algorithme fonctionne en attribuant un jeton à chaque processus ou thread qui effectue une demande d'accès aux ressources, puis en comparant les valeurs de ces jetons pour déterminer l'ordre dans lequel ils ont été attribués. La ressource est disponible en premier pour les opérations avec le moins de jetons.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!