Rappel interblocage des processus  Amira BELHEDI [email protected]  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 est le nombre de ressources de type E disponibles (non attribuées). – L’élément E est le nombre total de ressources de type  j existantes dans le système.  28  Algorithme du banquier 

1. Rechercher un processus P non marqué dont la 

rangée R est inférieure à A. 2. Si ce processus existe, ajouter la rangée C à 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