Exclusion mutuelle
Un mutex (de l'anglais mutual exclusion, exclusion mutuelle) est une primitive de synchronisation utilisée en programmation informatique pour éviter qu'une ressource partagée d'un système ne soit utilisée en même temps par plusieurs utilisateurs. Son implémentation varie selon les systèmes (masquage des interruptions, lecture/écriture en un cycle, etc.)
Les mutex permettent par exemple de réguler l'accès parallèle par plusieurs fils d'exécution (threads) à une même donnée.
Explication
[modifier | modifier le code]Dans un environnement informatique donné, il arrive que plusieurs agents tentent d'accéder simultanément à une même ressource. Par exemple, deux programmes en cours d'exécution peuvent tous deux chercher à accéder à un même fichier, ou un thread d'un programme peut chercher à lire la valeur d'une variable pendant qu'un autre thread cherche à modifier cette valeur.
Dans certains cas, cette situation peut amener à des comportements non souhaités. Ainsi, si un thread écrit dans un fichier pendant qu'un autre thread lit le même fichier, le résultat de la lecture peut être incohérent.
Dans ce contexte, un mutex sert à empêcher l'accès simultané en laissant les différents agents accéder à la ressource l'un après l'autre. Selon l'algorithme, il peut par exemple utiliser un état pour commander l'ordre d'exécution : le mutex doit savoir si les programmes cherchant à accéder à la ressource sont occupés (busy) ou s'ils ont terminé et sont en attente (wait). De tels algorithmes sont par exemple :
La plupart des mutex ont des effets secondaires. Ainsi, les sémaphores (mutex avec un compteur) peuvent bloquer l'exécution en créant des goulots d'étranglement. Un autre effet est le blocage total de la ressource tant que le programme qui l'utilisait n'a pas informé le système qu'il n'en avait plus besoin.
Interblocage
[modifier | modifier le code]L'interblocage (de l'anglais deadlock) se produit, par exemple, lorsqu'un thread T1 ayant déjà acquis la ressource R1 demande l'accès à une ressource R2, pendant que le thread T2, ayant déjà acquis la ressource R2, demande l'accès à la ressource R1. Chacun des deux threads attend alors la libération de la ressource possédée par l'autre. La situation est donc bloquée.
Plusieurs méthodes existent pour les éviter :
- imposition de l'ordre d'acquisition des ressources ;
- élimination lors de la conception par une analyse détaillée des algorithmes ;
- système préventif qui détecte un risque d'interblocage avant que celui-ci ne se produise durant l'exécution ;
- système de récupération si un interblocage se produit, le système devant pouvoir repartir dans un état valide.
Un interblocage peut également se produire si un seul thread demande l'accès à une ressource qu'il a déjà acquise, certaines implémentations comme le mutex « rapide » de Linux vont bloquer le thread. L'implémentation peut gérer cette situation grâce à un mutex réentrant ou en détectant cette situation et en indiquant une erreur.
Le deadlock ne se limite pas aux primitives de synchronisation comme les mutex, il peut également survenir lors d'inversions de priorité dans le cadre de l'ordonnancement des tâches.
Un problème concret : Mars Pathfinder
[modifier | modifier le code]En 1997, la mission Mars Pathfinder rencontre un problème alors que le robot est déjà sur Mars. Après un certain temps, des données sont systématiquement perdues. Les ingénieurs découvrent alors un bug lié à la synchronisation de plusieurs tâches. Les éléments incriminés étaient les suivants :
- une mémoire partagée, qui était protégée par un mutex
- une gestion de bus sur la mémoire partagée, qui avait une priorité haute
- une écriture en mémoire partagée (récupération de données), qui avait la priorité la plus basse
- une troisième routine de communication, avec une priorité moyenne, qui ne touchait pas à la mémoire partagée
Il arrivait parfois que l'écriture (priorité faible) s'approprie le mutex. La gestion du bus (priorité haute) attendait ce mutex. La commutation de tâches laissait alors la routine de communication (priorité moyenne) s'exécuter. Or pendant ce temps, le mutex restait bloqué puisque les ressources étaient allouées à la routine de priorité basse. La gestion de bus ne pouvait donc plus s'exécuter et après un certain temps d'attente (une protection insérée par les ingénieurs via un chien de garde), le système effectuait un redémarrage. Un tel problème est connu sous le nom d'inversion de priorité.
Le problème n'était pas critique et le code fut corrigé à distance. Toutefois dans d'autres situations, les conséquences auraient pu être catastrophiques. On a ensuite constaté le fait que le problème était déjà survenu lors des essais sans avoir été corrigé.
Voir aussi
[modifier | modifier le code]Articles connexes
[modifier | modifier le code]- Les sémaphores d'Edsger Dijkstra
- Mutex réentrant
- Futex
- Algorithmes Lock-free et wait-free
- Algorithme de Naimi-Trehel
- Calcul parallèle
- Record locking
Références
[modifier | modifier le code]- Michel Raynal : Algorithms for Mutual Exclusion, MIT Press, (ISBN 0-262-18119-3)
- Sunil R. Das, Pradip K. Srimani : Distributed Mutual Exclusion Algorithms, IEEE Computer Society, (ISBN 0818633808)
- Thomas W. Christopher, George K. Thiruvathukal : High-Performance Java Platform Computing, Prentice Hall, (ISBN 0130161640)
