Barrière De Synchronisation

Barrière de synchronisation

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.

Sommaire

Algorithme mono-barrière

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

Limite de l'algorithme

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. Le sémaphore ATTENTE garde une valeur supérieur ou égale à 1 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
  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 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

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.

Exemple d'utilisation

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

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

Voir aussi

Problèmes classiques des
méthodes de synchronisation

Couplage fort - Famine

Interblocage - Inversion de priorité

Les méthodes de synchronisation

Barrière de synchronisation - Futex - Moniteur

Mutex - Sémaphore - Spinlock

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Barri%C3%A8re de synchronisation ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Barrière De Synchronisation de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Barriere de synchronisation — Barrière de synchronisation 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… …   Wikipédia en Français

  • Barrière de synchronisation — 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 à… …   Wikipédia en Français

  • Barrière commerciale — Barrière Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.  Pour l’article homophone, voir barrier …   Wikipédia en Français

  • Synchronisation (multitaches) — Synchronisation (multitâches) Pour les articles homonymes, voir Synchronisation. Problèmes classiques des méthodes de synchronisation …   Wikipédia en Français

  • Synchronisation (multitâches) — Pour les articles homonymes, voir Synchronisation. Dans le contexte de la programmation concurrente, le terme de synchronisation se réfère à deux concepts distincts mais liés : la synchronisation de processus et la synchronisation de données …   Wikipédia en Français

  • Barrière — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.  Pour l’article homophone, voir barrier. Sur les autres projets Wikimedia : « Barriè …   Wikipédia en Français

  • Algorithme De Dekker — L algorithme de Dekker est un algorithme d exclusion mutuelle. Il est basé sur une approche par attente active et est divisé en deux parties, à savoir le protocole d entrée dans la section critique et le protocole de sortie. L algorithme présenté …   Wikipédia en Français

  • Algorithme De Peterson — L algorithme de Peterson est un algorithme d exclusion mutuelle. Cet algorithme est basé sur une approche par attente active. Il est constitué de deux parties : le protocole d entrée dans la section critique et le protocole de sortie. L… …   Wikipédia en Français

  • Algorithme de dekker — L algorithme de Dekker est un algorithme d exclusion mutuelle. Il est basé sur une approche par attente active et est divisé en deux parties, à savoir le protocole d entrée dans la section critique et le protocole de sortie. L algorithme présenté …   Wikipédia en Français

  • Algorithme de peterson — L algorithme de Peterson est un algorithme d exclusion mutuelle. Cet algorithme est basé sur une approche par attente active. Il est constitué de deux parties : le protocole d entrée dans la section critique et le protocole de sortie. L… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”