Exclusion Mutuelle

Exclusion Mutuelle

Exclusion mutuelle

Un Mutex (anglais : Mutual exclusion, Exclusion mutuelle) est une primitive de synchronisation utilisée en programmation informatique pour éviter que des ressources partagées d'un système ne soient utilisées en même temps. Son implémentation varie selon les systèmes (masquage des interruptions, lecture/écriture en un cycle, etc.)

Ces algorithmes permettent de réguler l'accès aux données, par exemple pour qu'une routine ne s'exécute qu'une seule fois en même temps.

Certains algorithmes utilisent un état pour commander l'exécution : les mutex doivent savoir si les programmes concernés 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, par exemple les sémaphores (mutex avec un compteur) qui peuvent bloquer l'exécution, créer des goulets d'étranglement, voire ne pas remplir leur rôle en permettant tout de même l'accès aux données protégées. Un autre effet est le blocage total des ressources, si le programme qui les utilisait n'a pas informé le système qu'il n'en avait plus besoin.

On ne connait pas, aujourd'hui, d'algorithme parfait - ils sont tous faillibles dans des conditions données.

Sommaire

Interblocage

Problèmes classiques des
méthodes de synchronisation

Couplage fort - Famine

Interblocage - Inversion de priorité

Article détaillé : Interblocage.

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 doit pouvoir repartir dans un état valide.

Le deadlock ne se limite pas qu'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

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 bogue lié à la synchronisation de plusieurs tâches. Les éléments incriminés étaient les suivants :

  • une mémoire partagée était protégée par un mutex
  • une gestion de bus sur la mémoire partagée, cette routine avait une grande priorité
  • une écriture en mémoire partagée (récupération de données), cette écriture 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 sur 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é moyenne. 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 code fut corrigé à distance, le problème n'étant pas critique mais dans d'autres situations, le résultat aurait pu être catastrophique. Il s'est avéré par la suite que le problème était déjà survenu lors des essais sans avoir été corrigé.

Voir aussi

Articles connexes

Les méthodes de synchronisation

Barrière de synchronisation - Futex - Moniteur

Mutex - Sémaphore - Spinlock

Références

  • 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

Liens externes

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Exclusion mutuelle ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Exclusion Mutuelle de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Exclusion mutuelle — Un Mutex (anglais : Mutual exclusion, Exclusion mutuelle) est une primitive de synchronisation utilisée en programmation informatique pour éviter que des ressources partagées d un système ne soient utilisées en même temps. Son implémentation …   Wikipédia en Français

  • Non respect de l'exclusion mutuelle — Conditions de concurrence Les conditions de concurrence correspondent aux situations dans lesquelles se retrouvent plusieurs processus tentant d accéder au même moment à une même ressource partagée ( Fichier, Imprimante, etc... ). Le résultat de… …   Wikipédia en Français

  • Mutuelle — Société mutuelle Une société mutuelle, ou une mutuelle, désigne en droit français une personne morale de droit privé à but non lucratif, immatriculée au Registre national des mutuelles et soumise aux dispositions du Code de la mutualité. L… …   Wikipédia en Français

  • Garantie mutuelle des fonctionnaires — Pour les articles homonymes, voir GMF. Logo de Garantie mutuelle des fonctionnaires Création …   Wikipédia en Français

  • Société mutuelle — Une société mutuelle (ou mutuelle) est, en droit français, une personne morale de droit privé à but non lucratif, immatriculée au registre national des mutuelles et soumise aux dispositions du code de la mutualité. L adjectif mutuel désigne, plus …   Wikipédia en Français

  • Groupe d'entraide mutuelle (GEM) — Groupe d entraide mutuelle La loi Nº 2005 102, du 12 février 2005 pour l égalité des droits et des chances et la citoyenneté des personnes handicapées, reconnaît explicitement, pour la première fois, la spécificité du handicap psychique et crée… …   Wikipédia en Français

  • Groupe d'entraide mutuelle — La loi Nº 2005 102, du 12 février 2005 pour l égalité des droits et des chances et la citoyenneté des personnes handicapées, reconnaît explicitement, pour la première fois, la spécificité du handicap psychique et crée un nouveau dispositif… …   Wikipédia en Français

  • Algorithme de la boulangerie — L algorithme de la boulangerie (Lamport s bakery algorithm en anglais) est un algorithme d exclusion mutuelle découvert par Leslie Lamport[1], dans le cadre général de machines multi processeurs à mémoire partagée ne fournissant aucune opération… …   Wikipédia en Français

  • Algorithme de Ricart et Agrawala — L Algorithme Ricart Agrawala est un algorithme d exclusion mutuelle sur un système distribué. Cet algorithme est une extension et une optimisation de l algorithme de Lamport, en supprimant la nécessité de communiquer un messages de libération. Il …   Wikipédia en Français

  • Algorithme De La Boulangerie — Les méthodes de synchronisation Barrière de synchronisation  Futex  Moniteur Mutex  Sémaphore  Spinlock L …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”