Université Aboubekr BELKAID
كلية العلوم – تيجاني هدام
Faculté des Sciences – Tidjani HAddam
قسم اإلعالم اآللي
Département d’informatique
Classe LMD S5 Informatique
Année Universitaire : 2013 / 2014
Mr Benaissa Mohamed
Examen N°1 : Module système d’exploitation
Questions de cours
Q1 : citez une solution logicielle et une solution matérielle pour résoudre le problème
d’exclusion mutuelle.
Q2 : Expliquez ce qui peut arriver si la file d’attente d’un sémaphore est gérée selon la
discipline LIFO (last in first out).
Q3 : quelle est la différence entre les primitifs d’un moniteur et les primitifs d’un
sémaphore pour la synchronisation de processus.
Q4 : quelle sont les primitifs systèmes utilisées dans l’envoi et la réception d’un
signale ?comment peut on ignoré le traitement d’un signal ?
Q5 : quelle est la différence entre un tube nommé et un tube anonyme ? Indiquez les fonctions
systèmes utilisées pour la création d’un tube nommé et d’un tube anonyme.
Exercice N° 1
Vous avez le système suivant :
R1 R2 R3 R1 R2 R3 R1 R2 R3
P1 3 3 0 P1 6 6 3 0 3 3
P2 3 0 0 P2 3 3 3
Disponible
P3 3 0 3 P3 X Y Z
P4 0 3 0 P4 3 6 6
Allocation Max
Q1 : calculer la matrice besoin
Q2 : Quelle est la valeur maximale demander par P3 (x,y,z) pour laquelle l’état de système
reste stable et sain (en appliquant l’algorithme de banquier pour trouver x, y et z).
Q3 : Combien faut-il ajouter de ressources (pour chaque Ri) de manière à ce que les
processus puissent s’exécuter sans contrainte (en prendre en considération la valeur de x, y et
z trouves dans la question 2 : matrice Max).
Q4 : Si le processus P1 déposé la requête (0, 2, 1), cette requête est-elle acceptée
immédiatement ? (Justifiez votre réponse).
Q5 : quelle est le nombre totale des exemplaires de ressources R1, R2 et R3 dans ce système ?
Exercice N°2
Une ligne de chemin de fer comporte une section à voie unique ne laisse passer qu’un seule
train et qui peut être traversé par un ensemble de voiture en même temps.
Q1 : Quel est le modèle vu dans le cours qui ressemble à ce problème (modèle
producteur/consommateur où modèle lecteur/rédacteur) ?
- Ce problème de conflit entre les trains et les voitures doit respecter les conditions
suivantes :
1- La priorité est donnée aux voitures si et seulement si une voiture est entraîne de traversé la
section.
2- Lorsque un train sort de la section il réveil en premier lieu une voiture sinon un train.
Q2 : indiquer les contraintes d’exclusion mutuelle dans ce problème.
Q3 : Résoudre ce problème en utilisant les moniteurs en respectant les conditions indiquées
Pour résoudre ce problème utilisé les procédures suivants :
- procédure entré_voiture, procédure sortie_voiture, procédure entré_train, procédure
sortie_train
- Plus un variable booléen passage_train qui prend une valeur vrai si le train est entraîne de
traversé la section sinon faux
Exercice N°3
Dans une ville, un coiffeur possède un petit salon ayant une porte d’entrée, une porte de
sortie, un fauteuil de coiffure et N chaises. Les clients arrivent par la porte d’entrée et sortent
par la porte de sortie après avoir eu leur coupe de cheveux.
Comme le salon est petit, uniquement le client sur le fauteuil de coiffure peut- être servi à un
moment donné par le coiffeur. Le coiffeur passe sa vie entre dormir et servir ses clients.
Quand il n’a aucun client, le coiffeur dort. Quand un client arrive et le fauteuil est libre, il
s’assoit dans le fauteuil et il réveille le coiffeur.
Si le fauteuil n’est pas libre, le client occupe une chaise s’il y a des chaises de libre ou il
attend qu’une chaise se libère sinon.
Un client sur une chaise attend que le fauteuil se libère.
Après avoir fini une coupe, le coiffeur fait sortir le client servi et s’endort.
1. un processus Client dans lequel sont identifiés clairement ses états : en attente d’une
chaise, sur une chaise en attente du fauteuil, sur le fauteuil en attente de la fin de sa
coupe et servi.
2. un processus Coiffeur avec les états endormi et en service
Pour résoudre ce problème nous utilisons 3 sémaphores et un compteur
Sémaphore Clients : bloque le coiffeur s’il n’y a pas de clients
Sémaphore Mutex : accès exclusif à la zone critique (client + fauteuil)
Sémaphore Coiffeur : bloque le client si le coiffeur est occupé avec un autre client
cpt = 0 : Le nombre de clients en attente
Il y a 5 chaises.
Q1 : quelle est le rôle joué par sémaphore mutex
Q2 : quelle est le rôle joué par le sémaphore client et le sémaphore coiffeur
Q3 : quelle est la valeur initiale des sémaphores clients, mutex et coiffeur
Q4 : compléter la solution de problème (remplir les vides) synchronisation entre le coiffeur et
ses clients en ajoutons les différents primitives de synchronisation entre coiffeur et client en
utilisons les 3 sémaphores:
Semaphore Client ;
Semaphore Mutex ;
Semaphore Coiffeur ;
cpt:entier (initialisee a 0) ;
chaises =5
//Coiffeur //Client
void coiffeur() { void client() {
P(Mutex)
{---vide1---} if (cpt < Chaises) {
{---vide2---} cpt = cpt+1
cpt = cpt – 1; {---vide5---}
{---vide3---} v(Mutex)
{---vide4---} {---vide6---}
Couper_cheveux(); Obtenir_coupe
} } else {
v(Mutex)
}
}
Université Aboubekr BELKAID
كلية العلوم – تيجاني هدام
Faculté des Sciences – Tidjani HAddam
قسم اإلعالم اآللي
Département d’informatique
--------------------
Classe LMD S5 Informatique
------------------Année Universitaire : 2013 / 2014
Mr Benaissa Mohamed
Correction Examen N°1 : Module système d’exploitation
Questions de cours
Q1 : citez une solution logicielle et une solution matérielle pour résoudre le problème
d’exclusion mutuelle. (1 pts)
Solution logicielle : sémaphore + moniteur
Solution matérielle : la fonction tas+ masquage interruption
Q2 : Expliquez ce qui peut arriver si la fie d’attente d’un sémaphore est gérée selon la
discipline LIFO (last in first out). (1 pts)
Problème de famine
Q3 : quelle est la différence entre les primitifs d’un moniteur et les primitifs d’un
sémaphore pour la synchronisation de processus. (1 pts)
P(s) et v(s) bloque et débloque un processus selon la valeur de e(s)
Wait() et signale() bloque et débloque un processus automatiquement
Q4 : quelle sont les primitifs systèmes utilisées dans l’envoi et la réception d’un
signale ?comment peut on ignoré le traitement d’un signal ? (1 pts)
Signal : réception d’un signale
kill : envoi d’un signale
Avec Le paramètre SIG_IGN : ignore le traitement d’un signal
Q5 : quelle est la différence entre un tube nommé et un tube anonyme ? Indiquez les fonctions
systèmes utilisées pour la création d’un tube nommé et d’un tube anonyme. (1 pts)
Tube anonyme : invisible dans le système créer par la fonction pipe
Tube nommée visible dans le système de gestion de fichier créé par la fonction mkfifo
Q6 : quelles sont les conditions d’apparition d’une situation d’interblocage ?comment éviter
cette situation ? (1 pts)
Les Condition d’inteblocage sont :
Exclusion mutuelle
Pas de réquisition
Occupation et attendre
Attente circulaire
Pour éviter l’interblocage nous utilisons l’algorithme de banquier(etat sain)
Exercice N° 1
Vous avez le système suivant :
R1 R2 R3 R1 R2 R3
R1 R2 R3
P1 3 3 0 P1 6 6 3
0 3 3
P2 3 0 0 P2 3 3 3
P3 3 0 3 P3 X Y Z Disponible
P4 0 3 0 P4 3 6 6
Allocation Max
Q1 : calculer la matrice besoin r(0,5 pts)
R1 R2 R3
P1 3 3 3
P2 0 3 3
P3 X-3 Y Z-3
P4 3 3 6
Q2 : Quelle est la valeur maximale demander par P3 (x,y,z) pour laquelle l’état de système
reste stable et sain (en appliquant l’algorithme de banquier pour trouver x, y et z).(1 pts)
Application l’algorithme de banquier
X=9, y =6, z=6
Q3 : Combien faut-il ajouter de ressources (pour chaque Ri) de manière à ce que les
processus puissent s’exécuter sans contrainte (en prendre en considération la valeur de x, y et
z trouves dans la question 2 : matrice Max). (1 pts)
Utilisation de la matrice besoin
R1 R2 R3
P1 3 3 3
P2 0 3 3
P3 6 6 3
P4 3 3 6
Besoin de r1 =3+0+6+3=12
Besoin de r2 =3+3|+6+3=15
Besoin de r3 =3+3+3+6= 15
Ressource ajouter = besoin –disponible
=(12,15,15)-(0,3,3)=(12,12,12)
Q4 : Si le processus P1 déposé la requête (0, 2, 1), cette requête est-elle acceptée
immédiatement ? (Justifiez votre réponse). (1 pts)
La requête de p1 est acceptée
P1(0,2,1) < = disponible(0,3,3)
P1((0,2,1)< = besoin p1(3,3,3)
Disponible = disponible-requête p1= (0,3,3)-(0,2,1)=(0,1,2)
Besoin p1 =besoin p1 –requête p1=(3,3,3)-(0,2,1)= (3,1,2)
Allocation p1 = allocation p1 + requête p1=(3,3,0)+(0,2,1)=(3,5,1)
Q5 : quelle est le nombre totale des exemplaires de ressources R1, R2 et R3 dans ce système ?
(0,5 pts)
Ressources totale = (r1=9, r2=6,r3=6)
Exercice N°2
Une ligne de chemin de fer comporte une section à voie unique ne laisse passer qu’un seule
train et qui peut être traversé par un ensemble de voiture en même temps.
Q1 : Quel est le modèle vu dans le cours qui ressemble à ce problème (modèle
producteur/consommateur où modèle lecteur/rédacteur) ?
Problème de lecteur rédacteur (1 pts)
- Ce problème de conflit entre les trains et les voitures doit respecter les conditions
suivantes :
1- La priorité est donnée aux voitures si et seulement si une voiture est entraîne de traversé la
section.
2- Lorsque un train sort de la section il réveil en premier lieu une voiture sinon un train.
Q2 : indiquer les contraintes d’exclusion mutuelle dans ce problème. (1 pts)
- Exclusion mutuelle entre train
- Exclusion mutuelle entre train et voiture
- Pas d’Exclusion mutuelle entre les voitures
Q3 : Résoudre ce problème en utilisant les moniteurs en respectant les conditions indiquées
Pour résoudre ce problème utilisé les procédures suivants :
- procédure entré_voiture, procédure sortie_voiture, procédure entré_train, procédure
sortie_train
- Plus un variable booléen passage_train qui prend une valeur vrai si le train est entraîne de
traversé la section sinon faux
Solution par moniteur est
Moniteur voiture-train
Var
Passage-train: booléen; inialise a faux
train, voiture : condition;
nv : entier (compter le nombre de processus voiture) nv = 0
Procédure entrer-voiture (1 pts)
Début
Si (passage-train) alors wait(voiture);
nv : = nv + 1;
Signale(voiture);
fin
Procedure sortie-voiture(1 pts)
Debut
nv:= nv – 1;
Si nv = 0 alors signale (train);
fin
Procedure entrer-train(1 pts)
Debut
si (passage-train) ou (nv >0) alors wait(train);
passage-train := vrai;
fin
Procedure sortie-train(1 pts)
Debut
Passage-train := faux;
Si not empty (voiture) alors signale (voiture)
else signale (train);
fin
Exercice N°3
Dans une ville, un coiffeur possède un petit salon ayant une porte d’entrée, une porte de
sortie, un fauteuil de coiffure et N chaises. Les clients arrivent par la porte d’entrée et sortent
par la porte de sortie après avoir eu leur coupe de cheveux.
Comme le salon est petit, uniquement le client sur le fauteuil de coiffure peut- être servi à un
moment donné par le coiffeur. Le coiffeur passe sa vie entre dormir et servir ses clients.
Quand il n’a aucun client, le coiffeur dort. Quand un client arrive et le fauteuil est libre, il
s’assoit dans le fauteuil et il réveille le coiffeur.
Si le fauteuil n’est pas libre, le client occupe une chaise s’il y a des chaises de libre ou il
attend qu’une chaise se libère sinon.
Un client sur une chaise attend que le fauteuil se libère.
Après avoir fini une coupe, le coiffeur fait sortir le client servi et s’endort.
1. un processus Client dans lequel sont identifiés clairement ses états : en attente d’une
chaise, sur une chaise en attente du fauteuil, sur le fauteuil en attente de la fin de sa
coupe et servi.
2. un processus Coiffeur avec les états endormi et en service
Pour résoudre ce problème nous utilisons 3 sémaphores et un compteur
Sémaphore Clients : bloque le coiffeur s’il n’y a pas de clients
Sémaphore Mutex : accès exclusif à la zone critique (client + fauteuil)
Sémaphore Coiffeur : bloque le client si le coiffeur est occupé avec un autre client
cpt = 0 : Le nombre de clients en attente
Il y a 5 chaises.
Q1 : quelle est le rôle joué par sémaphore mutex(0,5 pts)
Mutex est un semaphore binaire pour l’exclusion mutuelle
Q2 : quelle est le rôle joué par le sémaphore client et le sémaphore coiffeur (0,5 pts)
Semaphore coiffeur et client sont des semaphores de synchronisation
Q3 : quelle est la valeur initiale des sémaphores clients, mutex et coiffeur (1 pts)
Mutex =1
Client =0
Coiffeur =0
Q4 : compléter la solution de problème (remplir les vides) synchronisation entre le coiffeur et
ses clients en ajoutons les différents primitives de synchronisation entre coiffeur et client en
utilisons les 3 sémaphores: (2 pts)
Semaphore Client ;
Semaphore Mutex ;
Semaphore Coiffeur ;
cpt:entier (initialisee a 0) ;
chaises =5
//Coiffeur //Client
void coiffeur() { void client() {
{P(Mutex)}
{p(client)} if (cpt < Chaises) {
{p(mutex)} cpt = cpt+1
cpt = cpt – 1; {v(client)}
{v(coiffeur)} {v(Mutex)}
{v(mutex)} {p(coiffeur)}
Couper_cheveux(); Obtenir_coupe
} } else {
v(Mutex)
}
}
