Ecole Nationale des Sciences de l’Informatique
A. U. : 2015/2016
Devoir Surveillé
Systèmes d’exploitation Programmation Concurrente
Classes
Durée
: II2
: 2h00
Date
: 20/11/2015
Nb. Pages
: 5
Documents : Non autorisés
Enseignants: F. Najjar, M. S. Ouerghi, N. Chakchouk
Note: On demande des réponses brèves mais claires, précises et concises
Exercice 1. Questions de cours (4,5 points –1,5+1+1+1)
1) Donnez le(s) terme(s) technique correspondant à chacune des phrases suivantes :
a) L’un des rôles importants d’un système d’exploitation est de masquer la mise en œuvre
des services (ou fonctions systèmes).
b) Section de code qui doit s’exécuter de manière atomique afin d’éviter les conditions de
vitesse.
c) Fonction système de clonage du processus (Unix) courant.
d) Etat d’un processus qui n’est pas en cours d’exécution mais éligible à être ordonnancé.
e) L’intervalle de temps entre le lancement d’un processus et sa fin
f) Un dispositif matériel qui permet au système d'exploitation la protection des
processus en exécution
2) Donnez la définition d'un interblocage et précisez la différence avec un blocage.
3) Expliquez ce qu'est la famine.
4) Combien de files d’attente sont nécessaires pour implémenter un moniteur ?
5) Optionnelle (2 points) : Ecrire un programme C qui engendre 6 processus liés au ancêtre
de la manière suivante:
1/6
Exercice 2. Synchronisation par pthread_join (3,5 points)
La manipulation des matrices et des vecteurs est champ particulièrement propice pour la
programmation concurrente (ou parallèle).
On vous demande d’écrire un programme multithtreadé (Pthread) qui calcule la somme de tous
les éléments d’une matrice M(m,n) et l’affiche en utilisant n threads concurrents qui calculent
partiellement et retournent (par pthread_exit) la somme sur une colonne passée en paramètre.
Indications :
Les éléments de la matrice sont supposés être entrés aléatoirement (ou par appel à une
procédure init_mat(int M[m][n]) que vous n’êtes pas censés écrire) ;
La variable somme totale (ST) est déclarée dans la fonction main.
Utiliser les pthread_join afin de récupérer les sommes partielles.
Exercice 3. Ordonnancement (7 points –4+2+1)
On suppose disposer d’un ordonnanceur qui admet les caractéristiques suivantes :
Plus la valeur de priorité est grande et plus la priorité est grande.
L’ordonnancement est basé sur une priorité préemptive.
Soient trois processus P1, P2, et P3, ayant les codes et caractéristiques comme suit :
P1
(Priorité =1, prêt à t=0)
begin
1. <code séquence A> //Exécution en 2 ut
2. P(X);
3.
4. V(X);
5. <Code séquence B> //Exécution en 3 ut
End
Section critique //Exécution en 4 ut
P2
(Priorité =2, prêt à t=3)
P3
(Priorité =3, prêt à t=10)
begin
1. <code séquence A> //Exécution en 2 ut
2. P(X) ;
3.
4.
5.
6. V(Y) ;
7. <Code séquence B> //Exécution en 3 ut
end
P(Y) ;
Section critique //Exécution en 4 ut
V(X) ;
begin
1. <code séquence A> //Exécution en 2 ut
2. P(Y) ;
3.
4.
5.
6. V(X) ;
7. <Code séquence B> //Exécution en 3 ut
end
P(X) ;
Section critique //Exécution en 4 ut
V(Y) ;
2/6
Où ut représente une unité de temps, X, Y sont deux sémaphores d’exclusion mutuelle (init.
à 1), et les opérations P et V s’exécutent pendant un temps nul. En plus le temps de
commutation est aussi négligeable.
1) Donnez le diagramme de GANTT (voir annexe) correspondant à cet ordonnancement en
supposant les notations suivantes :
Publicité
‘’A’’ signifie que le processus est en train d’exécuter la <séquence de code A>
‘’B’’ signifie que le processus est en train d’exécuter la <séquence de code B>
‘’X’’ signifie que le processus détient le sémaphore X et qu’il occupe actuellement la
section critique.
‘’Y’’ signifie que le processus détient le sémaphore Y et qu’il occupe actuellement la
section critique.
‘’2’’ signifie que le processus détient les deux sémaphores et qu’il occupe
actuellement la section critique.
‘’ ‘’ signifie que le processus n’est pas en exécution (pour n’importe quelle raison)
Puis calculez :
a) le temps de réponse de chaque processus et le temps de réponse moyen
b) le temps d’attente de chaque processus et le temps d’attente moyen
c) le rendement de l'Unité Centrale (CPU) qui est défini comme le rapport temps pendant
lequel la CPU exécute les processus/temps total de traitement
2) Reprendre la question 1) avec les changements suivants :
P1 a la priorité 1, P2 a la priorité 3 et P3 a la priorité 2
P1 arrive au temps 0, P2 est prêt au temps 6 et P3 est prêt au temps 3
Conclure
3) Afin d’apporter une solution au problème généré rencontré dans la question 2) proposer
une modification dans le code des processus.
Exercice 4. Synchronisation (5 points –1+2+3)
Deux villes A et B sont reliées par une seule voie de chemin de fer.
Les règles de circulation sont les suivantes :
3/6
− La voie ne doit jamais être empruntée simultanément par deux trains allant en sens
inverse
− La voie peut être empruntée par un ou plusieurs trains allant tous dans le même sens
− La priorité de parcours est la même pour les deux sens.
On considère deux classes de processus : les trains allant de A vers B : « T-AB » et les trains
allant de B vers A : « TBA ».
Processus T-AB
Début
Entree_A();
Circulation sur la voie de A vers B ;
Sortie_B();
Fin.
Processus T-BA
Début
Entree_B();
Circulation sur la voie de B vers A ;
Sortie_A();
Fin.
1) Quelle est la différence entre ce problème et le modèle des lecteurs/rédacteurs ?
2) Expliquer pourquoi la solution suivante (avec moniteurs) n’est pas correcte.
Monitor AB ;
int nbA , nbB ;
condition ca, cb ;
void Entree_A() { nbA++ ; if (nbB >0) wait(ca) ; }
void Entree_B() { nbB++ ; if (nbA >0) wait(cb) ; }
void Sortie_B() { nbA-- ; if (nbA==0) signal(cb) ; }
void Sortie_A() { nbB-- ; if (nbB==0) signal(ca) ; }
begin
nbA =0 ; nbB =0
end AB.
3) Donnez une correction de la solution erronée.
Bon travail
4/6
Nom & Prénom :
Classe :
CIN :
ANNEXE
1) Diagramme de Gantt 1 : ordonnancement avec priorité avec Préemption
0 1 2 3 4 5 6 7 8 9 1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
2
3
Publicité
2
4
2
5
2
6
2
7
2
8
2
9
3
0
2) Diagramme de Gantt 2 : ordonnancement avec priorité avec Préemption
0 1 2 3 4 5 6 7 8 9 1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
3
0
P1
P2
P3
P1
P2
P3
5/6
Proposition de Correction
Exercice 1. QC
a. ) The goal of an operating system that concerns making services easy to understand and combine
Answer: Abstraction
b.) Section of code that must be executed atomically to avoid race conditions
Answer: Critical Section
c) Process creation method that starts by making a copy of the current process
Answer: Fork (or Fork/Exec)
d) State of a process that is not currently running, but is eligible to be scheduled
Answer: Ready
e) The time elapsed between when a process starts and when it completes
Answer: Response time
f. Un dispositif matériel qui permet au système d'exploitation la protection des processus en exécution
Réponse : Mode d’exécution
1) Donnez la définition d'un interblocage et précisez la différence avec un blocage.
Réponse : Le blocage d’un processus correspond à l’attente d'éléments dont il a besoin et qui ne
sont pas disponibles (attente de la réalisation d’une demande d’E/S, attente du signalement d’un
événement, …). Un ensemble de processus est en interblocage si et seulement si tout processus de
l'ensemble est en attente d'un évènement qui ne peut être réalisé que par un autre processus de
l'ensemble.
2) Expliquez ce qu'est la famine.
Réponse : la famine est le fait qu’un processus demande d’accès à une ressource ou de passer un
certain point de synchronisation pûre et se voit perpétuellement différé l’exécution de sa
demande.
3) Combien de files d’attente sont nécessaires pour implémenter un moniteur ?
Réponse : Il faut une file d’attente pour mémoriser les demandes d’accès au moniteur (une par
fonction du moniteur) et une file d’attente pour chaque variable de condition. Il faut
éventuellement, une file d’attente des processus suspendus dans le moniteur suite à l’opération
signal(x). Si cette dernière file est gérée, elle est plus prioritaire que la file d’attente du moniteur
6) Optionnelle (2 points) : Ecrire un programme C qui engendre 6 processus liés au ancêtre
Publicité
de la manière suivante:
#include <unistd.h>
int main(){
if (fork())
(fork() || ( fork()) && fork() )) && fork() ;
else
fork() ;
return 0 ; }
6/6
Exercice 3. Ordonnancement
1)
Job throughput: 3 jobs in 27 time units = 1/9 jobs/time-unit
Average turnaround time: job 1: 27 time unit turnaround.
job 2: 21 time unit turnaround.
job 3: 11 time unit turnaround.
Average: (27 + 21 + 11) / 3 = 59 / 3 = 19 2/3
3)
Job throughput: _________0________________
Average turnaround time: _________infinity!___________
4) Respecter le même ordre d’appel de sémaphores mutex dans les deux processus P2 et P3. Ainsi,
ineverser par exemple l’ordre des appels P(Y) et P(X) dans P3 ;
Exercice 4 : synchronisation
Deux villes A et B sont reliées par une seule voie de chemin de fer.
Les règles de circulation sont les suivantes :
− La voie ne doit jamais être empruntée simultanément par deux trains allant en sens inverse
− La voie peut être empruntée par un ou plusieurs trains allant tous dans le même sens
− La priorité de parcours est la même pour les deux sens.
On considère deux classes de processus : les trains allant de A vers B : « T-AB » et les trains allant de B
vers A : « TBA ».
Processus T-AB
Début
Entree_A(); Circulation sur la voie de A vers B ; Sortie_B();
Fin.
Processus T-BA
Début
Entree_B(); Circulation sur la voie de B vers A ; Sortie_A();
Fin.
1) Quelle est la différence entre ce problème et le modèle des lecteurs/rédacteurs ?
7/6
Réponse : La différence est que dans le modèle lecteur/rédacteur, on ne peut trouver qu’un seul
rédacteur à la fois entrain d’occuper la ressource partagée (fichier) alors que dans ce problème la
ressource (la voie) peut être occupée par plusieurs processus en même temps et ceci pour les deux
classes T-AB et T-BA.
2) Expliquer pourquoi la solution suivante (avec moniteurs) n’est pas correcte.
Monitor AB ;
int nbA , nbB ;
condition ca, cb ;
void Entree_A() { nbA++ ; if (nbB>0) wait(ca) ; }
void Entree_B() { nbB++ ; if (nbA>0) wait(cb) ; }
void Sortie_B() { nbA-- ; if (nbA==0) signal(cb) ; }
void Sortie_A() { nbB - - ; if (nbB==0) signal(ca) ; }
begin
nbA =0 ; nbB =0
end AB.
Réponse :
L’erreur dans la solution donnée est qu’en utilisant un seul compteur (nbA et nbB) pour chaque classe
on n’arrivera pas à différencier le nombre de processus entrain d’utiliser la voie de celui qui est
attente. Et cette solution peut induire un problème d’interblocage comme par exemple le cas où A1, B1,
A2 arrivent successivement, à la sortie de A1, nbA sera égal à 1 et donc B1 reste bloqué sur cb en
attente d’être débloqué et A2 reste bloqué sur ca en attente d’être débloqué par B1.
3) Donnez une correction de la solution erronée.
Réponse :
Monitor AB
int nbA, nbB, attA, attB;
condition ca, cb ;
//
void Entree_A() {
if (nbB>0) { attA++ ; wait(ca) ; }
nbA++ ; if (attA>0) { attA-- ; signal(ca) ; }
}
/*/
void Sortie_B() {
nbA-- ;
if (nbA==0) { if (attB>0) { attB-- ; signal(cb) } }
}
/*/
void Entree_B() {
if (nbA>0) { attB++ ; wait(cb) }
nbB++ ; if (attB>0) { attB-- ; signal(cb) ; }
}
//
void Sortie_A() {
nbB-- ;
if (nbB==0) { if (attA>0) { attA-- ; signal(ca) } }
}
/*/
begin
/Initialisation / nbA=0, nbB=0, attA=0, attB=0 ;
end.
8/6
9/6