Exclusion mutuelle et exclusion mutuelle de groupe

le problème de l’exclusion mutuelle

Le problème d’allocation en exclusivité d’une seule ressource (Exclusion Mutuelle) est un paradigme des problèmes de compétition dans les systèmes. Il s’agit d’un problème de compétition dont l’énoncé est très simple : une entité, appelée ressource non partageable ou critique, ne peut être octroyée à un instant donné qu’à un seul processus parmi N processus du système. Autrement dit, dans un tel problème, c’est l’aspect de concurrence qui domine lorsque plusieurs processus tentent en même temps d’accéder à une même ressource. En effet, l’utilisation de la ressource critique simultanément par un ensemle de processus peut créer une situation d’incohérence. Exclusion mutuelle et exclusion mutuelle de groupe Exclusion mutuelle et exclusion mutuelle de groupe : état de l’art D’où la nécessité du développement des algorithmes de contrôle ayant comme fonctions principales : synchroniser les différents processus d’un système distribué pour l’accès à la même ressource, et éviter toute incohérence. Ce sont les algorithmes distribués d’exclusion mutuelle. 

Environnement

Nous considérons un système distribué constitué par un ensemble fini de processus {P1, · · · , Pi , · · ·PN } qui communiquent exclusivement par messages. Le canal de communication où transitent les messages est le moyen qui permet aux processus de communiquer entre eux. Tous les algorithmes qui seront examinés dans cette section se basent sur les hypothèses suivantes : 1. Les canaux : • ne dupliquent pas les messages, • peuvent être FIFO ou non : ceci signifie que les messages peuvent être reçus ou non dans l’ordre de leur emission, • délivrent les messages sans perte, • peuvent être bidirectionnels 2. Le délai : • de traitement est nul, • de transmission de messages est arbitraire mais fini.

Spécification des contraintes

Dans un algorithme distribué d’exclusion mutuelle, deux procédures1 sont généralement offertes à un processus désirant accéder à la ressource critique : une procédure d’acquisition et une procédure de libération. Les exécutions de ces procédures doivent être synchronisées de façon à ce qu’à tout moment, un processus et un seul soit en cours d’utilisation de la ressource critique. Généralement, la partie de l’algorithme distribué qui utilise la ressource est appelée section critique. 1On parle aussi de protocole 2  Le schéma général d’un algorithme distribué d’exclusion mutuelle est illustré par la figure 1.1. 

Invariants du problème

Dans le contexte de l’exclusion mutuelle, nous distinguons deux invariants fondamentaux auxquels est assujetti tout algorithme distribué d’exclusion mutuelle. Envoi de messages Envoi/Réception de messages Envoi de demandes Transition Acquisition Exécution Section Critique Libération Réseau de communication Processus P FIG. 1.1 – Structure générale d’un algorithme distribué d’exclusion mutuelle • Invariant 1 : La sûreté2 , à tout moment au plus un seul processus exécute la section critique. • Invariant 2 : La vivacité3 , la section critique est toujours accessible par un processus demandeur au bout d’un temps fini. Autrement dit, le premier invariant implique que l’exclusion mutuelle à une seule ressource est garantie à tout moment. Tandis que le second indique qu’une situation d’interblocage ne se présente jamais. Généralement, toute exécution de la section critique se déroule en un temps fini. Ceci signifie qu’aucun processus demandeur de la section critique n’attend indéfiniment : ce qui 2Ou safety en anglais 3Ou liveness en anglais 3 Exclusion mutuelle et exclusion mutuelle de groupe : état de l’art implique l’absence d’une situation de famine. 

Classification des algorithmes

Notre étude approfondie des algorithmes d’exclusion mutuelle existants a donné naissance à une classification très synthétique sous forme d’approches. La notion d’approche est intimement liée aux outils et mécanismes utilisés dans l’ensemble des algorithmes qui y sont exhibés [KHI98]. Nous nous sommes interessés aux premiers algorithmes proposés et nous avons étudié leur évolution progressive ; ce qui nous a aidé à établir une classification hiérarchique que nous illustrons par la figure ci-dessous.