Annales 3

2 Gestion des processus et synchronisation (8 points)
Troisième année de la licence d’informatique

Système d’exploitation UFR Sciences, site de Luminy, Aix-Marseille Université
Considérons un système équipé d’un seul disque et dans lequel le processeur unique est géré en temps
partagé par l’algorithme du tourniquet.
16 mai 2018, première session
Responsable : Jean-Luc Massat
durée 2 heures, calculatrices et documents autorisés a) Donnez le temps de réponse du processus ci-dessous et le taux d’utilisation du processeur sur la
période considérée. [2 points]
pour i ∈ {1, 2} faire
| calculer pendant i seconde(s)
| écrire sur un fichier pendant 4 secondes
1 Questions... réponses (8 points) fin-pour
Les questions ci-dessous doivent être traitées dans le cadre d’un système d’exploitation moderne, multi- calculer pendant 1 seconde
programmé et doté d’une gestion mémoire performante (n’oubliez pas de justifier vos réponses). Ques-
tions : (un point par question sauf exceptions) b) Même question que précédemment mais nous modifions le processus comme suit (indiquez clairement
sur un schéma le déroulement de l’exécution). [2 points]
a) Sur une zone de 1024 ko gérée par l’algorithme du buddy system, quel est l’état des blocs libres et
occupés après les allocations de 65 ko, 130 ko, 220 ko, 50 ko et 91 ko dans cet ordre ? pour i ∈ {1, 2} faire
| créer un thread pour faire
b) Si le programme P (s); P (t); . . . ; V (s); . . . ; P (t); . . . ; V (t); V (t); . . . ; P (s); V (s); est exécuté | | calculer pendant i seconde(s)
en plusieurs exemplaires, existe-t-il un risque d’interblocage (les compteurs sont initialisés à deux) ? | | écrire sur un fichier pendant 4 secondes
| fin du thread
c) Soient les cinq processus suivants qui démarrent en même temps. Combien faut-il de processeurs fin-pour
pour les exécuter sans contrainte (nous considérerons que les E/S se déroulent en parrallèle) ? Quel attendre la fin des threads fils
est le taux d’utilisation du processeur ? [2 points] calculer pendant 1 seconde
— calculer 3s, E/S sur 4s, calculer 3s c) Si nous considérons que les deux E/S se déroulent sur deux disques différents, quel est l’impact sur
le temps de réponse et le taux d’utilisation du processeur ? [2 points]
— calculer 2s, E/S sur 3s, calculer 1s, E/S de 3s, calculer 1s
— calculer 2s, E/S de 2s, calculer 2s, E/S de 2s, calculer 2s d) En gardant l’organisation en threads, comment modifier le code (avec l’utilisation d’un sémaphore)
pour s’assurer que le calcul de 1 seconde s’exécute en premier et occupe toute la CPU ? [2 points]
— dormir sur 5s, calculer 2s, E/S de 3s
— E/S de 3s, calculer 3s, E/S de 4s

3 Gestion des disques (4 points)
d) Donnez la matrice max de l’algorithme des banquiers pour ces trois processus :
Considérons une machine dotée de 6 disques d’un téra-octet et des circuits d’E/S permettant à ces disques
de réaliser des opérations en parallèle.
— P1 : allouer R1 et R2 , ..., libérer R1 , ..., allouer R3 , R2 et R1 , ..., libérer toutes les resources
a) Quelle est la capacité de stockage pour une configuration RAID5 construite sur les six disques (que
— P2 : allouer R3 et R1 , ..., libérer R3 , ..., allouer R2 et R1 , libérer toutes les ressources
nous noterons par la suite RAID5(D1,D2,D3,D4,D5,D6) ) ? [1 point]
— P2 : allouer R2 et R3 , ..., allouer R2 , ..., allouer R3 , ..., libérer toutes les ressources
b) Même question pour un striping (RAID0) des diques : RAID0(D1,D2,D3,D4,D5,D6) ? [1 point]

e) Si le système reçoit les requêtes ci-dessous, donnez l’ordre de traitement en se basant sur l’algorithme
SSTF (Shortest Seek Time First). La tête de lecture se trouve sur la piste 500.
c) Quelle est la capacité de stockage et le nombre maximum de disques défaillants (sans altérer le bon
200, 150, 320, 700, 210, 100, 600, 705, 490, 150, 310, 610, 150 fonctionnement du système) pour la configuration RAID0( RAID5(D1,D2,D3), RAID5(D4,D5,D6) )
Indiquez par un exemple les disques susceptibles d’être défaillants. [2 points]
f) Dans la FAT ci-dessous combien avons-nous de fichiers et quels sont les blocs physiques de chaque
fichier ? [2 points]
i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
FAT[i] 22 22 13 19 52 -1 20 17 52 15 6 3 -1 -1 4 52 18 -1 -1 8
2 Les philosophes et les banquiers 5 points
Troisième année de la licence d’informatique Un beau jour de mai, 5 philosophes décident d’aller manger ensemble des spaghettis. Le restaurateur
Système d’exploitation UFR Sciences, site de Luminy, Aix-Marseille Université dresse une table ronde, mais place seulement 5 fourchettes (une entre chaque assiette). Pour manger, un
16 mai 2017, première session, philosophe a besoin de deux fourchettes : celle placée à sa droite et celle placée à sa gauche.
durée 2 heures, calculatrices et documents autorisés.
Questions :
A) Montrez qu’il existe un risque d’interblocage et proposez une solution simple à ce problème. [1 point]
1 Exécution d’un processus 9 points B) Pour éviter les interblocages, les philosophes décident d’appliquer l’algorithme des banquiers. Donnez
Considérons le programme ci-dessous : la matrice Max et le vecteur Dispo. [1 point]
// Exécution : faire a fois ( 1 minute de CPU puis 2 minutes d’E/S ) C) Pour ce problème bien particulier donnez l’algorithme simplifié permettant de déterminer si oui
int fa(int a) { ... } ou non, le système est dans un état sain. [2 points]
// Exécution : faire b fois ( 1 minute de CPU puis 3 minutes d’E/S )
D) Le restaurateur place maintenant les cinq fourchettes au centre de la table (chaque philosophe a
int fb(int b) { ... }
toujours besoin de deux fourchettes). Donnez la nouvelle version de la matrice Max et du vecteur
Dispo. [1 point]
// Exécution : 1 minute de CPU
int fc(int s) { ... }
3 Système de gestion de fichiers 6 points
int main() { int a = fa(2); int b = fb(3); return fc(a+b); }
Questions (donnez à chaque fois la trace de l’exécution) : Considérez un système de gestion de fichiers où le disque est géré à l’aide d’une FAT (File Allocation
Table). La FAT est un tableau d’entier qui possède autant de lignes que des blocs sur le disque. Un bloc
A) Si nous avons un seul processeur, quel est le temps de réponse de ce programme et le taux d’utilisation i est libre si fat[i] = FAT FREE. Si le bloc i est le dernier bloc d’un fichier, on a fat[i] = FAT EOF.
de la CPU ? [1 point] Toute autre valeur positive sur fat[i] indique le bloc suivant.
B) Même question si nous disposons de deux processeurs. [1 point] A) Écrivez la fonction d’allocation qui recherche un espace libre de n blocs consécutifs et renvoie
l’adresse du premier bloc (ou −1 en cas d’échec) en se basant sur le principe de meilleur ajustement
(best-fit). La FAT doit être parcourue une seule fois. [2 points]
C) Revenons au processeur unique et considérons que les E/S sont des écritures. Nous disposons
d’un tampon de sortie de 4 minutes. L’opération de vidage de ce tampon est assurée de manière
asynchrone par le système d’exploitation. La fin du processus implique l’attente du vidage du int alloc bloc best fit (int fat[], int taille fat, int n)
tampon. Dans ces conditions quel est le temps de réponse et le taux d’utilisation du processeur ?
[2 points] B) Écrivez la fonction de chaı̂nage de la FAT lorsque les blocs sont alloués par la fonction d’allocation
alloc bloc best fit. Le paramètre debut représente le premier bloc alloué et le paramètre n le
D) Nous avons maintenant deux disques (et donc deux tampons de 4 minutes). La fonction fa() nombre de blocs alloués. Rappel : le dernier bloc d’un fichier a la valeur FAT EOF. [2 points]
utilise un disque et fb() l’autre. Calculez le temps de réponse et le taux d’utilisation du processeur.
[2 points] void chainages(int fat[], int debut, int n)
E) En plus des deux disques (et donc des deux tampons), nous disposons maintenant de trois proces- C) Écrivez la fonction d’allocation alloc bloc frac qui alloue n blocs non-consécutifs et retourne
seurs et nous ajoutons à notre système des fonctions de gestion des threads : l’adresse du premier (ou −1 s’il n’existe pas assez de blocs libres). Rappel : n’oubliez pas d’enchaı̂ner
int th_create(); // 0: fils; numéro:père correctement les blocs sur la fat. [2 points]
void th_exit(); // fin du thread courant
void th_join(int n); // attente de la fin d’un thread int alloc bloc frac (int fat[], int taille fat, int n)
Modifiez la fonction main() pour exécuter les deux fonctions dans deux threads et calculez le
temps de réponse et le taux d’utilisation du processeur. [3 points]
Tournez la page SVP...

3 Ordonnancement de processus 9 points
Troisième année de la licence d’informatique Considérez un système d’ordonnancement qui utilise les structures de données ci-dessous.
11 mai 2016, première session, #define EMPTY (0)
durée 2 heures, calculatrices et documents autorisés. #define READY (1)
#define HIGH (0)
#define LOW (1)
struct {
1 Gestion de ressources 5 points PSW cpu; // Process State Word
Considérez le graphe d’allocation des ressources ci-dessous : int state; // EMPTY or READY
int time; // Estimated execution time
} process[2][MAX_PROCESS]; // process[0] = high priority process
P1 P2 P3
// process[1] = low priority process
int current_high_process = -1; int current_low_process = -1;

