Programmation concurrente (coopérante ?), Synchronisation¶

Traitement séquentiel vs. parallélisation¶

Un programme informatique classique se présente comme une séquence d'opérations que l'exécutant réalise 1 à 1

On parle de programmation séquentielle

Limitation 1 :¶

  • un programme séquentiel est destiné à un seul "exécutant" (1 cpu). Alors que les machines disposent de plusieurs "coeurs" (les cartes graphiques en ont des centaines ...). on sous-exploite les ressources disponibles

Exemple : "miner du bitcoin"¶

Activité répétitive, polluante (consommation électrique annuelle équivalente à celle d'un quart de la France), mais (parfois) rémunératrice

Défi (pour gagner 3.125 bitcoins).¶

Etant donné un nombre $x$, trouver $y$ tel que $hash(y) = x$

  • $hash$ fonction de hachage, impossible à inverser (en l'état actuel des connaissances)

  • $x$ et $y$ codés sur un grand nombre de bits ... il y a des milliards de milliards de valeurs possibles pour $y$

miner du bitcoin = calculer des hachés jusqu'à obtenir $x$

(celui qui trouve gagne les 3.125 bitcoins)

Parallélisation et synchronisation¶

Plutôt que de faire calculer 1 seul coeur ...

On parallélise :

  • on fait calculer chaque coeur

On synchronise :

  • si un exécutant trouve la solution : on peut tout arrêter

Limitation 2 :¶

la "vraie vie" est concurrente

Si on considère que chaque entité est régie par un programme :

  • les actions d'une entité tiennent compte de l'extérieur
  • les actions d'une entité ont des conséquences sur l'extérieur

NB : concurrence est à prendre au sens "les entités évoluent côte-à-côte en s'influençant mutuellement".

Exemple : simuler des déplacements de voiture¶

simulation séquentielle :¶
  • à chaque tour de boucle :
    • pour chaque voiture v
      • v se déplace ...

C'est assez artificiel !

simulation concurrente :¶
  • chaque voiture évolue indépendamment
    • il n'y a pas de "chef d'orchestre"

C'est plus proche de la conduite autonome !

Nouveau modèle, nouvelles problématiques¶

  • nouveau modèle : plusieurs programmes qui s'exécutent "simultanément", accèdent à des "ressources communes", doivent pouvoir se "synchroniser"
  • nouvelles difficultés : il y a de nombreux cas à envisager ("entrelacement"). Les programmes se comportent-ils correctement dans tous les cas ?

Mise en oeuvre pratique ?¶

Idée 1 :¶

  • 1 exécutant = 1 programme en cours d'exécution (= 1 processus dit "processus lourd")

OS multi-tâche, donc possible, mais

  • la communication entre les processus n'est pas simple (HP)

  • changer d'exécutant (ordonnancement) a un coût non négligeable

  • en pratique, impossible d'exécuter 10 processus qui demandent beaucoup de ressources en parallèle

Idée 2 :¶

Avoir plusieurs fils d'exécution dans un même processus lourd

On appelle ces fils d'exécution thread ou processus léger

  • au programme MPI

  • possible dans la plupart des langages modernes

  • beaucoup moins gourmand que la solution précédente, 100 à 1000 threads simultanés sans problème

La "Programmation concurrente" en MPI¶

Les programmes concurrents sont souvent plus difficiles que les programmes "classiques" :

  • à comprendre, à concevoir, à débugger

  • les threads exécutent du code présent dans un même programme

  • les threads ne communiquement pas directement entre eux (c'est bien dommage ...), mais de manière indirecte, via de la mémoire partagée, et des primitives de synchronisation

Mais réelle utilité pratique ...

I. Programmation concurrente : les concepts¶

cf cours¶

II. Historique : comment implémenter l'exclusion mutuelle ?¶

1. Algorithme de Peterson¶

On considère 2 threads t0 et t1 (numérotés 0 et 1).

Ecrire une fonction void entrer_sc(int tid) et une fonction void sortir_sc(int tid) qui réalise l'exclusion mutuelle.

C'est-à-dire :

  • si t0 termine son appel à entrer_sc, il empêche t1 de terminer son appel à entrer_sc, jusqu'à ce que t0 appelle sortir_sc
  • et inversement, si t1 termine son appel à entrer_sc en premier ...
In [ ]:
// Tentative 1 (incorrecte ...) // deux threads : 0 et 1

bool dans_sc[2] = {false; false};

void enter_sc(int tid) {
    while (dans_sc[1-tid]) {}
    dans_sc[tid] = true;
}

void sortir_sc(int tid){
    dans_sc[tid] = false;
}
In [ ]:
// Tentative 1 (incorrecte ...) // deux threads : 0 et 1

bool dans_sc[2] = {false; false}; 
// indique si un thread est dans le section critique
// dans_sc[i] : modifié par i, lu par (1-i)

void enter_sc(int tid) {
    while (dans_sc[1-tid]) {} // attente active
    dans_sc[tid] = true;
}

void sortir_sc(int tid){
    dans_sc[tid] = false;
}

Montrer que cet algorithme est incorrect

Les deux threads peuvent être simultanément dans la section critique ...

In [ ]:
// Tentative 2 (incorrecte ...) // deux threads : 0 et 1

bool veut_entrer_sc[2] = {false; false};
// indique si un thread veut entrer dans la section critique

void enter_sc(int tid) {
    veut_entrer_sc[tid] = true;
    while (veut_entrer_sc[1-tid]) {}
}

void sortir_sc(int tid){
    veut_entrer_sc[tid] = false;
}

Montrer que cet algorithme est incorrect

Les deux threads s'empêchent l'un l'autre d'entrer en section critique (interblocage) ...

In [ ]:
// Tentative 3 (correcte : Algorithme de Peterson ...) // deux threads : 0 et 1

int prioritaire = 0; 
// le numéro du thread prioritaire si les deux veulent entrer

bool veut_entrer_sc[2] = {false; false}; 
// indique si un thread veut entrer dans la section critique

void enter_sc(int tid) {
    veut_entrer_sc[tid] = true;
    prioritaire = 1 - tid;
    while (veut_entrer_sc[1-tid] && prioritaire==1-tid) {}
}

void sortir_sc(int tid){
    veut_entrer_sc[tid] = false;
}

Prouver l'exclusion mutuelle

Prouver l'absence d'interblocage

2. Algorithme de "la boulangerie de Lamport"¶

Leslie Lamport (prix Turing 2013)

Une boulangerie avec beaucoup de clients ... on doit prendre un ticket et attendre son tour ...

On considère $N$ threads numérotés 0 et $N-1$.

Pour entrer dans la section critique, un thread doit :

  • prendre un ticket,
  • vérifier qu'aucun autre thread n'a de numéro de ticket inférieur
In [ ]:
// (Tentative 1 : incorrecte ...)

int ticket = 1; // distributeur de ticket

int num_ticket[N] = {INT_MAX, ...};
// indique le numéro de ticket du thread (INT_MAX: pas de ticket)

void enter_sc(int tid) {
    num_ticket[tid] = ticket;
    ticket += 1;
    for (int i = 0; i < N; i += 1) {
        while (num_ticket[i] < num_ticket[tid]) {}
    }
}

void sortir_sc(int tid){
    num_ticket[tid] = INT_MAX;
}

Deux threads peuvent obtenir le même ticket, et donc entrer tous deux en section critique

En cas d'égalité, on priorise le thread de plus petit numéro

il faut être sûr que personne n'est entrain de prendre un ticket : ce pourrait être un thread avec le même ticket et prioritaire (les deux rentreraient en section critique ...)

In [ ]:
// Algorithme de la boulangerie de Lamport 

int ticket = 1; // distributeur de ticket

bool ticket_en_cours[N] = {false, ...}; 
// indique si un thread est entrain de prendre son ticket

int num_ticket[N] = {INT_MAX, ...};
// indique le numéro de ticket du thread (INT_MAX: pas de ticket)

void enter_sc(int tid) {
    ticket_en_cours[tid] = true;
    num_ticket[tid] = ticket;
    ticket += 1;
    ticket_en_cours[tid] = false;
    for (int i = 0; i < N; i += 1) { // 
        while ticket_en_cours[i] {} // prise de ticket en cours
        while (num_ticket[i] < num_ticket[tid] ||  // priorité au thread i
               (num_ticket[i] ==  num_ticket[tid] && i < tid) {} 
    }
    // enfin, c'est mon tour !
}

void sortir_sc(int tid){
    num_ticket[tid] = INT_MAX;
}

III. Quelques situations classiques¶

cf cours, exercices et TP¶

Attention : les énoncés sont parfois assez "étranges" ...¶

(mais mettent en avant des problématiques qui peuvent se retrouver en programmation "réelle")

ne pas faire de contre-sens lorsqu'il s'agit de "programmation concurrente"¶

Exemple :¶

Exercice : La salle de bain commune.¶

"3 hommes et 3 femmes partagent le même logement. La salle de bain peut accueillir 3 personnes, mais qui ne peuvent être que des hommes ou que des femmes (on ne mélange pas). Proposer une solution"¶

Solution "hors sujet" :¶

"c'est facile : on fait passer les 3 femmmes, puis quand elles sont toutes sorties, on fait passer les 3 hommes"

Progr : faire entrer F1, faire entrer F2, faire entrer F3 ....

HORS-SUJET : ceci est un programme séquentiel (pas de programmation concurrente ici !)

On veut une solution avec plusieurs processus et une / des ressources communes

Exercice : La salle de bain commune.¶

"3 hommes et 3 femmes partagent le même logement. La salle de bain peut accueillir 3 personnes, mais qui ne peuvent être que des hommes ou que des femmes (on ne mélange pas). Proposer une solution"¶

Quels sont les processus (ou "threads" / "agents") ? Quelle est la (ou les) ressouce(s) commune(s) ?¶

  • 3 processus "homme", 3 processus "femme"

  • 1 ressouce commune : la salle de bain

Le code des processus ressemble à :

Progr H. : .... print "H entre dans la sdb"; ... print "H sort de la sdb" ...

Progr F. : .... print "F entre dans la sdb"; ... print "F sort de la sdb" ...

NB :

  • 3 processus vont exécuter le code Progr. H

  • 3 processus vont exécuter le code Progr. F

  • la salle de bain est très "virtuelle" : on considère qu'un processus est "dans la salle de bain" lorsque le premier print a été réalisé, mais pas encore le deuxième. (En TP, on endormira le thread pour simuler le temps passé dans la salle de bain : "sleep(random())")

Solution incorrecte :¶

3 processus exécutent Progr H. : print "H entre dans la sdb"; print "H sort de la sdb"

3 processus exécutent Progr F. : print "F entre dans la sdb"; print "F sort de la sdb"

incorrect : un entrelacement possible permet de faire entrer un H et une F

(on aura l'affichage global : "H entre - F entre ... ")

On peut même avoir les 6 personnes dans la salle de bain

Solution non optimale :¶

on s'arrange (comment ?) pour que les processus F rentrent et sortent avant que les processus H rentrent et sortent

NB : ça ressemble à la solution "hors sujet" ; si on choisit un "chef" (ce qui n'est pas forcément simple), ça revient à faire de la programmation séquentielle.

NB : et cette solution n'est pas optimale (considérée incorrecte pour ce genre d'exercice ...) : peut-être qu'un processus H sera le premier à vouloir entrer dans la sdb, et sera injustement "bloqué"

NB : on peut argumenter ainsi : "peut-être que les filles ne sont pas pressées d'utiliser la sdb ..."

Amusant ... mais on parle bien de l'avancée de chaque processus qui se fait de manière indépendante

Ce qu'il faut comprendre¶

Contraintes pour la solution attendue :

  • si la salle de bain est libre, il faut que celui/celle qui souhaite y entrer puisse le faire
  • si la salle de bain est occupée par une / des filles, seules les filles peuvent rentrer : les garçons doivent être bloqués (mais pouvoir y rentrer dès que ce sera possible)
  • et inversement, si la salle de bain est occupée par un / des garçons, ...
  • tout le monde doit pouvoir sortir de la salle, sans contrainte

NB : à implémenter le plus simplement possible, avec les outils du cours ("primitives de synchronisation" : mutex et/ou sémaphore)

IV. Programmation concurrente : en pratique¶

cf cours et Complément Memo OCaml / C