Ministère de l’Enseignement Supérieur et de la Recherche

Université de THIES

UFR en Sciences et Technologies (UFR SET)

Département Informatique : Licence 2 en Informatique (L2)
INF 2341 : Systèmes d’Exploitation 2
Gestion des interblocages

1 Rappels

1.1 Problématique
Nous avons vu plusieurs algorithmes permettant d’ordonnancer l’accès au processeur par les
processus. Cependant au cours de leur vie les processus peuvent avoir besoin de
communiquer entre eux. Cette communication se fait soit par :
● Signal asynchrone qui constitue un mode de communication interprocessus assimilable à
une sonnerie susceptible d'être entendu dans une maison. De même que chaque type de
sonnerie signale un événement particulier, à chaque signal correspond un événement
particulier pour le processus qui le reçoit (terminaison du processus, terminaison de l'un
des fils, suspension, etc.)
Processus P1 Processus P2 Temps
… …
Envoi un signal SIG1 à P2 Installation d'un handler sinon
… handler par défaut.
…
Traitement de SIG1 par un handler
● Echange de données est un mode de communication inter-processus plus général et plus
riche que les signaux; il permet d'échanger des données. L'utilisation de ce type de
communication se fait en plusieurs étapes:
÷ établissement d'une connexion (canal virtuel)
÷ ouverture de la connexion
÷ échange de données
÷ fermeture de la connexion
÷ suppression de la connexion
● Partage de ressources (exclusion mutuelle) cf. cours
Un ensemble de processus est en interblocage si chaque processus attend un événement que
seul un autre processus de l'ensemble peut engendrer. Coffman et al (1971) ont montré qu'il
faut réunir quatre conditions pour provoquer un interblocage : exclusion mutuelle ; détention
et attente ; non réquisition ; attente circulaire.
Holt a montré en 1972 comment modéliser ces 4 conditions au moyen de graphes orientés
ayant deux types de nœuds: un carré modélise une ressource et un cercle un processus.

A détient R B demande S Interblocage

Il existe en général quatre stratégies pour traiter les interblocages:

● ignorer complètement les problèmes;
● les détecter et y remédier;
● les éviter dynamiquement en allouant les ressources avec precaution;
● les prévenir en empêchant l'apparition d'une des 4 conditions de leur existence.

1
PSE LI2 S3/2019-2020Pr. Thiam
Ministère de l’Enseignement Supérieur et de la Recherche
Université de THIES

UFR en Sciences et Technologies (UFR SET)

Département Informatique : Licence 2 en Informatique (L2)
INF 2341 : Systèmes d’Exploitation 2
1.2 Quelques solutions
1.2.1 La polique de l’Autruche
Les mathématiciens trouvent cette approche inacceptable et disent que les interblocages
doient absolument être évités. Les informaticiens cherchent à connaître la fréquence du
phéomène et à déterminer sa gravité.
1.2.2 La détection et la reprise
Cette approche est optimiste. Elle consiste à laisser les interblocages se produire, puis à tenter
de les détecter et d'y remédier à posteriori. Avec un exemplaire de différents types de
ressources: Il existe de nombreux algorithmes de détection de cycles dans les graphes
orientés.
Un exemple d'algorithme simple qui examine le graphe et s'arrête lorsqu'il a détecté un
circuit ou examiné tous les noeuds
1. Prendre un noeud N du graphe, N devient noeud courant Nc aller à (2).
2. Initialiser L à une liste vide et indiquer que les arcs ne sont pas marqués.
3. Ajouter le noeud courant Nc à la fin de la liste s'il n y figure pas déjà. Sinon, un circuit est
détecté et l'algorithme se termine.
4. Aller à (5) s'il y a un arc non marqué partant de Nc. Sinon aller à (6).
5. Prendre l'arc et le marquer. Nc devient le noeud de destination, aller à (3).
6. Revenir au noeud précédent, si ce noeud est le noeud de départ, aller à (1). Sinon , ce nœud
devient Nc, aller à (4).
Exemple : R, S, T, U, V, W plusieurs types de ressources (1 exemplaire chacune)

Le graphe et un circuit extrait du graphe

2 Application
2.1 Exercice 1
Étant donné le graphe d'allocation des ressources de la figure suivante. 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 P1, P2, P5, P6.
● Aucune des réponses antérieures n'est correcte.

2
PSE LI2 S3/2019-2020Pr. Thiam
Ministère de l’Enseignement Supérieur et de la Recherche
Université de THIES

UFR en Sciences et Technologies (UFR SET)

Département Informatique : Licence 2 en Informatique (L2)
INF 2341 : Systèmes d’Exploitation 2