int current_priority = HIGH;
R1 R2 R3 R4
L’algorithme d’ordonnancement de ce système est basé sur le principe de Files de priorité. Les
processus sont classés sur 2 niveaux de priorités distincts : HIGH et LOW. La file HIGH gère les processus
P4 P5 de priorité haute. Cette file utilise l’algorithme SJF - (Shortest Job First) pour ordonnancement. La file
LOW gère les processus de priorité basse et utilise l’algorithme RR - (Round Robin ou Tourniqué). Les
processus de priorité HIGH sont, bien sûr, prioritaire par rapport aux processus de priorité LOW.
Dans ce cadre, répondez aux questions suivantes : A) Écrivez la fonction d’ordonnancement pour les processus de priorité haute. La fonction doit retour-
A) Le système est-il bloqué ? Justifiez votre réponse. ner l’indice du processus choisi ou -1 s’il y a aucun processus à ordonnancer.
B) Proposez des structures de données et écrivez (sommairement) un algorithme permettant de int ordonnancement HIGH ();
détecter automatiquement si le système est dans un état de blocage.
B) Écrivez la fonction d’ordonnancement pour les processus de priorité basse. La fonction doit retourner
l’indice du processus choisi ou -1 s’il y a aucun processus à ordonnancer.
2 Système de gestion de fichiers 6 points int ordonnancement LOW ();
Considérez un système de gestion de fichiers où le disque est géré à l’aide d’une FAT (File Allocation C) Écrivez la fonction générale d’ordonnancement basée sur la structure et le principe des Files de
Table). La FAT est un tableau d’entier qui possède autant de lignes que des blocs sur le disque. Un bloc priorité décrits ci-dessus. Cette fonction doit également sauvegarder le processus courant dans
i est libre si fat[i] = FAT FREE. Si le bloc i est le dernier bloc d’un fichier, on a fat[i] = FAT EOF. la bonne file de priorité, restaurer et retourner le processus choisi. Cette fonction utilise les deux
Toute autre valeur positive sur fat[i] indique le bloc suivant. fonctions précédentes. Elle reçoit en paramètre le processus courant et la priorité du processus. La
A) Écrivez la fonction d’allocation qui recherche un espace libre de n blocs consécutifs et renvoie fonction fait un exit s’il n’y a plus aucun processus à ordonnancer.
l’adresse du premier bloc (ou −1 en cas d’échec) en se basant sur le principe de meilleur ajustement PSW ordonnancement (PSW cpu, int prior);
(best-fit).
D) En se basant sur le principe de Files de priorités décrits ci-dessus et pour un quantum égal à
int alloc bloc best fit (int fat[], int taille fat, int n) 5 unités de temps. Donnez l’ordonnancement des processus et le temps moyen d’attente pour les
B) Écrivez la fonction de chaı̂nage de la FAT lorsque les blocs sont alloués par la fonction d’allocation processus suivants :
alloc bloc best fit. debut représente le premier bloc alloué et n le nombre de blocs alloués.
Process Date Time Priority
Rappel : le dernier bloc d’un fichier a la valeur FAT EOF.
P1 0 18 LOW
void chainages(int fat[], int debut, int n) P2 8 25 LOW
P3 12 10 HIGH
C) Écrivez la fonction d’allocation alloc bloc frac qui alloue n blocs non-consécutifs et retourne P4 18 2 HIGH
l’adresse du premier (ou −1 s’il n’existe pas assez de blocs libres). Rappel : n’oubliez pas d’en- P5 20 23 LOW
chaı̂ner correctement les blocs sur la fat. P6 21 3 HIGH
int alloc bloc frac (int fat[], int taille fat, int n)
2 Gestion de fichiers à trous (12 points)
Troisième année de la licence d’informatique Considérons un disque géré à l’aide d’une FAT (File Allocation Table) :
20 mai 2015, première session, struct {
durée 2 heures, calculatrices et documents autorisés. int suiv; /* adr. physique sur bloc suivant (-1 si dernier) */
int num; /* numéro du bloc logique */
} fat[ NB_BLOCS ]; /* la FAT chargée en mémoire */
Le numéro permet de coder des fichiers à trous (tous les numéros logiques ne correspondent pas à des blocs
1 Gestion des processus et synchronisation (8 points)
physiques). Si fat[P ].num = L, alors le bloc logique L est stocké dans le bloc physique P . Attention : le
Considérons un système dans lequel le processeur unique est géré sans réquisition. La machine possède un chaı̂nage de la FAT ne suit pas forcément l’ordre logique des blocs.
seul disque. Traitez les questions suivantes : Un descripteur est un enregistrement qui permet l’accès aux données d’un fichier.
A) Donnez le temps de réponse du processus ci-dessous et le taux d’utilisation du processeur sur la période typedef struct {
considérée. [2 points] int premier; /* adr. du premier bloc physique (-1 si vide) */
int nb_blocs; /* nombre de blocs physiques */
pour i variant de 1 à 3 faire } descripteur;
| calculer pendant i seconde(s)
| écrire sur un fichier pendant (2 × i) secondes Dans l’exemple ci-dessous vous pouvez retrouver un fichier qui commence à l’adresse 4 et qui est constitué
| si (i = 2) alors calculer pendant une seconde de trois blocs physiques. Les blocs libres sont signalés par le champ suiv à -2.
fin-pour
calculer pendant une seconde 0 1 2 3 4 5 6 7 8 9 10 11 12
suivant -2 -1 -2 11 8 -2 -1 -2 1 -2 -2 12 6
B) Même question que précédemment mais nous modifions le processus comme suit (indiquez sur un
numéro - 0 - 3 9 - 10 - 7 - - 4 5
schéma le déroulement de l’exécution pour le cas le plus favorable et le cas le moins favorable).
[2 points]
Questions :
pour i variant de 1 à 3 faire
A) Retrouvez dans l’exemple l’autre fichier, son nombre de blocs logiques et physiques. [2 points]
| | calculer pendant i seconde(s) B) Écrivez int nb trous(descripteur d) qui calcule le nombre de trous (des blocs logiques qui ne
| | écrire sur un fichier pendant (2 × i) secondes correspondent à aucun bloc physique). [2 points]
| | si (i = 2) alors calculer pendant une seconde
| fin du thread C) Écrivez int adr physique pour lecture(descripteur d, int num) qui renvoie l’adresse phy-
fin-pour sique d’un bloc logique afin de le lire. Cette fonction renvoie -1 si le bloc en question n’existe pas
attendre la fin des threads fils (tentative de lecture dans un trou). [2 points]
calculer pendant une seconde
D) Écrivez int allouer bloc() qui permet d’allouer un bloc sur disque. Cette fonction renvoie -1 si le
C) Visiblement l’ordre d’exécution des threads a un impact sur les performances. Comment modifier le disque est plein. [1 point]
code pour s’assurer que le bon thread s’exécute en premier ? [2 points] E) Écrivez int adr physique pour ecriture(descripteur *d, int num) qui renvoie l’adresse phy-
Conseil : utilisez un sémaphore. sique d’un bloc logique afin de le modifier. Si ce bloc n’existe pas, la fonction doit allouer un nouveau
D) En partant de la question B, si nous utilisons un algorithme de type tourniquet avec une tranche bloc et mettre à jour les chaı̂nages. Cette fonction renvoie -1 si le disque est plein. [2 points]
de temps très fine et que nous négligeons les temps de commutation d’un thread à une autre, quel F) Écrivez void creer un trou(descripteur *d, int num) qui supprime un bloc logique si il existe.
ordonnancement obtenons-nous (faites un schéma et donnez le temps de réponse) ? [2 points]
[3 points]

Questions : (un point par question)
Systèmes Troisième année de la licence d’informatique

Faculté des Sciences, site de Luminy
a) Sur une zone de 1024 ko gérée par l’algorithme du buddy system, quel est l’état des blocs libres et
occupés après les allocations de 65 ko, 130 ko, 220 ko, 50 ko et 91 ko dans cet ordre ?
d’exploitation Aix-Marseille Université
15 mai 2014, première session,
b) Si le programme P (s); P (t); . . . ; V (s); . . . ; P (t); . . . ; V (t); V (t); . . . ; P (s); . . . ; V (s); est
exécuté en plusieurs exemplaires, existe-t-il un risque d’interblocage (les compteurs sont initialisés
Responsable : Jean-Luc Massat durée 2 heures, calculatrices et documents autorisés. à deux) ?
c) soit les cinq processus suivants qui démarrent en même temps. Combien faut-il de processeurs pour
les exécuter sans contrainte ? Quel est le taux d’utilisation du processeur ?
1 Gestion des processus et synchronisation (7 points) – calculer 3s, E/S sur 4s, calculer 3s
– calculer 2s, E/S sur 3s, calculer 1s, E/S de 3s, calculer 1s
Considérons un système dans lequel le processeur unique est géré sans réquisition. – calculer 2s, E/S de 2s, calculer 2s, E/S de 2s, calculer 2s
– dormir sur 5s, calculer 2s, E/S de 3s
Questions : – E/S de 3s, calculer 3s, E/S de 4s
a) Donnez le temps de réponse du processus ci-dessous et le taux d’utilisation du processeur sur la d) Donnez la matrice max pour ces trois processus :
période considérée. [1 point]
– P1 : allouer R1 et R2 , ..., libérer R1 , ..., allouer R3 , R2 et R1 , ..., libérer toutes les resources
pour i ∈ {1, 2, 3} faire – P2 : allouer R3 et R1 , ..., libérer R3 , ..., allouer R2 et R1 , libérer toutes les ressources
| calculer pendant i seconde(s) – P2 : allouer R2 et R3 , ..., allouer R2 , ..., allouer R3 , ..., libérer toutes les ressources
| écrire sur un fichier pendant (2 × i) secondes
fin-pour e) Si le système recoit les requêtes ci-dessous, donnez l’ordre de traitement en se basant sur l’algorithme
calculer pendant 1 seconde SSTF (Shortest Seek Time First). La tête de lecture se trouve sur la piste 500.
b) Même question que précédemment mais nous modifions le processus comme suit (indiquez clairement 200, 150, 320, 700, 210, 100, 600, 705, 490, 150, 310, 610, 150
sur un schéma le déroulement de l’exécution pour le cas le plus favorable). [2 points]
f) Même question mais pour l’algorithme de balayage (la position initiale est 500 et le sens est des-
pour i ∈ {1, 2, 3} faire cendant).
| | calculer pendant i seconde(s) 3 Mémoire paginée (7 points)
| | écrire sur un fichier pendant (2 × i) secondes
| fin du thread Considérons une machine 32 bits (pointeurs et données) dotée d’un mécanisme de pagination à un seul
fin-pour niveau (une table des pages par processus et des pages de données). Chaque entrée de la table de pages
attendre la fin des threads fils mesure 32 bits (dont seulement 28 sont utilisables). Questions :
calculer pendant 1 seconde a) Pourquoi perdons-nous quatre bits dans chaque entrée de la table des pages ? [1 point]
c) Si nous considérons que les E/S de 2s et 4s se déroulent sur un disque A et que celle de 6s se b) Si les pages mesurent 210 octets, quelle est la taille de mémoire centrale susceptible d’être gérée par
déroule sur un autre disque B, quel est l’impact sur le temps de réponse et le taux d’utilisation du le système d’exploitation ? [1 point]
processeur ? Étudiez le cas le plus favorable et le cas le moins favorable. [2 points]
c) Si les pages mesurent 210 octets, donnez la composition d’une adresse paginée (parties et tailles en
d) Visiblement l’ordre d’exécution des threads a un impact sur les performances. Comment modifier le bits) [1 point]
code pour s’assurer que le calcul de 3 secondes s’exécute en premier ? [2 points] Considérons maintenant que nous avons une pagination à deux niveaux (une table des hyper-pages par
Conseil : utilisez un sémaphore. processus, des tables de pages et des pages de données). Chaque entrée de la table des hyper-pages mesure
32 bits. Questions :
2 Questions... réponses (6 points)
d) Partons du principe que nous avons des pages de 211 octets. Précisez la forme d’une adresse paginée
Les questions ci-dessous doivent être traitées dans le cadre d’un système d’exploitation moderne, multi- (parties et tailles en bits). [1 point]
threads, multi-programmé et doté d’une gestion mémoire performante (n’oubliez pas de justifier vos e) Toujours avec des pages de 211 octets, quelle est la taille maximale de la table des hyper-pages ?
réponses). Quel est le problème posé par cette taille ? [1 point]
f) Répondez à la question d) avec des pages de 212 octets. Expliquez pourquoi le problème évoqué à
la question e) est résolu. [2 points]
Questions : (un point par question)

