TD algorithmique répartie EXCLUSION MUTUELLE REPARTIE On rappelle que les supports de cours sont disponibles à http://mathieu.delalandre.free.fr/teachings/dcomputing.html 1. Exclusion mutuelle – cas non ordonnée 1.1.Algorithme centralisé On considère le schéma de communication suivant entre quatre processus distants P1, P2, P3 et P4 et un processus coordinateur C. En vous basant sur le protocole d’exclusion mutuelle par algorithme centralisé, veuillez indiquer pour chaque message échangé les informations suivantes: type de message, processus émetteur et destinataire, processus détenteur de la section critique, état de la pile de C. de P1 P2 C P3 P4 P1 P2 C P2 P3 C P3 C P4 1.2.Algorithme par échange de jeton On souhaite synchroniser en exclusion mutuelle un ensemble de 9 processus (de P0 à P8), structurés en anneau, par échange de jetons « token ring ». A l’état initial, le processus P3 détient le jeton. On considère par la suite que les processus effectuent leurs requêtes au cours de tour de communication « round », chaque tour correspondant à un échange pair à pair du jeton entre deux processus voisin dans la structure en anneau. L’ordre des requêtes est spécifié ci-dessous; les valeurs 3,7 pour P5 signifient que le processus requière le jeton deux fois au cours du cycle d’échange. Etablir la chronologie des échanges entre ces processus en précisant les informations suivantes: nombre de tours minimum pour satisfaire l’ensemble des processus, tour d’accès à la section critique pour chacun des processus, temps d’attente. processus requête(s) « tour » P0 3 P1 P2 4 P3 P4 7 P5 3,7 P6 P7 4 P8 2. Exclusion mutuelle – cas ordonnée 2.1. Algorithme de Ricard-Agrawala On considère la séquence de synchronisation ci-dessous entre trois processus distants P0, P1 et P2 pour un accès en exclusion mutuelle via l’algorithme de Ricard-Agrawala. Au sein de cette séquence, les évènements sont reportés dans un ordre t0 à t16. Les flèches pleines et en pointillées représentent respectivement les requêtes en accès à la section critique (avec valeur de tampon temps « timestamp ») et les réponses. On considère à l’état initial (< t0) que les valeurs des horloges logiques CLi (avec i = 0, 1 et 2) sont respectivement de 8, 6 et 3 pour P0, P1 et P2. Indiquer pour l’ensemble de la séquence les informations suivantes: instructions exécutées, états d’accès en exclusion mutuelle de chaque processus, valeurs des buffers RDi, horloges logiques CLi et compteurs MSGi. Exprimer, dans un deuxième temps, en fonction de tk avec k ∈ [0-16], les délais de synchronisation SD, temps d’exécution E et temps de réponse RT pour P0, P1 et P2 sur la séquence observée.