Systèmes d'Exploitation Avancés

GESTION DE LA MÉMOIRE - Exercice I

Question 1 - Taille du plus grand segment

L'adressage virtuel se fait sur 32 bits, répartis ainsi selon l'énoncé :

• 14 bits pour le numéro de segment
• 6 bits pour le numéro de page
• 12 bits de déplacement (offset), ce qui correspond bien à une taille de page de 4 Ko (car 2^12 octets = 4096 octets = 4 Ko).

Le plus grand segment possible contient le nombre maximum de pages adressables par les 6 bits réservés au numéro de page.

• Nombre maximum de pages par segment : 2^6 = 64 pages.
• Taille en Ko : 64 pages × 4 Ko/page = 256 Ko.

La taille du plus grand segment est donc de 64 pages, soit 256 Ko.

Question 2 - Traduction de l'adresse virtuelle

Pour traduire l'adresse virtuelle 0xAE854C9C en adresse physique, il nous manque la table des segments (qui donne l'adresse de base de la table des pages du segment correspondant) ainsi que la table des pages de ce segment (qui donne le numéro du cadre physique en mémoire centrale).

Si nous avions ces structures, les étapes seraient les suivantes :

1. Découpage de l'adresse : Convertir 0xAE854C9C en binaire (32 bits) et l'isoler en trois parties : les 14 premiers bits (numéro de segment), les 6 bits suivants (numéro de page) et les 12 derniers bits (déplacement).
2. Recherche du segment : Utiliser le numéro de segment comme index dans la table des segments pour trouver l'adresse de la table des pages associée.
3. Recherche de la page : Utiliser le numéro de page comme index dans cette table des pages pour récupérer le numéro du cadre de page (case mémoire physique).
4. Calcul de l'adresse physique : Concaténer le numéro du cadre trouvé avec les 12 bits de déplacement d'origine.

Question 3 - Taille des tables de pages pour un processus complet

L'adresse est maintenant divisée en : 10 bits (niveau 1) + 10 bits (niveau 2) + 12 bits (déplacement). Chaque entrée de la table de premier niveau fait 4 octets.

Calculons le nombre de pages nécessaires pour stocker l'arborescence des tables :

• Table de niveau 1 : Elle possède 2^10 = 1024 entrées. Puisque chaque entrée pèse 4 octets, la table complète pèse 1024 × 4 = 4096 octets (soit 4 Ko, donc exactement 1 page).
• Tables de niveau 2 : Si le processus utilise tout l'espace adressable, les 1024 entrées de la table de niveau 1 pointent toutes vers une table de niveau 2 valide. Il y a donc 1024 tables de niveau 2. Chacune possède 2^10 entrées et occupe également 4 Ko (soit 1 page par table).
• Total : 1 page (niveau 1) + 1024 pages (niveau 2) = 1025 pages.

Note pédagogique sur la correction source : La correction de l'énoncé indique un calcul aboutissant à 4 Go (4 × 2^10 × 2^10 Ko). Ce calcul ne donne pas le nombre de pages nécessaires pour stocker les tables, mais plutôt la taille totale de la mémoire virtuelle adressable par le processus (2^20 cadres de 4 Ko = 4 Go). La vraie réponse à la question posée ("combien de pages pour contenir les tables") est 1025.

Question 4 - Chargement des tables de niveau 2 pour un processus de 22 Mo

Chaque table de pages de niveau 2 référence 1024 pages de 4 Ko, soit une plage de 4 Mo d'espace virtuel. Les plages couvertes par les tables de niveau 2 successives sont donc :

• Table 0 : de 0 à 4 Mo - 1
• Table 1 : de 4 Mo à 8 Mo - 1
• Table 2 : de 8 Mo à 12 Mo - 1
• Table 3 : de 12 Mo à 16 Mo - 1
• Table 4 : de 16 Mo à 20 Mo - 1
• Table 5 : de 20 Mo à 24 Mo - 1

Évaluons les besoins du processus :