a) Comment le système peut-il retirer de la mémoire à un processus et sur quels critères ?
b) A quels moments le système s’exécute-t-il ? et à qui est facturé cette exécution ?

15 mai 2013, première session, c) Comment le système assure-t-il la sécurité des données stockées sur un disque ?
Responsable : Jean-Luc Massat durée 2 heures, calculatrices et documents autorisés.
d) Si le programme P (s); P (t); . . . ; V (s); . . . ; P (t); . . . ; V (t); V (t) est exécuté en plusieurs exem-
plaires, existe-t-il un risque d’interblocage ?
e) Sur une zone de 1024 ko gérée par l’algorithme du buddy system, quel est l’état des blocs libres et
1 Gestion des processus et synchronisation (6 points) occupés après les allocations de 70 ko, 150 ko, 200 ko, 60 ko et 71 ko dans cet ordre ?
Questions : f) Les pseudo-partitions de répartition (RAID 0 ou stripping ) améliorent-elles la sécurité ou l’efficacité ?
a) Donnez le temps de réponse du processus ci-dessous et le taux d’utilisation du processeur (qui est g) Pourquoi peut-on, dans le système UNIX, agir sur plusieurs sémaphores (par P ou V) en une seule
unique) sur la période considérée. [1 point] opération atomique ?
pour i ∈ {1, 2, 3} faire
| calculer pendant 2 secondes 3 Gestion de fichiers (7 points)
| écrire sur un fichier pendant 4 secondes
Considérons un disque géré à l’aide d’une FAT (File Allocation Table). Ce tableau d’entiers possède autant
fin-pour
de cases que de blocs sur le disque. Un bloc i est libre si fat[i] = 0. Dans les autres cas, il est utilisé.
calculer pendant 1 seconde
Un descripteur est un enregistrement qui permet l’accès aux données d’un fichier. Pour un fichier
b) Même question que précédemment mais nous modifions le processus comme suit (indiquez clairement donné, si les blocs i et j se suivent, alors fat[i] = j. Si le bloc k est le dernier, alors fat[k] = −1.
sur un schéma le déroulement de l’exécution). [2 points]
typedef struct {
pour i ∈ {1, 2, 3} faire int taille; /* nombre de blocs */
| créer un thread pour faire int premier, dernier; /* adr. physiques des blocs (-1 si vide) */
| | calculer pendant 2 secondes } descripteur;
| | écrire sur un fichier pendant 4 secondes
| fin du thread
Questions :
fin-pour
attendre la fin des threads fils a) Écrivez la fonction qui insère un nouveau bloc (d’adresse adr_bloc) à la position nu_bloc (0
calculer pendant 1 seconde dénote le début du fichier). [2 points]
c) Dans la version précédente il existe un risque de ne pas construire exactement le même fichier. void inserer_bloc(descripteur *d, int fat[], int adr_bloc, int nu_bloc)
Pouvez-vous expliquer ce phénomène et proposer une correction. [2 points]
Conseil : utilisez un tableau de sémaphores défini par b) Écrivez la fonction qui vide un fichier de son contenu. [1 point]
soit sems : tableau[1..3] de sémaphores initialisés à zéro void vider(descripteur *d, int fat[])
d) Finalement, l’instruction d’attente de la fin des threads fils n’existe pas ! Comment obtenir (élégamment)
c) Écrivez une fonction qui crée un fichier de n blocs (utilisez les fonctions des questions a et b). Cette
le même comportement en utilisant un sémaphore ? [1 point]
fonction renvoie 1 en cas de réussite et 0 sinon. [2 points]
2 Questions... réponses (7 points) int creation(descripteur *d, int fat[], int taille_fat, int n)
Les questions ci-dessous doivent être traitées dans le cadre d’un système d’exploitation moderne, multi- d) Écrivez la fonction qui liste sur la sortie standard l’adresse physique du premier bloc de chaque
threads, multi-programmé et doté d’une gestion mémoire performante (n’oubliez pas de justifier vos fichier. A quoi peut servir cette fonction ? [2 points]
réponses).
void lister_1er_blocs(int fat[], int taille_fat)

2 Allocation de zones mémoire contiguës (7 points)

On considère une mémoire d’entiers composée de zones occupées et de zones libres. Chaque zone
débute par sa taille (positive pour les zones libres et négative pour les zones occupées). Nous avons donc
25 juin 2013, deuxième session,
un chainage qui permet de retrouver toutes les zones.
Dans l’exemple ci-dessous, il y a deux zones libres qui totalisent une taille de 8 et une zone occupée
Responsable : Jean-Luc Massat durée 2 heures, calculatrices et documents autorisés. de taille 4 :
3 0 -1 -4 10 11 -2 5 0 1 3 5
1 Gestion des processus (7 points) Questions :
a) Écrivez la fonction qui calcule la taille des zones libres de la mémoire. N’oubliez pas qu’il existe, en
On dispose d’une machine dotée d’un processeur et d’un seul disque. Considérons un processus unique
C, une fonction abs(v) qui permet de calculer la valeur absolue d’un entier v. [1 point]
qui réalise des calculs et des entrées/sorties d’une seconde chacune :
1s de CPU, deux E/S, 1s de CPU, trois E/S, 1s de CPU, quatre E/S, 1s de CPU. int taille_libre(int mem[], int taille_mem)
Questions : b) Écrivez la fonction qui recherche et renvoie la position de la zone (occupée ou libre) qui précède la
zone z. En cas d’erreur, cette fonction renvoie -1. [1,5 point]
a) Donnez le temps de réponse et le taux d’utilisation du processeur sur la période considérée. [1 point]
int predecesseur(int z, int mem[], int taille_mem)
b) Considérons que les E/S sont des écritures et que nous disposons d’un tampon de sortie capable
de stocker deux E/S. Dans ces conditions, donnez le déroulé des opérations et calculez le nouveau b) Écrivez la fonction qui fusionne la zone z et sa suivante si elles sont contiguës et libres. Cette
taux d’utilisation du processeur. [2 points] fonction renvoie 1 si une modification est faite et zéro sinon. [2 points]
c) Quelle est la plus petite taille du tampon permettant que les quatre secondes de CPU s’exécutent int fusionner_si_besoin(int z, int mem[], int taille_mem)
sans interruption (donc en quatre secondes) ? Pourquoi voulons-nous une telle configuration et quel
est le temps réponse obtenu ? [2 points] b) Écrivez la fonction qui libère la zone z en essayant de reconstituer la zone libre la plus grande.
Utilisez les deux fonctions précédentes (même si vous n’avez pas répondu aux questions). Cette
d) Si chacun des trois cycles d’E/S est réalisé sur un disque différent (chacun ayant un tampon de deux
fonction 0 en cas de problème et 1 si la libération est faite. [2,5 points]
secondes), quel est l’impact sur le temps de réponse ? Justifiez votre réponse et indiquez clairement
à quelle(s) condition(s) vous obtenez ce résultat [2 points]
int liberer(int z, int mem[], int taille_mem)
3 Gestion d’une mémoire virtuelle (6 points)
Exercice déjà posé.

void inserer_bloc(descripteur *d, int fat[], int adr_bloc, int nu_bloc)
Systèmes Faculté des Sciences
c) Écrivez la fonction qui vide un fichier de son contenu. [1 point]
Aix-Marseille Université
d’exploitation 9 mai 2012, première session,
void vider(descripteur *d, int fat[])
durée 2 heures, d) Écrivez une fonction qui crée un fichier de n blocs (utilisez les fonctions des questions a et c). Cette
Responsable : Jean-Luc Massat calculatrices et documents autorisés. fonction renvoie 1 en cas de réussite et 0 sinon. [2 points]
int creation(descripteur *d, int fat[], int taille_fat, int n)
1 Gestion des processus (6 points, 35 minutes) e) Écrivez la fonction qui liste sur la sortie standard l’adresse physique du premier bloc de chaque
fichier. A quoi peut servir cette fonction ? [2 points]
qui réalise des calculs et des entrées/sorties d’une seconde chacune : void lister_1er_blocs(int fat[], int taille_fat)
2s de CPU, trois E/S, 2s de CPU, quatre E/S, 2s de CPU, une E/S, 1s de CPU.
3 Mémoire paginée (6 points, 35 minutes)
Questions :
de stocker deux E/S. Dans ces conditions, donnez le déroulé des opérations et calculez le nouveau
taux d’utilisation du processeur. [1,5 point]
c) Quelle est la plus petite taille du tampon permettant d’obtenir le temps de réponse le plus court ?
(justifiez votre réponse) [1,5 point]
d) Si chaque E/S est réalisée sur un disque différent, quel est l’impact sur le temps de réponse ? (justifiez
votre réponse et indiquez clairement à quelle(s) condition(s) vous obtenez ce résultat) [2 points]
2 Gestion de fichiers (8 points, 50 minutes)
donné, si les blocs i et j se suivent, alors fat[i] = j. Si le bloc k est le dernier, alors fat[k] = −1.
typedef struct {
int taille; /* nombre de blocs */
int premier; /* adresse du premier bloc */
int dernier; /* adresse du dernier bloc */
} descripteur;
Questions :
a) Écrivez une fonction qui ajoute un bloc à un fichier en mettant à jour les chaı̂nages et le descripteur.
[1 point]
void ajouter_bloc(descripteur *d, int fat[], int adr_bloc)
b) Écrivez la fonction qui insère un nouveau bloc (d’adresse adr_bloc) à la position nu_bloc (0
dénote le début du fichier). [2 points]
Questions :

Faculté des Sciences - Aix-Marseille Université
a) Écrivez une fonction qui ajoute un bloc à un fichier en mettant à jour les chaı̂nages et le descripteur.
[1,5 point]
d’exploitation 18 juin 2012, deuxième session,
durée 2 heures, void ajouter_bloc(descripteur *d, int fat[], int adr_bloc)
Responsable : Jean-Luc Massat calculatrices et documents autorisés.
b) Écrivez la fonction qui supprime le premier bloc d’un fichier et met à jour le descripteur et la FAT.
[2 points]
void supprimer_premier_bloc(descripteur *d)

