Systèmes à mémoire partagée

Objectifs :Présentation du modèle à mémoire partagée de la programmation parallèle : section critique, exclusion mutuelle, sémaphores, processus légers en O'Caml

Généralités

On s'intéresse à deux grands modèles de programmation parallèle (ou simultanée) qui sont : les systèmes à mémoire partagée et les systèmes répartis (à mémoire répartie) que l'on étudiera au prochain cours. Chaque modèle met en valeur plusieurs notions fondamentales et étudie leurs relations. Les notions les plus importantes sont :

• la séquentialité (dépendance causale) : une instruction s'exécute après une autre;
• la concurrence (indépendance causale) : plusieurs instructions s'exécutent en "même temps";
• le non-déterminisme (une cause peut avoir plusieurs effets, mutuellement exclusifs) : un même programme ne termine pas ou termine en produisant des résultats différents;
• la synchronisation (plusieurs causes indépendantes doivent s'être produites avant que l'effet puisse avoir lieu) : attente d'une condition sur plusieurs processus;
• la communication (transfert d'informations) : envoi et réception d'informations d'un ou plusieurs processus à un ou plusieurs processus.

Systèmes à mémoire partagée

On considère un ensemble $S$ de processus séquentiels $P$_i interagissant sur une mémoire commune (ou partagée) que l'on note $S\; =\; [\; P$₁ &thicksp; || ... || &thicksp; P_n ] . Ces processus peuvent être aussi bien physiquement indépendants (un processus correspond à un processeur) que simulés logiquement par un unique processeur (comme les Threads en O'Caml).

La communication dans ce modèle est implicite. L'information est transmise lors de l'écriture dans une zone de la mémoire partagée, puis quand un autre processus vient lire cette zone. Ce mécanisme est asynchrone, i.e. il ne nécessite pas que le récepteur soit prêt à écouter l'émetteur. Par contre la synchronisation doit être explicite, en utilisant des instructions élémentaires.

Sans synchronisation explicite, le résultat d'un programme est imprévisible. Par exemple, soit l'ensemble $S$ de processus (avec $x$ valant 0) défini ainsi : $S\; =\; [\; x:\; =\; x\; +\; 1;\; x\; :=\; x\; +\; 1\; ||\; x\; :=\; 2\; *\; x]$. Après l'exécution de $S$, $x$ peut valoir 2,3, ou 4.

La synchronisation la plus simple est l'attente d'une condition. On la note wait b, où $b$ est une expression booléenne. Un processus ne peut exécuter cette instruction que si $b$ est vraie. En reprenant l'exemple précédent :
$S\; =\; [\; x:\; =\; x\; +\; 1;\; x\; :=\; x\; +\; 1\; ||\; wait(x=1);x\; :=\; 2\; *\; x]$on obtient comme valeur pour $x$ que 3 ou 4. Par contre il est possible que le second processus reste bloqué s'il n'a testé $x$ que pour les valeurs $0$ ou $2$.

Cela amène le problème de l'atomicité. Il peut être utile de manipuler l'atomicité de manière explicite. L'instruction await b do P attend que la condition $b$ soit vraie pour exécuter les instructions de $P$ de manière atomique dans le même état mémoire que le test de $b$.

Section critique, exclusion mutuelle

On appelle section critique une ressource qui ne doit être utilisée que par un processus au plus. Par exemple, on désire qu'un seul processus puisse utiliser une imprimante. C'est le cas du système Unix qui gère une queue d'impression sur les périphériques d'impression.

Pour cela les processus doivent s'exclure mutuellement de la section critique. On dit que l'activité $A$₁ du processus $P$₁ et l'activité $A$₂ du processus $P$₂ sont en exclusion mutuelle lorsque l'exécution de $A$₁ ne doit pas se produite en même temps que celle de $A$₂ .

Le problème de l'exclusion mutuelle, dans un cas simple de deux processus, n'est pas si évident que cela. L'algorithme de Dekker est une solution qui fonctionne. Il utilise une variable globale turn que chaque processus peut consulter et changer dans la section critique.

let turn = ref 1;;
let c = Array.create 2 1;;

let crit i = ();;                  (* action dans la section critique *)
let suite i = ();;                 (*        hors section critique    *)

