Système d'Exploitation II

Exercice 1 - Qui suis-je ?

Question 1 - Identifications

(a) Je suis une fragmentation qui affecte les systèmes de gestion de mémoire segmentée ? La fragmentation externe. Contrairement à la pagination, la segmentation crée des blocs de tailles variables, ce qui laisse des espaces libres (trous) de petite taille éparpillés en mémoire physique.

(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 grand espace pouvant contenir ce processus ? L'algorithme du Pire Ajustement (Worst-Fit).

(c) Je permet de modéliser des processus qui entrent en concurrence pour un accès exclusif à un nombre limité de ressources, comme le cas des périphériques d'E/S. Un sémaphore (plus particulièrement un sémaphore à compteur, bien qu'un mutex soit utilisé si la ressource est unique).

(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. Une variable conditionnelle (type pthread_cond_t).

(e) Je suis un processus qui s'est achevé tout en disposant toujours d'un identifiant de processus (PID). Un processus zombie (zombie process). Il a terminé son exécution mais son processus père n'a pas encore lu son code de retour via wait().

Exercice 2 - Processus et Threads

Question 2 - Analyse de processus

(a) Nombre de processus créés et arborescence

La fonction main lance le processus initial (P0) avec i = 0. L'appel à creer() s'exécute de la façon suivante :

1. P0 exécute le premier fork(), créant P1. (Total : 2 processus). Les deux ont i = 0.
2. P0 et P1 exécutent le premier printf et affichent tous deux i=0.
3. P0 et P1 incrémentent i : i = 0 + 1 = 1.
4. P0 et P1 exécutent le second fork(). P0 crée P2, et P1 crée P3. (Total : 4 processus). Tous ont maintenant i = 1.
5. De retour dans main(), les 4 processus exécutent le second printf et affichent tous i=1.

Le nombre total de nouveaux processus créés (en plus du processus initial P0) est de 3.

Arborescence et affichages :

• P0 (Processus principal) : Affiche i=0 puis i=1
  • P1 (Créé par le 1er fork de P0) : Affiche i=0 puis i=1
    • P3 (Créé par le 2nd fork de P1) : Affiche i=1
  • P2 (Créé par le 2nd fork de P0) : Affiche i=1

(b) Remplacement par des threads

Si l'on remplace conceptuellement chaque création de processus par une création de thread (pthread_create), la fonction appelée par le thread principal crée un premier thread, fait un calcul local (i = i + 1), puis crée un second thread. Ces nouveaux threads exécutent leur fonction puis s'arrêtent via pthread_exit. Le nombre de threads créés (en plus du thread principal) est de 2.

(c) Le thread principal devrait-il attendre la fin des threads créés ?

Oui, absolument. L'appel à exit(0) dans le thread principal termine immédiatement le processus entier, détruisant de fait tous les threads existants, qu'ils aient terminé leur travail ou non. Pour que les threads secondaires aient le temps d'accomplir leurs calculs locaux, le thread principal doit utiliser pthread_join pour attendre leur terminaison avant de faire appel à exit(0).

Question 3 - Exécution de threads partagés

Remarque : Le code source fourni contient une variable partagée non protégée, ce qui génère une situation de compétition (race condition).

Résultat de l'exécution du programme :

L'exécution du programme donne un affichage entrelacé à l'écran de 20 caractères o et 20 caractères ., typiquement de manière très mélangée (par exemple o.o.o.o.o.o. ou similaire), suivi du texte final de la variable myglobal.

Le résultat final imprimé pour myglobal sera imprévisible et indéterministe, mais très probablement différent de 40 (valeur qu'on obtiendrait avec une synchronisation parfaite). À cause du sleep(1) entre la lecture et l'écriture dans la fonction du thread, on assiste à un écrasement systématique (lost update) :

• Le thread lit la valeur de myglobal dans j.
• Il incrémente j.
• Il attend 1 seconde (sleep(1)). Pendant ce temps, la boucle du thread principal incrémente également myglobal et attend.
• Au réveil, le thread écrase myglobal avec j, annulant l'incrémentation effectuée par le programme principal.

La valeur finale de myglobal sera généralement autour de 20 (ou comprise entre 20 et 39) en fonction de l'ordre exact d'ordonnancement par le système, car le thread finit souvent par imposer sa propre version retardée du compteur.

Exercice 3 - Concurrence et synchronisation des processus

Question 4 - Ordres d'exécution avec sémaphore

(a) Le sémaphore S est initialisé à 1

Les instructions b et c sont protégées par le sémaphore et constituent des sections critiques : elles ne peuvent pas s'exécuter en même temps.

• a s'exécute toujours avant b.
• d s'exécute toujours après c.

Si le processus A entre en premier dans sa section critique, b s'exécute avant c.

• Ordre possible 1 : a, b, c, d

Si le processus B entre en premier dans sa section critique, c s'exécute avant b. L'instruction a n'est pas bloquée par le sémaphore et peut s'exécuter avant, pendant ou après c, tant qu'elle est avant b.

• Ordre possible 2 : c, d, a, b
• Ordre possible 3 : c, a, d, b
• Ordre possible 4 : c, a, b, d
• Ordre possible 5 : a, c, d, b
• Ordre possible 6 : a, c, b, d

(b) Le sémaphore S est initialisé à 0

L'initialisation à 0 signifie que le premier processus qui effectue un appel à P(S) sera bloqué en attendant un signal V(S) qui ne viendra jamais.

• Le Processus A va exécuter a, puis appeler P(S) et se bloquer.
• Le Processus B va appeler P(S) dès le début et se bloquer. Il s'agit d'une situation d'interblocage (deadlock). Le seul ordre d'exécution d'instructions atomiques possible est l'exécution de a. Les instructions b, c et d ne seront jamais exécutées.

Question 5 - Section critique et signaux

(a) P1 et P2 peuvent-ils se retrouver en section critique en même temps ?

Oui, absolument. Il s'agit d'une vulnérabilité classique de type "Check-Then-Act" (Vérifier puis Agir), car la vérification de la variable et son assignation ne sont pas atomiques. Scénario de défaillance :

1. P1 teste verrou != 0. La valeur est 0, donc P1 ne se met pas en pause.
2. Avant que P1 ne puisse exécuter verrou = 1, le système donne la main à P2 (préemption).
3. P2 teste verrou != 0. La valeur est toujours 0, donc P2 ne se met pas en pause.
4. P2 exécute verrou = 1 et entre dans SC().
5. P1 reprend son exécution, exécute verrou = 1 (écrasant la même valeur) et entre à son tour dans SC(). Les deux processus sont alors en section critique simultanément.

(b) Est-ce que l'un des processus peut se retrouver en pause pour toujours ?

Oui. Le problème est lié à la perte de signal (Lost Wakeup). Scénario de défaillance :

1. P1 est en section critique. P2 exécute while (verrou != 0) et s'apprête à appeler pause().
2. Juste avant que P2 n'exécute l'instruction pause(), il est suspendu par le système.
3. P1 termine sa section critique, met verrou = 0 et envoie le signal SIGCONT à P2 avec kill().
4. Comme stipulé dans l'énoncé, si le processus n'est pas bloqué (ce qui est le cas puisque P2 n'a pas encore exécuté pause()), le signal est ignoré et perdu.
5. P2 reprend son exécution, appelle finalement pause() et s'endort indéfiniment car P1 ne lui enverra plus de signal.

Question 6 - Graphe de précédence

Pour forcer l'ordre P1 → P2 → P3, nous avons besoin de deux sémaphores pour transmettre l'autorisation d'exécution d'un processus au suivant.

PROGRAM P1P2P3;
var 
    S12, S23: semaphore;
semaphore init S12 = 0, S23 = 0;

Process P1 { 
    I1; 
    V(S12); 
}

Process P2 { 
    P(S12); 
    I2; 
    V(S23); 
}

Process P3 { 
    P(S23); 
    I3; 
}

Note sur le code source : L'énoncé d'origine contenait quelques coquilles de syntaxe. Le code ci-dessus les corrige pour présenter une syntaxe valide.

Exercice 4 - Gestion de la mémoire

Question 7 - Pagination simple et multiniveaux

Pagination simple

• RAM = 4 Go = 4 × 10⁹ octets ≈ 2³² octets
• Taille de page = 4 Ko = 4 × 10³ octets ≈ 2¹² octets
• Adresse virtuelle = 64 bits

(a) Bits de l'adresse physique spécifiant le cadre de page Le nombre total de cadres de pages en mémoire physique est : (Taille de la RAM) ÷ (Taille de page) = 2³² ÷ 2¹² = 2²⁰ cadres. Il faut donc 20 bits pour spécifier le numéro du cadre de page.

(b) Taille de la table des pages

• Nombre de bits pour le déplacement (offset) dans une page de 4 Ko : 12 bits.
• Nombre de bits pour la page virtuelle : 64 bits - 12 bits = 52 bits. Le nombre d'entrées dans la table des pages est donc de 2⁵².

Taille d'une entrée : 20 bits (cadre de page) + 1 bit (Présence) + 1 bit (Référence) + 1 bit (Modification) = 23 bits. Taille totale de la table des pages : 23 bits × 2⁵² entrées (ce qui équivaut à un peu moins de 3 octets par entrée, soit presque 12 Pétaoctets si on aligne sur 3 octets).

(c) Recommandation de cette approche Non, cette approche est à proscrire absolument. Une table de pages simple nécessiterait environ 12 Pétaoctets (Po) d'espace, ce qui est immensément supérieur à la capacité totale de la RAM (4 Go) et même du disque SSD (64 Go). L'ordinateur ne pourrait physiquement pas stocker sa propre table de pages.

Pagination à plusieurs niveaux

(a) Le nombre maximal de pages de l'espace virtuel dépend-il de la répartition des bits restants ? Non. Le nombre maximal de pages dépend exclusivement du nombre de bits utilisés pour adresser les pages (la partie identifiante de l'adresse), qui reste fixe à 52 bits (64 bits - 12 bits d'offset). Le nombre maximal de pages de l'espace virtuel est invariablement de 2⁵² pages, peu importe si les 52 bits sont segmentés en 2, 3 ou 4 niveaux de pagination. La répartition affecte seulement la taille et le nombre des tables intermédiaires, pas l'espace d'adressage total.

(b) Un avantage de la mémoire paginée à plusieurs niveaux La pagination à plusieurs niveaux permet de ne pas avoir à créer la table de pages entière ni à l'allouer en mémoire physique contiguë. Le système d'exploitation ne crée que les tables des répertoires et sous-répertoires correspondant aux zones de mémoire virtuelle effectivement utilisées par le processus. Cela permet une économie drastique de la RAM consommée par les structures de gestion mémoire pour des processus ayant des adressages clairsemés.

Méthode

Pour réussir ce type d'examen sur les Systèmes d'Exploitation :

1. Arborescence de processus (fork) : Dessinez toujours systématiquement un arbre sur votre brouillon. Chaque fork() dédouble la branche sur laquelle vous vous trouvez. Marquez le point d'exécution après le fork pour savoir quelles instructions touchent les enfants, et suivez la copie des variables locales.
2. Concurrency et Course critique : Face à des problèmes de threads synchronisés par le temps (sleep) et manipulant une variable globale, recherchez immédiatement le schéma "Read-Modify-Write". Un thread est souvent préempté après avoir lu la valeur, rendant ses écritures destructives envers celles des autres (Lost Update).
3. Ordres d'exécution (Sémaphores) : Décomposez les séquences. Ce qui est avant un P() est libre, ce qui est entre un P() et un V() est exclusif. Faites la liste mentale de "qui obtient le mutex en premier ?" et déduisez tous les entrelacements possibles à partir de là.
4. Conception de mémoire : Maîtrisez les puissances de 2. Apprenez par cœur que 1 Ko = 2¹⁰ octets, 1 Mo = 2²⁰ octets, 1 Go = 2³⁰ octets. Calculez systématiquement l'adresse sous forme de (Numéro de page | Déplacement) pour l'espace virtuel, et de (Cadre de page | Déplacement) pour l'espace physique.