Fiche de révision : Synchronisation et interblocages

📋 Plan du Cours

1. Lecteurs et écrivains
2. Méthode de programmation par sémaphores
3. Conditions POSIX et réveils
4. Attente correcte avec une condition
5. Mécanismes de synchronisation
6. Attente passive et attente active
7. Interblocage et exemples
8. Conditions de Coffman
9. Graphes et cycles de ressources

📖 1. Lecteurs et écrivains

★ À maîtriser

📌 Dans le problème lecteurs-écrivains, plusieurs lecteurs peuvent accéder simultanément à la donnée, tandis qu’un écrivain doit y accéder seul, sans lecteur ni autre écrivain.

• Avec la priorité aux lecteurs, un écrivain n’accède à la donnée que lorsqu’aucun lecteur n’est en train de lire.

• Sans protection, nbrl++ et le test if (nbrl == 1) ne sont pas atomiques et plusieurs lecteurs peuvent ainsi fausser le compte des lecteurs.

• Smut, initialisé à 1, protège la variable nbrl ; Se, également initialisé à 1, exclut les écrivains pendant que le groupe des lecteurs accède à la donnée.

• 🔄 La synchronisation du groupe des lecteurs suit ces étapes :

  1. Le premier lecteur prend Se lorsque nbrl passe à 1.
  2. Les lecteurs accèdent à la donnée sans prendre Se individuellement.
  3. Le dernier lecteur libère Se lorsque nbrl revient à 0.

Compléments

• Dans l’exemple de struct timespec, lire tv_sec avant une modification et tv_nsec après peut produire un mélange incohérent des anciennes et nouvelles valeurs.

💡 Astuce mémo

Le premier lecteur ferme la porte aux écrivains ; le dernier la rouvre.

📖 2. Méthode de programmation par sémaphores

📝 Points essentiels

• Pour aborder un problème de synchronisation par sémaphores, on le ramène aux cas typiques connus, on repère l’endroit où attendre, on associe un sémaphore à chaque attente unique et on protège les variables critiques annexes.

📖 3. Conditions POSIX et réveils

★ À maîtriser

📌 Une condition POSIX est un outil spécialisé dans l’attente d’événement, tandis qu’un sémaphore peut aussi servir à l’exclusion mutuelle ou au comptage de ressources.

• Les opérations de réveil des conditions POSIX sont : pthread_cond_wait attend sur une condition., pthread_cond_signal réveille un thread en attente., pthread_cond_broadcast réveille tous les threads en attente.

📌 Un réveil perdu survient lorsqu’un signal de condition est émis sans thread en attente et n’est pas mémorisé, tandis qu’un réveil trompeur survient lorsque le thread réveillé reprend après que la condition justifiant son réveil a cessé d’être vraie.

Compléments

• Contrairement à un signal de condition, qui n’est pas mémorisé quand aucun thread n’attend, un V sur un sémaphore incrémente un compteur persistant.

💡 Astuce mémo

Réveil perdu : le signal disparaît ; réveil trompeur : la condition a changé.

📖 4. Attente correcte avec une condition

★ À maîtriser

• pthread_cond_wait libère atomiquement le mutex associé en mettant le thread en attente, puis reverrouille automatiquement ce mutex avant de rendre la main au thread réveillé.

📌 La condition d’attente doit être testée dans une boucle while autour de pthread_cond_wait, et non dans un simple if, afin de la retester après le réveil.

• Pour attendre correctement un événement, il faut exprimer l’événement par une assertion, tester cette assertion en section critique dans une boucle, attendre si elle n’est pas satisfaite et vérifier qu’elle l’est en sortant de la boucle.

Compléments

• L’API POSIX des conditions comprend :

  • pthread_cond_init
  • pthread_cond_destroy
  • pthread_cond_wait
  • pthread_cond_signal
  • pthread_cond_broadcast
  • pthread_cond_timedwait

• Il n’existe pas de fonction pthread_cond_trywait, car une condition POSIX sert uniquement à attendre un événement et non à tenter l’obtention d’une ressource sans bloquer.

💡 Astuce mémo

