Site du prof
Email: abou(at)irif.fr
Partiel 16 novembre + Examen en janvier
Tout les documents sont autorisés

Cours et TD du 28/09/2023

Notation : q \xrightarrow[\qquad\Delta]{a} q\prime \text{ pour } (q, a, q\prime) \in \Delta

Année 80-90 : On fait des majeures avancées dans la partie hardware, jusqu’à atteindre une certaine limite
Ensuite, on veut mieux optimiser les logiciels, c’est pour ça qu’ont créé des processus multicœurs afin de pouvoir paralléliser les logiciels.

Dans l’ordre : Matériel > Langage de programmation > Logiciels programmés > Exécuté de manière centralisée ou distribuée ?

On ne peut pas, pour paralléliser des programmes, pour une structure donnée, dire qu’un morceau de code utilise une structure en bloquant les autres, ça, ce serait mauvais niveau performance.

Le but du cours est de comprendre comment de tels logiciels sont écrits pour faire de la concurrence.

Configuration d’un programme : sa mémoire, permet de savoir ce que peut faire un programme à un instant T.

Actions du programme (par ex. une affectation) → changer de configuration (a.k.a. changer la mémoire).

Avec ça on peut définir un graphe d’état avec les sommets, les configurations du programme et les arcs, les actions passant d’un état à un autre (transition).

Système de transition :

S = (Q, \Delta, \Sigma)
avec :

• Q : ensemble d’états
• \Sigma : alphabet d’actions
• \Delta Q \times \Sigma \times Q
  Ceci représente un graphe étiqueté.
  Un compteur :

graph LR;
    id1(( ))--put-->id2(((1)));
    id2--get-->id3(( ));

graph TD;
    0--put-->1;
    1--get-->0;

Un compteur qui va jusqu’à 2 : (buffer de taille 2)

graph LR;
    id1(( ))--put-->id2(((2)));
    id2--get-->id3(( ));

graph LR;
    0--put-->1;
    1--get-->0;
    1--put-->2;
    2--get-->1;

⇾ Avec 2 buffers de taille 1, on peut faire un buffer de taille 2 en les connectant entre eux.

graph LR;
  subgraph " "
    direction TB
    0'--put-->1';
    1'--get-->0';
  end
  subgraph "  "
    direction TB
    0--put-->1;
    1--get-->0;
  end
  1-->0'

Mais ce serait une composition séquentielle, alors, on peut faire ça :

Abstraction :
\begin{aligned} S_{1} =& (Q_{1}, \Delta_{1}, \Sigma) \\\\ S_{2} =& (Q_{2}, \Delta_{2}, \Sigma) \\\\ S_{1} || S_{2} =& (Q_{1} \times Q_{2}, \Delta_{12}, \Sigma) \\\\ \frac{q_{1} \xrightarrow[\qquad\Delta_{1}]{a} q_{1}\prime}{(q_{1}, q_{2}) \xrightarrow[\qquad\Delta_{12}]{a} (q_{1}\prime, q_{2})} & \frac{q_{2} \xrightarrow[\qquad\Delta_{2}]{a} q_{2}\prime}{(q_{1}, q_{2}) \xrightarrow[\qquad\Delta_{12}]{a} (q_{1}, q_{2}\prime)} \end{aligned}

Implémentation :

graph TD;
  a["(0, 0')"]
  b["(0, 1')"]
  c["(1, 1')"]
  d["(1, 0')"]
  a--put-->b
  a--put-->d
  b--put-->c
  d--put-->c

  c--get-->b
  c--get-->d
  d--get-->a
  b--get-->a

Pour un buffer FIFO :

graph LR;
  puta(( ))
  putb(( ))
  geta(( ))
  getb(( ))
  id[ ]
  puta--"put(a)"-->id
  putb--"put(b)"-->id
  id--"get(a)"-->geta
  id--"get(b)"-->getb

graph TB;
  a(a)
  b(b)
  id("-")
  a--"get(a)"-->id
  b--"get(b)"-->id
  id--"put(a)"-->a
  id--"put(b)"-->b

graph TB;
  vide( )
  a(a)
  b(b)
  aa(aa)
  bb(bb)
  ab(ab)
  ba(ba)
  vide--"put(a)"-->a
  vide--"put(b)"-->b
  a--"get(a)"-->vide
  b--"get(b)"-->vide
  a--"put(a)"-->aa
  a--"put(a)"-->ba
  aa--"get(a)"-->a
  ab--"get(b)"-->a
  b--"put(b)"-->ab
  b--"put(b)"-->bb
  ba--"get(a)"-->b
  bb--"get(b)"-->b

