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.

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

• Portail de l’algorithmique