1 Gestion des processus (6 points, 35 minutes)
c) Écrivez la fonction qui vide un fichier de son contenu et met à jour le descripteur. [1,5 point]
qui réalise des calculs et des entrées/sorties d’une seconde chacune : void vider(descripteur *d, int fat[])
1s de CPU, deux E/S, 1s de CPU, trois E/S, 1s de CPU, quatre E/S, 1s de CPU.
d) Écrivez une fonction qui crée un fichier de n blocs contigus (placés les uns après les autres). Cette
fonction renvoie le descripteur de ce nouveau fichier. La taille est forcée à -1 si l’opération a échoué.
Questions : [2 points]
descripteur creation_contigue(int fat[], int taille_fat, int n)
de stocker deux E/S. Dans ces conditions, donnez le déroulé des opérations et calculez le nouveau 3 Mémoire paginée (7 points, 40 minutes)
taux d’utilisation du processeur. [1,5 point]
c) Quelle est la plus petite taille du tampon permettant que les quatre secondes de CPU s’exécutent
sans interruption (donc en quatre secondes) ? Pourquoi voulons-nous une telle configuration et quel
est le temps réponse obtenu ? [1,5 point]
d) Si chacun des trois cycles d’E/S est réalisé sur un disque différent (chacun ayant un tampon de deux
secondes), quel est l’impact sur le temps de réponse ? Justifiez votre réponse et indiquez clairement
à quelle(s) condition(s) vous obtenez ce résultat [2 points]
2 Gestion de fichiers (7 points, 45 minutes)
donné, si les blocs i et j se suivent, alors fat[i] = j. Si le bloc k est le dernier, alors fat[k] = −1.
typedef struct {
int taille; /* nombre de blocs */
int premier; /* adresse du premier bloc (-1 si vide) */
int dernier; /* adresse du dernier bloc (-1 si vide) */
} descripteur;

3 Les philosophes et les banquiers (5 points, 40 minutes)
Système U.F.R. Sciences de Luminy
Un beau jour de mai, 5 philosophes décident d’aller manger ensemble des spaghettis. Le restaurateur
dresse une table ronde, mais place seulement 5 fourchettes (une entre chaque assiette). Pour manger, un
Université de la Méditerranée
philosophe a besoin de deux fourchettes : celle placée à sa droite et celle placée à sa gauche.
durée 2 heures,
Responsable : Jean-Luc Massat Questions :
calculatrices et documents autorisés.
a) Montrez qu’il existe un risque d’interblocage et proposez une solution simple à ce problème. [1 point]
b) Pour éviter les interblocages, les philosophes décident d’appliquer l’algorithme des banquiers. Donnez
1 Parallélisme et allocation de la CPU (10 points, 1 heure) la matrice Max et le vecteur Dispo. [1 point]
Considérons le programme suivant c) Pour ce problème bien particulier donnez l’algorithme simplifié permettant de déterminer si oui
ou non, le système est dans un état sain. [1,5 point]
(A1 , {B1 , A2 }, A3 , {C1 , (A4 , {C2 , B2 })}, {A5 , A6 , A7 })
d) Sans vous préoccuper des problèmes de parallélisme et de synchronisation, donnez l’algorithme
où les parenthèses dénotent une exécution séquentielle et les accolades une exécution parallèle. Une appliqué par le ième philosophe avant de manger. [1,5 point]
instruction {X1 , . . . , Xn } se termine quand toutes les instructions Xi sont terminées. Les instructions Ai
durent une seconde, les Bi deux secondes et les Ci trois secondes.
Questions :
a) Donnez le temps d’exécution de ce programme et le taux d’utilisation du processeur sur une machine
mono-processeur. [1 point]
b) Même question pour une machine bi-processeurs. Indiquez clairement la répartition de l’exécution
sur les processeurs. [1,5 point]
c) Même question pour une machine dotée de trois processeurs. [2 points]
d) Si les instructions Ci sont composées, pour moitié de calcul processeur et pour l’autre moitié
d’opérations d’E/S, quel est le taux d’utilisation du processeur sur une machine mono-processeur ?
[1,5 point]
e) On vous donne les fonctions suivantes :
int thread_create(); /* création d’un thread */

void thread_exit(); /* suicide d’un thread */
sem_t sema_create(int compteur); /* création d’un sémaphore */
void sema_wait(sem_t s); /* prise d’un sémaphore (P) */
void sema_signal(sem_t s); /* libération d’un sémaphore (V) */
Le thread fils est créé par recopie du thread père. Les deux threads reviennent donc de l’appel à
thread create. Cette fonction renvoie 0 chez le fils et 1 chez le père.
Avec l’aide de ces fonctions, comment écrire un programme dans un langage proche du C qui soit
équivalent à {{U, V }, (W, T ), X} ? [2 points]
e) Même question pour le programme {(A, B), (C, B)} avec la contrainte supplémentaire : le code B
ne doit être exécuté qu’une seule fois. [2 points]
2 Mémoire paginée (5 points, 20 minutes)

Questions :
Système U.F.R. Sciences de Luminy
a) Entre First-Fit, Best-Fit et Buddy-System quel est l’algorithme le plus rapide ?
Université de la Méditerranée b) Pourquoi dit-on que les systèmes modernes sont dirigés par les interruptions ?
c) Dans un système de mémoire virtuelle paginée, pourquoi le système garde-t-il quelques pages phy-
durée 2 heures,
Responsable : Jean-Luc Massat calculatrices et documents autorisés. siques libres en réserve ?
d) Dans certains systèmes paginés, la PMMU n’a pas accès à la table des pages. Dans ces conditions,
comment fonctionne la transformation des adresses ?
1 Parallélisme et allocation de la CPU (9 points) e) Le principe du tassage est-il utilisable pour l’algorithme par subdivision (buddy system) ?
Considérons un programme composé de quatre parties : A, B, C et D. Les parties A, B et C sont f) Dans le problème des philosophes (simulés par des processus) et des spaghettis, donnez la matrice
indépendantes. Pour s’exécuter, la partie D a besoin des résultats des trois autres parties. des besoins (matrice max de l’algorithme des banquiers). Pour ce problème, à quelle condition un
état est-il sain ?
Questions : N’oubliez pas de justifier vos réponses.
a) Si A, B, C et D durent respectivement 1 seconde, 3 secondes, 3 secondes et 1 seconde, donnez
le meilleur temps d’exécution et le meilleur taux d’utilisation de la ressource processeur sur une
machine dotée d’un processeur, puis de deux, puis de trois. Indiquez clairement la répartition de
l’exécution sur les processeurs. [3 points]
b) On vous donne les fonctions suivantes :

void thread_exit(); /* suicide d’un thread */
Le thread fils est créé par recopie du thread père. Les deux threads reviennent donc de l’appel à
thread create. Cette fonction renvoie 0 chez le fils et 1 chez le père.
Avec l’aide de ces fonctions, et sans connaı̂tre le temps d’exécution des quatre parties, comment
écrire un programme dans un langage proche du C qui exploite le parallélisme de cet exemple ?
Attention : vous ne disposez que de ces deux fonctions, mais les threads partagent les variables
globales [2 points].
c) On vous donne les fonctions suivantes :

Comment utiliser ces fonctions pour améliorer le code de la question précédente ? Exliquer l’amélioration
attendue. [2 points]
c) Vous voulez maintenant brider votre programme pour ne pas utiliser plus de deux processeurs
simultanément. Comment faire en utilisant les sémaphores ? [2 points]
2 Mémoire paginée (5 points)
Les questions ci-dessous doivent être traitées dans le cadre d’un système d’exploitation moderne, multi-
threads, multi-programmé et doté d’une gestion mémoire performante.
2 Gestion des processus (5 points)
Systèmes U.F.R. Sciences de Luminy
On dispose d’une machine dotée d’un processeur (géré sans réquisition) et d’un seul disque. Considérons
deux processus A (arrivé en premier) et B (arrivé une seconde après) définis par :
d’exploitation 18 mai 2010, première session, A : 2s de CPU, 3s d’E/S, 2s de CPU, 4s d’E/S et 1s de CPU ;
durée 2 heures, B : 2s de CPU, 3s d’E/S, 1s de CPU, 3s d’E/S et 2s de CPU ;
Questions :
a) Donnez le taux d’utilisation du processeur pour chaque processus et de manière globale sur la période
considérée. [1,5 point]
1 Gestion de fichiers (8 points)
Considérons un disque géré à l’aide d’une FAT (File Allocation Table). Ce tableau d’entiers possède autant de stocker une seconde d’écriture. Dans ces conditions, donnez le schéma de l’ordonnancement des
de cases que de blocs sur le disque. Un bloc i est libre si fat[i] = 0. Dans les autres cas, il est utilisé. processus et calculez les nouveaux taux d’utilisation du processeur. [1,5 point]
Questions : c) A quelles conditions l’ajout d’un nouveau disque permet-il d’améliorer les performances ? [2 points]
a) Écrivez une fonction qui recherche un espace libre de n blocs consécutifs et renvoie son adresse (ou
-1 en cas d’échec) en se basant sur la stratégie du premier trouvé (first-fit) [2 points].
int alloc_contigue(int fat[], int taille_fat, int n)
b) Même question pour la stratégie du meilleur ajustement (best-fit) [2 points].
Questions :
c) Un descripteur est un enregistrement qui permet l’accès aux données d’un fichier. Pour un fichier
donné, si les blocs i et j se suivent, alors fat[i] = j. Si le bloc k est le dernier, alors fat[k] = −1. a) Pourquoi faut-il ajuster la taille de la tranche de temps ? (0,5 point) et comment le faire ? (0,5 point)
typedef struct { b) Pourquoi et sur quels critères le système retire-t-il de la mémoire à un processus ? (1 point)
int taille_en_blocs; c) Pourquoi la taille des pages est-elle toujours une puissance de deux ? (0,5 point)
int adr_premier_bloc;
int adr_dernier_bloc; e) A quel moment un processus s’exécute-t-il en mode système ? (1 point)
} descripteur;
g) L’algorithme par subdivision (buddy system) provoque-t-il de la fragmentation interne ? externe ?
Écrivez la fonction verifier qui vérifie le codage d’un fichier (descripteur, taille et chaı̂nage) (0,5 point)
et renvoie 1 en cas de succès et 0 sinon. [2 points]
h) Si nous disposons de disques capables de lire ou d’écrire des blocs de 512 octets, pourquoi le système
va-t-il utiliser des blocs de 1ko ou plus ? (1 point)
int verifier(descripteur d, int fat[], int taille_fat)
i) Pourquoi peut-on, dans le système UNIX, agir sur plusieurs sémaphores (par P ou V) en une seule
d) Écrivez la fonction tronquer qui réduit la taille du fichier à n blocs (ou moins si la taille d’origine opération atomique ? (1 point)
est inférieure à n blocs). [2 points]
j) A quoi peut servir une fonction système non bloquante permettant de récupérer le compteur d’un
void tronquer(descripteur *d, int fat[], int n) sémaphore ? (1 point)
N’oubliez pas de justifier vos réponses.

Prenons cinq processus notés de A à E ayant les caractéristiques suivantes :
processus
A
date d’arrivé
0
durée
3
durée 2 heures, B 1 5
Responsable : Jean-Luc Massat calculatrices et documents autorisés. C 7 1
D 6 3
E 4 2
1 Gestion de fichiers (8 points) Questions :