• Code (2 Mo à 6 Mo - 1) : Cette plage chevauche la Table 0 (qui va jusqu'à 4 Mo) et la Table 1 (qui commence à 4 Mo). Il faut donc charger 2 pages de niveau 2.
• Données (12 Mo à 21 Mo - 1) : Cette plage commence au début de la Table 3, traverse entièrement la Table 4, et déborde sur la Table 5 (jusqu'à 21 Mo). Il faut donc charger 3 pages de niveau 2.

Au total, 5 pages de niveau 2 devront être chargées en mémoire centrale.

GESTION DE LA MÉMOIRE - Exercice II : Taille de cache

La séquence d'accès est : 0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 1, 0, 2, 3, 2, 5.

Analyse avec une mémoire tampon de 3 pages

• Algorithme PAPS (FIFO) : La page la plus ancienne chargée est remplacée. Le déroulement complet montre des défauts sur les accès suivants : 0, 1, 2, 3, 4, 5, 1, 0, 2, 3, 5. On compte 11 défauts de page.
• Algorithme LRU : La page non utilisée depuis le plus longtemps est remplacée. Le déroulement aboutit également aux mêmes moments de remplacement critiques (0, 1, 2, 3, 4, 5, 1, 0, 2, 3, 5). On compte 11 défauts de page.

Lequel semble préférable ? Dans ce cas précis, les deux algorithmes donnent exactement le même nombre de défauts de page (11). Généralement, LRU est préférable car il exploite le principe de localité temporelle, mais sur cette séquence particulière, il n'y a pas d'avantage chiffré.

Analyse avec une mémoire tampon de 4 pages

• Algorithme PAPS (FIFO) : En allouant 4 cadres, la séquence produit toujours 11 défauts de page.
• Algorithme LRU : En allouant 4 cadres, la séquence produit également 11 défauts de page.

Note pédagogique majeure : La correction source évoque "l'anomalie de Belady" pour justifier que le taux de défaut de page puisse stagner ou croître avec plus de mémoire, et attribue cette remarque à la fois à PAPS et à LRU à cause d'un copier-coller dans le document original. Il est crucial de retenir que seul l'algorithme FIFO (PAPS) est sujet à l'anomalie de Belady. L'algorithme LRU fait partie de la famille des algorithmes à pile (stack algorithms) : il est mathématiquement garanti que l'ajout de cadres de page ne peut jamais augmenter le nombre de défauts de page pour LRU. Ici, le nombre stagne à 11, ce n'est pas une anomalie.

GESTION DE LA MÉMOIRE - Exercice III : Algorithme LRU dans le pire cas

Question 1 - Méthodologie optimale

Pour une séquence répétitive cyclique où la période (4 pages : 0, 1, 2, 3) est strictement supérieure à la taille du tampon (3 cadres), LRU se trompe à chaque fois en éjectant la page qui sera demandée immédiatement après. La stratégie optimale ici est l'algorithme MRU (Most Recently Used) : il faut remplacer la page qui vient d'être utilisée le plus récemment, car dans une boucle stricte, c'est celle qui sera redemandée le plus tard.

Question 2 - Comparaison des fautes de pages (tampon de 3 pages)

• Avec LRU : La page demandée est systématiquement celle qui vient d'être évincée. On a donc 1 faute par accès (taux de défaut de 100%).
• Avec l'algorithme optimal (MRU) : Après le chargement initial, sur chaque cycle de 4 accès, on aura 3 succès en cache (hits) et 1 seule faute de page. On a donc en moyenne 1 faute pour 4 accès au régime permanent (la correction source note 1 faute pour 3 accès en observant la distance entre les défauts). En conclusion, LRU est environ 3 à 4 fois pire que l'algorithme optimal sur ce profil d'exécution.

Question 3 - Séquence de 5 pages {0,1,2,3,4...} avec un tampon de 4 pages

Si l'on passe à un cycle de 5 pages avec 4 cadres physiques, le phénomène se reproduit à l'identique :

• LRU présentera toujours un défaut pour chaque accès (1 faute par accès).
• MRU produira une seule faute de page par cycle de 5 accès (soit 1 faute pour 4 ou 5 accès selon la phase). Cela confirme que LRU a des performances catastrophiques (pire cas absolu) face à des accès séquentiels cycliques dont la période dépasse de 1 la taille du cache.

GESTION DE LA MÉMOIRE - Exercice IV : Adresses et défauts de page

Note : La table des pages n'a pas été numérisée dans le document source, mais les réponses fournies par la correction permettent de la déduire.

Question 1 - Liste des adresses provoquant un défaut de page

La taille d'une page est de 1024 mots (adresses). La correction source indique que les pages virtuelles absentes de la mémoire physique sont les pages 2, 3, 5 et 7. Voici les plages d'adresses virtuelles correspondantes qui provoqueront un défaut de page :

• Page 2 : adresses de 2048 à 3071
• Page 3 : adresses de 3072 à 4095
• Page 5 : adresses de 5120 à 6143 (Attention : la correction source indique par erreur 3072 à 4095 deux fois. Le calcul correct est 5 × 1024 = 5120).
• Page 7 : adresses de 7168 à 8191

Question 2 - Adresses physiques

L'adresse physique se calcule ainsi : (Taille de la page × numéro de cadre physique) + Déplacement. Le déplacement est le reste de la division de l'adresse virtuelle par 1024.

• 3727 : Appartient à la page 3 (3727 / 1024 = 3). La page 3 est absente. -> Défaut de page.
• 7425 : Appartient à la page 7 (7425 / 1024 = 7). La page 7 est absente. -> Défaut de page.

Pour les adresses 0, 1023, 1024, et 4196, elles appartiennent aux pages virtuelles présentes. Cependant, la table des pages (indiquant quels cadres physiques leur sont attribués) étant absente du document, le calcul exact de l'adresse physique finale est impossible.

Examen janvier 2012 - Questions de cours

Question 1.1 - Dispositifs matériels de protection

Les deux dispositifs matériels vitaux pour le système d'exploitation sont :

1. L'unité de gestion de la mémoire (MMU) : Elle traduit les adresses virtuelles en adresses physiques et vérifie les droits d'accès, empêchant un processus d'écrire ou de lire dans une zone mémoire qui ne lui appartient pas.
2. Les modes d'exécution (Kernel / User) : Maintenus par le processeur, ils empêchent les processus utilisateurs d'exécuter des instructions privilégiées (comme modifier les tables de pages ou interagir directement avec le matériel) ; ces opérations nécessitent un appel système.

Question 1.2 - Différences de concepts

1. Segmentation vs Pagination : Ce sont deux méthodes de partitionnement de l'espace d'adressage. La segmentation a un sens logique pour le programmeur (elle sépare le code, la pile, les données) et manipule des blocs de taille variable. La pagination divise la mémoire de façon transparente et purement physique, en blocs (pages et cadres) de taille fixe.
2. Fragmentation interne vs externe : La fragmentation interne survient lorsqu'un bloc alloué (comme une page de 4 Ko) est plus grand que la donnée qu'il contient (l'espace résiduel est perdu). La fragmentation externe survient (surtout en segmentation) lorsque l'espace libre total est suffisant pour satisfaire une requête, mais est morcelé en plusieurs petits blocs non contigus, rendant l'allocation impossible.
3. Évitement (Avoidance) vs Prévention (Prevention) d'interblocage :
   • Correction selon l'énoncé : L'évitement garantit l'absence d'interblocage par des restrictions, tandis que la prévention vérifie si l'état suivant est sécurisé.
   • Note pédagogique : Les définitions fournies par la correction source sont inversées par rapport à la littérature standard des systèmes d'exploitation. En réalité, c'est la Prévention qui brise structurellement l'une des 4 conditions de Coffman (les restrictions), et c'est l'Évitement qui vérifie dynamiquement à chaque requête si l'état d'allocation résultant est sûr (ex: Algorithme du Banquier de Dijkstra). Pensez à vérifier la convention utilisée par votre professeur.
4. Ordonnancement préemptif vs non préemptif : En mode préemptif, le système d'exploitation peut réquisitionner de force le processeur à un processus en cours (via l'horloge) pour l'allouer à un autre. En mode non préemptif, le processus conserve le processeur jusqu'à ce qu'il se bloque (E/S) ou se termine de lui-même.

Question 1.3 - Moyens de synchronisation multithread

Quatre moyens classiques sont :

1. L'attente de terminaison : join (ex: pthread_join())
2. Les verrous d'exclusion mutuelle : Mutex
3. Les sémaphores
4. Les variables conditions (Condition variables)

Question 2.1 - Gestion mémoire virtuelle à pagination

1. Défaut de page : Il se produit lorsque le bit de validité/présence dans l'entrée de la table des pages vaut 0, signifiant que la page virtuelle demandée ne réside pas en mémoire physique.
2. Réécriture sur le swap : Elle est nécessaire si le bit de modification (dirty bit) vaut 1, ce qui indique que le contenu de la page a été modifié depuis son chargement initial depuis le disque.
3. Coût en E/S : Dans le meilleur des cas, la page évincée n'était pas modifiée (1 E/S pour lire la nouvelle page). Dans le pire des cas, la page évincée a été modifiée (2 E/S : une pour écrire l'ancienne page sur le disque, une pour lire la nouvelle).

Question 2.2 - Graphe d'allocation de ressources

Il n'apparaît pas d'interblocage dans ce système. En analysant le graphe, on constate que P2 et P4 ne sont pas bloqués par une attente circulaire. Ils peuvent donc terminer leur exécution et libérer leurs instances des ressources R1 et R2. Ces instances libérées permettront alors à P1 et P3 de satisfaire leurs demandes, de s'exécuter et de terminer à leur tour. Le graphe se réduira entièrement.

SYNCHRONISATION & CONCURRENCE

Problème 1 - Le coiffeur endormi

Voici le code complété en C pour la solution du coiffeur endormi, basé sur la correction fournie.

Note pédagogique : Dans le bloc else du processus client d'origine, le document source contenait l'instruction down(&mutex) ; /*shop is full*/. C'est une erreur classique : si le salon est plein, le client doit relâcher le verrou (mutex) avant de partir pour ne pas bloquer le système entier. La correction ci-dessous utilise up(&mutex) à la place pour garantir un fonctionnement sans interblocage.

#define CHAIRS 5
typedef int semaphore;

// Initialisation des sémaphores
semaphore customers = 0;
semaphore barbers = 0;
semaphore mutex = 1;
int waiting = 0;

void barber(void) {
    while(1) {
        down(&customers);      /* go to sleep if # of customers is 0 */
        down(&mutex);          /* acquire access to 'waiting' */
        waiting = waiting - 1; /* decrement count of waiting customers */
        up(&barbers);          /* one barber is now ready to cut hair */
        up(&mutex);            /* release 'waiting' */
        cut_hair();            /* cut hair (outside critical region) */
    }
}

void customer(void) {
    down(&mutex);              /* enter critical region */
    if (waiting < CHAIRS) {    /* if there are free chairs */
        waiting = waiting + 1; /* increment count of waiting customers */
        up(&customers);        /* wake up barber if necessary */
        up(&mutex);            /* release access to 'waiting' */
        down(&barbers);        /* go to sleep if barber is busy */
        get_haircut();         /* be seated and be serviced */
    } else {
        up(&mutex);            /* CORRECTIF : shop is full, release mutex and leave */
    }
}

Problème 2 - Rendez-vous

Note : Le document source ne fournit pas le code de correction pour cet exercice. En tant qu'assistant, voici le principe général d'une barrière de synchronisation (rendez-vous) avec sémaphores, pour vous aider à réviser.

Il faut un mutex (initialisé à 1) pour protéger le compteur d'arrivées, et un sémaphore barriere (initialisé à 0) pour bloquer les processus arrivés tôt. Le code de chaque processus i ressemble à ceci :

down(&mutex);
cpt = cpt + 1;
if (cpt == N) {
    // Le dernier arrivé libère tout le monde
    for (int j = 0; j < N; j++) {
        up(&barriere);
    }
}
up(&mutex);

down(&barriere);
// Travaux de l'assemblée

Gestion des processus/threads

Exercice I - Vrai ou Faux

1. Un processus est une entité produite après compilation : NON. La compilation produit un programme (un exécutable sur le disque, entité passive). Un processus est l'image de ce programme en cours d'exécution en mémoire (entité active).
2. Un processus est une entité produite après chargement d’un binaire en mémoire : OUI. Une fois le code chargé en mémoire centrale et les ressources allouées par l'OS, un processus est bien instancié.
3. Le pseudo-parallélisme impose aux processus de se connaître mutuellement : NON. L'ordonnancement est totalement transparent pour eux. C'est le système d'exploitation qui effectue les commutations de contexte et suspend/reprend les processus.

Exercice II - Création de 10 processus fils

Note : Le code de la correction n'apparaît pas dans le document source. Voici la solution standard en C correspondant à la demande, pour votre révision.

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main() {
    for (int i = 0; i < 10; i++) {
        if (fork() == 0) { // Code du processus fils
            for (int j = 0; j < 10; j++) {
                printf("Numéro d'ordre : %d | PID : %d\n", j, getpid());
            }
            return 0; // Le fils termine pour ne pas cloner à son tour
        }
    }
    // Le père attend la fin de ses 10 fils
    for (int i = 0; i < 10; i++) wait(NULL);
    return 0;
}

Exercice III - Analyse d'arbre généalogique

Note : Le code C d'origine de cet exercice est absent du document source, ce qui empêche de dessiner l'arbre généalogique. Néanmoins, les réponses de la correction permettent de déduire le comportement du programme.

1. Affichage à l'écran : Le programme produira 5 lignes de la forme Mon nom est <c> j'ai dormi n secondes avec c valant A, B, C, D, E et n un nombre aléatoire entre 0 et 3. L'ordre de ces affichages est non déterministe et dépendra de l'ordonnancement du système d'exploitation.
2. Déplacement de l'initialisation (srand) de la ligne 10 à la ligne 7 : D'après la correction, la fonction srand(getpid()) serait alors appelée une seule fois par le processus ancêtre avant les fork(). Par conséquent, tous les processus fils hériteraient de la même graine aléatoire initiale, et feraient le même tirage rand() pour la variable n. Ils dormiraient donc exactement le même nombre de secondes.
3. Affichage en ordre inverse : Pour forcer les processus à s'afficher dans un ordre précis imposé par l'arbre de création, la correction indique qu'il faut ajouter l'instruction wait(NULL); à la ligne 12. Cela force le processus parent courant à attendre la mort de son ou ses propres enfants avant d'exécuter sa routine d'affichage.

Exercice IV - Multithreading

1. Multithreading vs Multiprogrammation :
   • La multiprogrammation est un concept système visant à charger plusieurs processus différents en mémoire pour optimiser l'utilisation du processeur (pendant que l'un fait des E/S, l'autre calcule).
   • Le multithreading est la capacité pour un unique processus de posséder plusieurs fils d'exécution (threads) s'exécutant de manière concurrente en partageant le même espace d'adressage (même code, mêmes données globales).
2. Partage de données en mémoire : Processus ou Threads ?
   • Il faut privilégier les threads. Au sein d'un même processus, les threads partagent nativement le segment de données et le tas (heap). De plus, la création d'un thread et surtout la commutation de contexte entre deux threads d'un même processus sont nettement moins coûteuses (en temps CPU et mémoire) qu'entre deux processus distincts.

Méthode

Face à ce type de sujet d'examen d'architecture système :

1. Faites très attention aux unités : La plupart des erreurs sur la pagination viennent d'une confusion entre bits, octets, et Ko. Prenez toujours le réflexe de convertir les puissances de 2 (ex: 2^10 = 1024, 2^20 = 1 Mo). Un adressage sur $n$ bits donne $2^n$ possibilités.
2. Maîtrisez les bits de statut : En mémoire virtuelle, sachez associer mécaniquement chaque bit de la table des pages à sa conséquence (bit de validité = défaut de page ; bit de modification = réécriture swap ; bit de référence = utilisé par l'algorithme LRU/horloge).
3. Algorithmes de remplacement : Ne faites pas les traces de cache de tête. Dessinez un tableau clair pour chaque page physique au cours du temps, comme dans la correction. Rappelez-vous que la file (PAPS) sort la page entrée il y a le plus longtemps, tandis que LRU sort la page utilisée il y a le plus longtemps.
4. Concurrence en C : Devant un code de sémaphores, vérifiez toujours qu'un down(mutex) est impérativement suivi de son up(mutex) dans toutes les branches d'exécution, y compris dans les conditions else ou les cas d'erreur. C'est la source numéro un des interblocages en examen.