Système d’Exploitation II Exam

Exercice 1 - Qui suis-je ?

Cet exercice teste vos connaissances de base sur les concepts fondamentaux des systèmes d'exploitation.

Question 1.a - Je suis une fragmentation qui affecte les systèmes de gestion de mémoire paginée ? La réponse est la fragmentation interne. Dans un système paginé, la mémoire est divisée en blocs de taille fixe (les pages). Si un processus n'utilise pas entièrement la dernière page qui lui est allouée, l'espace restant dans cette page est gaspillé. C'est ce qu'on appelle la fragmentation interne. La fragmentation externe, quant à elle, affecte la segmentation.

Question 1.b - Je suis un algorithme qui alloue un espace libre de la mémoire à un processus donné. Je parcours toute la liste et recherche le plus petit espace pouvant contenir ce processus ? La réponse est l'algorithme Best Fit (ou le "plus juste"). L'algorithme parcourt toute la liste des blocs libres pour trouver celui dont la taille est la plus proche de la taille requise (le plus petit bloc suffisamment grand), afin de minimiser l'espace perdu dans ce bloc.

Question 1.c - Je permets de modéliser des processus qui entrent en concurrence pour les accès aux bases de données ? La réponse est le problème des lecteurs-rédacteurs. C'est un problème classique de synchronisation où plusieurs processus tentent de lire et d'écrire des données partagées. Les lecteurs peuvent accéder simultanément à la ressource, mais un rédacteur doit avoir un accès exclusif.

Question 1.d - Je suis un mécanisme de pthread qui est utilisé conjointement avec les mutex. Il permet à un thread de se bloquer en attendant l'occurrence d'un événement particulier ? La réponse est la variable de condition (condition variable). Les variables de condition (pthread_cond_t) permettent aux threads de se suspendre et de libérer le processeur jusqu'à ce qu'une certaine condition logique sur les données partagées (protégées par le mutex) soit remplie.

Question 1.e - Je suis un processus qui est toujours en exécution alors que son père s'est terminé ? La réponse est un processus orphelin. Lorsqu'un processus père se termine avant son fils, ce dernier devient orphelin. Sous les systèmes de type UNIX, il est alors généralement adopté par le processus init (PID 1).

Exercice 2 - Processus et Threads (fork)

Le code fourni génère de nouveaux processus à l'aide de l'appel système fork(). Note : Le code source original manque des inclusions de bibliothèques standards (stdio.h, sys/types.h, unistd.h). Nous supposerons qu'elles sont présentes pour que le code compile.

Question 2.a - Arborescence des processus

Le processus initial P1 exécute le premier fork(). Cela crée un processus fils P2. À ce stade, P1 et P2 poursuivent l'exécution et rencontrent tous les deux le second fork(). P1 crée un nouveau fils P3. P2 crée un nouveau fils P4.

L'arborescence est donc la suivante : P1 ├──> P2 │ └──> P4 └──> P3

Question 2.b - Affichage à l'écran

Rappelons que fork() renvoie 0 au processus fils, et le PID du fils au processus père. Nous supposons que les numéros de PID sont strictement croissants.

Analysons l'état des variables pid1 et pid2 pour chaque processus au moment d'arriver à l'instruction printf :

1. Processus P1 (le père initial) :

   • Premier fork : reçoit le PID de P2 dans pid1. Donc pid1 = PID-P2.
   • Deuxième fork : reçoit le PID de P3 dans pid2. Donc pid2 = PID-P3.
   • Affichage : Je suis PID-P1, pid1=PID-P2, pid2=PID-P3

2. Processus P2 (le premier fils de P1) :

   • Issu du premier fork : la valeur de retour est 0, donc pid1 = 0.
   • Deuxième fork : P2 crée P4 et reçoit son PID. Donc pid2 = PID-P4.
   • Affichage : Je suis PID-P2, pid1=0, pid2=PID-P4

3. Processus P3 (le deuxième fils de P1) :

   • P3 est créé par le deuxième fork du processus P1. Il hérite de la mémoire de P1 après le premier fork.
   • P1 avait déjà enregistré pid1 = PID-P2. P3 en hérite, donc pid1 = PID-P2.
   • Issu du deuxième fork : la valeur de retour est 0, donc pid2 = 0.
   • Affichage : Je suis PID-P3, pid1=PID-P2, pid2=0

Processus P4 (le fils de P2) :

• P4 est créé par le deuxième fork du processus P2. Il hérite de la mémoire de P2.
• P2 avait pid1 = 0. P4 en hérite, donc pid1 = 0.
• Issu du deuxième fork : la valeur de retour est 0, donc pid2 = 0.
• Affichage : Je suis PID-P4, pid1=0, pid2=0

Exercice 3 - Exécution de threads

Note sur le code : J'ai corrigé l'indentation et je considère que les bibliothèques stdio.h, stdlib.h et pthread.h sont incluses. Le code tel que retranscrit comporte aussi un paramètre manquant dans l'appel de création, mais le contexte permet de deviner l'intention.

