Ecole Supérieure de Technologie Mai 2014

et d’Informatique 1ère année Ingénieur

____***____ ____***____

EXAMEN DE LA SESSION PRINCIPALE

SYSTÈME D’EXPLOITATION
Enseignantes : Mme. E. Menif et Mme. K. ElBedoui, Nom : ……………………………………………………..
Formation : Ingénieur Informatique Prénom : ……………………………………………………..
Niveau / Groupes : 1ère année/ A, B, C, D, E et F C.I.N : ……………………………………………………..
Documents : Non Autorisés Section : ……………………………………………………..
Calculatrice : Non Autorisée Salle : ……………………………………………………..
Nombre de pages : 6
Durée : 1 h 30 min
Barème : 4; 4; 5 ; 5 ; 2;

Exercice 1 : Questions de cours 4pts, 10 min

1. Compléter le tableau suivant :

Table Structure Utilité

1 bit par bloc du disque Sert à gérer l’espace libre sur disque ou en mémoire
Table de bits
(0,25 + 0,25)

Une entrée par page : numéro Sert à indiquer quelles pages sont chargées et dans quels
Table de pages
(0,25 + 0. 50) du cadre où est chargée la page cadres

Une entrée par Sert à assurer une gestion cohérente des processus
Table de processus processus chargé: un pointeur notamment lors des commutations
(0,25 + 0. 50)
vers le PCB du processus

2. Compléter le tableau suivant :

Terme SE correspondant Utilité

Cluster(0,25 + 0,25) Windows un ensemble de secteurs

Clock(0,25 + 0,25) Linux Algorithme de remplacement de page

Linux/unix structure sauvegardant les indices des blocs utilisés par un

i-node(0,25 + 0,25)
fichier

Jiffies(0,25 + 0,25) Linux un jiffy = un top horloge

Page | 1
 NE RIEN ECRIRE ICI

Exercice 2 : Pagination 4 pts, 15 min

On considère un système disposant d’une mémoire centrale de taille 12KO initialement libre. On
suppose que la mémoire est paginée avec des pages de taille 4K et que l’algorithme de remplacement
de page adopté est OPT. Au cours de l'exécution d’un processus de taille 18KO, on suppose avoir
dans l’ordre les dix référencements suivants :

0, 1, 2, 3, 2, 1, 3, 0, 2, 1

On vous demande de :

1. Déterminer le type et la valeur de la fragmentation.

Il s’agit de la fragmentation interne. L’espace d’adressage du processus nécessite 18/4 = 4.5 soit 5
pages. La 5ème page n’est pas utilisée entièrement 0.25

La valeur de la fragmentation interne est : (4*5)-18 = 2 Ko 0.25

2. Dresser l’évolution de la mémoire centrale et de la table de pages

Réf 0 1 2 3 2 1 3 0 2 1
Cadre0 0 0 0 3 3 3 3 0 0 0
Cadre1 1 1 1 1 1 1 1 1 1
Cadre2 2 2 2 2 2 2 2 2
Défaut de X X X X X
page 0.25 0.25 0.25 0.25 0.25 0.25 0.25

Pages 0.25 0.25 0.25 0.25 0.25 0.25 0.25

0 0 0 0 * * * * 0 0 0
1 * 1 1 1 1 1 1 1 1 1
2 * * 2 2 2 2 2 2 2 2
3 * * * 0 0 0 0 * * *
4 * * * * * * * * * *

Page | 2
Exercice 3 : Ordonnancement des processus et gestion de la mémoire 5 pts, 25
min
On considère un système disposant des informations suivantes :

Processus Date d’arrivée Références aux pages Taille Temps CPU

