interblocage des processus

Rappel interblocage des processus 

Amira BELHEDI belhedi.amira@yahoo.fr 

ISTIC 2018 

Processus et ressources 

• L’utilisation d’une ressource passe par les étapes suivantes 

– Demande de la ressource : 

• Si l’on ne peut pas satisfaire la demande il faut attendre. La demande sera mise dans une table d’attente des ressources – Utilisation de la ressource 
• Le processus peut utiliser la ressource – Libération de la ressource 
• Le processus libère la ressource demandée et allouée. 

2 

Processus et ressources 

• Les ressources peuvent être de plusieurs types 

– D’usage partagé : Est-ce que la ressource peut être utilisée par plusieurs processus en même temps → Les ressources partagées n’affectent pas les interblocages. – Avec un ou multiples exemplaires – Preémptible ou non preémptible : Est-ce qu’on a le droit de retirer une ressource quand elle est utilisée par un processus – Reutilisables ou disponibles Existent-elles après son utilisation ? 

• Reutilisables : Toutes les ressources physiques et quelques unes logiques (chiers, mutex, verrous, etc.). 
• Disponibles :Ressources associées à la communication et à la synchronisation comme les messages, les signaux, les sémaphores, etc. 

3 

Problème d’interblocage 

• Soit deux processus P1 et p2 en cours d’exécution 

Processus P1 Processus P2 -Demande ressource R1 -demande ressource R2 -calcul 

4 -Demande ressource R2 -demande ressource R1 -calcul 

Problème d’interblocage 

• 1er cas ordonnanceur non préemptif : chaque processus s’éxécutera puis permettra à l’autre de s’éxécuter 
• 2ème cas ordonnanceur préemptif : 
• P1 détient R1 et attend R2 qui est utilisée par P2 
• P2 détient R2 et attend R1 qui est utilisée par P1 

➢ situation d’interblocage : P1 attend P2 et P2 attend P1. Les 

deux processus vont attendre indéfiniment 

5 

Problème d’interblocage 

Situation d’interblocage de deux processus 

6 

Problème d’interblocage 

• Définition: un ensemble de processus est en interblocage si chaque processus attend la libération d’une ressource qui est allouée à un autre processus de l’ensemble. 

➢Comme tous les processus sont en attente, aucun ne pourra s’exécuter et donc libérer les ressources demandées par les autres. Ils attendront tous indéfiniment. 

7 

Conditions nécessaires pour l’interblocage 

• Les 4conditions pour qu’un interblocage ait lieu (Conditions de Coffman) : 

– L’exclusion mutuelle: à un instant précis, une ressource est 

allouée à un seul processus. – La détention et l’attente: les processus qui détiennent des ressources 

peuvent en demander d’autres. – Pas de préemption: les ressources allouées à un processus sont libérées 

uniquement par le processus. – L’attente circulaire: il existe une chaîne de deux ou plus processus de 

telle manière que chaque processus dans la chaîne requiert une ressource allouée au processus suivant dans la chaîne. 

8 

Graphe d’allocation des ressources 

C’est un graphe modélisant l’état d’allocation des ressources pour les processus. Il est composé des : 

• processus représentés par des cercles. 
• ressources représentées par des rectangles. 

– Chaque rectangle contient autant de points qu’il y a d’exemplaires de la 

ressource représentée. 

• Un arc orienté d’une ressource vers un processus signifie que la ressource est allouée au processus. 
• Un arc orienté d’un processus vers une ressource signifie que le processus est bloqué en attente de la ressource. → Ce graphe indique pour chaque processus les ressources qu’il 

détient ainsi que celles qu’il demande. 

9 

Graphe d’allocation des ressources 

• 1er cas : Exécution séquentielle A suivi de B suivi de C. → Pas d’interblocage 

10 

Graphe d’allocation des ressources 

• 2eme cas : Exécution par ordonnancement circulaire dans l’ordre : 

1. A demande R 2. B demande S 3. C demande T 4. A demande S 5. B demande T 6. C demande R 

11 

Graphe d’allocation des ressources 

• Situation d’interblocage de trois processus. 

12 

Réduction du graphe d’allocation des ressources 

• Un graphe réduit peut-être utilisé pour déterminer s’il existe ou non un interblocage. 
• Pour la réduction d’un graphe d’allocation des ressources, les flèches associées à chaque processus et à chaque ressource doivent être vérifiées. 