Le programme principal crée un thread qui exécute la fonction thread_function. Ensuite, le thread principal affiche I have to wait ?, puis appelle pthread_join, ce qui le bloque jusqu'à ce que le thread secondaire se termine. Le thread secondaire affiche Hello World :) puis quitte. Une fois le thread secondaire terminé, le thread principal reprend et affiche Goodbye Cruel World :(.

Résultat de l'exécution attendu selon l'énoncé : I have to wait ? Hello World :)

Correction importante : L'énoncé omet la dernière ligne dans sa solution officielle. En réalité, un programme C correct exécutera également le dernier printf situé après le pthread_join. Le véritable affichage complet sur la console sera : I have to wait ? Hello World :) Goodbye Cruel World :(

Exercice 4 - Concurrence et synchronisation des processus

Le sémaphore S est initialisé à 2. La primitive P(S) décrémente le sémaphore (et bloque si S < 0). La primitive V(S) l'incrémente.

Question 4.a - Ordres d'exécution possibles (S=2)

Le processus A a besoin d'obtenir deux fois le sémaphore avant d'exécuter a et b. Le processus B a besoin de l'obtenir une fois avant d'exécuter c et d. Puisque S est initialisé à 2 :

• Soit A exécute ses deux P(S) sans être interrompu, la valeur de S tombe à 0. A exécute a et b. B est bloqué jusqu'à ce que A libère au moins un jeton. (Ordre : a, b, c, d)
• Soit B exécute son P(S) en premier, S passe à 1. B exécute c et d. Même si A commence et prend un jeton (S=0), il sera bloqué au deuxième P(S) jusqu'à ce que B relâche ses jetons. B fait ses deux V(S). A peut alors finir. (Ordre : c, d, a, b)

Question 4.b - Blocage mutuel (S=1)

Supposons que le sémaphore S est initialisé à 1. A et B peuvent-ils se bloquer mutuellement ? Oui. Justification : Si le processus A s'exécute en premier, il fait un appel à P(S). Le sémaphore passe à 0. A essaie ensuite de faire un deuxième P(S) consécutif, mais comme S=0, il se bloque en attendant. Si le processus B prend la main, il tente de faire P(S). Comme S=0, B se bloque aussi. Les deux processus s'attendent indéfiniment : c'est un interblocage (deadlock).

Question 4.c - Scénario sans blocage (S=1)

Existe-t-il un scénario où les quatre instructions s'exécutent avec S=1 ? Oui, l'ordre c d a b. Scénario :

1. Le processeur alloue le temps à B en premier.
2. B exécute P(S) (S devient 0).
3. B exécute c et d.
4. B exécute le premier V(S) (S devient 1).
5. B exécute le second V(S) (S devient 2).
6. Le processus A prend la main.
7. A exécute P(S) (S devient 1).
8. A exécute son deuxième P(S) (S devient 0).
9. A exécute a et b.
10. A exécute V(S) (S redevient 1). Tout s'est déroulé sans blocage.

Exercice 5 - Graphe de précédence

Il faut synchroniser les processus P1, P2, P3 et P4 de manière à respecter un graphe où (selon la logique du code solution) :

• L'instruction I1 (dans P1) doit s'exécuter avant I2 (dans P2) et avant I3 (dans P3).
• Les instructions I2 et I3 doivent toutes deux s'exécuter avant l'instruction I4 (dans P4).

