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