Exclusion mutuelle
Algorithme de Carvalho et Roucairol
Variables :
•état : peut prendre les valeurs demandeur, utilisateur, ailleurs, initialisée
à ailleurs ;
h : entier positif initialisé à 0.
•
heure_demande : entier. ;
•
•permissions : ensemble d’identificateurs de sites initialisé de telle sorte
que : Si sur le site i, j est dans permissions
Alors sur le site j, j n’est pas dans permissions
•en_attente : ensemble d’identificateurs de sites initialisé à .ensemble
vide
381
381
Exclusion mutuelle
Algorithme de Carvalho et Roucairol
382
382
1
Exclusion mutuelle
Algorithme de Carvalho et Roucairol
383
383
Exclusion mutuelle
Algorithme de Carvalho et Roucairol
Hypothèse : Tous les sites connaissent le nombre total de sites.
Algorithme
1. Chaque site i voulant accéder a la ressource date sa demande et
l’envoie à tout le monde un message de demande d'acces + sa date
2. Tous les sites ne voulant pas y accéder ou voulant accéder mais ayant
une date de demande postérieure a celle de i lui donnent leur accord.
3. Les autres, qui attendent l’accès à la ressource, lui donnent leur
accord, une fois ils libèrent la ressource .
4. Des qu'il a reçu l'accord de tout le monde, il rentre dans la section
critique.
384
384
2
Exclusion mutuelle
Algorithme de Carvalho et Roucairol
Question : Sûreté et vivacité sont elles assurées?
•
Réponse
•
•Sûreté(safety): au plus un processus est Dedans, accède à la section
critique.
•Vivacité (liveness) tout processus Demandeur passe en un temps fini à
l’état Dedans.
-Preuve de sûreté:
Par l'absurde, i et j rentrent en même temps dans la ressource
critique.
Donc, i a envoyé sa permission vers j
et j a envoyé sa permission vers i .
Pour en arriver la, il y a 3 cas possibles.
385
1. i a fait sa requête à j avant que j puisse faire sa demande ce cas est
385
Exclusion mutuelle
Algorithme de Carvalho et Roucairol
-Preuve de vivacité
•Les demandes de section critique sont totalement ordonnées (grâce aux
estampilles).
•Supposons qu'a un instant donne (hi ; i) soit la plus petite: Tous les
autres sites donnent la priorité au site i
le site i est dans la section critique pendant un temps fini: il finira par en
sortir. Toute demande finira par avoir la plus petite estampille par
rapport aux autres.
•Question : donner les nombres min et max , de messages envoyés par
un site pour se procurer la section critique
L’utilisation de la ressource nécessite entre 0 et 2(n – 1) messages.
Question : donner la durée pendant laquelle la ressource peut rester
inutilisée alors qu’elle est demandée :
386
Si le temps de transmission d’un message est de T, cette durée est
comprise entre 0 et 2T.
386
3
Exclusion mutuelle
Algorithme de Carvalho et Roucairol
Dans cet algorithme, le site i demande la permission à j à chaque
nouvelle demande pour accéder à la ressource critique. Nous allons
considérer l’amélioration suivante :
« puisque j a donné sa permission à i, i la considère comme acquise
jusqu’à ce que j demande à i sa permission ».
•Question : Donner une exécution où 3 sites veulent accéder à la
ressource critique avec un site qui réclame deux fois de suite une
ressource.
387
387