Note : La solution originale du corrigé contient des erreurs de frappe (oubli du processus P4 dans l'entête, et affectation de I3 au lieu de I4 dans le processus P4). Voici la version corrigée et fonctionnelle.

Nous utiliserons 3 sémaphores initialisés à 0 :

• S1 pour signaler que P1 est terminé à P2.
• S2 pour signaler que P1 est terminé à P3.
• S3 pour comptabiliser la fin de P2 et P3 avant de lancer P4.

PROGRAM P1P2P3P4;

semaphore S1, S2, S3 init 0;

var
Process P1 { 
    I1; 
    V(S1); 
    V(S2); 
}
Process P2 { 
    P(S1); 
    I2; 
    V(S3); 
}
Process P3 { 
    P(S2); 
    I3; 
    V(S3); 
}
Process P4 { 
    P(S3); 
    P(S3); 
    I4; 
}

Explication : P1 débloque P2 et P3. P4 attend que P2 ET P3 envoient un signal sur S3 (il fait donc deux fois P(S3) car chaque V(S3) ajoute un jeton).

Exercice 6 - Gestion de la mémoire (Segmentation et Pagination)

Données du problème :

• Taille d'une page : 4 Ko = 4096 octets.
• Taille S1 = 16 Ko, S2 = 8 Ko, S3 = 4 Ko.
• Pages en mémoire physique :
  • Segment S1 : Page 2 dans le cadre 0, Page 3 dans le cadre 2. (Note : L'énoncé dit "pages 2 et 3 ... dans les cadres 2, 0", ce qui prêterait à confusion, mais la solution officielle indique que le cadre de la page 2 est 0).
  • Segment S2 : Page 2 dans le cadre 9.
  • Segment S3 : Page 1 dans le cadre 12.
• Adresse logique décimale recherchée = 8212.

Calculons l'emplacement de cette donnée.

Question 6.a - Le segment

Dans un espace d'adressage linéaire où les segments se suivent (S1 de 0 à 16383, S2 à partir de 16384, etc.), l'adresse 8212 est strictement inférieure à la taille de S1 (16384 octets). Segment = S1

Question 6.b - Le numéro de page dans le segment

On divise l'adresse par la taille de la page : 8212 ÷ 4096 = 2,0048... La partie entière nous donne le numéro de la page. Numéro de page = 2

Question 6.c - Le déplacement (offset) dans la page

Le déplacement est le reste de la division entière (modulo) : 8212 - (2 × 4096) = 8212 - 8192 = 20. Déplacement = 20

Question 6.d - Le numéro de cadre

D'après l'énoncé (et comme vérifié par la solution), la page 2 du segment S1 est mappée dans le cadre 0. Cadre = 0

Question 6.e - Le déplacement dans le cadre

Le déplacement physique dans le cadre est toujours rigoureusement identique au déplacement virtuel dans la page. Déplacement = 20

Question 6.f - L'adresse physique (en décimal)

L'adresse physique = (Numéro de cadre × Taille de la page) + Déplacement Adresse = (0 × 4096) + 20 = 20. L'adresse physique est donc 20 en décimal.

Exercice 7 - Pagination à trois niveaux

Données du système :

• Adresses virtuelles et physiques sur 32 bits.
• Taille d'une page : 2 Ko = 2048 octets (donc 11 bits dédiés au déplacement, car 2^11 = 2048).
• Taille d'une table de pages : 512 octets.
• Taille d'une entrée : 4 octets.

Calcul du nombre d'entrées par table : 512 octets ÷ 4 octets = 128 entrées par table. Pour indexer 128 entrées, il faut 7 bits (car 2^7 = 128).

Question 7.a - Taille maximale de l'espace virtuel

L'espace virtuel est géré par des adresses de 32 bits. Le nombre de pages maximum est l'espace adressable total divisé par la taille d'une page. Nombre de pages = 2^32 ÷ 2^11 = 2^(32-11) = 2^21 pages (ce qui équivaut à 2 Méga-pages ou Mi pages).

Question 7.b - Nombre maximal de tables de pages

Dans un système à 3 niveaux où chaque table contient 128 entrées :

• Niveau 1 (répertoire principal) : 1 seule table.
• Niveau 2 : chaque entrée du niveau 1 pointe vers une table de niveau 2. Donc 128 tables maximum au niveau 2 (2^7).
• Niveau 3 : chaque entrée du niveau 2 pointe vers une table de niveau 3. Donc 128 × 128 tables maximum au niveau 3 (2^7 × 2^7).

Nombre total maximal de tables = 1 + 128 + (128 × 128) = 1 + 128 + 16384 = 16513 tables.

Question 7.c - Format d'une adresse virtuelle

Puisque le déplacement (offset) nécessite 11 bits (pour adresser les 2 Ko), il reste 32 - 11 = 21 bits pour indexer les tables de pages. Puisque chaque table nécessite 7 bits d'indexation (pour ses 128 entrées), ces 21 bits sont divisés équitablement entre les trois niveaux : 21 = 7 + 7 + 7.

Le format de l'adresse virtuelle sur 32 bits est :

• 7 bits : Index pour l'entrée dans la table de 1er niveau
• 7 bits : Index pour l'entrée dans la table de 2nd niveau
• 7 bits : Index pour l'entrée dans la table de 3ème niveau
• 11 bits : Déplacement dans la page (offset).

Méthode

Voici comment bien aborder ce type d'épreuve d'architecture et systèmes d'exploitation :

1. Ne paniquez pas sur les calculs d'adresses : Les exercices de pagination (comme les exercices 6 et 7) sont de simples conversions d'unités. Rappelez-vous que tout se résume à des puissances de 2. Apprenez par cœur que 1 Ko = 2^10 octets, 2 Ko = 2^11, 4 Ko = 2^12. L'offset (déplacement) est toujours constitué des bits de poids faible.
2. Lisez les hypothèses de l'énoncé : Dans l'exercice 6, la formulation "respectivement dans les cadres 2, 0" peut prêter à confusion. Toujours recalculer pour voir quelle correspondance donne un sens cohérent au problème.
3. Simulez l'exécution avec papier et crayon : Pour les questions de threads, de fork() ou de sémaphores, tracez un arbre pour les processus ou un tableau temporel (chronogramme). C'est le seul moyen infaillible d'identifier les deadlocks (interblocages) ou les affichages exacts à l'écran.
4. Apprenez la sémantique de Dijkstra : P() (Proberen) prend une ressource (décrémente), V() (Verhogen) libère une ressource (incrémente). Un sémaphore d'exclusion mutuelle s'initialise généralement à 1. Un sémaphore de synchronisation pour imposer un ordre d'exécution (comme dans l'exercice 5) s'initialise à 0.