A 0 1; 0 10 KØ 4 ms (2; 2)
B 1 0; 1 14 KØ 4 ms (2; 2)
C 3 0; 1; 2; 3 30 KØ 5 ms (2; 1; 1; 1)
Le système utilise les hypothèses suivantes :
● La mémoire centrale comporte trois cadres (initialement libres).
● L'utilisation de la technique de pagination avec la taille d'une page est de 8 KØ.
● La pagination est à la demande (la page n'est chargée en RAM que ssi elle est demandée).
● Le remplacement de pages se base sur l'algorithme LRU.
● Tant qu'une page est utilisée par le processeur, elle reste en RAM.
● Si un processus termine son exécution alors ses pages sont retirées du système.
● L’ordonnancement sur le processeur se fait selon la stratégie RR avec Q=2.
1. Déterminer le nombre de bits nécessaires pour représenter un déplacement. 0.50
Taille d’une page = 8 ko = 23*210 o= 213 octets d’où il nous faut 13 bits pour adresser les différents
octets d’une page
2. Déterminer le nombre de bits nécessaires pour représenter le numéro d’un cadre. 0.50
La RAM contient trois cadres, d’où il nous faut 2 bits pour adresser les cadres
3. En déduire la taille d’une adresse physique. 0.50
Une adresse physique =(n°cadre, déplacement)
Une adresse physique nécessite 2+13 = 15 bits
4. Dresser l'évolution de l'état de processeur et de l’état de la RAM aux différentes étapes de
traitement de ces processus.
Processeur A A B B A A C C B B C C C 0.50
temps

Actif A A B B A A C C B B C C C

Prêt B A A C C B B C C
C B B
Bloqué 0.25 0.25 0.25 0.25 0.25 0.25

1A 1A 0B 0B 0A 0A 0C 0C 1B 1B 1C 2C 3C

RAM SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE SE

Cadre 0 1A 1A 1A 1A 1A 1A 0C 0C 0C 0C 0C 0C 3C
Cadre 1 0B 0B 0B 0B 0B 0B 0B 0B 1C 1C 1C
Cadre 2 0A 0A 1B 1B 2C 2C
0.25 0.25 0.25 0.25 0.25 0.25

Page | 3
Exercice 4 : Section Critique 5 pts, 25
min

Deux villes A et B sont reliées par une seule voie de chemin de fer. Les trains circulant sur cette voie
peuvent être classés en deux groupes:
● les trains allant de A vers B (Train AversB)
● les trains allant de B vers A (Train BversA).
Sur cette voie, la gestion de la traversée se passe comme suit :
Chaque train d’un groupe donné demande l’accès à la voie dans un sens qui lui est défini (de A vers B
ou de B vers A). Si la voie n’est pas occupée par des trains de l’autre groupe l’autorisation de passage
est permise. Une fois que ce train ait l’autorisation de passage alors il signale l’autorisation de
traverser la voie au train suivant en attente et du même groupe, s’il y en a bien sûr, et ainsi de suite
jusqu’au dernier train qui donnera, cette fois-ci, l’autorisation de passage à l’autre groupe bloqué s’il y
en a.
On se propose de gérer la circulation sur la voie, pour ce faire on suppose que chaque train fait appel à
des fonctions qui peuvent se décrire, selon son groupe, comme suit :
Train AversB :
Demande_voie_AversB( ) ;
Circulation sur la voie de A vers B;
Sortie_voie_par_B( );
Train BversA :
Demande_voie_BversA( ) ;
Circulation sur la voie de B vers A;
Sortie_voie_par_A( );

Ville A ⬟ ⬟ Ville B

1. Préciser la ressource critique dans ce problème.

La ressource critique dans ce problème est la voie ferrée 0.25

2. Préciser le rôle de chacune des deux principales fonctions (Demande… et Sortie…) de chaque
groupe.
Les fonctions DemandeX servent à demander l’utilisation exclusive de la ressource critique qu’est la
voie et par conséquent à entrer en section critique 0.25

Quant aux fonctions SortieX servent à libérer la ressource critique après avoir terminé l’utilisation de
la ressource critique. 0.25

Page | 4
 NE RIEN ECRIRE ICI

3. En quoi ce problème diffère de celui de lecteurs/rédacteur ?

L’équivalent de la base de données est ici la voie le premier groupe des trains peut représenter
les lecteurs et le deuxième groupe les rédacteurs ou inversement. Dans le cas du problème du
lecteur/rédacteur, tant qu’il y a un lecteur (groupe i), d’autres lecteurs (groupe i) peuvent
accéder la base, mais dès qu’il a un rédacteur (groupe j) aucun autre rédacteur ni lecteur
(groupe i , groupe j) ne peut accéder à la base. Par contre, dans le problème des trains, s’il y a
un train d’un groupe qui occupe la voie alors tous les trains du même groupe peuvent utiliser
la voie. 0.25
On se propose de résoudre le problème en utilisant les sémaphores.

int NbAB = 0 ; // donne le nombre de trains traversant la voie de A vers B

int NbBA = 0 ; // donne le nombre de trains traversant la voie de B vers A
semaphore S1, S2, M1, M2 ;
Sem_Init (S1, 1); // pour permettre que des trains de sens contraire ne s'engagent pas dans la voie en
même temps
Sem_Init (S2, 1); // pour protéger la ressource critique
Sem_Init (M1, 1); // pour protéger la mise à jour en exclusion mutuelle de la variable partagée NbAB
Sem_Init (M2, 1); // pour protéger la mise à jour en exclusion mutuelle de la variable partagée NbBA
Demande_voie_AversB ( )
{
P(S1) ; //demander l’autorisation de manipuler la voie 0.25
P(M1) ; //demander l’autorisation de mettre à jour NbAB 0.25
NbAB = NbAB+1 ; //mise à jour
Si(NbAB ==1) //premier train de A vers B
P(S2); // bloquer les trains du sens contraire 0.25
V(M1) ; //libérer NbAB 0.25
V(S1) ; // libérer la voie 0.25
}

Page | 5
Sortie_voie_par_B ( )
{
P(M1) ; //demander l’autorisation de mettre à jour NbAB 0.25
NbAB = NbAB-1 ; //mise à jour
Si(NbAB ==0) //dernier train de A vers B
V(S2); // débloquer les trains du sens contraire 0.25
V(M1) ; //libérer NbAB 0.25
}
Demande_voie_BversA()
{
P(S1) ; 0.25
P(M2) ; 0.25
NbBA = NbBA +1;
Si(NbBA ==1)
P(S2); 0.25
V(M2) ; 0.25
V(S1) ; 0.25
}
Sortie_voie_par_A ( )
{
P(M2) ; 0.25
NbBA = NbBA -1;
Si(NbBA ==0)
V(S2); 0.25
V(M2) ; 0.25
}
 Exercice 5 : Synchronisation des processus 2 pts, 5
min

Voici le graphe de précédence de quatre processus P1, P2, P3 et P4 :

Proposer une solution, à l’aide de sémaphores, pour

synchroniser ces processus tels présentés dans le graphe.

Chaque procédure Ai représente l’action du processus Pi.

P1( ) P2( ) P3( ) P4( )

{ { { {
A1( ); P(S12); 0.25 P(S13); 0.25 P(S24); 0.25
V(S12); 0.25 A2( ); A3( ); P(S34); 0.25
V(S13); 0.25 A4( );
V(S24); 0.25 V(S34); 0.25 }
} }
}