Cours et TD du 26/10/2023

Exclusion mutuelle

Logique

• Pre-protocole
• Critique
• Post-protocole

“Définitions” qu’on veut remplir

Sûreté

Jamais 2 processus dans la section critique

Vivacité

Tout processus qui demande l’accès l’aura inévitablement (il ne pourrait pas être ignoré)

Absence de blocage

Toujours possible d’avancer (exécuter une action)

Protocoles 1

Tour de rôle

var turn : int = 1 # init

P1 || P2 # On lance P1 en parallèle avec P2

processus P1
begin
  repeat
    while turn = 2 do {} # on attend d'avoir l'accès
    crit1 # accès à la zone critique
    turn := 2
    rest1 # reste du programme
  forever
end

processus P2
begin
  repeat
    while turn = 1 do {} # on attend d'avoir l'accès
    crit2 # accès à la zone critique
    turn := 1
    rest2 # reste du programme
  forever
end

Ce protocole à un problème, car on lit turn en même temps qu’on l’écrit
On part du principe que l’accès à la variable est assurée par le module “inférieur”, on a donc un accès atomique à la variable

Sûreté

Oui, assuré par la variable turn qui ne peut pas être =1 et =2

Vivacité

Si on suppose que la section critique ne peut pas mourir, alors oui, à la sortie de la section critique, un programme donnera toujours l’accès à l’autre

Absence de blocage

Il y a blocage parce que le programme peut mourir dans le rest du programme

Critique

Le temps est rythmé par le processus le plus long, car on fait à tour de rôle, ce qui va à l’encontre de la parallélisation.
Aussi, on force aux programmes d’y aller même s’ils ne veulent pas y aller.
En plus, si 1 programme meurt, il bloque l’ensemble du processus
Enfin, ce n’est pas super, si on doit ajouter des processus (+ de 2), alors, on doit incrémenter turn

Protocole 2

On fait savoir l’envie d’aller en section critique, afin de ne plus avoir de blocage à cause d’un rest qui meurt.

var c1, c2 : int = 1, 1 # init, 1 = pas intéréssé

P1 || P2 # On lance P1 en parallèle avec P2

processus P1
begin
  repeat
    while c2 = 0 do {} # processus 2 interéssé, donc on attend
    c1 := 0 # on se dit intéressé
    crit1
    c1 := 1 # on a terminé
    rest1
  forever
end

processus P2
begin
  repeat
    while c1 = 0 do {} # processus 1 interéssé, donc on attend
    c2 := 0 # on se dit intéressé
    crit2
    c2 := 1 # on a terminé
    rest2
  forever
end

Sûreté

Problème de sûreté, car les 2 programmes peuvent rentrer en section critique s’ils se lancent exactement en même temps

Vivacité

La vivacité n’est pas assurée, parce que c’est le scheduler qui doit donner l’autorisation à l’autre de s’autoriser, s’il les programmes ne sont pas appelés équitablement, alors un programme peut ne jamais s’exécuter.
Par exemple, si le scheduler donne souvent la “parole” à P1 et que P1 s’exécute, ainsi même s’il donne théoriquement la main à P2 à la fin, si le scheduler donne tout le temps la main à P1 par défaut, ainsi P1 sera toujours appelé (et pas P2)

Protocole 3

Version réparée du protocole 2

var c1, c2 : int = 1, 1 # init, 1 = pas intéréssé

P1 || P2 # On lance P1 en parallèle avec P2

processus P1
begin
  repeat
    c1 := 0 # on se dit intéressé
    while c2 = 0 do {} # processus 2 interéssé, donc on attend
    crit1
    c1 := 1 # on a terminé
    rest1
  forever
end

processus P2
begin
  repeat
    c2 := 0 # on se dit intéressé
    while c1 = 0 do {} # processus 1 interéssé, donc on attend
    crit2
    c2 := 1 # on a terminé
    rest2
  forever
end

Sûreté

La sûreté est maintenant assurée, car c1 (ou c2) ne peut pas être 0 et 1 en même temps.

Vivacité

La vivacité n’est pas assurée, car si les deux sont intéressés en même temps, alors ils vont s’attendre éternellement.

Protocole 4

Version réparée du protocole 3

var c1, c2 : int = 1, 1 # init, 1 = pas intéréssé

P1 || P2 # On lance P1 en parallèle avec P2

processus P1
begin
  repeat
    c1 := 0 # on se dit intéressé
    while c2 = 0 do # processus 2 interéssé, donc on attend
      c1 := 1
      attendre(t)
      c1 := 0
    end
    crit1
    c1 := 1 # on a terminé
    rest1
  forever
end

processus P2
begin
  repeat
    c2 := 0 # on se dit intéressé
    while c1 = 0 do # processus 1 interéssé, donc on attend
      c2 := 1
      attendre(t)
      c2 := 0
    end
    crit2
    c2 := 1 # on a terminé
    rest2
  forever
end

Sûreté

La sûreté est validée, puisqu’il faudrait que c1 et c2 ait les valeurs inverses

Vivacité

Toujours le même problème s’ils attendent le même temps.
Mais en pratique, c’est quasi impossible que les deux processus restent synchrones à l’infini

Algorithme de Dekker

Un mix entre le protocole 1 et 4.

var turn, c1, c2 : int = 1, 1, 1

processus P1
begin
  repeat
    c1 := 0
    while c2 = 0 do
      if turn = 2 then
        c1 != 1
        while turn = 2 do {}
        c1 := 0
      end
    end
    crit1
    turn := 2
    c1 := 1
    rest1
  forever
end

processus P2
begin
  repeat
    c2 := 0
    while c1 = 0 do
      if turn = 1 then
        c2 != 1
        while turn = 1 do {}
        c2 := 0
      end
    end
    crit2
    turn := 1
    c2 := 1
    rest2
  forever
end

Sûreté

La sureté est assurée, car turn devrait être égale à deux valeurs distinctes en même temps.

Vivacité

Grâce au turn la vivacité est assurée

Absence de blocage

Pas de blocage si le programme meurt

TD

Exercice piscine

Imaginez un protocole pour une piscine

• 2 guichets :
  • 1 pour prendre la clef d’une cabine pour se changer
  • 1 pour prendre un panier pour prendre ses habits
• On suppose que l’ordre n’est pas imposé
• Ensuite, on va dans la cabine, on se change, on libère la cabine, on met mes affaires dans le panier qui sera rangé et on va se baigner
• Quand on revient, on fait l’inverse et on s’en va

Solution

• prendre_panier : pré-condition : panier libre et post-condition : panier libre
• prendre_cabine : pré-condition : panier libre et post-condition : panier libre
• rendre_panier
• rendre_cabine

1 personne	2 personne	n personnes
	Il y a un possible blocage s’il y a N_{p} personnes qui attendent un panier et N_{c} personnes attendent une cabine via la séquence : \forall N_{p} N_{c} : (T_{1}T_{2}T_{3})^{N_{p}} T_{1}^{N_{c}}	On a unifier pour enlever la source du problème

Exercice administration

• Faîtes entrer tous les clients puis fermer la porte avant de commencer le service
• Servir les clients. Une fois servit, les clients sortent au fur et à mesure
• La porte n’est réouverte que si tous les clients sont sortis

Solution