Gestion de la MC– Exercices corrigés

Ce document présente une série d'exercices corrigés en gestion de la mémoire centrale (MC) dans les systèmes informatiques. Ces exercices évaluent la compréhension des mécanismes de pagination, segmentation, gestion des défauts de pages, algorithmes de remplacement, et organisation de la mémoire physique et virtuelle.

Exercice 1

On considère un système avec 4 cases mémoire et une taille de page de 100. Un programme P fait successivement référence aux adresses suivantes : 100, 210, 355, 120, 420, 110, 200, 550, 139, 201, 395, 404, 505.

1) Donner la chaîne de références aux pages correspondant aux adresses.

Chaque adresse est divisée par la taille de la page (100) pour obtenir le numéro de page :

• 100 / 100 = 1
• 210 / 100 = 2
• 355 / 100 = 3
• 120 / 100 = 1
• 420 / 100 = 4
• 110 / 100 = 1
• 200 / 100 = 2
• 550 / 100 = 5
• 139 / 100 = 1
• 201 / 100 = 2
• 395 / 100 = 3
• 404 / 100 = 4
• 505 / 100 = 5

La chaîne de références aux pages est donc :

1, 2, 3, 1, 4, 1, 2, 5, 1, 2, 3, 4, 5

2) Calculer le nombre de défauts de pages en appliquant la stratégie MFU (Most Frequently Used).

La stratégie MFU remplace la page la plus fréquemment utilisée. On simule la gestion des 4 cases mémoire :

• Chargement initial des pages 1, 2, 3, 4 avec défauts de pages (4 défauts)
• Ensuite, les références suivantes sont traitées en remplaçant la page la plus utilisée.

Le tableau de simulation montre que le nombre total de défauts de pages est :

7 défauts de pages

3) Proposer une méthode donnant un nombre minimum (optimal) de défauts de pages et calculer ce nombre.

La méthode optimale consiste à remplacer la page qui ne sera pas utilisée dans un futur immédiat. En simulant cette méthode :

Le nombre total de défauts de pages est :

6 défauts de pages

Exercice 2

A) Calculs liés à la mémoire virtuelle et pagination

Considérons une mémoire physique de 32 Mo, une taille de bloc de 512 octets, et un processus occupant 856 Ko en mémoire logique.

1) Calculer le nombre de pages dans l’espace d’adressage logique et le nombre de cases dans l’espace d’adressage physique.

• Nombre de pages = 856 Ko / 512 = 1712 pages
• Nombre de cases = 32 Mo / 512 = 65536 cases

2) Montrer les formats des adresses logiques et physiques, avec le nombre de bits pour les déplacements, pages et cases.

• Adresse logique : 11 bits pour le numéro de page (car 2^11 = 2048 > 1712), 9 bits pour le déplacement (512 = 2^9)
• Adresse physique : 16 bits pour le numéro de case (2^16 = 65536), 9 bits pour le déplacement

3) Pour l’adresse logique 11301, spécifier son emplacement en mémoire physique sachant que la page contenant cette adresse est dans la case 15240.

• Adresse de base de la case 15240 = 15240 × 512 = 7 802 880
• Déplacement dans la page = 11301 mod 512 = 37
• Adresse physique = 7 802 880 + 37 = 7 802 917

L’adresse physique correspondante est 7 802 917.

4) Est-il possible que le nombre de pages requis par un processus soit supérieur au nombre de cases disponibles en mémoire physique ?

Oui, car la mémoire virtuelle permet de ne charger en mémoire physique que les pages nécessaires à la localisation de référence du processus. Le système d’exploitation n’alloue souvent qu’un nombre de cases inférieur au nombre total de pages du processus, même si la mémoire physique est disponible.

B) Séquence de référence de pages et algorithme FIFO

Séquence : 0,1,2,1,2,1,2,1,2,3,4,5,6,5,6,7 avec 3 cases mémoire.

1) Représenter l’allocation en mémoire physique selon FIFO.

Simulation FIFO :

• Chargement initial des pages 0, 1, 2 (3 défauts)
• Remplacement selon ordre d’arrivée pour les suivantes
• Au total, 8 défauts de pages sont comptabilisés

2) Estimer le taux de défauts de pages.

Le taux est de 8 défauts sur 16 références, soit :

50%

Exercice 3

On considère un système avec pagination et segmentation, pages de 1 Ko, mémoire physique de 32 Mo, mémoire virtuelle de 512 Mo, segments contigus de 1 à 128 pages, et algorithme LRU.

1) Calculer le format d’une adresse virtuelle et d’une adresse physique, en spécifiant les bits pour chaque champ.

Le document ne donne pas explicitement les bits, mais on peut déduire :

• Taille d’une page = 1 Ko = 2^10 octets → 10 bits pour le déplacement
• Segments entre 1 et 128 pages → 7 bits pour numéro de page dans le segment (2^7=128)
• Le nombre de bits pour le segment dépend du nombre total de segments (non précisé)

Le format exact n’est pas donné dans le document, donc on s’en tient à ces observations.