let p i =
  while true do 
  begin
    c.(i)<-0;                       (* desire entrer dans la section critique *)
    while c.((i+1) mod 2) = 0 do    (* tant que l'autre processus
                                        desire aussi entrer dans la section critique *)
      if !turn = ((i+1) mod 2) then (* si c'est au tour de l'autre *)
      begin
        c.(i)<-1;                              (* abandon *)
        while !turn = ((i+1) mod 2) do done;   (* et attente de son tour *)
        c.(i)<-0                               (* puis reprise *)
      end;
    done;
    crit i;
    turn := ((i+1) mod 2);          (* passe le droit \`a l'autre processus *)
    c.(i)<-1;                       (* remise \`a 1 : sortie de la section critique *)
    suite i
  end;;

(* initialisation *)
c.(0)<-1;;
c.(1)<-1;;
turn:=1;;

(* lancement des processus *)

Thread.create p 0;;
Thread.create p 1;;

Les processus indiquent leur volonté d'entrer dans la section critique en mettant à $0$l'élément de tableau $c$ les concernant. Après avoir marqué son élément de tableau le processus va regarder si l'autre processus est dans le même état (volonté d'entrer dans la section critique). Si ce n'est pas le cas, il entre dans la section critique, sinon il doit consulter l'arbitre ($turn$) qui indique à qui est le tour. Cet arbitre ne peut être modifié que dans la section critique (ici à la sortie). De ce fait, seul le processus étant entré dans la section critique modifiera l'arbitre à la fin de son travail en lui indiquant l'autre processus.

Sémaphores

Un sémaphore est une variable entière $s$ ne pouvant prendre que des valeurs positives (ou nulles). Une fois $s$ initialisé, les seules opérations admises sont : $wait(s)$ et $signal(s)$, notées respectivement $P(s)$ et $V(s)$. Elles sont définies ainsi :

• $wait(s)$ : si $s\; >\; 0$ alors $s\; :=\; s\; -1$ ( ), sinon l'exécution du processus ayant appelé $wait(s)$ est suspendue.
• $signal(s)$ : si un processus a été suspendu lors d'une exécution antérieure d'un $wait(s)$ alors le réveiller, sinon $s\; :=\; s\; +\; 1$.

$s$ correspond au nombre de ressources d'un type donné.

remarques

Un sémaphore ne prenant que les valeurs $0$ ou $1$ est appelé sémaphore binaire.

Les primitives $wait(s)$ et $signal(s)$ s'excluent mutuellement si elles portent sur le même sémaphore (l'ordre n'est donc pas connu).

La définition de signal ne précise pas quel processus est réveillé s'il y en a plusieurs.

On peut utiliser les sémaphores pour l'exclusion mutuelle. Les deux processus p 1 et p 2 sont exécutés en parallèle grâce à la bibliothèque de threads d'OCaml.

let s = ref 1;;

let p i =
  while true do
  begin
    wait(s);
    crit();
    signal(s);
    suite()
  end
;;

Thread.create p 1;;
Thread.create p 2;;

Dans cet exemple, si un processus veut entrer en section critique, il entrera en section critique si :
- il n'y a que 2 processus (si $P$₁ est suspendu alors $P$₂ est en section critique;
- si aucun processus ne s'arrête en section critique (si $P$₂ est dans crit alors il exécutera $signal(s)$.

Cette vérification ne fonctionne plus à partir de 3 processus. Il peut y avoir privation si le choix du processus se fait toujours en faveur de certains processus. Par exemple, si le choix s'effectue toujours en faveur du processus d'indice le plus bas, $P$₁ et $P$₂ pourraient se liguer pour se réveiller mutuellement, $P$₃ étant alors indéfiniment suspendu.

Le classique "dîner des philosophes"

Le "dîner des philosophes", du à Dijkstra, illustre les différents pièges du modèle à mémoire partagée.

L'histoire se passe dans un monastère reculé où 5 moines se consacrent exclusivement à la philosophie. Ils passeraient bien tout leur temps à la réflexion s'ils ne devaient manger de temps en temps. La vie d'un philosophe se résume en une boucle infinie : penser - manger. Ils possèdent une table commune ronde. Au centre se trouve un plat de spaguettis qui est toujours rempli. Il y s 5 assiettes et cinq fourchettes. Le philosophe qui veut manger sort de sa cellule, s'assoit à table, mange et retourne ensuite à ses pensées. Les spaguettis sont si enchevétrés qu'il faut deux fourchettes pour pouvoir les manger. Un philosophe ne peut utiliser que les deux fourchettes autour de son assiette.

Les problèmes posés sont :

• l'interblocage : chaque philosophe tient une fourchette et attend qu'une autre se libère;
• privation (ou famine) : un philosophe n'arrive jamais à obtenir 2 fourchettes.

Threads en O'Caml

La bibliothèque de threads (processus légers) d'O'Caml permet la programmation concurrente de processus pour un système à mémoire partagée. La communication s'effectue par modification des structures de données communes ou à travers des canaux de communications. On s'intéresse à la première approche. Cette bibliothèque ne peut s'utiliser qu'avec le compilateur en ligne dans sa version byte-code. Comme cette bibliothèque simule logiquement les processus par un seul programme, il ne faut pas attendre des gains de performance, mais seulement un gain d'expressivité du langage. Cette présentation est simplifiée dans la mesure où elle ne s'intéresse pas aux synchronisation d'écriture et de lecture, nis aux communications via les canaux.

les primitives importantes

module Thread

• create f a crée le processus de l'application de f sur a;
• self () retourne le processus courant et id t son identificateur.
• exit () termine le processus courant et kill t le processus indiqué.

module Mutex

• create () crée un verrou d'exclusion mutuelle (mutex);
• lock m capture un "mutex",try_lock m capture si possible un verrou, retourne true si cela est fait et false sinon, et unlock libère un verrou.

module Condition

• create () crée une variable condition;
• wait c m libère m et suspend le processus appelant sur la variable condition c, signal c réveille un des processus suspendus sur la variable condition c, et broadcast c réveille tous les processus suspendus sur c.

Une solution pour le dîner

En utilisant la bibliothèque des processus légers de O'Caml, voici une solution nai"ve pour le dîner des philosophes :

let forks = Array.create 5 (Mutex.create());;
let i = ref 0 in
  Array.iter (fun x -> forks.(!i) <- Mutex.create(); incr i) forks;;

let think i = print_string (string_of_int(i)^" pense");print_newline();;
let eat i =  print_string (string_of_int(i)^" mange");print_newline();;

let philo i =
  print_string "debut du philosophe "; print_int i;print_newline();
  while true do
    think i;
    Mutex.lock(forks.(i));
    Mutex.lock(forks.((i+1) mod 5));
    eat i;
    Mutex.unlock(forks.(i));
    Mutex.unlock(forks.((i+1) mod 5))
  done
;;

List.iter (Thread.create philo) [0;1;2;3;4];;
while true do () done;;

Cette solution pose un problème d'interblocage, si tous les philosophes prennent leur fourchette droite "en même temps" ils restent en attente de la fourchette gauche.

Une solution serait de limiter la salle à manger à au plus quatre philosophes. Pour cela, il faut ajouter un sémaphore sur la salle à manger de capacité 4 au maximum.

On simule le sémaphore par les variables room et mutex_room qui correspondent respectivement à un compteur en zone critique.

let forks = Array.create 5 (Mutex.create());;
let i = ref 0 in
  Array.iter (fun x -> forks.(!i) <- Mutex.create();incr i) forks;;

let room = ref 0;;
let mutex_room = Mutex.create();;

let think i = print_string (string_of_int(i)^" pense");print_newline();;
let eat i =  print_string (string_of_int(i)^" mange");print_newline();;

let philo i =
  print_string "debut du philosophe "; print_int i;print_newline();
  while true do
    think i;
    Mutex.lock mutex_room;
    if !room < 4 then 
    begin
      room := !room +1;
      Mutex.unlock mutex_room;
      print_string ("avec " ^string_of_int (i)^ " on est "^(string_of_int !room));
      print_newline();
      Mutex.lock(forks.(i));
      Mutex.lock(forks.((i+1) mod 5));
      eat i;
      Mutex.unlock(forks.(i));
      Mutex.unlock(forks.((i+1) mod 5));
      Mutex.lock mutex_room;
      room := !room - 1
    end;
    Mutex.unlock mutex_room
  done
;;

List.iter (Thread.create philo) [0;1;2;3;4];;
while true do () done;;

Relations entre threads

Les différentes threads d'un programme peuvent être en relation selon l'un des 4 modèles suivants :

• sans relations
• en relation mais sans synchronisation
• en relation avec exclusion mutuelle
• en relation avec exclusion mutuelle et communication (wait/signal

un producteur/consommateur

Cet exemple décrit un producteur/consommateur. Le programme principal comporte un "producteur" et 3 clients. Le producteur envoie des produits dans une boutique qui seront pris par les clients. Le stockage de la boutique étant limité, le producteur devra attendre qu'il y ait une place libre pour déposer son produit. Si ce n'est pas le cas, il se met en attente (wait) d'un signal indiquant une modification de l'état de la boutique. De même un client attendra qu'il y ait au moins un produit pour pouvoir le prendre. Dans tout les cas la boutique correspond à la zone d'exclusion mutuelle : on ne peut pas déposer ou prendre en même temps un produit.

verbatim19

Autres lectures

Ce cours s'inspire des documents suivants :

• ``Processus Concurrents'', Ben Ari, Masson 1986;
• ``Concurrent Programming : Principles and practices'', G. Andrews, Benjamin Cumming, 1991;
• Sémantique du parallélisme : un tour d'horizon en PostScript compressé de Luc Bougé.
• Le cours de Jean-Jacques Levy à l'X sur concurrence et mémoire partagée
• La page de Concurrent ML extension de SML/NJ.