Il y a une synchronisation, la boite doit attendre la boite précédente.
\text{Sync} \subseteq \Sigma
\frac{q_{1} \xrightarrow[\qquad\Delta_{1}]{a} q_{1}' \quad q_{2} \xrightarrow[\qquad\Delta_{2}]{a} q_{2}' \quad a \leftarrow \text{Sync}}{(q_{1}, q_{2}) \xrightarrow[\qquad\Delta_{12}]{a} (q_{1}, q_{2}')}

\begin{aligned} & \tau_{a}, \tau_{b} \in \text{Sync} \\\\ S_{1}\prime =& S_{1}\left[\frac{\text{get(a)}}{\tau_{a}}, \frac{\text{get(b)}}{\tau_{b}}\right] \\\\ S_{2}\prime =& S_{2}\left[\frac{\text{put(a)}}{\tau_{a}}, \frac{\text{put(b)}}{\tau_{b}}\right] \\\\ & S_{1}\prime ||\scriptstyle{\{\tau_{a}, \tau_{b}\}}S_{2}\prime \end{aligned}

graph TB;
  subgraph S2
    puta(( ))
    putb(( ))
    geta(( ))
    getb(( ))
    id[ ]
    puta--"τ_a"-->id
    putb--"τ_b"-->id
    id--"get(a)"-->geta
    id--"get(b)"-->getb
  end
  subgraph S1
    2puta(( ))
    2putb(( ))
    2geta(( ))
    2getb(( ))
    2id[ ]
    2puta--"put(a)"-->2id
    2putb--"put(b)"-->2id
    2id--"τ_a"-->2geta
    2id--"τ_b"-->2getb
  end

graph TB;
  vide("(-, -)")
  a_("(a, -)")
  b_("(b, -)")
  _a("(-, a)")
  _b("(-, b)")
  aa("(a, a)")
  bb("(b, b)")
  ab("(a, b)")
  ba("(b, a)")
  
  a_--"τ_a"-->_a
  b_--"τ_b"-->_b
  
  vide--"put(a)"-->a_
  vide--"put(b)"-->b_
  _a--"put(a)"-->aa
  _a--"put(b)"-->ba
  _b--"put(a)"-->ab
  _b--"put(b)"-->bb
  
  _a--"get(a)"-->vide
  _b--"get(b)"-->vide
  aa--"get(a)"-->a_
  ab--"get(b)"-->a_
  ba--"get(a)"-->b_
  bb--"get(b)"-->b_

Pour LIFO maintenant :

graph TB;
  vide("(-, -)")
  
  vide--"put(a)"-->a
  vide--"put(b)"-->b
  a--"put(a)"-->aa
  a--"put(b)"-->ba
  b--"put(a)"-->ab
  b--"put(b)"-->bb
  
  a--"get(a)"-->vide
  b--"get(b)"-->vide
  aa--"get(a)"-->a
  ab--"get(a)"-->b
  ba--"get(b)"-->a
  bb--"get(b)"-->b

Avec des boîtes là (la S2 est la même qu’avant) :

graph TB;
subgraph S2
  a(a)
  b(b)
  id("-")
  a--"get(a)"-->id
  b--"get(b)"-->id
  id--"put(a)"-->a
  id--"put(b)"-->b
end
subgraph S1
  vide["-"]
  x[x]
  vide--"put_g(x)<br>put_d(x)"-->x
  x--"get_g(x)<br>get_d(x)"-->vide
end

Autrement dit :

On a donc :
\tau_{a} = \text{put(x) = get\_d(x) et }\tau_{b} = \text{get(x) et put\_d(x)}

graph LR;
  vide("(-, -)")
  x_("(x, -)")
  _x("(-, x)")
  xx("(x, x)")

  vide--"put_g(x)"--> x_
  x_ --"get_g(x)"--> vide
  x_ --"Tau_a"--> _x
  _x --"Tau_b"--> x_
  _x --"put_g(x)"--> xx
  xx --"get_g(x)"--> _x

Cours et TD du 05/10/2023

Équivalence

Plusieurs méthodes :

• On regarde ce qui est observable de l’extérieur des systèmes et on compare si c’est la même (c’est ce qu’on a fait au Cours 1)
• On peut vérifier si les deux systèmes comparés sont capables de faire les mêmes actions, dans les deux sens. Il suffit d’un chemin permettant l’équivalence pour avoir une équivalence. (simulation, exemple : A puis B, puis A, puis B…)
• On peut vérifier en faisant comme le point précédent, mais on peut faire une simulation depuis n’importe quel graphe, c’est-à-dire, on peut faire avancer n’importe quel système en premier tant que l’autre répond (bisimulation, exemple : A, puis B, puis B, puis A)

Relation de simulation

Soit un système donné : S = (Q, \Delta, \Sigma)
On a : R \subseteq Q\times Q la simulation SSI \forall a \in \sigma, \forall q_{1}' \in Q_{1}, q_{1} \xrightarrow[\qquad\Sigma]{a} q_{1}' \RA \exists q_{2}' \in Q, q_{2} \xrightarrow[\qquad\Sigma]{a} q_{2}' et (q_{1}', q_{2}')\in R
Aussi, q \subseteq q' SSI \exists R une simulation (q, q') \in R
q \backsimeq_{sim} q' SSI q \subseteq q' et q' \subseteq q

Relation de bisimulation

Soit un système donné : S = (Q, \Delta, \Sigma)
On a : R \subseteq Q\times Q la simulation SSI \forall a \in \Sigma, \forall q_{1}' \in Q_{1}, q_{1} \xrightarrow[\qquad\Sigma]{a} q_{1}' \RA \exists q_{2}' \in Q, q_{2} \xrightarrow[\qquad\Sigma]{a} q_{2}' et (q_{1}', q_{2}')\in R et \forall q_{2}' \in Q_{2}, q_{2} \xrightarrow[\qquad\Sigma]{a} q_{2}' \RA \exists q_{1}' \in Q, q_{1} \xrightarrow[\qquad\Sigma]{a} q_{1}' et (q_{2}', q_{1}')\in R
Aussi, q \subseteq q' SSI \exists R une bisimulation (q, q') \in R
q \backsimeq_{bisim} q' SSI q \subseteq q' et q' \subseteq q

