Systèmes d'Exploitation II - 2

Ce travail dirigé porte sur la gestion de la mémoire dans les systèmes d'exploitation, en particulier la pagination et la segmentation paginée. Il permet d'aborder la traduction d'adresses virtuelles en adresses physiques dans différents systèmes de pagination, avec des tables de pages à un ou plusieurs niveaux. Pour réaliser ce TP, il est nécessaire de comprendre les concepts de pagination, segmentation, tables de pages, ainsi que la représentation binaire des adresses.

Objectifs

• Comprendre la structure des adresses virtuelles dans un système paginé.
• Effectuer la traduction d'adresses virtuelles en adresses physiques.
• Analyser les systèmes de pagination à plusieurs niveaux.
• Calculer la taille des espaces virtuels et physiques selon les paramètres du système.
• Appréhender la gestion de la mémoire dans un système utilisant la segmentation paginée.

Prérequis et installation

• Connaissances de base en gestion de mémoire dans les systèmes d'exploitation.
• Compréhension des notions de pagination, segmentation, tables de pages et traduction d'adresses.
• Maîtrise de la représentation binaire des nombres et des opérations sur les bits.
• Pas de matériel ou logiciel spécifique requis, travail théorique et calculs manuels.

Gestion de la mémoire par pagination pure avec tables de pages à un niveau

On considère un système monoprocesseur avec pagination pure et tables de pages à un niveau. La mémoire physique est composée de 4 cadres (frames) de 4 Ko chacun. L'adresse virtuelle est codée sur 16 bits. Deux processus P1 et P2 arrivent successivement, composés respectivement de 7 et 5 pages. Le système charge dans l'ordre les pages 0 et 1 de P1 dans les cadres 1 et 2, puis la page 1 de P2 dans le cadre 3, avant de commencer l'exécution des deux processus.

(a) Structure d'une adresse virtuelle

La structure d'une adresse virtuelle doit permettre d'identifier la page virtuelle et le décalage (offset) à l'intérieur de la page. Puisque la taille d'une page est de 4 Ko, soit 2^12 octets, les 12 bits de poids faible de l'adresse virtuelle correspondent au décalage dans la page. Les 4 bits restants (16 - 12) correspondent au numéro de page virtuelle.

(b) Traduction d'une adresse virtuelle pour P1

Adresse virtuelle donnée : 0001 0011 0111 1000 (binaire)

Pour P1, les pages 0 et 1 sont chargées dans les cadres 1 et 2 respectivement. Il faut extraire le numéro de page virtuelle et le décalage :

• Numéro de page virtuelle : bits 15 à 12 → 0001 (page 1)
• Décalage : bits 11 à 0 → 0011 0111 1000 (0x378 en hexadécimal)

Le cadre physique correspondant à la page 1 de P1 est le cadre 2.

L'adresse physique est donc : cadre 2 * taille cadre + décalage = (2 * 4 Ko) + 0x378 = 8 Ko + 888 (en décimal) = 8 888 octets.

(c) Traduction d'une adresse virtuelle pour P2

Pour P2, seule la page 1 est chargée dans le cadre 3. En reprenant la même adresse virtuelle :

• Numéro de page virtuelle : 0001 (page 1)
• Décalage : 0x378

L'adresse physique est donc : cadre 3 * 4 Ko + 0x378 = 12 Ko + 888 = 12 888 octets.

Pagination avec tables de pages à 4 niveaux et pages de 4096 octets

On considère un système avec tables de pages à 4 niveaux. Chaque adresse virtuelle est codée sur 48 bits répartis en 5 champs : 1, 2, 3, 4 et d, où d est le décalage dans la page.

(a) Taille du champ décalage (offset)

La taille d'une page est de 4096 octets, soit 2^12 octets. Le champ d (offset) doit donc être codé sur 12 bits.

(b) Influence de la répartition des bits sur le nombre maximal de pages

Le nombre maximal de pages dans l'espace virtuel dépend du nombre total de bits alloués aux numéros de page (champs 1 à 4). La répartition des bits entre ces champs n'affecte pas le nombre total de pages, car celui-ci est déterminé par la somme des bits de ces champs. Ainsi, le nombre maximal de pages est 2^(48 - 12) = 2^36 pages, indépendamment de la répartition entre les différents niveaux.

Pagination à trois niveaux avec adresses sur 32 bits et pages de 2 Ko

Considérons un système avec pagination à trois niveaux, adresses virtuelles et physiques codées sur 32 bits, taille de page 2 Ko (2^11 octets). Chaque table de pages a une taille de 512 octets, chaque entrée occupant 4 octets. Le premier octet de chaque entrée est réservé aux bits de contrôle (présence, référence, modification, protection, etc.).

(a) Taille maximale de l'espace virtuel en nombre de pages

La taille d'une page est 2 Ko = 2^11 octets. L'adresse virtuelle est sur 32 bits, donc le nombre total d'adresses est 2^32. Le nombre maximal de pages est donc :

