Ce document de travaux dirigés est destiné aux étudiants de 1ère année Ingénierie en Systèmes d'Exploitation Avancés de l'Institut Supérieur d'Informatique. Il aborde de manière approfondie la problématique des interblocages, un défi majeur dans la gestion des systèmes concurrents.
Ce TD, préparé par Mme Lilia Sfaxi, propose plusieurs exercices pratiques visant à renforcer la compréhension des mécanismes d'interblocage, de leur détection et des stratégies pour les éviter ou les prévenir. Les étudiants exploreront les concepts clés tels que :
- Les processus concurrents et l'utilisation des ressources.
- Les graphes d'allocation des ressources.
- L'algorithme du banquier.
- La prévention et l'évitement des interblocages.
Comprendre les Interblocages dans les Systèmes d'Exploitation
Les interblocages, ou deadlocks, sont un problème fondamental en informatique, particulièrement dans la gestion des systèmes d'exploitation. Ils surviennent lorsque plusieurs processus attendent indéfiniment des ressources détenues par d'autres processus, créant une impasse où aucun ne peut progresser. Cette section explore différents aspects des interblocages à travers des cas pratiques, incluant leur détection, leur prévention et leur évitement.
Exercice 1 : Analyse d'Interblocages entre Processus Concurrents
Soient trois processus concurrents qui utilisent en exclusion mutuelle six ressources différentes (de A à F). Ces trois processus exécutent respectivement les codes suivants :
Processus_1()
while(1){
prendre (D);
prendre (E);
prendre (C);
// Utilisation des ressources;
liberer(D);
liberer(E);
liberer(C);
}Processus_2()
while(1){
prendre (C);
prendre (B);
prendre (F);
// Utilisation des ressources;
liberer (F);
liberer (B);
liberer (C);
}Processus_3()
while(1){
prendre (A);
prendre (B);
prendre (E);
// Utilisation des ressources;
liberer(E);
liberer(B);
liberer(A);
}Ces processus concurrents peuvent-ils entrer en interblocage ? Expliquez à l’aide d’un graphe. Si oui, peut-on l’éviter ? Justifiez brièvement. Peut-on le prévenir ? Proposez une solution.
Explication additionnelle : Un interblocage est possible si les quatre conditions de Coffman sont remplies : exclusion mutuelle, maintien et attente, non-préemption, et attente circulaire. Pour résoudre cet exercice, la construction d'un graphe d'allocation des ressources est essentielle. Un cycle dans ce graphe, où chaque nœud représente un processus ou une ressource, indiquerait une situation potentielle d'interblocage. La prévention consiste à concevoir le système de manière à ce qu'une des quatre conditions ne puisse jamais se produire. L'évitement, quant à lui, implique un contrôle dynamique des allocations de ressources, comme avec l'algorithme du banquier, pour garantir que le système reste toujours dans un état sûr.
Exercice 2 : Application de l'Algorithme du Banquier
Considérez un scénario où les ressources disponibles d’un système, les réclamations maximales faites par des processus, et l’état d’allocation courant de ressources aux processus sont définis par des tables spécifiques (non fournies ici mais nécessaires pour une résolution complète).
- Représenter le graphe d’allocation des ressources à cet instant.
- Appliquer l’algorithme du banquier pour déterminer si l’état courant d’allocation est sûr.
Note : L'algorithme du banquier est une stratégie d'évitement des interblocages. Il nécessite que chaque processus déclare à l'avance le nombre maximal de ressources de chaque type qu'il pourrait demander. Le système autorise une allocation uniquement si celle-ci maintient le système dans un état sûr, c'est-à-dire un état où il existe au moins une séquence d'exécution des processus permettant à tous de se terminer sans interblocage.
Exercice 3 : Analyse d'un Graphe d’Allocation de Ressources
Soit un graphe d’allocation des ressources (dont l'illustration est nécessaire pour l'analyse). Il y a une réponse correcte parmi les 5 suivantes. Choisissez et justifiez :
- Le graphe a un cycle et donc on peut assurer qu’il n’y a pas d’interblocage.
- Le graphe a un cycle et donc on peut assurer qu’il y a un interblocage.
- Il y a une séquence de terminaison des processus qui ne produit pas d’interblocage.
- Il y a un interblocage entre les processus.
- Aucune des réponses antérieures n’est correcte.
Clarification : La présence d'un cycle dans un graphe d'allocation des ressources est une condition nécessaire pour un interblocage. Si chaque type de ressource n'a qu'une seule instance, un cycle est alors suffisant pour garantir un interblocage. Cependant, si un type de ressource a plusieurs instances, un cycle n'est plus une condition suffisante, et une analyse plus approfondie est requise.
Exercice 4 : Graphe Réduit et Détection d'Interblocage
Soit un graphe d’allocation (spécifique, non représenté ici).
- Représenter le graphe réduit correspondant à ce graphe d’allocation.
- Ce graphe réduit représente-t-il une situation d’interblocage ? Justifiez.
Contexte : L'approche du graphe réduit est une méthode de détection d'interblocage. Elle consiste à retirer itérativement du graphe les processus qui peuvent potentiellement terminer leur exécution (c'est-à-dire qui peuvent obtenir toutes les ressources nécessaires, puis libérer celles qu'ils détiennent). Si, après avoir appliqué cette réduction maximale, le graphe est vide, il n'y a pas d'interblocage. Si des nœuds de processus subsistent, cela indique une situation d'interblocage.
Foire Aux Questions (FAQ) sur les Interblocages
Qu'est-ce qu'un interblocage (deadlock) ?
Un interblocage est une situation en informatique où deux processus ou plus sont bloqués de manière permanente, attendant chacun une ressource détenue par un autre processus dans le même ensemble. Aucun des processus ne peut progresser, ce qui entraîne une stagnation du système ou des applications concernées.
Quelles sont les quatre conditions nécessaires pour qu'un interblocage se produise ?
Les quatre conditions de Coffman, nécessaires pour un interblocage, sont :
- Exclusion mutuelle : Au moins une ressource doit être utilisée en mode non-partageable, c'est-à-dire qu'un seul processus peut l'utiliser à la fois.
- Maintien et attente : Un processus détenant au moins une ressource attend d'acquérir des ressources supplémentaires détenues par d'autres processus.
- Non-préemption : Une ressource ne peut être libérée que volontairement par le processus qui la détient, et ce, après avoir terminé sa tâche.
- Attente circulaire : Il existe un ensemble de processus P0, P1, ..., Pn tel que P0 attend une ressource détenue par P1, P1 attend une ressource détenue par P2, ..., Pn-1 attend une ressource détenue par Pn, et Pn attend une ressource détenue par P0.
Comment les interblocages peuvent-ils être gérés ou évités ?
Il existe trois principales stratégies pour gérer les interblocages :
- Prévention : Elle consiste à garantir qu'au moins une des quatre conditions d'interblocage ne puisse jamais être remplie (par exemple, en imposant un ordre sur l'acquisition des ressources pour briser l'attente circulaire).
- Évitement : Elle implique que le système d'exploitation prenne des décisions d'allocation de ressources de manière dynamique. Des algorithmes comme l'algorithme du banquier vérifient si une allocation de ressources potentielle peut conduire à un état sûr avant de l'accorder.
- Détection et récupération : Cette approche permet aux interblocages de se produire, puis le système les détecte et prend des mesures pour les résoudre, telles que la terminaison de processus, la préemption de ressources, ou le retour en arrière (rollback) à un état antérieur.