Ce document de travail dirigé, intitulé « TD8 : Interblocages 2 », est destiné aux étudiants de première année d'ingénierie en Systèmes d'Exploitation Avancés. Il a pour objectif d'approfondir la compréhension et la gestion des interblocages, un concept fondamental dans la conception et l'optimisation des systèmes d'exploitation.
À travers des exercices pratiques, ce TD couvre principalement les notions suivantes :
- L'identification des interblocages via les graphes d'allocation de ressources.
- Les stratégies de prévention et d'évitement des interblocages, y compris l'algorithme du banquier.
- L'analyse des états de sûreté dans les systèmes d'allocation de ressources.
Interblocages et Gestion des Ressources dans les Systèmes d'Exploitation
La gestion des ressources dans un système d'exploitation est cruciale pour assurer le bon fonctionnement et l'efficacité des processus. Un défi majeur est la prévention et la détection des interblocages, situations où plusieurs processus sont bloqués indéfiniment en attendant des ressources.
Exercice 1 : Analyse d'Interblocage avec des Processus Concurrents
Soient trois processus concurrents qui utilisent en exclusion mutuelle 6 ressources différentes (de A à F). Ces trois processus exécutent respectivement les codes suivants :
Code des Processus
Processus_1( ) {
while(1){
prendre (&D);
prendre (&E);
prendre (&C);
// Utilisation des ressources;
libérer(&D);
libérer(&E);
libérer(&C);
}
}
Processus_2( ) {
while(1){
prendre (&C);
prendre (&B);
prendre (&F);
// Utilisation des ressources;
libérer (&F);
libérer (&B);
libérer (&C);
}
}
Processus_3( ) {
while(1){
prendre(&A);
prendre (&B);
prendre (&E);
// Utilisation des ressources;
libérer(&E);
libérer(&B);
libérer(&A);
}
}
Potentiel d'Interblocage
Ces processus concurrents peuvent-ils entrer en interblocage ? Expliquez à l’aide d’un graphe d'allocation des ressources. Si oui, peut-on l’éviter ? Justifiez brièvement.
Oui, ces processus peuvent entrer en interblocage. Considérons l'état suivant :
- Le Processus_1 détient la ressource D et attend la ressource C.
- Le Processus_2 détient la ressource C et attend la ressource B.
- Le Processus_3 détient la ressource A et attend la ressource E.
À partir de cet état initial, un scénario d'interblocage est possible :
- Processus_1 détient D, attend C (qui peut être détenue par P2).
- Processus_2 détient C, attend B (qui peut être détenue par P3).
- Processus_3 détient E, attend A (qui peut être détenue par P1).
Cette configuration illustre une attente circulaire : P1 attend C de P2, P2 attend B de P3, et P3 attend E de P1. Un tel cycle dans le graphe d'allocation des ressources indique une condition d'interblocage.
Prévention des Interblocages
Oui, l'interblocage peut être prévenu. Voici des solutions :
- Ordonnancement des ressources : Imposer un ordre total sur toutes les ressources. Chaque processus doit demander les ressources dans cet ordre. Par exemple, si l'ordre est A, B, C, D, E, F, un processus ne peut demander B qu'après avoir demandé A. Cela brise la condition d'attente circulaire.
- Utilisation de l'algorithme du banquier : Cet algorithme permet de déterminer si un état d'allocation de ressources est sûr, c'est-à-dire s'il existe une séquence d'exécution des processus qui permettra à tous de se terminer sans interblocage. Si une demande de ressource met le système dans un état non sûr, la demande est refusée.
Exercice 2 : Application de l'Algorithme du Banquier
Considérez les tables suivantes qui indiquent 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.
Ressources Disponibles (Available)
| Ressource | Unités disponibles |
|---|---|
| R0 | 5 |
| R1 | 6 |
| R2 | 9 |
| R3 | 4 |
Réclamations Maximales (Max)
| Processus | R0 | R1 | R2 | R3 |
|---|---|---|---|---|
| P0 | 3 | 1 | 3 | 2 |
| P1 | 0 | 4 | 5 | 1 |
| P2 | 2 | 0 | 2 | 3 |
| P3 | 2 | 3 | 4 | 1 |
| P4 | 1 | 2 | 3 | 0 |
Allocation Courante (Allocation)
| Processus | R0 | R1 | R2 | R3 |
|---|---|---|---|---|
| P0 | 1 | 1 | 2 | 1 |
| P1 | 0 | 2 | 2 | 1 |
| P2 | 1 | 0 | 0 | 2 |
| P3 | 2 | 1 | 3 | 1 |
| P4 | 0 | 1 | 1 | 0 |
Détermination de l'État Sûr
Appliquez l’algorithme du banquier pour déterminer si l’état courant d’allocation est sûr.
Pour appliquer l'algorithme du banquier, nous devons d'abord calculer la matrice des besoins (Need) en soustrayant l'allocation courante des réclamations maximales. Ensuite, nous cherchons une séquence de processus qui peuvent s'exécuter jusqu'à la fin en utilisant les ressources disponibles et celles qu'ils détiennent. Si une telle séquence est trouvée, l'état est dit "sûr".
Dans ce cas, après l'application de l'algorithme : Tous les processus peuvent être satisfaits par les ressources disponibles en suivant une séquence d'exécution sûre, c'est donc un état sûr.
Exercice 3 : Analyse d'un Graphe d’Allocation des Ressources
Soit le graphe d’allocation des ressources d'une figure (non fournie ici). Il y a une réponse correcte parmi les 5 suivantes. Choisissez et justifiez :
Options de Réponse
- 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.
Justification
La réponse correcte est la 3 : Il y a une séquence de terminaison des processus qui ne produit pas d’interblocage.
Explication :
- P3 est réductible : Cela signifie que le processus P3 peut terminer son exécution avec les ressources qu'il détient et les ressources actuellement disponibles dans le système, sans avoir besoin d'attendre d'autres ressources.
- Libération des ressources : Une fois que P3 termine, il libère toutes ses ressources. Cette libération de ressources peut rendre disponibles des instances de ressources qui étaient attendues par d'autres processus.
- Rupture du cycle : Si, par exemple, un exemplaire de R1 est libéré par P3 et est ensuite disponible pour P1 (qui l'attendait), alors le cycle potentiel d'attente qui existait est détruit. La possibilité d'une séquence de terminaison, où tous les processus peuvent s'achever sans se bloquer mutuellement, indique que, malgré la présence éventuelle d'un cycle, il n'y a pas d'interblocage au sens strict car le système peut progresser. Un cycle dans un graphe d'allocation de ressources à instances multiples est une condition nécessaire mais non suffisante pour un interblocage.
FAQ : Questions Fréquentes sur les Interblocages
Qu'est-ce qu'un interblocage (deadlock) ?
Un interblocage est une situation où deux ou plusieurs processus sont bloqués indéfiniment, chacun attendant une ressource détenue par un autre processus de la même suite d'attente. Il se caractérise par quatre conditions de Coffman : exclusion mutuelle, détention et attente, non-préemption et attente circulaire.
Comment l'algorithme du banquier permet-il d'éviter les interblocages ?
L'algorithme du banquier est un algorithme de prévention des interblocages qui évalue chaque demande de ressource. Avant d'accorder une ressource, il simule l'allocation et vérifie si le système resterait dans un "état sûr" (c'est-à-dire s'il existe une séquence d'exécution des processus permettant à tous de se terminer). Si l'allocation rend le système non sûr, la demande est refusée, évitant ainsi un interblocage.
Quelle est la différence entre un cycle et un interblocage dans un graphe d'allocation de ressources ?
Dans un graphe d'allocation de ressources avec des ressources à instance unique, un cycle est une condition nécessaire et suffisante pour un interblocage. Cependant, pour des ressources à instances multiples, un cycle est une condition nécessaire mais non suffisante. Un cycle indique une attente circulaire, mais un interblocage réel ne se produit que si aucun processus impliqué dans le cycle ne peut s'achever, même avec les ressources qu'il détient et celles disponibles, et ainsi libérer des ressources.