TD — Séance 3 — Programmation parallèle avancée (synchronisation)

TD de la séance 3 d’Architecture et Programmation Parallèles : programmation parallèle avancée (synchronisation).
Auteur

Dr. El Hadji Bassirou TOURÉ · DMI/FST/UCAD

ImportantObjectif

Appliquer chaque notion du cours sur des données nouvelles : entrelacements et incréments perdus, sections critiques, sémaphores et barrières, graphe d’attente et conditions de Coffman, file bornée, pipeline et équilibrage de charge. Durée : une séance de TD.

NoteConventions

Fils Python (threading). Une instruction x = x + 1 se décompose en trois opérations : lire x dans un registre local \(r\), calculer, écrire \(r\) dans x. Un entrelacement est un ordre global des opérations qui respecte l’ordre de chaque fil. Pour un verrou, un sémaphore ou une file, les fils en attente sont servis dans leur ordre d’arrivée. Durées en secondes, sauf mention contraire.

Exercice 1 : entrelacements

La variable partagée x vaut \(3\). Le fil F1 exécute x = x + 1, le fil F2 exécute x = x * 2, une seule fois chacun.

  1. Écrire les trois opérations de chaque fil.

  2. Quelle valeur finale obtient-on si F1 s’exécute entièrement avant F2 ? Si F2 s’exécute entièrement avant F1 ?

  3. Donner un entrelacement qui donne \(x=4\) et un autre qui donne \(x=6\), en remplissant pour chacun le tableau (une ligne par opération).

    # fil opération \(r\) de F1 \(r\) de F2 x

  4. Combien y a-t-il d’entrelacements des six opérations ? Combien donnent chacune des valeurs finales possibles ? (Raisonner sur l’ordre des deux lectures et des deux écritures.)

  5. Chaque instruction est maintenant protégée par un même verrou. Quelles valeurs finales restent possibles ?

  6. Trois fils exécutent chacun une fois compteur = compteur + 1, avec compteur à \(0\). Quelles valeurs finales sont possibles ? Combien y a-t-il d’entrelacements, et quelle part donne la valeur attendue ?

Exercice 2 : vérifier puis agir

Trois agents vendent en même temps des places du même car : Awa demande \(2\) places, Cheikh \(2\), Khadim \(1\). Chaque demande est un fil qui appelle reserver.

places = 3          # car Dakar - Saint-Louis
billets = []

def reserver(nom, k):
    global places
    if places >= k:                  # A
        reste = places - k           # B
        time.sleep(0.001)            # C : appel au serveur
        places = reste               # D
        billets.append((nom, k))     # E
        return True
    return False
  1. Quelles lignes forment la section critique ? Pourquoi la ligne E en fait-elle partie ?
  2. Les trois fils exécutent la ligne A avant qu’aucun n’exécute la ligne D. Qui est servi ? Combien de places sont vendues ? Quelle valeur de places reste affichée, selon le fil qui écrit le dernier ?
  3. On découpe chaque appel en deux opérations : R (lignes A et B : lire, tester, calculer) et W (lignes D et E : écrire). Combien y a-t-il d’entrelacements des six opérations ? Donner un entrelacement où les trois agents sont servis et où places vaut \(0\) à la fin.
  4. Tout le corps de reserver est placé dans un bloc with verrou:. Pour chacun des six ordres d’arrivée, dire qui est servi et ce que vaut places.
  5. Un collègue ne protège que la ligne D. Le problème est-il résolu ?

Exercice 3 : sémaphore et barrière

Partie A. Un service accepte au plus \(4\) accès à la fois : acces = Semaphore(4). \(14\) requêtes arrivent ensemble ; chacune fait with acces: time.sleep(0.3).

  1. Quelle est la durée totale ?

  2. Remplir le tableau : à chaque instant, les requêtes (numérotées \(0\) à \(13\) dans l’ordre d’arrivée) qui entrent, le nombre en attente, et la valeur du compteur du sémaphore juste après.

    instant entrent en attente compteur
    \(t=0\)
    \(t=0{,}3\)
    \(t=0{,}6\)
    \(t=0{,}9\)
    \(t=1{,}2\)

  3. Même question (a) avec Semaphore(5).

  4. Un sémaphore initialisé à \(1\) et un Lock assurent tous deux l’exclusion mutuelle. Donner une différence.

Partie B. Cinq fils exécutent trois phases ; une barrière Barrier(5) les synchronise après la phase 1 et après la phase 2 (pas après la phase 3). Durées des phases :

