Étreinte fatale

Étreinte fatale

Interblocage

Problèmes classiques des
méthodes de synchronisation

Couplage fort - Famine

Interblocage - Inversion de priorité

Un interblocage (deadlock en anglais, appelé aussi étreinte fatale) est un phénomène qui peut survenir en programmation concurrente. L'interblocage se produit lorsque deux processus légers (thread) concurrents s'attendent mutuellement. Les processus bloqués dans cet état le sont définitivement, il s'agit donc d'une situation catastrophique. C'est E.G Coffman (1971 St Gravé) principalement qui a étudié les mécanismes conduisant aux phénomènes d'interblocage.

Sommaire

Exemples

Les méthodes de synchronisation

Barrière de synchronisation - Futex - Moniteur

Mutex - Sémaphore - Spinlock

Un exemple concret d'interblocage peut se produire lorsque deux processus légers essayent d'acquérir deux verrous dans un ordre différent. Ainsi, si par exemple il y a deux mutex (nommés M1 et M2) et les deux processus légers suivants :

TâcheA :
  Obtenir M1
  Obtenir M2
  Action nécessitant les deux verrous
  Rendre M2
  Rendre M1
TâcheB :
  Obtenir M2
  Obtenir M1
  Action nécessitant les deux verrous
  Rendre M1
  Rendre M2

Un interblocage est possible. En effet, si par exemple, la séquence d'opération suivante survient :

  1. La TâcheA obtient M1.
  2. La TâcheB obtient M2.
  3. La TâcheA attend pour obtenir M2 (qui est entre les mains de TâcheB).
  4. La TâcheB attend pour obtenir M1 (qui est entre les mains de TâcheA).

Dans cette situation, les deux tâches (TâcheA et TâcheB) sont définitivement bloquées.

Évitement

Les interblocages peuvent êtres évités si certaines informations sont connues à l'avance lors des allocations de ressources. Pour chaque allocation de ressources, le système regarde s'il va entrer dans un état « non-sûr », c'est-à-dire un état qui pourrait engendrer un interblocage. Le système ne répond favorablement qu'aux requêtes qui mènent à des états « sûrs ». Pour être capable de décider si l'état suivant sera sûr ou non-sûr, le système a besoin de connaître à tout moment le nombre et le type de ressources existantes, disponibles et demandées. Un algorithme classique permettant la détection des interblocage à l'avance est l'Algorithme du Banquier. Celui-ci nécessite de connaître à l'avance les limites d'utilisation des ressources. Toutefois, pour beaucoup de système, il est impossible de connaître à l'avance les demandes de chaque processus. Cela implique que l'évitement des interblocages est souvent impossible.

Les algorithmes Attente/Mort (Wait/Die) et Blessé/Attente (Wound/Wait) sont deux autres méthodes d'évitement qui utilisent une technique de rupture de la symétrie. Dans ces deux algorithmes on prend en compte l'âge des processus et l'on distingue un processus âgé (A) et un processus jeune (J).

L'âge d'un processus peut être déterminé par horodatage (timestamp) lors de sa création. Les dates les plus petites appartiennent à des processus plus âgés, les plus grandes à des processus plus jeunes.


Wait/Die Wound/Wait
A a besoin d'une ressource détenue par J A Attend J Meurt
J a besoin d'une ressource détenue par A J Meurt J Attend


Il est important de se rendre compte qu'un processus peut être dans un état non-sûr sans pour autant forcément conduire à un interblocage. La notion de sûr/non-sûr fait uniquement référence à la possibilité que le système entre dans un interblocage ou non. Par exemple, si un processus fait une requête sur une ressource A qui résulte en un état non-sûr, mais relâche une ressource B pour éviter une attente circulaire, alors l'état est non-sûr mais le système n'est pas en interblocage.

Prévention

Une méthode consiste à toujours acquérir les mutex (exclusion mutuelle) dans le même ordre. En effet, si plusieurs processus légers (thread) nécessitent d'acquérir plusieurs verrous pour effectuer leur travail, s'ils acquièrent les verrous dans un ordre différent, il est possible qu'ils se bloquent lors de la séquence d'acquisition (comme dans l'exemple précédent).

Il convient aussi de s'intéresser aux priorités des processus. En effet, si par exemple un processus de haute priorité utilise un verrou en commun avec un processus de basse priorité (voir aussi inversion de priorité), il est possible d'obtenir des situations de blocage. Une solution à ce genre de problème consiste à n'utiliser des verrous qu'entre des processus de même priorité.

Référence

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Interblocage ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Étreinte fatale de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • étreinte fatale — ● loc. f. ►DEBUG On trouve aussi étreinte mortelle . Nom poétique donné au deadlock, aussi appelé interblocage …   Dictionnaire d'informatique francophone

  • étreinte mortelle — ● loc. f. ►DEBUG Syn. de étreinte fatale …   Dictionnaire d'informatique francophone

  • Parallélisme (informatique) — Pour les articles homonymes, voir parallèle. Blue Gene L cabinet., un des ordinateurs massivement parallèle les plus rapides des années 2000 En informatiqu …   Wikipédia en Français

  • Synchronisation (multitâches) — Pour les articles homonymes, voir Synchronisation. Dans le contexte de la programmation concurrente, le terme de synchronisation se réfère à deux concepts distincts mais liés : la synchronisation de processus et la synchronisation de données …   Wikipédia en Français

  • Interblocage — Un interblocage (deadlock en anglais, appelé aussi « étreinte fatale ») est un phénomène qui peut survenir en programmation concurrente. L interblocage se produit lorsque deux processus concurrents s attendent mutuellement. Les… …   Wikipédia en Français

  • Monstre — Godzilla, le monstre le plus réputé au Japon. Un monstre est un individu ou une créature dont l apparence, voire le comportement, surprend par son écart avec les normes d une société. Sommaire …   Wikipédia en Français

  • interblocage — ● n. m. ►EXEC Équivalent français de deadlock. Blocage du système du fait de deux processus qui s attendent mutuellement, ou d un processus qui ne peut se terminer car il attend des ressources qui ne lui seront jamais attribuées (Voir famine).… …   Dictionnaire d'informatique francophone

  • FEMME - L’image de la femme — Il n’y a pas de nu en littérature. Seul eût été capable de nous le donner Raymond Roussel si, moins intéressé par les mécanismes, il avait pu, à propos d’une femme, ne nous en tendre que l’enveloppe. Telle école ou tel moment parcelle la femme en …   Encyclopédie Universelle

  • Hollywood Night — Titre original Hollywood Night Genre Série d action, de suspense Pays d’origine  États Unis Chaîne d’origine …   Wikipédia en Français

  • Hollywood night — Titre original Hollywood Night Genre Série d action, de suspense Pays d’origine  États Unis Chaîne d’origine NBC Nomb …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”