Exclusion mutuelle - Mutual exclusion

Deux nœuds, et , étant supprimés simultanément, le nœud n'est pas supprimé.

{\style d'affichage i}

{\style d'affichage i+1}

{\style d'affichage i+1}

En informatique , l'exclusion mutuelle est une propriété du contrôle de la concurrence , qui est institué dans le but de prévenir les conditions de concurrence . C'est l'exigence qu'un thread d'exécution n'entre jamais dans une section critique alors qu'un thread d'exécution concurrent accède déjà à la section critique, qui fait référence à un intervalle de temps pendant lequel un thread d'exécution accède à une ressource partagée , telle que [Objets de données partagés , ressources partagées, mémoire partagée].

La ressource partagée est un objet de données, que deux ou plusieurs threads simultanés tentent de modifier (où deux opérations de lecture simultanées sont autorisées mais aucune opération d'écriture simultanée ou une lecture et une écriture ne sont autorisées, car cela conduit à une incohérence des données). L'algorithme d'exclusion mutuelle garantit que si un processus effectue déjà une opération d'écriture sur un objet de données [section critique] aucun autre processus/fil n'est autorisé à accéder/modifier le même objet jusqu'à ce que le premier processus ait fini d'écrire sur l'objet de données [section critique] et a libéré l'objet pour que d'autres processus puissent lire et écrire dessus.

L'exigence d'exclusion mutuelle a été identifiée et résolue pour la première fois par Edsger W. Dijkstra dans son article fondateur de 1965 "Solution of a problem in concurrent programming control", qui est considéré comme le premier sujet d'étude des algorithmes concurrents .

Un exemple simple des raisons pour lesquelles l'exclusion mutuelle est importante dans la pratique peut être visualisé à l'aide d'une liste de quatre éléments à enchaînement unique , où les deuxième et troisième doivent être supprimés. La suppression d'un nœud qui se trouve entre 2 autres nœuds est effectuée en changeant le pointeur suivant du nœud précédent pour pointer vers le nœud suivant (en d'autres termes, si le nœud est supprimé, le pointeur suivant du nœud est modifié pour pointer vers node , supprimant ainsi de la liste chaînée toute référence à node ). Lorsqu'une telle liste chaînée est partagée entre plusieurs threads d'exécution, deux threads d'exécution peuvent tenter de supprimer deux nœuds différents simultanément, un thread d'exécution changeant le prochain pointeur de nœud pour pointer vers node , tandis qu'un autre thread d'exécution change le suivant pointeur de nœud pour pointer sur nœud . Bien que les deux opérations de suppression se terminent avec succès, l'état souhaité de la liste chaînée n'est pas atteint : node reste dans la liste, car le pointeur suivant de node pointe sur node . ${\style d'affichage i}$ ${\style d'affichage i-1}$ ${\style d'affichage i+1}$ ${\style d'affichage i}$ ${\style d'affichage i-1}$ ${\style d'affichage i+1}$ ${\style d'affichage i}$ ${\style d'affichage i+2}$ ${\style d'affichage i+1}$ ${\style d'affichage i-1}$ ${\style d'affichage i+1}$

Ce problème (appelé condition de concurrence ) peut être évité en utilisant l'exigence d'exclusion mutuelle pour garantir que des mises à jour simultanées de la même partie de la liste ne peuvent pas se produire.

Le terme exclusion mutuelle est également utilisé en référence à l'écriture simultanée d'une adresse mémoire par un fil alors que l'adresse mémoire précitée est manipulée ou lue par un ou plusieurs autres fils.

Description du problème

Le problème auquel s'attaque l'exclusion mutuelle est un problème de partage des ressources : comment un système logiciel peut-il contrôler l'accès de plusieurs processus à une ressource partagée, alors que chaque processus a besoin du contrôle exclusif de cette ressource tout en faisant son travail ? La solution d'exclusion mutuelle rend la ressource partagée disponible uniquement lorsque le processus se trouve dans un segment de code spécifique appelé section critique . Il contrôle l'accès à la ressource partagée en contrôlant chaque exécution mutuelle de la partie de son programme où la ressource serait utilisée.

Une solution réussie à ce problème doit avoir au moins ces deux propriétés :

Il doit mettre en œuvre l'exclusion mutuelle : un seul processus peut être dans la section critique à la fois.
Il doit être exempt de blocages : si des processus tentent d'entrer dans la section critique, l'un d'entre eux doit éventuellement pouvoir le faire avec succès, à condition qu'aucun processus ne reste en permanence dans la section critique.

La liberté de blocage peut être étendue pour implémenter l'une de ces propriétés ou les deux :

Lockout-freedom garantit que tout processus souhaitant entrer dans la section critique pourra le faire à terme. Cela est différent de l' évitement de blocage, ce qui exige que certains processus d'attente soit en mesure d'accéder à la section critique, mais ne nécessite pas que chaque processus obtient un tour. Si deux processus échangent continuellement une ressource entre eux, un troisième processus pourrait être verrouillé et subir une privation de ressources , même si le système n'est pas dans une impasse. Si un système est exempt de verrouillages, cela garantit que chaque processus peut avoir un tour à un moment donné dans le futur.
Une propriété d'attente délimitée par k donne un engagement plus précis que la liberté de verrouillage. La liberté de verrouillage garantit que chaque processus peut accéder à la section critique à terme : elle ne donne aucune garantie sur la durée de l'attente. En pratique, un processus peut être dépassé un nombre arbitraire ou illimité de fois par d'autres processus de priorité plus élevée avant d'avoir son tour. Sous une propriété d'attente k- bornée, chaque processus a un temps d'attente maximum fini. Cela fonctionne en fixant une limite au nombre de fois que d'autres processus peuvent couper en ligne, de sorte qu'aucun processus ne puisse entrer dans la section critique plus de k fois pendant qu'un autre attend.

Le programme de chaque processus peut être divisé en quatre sections, résultant en quatre états. L'exécution du programme passe par ces quatre états dans l'ordre :

le cycle des sections d'un même processus

Section non critique: L'opération est en dehors de la section critique ; le processus n'utilise pas ou ne demande pas la ressource partagée.

En essayant: Le processus tente d'entrer dans la section critique.

Section critique: Le processus est autorisé à accéder à la ressource partagée dans cette section.

Sortir: Le processus quitte la section critique et met la ressource partagée à la disposition d'autres processus.

Si un processus souhaite entrer dans la section critique, il doit d'abord exécuter la section d'essai et attendre qu'il acquière l'accès à la section critique. Une fois que le processus a exécuté sa section critique et a terminé avec les ressources partagées, il doit exécuter la section de sortie pour les libérer pour une utilisation par d'autres processus. Le processus retourne alors dans sa section non critique.

Faire respecter l'exclusion mutuelle

Solutions matérielles

Sur les systèmes monoprocesseur , la solution la plus simple pour obtenir une exclusion mutuelle consiste à désactiver les interruptions pendant la section critique d'un processus. Cela empêchera toute routine de service d'interruption de s'exécuter (cela empêchera effectivement un processus d'être préempté ). Bien que cette solution soit efficace, elle entraîne de nombreux problèmes. Si une section critique est longue, l' horloge système dérivera à chaque fois qu'une section critique est exécutée car l'interruption du temporisateur n'est plus desservie, de sorte que le suivi du temps est impossible pendant la section critique. De plus, si un processus s'arrête au cours de sa section critique, le contrôle ne sera jamais rendu à un autre processus, ce qui arrêtera effectivement l'ensemble du système. Une méthode plus élégante pour parvenir à l'exclusion mutuelle est l' attente occupée .

L'attente occupée est efficace pour les systèmes monoprocesseur et multiprocesseur . L'utilisation de la mémoire partagée et d'une instruction de test et d'ensemble atomique fournit l'exclusion mutuelle. Un processus peut tester et définir sur un emplacement dans la mémoire partagée, et comme l'opération est atomique, un seul processus peut définir le drapeau à la fois. Tout processus qui ne parvient pas à définir l'indicateur peut soit continuer à effectuer d'autres tâches et réessayer plus tard, libérer le processeur vers un autre processus et réessayer plus tard, ou continuer à boucler tout en vérifiant l'indicateur jusqu'à ce qu'il réussisse à l'acquérir. La préemption est toujours possible, donc cette méthode permet au système de continuer à fonctionner, même si un processus s'arrête tout en maintenant le verrou.

Plusieurs autres opérations atomiques peuvent être utilisées pour fournir une exclusion mutuelle des structures de données ; le plus notable d'entre eux est la comparaison et l'échange (CAS). CAS peut être utilisé pour obtenir une exclusion mutuelle sans attente pour toute structure de données partagée en créant une liste chaînée où chaque nœud représente l'opération souhaitée à effectuer. CAS est ensuite utilisé pour changer les pointeurs dans la liste chaînée lors de l'insertion d'un nouveau nœud. Un seul processus peut réussir dans son CAS ; tous les autres processus tentant d'ajouter un nœud en même temps devront réessayer. Chaque processus peut alors conserver une copie locale de la structure de données, et lors de la traversée de la liste chaînée, peut effectuer chaque opération de la liste sur sa copie locale.

Solutions logicielles

En plus des solutions prises en charge par le matériel, certaines solutions logicielles existent qui utilisent l' attente occupée pour réaliser l'exclusion mutuelle. Les exemples comprennent:

L'algorithme de Dekker
Algorithme de Peterson
Algorithme de boulangerie de Lampport
L'algorithme de Szymański
Algorithme de boulangerie noir-blanc de Taubenfeld
L'algorithme de Maekawa

Ces algorithmes ne fonctionnent pas si une exécution dans le désordre est utilisée sur la plateforme qui les exécute. Les programmeurs doivent spécifier un ordre strict sur les opérations de mémoire au sein d'un thread.

Il est souvent préférable d'utiliser les fonctionnalités de synchronisation fournies par la bibliothèque multithread d' un système d'exploitation , qui tirera parti des solutions matérielles si possible mais utilisera des solutions logicielles si aucune solution matérielle n'existe. Par exemple, lorsque la bibliothèque de verrous du système d'exploitation est utilisée et qu'un thread essaie d'acquérir un verrou déjà acquis, le système d'exploitation peut suspendre le thread à l'aide d'un changement de contexte et l'échanger avec un autre thread prêt à être exécuté, ou peut mettre ce processeur dans un état de faible consommation s'il n'y a pas d'autre thread qui peut être exécuté. Par conséquent, la plupart des méthodes d'exclusion mutuelle modernes tentent de réduire la latence et les temps d'attente occupés en utilisant des commutateurs de mise en file d'attente et de contexte. Cependant, s'il est prouvé que le temps passé à suspendre un thread, puis à le restaurer, est toujours supérieur au temps qu'il faut attendre pour qu'un thread soit prêt à s'exécuter après avoir été bloqué dans une situation particulière, alors les verrous tournants sont une solution acceptable. solution (pour cette situation seulement).

Lié au problème de l'exclusion mutuelle

Un registre binaire test&set est suffisant pour fournir la solution sans blocage au problème d'exclusion mutuelle. Mais une solution construite avec un registre test&set peut éventuellement conduire à la famine de certains processus qui se retrouvent coincés dans la section d'essai. En fait, des états de mémoire distincts sont nécessaires pour éviter le verrouillage. Pour éviter une attente illimitée, n états mémoire distincts sont nécessaires. $\Omega ({\sqrt {n}})$

Exclusion mutuelle récupérable

La plupart des algorithmes d'exclusion mutuelle sont conçus en partant du principe qu'aucune défaillance ne se produit lorsqu'un processus s'exécute à l'intérieur de la section critique. Cependant, en réalité, de tels échecs peuvent être monnaie courante. Par exemple, une perte d'alimentation soudaine ou une interconnexion défectueuse peut entraîner une erreur irrécupérable dans un processus d'une section critique ou l'empêcher de continuer. Si une telle défaillance se produit, les algorithmes d'exclusion mutuelle conventionnels non tolérants aux défaillances peuvent bloquer ou échouer les propriétés de vitalité des clés. Pour faire face à ce problème, plusieurs solutions utilisant des mécanismes de récupération après incident ont été proposées.

Types de dispositifs d'exclusion mutuelle

Les solutions expliquées ci-dessus peuvent être utilisées pour construire les primitives de synchronisation ci-dessous :

De nombreuses formes d'exclusion mutuelle ont des effets secondaires. Par exemple, les sémaphores classiques autorisent les interblocages , dans lesquels un processus obtient un sémaphore, un autre processus obtient un deuxième sémaphore, puis les deux attendent que l'autre sémaphore soit libéré. D'autres effets secondaires courants incluent la famine , dans laquelle un processus n'obtient jamais suffisamment de ressources pour s'exécuter jusqu'à la fin ; inversion de priorité , dans laquelle un thread de priorité supérieure attend un thread de priorité inférieure ; et une latence élevée, dans laquelle la réponse aux interruptions n'est pas rapide.

De nombreuses recherches visent à éliminer les effets ci-dessus, souvent dans le but de garantir des progrès non bloquants . Aucun schéma parfait n'est connu. Blocage des appels système utilisés pour mettre en veille un processus entier. Jusqu'à ce que de tels appels deviennent threadsafe , il n'y avait pas de mécanisme approprié pour mettre en veille un seul thread dans un processus (voir polling ).

Voir également

Les références

Lectures complémentaires

Michel Raynal : Algorithmes d'exclusion mutuelle , MIT Press, ISBN 0-262-18119-3
Sunil R. Das, Pradip K. Srimani : algorithmes d'exclusion mutuelle distribués , IEEE Computer Society, ISBN 0-8186-3380-8
Thomas W. Christopher, George K. Thiruvathukal : plate-forme informatique Java hautes performances , Prentice Hall, ISBN 0-13-016164-0
Gadi Taubenfeld, Algorithmes de synchronisation et programmation concurrente , Pearson/Prentice Hall, ISBN 0-13-197259-6

Languages

In other projects