Réseau de Petri

Exemple

Soit 2 étudiants, ils travaillent dans une salle et à un instant t ils prennent une clé pour entrer dans une salle dortoir et se reposer, il n’y a qu’une place dans le dortoir. Ensuite l’étudiant revient dans la salle de travail.

Définition

Soit un réseau de Petri R : R(P, T, \Delta) avec ensemble de place P, de transition T et relation reliant les places et les transitions \Delta, donc \Delta \subseteq P\times T \cup T\times P.

Un marquage

Fonction qui associe à chaque place sa valeur : soit le marquage M : P \ra \N
Soit \triangleright une relation de transition entre marquages
\forall M_{1}, M_{2} des marquages de R
M_{1}\triangleright M_{2} SSI \exists t\in T : M_{1} \triangleright_{t} M_{2}

Notation

Soit t \in T (une transition)
^{\bullet}t = \{p\in P | (p, t) \in \Delta \}
t^{\bullet} = \{p\in P| (t, p) \in \Delta \}

Donc

M_{1} \triangleright_{t} M_{2} SSI

1. \forall p \in \ ^{\bullet}t, M_{1}(p) > 0
2. \forall p \in P \begin{cases} M_{1}'(p) = M_{1} (p) - 1 \text{ si } p \in \ ^{\bullet}t \\\\ M_{1}'^{(p)}= M_{1}(p) \text{ sinon} \end{cases}
   alors :
   \forall p \in P \begin{cases} M_{2}'(p) = M_{2} (p) + 1 \text{ si } p \in t^{\bullet} \\\\ M_{2}'^{(p)}= M_{2}(p) \text{ sinon} \end{cases}
   

Accessibilité

\triangleright = \underset{t \in T}{U} \triangleright_{t} \triangleright^{\*} = \underset{i\geqslant 0}{U}\triangleright^{i} \begin{cases}\triangleright^{0} = Id \\\\ \triangleright^{i+1} = \triangleright^{i}\circ\triangleright\end{cases}
Relation d’accessibilité par un chemin dans le graphe des marquages : \text{Acc}(M) = \{M' | M \triangleright^{*}M'\}

Boucle infinie : P_{1}, P_{2} \ra (1, 0) \ra (1, 1) \ra (1, 2) \ra \dots

• K \in \N
• Un réseau est K-borné pour un marquage initial M_{init} SSI \forall M \in \text{Acc}(M_{init}), \forall p \in P : M(p) \leqslant K

Lecture et écriture

Modélisation d’un lecteur et un écrivain :

Modélisation de deux lecteurs et un écrivain :

Modélisation d’un producteur/consommateur avec buffer :

Cours et TD du 12/10/2023

Comment connaître si un réseau est borné ou non ?

La création de jeton permet de créer un réseau non borné.

Rappel : Soit N places dans le réseau, p_{1} \dots p_{N} est le marquage.

Nombre des marquages possibles dans un réseau de Petri bornée : (K+1)^{N} avec K la borne et N le nombre de marquages.

Pour répondre à la question, voici un exemple :

On a donc :

Si M_1 et M_2 sont deux marquages :
M_{1} \leqslant M_{2} \text{ SSI } \forall p \in P \quad M_{1}(p) \leqslant M_{2}(p)
Développer le graphe de marquages :

• On part du marquage initial
• On explore les successeurs
• Traitement d’un successeur M :
  • Si \exists M' un ancêtre de M tant que M' \leqslant M alors remplacer M par M_{\omega} où :
    • M_{\omega}(p) = \omega si M'(p) < M(p)
    • M_{\omega}(p) = M(p) si M'(p) = M(p)

Rappel sur les transitions et ajout de l’arc inibiteur :

Priorité

Ordre (partiel) sur les transitions :
t_{1}< t_{2}
\forall M, a partir de M, t_{1} est exécutable uniquement si t_{2} ne l’est pas (parce que sinon on doit exécuté t_{2} et non t_{1})

Dans ce schéma, on ne veut jamais avoir les deux utilisations en même temps. On peut utiliser des priorités pour éviter ce conflit.

Le conflit est entre t_{1} rendre et t_{2} prendre.

Est-ce que c’est possible de transformer un réseau de Petri avec des arcs inhibiteurs vers un réseau de Petri avec des priorités ? Et inversement ?


Exemple pour les T-bornés : est-ce que c’est borné ?

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

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

TD du 16/11/2023
Pas de cours, car semaine de partiel

Problème du train

Un train qui va de droite à gauche et ensuite, il va de gauche à droite.
Il y a qu’un seul tunnel et qu’une seule ligne.

Cas d’un seul train

Un train va juste de gauche à droite et ne reviens pas

Il nous faut donc un sémaphore booléen pour protéger l’accès au tunnel

t (sémaphore) := 0

Processus train
begin
  P(t)
  passe
end

Cas d’un groupe de train