Nombre de pages = 2^32 / 2^11 = 2^(32 - 11) = 2^21 pages.

(b) Nombre maximal de tables de pages

Chaque table de pages fait 512 octets, avec des entrées de 4 octets, donc chaque table contient :

512 / 4 = 128 entrées.

Le nombre maximal de tables de pages dépend du nombre de pages et de la structure à trois niveaux. Le calcul précis nécessite la connaissance du nombre d'entrées par table et la hiérarchie, mais ici, on sait que chaque table peut référencer 128 pages ou tables de niveau inférieur.

(c) Format d'une adresse virtuelle

L'adresse virtuelle est divisée en plusieurs champs correspondant aux indices dans les tables de pages de chaque niveau, plus le décalage dans la page. La taille de chaque champ est déterminée par le nombre d'entrées par table (128 = 2^7), donc chaque champ d'indice fait 7 bits. Le format est :

• 7 bits pour le niveau 1
• 7 bits pour le niveau 2
• 7 bits pour le niveau 3
• 11 bits pour le décalage dans la page

Total : 7 + 7 + 7 + 11 = 32 bits.

Système de gestion de mémoire avec segmentation paginée

On considère un système avec :

• Adressage virtuel sur 32 bits, dont 14 bits pour le numéro de segment et 6 bits pour le numéro de page.
• Taille de page de 4 Ko.
• Mémoire physique de 1 Mo.

(a) Taille du plus grand segment

Le numéro de segment est codé sur 14 bits, donc un segment peut contenir :

2^6 = 64 pages (car 6 bits pour le numéro de page)

Chaque page fait 4 Ko, donc la taille maximale d'un segment est :

64 pages * 4 Ko = 256 Ko.

(b) Données manquantes pour la traduction de l'adresse virtuelle 0xAE854C9C

Pour traduire cette adresse virtuelle en adresse physique, il manque :

• La table des segments pour identifier le segment correspondant au numéro de segment.
• La table de pages associée à ce segment pour localiser la page physique.
• Les informations sur la mémoire physique (allocation des cadres).

Les étapes de traduction seraient :

1. Extraire le numéro de segment (bits 31 à 18) et localiser l'entrée correspondante dans la table des segments.
2. Extraire le numéro de page (bits 17 à 12) et localiser l'entrée correspondante dans la table de pages du segment.
3. Ajouter le décalage (bits 11 à 0) pour obtenir l'adresse physique finale.

(c) Pagination à deux niveaux avec structure d'adresse virtuelle

La structure de l'adresse virtuelle est :

#page niveau 1 (10 bits) | #page niveau 2 (10 bits) | décalage page (12 bits)

Si un processus utilise tout l'espace adressable, le nombre total de pages nécessaires pour contenir toutes les tables de pages est :

Nombre de pages = 2^10 (niveau 1) + 2^10 * 2^10 (niveau 2) = 1024 + 1 048 576 = 1 049 600 pages.

Ce calcul inclut :

• 1024 pages pour les tables de premier niveau.
• 1 048 576 pages pour les tables de second niveau.

(d) Chargement des tables de pages pour un second processus

Un second processus nécessite 22 Mo pour s'exécuter, répartis ainsi :

• Code : adresses virtuelles de 2 Mo à 6 Mo - 1
• Données : adresses virtuelles de 12 Mo à 21 Mo - 1

Pour charger les tables de pages associées à ces deux parties, il faut calculer le nombre de pages de niveau 2 chargées en mémoire centrale.

Calcul :

• Code : 6 Mo - 2 Mo = 4 Mo → nombre de pages = 4 Mo / 4 Ko = 1024 pages
• Données : 21 Mo - 12 Mo = 9 Mo → nombre de pages = 9 Mo / 4 Ko = 2304 pages

Le nombre total de pages de niveau 2 chargées est donc :

1024 + 2304 = 3328 pages de niveau 2.

Résultats attendus

• Compréhension claire de la structure des adresses virtuelles et physiques dans divers systèmes de pagination.
• Capacité à traduire une adresse virtuelle en adresse physique selon la configuration donnée.
• Calcul correct du nombre maximal de pages et de tables de pages nécessaires.
• Identification des données manquantes pour la traduction d'adresses dans un système segmenté paginé.
• Estimation précise du nombre de pages de tables de pages à charger pour un processus donné.

Pièges courants

• Confondre la taille du décalage (offset) avec la taille du numéro de page dans l'adresse virtuelle.
• Oublier que la taille d'une page détermine le nombre de bits du décalage.
• Ne pas prendre en compte la hiérarchie des tables de pages dans les systèmes multi-niveaux.
• Ignorer les bits de contrôle dans les entrées des tables de pages, ce qui peut fausser le calcul du nombre d'entrées.
• Ne pas vérifier que les adresses virtuelles correspondent bien aux pages chargées en mémoire physique.
• Omettre de calculer correctement le nombre de pages nécessaires pour contenir toutes les tables de pages dans un système à plusieurs niveaux.