Instructions spéciales atomiques

On peut construire des algorithmes utilisant des instructions spéciales :

• SWAP (x,y) qui échange les 2 valeurs x et y (x est un registre local et y un mot mémoire).
• TAS (y) qui rend y en résultat et met y à 1 (y est un mot mémoire).

Exemple de processus avec SWAP verrou = 0 est une variable partagée.	Exemple de processus avec TAS verrou est une variable partagée.
Processus i cléi = 1 ; répéter SWAP (clei, verrou) jusqu’à (cléi = 0) ; Section Critique SWAP(cléi,verrou) Invariant : Somme(clei) + verrou = nombre de processus.	Processus i verrou :=0 tant que Tas(verrou) ne rien faire Section Critique verrou :=0 Programme équivalent : verrou := faux cléi :=vrai tant que cléi faire cléi :=TAS(verrou) Section Critique verrou := faux

Dans ces deux exemples, on a la SURETE mais pas la vivacité : " FAMINE ". Pour le résoudre, deux solutions sont possibles ; logicielle ou matériel (instruction spéciale). Si on envisage la solution logicielle, il s’agit de placer les processus sur un anneau (priorité tournante). Il nous faut donc des drapeaux…

drap[1..n] de booléens initialisés à faux Pi drap[i] :=vrai ; cléi :=vrai ; tant que drap[i] et clei faire cléi :=TAS(verrou) ; drap[i] :=faux ; Section Critique j := (i mod n ) + 1 ; tant que j<>i et non drap[i] faire j := (j mod n) + 1 si j<>i alors drap[j] :=faux sinon verrou :=faux ;

Pour vérifier cette solution, on pourrait faire un graphe comme précédemment. Des logiciels le font très bien. On peut déjà remarquer que l’on a un nombre fini de variables et un nombre fini d’états. C’est un Algorithme à JETON.

• FA(var, inc) qui rend var en résultat et qui fait var := var + inc (Fetch and Add).

Cette instruction permet de mettre en place un algorithme à ticket.
tour[i] =0 est une variable locale, numéro = 0 et suivant = 0 sont des variables partagées.

tour[i] := FA(numéro, 1) ; (a) tant que tour[i]<>suivant attendre ; (b) Section Critique (c) suivant := suivant + 1 ; (d)

L’instruction (a) est équivalente à tour[i] := numéro ; numéro := numéro +1 , il est important qu’elle soit atomique. Par contre, ce n’est pas gênant que (d) ne le soit pas. On est en effet encore dans la section critique.