2 groupes de train arrivent, le tunnel est très long, ainsi si 2 trains vont dans le même sens alors, ils peuvent tous y aller, pas besoin qu’il n’y est personne dans le tunnel

tunnel (sémaphore binaire) := 1
nb_g (nombre train à gauche - int) := 0
nb_d (nombre train à droite - int) := 0
S_g (sémaphore binaire) := 1
S_d (sémaphore binaire) := 1

Processus Train_G
begin
  # Section critique 1
  Wait(S_g)
  nb_g := nb_g + 1
  if nbg_g = 1
    Wait(tunnel)
  endif
  Signal(S_g)
  # Fin section

  Traverser

  # Section critique 2
  Wait(S_g)
  nb_g := nb_g - 1
  if nbg_g = 0
    Signal(tunnel)
  endif
  Signal(S_g)
  # Fin section
end

Processus Train_D
begin
  # Section critique 1
  Wait(S_d)
  nb_d := nb_d + 1
  if nbg_d = 1
    Wait(tunnel)
  endif
  Signal(S_d)
  # Fin section

  Traverser

  # Section critique 2
  Wait(S_d)
  nb_d := nb_d - 1
  if nbg_d = 0
    Signal(tunnel)
  endif
  Signal(S_d)
  # Fin section
end

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

Sémaphores

• wait(S) : s > s-- sinon on se bloque
• signal(S) : s++ ou débloquer un processus en attente

Maintenant, supposons que l’on veut les implémenter. On doit utiliser quelque chose qui va être de plus bas niveau qui va assurer l’exclusion mutuelle, car ces primitives sont supposées atomique.

Pour implémenter ça, il faut utiliser, au plus bas niveau, quelque chose qui permet un accès atomique à une certaine variable. On a besoin de primitives de type T & S = Test and Set.

T & S d’une variable booléenne “lock”, ça revient à faire :

Test and Set(lock) {
  v := lock
  lock := true
  return v
}

qui est atomique (a.k.a offert par le matériel)

Si la valeur est 0, c’est bon, on a pris le lock et la valeur passe de 0 à 1, le prochain qui va tester va voir qu’il obtient une valeur de 1.
Donc : c’est prendre la valeur et en même temps la modifier : si elle est 0, elle passe à 1.
Si elle est à 1 : on attend ; avec ça on peut faire de l’attente active : attendre que le lock en paramètre devient 0.

Du coup, on aura un lock sur notre sémaphore S, il faut s’assurer que cela se passe de manière atomique (Test and Set).

Dans certains langages : on a une notion qui permet à une certaine section de s’exécuter de manière atomique. Alors cela passe à la charge du compilateur…

Exemple d’implémentation

l = false # le lock est libre (pas pris)

begin
  wait(S)
  done := false
  do
    # on attend le lock pour accéder à S
    # on attend que le retour de T&S soit false (l = false)
    if (¬ T&S(l)) then # quand on fait T&S on avait 0, maintenant il devient 1
      if (S>0) then # on termine la boucle, on ne cherche plus
        done := true
        S--
      endif
      l := false # lâche le lock pour que d'autres accèdes à S
    endif
  while (¬ done)
end

• Ici la queue est déjà implémentée : Attente active que S devienne positif.
• On va attendre que l’on ait le droit de décrémenter S.

Implémentation de signal(S)

• simple

Signal(S) # faut qu'il décrémente le S
# dit qu'il y a la possibilité d'incrémenter le S, il lâche le lock et s'en va
while(T&S(l)) do {}
S++
l := false

Exclusion mutuelle

• Attente active

• Attendre que quelqu’un nous réveille

• L’attente active a du sens lorsqu’on a plusieurs processus.

• D’une certaine manière, elle peut couter moins cher que le blocage d’un thread.

Cela est vrai au bas niveau.

• Mais, au niveau logique, on a plutôt envie des mécanismes qui nous permet de ne pas se tromper.
• Le sémaphore : un mécanisme de bas niveau, difficile à maitriser.
• Pour cela, il existe un autre concept, de plus haut niveau : les moniteurs.

Les moniteurs

• Disons qu’on a un certain nombre de structures qu’on veut manipuler, si ces structures sont partagées, il faudra régler tous les problèmes de synchronisation sur cette mémoire partager.

• Par exemple, le problème du producteur-consommateur avec les actions append() et take().

• Une façon simple est de programmer de manière séquentielle et faire un lock sur la structure entière avant de faire une certaine opération.

• Le problème est que cette méthode prend beaucoup de temps…

• Ce que nous voulons : deux opérations qui s’exécutent de manière atomique.

• C’est pour cette raison que les langages de programmations propose des différentes structures (piles, files, etc.) qui permette de réduire la latence (l’attente) dû à la synchronisation.

• À notre niveau, on fait de l’abstraction.

• Les moniteurs (qui est un vieux concept qui est un peu comme la POO) : c’est ce que nous donne cette notion d’atomicité élevée.
  

• C’est bien, mais ça ne suffit pas, car l’exécution d’une certaine fonction a besoin de se synchroniser avec les autres exécutions.

• Donc, il y a un mécanisme qui ressemble à wait() et signal() : blocage/réveil.

• C’est quelque chose de plus abstrait : on va se bloquer sur une condition.
  C_{1}\ C_{2}\ \dots\ C_{n}