Considérons un disque géré à l’aide d’une FAT (File Allocation Table). Ce tableau d’entiers possède autant a) Donnez le temps de réponse cumulé si le système applique la stratégie FIFO pour ordonnancer les
de cases que de blocs sur le disque. Un bloc i est libre si fat[i] = 0. Dans les autres cas, il est utilisé. processus. (1 point)
Un descripteur est un enregistrement qui permet l’accès aux données d’un fichier. Pour un fichier b) Même question pour les stratégies SJF, SRT et Tourniquet (avec une tranche de temps de une
donné, si les blocs i et j se suivent, alors fat[i] = j. Si le bloc k est le dernier, alors fat[k] = −1. unité). (3 points)
typedef struct { c) Pourquoi ne parle-t-on pas d’entrées/sorties dans la description de ces processus ? (1 point)
int taille_en_blocs;
int adr_dernier_bloc;
} descripteur; Les questions ci-dessous doivent être traitées dans le cadre d’un système d’exploitation moderne, multi-
Questions :
a) Écrivez une fonction qui va créer un fichier de n blocs (les chainages et le descripteur doivent être Questions :
préparés). Cette fonction renvoie 1 en cas de réussite et 0 sinon. (2 points) a) Entre First-Fit, Best-Fit et Buddy-System quel est l’algorithme le plus rapide ?
int creation(descripteur *d, int fat[], int taille_fat, int n) b) Pourquoi dit-on que les systèmes modernes sont dirigés par les interruptions ?
b) Écrivez une fonction qui ajoute un bloc à un fichier en mettant à jour les chaı̂nages et le descripteur. c) Dans un système de mémoire virtuelle paginée, pourquoi le système garde-t-il quelques pages phy-
(1 point) siques libres en réserve ?
void ajouter_bloc(descripteur *d, int fat[], int adr_bloc) d) Dans certains systèmes paginés, la PMMU n’a pas accès à la table des pages. Dans ces conditions,
comment fonctionne la transformation des adresses ?
c) Écrivez la fonction qui insère un nouveau bloc (d’adresse adr_bloc) à la position nu_bloc (0
e) Si un processus exécute la séquence suivante : P(s) ;P(s) ;V(s) ;P(s) ;P(s) ;V(s) ;P(s) à quelle condi-
dénote le début du fichier). (2 points)
tion peut-on garantir l’absence de blocage ?
void inserer_bloc(descripteur *d, int fat[], int adr_bloc, int nu_bloc) f) Le principe du tassage est-il utilisable pour l’algorithme par subdivision (buddy system) ?
d) Écrivez la fonction qui vide un fichier de son contenu. (1 point) g) Dans le problème des philosophes (simulés par des processus) et des spaghettis, donnez la matrice
des besoins (matrice max de l’algorithme des banquiers). Pour ce problème, à quelle condition un
void vider(descripteur *d, int fat[]) état est-il sain ?
e) Écrivez la fonction qui liste sur la sortie standard l’adresse physique du premier bloc de chaque N’oubliez pas de justifier vos réponses.
fichier. A quoi peut servir cette fonction ? (2 points)
void lister_1er_blocs(int fat[], int taille_fat)

j) A quoi peut servir une fonction système non bloquante permettant de récupérer le compteur d’un
sémaphore ?
Systèmes U.F.R. Sciences de Luminy N’oubliez pas de justifier vos réponses.
durée 2 heures,
1 Synchronisation de processus (7 points)
2 Allocation contigüe de la mémoire (6 points)
On considère la suite de demandes d’allocation (+) et de libération (−) suivantes, dans un espace
mémoire de 1000 blocs.
+300, +200, +240, −200, +100, −300, +250, +400, −240, +150,
+95, −100, −95, +200, −150, −250, +100, −400, −100, −200
a) Si la mémoire est initialement vide, comment le S.E. réalise les allocations en partant du principe
qu’il applique la stratégie de la première zone libre. On complète cette stratégie par l’application
d’un algorithme de tassage si aucune des zones libres ne convient.
b) Même question si le système applique la stratégie du meilleur ajustement. Comparez ces deux
stratégies en utilisant le nombre de tassages effectués et la quantité de données déplacées.
Questions :
a) Faut-il plusieurs processus pour exploiter pleinement une machine bi-processeurs ?
b) Comment le système peut-il retirer de la mémoire à un processus ?
c) A quels moments le système s’exécute-t-il ?
d) Comment le système assure-t-il la sécurité des données stockées sur un disque ?
e) Quel est le mécanisme permettant à un processus de réaliser des écritures asynchrones sur disque ?
f) Quelle est la définition du tampon utilisateur et son rôle ?
g) L’algorithme par subdivision (buddy system) provoque-t-il de la fragmentation interne ? externe ?
h) Si nous disposons de disques capables de lire ou d’écrire des blocs de 512 octets, pourquoi le système
va-t-il utiliser des blocs de 1ko ou plus ?
i) Pourquoi peut-on, dans le système UNIX, agir sur plusieurs sémaphores (par P ou V) en une seule
opération atomique ?
durée 2 heures,
1 Gestion de fichiers (7 points)
threads, multi-programmé et doté d’une gestion mémoire performante. N’oubliez pas de justifier vos
réponses.
Questions :
a) Soit un processus qui effectue 5 fois, 1 seconde de calcul et 2 secondes d’écriture sur un fichier,
donnez le taux d’utilisation du processeur sur la période considérée.
b) Si nous ajoutons à la question a) un tampon de sortie pouvant contenir 1 seconde d’entrée/sortie,

quel est le gain espéré ?
c) A quels moments dit-on que le système s’exécute pour le compte d’un processus ?
d) Les pseudo-partitions de répartition (RAID 0 ou stripping ) améliorent-elles la sécurité ou l’efficacité ?
e) Pourquoi, pour un sémaphore s donné, les procédures P(s) et V(s) s’exécutent-elles en exclusion
mutuelle ?
f) Dans le problème des philosophes et des spaghettis, comment appliquer une règle simple (mais
efficace) pour éviter les interblocages ?
g) Quels sont les critères utilisés par le système d’exploitation pour réduire ou augmenter la taille des
tranches de temps alloués à un processus ?
h) Quels sont les critères utilisés par le système d’exploitation pour réduire ou augmenter la mémoire
physique alloué à un processus.

2 Parallélisme et utilisation des threads (6 points)
Vous venez d’acquérir une nouvelle machine dotée de plusieurs processeurs. Pour l’exploiter au mieux,
vous décidez de modifier vos anciens programmes afin de les adapter à cette architecture. Pour ce faire,
le système d’exploitation vous offre deux fonctions pour gérer des threads :
durée 3 heures, int thread_create(); /* création d’un thread */
Responsable : Jean-Luc Massat calculatrices et documents autorisés. void thread_exit(); /* suicide d’un thread */
La fonction thread_create crée un nouveau thread fils par recopie à l’identique du thread
courant (le père). Le thread fils démarre son exécution comme si il revenait de l’appel à la fonction
1 Gestion de fichiers (10 points) thread create. La fonction renvoie 0 chez le fils, et 1 chez le père.
Considérons un disque géré à l’aide d’une FAT (File Allocation Table). Ce tableau d’entiers possède Questions :
autant de lignes que de blocs sur le disque. Un bloc i est libre si fat[i] = 0. Dans les autres cas, il est
utilisé. a) Le programme A est composé de trois parties (notées A1 , A2 et A3 ). A3 a besoin des résultats de
A1 et A2 et l’exécution de A1 est toujours plus longue que celle de A2 . Dans ce cadre, donnez une
Questions : version qui utilise le parallélisme de A et expliquez le gain attendu.
a) Écrivez une fonction qui recherche un espace libre de n blocs consécutifs et renvoie son adresse (ou b) Même question, mais on ne connaı̂t pas le plus long des deux codes A1 et A2 . J’insiste : vous ne
-1 en cas d’échec) en se basant sur la stratégie du premier trouvé (first-fit) [2 points]. disposez de rien d’autre que les deux fonctions présentées ci-dessus. Par contre, je vous rappelle que
les threads partagent les variables globales. Quelle critique pouvez-vous faire de la solution que
int alloc_contigue(int fat[], int taille_fat, int n) vous proposez ?
b) Même question pour la stratégie du meilleur ajustement (best-fit) [3 points]. c) Le programme B est composé de trois parties. Le code B3 a besoin des résultats de B1 ou B2 .
Proposez une version parallèle sans perte de CPU. Pour vous aider, on vous donne une fonction
non interruptible qui incrémente son argument et renvoie son ancienne valeur :
Descripteur. Un descripteur est un bloc qui permet l’accès aux données d’un fichier. Pour un fichier
donné, si les blocs i et j se suivent, alors fat[i] = j. Si le bloc k est le dernier, alors fat[k] = −1. int test_and_set(int* verrou); /* renvoyer puis incrémenter */
struct descripteur {
int taille_en_blocs; 3 Mémoire virtuelle paginée (4 points)
int adr_dernier_bloc; n˚ p. phys.
}; 0 600
.. ..
Soit un système basé sur une mémoire paginée. La . .
Questions : taille des pages est fixée à 212 octets et la machine 70 900
RL = 120 71 950
manipule des adresses et des entiers de 32 bits. La
c) Écrivez la fonction int verifier(struct descripteur d) qui vérifie le codage d’un fichier mémoire du processus courant est décrite par les
RB = 300 .. ..
. .
(descripteur, taille et chaı̂nage) et renvoie 1 en cas de succès et 0 sinon. [2 points] paramètres ci-contre. 119 210
d) Sachant que les descripteurs sont marqués -2 dans la FAT, écrivez une fonction qui affiche les blocs 120 350
.. ..
de données qui n’appartiennent à aucun fichier (erreur de codage). [3 points] . .
void verifier_disque(int fat[], int taille_fat); Questions :

Vous avez à votre disposition une fonction de lecture des descripteurs : a) Si la table des pages mesure au maximum une page, quelle est la taille maximun de la mémoire
alloué à un processus. Pourquoi cette limitation ? [1 point]
struct descripteur lire_descripteur(int adr);
b) Quelle est la taille de la mémoire allouée au processus courant. [0,5 point]
Conseil : utilisez un tableau supplémentaire qui donne l’état de chaque bloc du disque.
c) Quelle est la taille maximum de la mémoire physique que le système puisse gérer. [1 point]
d) Donnez les adresses physiques des adresses paginées 3977, 288820 et 494640. [1,5 point]
N’oubliez pas de justifier vos réponses.

