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.