• Disons qu’il y a un processus qui attend que quelque chose devient true, donc il va se mettre dans une file d’attente, et ensuite, le processus qui va changer la valeur à true devra réveiller le processus qui se trouve dans la file d’attente.

• Exemple : j’attends que le buffer contienne quelque chose, ainsi le processus qui va mettre quelque chose dans le buffer va devoir le réveiller.

• On peut imaginer qu’on a des files d’attentes FIFO pour chaque condition.

• Les indices des fonctions f_{1}\ f_{2}\ \dots n’ont rien à voir avec les conditions C_{1}\ C_{2}\ \dots

Différence avec les sémaphores

• Lorsqu’ils attendent, un processus arrive et fait wait. S’il ne peut pas le décrémenter, il attend.
• Lorsqu’un processus fait signal, quelqu’un d’autres peut passer. Mais il n’y a aucune supposition sur l’ordre (l’ordre dans lequel nous réveillons les processus en attente). Or, nous voulons que le réveiller soit par l’ordre.
• Sémaphore pas positif \RA je ne peux pas décrémenter \RA j’attends qu’il soit positif \RA l’ordre de l’attente n’est pas défini, en particulier l’implémentation que nous avons fait pour les sémaphores.
• Dans les moniteurs, on suppose qu’il y a FIFO. C’est-à-dire que l’on peut imaginer que chaque condition est une file d’attente. Initialement la file d’attente est vide, toujours, on réveille le processus qui a dormi le plus de temps, les files des conditions sont ordonnées (FIFO), donc on réveille les processus dans cet ordre.
• Pour un certain moniteur : a un moment donner une fonction s’exécute. La supposition qu’on fait est que l’appel des fonctions assure l’atomicité.

On peut imaginer que le moniteur lui-même a une file d’attente, et ensuite, ils entrent, un par un.

• Si le premier qui rentre est celui qui veut retirer du buffer, mais le buffer est vide \RA il va attendre, mais comme il est déjà à l’intérieur, il faut le suspendre, on va donc le mettre dans une certaine file, C_{4} par exemple. Et on passe au processus suivant.

• Or, au moment où il va réveiller le premier processus, on a un problème et cela, car il y a deux processus dans le moniteur, alors qu’on avait dit qu’il peut y avoir que 1.

• Là, on peut adopter plusieurs stratégies, par exemple que le processus qui a réveillé l’autre va céder au processus qui s’est réveillé et va revenir lorsque celui-ci va terminer.

• Dans l’hypothèse que le processus 2 à exécuter f_{2}, f_{2} n’a pas été exécuté jusqu’au bout. Donc, on obtient un mélange entre l’exécution des fonctions, mais l’exclusion mutuelle sur la structure de données qu’on veut protéger est toujours assuré.

• Ainsi, à chaque moment qu’une fonction s’exécute, mais cela ne veut pas dire qu’elle s’exécute totalement.

• Supposons même que f_{2} arrive à s’exécuter jusqu’au bout, il peut maintenant réveiller le processus 1, mais vu qu’il n’y a personne dans le moniteur, on a le choix entre le réveiller ou de faire entrer un autre processus. Or, tant qu’il y a un processus qui peut être réveillé, les processus qui se trouvent dans la file à l’extérieur, il attend.

• Un processus qui fait signal sur une condition est suspendu, jusqu’à ce que le processus réveiller termine ou alors se bloque sur une condition.

• Que ce que va se passer si ce processus réveiller va lui-même réveiller un autre processus ? il va également être suspendu. Donc, on peut avoir une chaine de processus suspendus.

• Si le processus réveiller, réveille un autre (= fait signal), ainsi, il est suspendu aussi.

• Un processus réveiller à la priorité sur un processus externe qui est en attente d’accès au moniteur.

Simulation des sémaphores avec les moniteurs

Pour ne pas mélanger les 2 types de wait et signal, pour les sémaphores, on va utiliser P() et V()
Un moniteur a une variable à l’intérieur, et on va avoir les 2 opérations P() et V()

On va définir notre moniteur Sem-simul (Sémaphore simulé). On va définir une variable et une condition.

Moniteur Sem-simul # Simulation d'un sémaphore binaire
var busy : boolean = false
var notbusy : condition

Procédure P
begin
  if busy then wait(notbusy) endif
  busy := true
end

Procédure V
begin
  busy := false
  signal(notbusy)
end

Donc, avec les moniteurs, on peut faire tout ce qu’on peut faire avec les sémaphores.

Producteur - Consommateur avec les moniteurs

• Si les 2 pointeurs se croisent : le buffer est vide
• Taille du buffer : B : lorsqu’on atteint cette borne : on s’arrête
  

On peut commencer, dans un premier temps, par un buffer infini où l’on peut toujours ajouter des éléments

• On ne s’occupe pas d’un cas ou le buffer risque d’être plein
• On a 2 fonctions à implémenter : ajouter et retirer
• Dans le moniteur, on va avoir un tableau et deux variables : int et out

Moniteur Buffer

b        : array[0, -] # tableau non borné de int
in       : integer = 0
out      : integer = 0
notempty : condition

Procédure append(v : integer)
begin
  b[in] := v
  in := in + 1
  signal(notempty) # réveiller les processus en attente (s'il y en a)