Soit un processus dont le travail consiste à calculer (pendant 1 seconde) et à sauver le résultat dans
un fichier (pendant 4 secondes) le tout dix fois.
Questions :
durée 3 heures,
Responsable : Jean-Luc Massat calculatrices et documents autorisés. a) Quel est le temps de réponse de ce processus et le taux d’utilisation de la CPU sur la période
considérée ? [1 point]
b) Admettons que le système alloue un tampon de sortie pouvant contenir 2 secondes d’entrée/sortie.
1 Gestion d’une mémoire virtuelle (9 points) Dans ces conditions répondez à la question a) et donnez la trace de l’exécution. [2 points]
Certaines machines (comme le processeur IBM RS-6000) n’utilisent pas une table des pages virtuelles c) Du point de vue du système d’exploitation, est-il intéressant d’allouer un tampon de sortie dont la
pour chaque processus. Sur ce type de système, l’état de la mémoire est décrit par une seule table qui taille est supérieur à 4 secondes (justifiez votre réponse) ? [2 points]
dispose d’une entrée pour chaque page physique. Cette table a la forme suivante
3 Mémoire paginée à deux niveaux (6 points)
struct {
int idp; /* nu de processus */ Considérons un système basé sur une mémoire paginée à deux niveaux. La taille des pages est fixée à
int npv; /* nu de page virtuelle */ 210 octets et la machine manipule des adresses et des entiers de 32 bits. La mémoire du processus courant
int protection; /* codage des permissions */ est décrite par les paramètres RL=31076, RB=600 et les pages ci-dessous.
int modif; /* bit de modification */
Adresse 150 : Adresse 400 : Adresse 600 : Adresse 900 :
} dpp[NB_PAGES_PHYSIQUES];
n˚ p. phys. n˚ p. phys. n˚ p. phys. n˚ p. phys.
Les pages physiques libres sont signalées par le champ idp égal à zéro. Les adresses virtuelles et physiques 0 950 .. .. 0 180 .. ..
.. .. . . .. .. . .
ont maintenant la forme suivante : . .
.. ..
50 800 . . ... ...
struct ADRV { int idp; int npv; int deplacement; }; . . 51 450 10 150 .. ..
100 500 52 350 11 170 . .
struct ADRP { int npp; int deplacement; };
101 190 .. .. 12 900 200 200
. . .. .. 201 700
Questions : 102 100 .. .. . .
.. .. . . 202 300
a) A-t-on, du point de vue d’un processus, les mêmes capacités d’adressage mémoire que dans un . . .. .. 120 400 .. ..
255 550 . . 121 401 . .
système plus classique ?
b) Ecrivez la fonction de transformation des adresses virtuelles en adresses physiques. Questions :

struct ADRP transformer(struct ADRV a) { ... } a) Donnez la composition d’une adresse paginée dans ce système (nature et taille en nombre de bits
de chaque composante) ? [1 point]
Dans cet algorithme, le défaut de page va correspondre à l’appel de la fonction :
b) Quelle est la taille maximum de la mémoire alloué à un processus ? Comment procéder pour aug-
struct ADRP defaut_de_page(struct ADRV a);
menter cette limite ? [2 points]
c) Quel est l’impact de la taille des pages sur la performance du processus de transformation des
c) Quelle est la taille de la mémoire allouée au processus courant. [1 point]
adresses. Justifiez votre réponse en présentant quelques exemples chiffrés. Quels sont les moyens,
matériels et/ou logiciels, qui permettent de réduire le coût de cette transformation. d) Donnez les adresses physiques des adresses paginées 2621440, 2726554, 3351702 et 31511528.
[2 points]
d) Écrivez la fonction defaut_de_page. Pour simplifier, vous pouvez considérer qu’il existe une zone
de pagination pour chaque processus. Vous disposez alors des deux fonctions : N’oubliez pas de justifier vos réponses.
charger_page( int idp, int npv, int npp);
sauver_page ( int idp, int npp, int npv);
e) Comment le partage de pages peut-il s’organiser dans ce système ?

2 Traitement des interblocages (5 points)
Considérons un système d’allocation de ressources portant sur 5 processus et 4 classes de ressources.
L’état du système est donné par les informations suivantes :
d’exploitation 16 mai 2006, Allocation Max
durée 3 heures, R1 R2 R3 R4 R1 R2 R3 R4
Responsable : Jean-Luc Massat calculatrices et documents autorisés. P0 0 0 1 2 P0 0 0 1 2 Dispo
P1 1 0 0 0 P1 1 7 5 0 R1 R2 R3 R4
P2 1 3 5 4 P2 2 3 5 6 1 5 2 0
P3 0 6 3 2 P3 0 6 5 2
1 Synchronisation de processus (9 points) P4 0 0 1 4 P4 0 6 5 6
Dans ce cadre, répondez aux questions suivantes en utilisant l’algorithme des banquiers :
On se propose de tirer parti d’une machine multi-processeurs pour accélerer l’exécution d’un processus.
Ce processus est composé de six portions de code notées A, B, C, D, E et F . L’analyse de ces portions a) Combien faut-il ajouter de ressources (pour chaque Ri ) de manière à ce que les processus puissent
nous révèle les contraintes suivantes : s’exécuter sans contrainte.
1. l’exécution de B doit se placer après C, G et A, b) Le système est-il dans un état sain ? justifiez votre réponse.
2. l’exécution de D doit se placer après A et G,
3. l’exécution de F doit se placer après B ou bien D, c) Si le processus P1 dépose la requête (0, 4, 2, 0), cette requête est-elle acceptée immédiatement ?
4. l’exécution de C doit se placer après A et E, (justifiez votre réponse).
Nous n’avons aucune information sur la durée d’exécution de ces portions de code. d) A partir de la situation initiale, si le processus P4 dépose la requête (1, 4, 2, 0), quel est le résultat ?
Questions : 3 Gestion des processus (6 points)
a) Donnez un ordre d’exécution séquentiel qui respecte les contraintes énoncées. Soit le processus ci-dessous exécuté sur une machine mono-processeur
b) Imaginons que dans un processus on puisse utiliser les notations suivantes : faire 3 fois
| calculer pendant 1 seconde
cobegin P1 ; . . . Pn ; coend | écrire sur le fichier F1 pendant 2 secondes
begin S1 ; . . . Sm ; end fin-faire
faire 2 fois
pour indiquer au système que les instructions Pi peuvent se dérouler en parallèle tandis que les | calculer pendant 1 seconde
instructions Si doivent être exécutées de manière séquentielle. Une instruction cobegin/coend se | écrire sur le fichier F1 pendant 3 secondes
termine quand toutes les instructions qui la composent sont terminées. fin-faire
Utilisez ces notations pour rendre le plus parallèle possible l’exécution des six portions de code. Les deux séries d’écritures sont indépendantes.
Tout le parallélisme potentiel est-il utilisé ? (justifiez votre réponse).
c) En utilisant des sémaphores, les cobegin/coend et les begin/end, pouvez vous reformuler le pro- Questions :
cessus pour utiliser tout le parallélisme potentiel. N’oubliez pas de préciser, pour chaque sémaphore, a) Quel est le temps de réponse de ce processus et le taux d’utilisation de la CPU sur la période
la valeur initiale du compteur. considérée ?
d) Même question que précédemment si la contrainte 2 est modifiée comme suit : b) Si le processus est maintenant structuré sous la forme de deux threads, chacun s’occupant d’une
2. l’exécution de D doit se placer après A et G ou bien après E. boucle, quel est le nouveau temps de réponse et le taux d’utilisation de la CPU ? Dessinez une trace
de l’exécution des threads.
e) Si chaque portion calcule pendant une seconde, quel est le nombre de processeurs dont vous avez
besoin ? c) Pour améliorer son code, le programmeur décide de garder les threads, mais de produire deux fichiers
différents (F1 et F2 par exemple). A quelles conditions peut-on obtenir une amélioration ? Evaluez
cette amélioration en calculant le temps de réponse et le taux d’utilisation de la CPU.
e) Admettons que le système alloue deux tampons de sortie pouvant contenir chacun 2 secondes
d’entrée/sortie (un pour chaque thread). Dans ces conditions, répondez à la question a) et donnez
la trace de l’exécution.
attente[i] := vrai;
répéter
Systèmes d’exploitation Test-And-Set(copie, verrou)
jusqu’à (copie = faux) ou (attente[i] = faux)
Troisième année de la licence d’informatique — U.F.R. des Sciences de Luminy
24 mai 2005, < section critique >
durée 3 heures,
Tous les documents sont autorisés. j := (i + 1) mod n;
tant-que (j <> i) et (attente[j] = faux) faire j := (j + 1) mod n;
attente[i] := faux
si (i = j) alors verrou := faux
sinon attente[j] := faux
Questions :
Considérons une machine qui comporte une mémoire composée de trois pages physiques initialement
vides. Lors de son exécution, un processus unique accède dans l’ordre aux pages virtuelles suivantes : a) Combien de processus exécutent leur section critique simultanément (justifiez votre réponse) ?
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1. b) Quel est le comportement particulier de ces processus et en quoi cette solution est-elle meilleur que
la programmation classique du prologue et de l’épilogue ?
Questions :
c) Malgré ses qualités, il reste un défaut à cette solution. Lequel ?
a) Pour chacun des algorithmes FIFO, LRU et OPT, donnez le contenu des pages physiques (c-à-d
un numéro de page virtuelle) après chaque accès. Précisez également le nombre total de défauts de
page provoqués par ces accès. (3 points) 3 Codage des fichiers (6 points)
b) Si le nombre de pages physiques passe à quatre, quel est le nombre de défauts de page pour Dans un système de fichiers, la position physique d’un fichier sur disque est définie par un descripteur :
l’algorithme LRU (2 points) ?
struct descripteur {
c) Quel est le meilleur compromis pour la taille de la mémoire physique (1 point) ? int nbblocs; /* taille du fichier en blocs */
int data[10]; /* adresses des 10 premiers blocs de données */
d) Donnez la nouvelle trace de l’exécution du processus en prenant comme hypothèse que la taille des int premierIndex; /* adresse du premier bloc d’index */
pages virtuelles a doublé (2 points). int dernierIndex; /* adresse du dernier bloc d’index */
}
2 Synchronisation de processus (6 points)
Les blocs d’index sont chaı̂nés et peuvent contenir TAILLE INDEX références aux blocs de données. Nous
Soient n processus numérotés P0 , P1 , . . . , Pn−1 . Chaque processus accède aux variables partagées disposons de deux fonctions pour manipuler ces index :
suivantes :
int creerIndex(int bloc, int precedent) Création d’un nouvel index contenant une seule référence.
Cette fonction renvoie l’adresse physique du nouvel index sur disque.
attente : tableau [ 0 ... n-1 ] de booléens;
verrou : booléen; void ajouterReference(int index, int bloc) Ajout d’un référence à un bloc d’index dont l’adresse
physique est passée en paramètre. Un emplacement doit être disponible dans l’index en question.
Ces variables sont toutes initialisées à la valeur faux. Les autres variables sont propres à chaque processus.
Par ailleurs, nous disposons sur cette machine d’une instruction câblée de synchronisation définie par Dans ce cadre, répondez aux questions suivantes :
instruction Test-And-Set ( var copie:booléen, var verrou:booléen ) a) Donnez une explication de ce codage (2 points).
début
en exclusion mutuelle faire b) Donnez une implantation de la fonction ajouterBloc qui a la charge d’ajouter un bloc de donnée
copie := verrou; à un descripteur en prenant soin, le cas échéant, de créer un nouvel index. Attention : quatre cas
verrou := vrai; sont à étudier (4 points).
fin-faire
void ajouterBloc(struct descripteur* d, int bloc)
fin
Le processus Pi a la forme suivante :