2) Calculer l’adresse en mémoire principale d’une donnée à l’adresse virtuelle 10728, sachant que le segment de données commence à 9216 et est chargé dans les cadres 4096, 4097, 4098.

• Page contenant l’adresse = (10728 - 9216) / 1024 = 1
• Déplacement dans la page = 10728 - 9216 - 1024 = 488
• Adresse du cadre 4097 = 4097 × 1024 = 4 195 328
• Adresse physique = 4 195 328 + 488 = 4 195 816

L’adresse physique est 4 195 816.

3) Séquence de références de pages de code R = {0, 1, 0, 1, 2, 3, 4, 2, 3, 4, 5, 6, 7, 8} avec allocation initiale de 4 cadres pour le code et 2 pour les données.

a) Représenter l’état d’occupation de la mémoire principale à chaque instant où une nouvelle page est chargée.

Le chargement est à la demande, sans cadres supplémentaires alloués. On note les défauts de pages et l’état des cadres à chaque instant :

• Chargement initial des pages 0, 1, 2, 3 (4 défauts)
• Pages suivantes chargées selon LRU, provoquant des remplacements

b) Calculer le nombre de défauts de pages générés par l’algorithme LRU. Ce nombre est-il optimal ?

Nombre total de défauts : 9 fautes pour le code + 3 fautes pour les données = 12 fautes sur 17 références, soit un taux de 70,5%.

Le nombre optimal de défauts est égal à la taille du processus (12 pages), donc l’algorithme LRU est optimal dans ce cas.

Nombre de défauts de pages = 12, ce qui est optimal.

Exercice 4

Une firme concurrente d’Apple lance un appareil avec 64 Mo de mémoire principale et 80 Go de mémoire secondaire, pouvant exécuter 3 processus en plus du système d’exploitation (SE) : Afficheur (A), Transfert (T), Son (S).

1) Proposer une organisation de la mémoire principale satisfaisant rapidité d’accès et minimisation de la fragmentation externe.

Les partitions fixes sont souvent inadaptées aux processus de tailles variables, mais ici, avec seulement 3 processus aux tailles stables, une mémoire à partitions fixes sans file d’attente est efficace.

• 16 Mo réservés au SE
• 500 Ko pour l’afficheur (A)
• 10,5 Mo pour le processus Son (S) (500 Ko initiaux + espace supplémentaire contigu entre 4 et 10 Mo)
• 37 Mo pour le transfert (T), avec tampons dynamiques

Cette organisation permet d’éviter la fragmentation externe et garantit que chaque processus a sa place dédiée, évitant les conflits et assurant la rapidité d’accès.

2) Quel type d’adressage proposer ? Avantages et dispositifs pour assurer la protection.

Un adressage relatif est recommandé, utilisant un registre de base et un registre limite pour chaque processus. Ce dispositif permet :

• La conversion d’adresses relatives en adresses physiques
• La protection mémoire en empêchant un processus d’accéder à la mémoire d’un autre ou au SE
• Une gestion simple et efficace des espaces mémoire dédiés

Exercice 5

Considérons un système avec adressage virtuel 32 bits, taille de page 4 Ko, mémoire physique 1 Mo.

a) Quelles sont les données manquantes pour traduire l’adresse virtuelle 32 bits AE854C9C en adresse physique ?

Il manque la table des segments qui indique la table de pages associée à chaque segment, ainsi que les tables de pages elles-mêmes pour obtenir le cadre correspondant. Sans ces informations, la traduction ne peut être effectuée.

Si ces informations étaient disponibles, quelles sont les étapes pour la translation ?

1. Identifier le segment à partir de l’adresse virtuelle
2. Consulter la table des segments pour obtenir la table des pages associée
3. Identifier la page dans la table des pages
4. Obtenir le cadre (case) correspondant
5. Calculer l’adresse physique en combinant le numéro de cadre et le déplacement

b) Pagination à deux niveaux avec entrées de 4 octets

b.1) Combien de pages sont nécessaires pour contenir toutes les tables de pages d’un processus utilisant tout l’espace adressable ?

Chaque table de pages contient 2^10 entrées (1024). Il y a 2^10 tables de pages de second niveau et une table de premier niveau. Donc :

2^10 + 1 = 1025 pages nécessaires pour toutes les tables de pages.

b.2) Pour un processus nécessitant 22 Mo, avec code entre 2 Mo et 6 Mo-1, données entre 12 Mo et 21 Mo-1, combien de pages de niveau 2 seront chargées ?

• Code : 4 Mo → 2 pages de niveau 2
• Données : 9 Mo → 3 pages de niveau 2

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

c) En pagination pure, avec bits 12 à 31 pour numéro de page, combien d’entrées la table de pages inversée contient-elle ?

Nombre de cadres = 2^20 (car 1 Mo mémoire physique / 4 Ko par page = 2^20 / 2^12 = 2^8 = 256 cadres). Le document indique :

La table de pages inversée contient 2^20 entrées.

Exercice 6

Un système avec pagination à la demande dispose de 4 cases mémoire occupées. La table suivante donne pour chaque case : temps de chargement, temps du dernier accès, bits R (référencé), M (modifié), P (présence).

