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 threads 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) = SECTIONCRITIQUE
NumeroTacheCourante = 1
TANTQUE NumeroTacheCourante ≤ NombreTacheMaximum ET (NumeroTacheCourante == NumeroTache OU
États(NumeroTacheCourante) ≠SECTIONCRITIQUE)
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