Systèmes d’exploitation Soit un processus dont le travail consiste à calculer (pendant 1 seconde) et à sauver le résultat dans
Licence d’informatique
Faculté des Sciences de Luminy Questions :
9 Juin 2004,
durée 3 heures, a) Quel est le temps de réponse de ce processus et le taux d’utilisation de la CPU sur la période
Tous les documents sont autorisés. considérée ?
Dans ces conditions répondez à la question a) et donnez la trace de l’exécution.
1 Producteur et consommateur (9 points) c) Du point de vue du système d’exploitation, est-il intéressant d’allouer un tampon de sortie dont la
taille est supérieur à 4 secondes (justifiez votre réponse) ?
L’activité de gestion d’un entrepôt est formalisée par les variables partagées définies ci-dessous. Un
processus producteur a la charge de remplir le stock tandis qu’un processus consommateur à la charge de d) Admettons maintenant que le fichier ainsi créé soit stocké sur une pseudo partition de répartition
le vider. construite à l’aide de deux disques. Quel est l’impact de cette organisation sur l’exécution du pro-
cessus ?
stock : tableau[0 à Max-1] de produits;
nbTotalProduits : entier; 3 Les philosophes et les banquiers (6 points)
nbTotalConsommés : entier;
Un beau jour de juin, n philosophes décident d’aller manger ensemble des spaghettis. Le restaurateur
Questions : dresse une table ronde, mais place seulement n fourchettes (une entre chaque assiette). Pour manger, un
a) proposez une version de l’algorithme du producteur et du consommateur basée sur l’attente active
pour régler les problèmes de synchronisation. N’utilisez ni sémaphore ni instruction particulière du Questions :
processeur et indiquez clairement pourquoi votre solution d’attente active est correcte.
a) Montrez qu’il existe un risque d’interblocage et proposez une solution simple à ce problème.
b) Pour éviter une perte de CPU, les concepteurs décident d’utiliser les sémaphores à compteur pour
régler les problèmes de synchronisation. Donnez la nouvelle version de l’algorithme du producteur b) Pour éviter les interblocages, les philosophes décident d’appliquer l’algorithme des banquiers. Donnez
et du consommateur. la matrice Max et le vecteur Dispo.
c) Les concepteurs observent que le stock est toujours plein. Ceci est dû au fait que le processus c) Pour ce problème bien particulier donnez l’algorithme simplifié permettant de déterminer si oui
producteur est plus rapide que le processus consommateur. Pour régler ce problème, ils décident de ou non, le système est dans un état sain.
placer deux consommateurs pour un producteur. Donnez la nouvelle version de producteur et des
consommateurs. d) Sans vous préoccuper des problèmes de parallélisme et de synchronisation, donnez l’algorithme
appliqué par le ième philosophe avant de manger.
d) Si nous avons deux consommateurs, nous pourrions avoir deux stocks (un pour chaque consomma-
teur) et le producteur pourrait placer sa production alternativement dans les deux stocks. Expliquez e) Face à ce problème, le restaurateur décide de placer une assiette au centre de la table dans laquelle
pourquoi la solution du stock unique est meilleure (donnez au moins deux bonnes raisons). il pose les n fourchettes. Les philosophes vont chercher les fourchettes sur cette assiette et les y
reposent après avoir mangé. Dans ce cadre, existe-t-il un risque d’interblocage ?
e) Sur une machine mono-processeur quelle doit être la nature du traitement effectué par les consom-
mateurs pour que la multiplication de ces derniers soit intéressante. f) Donnez la nouvelle version de la matrice Max et du vecteur Dispo.
Questions :
Systèmes d’exploitation a) Montrez qu’il existe un risque d’interblocage et proposez une solution simple à ce problème.
b) Pour éviter les interblocages, les philosophes décident d’appliquer l’algorithme des banquiers. Donnez
Licence d’informatique — Faculté des Sciences de Luminy
la matrice Max et le vecteur Dispo.
19 Juin 2003,
durée 3 heures, c) Pour ce problème bien particulier donnez l’algorithme simplifié permettant de déterminer si oui
Tous les documents sont autorisés. ou non, le système est dans un état sain.
d) Sans vous préoccuper des problèmes de parallélisme et de synchronisation, donnez l’algorithme

appliqué par le ième philosophe avant de manger.
1 Parallélisme et utilisation des threads (10 points) e) Face à ce problème, le restaurateur décide de placer une assiette au centre de la table dans laquelle
il pose les n fourchettes. Les philosophes vont chercher les fourchettes sur cette assiette et les y
Vous venez d’acquérir une nouvelle machine dotée de quatre processeurs. Pour l’exploiter au mieux, reposent après avoir mangé. Dans ce cadre, existe-t-il un risque d’interblocage ?
vous décidez de modifier vos anciens programmes afin de les adapter à cette architecture. Pour ce faire,
le système d’exploitation vous offre deux fonctions pour gérer des threads : f) Donnez la nouvelle version de la matrice Max et du vecteur Dispo.

void thread_exit(); /* suicide d’un thread */ 3 Mémoire virtuelle paginée (4 points)
Cette fonction crée un nouveau thread fils par recopie à l’identique du thread courant (le père). Soit un système basé sur une mémoire virtuelle paginée. La taille des pages est fixée à 210 octets.
Le thread fils démarre son exécution comme si il revenait de l’appel à la fonction thread create. La Dans un programme C on déclare la tableau ci-dessous. Pour l’exécution de ce programme, le système a
fonction renvoie 0 chez le fils, -1 en cas d’erreur et le numéro du fils (un entier positif) chez le père. réservé 8 pages physiques qui sont initialement vides.
char tableau[32][2048];
Questions :
a) Le programme A est composé de trois parties (notées A1 , A2 et A3 ). A3 a besoin des résultats de Questions :
A1 et A2 et l’exécution de A1 est toujours plus longue que celle de A2 . Dans ce cadre, donnez une
a) Dans ce cadre, combien de défauts de page sont générés par le code suivant (on part du principe
version qui utilise le parallélisme de A et expliquez le gain attendu.
que les indices sont dans des registres) :
b) Même question, mais on ne connaı̂t pas le plus long des deux codes A1 et A2 . J’insiste : vous ne
disposez de rien d’autre que les deux fonctions présentées ci-dessus. Par contre, je vous rappelle que for(i=0; i<32; i++) for(j=0; j<2048; j++) tableau[i][j] = ’A’;
les threads partagent les variables globales. Quelle critique pouvez-vous faire de la solution que
vous proposez ? Justifiez votre réponse. Quel est l’impact d’un doublement de la mémoire physique (8 à 16) ?
c) Le programme B est composé de quatre parties. Le code B2 a besoin du résultat de B1 , tandis que b) Même question si le code devient (la mémoire physique est de 16 pages) :
B4 a besoin de B2 ou B3 . Proposez une version parallèle et éventuellement montrez les défauts de
votre solution. for(j=0; j<2048; j++) for(i=0; i<32; i++) tableau[i][j] = ’A’;
d) La nouvelle version du système vous offre les trois fonctions ci-dessous. Dans ce cadre, répondez à c) De combien faut-il augmenter le nombre de pages physiques pour que le nombre de défaut de page
la question c). baisse de manière significative ?

e) Comment modifier la réponse à la question précédente pour être sûr que le thread initial est
bien le dernier à terminer son exécution (utilisez les sémaphores).
2 Les philosophes et les banquiers (6 points)
Un beau jour de juin, n philosophes décident d’aller manger ensemble des spaghettis. Le restaurateur
dresse une table ronde, mais place seulement n fourchettes (une entre chaque assiette). Pour manger, un
d) Si on applique l’algorithme des banquiers, combien reste-t-il d’états possibles pour le système d’al-
location de ressources ?
Systèmes d’exploitation e) Pour éviter les interblocages, on peut associer un ordre à chaque ressource (par exemple R1 < R2 )
Licence d’informatique — Faculté des Sciences de Luminy et interdire les demandes d’allocation qui ne respectent pas cet ordre. Dans ces conditions, combien
12 Juin 2002, d’états sont encore possibles ?
durée 3 heures,
Tous les documents sont autorisés. 3 Mémoire virtuelle paginée (6 points)
Sur certains processeurs, l’étape de transformation des adresses virtuelles paginées en adresses phy-
siques est particulièrement simple. En effet, ces processeurs utilisent seulement leur mémoire associative
1 Gestion des processus (6 points) sans effectuer d’accès à la table des pages (voir ci-dessous) :
Soit le processus ci-dessous <npv,dép> := adresse_virtuelle_paginée

