2-CI2-ExclusionMuelleDS.pdf

Architectures Réparties Exclusion Mutuelle Distribuée Khaled Barbaria [email protected] Faculté des Sciences de Bizerte CI2...

Architectures Réparties Exclusion Mutuelle Distribuée Khaled Barbaria [email protected] Faculté des Sciences de Bizerte CI2 2024-2025 Khaled Barbaria (FSB) Exclusion Mutuelle Distribuée 2024-2025 1 / 21 1 Introduction 2 Solution Centralisée 3 Algorithme de Lamport 4 Algorithme de Ricart et Agrawala 5 Algorithme Token Ring 6 Algorithme de Raymond Khaled Barbaria (FSB) Exclusion Mutuelle Distribuée 2024-2025 2 / 21  Introduction Introduction Objectifs Vivacité : Tout site demandant l’accès en SC finit par y entrer. Sûreté : A chaque instant, il y a au plus un site en SC. Solutions Permissions : Lamport, Ricart-Agrawala Jeton : Token Ring, Raymond Etc. Khaled Barbaria (FSB) Exclusion Mutuelle Distribuée 2024-2025 3 / 21  Solution Centralisée Solution Centralisée Un site reçoit les demandes d’entrées en SC (messages REQ). Un avis favorable (ACK) est émis par le site central si la ressource est libre. Sinon la demande est mémorisée par exemple dans une file. Lorsque le site sort de sa SC, il envoie un message LIB au site central. Ce dernier envoie un message ACK à un nouveau site (tête de la file). Khaled Barbaria (FSB) Exclusion Mutuelle Distribuée 2024-2025 4 / 21  Solution Centralisée Discussion Hypothèses Pas de pannes de processus. Pas de pertes des messages. Vivacité Garantie si les hypothèses sont vérifiées : chaque site finit par recevoir un ACK puisque les demandes sont soit directement satisfaites soit enregistrées dans la file. Sûreté Le site central garantit qu’à chaque instant, il y a au plus un seul processus en SC. Khaled Barbaria (FSB) Exclusion Mutuelle Distribuée 2024-2025 5 / 21  Algorithme de Lamport Algorithme de Lamport Hypothèses Pas de pannes de processus Canaux de communications fiables et FIFO Principe Chaque site participe à l’autorisation d’entrée en SC. Chaque site candidat à la SC envoie sa demande à tous les autres. L’ordre d’entrée en SC est celui établi par les horloges logiques (ordre total). Structures des données Chaque site i maintient un tableau Mi de messages (1 message par site) Initialement Mi [ j] = (LIB, 0, j) Khaled Barbaria (FSB) Exclusion Mutuelle Distribuée 2024-2025 6 / 21  Algorithme de Lamport Algorithme de Lamport Messages échangés (REQ, Hi , i) envoyé par i à tous les autres pour entrer en SC. (ACK, Hi , i) envoyé systématiquementpar i à j lorsque i reçoit un (REQ, H j , j) (LIB, Hi , i) envoyé par i à tous les autres à la libération de la SC. Réception des Messages Réception par i de M = (REQ, H j , j) ou (LIB, H j , j) : Mi [ j] ← M Réception par i de M = (ACK, H j , j) : Mi [ j] ← M ssi Mi [ j] n’est par de type REQ. Entrée en SC de i si ∀ j ̸= i, Mi [i]