end

Procédure take : return integer # soit le buffer est non-vide : alors on peut prendre un élément
                                # soit le buffer est vide : faut bloquer le processus
begin
  if (in = out) then # si les 2 pointeurs se croisent = le buffer est vide
    wait(notempty)
  endif
  tmp := b[out]
  out := out + 1
  return tmp
end

Vu que le buffer est non borné, le seul problème que l’on doit gérer est la situation ou le buffer est vide.

Producteur - Consommateur : buffer borné

Moniteur Buffer

n        : integer = 0 # nombre d'éléments dans le buffer
notfull  : condition
b        : array[0, B] # tableau borné de 0 à B de integer
in       : integer = 0
out      : integer = 0
notempty : condition

Procédure append(v : integer)
begin
  if (n = B + 1) then # on vérifie que c'est pas plein
    # si c'est plein on attend
    wait(notfull)
  endif
  b[in] := v
  in := in + 1
  if (n = B + 1) then # si on est au bout du buffer
    # on revient au début (car buffer circulaire)
    in := 0
  endif
  n := n + 1 # on incrémente le nombre d'éléments du buffer
  signal(notempty) # réveiller les processus en attente (s'il y en a)
end

Procédure take : return integer # soit le buffer est non-vide : alors on peut prendre un élément
                                # soit le buffer est vide : faut bloquer le processus
begin
  if (n = 0) then # si les 2 pointeurs se croisent = le buffer est vide
    wait(notempty)
  endif
  tmp := b[out]
  out := out + 1
  if (out = B + 1) then # si on est au bout du buffer
    # on revient au début car buffer circulaire
    out := 0
  endif
  n := n - 1
  signal(notfull) # s'il fait `signal`, un autre processus va se réveiller et `take()`
                  # va pas faire return, lui permettant de faire return plus tard
  return tmp
end

• Sémaphore : notion de compteur
• Moniteur : J’attends / un processus me réveille : Une condition, c’est une file d’attente

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

Comment programmer en utilisant des lock, des structures de données partagées ?

Ensemble d’entiers partagés

• add(key) : ajouter l’élément key

• remove(key) : retirer l’élément key

• contains(key) : boolean : Si l’élément key existe dans l’ensemble ou pas

• Il faut régler la synchronisation : l’accès à la structure de données

• On va choisir une représentation par liste chainée.

• Une liste ordonnée : ça simplifie la recherche d’un élément, notamment pour l’enlever de l’ensemble.

• Et on va avoir deux pointers particuliers : head, tail.

• Supposons qu’on a une solution complètement séquentielle. C’est-à-dire : chaque opération s’exécute seul, il n’y a aucune concurrence.
• Si je prends ce cas qu’on connait bien, on peut faire une version concurrente en ajoutons un lock sur la structure. Un processus qui vient va se battre pour le lock, cela est appelé Coarse-gain locking (le “gain-grossier”)
• On va supposer comme structure des nœuds Node :

type Node {
  int key;
  Node next;
}

Coarse-gain locking (le “gain-grossier”)

On va écrire une première fonction ajouter, on lui donne un certain key, qui est un entier. Il y a toujours au moins 2 Node : début et fin. Chaque élément existe dans la liste au plus une fois (l’occurrence d’un élément est 0 ou 1).

Procédure add(key : integer) return boolean
begin
  Node pred # prédécesseur
  Node curr # séquenceur
  lock(l) # on prend le lock
  try
    pred := head
    curr := pred.next
    while (curr.next < key) # rappel : key = le paramètre
      pred := curr # le prédécesseur devient le courant
      curr := curr.next # le courant devient le sucesseur
    endwhile
    if (key = curr.key) then # l'élément est déjà dans l'ensemble
      return false # on veut pas avoir de duplications
    else
      Node node = Node(key) // Création d'un nouveau noeud
      node.next := curr
      pred.next := node
      return true # tout s'est bien passé
    endif
  finally
    unlock(l) # on lâche le lock
  endtry
end


Procédure remove(key : integer) return boolean
begin
  Node pred # prédécesseur
  Node curr # séquenceur
  lock(l) # on prend le lock
  try
    pred := head
    curr := pred.next
    while (curr.next < key) # rappel : key = le paramètre
      pred := curr # le prédécesseur devient le courant
      curr := curr.next # le courant devient le sucesseur
    endwhile
    if (key = curr.key) then # on a trouvé l'élément
      pred.next := curr.next
      return true
    else
      return false # l'élément n'existe pas
    endif
  finally
    unlock(l) # on lâche le lock
  endtry
end

Inconvénient

L’ajout d’un élément à un emplacement X ne doit pas empêcher l’ajout d’un élément dans une autre zone

Fin-gain locking (plus locale)

• Je lâche a que lorsque je prends c… à chaque fois, j’ai donc 2 locks sur 2 éléments
• Quand je commence à traverser la liste, c’est possible qu’il y ait un processus plus loin que nous, on est tous les deux sur la liste, je ne l’attends pas
• Si un processus arrive, et un autre processus fait une opération devant lui, il doit attendre, il ne peut pas le dépasser.