Case	t chargement	t dernier accès	R	M	P
0	126	270	0	0	1
1	230	255	0	1	1
2	110	260	1	1	1
3	180	275	1	1	1

1) Quelle page sera remplacée en cas de défaut de page selon :

a) Algorithme LRU

LRU remplace la page la moins récemment utilisée, c’est-à-dire celle avec le plus ancien temps de dernier accès. Ici, c’est la page dans la case 1 (temps 255).

La page dans la case 1 sera remplacée.

b) Algorithme FIFO

FIFO remplace la page la plus ancienne en mémoire, c’est-à-dire celle avec le plus ancien temps de chargement. Ici, c’est la page dans la case 2 (temps 110).

La page dans la case 2 sera remplacée.

2) Calcul du temps d’accès moyen

Le taux d’accès rapide est 65%. Parmi les 35% défauts de page, 70% nécessitent 20 ms, 30% nécessitent 10 ms.

Calcul :

t accès moyen = 0,65 × 0,0001 + 0,35 × (0,7 × 20 + 0,3 × 10) = 5,950065 ms

3) Données sur un système segmenté paginé

Segments S1 (16 Ko), S2 (8 Ko), S3 (4 Ko). Pages 2 et 3 du S1, page 2 du S2, page 1 du S3 sont chargées dans les cases 2, 0, 9, 12 respectivement.

Pour une donnée à l’adresse décimale 8212 :

• a) Segment : S1 (car 8212 < 16 Ko)
• b) Numéro de page dans le segment : 8212 / 4096 = 2 (page 3 en comptant à partir de 0)
• c) Déplacement dans la page : 8212 mod 4096 = 20
• d) Numéro de case : case 0 (page 3 du segment S1 est en case 0)
• e) Déplacement dans la case : 20
• f) Adresse physique : case 0 × 4096 + 20 = 0 + 20 = 20 (sur 16 bits)

Exercice 7

I) Programme avec code de 1024 octets et vecteur de 1000 caractères, pagination avec pages de 512 octets, mémoire réelle 1 Mo, adresses mémoire sur 24 bits.

a) Calculs

1. Taille de l’espace logique d’adressage : 2^24 = 16 Mo
2. Nombre de bits pour le déplacement : log2(512) = 9 bits
3. Nombre de bits pour le numéro de page virtuelle : 24 - 9 = 15 bits
4. Nombre de bits pour une adresse réelle : 20 bits (car 1 Mo = 2^20)
5. Nombre de bits pour le numéro de page réelle (case) : 20 - 9 = 11 bits
6. Nombre d’entrées dans la table des pages : 2^15 = 32 768

b) Le chargement engendre-t-il une fragmentation interne ?

Oui, car le programme occupe 3024 octets (1024 code + 2000 données). Le nombre de pages nécessaires est 6 (3024 / 512 = 5,91 arrondi à 6). La dernière page contient 48 octets libres, ce qui provoque une fragmentation interne.

II) Format d’une adresse virtuelle 32 bits avec pages de 256 octets et table des pages à trois niveaux

Chaque niveau utilise 8 bits (256 entrées) :

Format : PT1 (8 bits) | PT2 (8 bits) | PT3 (8 bits) | Offset (8 bits)

Nombre de tables :

• 1 table de premier niveau
• 256 tables de second niveau
• 256 × 256 = 65 536 tables de troisième niveau

Nombre d’entrées par table : 256

III) Anomalie de Belady et algorithme FIFO

a) Montrer l’anomalie de Belady avec FIFO pour m=3 puis m=4 sur la séquence ω = {1,2,3,4,1,2,5,1,2,3,4,5}

Avec 3 cadres, FIFO génère 9 défauts de pages.

Avec 4 cadres, FIFO génère 10 défauts de pages.

Le nombre de défauts augmente en augmentant le nombre de cadres, illustrant l’anomalie de Belady.

b) Montrer que FIFO n’est pas un algorithme à pile

La propriété d’inclusion M(m,r) ⊆ M(m+1,r) n’est pas vérifiée aux index 7, 8 et 11 du vecteur de références, ce qui prouve que FIFO n’est pas un algorithme à pile.

Méthode

Ce sujet récompense la maîtrise des concepts fondamentaux de gestion de mémoire : conversion d’adresses, calculs de pages et cadres, simulation d’algorithmes de remplacement (MFU, FIFO, LRU), et organisation mémoire adaptée aux contraintes des processus.

Il est essentiel de suivre rigoureusement les définitions et conventions données, notamment pour les tailles de pages, formats d’adresses, et algorithmes spécifiques. Les erreurs fréquentes concernent la mauvaise conversion d’adresses, le calcul incorrect des nombres de pages ou cadres, et la confusion entre algorithmes de remplacement.

La présentation claire des étapes de calcul et la justification des choix sont indispensables pour obtenir une bonne note. Enfin, la compréhension des notions d’anomalie de Belady et des propriétés des algorithmes à pile est cruciale pour les questions avancées.