Verrouiller, tester en boucle, attendre, retester.

📖 5. Mécanismes de synchronisation

★ À maîtriser

• Pour les threads, le mécanisme indiqué pour l’exclusion mutuelle est le mutex et celui de l’attente d’événement est la condition ; pour les processus, un sémaphore peut servir aux deux.

Compléments

• Pour synchroniser des signaux, le mécanisme indiqué est le masquage pour l’exclusion mutuelle et sigsuspend pour l’attente d’événement.

📖 6. Attente passive et attente active

★ À maîtriser

📌 L’attente passive demande au système de mettre l’activité en pause, tandis que l’attente active vérifie une condition en boucle sur le processeur.

• L’attente active est à éviter dans la plupart des cas, mais peut être légitime sans support d’attente passive, lorsque beaucoup de processeurs sont disponibles ou pour des sections critiques très courtes et très fréquentes.

Compléments

• Ajouter sleep à une boucle de vérification ne transforme pas l’attente active en attente passive et peut retarder la réaction à l’événement jusqu’à 1 seconde dans l’exemple du cours.

📌 Parmi pthread_cond_broadcast, pthread_spin_lock, sem_trywait et sleep, pthread_cond_broadcast reste légitime dans certains usages, tandis que les trois autres sont à éviter par défaut.

💡 Astuce mémo

Passive : le système endort ; active : le processeur vérifie en boucle.

📖 7. Interblocage et exemples

🔑 Notions clés & Définitions

• Interblocage : Situation dans laquelle une ou plusieurs entités d’exécution sont bloquées de leur propre fait et ne peuvent pas se débloquer elles-mêmes.

★ À maîtriser

• Avec deux ressources, un interblocage survient si A détient r1 et attend r2 détenue par B, tandis que B détient r2 et attend r1 détenue par A.

Compléments

• Un seul processus peut s’interbloquer en exécutant deux fois P(r1) sur le même sémaphore binaire sans exécuter V(r1) entre les deux appels.

• Un interblocage peut survenir avec une barrière si A détient un mutex en attendant la barrière et si B ne peut pas atteindre cette barrière parce qu’il attend le même mutex.

• L’interblocage peut survenir avec tout mécanisme provoquant une attente conditionnelle, notamment les sémaphores, les mutex, les barrières et les conditions.

📖 8. Conditions de Coffman

★ À maîtriser

📌 Selon les conditions de Coffman, Elphick et Shoshani (1971), un interblocage se produit si et seulement si l’exclusion mutuelle, la conservation et attente, l’absence de réquisition et l’attente circulaire sont simultanément réunies.

Compléments

• Avec les primitives étudiées dans le cours, notamment P/V, pthread_mutex_lock et pthread_cond_wait, une ressource acquise ne peut pas être réquisitionnée de force.

💡 Astuce mémo

ECNA : Exclusion, Conservation, Non-réquisition, Attente circulaire.

📖 9. Graphes et cycles de ressources

🔑 Notions clés & Définitions

• Graphe d’allocation : Graphe orienté dont les sommets représentent des processus P et des ressources R, et dont les arcs indiquent les allocations ou les attentes.

★ À maîtriser

• Dans un graphe d’allocation, un arc R → P signifie qu’un exemplaire de R est alloué à P, tandis qu’un arc P → R signifie que P attend un exemplaire de R.

📌 Tout interblocage implique un cycle dans le graphe d’allocation, mais un cycle n’implique pas nécessairement un interblocage lorsque les ressources ont plusieurs exemplaires.

• Lorsque chaque ressource concernée par un cycle n’a qu’un exemplaire, ce cycle implique un interblocage.

Compléments

• Avec plusieurs exemplaires de R2, un cycle entre P1 et P2 peut ne pas provoquer d’interblocage si un troisième processus P3 libère un autre exemplaire de R2 et débloque P1.

💡 Astuce mémo

Interblocage implique cycle ; cycle implique interblocage seulement si chaque ressource a un exemplaire.

📊 Tableaux de synthèse

Mécanismes selon le contexte

Cycle et interblocage