Barrière de synchronisation

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En programmation concurrente, une barrière de synchronisation permet de garantir qu'un certain nombre de tâches ait passé un point spécifique. Ainsi, chaque tâche qui arrivera sur cette barrière devra attendre jusqu'à ce que le nombre spécifié de tâches soient arrivées à cette barrière.

Algorithme mono-barrière[modifier | modifier le code]

Pour réaliser ce premier algorithme de barrière de synchronisation, il faut disposer de deux sémaphores et d'une variable :

  • Un sémaphore MUTEX (initialisé à 1) protégeant la variable.
  • Un sémaphore ATTENTE (initialisé à 0) permettant de mettre en attente les tâches.
  • Une variable Nb_Att (initialisée à 0) permettant de compter le nombre de tâches déjà arrivées à la barrière de synchronisation.

Il faut encore définir la constante N qui indique le nombre de tâches devant arriver à la barrière avant de l'ouvrir.

Barriere :
   P(MUTEX)
   Nb_Att++
   SI Nb_Att==N ALORS
      POUR I DE 1 à N-1 FAIRE
         V(ATTENTE)
      FIN POUR
      Nb_Att=0
      V(MUTEX)
   SINON
      V(MUTEX)
      P(ATTENTE)
   FIN SI

Limites de l'algorithme[modifier | modifier le code]

Ce premier algorithme peut sembler correct, il peut cependant poser des problèmes si plusieurs barrières sont disposées dans le code.

Le scénario suivant n'est en effet pas impossible :

  1. Un processus A parmi les N-1 premiers est mis en pause (par un mécanisme préemptif) entre le V(MUTEX) et le P(ATTENTE) et ne reprendra pas la main avant un certain temps.
  2. Tous les processus arrivent au niveau de la barrière. Lorsque le dernier processus arrive, le sémaphore ATTENTE vaut alors -(N-2) (car A n'a pas effectué son opération P(ATTENTE)).
  3. Le dernier processus arrivé effectue N-1 fois V(ATTENTE) et libère le mutex. Le sémaphore ATTENTE vaut alors 1.
  4. Un processus B s'exécute rapidement et arrive à la deuxième barrière de synchronisation.
  5. B exécute le code de la barrière, et effectue un P(ATTENTE). Cette opération n'est pas bloquante car le sémaphore ATTENTE vaut 1 (le processus A n'a toujours pas effectué le P(ATTENTE) de la première barrière).

Le processus B aura donc traversé la deuxième barrière de synchronisation avant que tous les autres processus n'y soient arrivés.

Algorithme multi-barrière[modifier | modifier le code]

Pour remédier au problème évoqué ci-dessus, on a recours à un deuxième sémaphore qui permettra au dernier processus d'attendre que tous les autres processus aient effectués leur P(ATTENTE) avant de libérer le mutex. Il nous faut donc :

  • Un sémaphore MUTEX (initialisé à 1) protégeant la variable.
  • Un sémaphore ATTENTE (initialisé à 0) permettant de mettre en attente les N-1 ièmes tâches.
  • Un sémaphore PARTI (initialisé à 0) permettant de mettre en attente la dernière tâche.
  • Une variable Nb_Att (initialisée à 0) permettant de compter le nombre de tâches déjà arrivées à la barrière de synchronisation.
Barriere :
   P(MUTEX)
   Nb_Att++
   SI Nb_Att==N ALORS
      POUR I DE 1 à N-1 FAIRE
         V(ATTENTE)
      FIN POUR
      
      POUR I DE 1 à N-1 FAIRE
         P(PARTI)
      FIN POUR
      
      Nb_Att=0
      V(MUTEX)
   SINON
      V(MUTEX)
      P(ATTENTE)
      V(PARTI)
   FIN SI

Ainsi, si un processus s'exécute plus rapidement que les autres, il ne pourra pas verrouiller le mutex avant que tous les processus ne soient partis.

Exemples d'utilisation[modifier | modifier le code]

Les barrières de synchronisation peuvent être utilisées pour

  • Garantir qu'une ou plusieurs tâches ont effectué une opération particulière.
  • Attendre la fin d'un ensemble de tâches

Voir aussi[modifier | modifier le code]