L\'algorithme de Dekker
L'algorithme de Dekker de est un algorithme de la programmation concourante pour l'exclusion mutuelle dérivée par le hollandais T. Dekker du mathématicien du qui permet à deux processus (fils) de partager une ressource à utiliser une seule fois sans conflit, en utilisant seulement la mémoire partagée pour la communication.
Il évite l'alternance stricte d'un algorithme de tourner-prise naïf, et était l'un des premiers algorithmes d'exclusion mutuelle à inventer.
Introduction
Si deux processus essayent d'écrire une section critique en même temps, l'algorithme permettra seulement un processus dedans, basé sur à qui le tour il est. Si un processus est déjà dans la section critique, l'autre processus l'attente occupée le premier processus sortira. Ceci est fait en employant deux drapeaux f0 et f1 qui manifestent une intention d'écrire la section critique et une variable de tour qui indique qui a la priorité entre les deux processus.
Pseudo-code
f0 : = faux f1 : = faux tour : = 0 // ou 1 p0 : p1 : f0 : = f1 vrai : = rectifier tandis que f1 { tandis que f0 { si ≠ 0 de tour de { si ≠ 1 de tour de { f0 : = f1 faux : = faux tandis que ≠ 0 de tour de { tandis que ≠ 1 de tour de { }} f0 : = f1 vrai : = rectifier }} }} section critique de // de section critique de // … … section de reste de // de section de reste de // tour : = 1 tour : = 0 f0 : = f1 faux : = faux
Les processus manifestent une intention d'écrire la section critique qui est examinée par l'externe tandis que boucle. Si l'autre processus n'a pas marqué l'intention, la section critique peut être écrite sans risque indépendamment du tour courant. L'exclusion mutuelle sera encore garantie comme ni l'un ni l'autre processus ne peut devenir critique avant de placer leur drapeau (l'implication au moins d'un processus écrira la boucle de moment). Ceci garantit également le progrès car l'attente ne se produira pas sur un processus ce qui a retiré l'intention pour devenir critique. Alternativement, si l'autre variable de processus était placée la boucle de moment est écrite et la variable de tour établira qui est autorisé à devenir critique. Les processus sans priorité retireront leur intention d'écrire la section critique jusqu'à ce qu'ils soient accordés la priorité encore (l'intérieur tandis que boucle). Les processus avec la priorité se casseront de la boucle de moment et écriront leur section critique.
L'algorithme de Dekker garantit l'exclusion mutuelle, l'absence de l'impasse, et l'absence de la famine. Voyons pourquoi la dernière propriété se tient. Supposer que p0 est coincé à l'intérieur du " ; tandis que f1" ; boucle pour toujours. Il y a d'absence d'impasse, tellement par la suite p1 procédera à sa section critique et placera le tour = 0 (et la valeur du tour restera sans changement tant que p0 ne fait pas progrès). Par la suite p0 éclatera du " intérieur ; tandis que ≠ 0" de tour ; boucle (si elle était jamais stuck là-dessus). Ensuite qu'elle placera f0 : = rectifier et s'installer à f1 de attente pour devenir faux (depuis le tour = 0, il ne fera jamais les actions dans la boucle de moment). La prochaine fois que p1 essaye d'écrire sa section critique, il sera forcé d'exécuter les actions dans son " ; tandis que f0" ; boucle. En particulier, elle par la suite placera f1 = faux et deviendra stuck dans le " ; tandis que ≠ 1" de tour ; boucle (puisque le tour demeure 0). La prochaine fois que la commande passe à p0, elle sortira le " ; tandis que f0" ; faire une boucle et écrire sa section critique.
Si l'algorithme étaient modifiés en effectuant les actions dans le " ; tandis que f0" ; faire une boucle sans vérifier si tour = 0, puis il y a une possibilité de famine. Ainsi toutes les étapes dans l'algorithme sont nécessaires.
Note
Un avantage de cet algorithme est qu'il n'exige pas le spécial Essai-et-a placé des instructions de (atomiques lus/modifient/écrivent) et est donc fortement portable entre les langues et les architectures de machine. Un inconvénient est qu'il est limité à deux processus et se sert du de attente occupé au lieu de la suspension de processus. (L'utilisation de l'attente occupée suggère que les processus devraient passer un minimum de temps à l'intérieur de la section critique.)
Les logiciels d'exploitation modernes fournissent les primitifs d'exclusion mutuelle qui sont plus généraux et flexibles que l'algorithme de Dekker. Cependant, il convient noter qu'en l'absence de la controverse réelle entre les deux processus, l'entrée et la sortie de la section critique est extrêmement efficace quand l'algorithme de Dekker est employé.
Beaucoup d'unités centrales de traitement modernes exécutent leurs instructions d'une mode en panne. Cet algorithme ne travaillera pas aux machines de la SMP équipées de ces unités centrales de traitement sans utilisation des barrières de mémoire de
En plus, beaucoup de compilateurs de linéarisation peuvent exécuter les transformations qui feront échouer cet algorithme indépendamment de la plate-forme. Dans beaucoup de langues, elle est légale pour qu'un compilateur détecte que le f0 de variables de drapeau et le f1 ne sont jamais accédés dans la boucle. Elle peut alors enlever écrit à ces variables de la boucle, using un appelé de processus le mouvement Boucle-invariable de code. Il serait également possible que beaucoup de compilateurs de détecter que la variable du tour de n'est jamais modifiée par la boucle intérieure, et exécutent une transformation semblable, ayant pour résultat une boucle infinie potentiel. Si l'une ou l'autre de ces transformations sont exécutées, l'algorithme échouera, indépendamment de l'architecture.
Pour alléger ce problème, des variables volatiles du devraient être marquées en tant que modifiable en dehors de la portée du contexte actuellement d'exécution. Par exemple, dans Java, on annoterait ces variables en tant que « composé volatil ». Noter cependant cela le " de C/C++ ; volatile" ; l'attribut garantit seulement que le compilateur produit du code avec la commande appropriée ; il n'inclut pas les barrières nécessaires de mémoire de pour garantir l'exécution dans-ordre de ce code.
Voir également
l'algorithme de Peterson
Algorithme de la boulangerie de Lamport de
.
| Random links: | Église et antisémitisme d'unification | Search.ch | Gare de Nunhead | Adanur | Algoritmo_de_Dekker |