Procédure add(key : integer) return boolean
begin
  lock(head) # verrou sur la tête de liste
  Node pred = head
  try
    curr := pred.next
    lock(curr) # à ce stade on lock sur l'élément `head` et le suivant
    try
      while (curr.next < key) # on fait la recherche, pendant la recherche on va déplacer nos locks
        unlock(pred)
        pred := curr # le prédécesseur devient le courant
        curr := curr.next # le courant devient le sucesseur
        lock(curr)
      endwhile
      if (key = curr.key) then # l'élément est déjà dans l'ensemble
        return false # on veut pas avoir de duplications
      endif
      Node node = Node(key) // Création d'un nouveau noeud
      node.next := curr
      pred.next := node
      return true # tout s'est bien passé
    finally
      unlock(curr) # on lâche le premier lock
    endtry
  finally
    unlock(pred) # on lâche le second lock
  endtry
end


Procédure remove(key : integer) return boolean
begin
  lock(head) # verrou sur la tête de liste
  try
    Node pred = head
    curr := pred.next
    lock(curr) # à ce stade on lock sur l'élément `head` et le suivant
    try
      while (curr.next < key) # on fait la recherche, pendant la recherche on va déplacer nos locks
        unlock(pred)
        pred := curr # le prédécesseur devient le courant
        curr := curr.next # le courant devient le sucesseur
        lock(curr)
      endwhile
      if (key = curr.key) then # on a trouvé l'élément
        pred.next := curr.next
        return true # tout s'est bien passé
      else
        return false # l'élément n'existe pas
      endif
    finally
      unlock(curr) # on lâche le premier lock
    endtry
  finally
    unlock(pred) # on lâche le second lock
  endtry
end

Comment ça marche ?

• Maintenant, pour contains(key), on fait la même chose (comme la partie de remove(key) où on cherche l’élément).
• Donc, il faut avoir les 2 lock pour assurer que le résultat est correct.

On est toujours obligé de prendre les lock dans un certain ordre, comment on fait ?

• Par exemple, si add() prend les lock dans le sens qui prend, etremove() prend les lock dans l’autre sens ?

• Si add() veut insérer un élément, il va prendre head, et ensuite aller prendre le 2ᵉ élément, mais s’il commence par prendre d’abord le lock sur le 2ᵉ élément, et l’autre processus commence par prendre le lock sur le head \RA blocage.

• Quand ils prennent les lock dans le même ordre : aucun problème !

• On ne peut pas se dépasser : Lorsqu’un processus fait une recherche, les processus qui se trouvent derrière lui, ne peuvent pas le dépasser : on a une sorte de file d’attente (rajoutant donc du temps pour exécuter des programmes).

• Ainsi, si on essaie d’optimiser l’utilisation des locks, faire moins de synchronisation, qu’est-ce qu’on peut faire ?

• Si je “fonce” sur la structure, sans prendre de lock, et je veux retirer l’élément i, et je prends les lock que lorsque j’arrive à i. Quel est le problème ?

De manière plus générale, pendant que je me trouve à l’emplacement i, il y a d’autres processus qui peuvent venir et supprimer tous cette partie de la liste : par exemple, avant même d’avoir pris le lock, il y a un processus qui change le panorama, donc lorsqu’on va prendre le lock, tout le monde a déjà changé, ainsi c’est possible que je travaille sur une liste qui n’existe même plus (éléments plus accessibles à partir du head).

Dans l’exemple suivant, on veut retirer l’élément curr, mais un autre processus peut venir et faire lock sur le prédécesseur de pred, mais alors, lorsque ce processus lâche les locks, j’arrive à faire lock, mais je ne suis
pas au courant que la liste à changer. Je retire curr, et ainsi quand je fais return true, la signification est que l’opération a réussi même si c’est faux.

Donc, l’idée de “foncer”, faire lock et effectuer l’opération, c’est une bonne idée. Mais cela ne suffit pas, car entre le moment de la recherche et le moment du lock, il se passe des choses qui peuvent modifier notre liste.

Alors qu’est-ce qu’il faut vérifier ?

• Il faut voir si l’environnement des pointers pre et curr a changé entre le moment où j’ai vu l’élément et le moment où j’ai pris les lock.
• Comment voir si “ma” partie dans la liste n’est plus accessible ? Reparcourir la liste en repartant du head, si un processus a modifié la liste et a coupé “notre” partie de la liste du head, on va pouvoir identifier ça.

Procédure add(key : integer) return boolean
begin
  while true
    pred := head
    curr := pred.next
    while (curr.next < key)
      pred := curr # le prédécesseur devient le courant
      curr := curr.next # le courant devient le successeur
    endwhile
    # C'est que lorsqu'on arrive qu'on prend les locks
    lock(pred)
    lock(curr)
    try
      if validate(pred, curr) # on regarde la situation
        if (key = curr.key) # si l'élément est déjà dans l'ensemble
          return false # on veut pas avoir de duplication
        else
          Node node := Node(key) # création d'un nouveau noeud
          node.next := curr
          pred.next := node
          return true # tout s'est bien passé
        endif
      endif
    finally
      # On lâche les locks
      unlock(pred)
      unlock(curr)
    endtry
  endwhile
end


