Algorithme de Dekker

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é dans cet article est une version pouvant fonctionner avec N thread, version due à Edsger Dijkstra.

Sommaire

Description

L'algorithme de Dekker nécessite les éléments et les informations suivantes :

  • Chaque thread doit pouvoir être identifié par un numéro unique. Ces identificateurs doivent être contigus.
  • Le nombre maximum de thread doit être connu à l'avance.

Il faut disposer d'un tableau (dont chaque case correspond à un thread grâce à l'utilisation des numéros précités) et d'une variable définissant le thread ayant la priorité. Le tableau pourra contenir trois valeurs, à savoir une valeur indiquant qu'un thread souhaite entrer en section critique, qu'un thread est en section critique et qu'un thread ne souhaite pas entrer en section critique. Par défaut aucun thread ne souhaite entrer dans la section critique.

Pour la suite de la discussion, États désignera le tableau et Prochain désignera la variable précitée. Les constantes VEUX, SC et VEUXPAS définiront les trois états précités. Les numéros des thread iront de 1 à NombreTacheMaximum.

Protocole d'entrée

il faut initialiser Prochain

Le protocole d'entrée est défini par l'algorithme suivant (Le paramètre de l'algorithme est le numéro du thread)

Entree(NumeroTache) :
   REPETER
      États(NumeroTache) = VEUX
      TANTQUE  NumeroTache <> Prochain FAIRE
         SI États(Prochain) == VEUXPAS ALORS
            Prochain = NumeroTache
         FIN SI
      FIN FAIRE
      États(NumeroTache) = SC
      NumeroTacheCourante = 1
      TANTQUE NumeroTacheCourante ⇐ NombreTacheMaximum ET (NumeroTacheCourante == NumeroTache OU
                                                          États(NumeroTacheCourante) <> SC) FAIRE
         NumeroTacheCourante++
      FIN FAIRE
   JUSQU'À NumeroTacheCourante>NombreTacheMaximum

La première boucle TANTQUE permet à un thread d'attendre que ce soit son tour d'entrer (à l'aide de la variable prochain). La deuxième boucle TANTQUE permet de contrôler qu'il n'y a aucun autre thread dans la section critique. Enfin, la boucle principale permet, soit de laisser entrer un thread si la deuxième boucle TANTQUE a garanti qu'il n'y avait pas d'autres thread en section critique, soit de retirer la requête et d'attendre une autre occasion d'entrer.

Protocole de sortie

Le protocole de sortie est défini par l'algorithme suivant (Le paramètre de l'algorithme est le numéro du thread)

Sortie(NumeroTache) :
   États(NumeroTache)=VEUXPAS

Remarque

Cet algorithme nous affranchit de tout risque de famine, mais cela est coûteux, car on est forcé d'introduire de l'attente active. Elle consomme du temps processeur inutilement, ce qui implique une baisse de performances significative.

Ainsi, cet algorithme, très théorique, est peu employé en pratique : son seul avantage étant de nous préserver des famines sans que le développeur ait besoin de les mettre en avant lors de la conception.

On préférera adopter une modélisation différente, permettant d'expliciter les cas de famines durant la conception plutôt que de s'en remettre à l'algorithme d'exclusion mutuelle pour les éviter. Cela nécessitera plus de réflexion, mais une fois les cas de famines dégagés, on peut se contenter de simples sémaphores pour l'implémentation du mutex.

Voir aussi

  • Luigi Zaffalon et Pierre Breguet, Programmation concurrente et temps réel avec ADA 95, Presses polytechniques et universitaires romandes, Lausanne, 1999

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Dekker de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • 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 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 la boulangerie — L algorithme de la boulangerie (Lamport s bakery algorithm en anglais) est un algorithme d exclusion mutuelle découvert par Leslie Lamport[1], dans le cadre général de machines multi processeurs à mémoire partagée ne fournissant aucune opération… …   Wikipédia en Français

  • Dekker —  Cette page d’homonymie répertorie des personnes (réelles ou fictives) partageant un même patronyme. Le patronyme néerlandais Dekker (au nord) ou Decker (au sud) renvoie vers une profession : le couvreur (du nl:dekker). Il correspond au …   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 du banquier — L algorithme du banquier est un algorithme qui a été mis au point par Edsger Dijkstra en 1965 pour éviter les problèmes interblocages et gérer l allocation des ressources. Cet algorithme est nommé ainsi car il reproduit le modèle du prêt à des… …   Wikipédia en Français

  • Decker — Dekker  Cette page d’homonymie répertorie les différentes personnes partageant un même patronyme. Le patronyme néerlandais Dekker (au nord) ou Decker (au sud) renvoie vers une profession : le couvreur (du nl:dekker). Il correspond au… …   Wikipédia en Français

  • Deckers — Dekker  Cette page d’homonymie répertorie les différentes personnes partageant un même patronyme. Le patronyme néerlandais Dekker (au nord) ou Decker (au sud) renvoie vers une profession : le couvreur (du nl:dekker). Il correspond au… …   Wikipédia en Français

  • Dekkers — Dekker  Cette page d’homonymie répertorie les différentes personnes partageant un même patronyme. Le patronyme néerlandais Dekker (au nord) ou Decker (au sud) renvoie vers une profession : le couvreur (du nl:dekker). Il correspond au… …   Wikipédia en Français

  • Parallélisme (informatique) — Pour les articles homonymes, voir parallèle. Blue Gene L cabinet., un des ordinateurs massivement parallèle les plus rapides des années 2000 En informatiqu …   Wikipédia en Français

Share the article and excerpts

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