Cours 8 : Programmation concurrente

Exemple introductif

int i = 0;

void * toto(void *arg){
  while (1) printf ("%d\n", i++);
}

Dans ce contexte :

processus ~ thread

Situation :

  • un thread produit des données, un autre consomme les données produites ⟶ doivent communiquer

  • un processus ne doit pas être interrompu pendant exécution critique :

    • ex: interruption matérielle du clavier qui se déclenche : mémoire du périphérique clavier = très limitée ⟹ interruption immédiate nécessaire, pour ne pas perdre ce qui est en mémoire.

Ex :

On a une BDD de noms/prénoms :

nom prénom
Doe John
Doe Jane

et une variable contenant le nombre de personnes inscrites

v = 23

On souhaite interdire l’accès à la v directement : on veut pouvoir modifier v que quand on a supprimé une entrée dans la base.

Sections critiques

On a $n$ processus/unités d’exécution contenant chacun des sections critiques.

On veut qu’un seul processus au plus accède à ces sections critiques.

Solution 1 : Algo de Peterson

Important : la mémoire partagée n’est que d’un bit, pour simplifier.

Sinon, avec plusieurs processeurs, on peut modifier un octet simultanément (pas sur le même bit).

On utilise trois vairables :

flag[0], flag[1], victim pour gérer les conflits.

l i ($∈ \lbrace 0, 1 \rbrace$) : numéro du processus actif

int flag[2];
int autre = 1-i;
flag[i]=1;
victim = i; // si jamais il y a conflit, c'est i la victime

while (victim ==i && flag[autre]); // condition jamais vraie pour les deux processus en même temps

// section critique

flag[i]=0; // i a fini : il laisse la main

NB :

  • on fait l’hypothèse qu’un processus qui rentre termine toujours sa section critique.

  • on généraliser l’algorithme précédent à $n$ processus : algorithme de Peterson

  • c’est “juste”, dans le sens où celui qui attendait (la victime) est la première à avoir la main, dès que l’autre a terminé, aussi rapide soit-il pour “reprendre la main” (l’autre).

Solution 2 : Sémaphores

Les processus “se battent” pour obtenir un créneau partagé.

3 opérations :

  • init(n) : initier $n$ créneaux initiaux

  • wait : tant que le compteur est nul, attendre. Sinon, le décroître.

    • attention : on ne veut aucune interruption entre l’instant où le compteur ne vaut plus 0, et l’instant où on le décrémente.
  • post : incrémenter le compteur.
wait()
  while (n)
    bloquer interruptions
    if n>0:
      n-=1
      déloquer les interruptions
      return

  débloquer les interruptions

En C, compiler avec l’option pthread.


int i =0;
pthread_t thr[3];
sem_t s;

void *thread(void *parm)
{
int nr = (int)parm;
while(1){
  printf("(%d) I want to enter...\n", nr);

  sem_wait(&s);

  printf("(%d) I'm in ! Going to waste some time.... \n", nr);

  sleep(4);

  sem_post(&s);

  printf("(%d) I'm out... \n", nr);

  sleep(8);

}



}

int main(){
  sem_init(&s, 0, 1);
  pthread_create(thr, NULL, thread, (void*)1);
  pthread_create(thr+1, NULL, thread, (void*)2);
  pthread_create(thr+2, NULL, thread, (void*)3);

  while (1){ sleep(20); }

}

init(s, 0);
processus_1{
  générer(d);
  post(s);
}

processus_2{
  wait(s);
  consommer(d);
}

init(s, 0);
while(1){
  générer(d);
  post(s);
}

while(1){
  wait(s);
  consommer(d);
}

⟹ ça ne marchera pas toujours : ça dépend de la structure de données (ex: pour une pile : dépend de sa capacité).

⟶ à éviter.

init(s, 0);
init(t, 1);

while(1){
  wait(t);
  générer(d);
  post(s);
}

while(1){
  wait(s);
  consommer(d);
  post(t);
}

Si on veut $n$ créneaux disponibles :

on remplace init(t, 1); par init(t, n);

sem_unlink("str") :

libère une sémaphore

Les sémaphores nécessitent une forme “d’autorité centrale” : en l’occurrence, le noyau.

⟶ comment faire quand il n’y a pas cette “autorité” ?

  • Ex : en peer-to-peer

⟶ il y a “élection” d’un “processus leader” qui prend la décision à un instant $t$.

Élire un processus leader

Chaque processus a un identifiant unique

  • Ex : adresses MAC dans un réseau
digraph {
  1 -> 2;
  2 -> 3;
  3 -> 4;
  4 -> 1[label="envoie des messages à"];
}

Supposons d’abord que tous les processus ont la même vitesse d’exécution.

  • On fait plusieurs tours pour élire un leader : $\log n$ tours.
  • On commence avec tous les noeuds, et à chaque tour, on élimine la moitié des noeuds. Les noeuds éliminés deviennent “passifs” : ils ne contentent plus dès lors que de passer les messages.
  • Chaque noeud passe son identifiant et celui de son voisin de gauche à son voisin de droite.
  • Le noeud $n$ devient passif ssi l’identifiant de $n-1$ est plus grand que celui de $n$ et de $n+1$.
spinlock :

autre paradigme, où le processus en attente “tourne en boucle” jusqu’à ce qu’un créneau devienne disponible.

spinlock ⟶ quand on a de la vraie concurrence, et quand le temps d’attente est très court.

⟶ il est alors moins coûteux d’attendre activement quelques cycles de processeur que de basculer vers un autre processus


main(int argc, char **argv){
  int i = atoi(argv[1]);
  while(1){ sleep(1); }
}

Deux instances de ce même programme ont le même espace d’adressage.

En assembleur

mov %rax, [addr]

l’adresse [addr] n’est que virtuelle : même au niveau le plus bas, on n’a pas un accès direct à la machine.

8200 = 2×4096 + 8 = ...010 0000 0000 1000 ⟶ le processeur propose au processus une “mémoire virtuelle”

  • certaines pages de la mémoire virtuelle correspondent à des pages de la mémoire réelle

  • les autres ne sont pas attribuées ⟶ “marqués x”

    • Segmentation Fault : interruption rattrapée par le noyau : on a essayé d’accéder à une page marquée x

Leave a comment