# Regarde si la structure n'a pas changer
Procédure validate(pred : Node, curr : Node) return boolean
begin
  node := head
  while (node.key <= pred.key)
    if (node = pred)
      # Si je suis arriver a pred, je regarde que la situation n'a pas changé
      return (pred.next = curr)
    endif
    node := node.next
  endwhile
  # Si on a dépassé pred, pred n'est plus accessible
  return false
end


Procédure remove(key : integer) return boolean
begin
  while true
    pred := head
    curr := pred.next
    while (curr.next < key)
      pred := curr # le prédécesseur devient le courant
      curr := curr.next # le courant devient le sucesseur
    endwhile
    # C'est que lorsqu'on arrive qu'on prend les locks
    lock(pred)
    lock(curr)
    try
      if (validate(pred, curr)) # on regarde la situation
        if (key = curr.key) # on a trouvé l'élément
          pred.next := curr.next
          return true # tout s'est bien passé
        else
          return false # l'élément n'eexiste pas
        endif
      endif
    finally
      # On lâche les locks
      unlock(pred)
      unlock(curr)
    endtry
  endwhile
end


Procédure contains(key : integer) return boolean
begin
  while true
    pred := head
    curr := pred.next
    while curr.next < key
      pred := curr # le prédécesseur devient le courant
      curr := curr.next # le courant devient le successeur
    endwhile
    # C'est que lorsqu'on arrive qu'on prend les locks
    lock(pred)
    lock(curr)
    try
      if (validate(pred, curr)) # on regarde la situation
        return (key = curr.key)
      endif
    finally
      # On lâche les locks
      unlock(pred)
      unlock(curr)
    endtry
  endwhile
end

boolean validate(Node pred, Node curr) On vérifie quoi ? Problèmes possibles ?

• Ma zone devient inaccessible.
• Il se peut que j’arrive jusqu’à pred, sauf qu’avant, pred pointé sur curr mais maintenant un processus à changer ce pointer et donc à ce moment la pred n’est plus le prédécesseur de l’élément courant.

Comme je fais le validate après avoir pris les lock, les choses ne risquent pas de changer. Si la validation ne marche pas (la fonction retourne false) : on lâche les lock et on revient à la ligne while true pour essayer à nouveau. Notre approche dans ce code est optimiste, donc on commence sans prendre les lock.

Cours du 07/12/2023
J’ai séché le TD sorry not sorry 🤓
C’est un peu un détail du cours 8.

Ensemble en concurrence

Opération atomique sur les assignations et le programme ne meurt pas en zone critique.

Tentative 1

flag : array[0, 1] of bool # le prof parle d'array mais + voir ça comme un dict
                           # où {0: false, 1: false} et les clés sont les 2 threads

Procédure lock
begin
  i := ThreadID.get()
  flag[i] := true
  j := 1 - i
  while (flag[j]) # attends
  endwhile
end

Procédure unlock
begin
  i := ThreadID.get()
  flag[i] := false
end

Procédure main
begin
  x.lock()
  # zone critique
  x.unlock()
rend

Exclusion mutuelle

Ok

Blocage

Oui, les opérations dans lock ont beau être atomique, lock en tant que telle ne l’est pas, alors si deux fonctions appellent lock en même temps, ils vont se bloquer.

Tentative 2

victim : int

Procédure lock
begin
  i := TheadID.get()
  victim := i
  while (victim = i) # tant que je suis la victime, j'attend
  endwhile
end

Procédure unlock
begin
end

Procédure main
begin
  x.lock()
  # zone critique
  x.unlock()
end

Blocage

Blocage tout seul, en plus on ne peut pas prendre 2x la ressource à la suite, car on est dépendant d’un autre processus pour être libéré.

Synthèse

• On veut déclarer que l’on a envie d’entrer
• On veut donner une priorité, un tour de rôle

flag : array [0, 1] of bool # le prof parle d'array mais + voir ça comme un dict
                            # où {0: false, 1: false} et les clés sont les 2 threads
victim : int

Procédure lock()
begin
  i := ThreadID.get()
  j := 1 - i
  flag[i] := true
  victim := i
  while (flag[j] && victim = i) # je suis intéressé + la victime
  endwhile
end

Procédure unlock()
begin
  i := ThreadID.get()
  flag[i] := false
end

Procédure main()
begin
  x.lock()
  # zone critique
  x.unlock()
end

Exclusion mutuelle

Oui

Blocage

Non

Famine

Non, liste FIFO 😎

Avec n threads

n thread 0..(n-1)
level  : array [0..n-1] of int{0} # tous initialisés à 0
victim : array [0..n-1] of int    # identité des threads

Procédure lock
begin
  curr := ThreadID.get() # thread courant
  for(i = 1 ; i < n ; i++)
    level[curr] := i
    victim[i] := curr
    # logique de comment passer d'un niveau à l'autre
    while (∃k != curr (level[k] >= i && victim[i] = curr)) # il existe quelqu'un différent de moi
                                                           # qui est devant moi
                                                           # ET je suis la victime
    endwhile
  endfor
end

Procédure unlock
begin
  curr := ThreadID.get()
  level[curr] := 0
end

Exclusion mutuelle

Oui, car les threads ferment la porte à ceux qui sont derrière lui dans l’array.

Blocage

Oui, c’est une généralisation de la seconde tentative \RA merci la victim

Famine

Non, liste FIFO (≧◡≦)

\RA cf. Cours 5