Fiche de révision : Introduction à la concurrence

📋 Plan du Cours

1. Enjeux de la concurrence
2. Processus et threads
3. Dépendances et parallélisme
4. Atomicité et sécurité
5. Problèmes de correction
6. Synchronisation et sémaphores
7. Conception concurrente
8. Patrons algorithmiques

📖 1. Enjeux de la concurrence

🔑 Notions clés & Définitions

• Programmation concurrente : Consiste à exécuter plusieurs processus sur un même ordinateur en organisant l’allocation des ressources, leur partage et la synchronisation de leurs accès.

★ À maîtriser

📐 Formule — Pour n acteurs exécutant chacun p actions séquentielles, le nombre de scénarios possibles est $S=\frac{(n\times p)!}{(p!)^n}$.

Compléments

• La concurrence apparaît notamment dans:
  • les systèmes d’exploitation
  • les systèmes distribués
  • les interfaces utilisateur
  • le calcul scientifique

💡 Astuce mémo

Activités simultanées → dépendances → besoin de contrôle

📖 2. Processus et threads

🔑 Notions clés & Définitions

• Processus : Abstraction du système d’exploitation représentant un programme en cours d’exécution, avec ses instructions et son contexte d’exécution, notamment sa mémoire, ses registres et ses descripteurs d’entrées-sorties.
• Thread : Unité d’exécution contenue dans un processus, possédant ses propres registres et sa propre pile, mais partageant la mémoire avec les autres threads du processus.

📝 Points essentiels

• Les trois états de base sont:
  • actif
  • en attente
  • prêt

💡 Astuce mémo

Processus séparés, threads partageurs

📖 3. Dépendances et parallélisme

🔑 Notions clés & Définitions

• Dépendance : État de données ou de contrôle qui doit être atteint avant qu’une partie du programme puisse s’exécuter.
• Conditions de Bernstein : Deux sous-programmes peuvent s’exécuter en parallèle avec un résultat équivalent à l’exécution séquentielle si leurs ensembles d’écritures sont disjoints et si aucune écriture de l’un ne recouvre une lecture de l’autre.

📝 Points essentiels

• Dans le calcul z=x+y, les affectations de x et y doivent être réalisées avant la lecture de ces variables pour calculer z.

📖 4. Atomicité et sécurité

🔑 Notions clés & Définitions

• Atomicité : Propriété d’une séquence d’opérations qui doit se comporter comme une opération indivisible afin qu’aucune autre unité d’exécution ne voie son état intermédiaire.
• Exclusion mutuelle : Garantit qu’un seul thread d’exécution se trouve dans une section critique à un instant donné.

📝 Points essentiels

📌 Une implémentation thread-safe se comporte correctement avec plusieurs threads, tandis qu’une implémentation non thread-safe peut se comporter de manière incorrecte et imprévisible.

💡 Astuce mémo

Atomique protège l’état intermédiaire, non atomique l’expose

📖 5. Problèmes de correction

🔑 Notions clés & Définitions

• Condition de course : Existe lorsque le résultat dépend de l’ordre relatif d’arrivée de plusieurs séquences d’exécution à un point critique.
• Interblocage : Edward G. Coffman, Jr., 1971 — Un interblocage peut apparaître lorsque sont réunies simultanément l’exclusion mutuelle, l’attente avec conservation, l’absence de préemption et l’attente circulaire.
• Livelock : Cycle infini d’opérations dans lequel le programme continue de s’exécuter mais ne parvient pas à progresser.
• Non-déterminisme : Propriété inhérente des systèmes parallèles dans lesquels le résultat ou l’ordre d’exécution peut varier, sans constituer nécessairement un problème.

📝 Points essentiels

📌 La vivacité exige que les threads finissent éventuellement ou accomplissent régulièrement un progrès, tandis que la famine survient lorsqu’un thread cesse de progresser sous l’effet des autres.

💡 Astuce mémo

RDLFSN : race, deadlock, livelock, famine, non-déterminisme

📖 6. Synchronisation et sémaphores

🔑 Notions clés & Définitions

• Sémaphore entier : Dijkstra — Primitive de synchronisation composée d’un compteur entier et d’une file de threads bloqués, manipulée par les opérations Init, P et V.
• Verrou : Mécanisme de synchronisation dont l’opération lock acquiert l’accès et dont l’opération unlock le libère, les autres threads devant attendre lorsque le verrou est détenu.
• Mutex : Un mutex est un sémaphore booléen doté d’un protocole d’héritage de priorité : si un thread de priorité P2 attend un mutex détenu par un thread de priorité P1 et que P2>P1, la priorité du détenteur augmente à P2 jusqu’à la libération du mutex.

📝 Points essentiels

• 🔄 La manipulation d’un sémaphore suit les étapes suivantes:
  1. Init(n) initialise le compteur à n et vide la file
  2. P décrémente le compteur et bloque le thread si le compteur devient négatif
  3. V incrémente le compteur et débloque un thread en attente le cas échéant

💡 Astuce mémo

Init → P attend ou décrémente → V libère ou réveille

📖 7. Conception concurrente

🔑 Notions clés & Définitions

• Patron de conception : Christopher Alexander, A Pattern Language — Un patron de conception décrit un problème récurrent et le cœur d’une solution réutilisable dans des contextes différents.

📝 Points essentiels

• 🔄 La recherche de la concurrence suit trois étapes:
  1. identifier les tâches concurrentes
  2. décomposer les données pour réduire le partage ou les mouvements
  3. décrire les dépendances d’ordre et de données entre les tâches

💡 Astuce mémo

Tâches → données → dépendances

📖 8. Patrons algorithmiques

🔑 Notions clés & Définitions

• Pipeline : Relie des étapes de calcul selon un schéma de communication fixe ; lorsque le pipeline est rempli, les étapes peuvent s’exécuter simultanément sur des données différentes.
• Fork-join : Commence avec un thread, crée des threads supplémentaires pour exécuter des fonctions, puis les rejoint avant de poursuivre le calcul.
• Master-worker : Dans lequel un thread maître gère une file de tâches, les threads travailleurs prennent une tâche, l’exécutent et reviennent en chercher une autre jusqu’à la terminaison.
• SPMD : Lance plusieurs copies d’un même programme, généralement avec des vues différentes des données, et le chemin d’exécution dépend notamment d’un identifiant unique appelé rang.
• Coordination événementielle : Définit des tâches qui s’exécutent concurremment en réponse à des événements arrivant dans une file.

📊 Tableaux de synthèse

Processus et threads