2.2 Exercice 2
Un système S accepte cinq utilisateurs, S = {U1, U2, U3, U4, U5}. Chaque utilisateur peut
déclarer des processus, des fichiers, des tampons (qui sont utilisés pour les entrées-sorties de
fichiers : un tampon par fichier ouvert) et des messages.
On veut étudier l'utilisation des ces quatre classes de ressources, lors de divers phases du
système, et pour cela on relève certains compteurs à différents instants:
à l'instant t :
● l'utilisateur U1 a obtenu 5 processus, 30 fichiers, 10 tampons et 30 messages, et il
demande 10 processus, 100 fichiers, 30 tampons et 40 messages.
● l'utilisateur U2 a obtenu 5 processus, 10 fichiers, 10 tampons et 5 messages, et il demande
30 processus, 150 fichiers, 40 tampons et 40 messages.
● l'utilisateur U3 a obtenu 10 processus, 50 fichiers, 5 tampons et 5 messages, et il demande
20 processus, 60 fichiers, 10 tampons et 10 messages.
● l'utilisateur U4 a obtenu 10 processus, 10 fichiers, 10 tampons et 5 messages, et il
demande 20 processus, 60 fichiers, 15 tampons et 5 messages.
● l'utilisateur U5 a obtenu 10 processus, 50 fichiers, 10 tampons et 5 messages, et il
demande 20 processus, 60 fichiers, 15 tampons et 5 messages.
à l'instant v :
● l'utilisateur U1 a obtenu 10 processus, 20 fichiers, 5 tampons et 5 messages, et il demande
20 processus, 70 fichiers, 20 tampons et 15 messages.
● l'utilisateur U2 a obtenu 10 processus, 20 fichiers, 5 tampons et 15 messages, et il
demande 40 processus, 100 fichiers, 50 tampons et 40 messages.
● l'utilisateur U3 a obtenu 10 processus, 20 fichiers, 5 tampons et 5 messages, et il demande
30 processus, 150 fichiers, 10 tampons et 40 messages.
● l'utilisateur U4 a obtenu 10 processus, 20 fichiers, 5 tampons et 10 messages, et il
demande 20 processus, 40 fichiers, 10 tampons et 30 messages.
● l'utilisateur U5 a obtenu 10 processus, 20 fichiers, 10 tampons et 5 messages, et il
demande 10 processus, 40 fichiers, 30 tampons et 15 messages.
On précise que la demande d'un utilisateur est sa demande totale, à l'instant considéré, qu'elle
inclut les ressources qui lui ont déjà été attribuées, qu'un utilisateur qui ne reçoit pas toutes ses
demandes est bloqué en attente, et que le système comporte au maximum 50 processus, 200
fichiers, 50 tampons et 50 messages.
Question 1
Notation :
● le vecteur X représente le nombre total de ressources dans chaque classe,
● le vecteur R représente les ressources non allouées dans chaque classe,
● la matrice A représente les ressources de chaque classe allouées à chaque utilisateur,
● la matrice D représente les ressources de chaque classe demandées par chaque utilisateur.

3
PSE LI2 S3/2019-2020Pr. Thiam
Ministère de l’Enseignement Supérieur et de la Recherche
Université de THIES

UFR en Sciences et Technologies (UFR SET)

Département Informatique : Licence 2 en Informatique (L2)
INF 2341 : Systèmes d’Exploitation 2
Présenter les états du système aux instants t et v du modèle faisant intervenir les vecteurs X et
R, ainsi que les matrices A et D. Déterminer s'il y a interblocage à l'instant t ou à l'instant v.
Question 2
Pour prévenir l'interblocage, on décide de fixer la demande maximale de chaque utilisateur à
30 processus, 150 fichiers, 40 tampons et 40 messages. Déterminer si les états du système aux
instants t et v sont fiables.
Pour répondre aux demandes, on envisage de placer le système à l'instant w dans l'état suivant
à l'instant w :
● l'utilisateur U1 a obtenu 5 processus, 10 fichiers, 2 tampons et 0 message,
● l'utilisateur U2 a obtenu 5 processus, 10 fichiers, 3 tampons et 0 messages,
● l'utilisateur U3 a obtenu 5 processus, 20 fichiers, 2 tampons et 0 messages,
● l'utilisateur U4 a obtenu 5 processus, 40 fichiers, 10 tampons et 5 messages,
● l'utilisateur U5 a obtenu 5 processus, 10 fichiers, 3 tampons et 10 messages.
Déterminer si cet état est fiable
Question 3
Pour éviter plus facilement l'interblocage, on décide de limiter la demande de l'utilisateur à 10
processus, 40 fichiers, 10 tampons et 10 messages. Dans ce cas, il n'y a jamais pénurie de
ressources. Comme cela semble trop restrictif, quelqu'un propose de réorganiser le système
pour qu'il comporte 51 processus, 200 fichiers, 50 tampons et 50 messages et ensuite de
limiter la demande de chaque utilisateur à 11 processus, 40 fichiers, 10 tampons et 10
messages. Déterminer si l'interblocage est possible (en envisageant le cas le plus défavorable).
Une autre proposition est de réorganiser le système pour qu'il comporte 51 processus, 201
fichiers, 50 tampons et 50 messages et ensuite de limiter la demande de chaque utilisateur à
11 processus, 41 fichiers, 10 tampons et 10 messages.
Déterminer si l'interblocage est possible.

4
PSE LI2 S3/2019-2020Pr. Thiam