fil 0 fil 1 fil 2 fil 3 fil 4
phase 1 0,4 0,7 0,5 0,3 0,6
phase 2 0,9 0,3 0,6 0,8 0,5
phase 3 0,2 0,6 0,5 0,4 0,3
  1. Quand chaque barrière s’ouvre-t-elle ? Quand chaque fil finit-il ? Quelle est la durée totale ?
  2. Combien de temps chaque fil attend-il à chaque barrière ? Quel est le temps d’attente total des cinq fils ?
  3. Quelle serait la durée sans aucune barrière ? Combien d’appels à wait() fait chaque fil ?
  4. Que se passe-t-il si l’on écrit Barrier(6) par erreur ?

Exercice 4 : graphe d’attente

Trois virements sont lancés en même temps, chacun dans un fil ; chaque compte a son verrou, et un virement verrouille d’abord le compte débité, puis le compte crédité :

F1 : Awa \(\to\) Cheikh F2 : Cheikh \(\to\) Khadim F3 : Khadim \(\to\) Awa

def virement(de, vers):
    with verrous[de]:
        time.sleep(0.05)
        with verrous[vers]:
            crediter(vers)
  1. Chaque fil a pris son premier verrou. Dessiner le graphe d’allocation (fils, verrous, flèches « détenu par » et « demandé par »), puis le graphe d’attente entre fils. Y a-t-il un cycle ?
  2. Vérifier une à une les quatre conditions de Coffman dans cette situation.
  3. Les verrous sont pris dans l’ordre alphabétique des noms (Awa, Cheikh, Khadim), quel que soit le sens du virement. Quel fil change d’ordre ? Dessiner le graphe d’attente quand F1 tient le verrou d’Awa et F2 celui de Cheikh. Peut-il encore y avoir un interblocage ?
  4. Sans F3, les virements F1 et F2 (ordre d’origine) peuvent-ils s’interbloquer ? Justifier avec le graphe d’attente.

Exercice 5 : file bornée

Une file q = Queue(maxsize=3) relie un producteur P à deux consommateurs C1 et C2. Les opérations suivantes ont lieu dans cet ordre (un fil bloqué reprend dès que c’est possible) :

  1. C1 : get()
  2. P : put(a)
  3. P : put(b)
  4. P : put(c)
  5. P : put(d)
  6. P : put(e)
  7. C2 : get()
  8. C1 : task_done()
  9. C1 : get()
  10. C2 : task_done()

  1. Remplir le tableau après chaque opération : contenu de la file (de la plus ancienne à la plus récente), fils bloqués ou réveillés, nombre de tâches non terminées (put ajoute \(1\), task_done retire \(1\)).

    # opération contenu bloqués, réveillés non terminées

  2. À quelles opérations un fil est-il bloqué ? Pourquoi la file ne contient-elle jamais plus de \(3\) éléments ?

  3. À la fin, P dépose un signal de fin None pour arrêter les consommateurs. Combien en faut-il ? Que se passe-t-il avec un seul ?

  4. Quand q.join() rendrait-il la main ?

Exercice 6 (approfondissement) : pipeline et équilibrage

  1. Un traitement d’images a quatre étapes, une par fil : décoder (\(2\) ms), redimensionner (\(4\) ms), filtrer (\(3\) ms), encoder (\(1\) ms). Calculer la durée pour \(50\) images en pipeline, puis à la suite, et l’accélération.
  2. On fusionne filtrer et encoder en une étape de \(4\) ms. La durée change-t-elle ? On coupe plutôt « redimensionner » en deux étapes de \(2\) ms. Nouvelle durée ?
  3. Un pool de \(5\) workers reçoit \(12\) sous-tâches de \(0{,}5\) s (fork-join). Durée ?
  4. Dix tâches de durées \(4, 2, 7, 1, 3, 3, 1, 5, 2, 2\) sont réparties sur \(3\) fils. Dessiner la frise et donner la durée totale : en statique (blocs consécutifs de \(\lceil 10/3\rceil=4\) tâches, le dernier fil reçoit le reste), en dynamique (chaque fil libre prend la tâche suivante dans l’ordre donné), et en dynamique après un tri par durée décroissante. Comparer à la borne \(\lceil 30/3\rceil\).

Pour cette séance

Le cours

Les slides

À lire en ligne

À télécharger

Retour au sommet