si il existe un couple <npv,npp> dans la mém. associative
faire 4 fois alors
| calculer pendant 1 seconde adresse_physique := <npp,dép>
| écrire sur le fichier F1 pendant 2 secondes sinon
fin-faire générer une interruption de défaut de mémoire associative
faire 4 fois fin si
| calculer pendant 1 seconde
| écrire sur le fichier F1 pendant 3 secondes Questions :
fin-faire
a) Sur ces processeurs il existe une instruction
Les deux séries d’écritures sont indépendantes.
ajouter_en_mémoire_associative <npv,npp>
Questions :
Que fait, d’après vous, cette instruction ?
a) Quel est le temps de réponse de ce processus et le taux d’utilisation de la CPU sur la période
considérée ? b) Même si le processeur n’utilise plus la table des pages virtuelles, cette structure de données est-elle
toujours utile (justifiez votre réponse) ?
b) Si le processus est maintenant structuré sous la forme de deux threads, chacun s’occupant d’une
boucle, quel est le nouveau temps de réponse et le taux d’utilisation de la CPU ? c) Donnez les grandes lignes du traitant associé à l’interruption défaut de mémoire associative .
c) Pour améliorer son code, le programmeur décide de garder les threads, mais de produire deux fichiers d) Quels sont les avantages et les inconvénients de cette implantation de la pagination par rapport à
différents (F1 et F2 par exemple). A quelles conditions peut-on obtenir une amélioration et laquelle la formule classique ?
(temps de réponse et taux de CPU) ?
e) Cette implantation pose un problème dans le choix d’une victime. Décrivez le problème et proposez
e) Admettons que le système alloue deux tampons de sortie pouvant contenir 2 secondes d’entrée/sortie une solution.
(un pour chaque thread). Dans ces conditions, répondez à la question a) et donnez la trace de
l’exécution.
2 Allocation de ressources (8 points)
Soit deux processus (P1 et P2 ) et deux ressources non partageables (R1 et R2 ). Les deux processus
vont utiliser les deux ressources (la matrice Max de l’algorithme des banquiers ne contient que des 1).
Questions :
a) Quels sont les états possibles de la ressource R1 (au sens du graphe d’allocation de ressources) ?
b) Quels sont les états possibles du processus P1 indépendamment de P2 ?
c) Quel est le nombre d’états possibles pour le système d’allocation de ressources (il est conseillé de
faire une étude de cas sur l’état de chaque ressource) ?
c) Du point de vue du système d’exploitation, est-il intéressant d’allouer un tampon de sortie dont la
taille est supérieur à 4 secondes (justifiez votre réponse) ?
Systèmes d’exploitation d) Admettons maintenant que le fichier ainsi créé soit stocké sur une pseudo partition de répartition
construite à l’aide de deux disques. Quel est l’impact de cette organisation sur l’exécution du
Licence d’informatique — Faculté de Luminy processus ?
4 mai 2001,
durée 3 heures,
Tous les documents sont autorisés.
3 Mémoire segmentée et paginée (7 points)
Soit un système basé sur une mémoire segmentée paginée. La taille des pages est fixée à 210 octets. La
taille maximale de chaque segment est fixée à 256 pages. La mémoire logique d’un processus est définie
par la table des segments suivante :
1 Implantation physique des fichiers (7 points)
N◦ de Segment table des pages Taille
Le bloc est l’unité élémentaire d’entrée/sortie sur disque. Il est défini comme suit : 0 1200 254
1 700 71
bloc = tableau [ 0..255 ] d’entiers; 2 750 3
Les lectures de blocs se font au moyen de la fonction lire_bloc(nu:entier; var b:bloc). Un des- Voila un extrait des tables de pages
cripteur de fichiers est un bloc qui contient les informations relatives à l’implantation physique du fichier.
adresse 1200 : adresse 700 :
Ce descripteur a la structure suivante : adresse 750 :
n◦ p. phys. n◦ p. phys.
— Les cases de 0 à 234 contiennent des informations diverses. n◦ p. phys.
0 100 0 600
— Les cases de 235 à 244 contiennent respectivement les adresses physiques des blocs de données 0 0 1000
1 250 .. ..
à 9 du fichier en question. .. .. . . 1 1100
— Les cases de 245 à 254 contiennent respectivement les adresses physiques des blocs d’index 0 à 9 . . 70 900 2 1150
du fichier en question. 253 80 71 - 3 -
— La case 255 contient l’adresse physique du dernier bloc d’index. 254 - .. .. .. ..
. . . .
Chaque entrée d’un bloc index contient l’adresse physique d’un bloc de données sauf la dernière (n◦ 255) 255 -
qui contient l’adresse du bloc d’index suivant et l’avant dernière (n◦ 254) qui contient l’adresse du bloc
d’index précédent. Questions :
a) Expliquez le sens des valeurs 1200, 700 et 750 présentes dans la table des segments.
Questions : b) Quelle est la taille totale de la mémoire occupée par ce processus ?
a) Quelle est la nature de ce codage ? c) Décrivez les composantes (taille et nature) d’une adresse logique segmentée et paginée dans un
b) Existe-t-il une limite pour la taille des fichiers avec cette organisation ? tel système.
c) Écrivez la fonction d) Quelles sont les adresses physiques pour les adresses logiques suivantes ?
fonction adresse physique( desc :bloc ; nubloc :entier ) : entier ; 262154, 2024, 335048, 525324, 259972
qui rend l’adresse physique du bloc de données d’adresse logique nubloc dans le fichier décrit par e) Pourquoi avoir choisi la limite de 256 pages pour la taille des segments ? Quelles en sont les
desc. Vous ne vous préoccuperez pas des problèmes de débordement ou des erreurs d’entrée/sortie. avantages ?
d) Si on cherche à lire 1000 entiers à partir de l’adresse 782800 (en entiers), combien de blocs
physiques le système d’exploitation doit-il lire en partant du principe qu’aucun bloc n’est gardé en
mémoire (à l’exception du descripteur) ?
e) Comment améliorer les accès séquentiels avec cette architecture ?
Soit un processus dont le travail consiste à calculer (pendant 1 seconde) et à sauver le résultat dans
Questions :
a) Quel est le temps de réponse de ce processus et le taux d’utilisation de la CPU sur la période
considérée ?
Dans ces conditions répondez à la question a) et donnez la trace de l’exécution.
adresse 1200 : adresse 700 : adresse 750 :
n◦ p. phys. n◦ p. phys. n◦ p. phys.
Systèmes d’exploitation 0
..
100
..
0
..
655
..
0
1
210
215
. . . .
Licence d’informatique — Faculté de Luminy 125 80 10 110 2 220
6 septembre 2001, .. ..
126 81 11 120 . .
durée 3 heures, .. .. .. .. .. ..
Tous les documents sont autorisés. . . . . . .
.. .. ..
255 . 255 . 255 .
Questions :
1 Synchronisation de processus (7 points) a) Expliquez le sens des valeurs 1200, 700 et 750 présentes dans la table des segments.
b) Quelle est la taille totale de la mémoire occupée par ce processus ?
On vous propose d’étudier le code de synchronisation suivant. Il utilise deux variables publiques (disponible c) Décrivez les composantes (taille et nature) d’une adresse logique segmentée et paginée dans un
et tour) et une variable privée (ticket). tel système.
d) Quelles sont les adresses physiques pour les adresses logiques suivantes ?
<init> disponible = 1
129124, 808970, 272404, 200, 526546
tour = 1
e) Pourquoi avoir choisi la limite de 256 pages pour la taille des segments ? Quelles en sont les
avantages ?
<prologue> ticket = disponible
f) Est-il possible de voir apparaı̂tre plusieurs fois la même valeur dans les tables de pages ? Que signifie
disponible = disponible + 1
cette répétition ?
répéter
jusqu’à (ticket = tour)
3 Traitement des interblocages (5 points)
<épilogue> tour = tour + 1
Considérons un système d’allocation de ressources portant sur 5 processus et 4 classes de ressources.
L’état du système est donné par les informations suivantes :
Questions :
a) Ce code est sensé régler un défaut lié aux solutions d’attente active. Quel est ce défaut et comment
Allocation Max
est-il supprimé ?
R1 R2 R3 R4 R1 R2 R3 R4
b) Ce code est-il une solution correcte au problème de l’exclusion mutuelle ? Expliquez votre réponse.
P0 1 0 0 2 P0 1 0 0 2 Dispo
c) Proposez une nouvelle version correcte basée sur le même principe. Vous pouvez utiliser une nouvelle
P1 0 0 1 0 P1 5 7 1 0 R1 R2 R3 R4
variable publique et l’instruction XRM.
P2 5 3 1 4 P2 5 3 2 6 2 5 1 0
P3 3 6 0 2 P3 5 6 0 2
2 Mémoire segmentée et paginée (8 points) P4 1 0 0 4 P4 5 6 0 6
10
Soit un système basé sur une mémoire segmentée paginée. La taille des pages est fixée à 2 octets. La Dans ce cadre, répondez aux questions suivantes en utilisant l’algorithme des banquiers :
taille maximale de chaque segment est fixée à 256 pages. La mémoire logique d’un processus est définie
par la table des segments suivante : a) Donnez la matrice des besoins.
b) Le système est-il dans un état sain ? Justifiez votre réponse.
N◦ de Segment table des pages Taille
0 1200 127 c) Si le processus P1 dépose la requête (2, 4, 0, 0), cette requête est-elle acceptée immédiatement ?
1 700 200 (justifiez votre réponse).
2 750 50 d) A partir de la situation initiale, si le processus P4 dépose la requête (2, 4, 1, 0), quel est le résultat ?
3 850 20
4 600 20
Voilà un extrait des tables de pages

Annales 3

Transféré par

Droits d'auteur :

Formats disponibles

Annales 3

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Annales 3

Transféré par

Droits d'auteur :

Formats disponibles

2 Gestion des processus et synchronisation (8 points)

Troisième année de la licence d’informatique

— E/S de 3s, calculer 3s, E/S de 4s

b) Même question pour un striping (RAID0) des diques : RAID0(D1,D2,D3,D4,D5,D6) ? [1 point]

Tournez la page SVP...

int current_high_process = -1; int current_low_process = -1;

Tournez la page SVP...

Systèmes Troisième année de la licence d’informatique

Systèmes Troisième année de la licence d’informatique

b) A quels moments le système s’exécute-t-il ? et à qui est  facturé  cette exécution ?

Tournez la page SVP...

Systèmes Troisième année de la licence d’informatique

1 Gestion des processus (7 points) Questions :

3 Gestion d’une mémoire virtuelle (6 points)

Exercice déjà posé.

Tournez la page SVP...

int creation(descripteur *d, int fat[], int taille_fat, int n)

2 Gestion de fichiers (8 points, 50 minutes)

void ajouter_bloc(descripteur *d, int fat[], int adr_bloc)

Systèmes Troisième année de la licence d’informatique

void supprimer_premier_bloc(descripteur *d)

2 Gestion de fichiers (7 points, 45 minutes)

Tournez la page SVP...

c) Même question pour une machine dotée de trois processeurs. [2 points]

e) On vous donne les fonctions suivantes :

int thread_create(); /* création d’un thread */

2 Mémoire paginée (5 points, 20 minutes)

Exercice déjà posé.

b) On vous donne les fonctions suivantes :

int thread_create(); /* création d’un thread */

c) On vous donne les fonctions suivantes :

sem_t sema_create(int compteur); /* création d’un sémaphore */

2 Mémoire paginée (5 points)

Exercice déjà posé.

3 Questions... réponses (6 points)

N’oubliez pas de justifier vos réponses.

1 Gestion de fichiers (8 points) Questions :

void lister_1er_blocs(int fat[], int taille_fat)

1 Synchronisation de processus (7 points)

Exercice déjà posé.

2 Allocation contigüe de la mémoire (6 points)

3 Questions... réponses (7 points)

a) Faut-il plusieurs processus pour exploiter pleinement une machine bi-processeurs ?

b) Comment le système peut-il retirer de la mémoire à un processus ?

c) A quels moments le système s’exécute-t-il ?

d) Comment le système assure-t-il la sécurité des données stockées sur un disque ?

f) Quelle est la définition du tampon utilisateur et son rôle ?

g) L’algorithme par subdivision (buddy system) provoque-t-il de la fragmentation interne ? externe ?

1 Gestion de fichiers (7 points)

Exercice déjà posé.

2 Questions... réponses (7 points)

b) Si nous ajoutons à la question a) un tampon de sortie pouvant contenir 1 seconde d’entrée/sortie,

d) Les pseudo-partitions de répartition (RAID 0 ou stripping ) améliorent-elles la sécurité ou l’efficacité ?

3 Gestion d’une mémoire virtuelle (6 points)

Exercice déjà posé.

void verifier_disque(int fat[], int taille_fat); Questions :

N’oubliez pas de justifier vos réponses.

b) Ecrivez la fonction de transformation des adresses virtuelles en adresses physiques. Questions :

e) Comment le partage de pages peut-il s’organiser dans ce système ?

b) A quels moments le système s’exécute-t-il ? et à qui est facturé cette exécution ?