Cours et TD du 09/11/2023
Je n’ai rien suivi désolé, le cours vient d’ailleurs

Suite à l’algorithme de Dekker, aujourd’hui, on va voir des algorithmes supplémentaires, notamment pour n processus, et pas que 2.

Une première tentative (qui ne va pas être bonne au départ, on va améliorer par la suite), est de partir du point de départ de la dernière fois : on va avoir une variable flag pour dire qu’on est intéressé.

Algo 1

On va déclarer un tableau de booléen qu’on va appeler flag et on va dire qu’il est de taille 2 (2 processus). Ensuite, on va voir la généralisation pour n processus.

flag = boolean[2]{false}

processus Pi
begin
  flag[i] := true
  while(flag[i-1]) do {}
  criti
  flag[i] := false
end

\RA On lance deux procédures comme ça en parallèle.

Sûreté

Oui. Au moment où je m’apprête à entrer, mon flag est à 1, je teste (dans le while) que l’autre n’est pas intéressé. L’autre, il est soit au début, soit à la fin de sa procédure. Si j’ai déjà « bloquer la porte » en disant que je suis intéressé, l’autre ne pourra pas franchir le while.

Algo 2

Toujours avec 2 processus

Lorsque je vais dire que je suis intéressé, je dis : « je suis intéressé, mais je vais laisser passer l’autre ». Pas de flag maintenant, mais on va avoir une variable globale qu’on va appeler “la victime” (= le processus qui va rester en arrière pour laisser passer les autres).

int victim

processus Pi
begin
  victim := i # c'est moi la victime
  while(victim = i) do {} # tant que la victime c'est moi, j'attend
  criti
end

Sûreté

Oui, car lorsqu’on dépasse le while, l’autre est forcément victime

Problème

Celui qui sort de section critique, risque de ne pas se déclarer à nouveau victime (parce que, par exemple, le thread c’est terminé) et ainsi l’autre processus reste bloqué.

Peterson (2 processus)

Un algorithme assez simple qui combine les deux algorithmes prédécèdent.

flag = boolean[2]{false}
int victim

processus Pi
begin
  flag[i] := true # la ressource m'interesse
  victim := i
  while(flag[i-1] ET victim = i) do {} # tant que l'autre est intéressé ET que je suis la victime
  criti;
  flag[i] := false # je ne suis plus intéresser (permet d'empecher les autres
                   # d'entrer dans leur zone critique)
end

Sûreté

Oui. Il y a toujours un qui va affecter victime en dernier.

Vivacité

Oui, même si l’autre reste la victime, on n’empêche pas l’autre d’entrer en section critique

Absence de blocage

Oui

Conclusion

\RA Algorithme plus simple que l’algo de Dekker

Rappelle de nos deux hypothèses

1. Les lectures et écritures sont atomiques, ce qui n’est pas le cas dans la réalité.
2. On ne meurt pas en zone critique

Comment généraliser à n processus ?

L’idée est de choisir un certain ordre entre les processus. S’il y a que 2, c’est soit un, soit l’autre.

Mais, s’il y a plusieurs, il faut décider qui va d’abord rester attendre et ainsi, on fait passer les n-1 autres processus, et ensuite : parmi les n-1 processus, qui va rester attendre et ainsi va laisser passer les n-2 processus ?

Jusqu’à la fin, il ne reste plus que deux processus. Les processus qui sont derrière (les victimes) peuvent passer que lorsque ceux devant-eu, ont tous passé.

Peterson (n processus)

level = int[n]{0} 
victim = int[n]{0}

processus Pi
# Pour pouvoir entrer faudra qu’il passe au level 1, ensuite level 2, ensuite level 3...
# Si il est choisi comme victime il reste au même level, et il pourra avancer
# que a une certaine condition.
begin
  for(l = 0 ; l < n ; l + 1) # l pour level
    level[i] := l
    victim[l] := i # je suis victime
    while existe un k != i : level[k] >= l ET victim[l] = i do {}
  endfor
  criti
  level := 0 # reviens au niveau 0
end

Sûreté

Exclusion mutuelle

Vivacité

Oui, mais pas de garantie d’équité

Absence de blocage

Oui

Explication

Exemple