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'A 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 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, sera très peu employé en pratique : Son seul avantage étant de nous préserver des famines sans que le développeur n'aie à les mettre en avant lors de la conception, on préférera alors 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
Les méthodes de synchronisation

Barrière de synchronisation - Futex - Moniteur

Mutex - Sémaphore - Spinlock

Problèmes classiques des
méthodes de synchronisation

Couplage fort - Famine

Interblocage - Inversion de priorité


  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Algorithme de Dekker ».

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

  • 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

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

  • 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

  • Allocation de ressources — v · d · m Synchronisation en …   Wikipédia en Français

  • Conditions de concurrence — Les conditions de concurrence correspondent aux situations dans lesquelles se retrouvent plusieurs processus tentant d accéder au même moment à une même ressource partagée (Fichier, Imprimante, etc... ). Le résultat de telles situations dépend de …   Wikipédia en Français

  • Inversion de priorité — L inversion de priorité est un phénomène qui peut se produire en programmation concurrente. Il s agit d une situation dans laquelle un processus de haute priorité ne peut pas avoir accès au processeur car il est utilisé par un processus de plus… …   Wikipédia en Français

Share the article and excerpts

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