13 

Réduction du graphe d’allocation des ressources 

3 règles : 

• Règle 1 : Une ressource ne possédant que des flèches qui sortent (il n’y a pas des requêtes) → on les efface. 
• Règle 2 : Un processus ne possédant que des flèches qui pointent vers lui → on les efface. 
• Règle 3 : Si une ressource a des flèches qui pointent vers elle → pour chaque ressource disponible il faut inverser la flèche. 

14 

Réduction du graphe d’allocation des ressources 

• Exemple 1 

15 

Réduction du graphe d’allocation des ressources 

• Exemple 

16 

Réduction du graphe d’allocation des ressources 

• Exemple 2 

17 

Réduction du graphe d’allocation des ressources22 

• Exemple 2 

18 

Réduction du graphe 

La matrice d’allocation des ressources et attente pour l’état courant est : A=[0,0,0] 

19 

Allocation Attente 

Réduction du graphe 

1. Donner le graphe d’allocation correspondant ?? 
2. Simplifier ce graphe 

20 

Réduction du graphe 

21 

Réduction du graphe 

Appliquer règle 2 sur P1 → P1 possède seulement des flèches qui pointent vers lui → on les efface. 

22 

Réduction du graphe 

• Appliquer règle3 sur R1 et règle 2 sur P2 et règle1 sur R1 –Les requêtes de R1peuvent être allouées→ on les inverse –P2 aura seulement des flèches qui pointent vers lui→ on les efface –R1 n’a que des flèches qui sortent → on les efface 

23 

Réduction du graphe 

Appliquer règle 3 sur R2 

C’est le graphe minimale indiquant une situation d’interblocage 

24 

Réduction du graphe 

Un graphe minimal contenant des transactions →interblocage 

Un graphe minimal sans transaction → pas d’interblocage 

25 

Détection des interblocages 

• Lorsqu’un processus demande une ressource, le système doit déterminer si l’attribution de la ressource est sûre. 

– Si c’est le cas → il lui attribue la ressource. – Sinon, la ressource n’est pas accordée. 

• Un état est sûr si tous les processus peuvent terminer leur exécution (il existe une séquence d’allocations de ressources qui permet à tous les processus de se terminer). 
• Un état est non sûr si on ne peut garantir que les processus pourraient terminer leurs exécutions 

26 

Algorithme du banquier 

• Comment déterminer si un état est sûr ou non sûr ? 
• Djikstra a proposé en 1965 un algorithme d’ordonnancement, appelé l’Algorithme du banquier qui permet de répondre à cette question. 
• Cet algorithme, utilise quater matrices: 

– matrices A,E,C et R. 

27 

Algorithme du banquier 

• Quater matrices 

– Matrice C des allocations courantes d’ordre (n*m). – Matrice R des demandes(attentes) de ressources d’ordre 

(n*m). – Vecteur A d’ordre m. L’élément A[j] est le nombre de ressources de type E[j] disponibles (non attribuées). – L’élément E[j] est le nombre total de ressources de type 

j existantes dans le système. 

28 

Algorithme du banquier 

1. Rechercher un processus P[i] non marqué dont la 

rangée R[i] est inférieure à A. 2. Si ce processus existe, ajouter la rangée C[i] à A, 

marquer le processus et revenir à l’étape 1 3. Si ce processus n’existe pas, les processus non 

marqués sont en interblocage. L’algorithme se termine. → L’algorithme du banquier permet bien de détecter les interblocages mais il est peu utilisé en pratique car on ne connaît pas toujours à l’avance les besoins en ressources des processus. 

29 

Algorithme du banquier 

• Exemple 

– 3 processus en cours – 4 types de ressources: 4 dérouleurs de bandes/2 scanners/ 3 

imprimantes / un lecteur de CD ROM 

30 

Détection d’interblocage(Algo) 

• Exemple 

– Seul P3 peut obtenir les ressources→ il s’exécute et libère 

les ressources →A = [2,2,2,0] – Ensuite, P2 peut obtenir les ressources→ il s’exécute et 

libère les ressources →A = [4,2,2,1] – Ensuite P1 peut obtenir les ressources → pas 

d’interblocage 

31 

télécharger gratuitement cours d’interblocage des processus