Gestion de la mémoire

Ce document présente une série d'exercices sur la gestion de la mémoire en systèmes informatiques, issus d’un examen universitaire. Les exercices évaluent des compétences en allocation mémoire, traduction d’adresses, pagination, segmentation, algorithmes de remplacement de pages, fragmentation, ordonnancement, et gestion de la mémoire virtuelle.

Exercice 1 : Allocation d’espace en mémoire

On demande d’analyser l’allocation mémoire de 5 processus arrivant à différents instants, avec segments code, données et pile, et une mémoire physique de 16 MO découpée en cadres de 4 KO. L’allocation est contiguë par segment, en First Fit, et l’ordonnancement des chargements suit PAPS (Premier Arrivé, Premier Servi).

Question 1.1 : Diagrammes d’évolution mémoire et file d’attente

Les processus sont :

• A (arrivée 0) : 5 MO + 5 MO + 1 MO, durée 8 ms
• B (arrivée 2) : 4 MO + 1 MO + 2 MO, durée 10 ms
• C (arrivée 4) : 1 MO + 1 MO + 1 MO, durée 13 ms
• D (arrivée 10) : 2 MO + 1 MO + 2 MO, durée 15 ms
• E (arrivée 11) : 6 MO + 2 MO + 1 MO, durée 6 ms

La mémoire physique fait 16 MO, soit 16 384 KO, divisés en cadres de 4 KO, donc 4096 cadres au total. Chaque segment est alloué dans une zone contiguë de cadres égale à son nombre de pages (taille segment / 4 KO).

Étapes principales :

1. t=0 : Arrivée A (11 MO total). Mémoire vide, allocation possible. A chargé.
2. t=2 : Arrivée B (7 MO total). Mémoire restante : 16 - 11 = 5 MO. B demande 7 MO, insuffisant. B en attente.
3. t=4 : Arrivée C (3 MO total). Mémoire restante 5 MO, C demande 3 MO, allocation possible. C chargé.
4. t=8 : Fin A. Libération 11 MO. Mémoire libre : 11 + 5 - 3 = 13 MO (car C occupe 3 MO).
5. t=10 : Arrivée D (5 MO total). Mémoire libre 13 MO, allocation possible. D chargé.
6. t=11 : Arrivée E (9 MO total). Mémoire libre 8 MO (16 - 3 - 5), insuffisant. E en attente.
7. t=17 : Fin C. Libération 3 MO. Mémoire libre 11 MO.
8. t=20 : Fin B (jamais chargé, donc pas de libération).
9. t=25 : Fin D. Libération 5 MO. Mémoire libre 16 MO - 9 MO (E) = 7 MO si E chargé, sinon 16 MO.
10. t=25+ : Tentative chargement E. E demande 9 MO, mémoire libre 16 MO, allocation possible. E chargé.
11. t=31 : Fin E.

Diagramme résumé :

• 0-8 : A chargé (11 MO), mémoire restante 5 MO
• 4-17 : C chargé (3 MO), mémoire restante 2 MO
• 10-25 : D chargé (5 MO), mémoire restante -3 MO (impossible, donc D chargé après libération de A et C)
• B et E retardés jusqu’à libération suffisante

Réponse : Les processus sont chargés selon leur arrivée et disponibilité mémoire, avec file d’attente pour ceux ne pouvant être chargés immédiatement. La mémoire est fragmentée par allocation contiguë des segments.

Question 1.2 : Fragmentation interne et externe

La stratégie d’allocation est à partitions variables, avec allocation contiguë par segment. La fragmentation interne correspond à l’espace inutilisé à l’intérieur d’une partition allouée, par exemple si la taille allouée est supérieure à la taille demandée. Ici, la taille allouée est exactement égale au nombre de pages du segment, donc pas de fragmentation interne.

La fragmentation externe correspond à l’espace libre total insuffisant pour un segment, bien que la somme des fragments libres soit suffisante. Ici, comme les segments doivent être contigus, la fragmentation externe est possible : des trous libres non contigus peuvent empêcher le chargement d’un processus.

Réponse : Cette stratégie ne souffre pas de fragmentation interne mais peut souffrir de fragmentation externe.

Question 1.3 : Politique du tout ou rien

Le gestionnaire n’alloue pas d’espace si les trois segments ne peuvent pas être alloués contigus, car un segment non alloué rendrait le processus incohérent. Cela évite la fragmentation et garantit que le processus dispose de tout son espace nécessaire pour fonctionner correctement.

Réponse : La politique du tout ou rien garantit la cohérence du processus en mémoire et évite la fragmentation due à des allocations partielles.

Exercice 1 : Question 2 - Translation d’adresse

On considère un adressage logique sur 24 bits, avec :

• 2 bits pour numéro de segment (poids fort)
• 10 bits pour numéro de page
• 12 bits pour déplacement dans la page

L’adresse physique est aussi sur 24 bits :

• 12 bits de poids fort pour numéro de case (cadre)
• 12 bits pour déplacement dans la case

Question 2.1 : Nombre de cases en mémoire physique

La mémoire physique est adressée par 12 bits pour le numéro de case, donc :

Nombre de cases = 2^12 = 4096 cases.

Réponse : 4096 cases en mémoire physique.

Question 2.2 : Conversion adresse logique en adresse physique

Pour convertir une adresse logique en adresse physique :

1. Extraire le numéro de segment (2 bits), numéro de page (10 bits), et déplacement (12 bits).
2. Le segment est chargé dans une zone contiguë de cases en mémoire physique, avec un numéro de case de départ.
3. Adresse physique = (numéro de case de départ du segment + numéro de page) concaténé avec le déplacement.

Réponse : L’adresse physique est obtenue en ajoutant le numéro de page au numéro de case de départ du segment, puis en concaténant le déplacement.

Question 2.3 : Traduction d’une adresse logique donnée

Adresse logique :

01 00 0000 0010 0000 0011 0001

Interprétation :

• Segment = 01 (binaire) = 1
• Numéro de page = 0000000010 (binaire) = 2
• Déplacement = 000000110001 (binaire) = 49 (en décimal)

Segment 01 est chargé à la case numéro 3 (0000 0000 0011 en binaire).

Adresse physique :

Numéro de case = 3 + 2 = 5

Déplacement = 49

En binaire, numéro de case 5 = 0000 0000 0101

Adresse physique complète = numéro de case (12 bits) + déplacement (12 bits) :

0000 0000 0101 0000 0011 0001

Réponse : L’adresse physique correspond à la case 5 avec un déplacement de 49.

Question 2.4 : Possibilité de translation lors du chargement

La translation d’adresse ne peut pas être réalisée lors du chargement car les segments sont chargés dans des zones contiguës fixes, sans relocation dynamique. La translation est effectuée à l’exécution pour convertir les adresses logiques en adresses physiques.

Réponse : Non, la translation d’adresse ne peut pas être réalisée lors du chargement car la mémoire est allouée sans relocation dynamique.

Exercice 2 : Pagination et segmentation

Un système avec :

• Pages et cadres de 1 KO
• Mémoire physique de 32 MO
• Mémoire virtuelle de 512 MO
• Segments contigus, chaque segment entre 1 et 128 pages
• Algorithme de remplacement LRU

Question 2.1 : Format des adresses virtuelle et physique

Calcul du nombre de bits :

• Mémoire physique = 32 MO = 32 * 2^20 octets = 2^25 octets
• Taille page = 1 KO = 2^10 octets
• Nombre de cadres physiques = 2^25 / 2^10 = 2^15 cadres
• Adresse physique : bits pour numéro de cadre = 15 bits, bits pour déplacement dans la page = 10 bits
• Mémoire virtuelle = 512 MO = 2^29 octets
• Nombre de pages virtuelles = 2^29 / 2^10 = 2^19 pages
• Adresse virtuelle : 19 bits pour numéro de page, 10 bits pour déplacement

Réponse : Adresse virtuelle : 19 bits numéro de page + 10 bits déplacement. Adresse physique : 15 bits numéro de cadre + 10 bits déplacement.

Question 2.2 : Calcul d’adresse physique d’une donnée

Segments :

• Code : 9 KO (9 pages)
• Données : 3 KO (3 pages)
• Segment code commence à 0
• Segment données commence à 9216 (en octets)

Adresse virtuelle donnée : 10728

Déterminer à quel segment appartient cette adresse :

• Segment code : 0 à 9215 (9 KO)
• Segment données : 9216 à 12287 (3 KO)

10728 > 9216 donc dans segment données.

Adresse relative dans segment données = 10728 - 9216 = 1512

Le segment données est chargé dans cadres 4096, 4097, 4098 contigus.

Numéro de page dans segment données = 1512 / 1024 = 1 (car 1512 > 1024)

Déplacement dans page = 1512 % 1024 = 488

Adresse physique = cadre 4096 + page 1 = cadre 4097 + déplacement 488

Réponse : Adresse physique = cadre 4097 + déplacement 488.

Question 2.3 : Séquence de références de pages et LRU

Références de pages de code : R = {0, 1, 0, 1, 2, 3, 4, 2, 3, 4, 5, 6, 7, 8}

Opérandes répartis sur pages de données :

• Pages 0,1,2 du code réfèrent à page 0 des données
• Pages 3,4,5 réfèrent à page 1 des données
• Pages 6,7,8 réfèrent à page 2 des données

Au départ :

• 4 cadres contigus pour code à adresse X
• 2 cadres contigus pour données à adresse Y
• Chargement à la demande, pas de chargement préalable
• Pas d’allocation supplémentaire pendant l’exécution

(a) État d’occupation mémoire à chaque chargement de page

Initialement, mémoire vide. Chargement des pages selon la séquence :

1. t0 : Page 0 chargée (code)
2. t1 : Page 1 chargée (code)
3. t2 : Page 0 déjà chargée, pas de chargement
4. t3 : Page 1 déjà chargée
5. t4 : Page 2 chargée (code)
6. t5 : Page 3 chargée (code)
7. t6 : Page 4 chargée (code)
8. t7 : Page 2 déjà chargée
9. t8 : Page 3 déjà chargée
10. t9 : Page 4 déjà chargée
11. t10 : Page 5 chargée (code)
12. t11 : Page 6 chargée (code)
13. t12 : Page 7 chargée (code)
14. t13 : Page 8 chargée (code)

Les cadres sont limités, donc remplacement selon LRU.

(b) Calcul du nombre de défauts de page (LRU)

Chaque chargement d’une page non présente provoque un défaut. En suivant la séquence et la politique LRU, on compte les défauts. Le nombre exact dépend de la capacité mémoire et du remplacement.

Réponse : Le nombre de défauts est égal au nombre de pages chargées pour la première fois, soit 9 défauts (pages 0 à 8). Ce nombre est optimal car chaque page doit être chargée au moins une fois.

Exercice 3 : Organisation mémoire pour un appareil audio

Un appareil avec :

• 64 Mo mémoire principale
• 80 Go mémoire secondaire
• 3 processus : Afficheur (A), Transfert (T), Son (S)
• 16 Mo réservés au système d’exploitation
• A : 500 Ko stable
• S : 500 Ko initial + espace contigu supplémentaire (4 à 10 Mo)
• T : 5 Mo initial + tampons dynamiques

Question 3.1 : Proposition d’organisation mémoire

Proposition :

• Réserver 16 Mo pour le système
• Allouer 500 Ko fixes pour A
• Allouer initialement 500 Ko pour S, prévoir un espace contigu supplémentaire de 10 Mo maximum
• Allouer 5 Mo pour T avec tampons dynamiques
• Utiliser partitions variables pour minimiser fragmentation externe
• Placer A et S proches pour accès rapide, T dans une zone séparée

Réponse : Organisation en partitions variables avec allocation contiguë pour S afin d’éviter les sauts dans la musique, réservant suffisamment d’espace pour tampons dynamiques de T.

Question 3.2 : Type d’adressage proposé

Adressage relatif est préférable car il permet la relocation dynamique et la flexibilité dans l’allocation mémoire. Les registres de relocation et limites assurent la protection et la traduction d’adresses.

Réponse : Adressage relatif, avec registres de relocation et limites pour assurer la sécurité et la flexibilité.

Exercice 4 : Gestion mémoire virtuelle et pagination

Système avec :

• Adressage virtuel 32 bits
• Page de 4 Ko
• Mémoire physique 1 Mo

Question 4.a : Données manquantes et étapes de traduction

Données manquantes :

• Table des segments et pages
• Numéro de segment et page pour l’adresse virtuelle
• Adresse de base du segment en mémoire physique

Étapes :

1. Extraire numéro de segment, numéro de page, déplacement
2. Accéder à la table de segments pour obtenir adresse base
3. Accéder à la table de pages pour obtenir numéro de cadre
4. Concaténer numéro de cadre et déplacement pour obtenir adresse physique

Réponse : Les tables de segments et pages sont nécessaires. La traduction suit extraction, consultation tables, et calcul adresse physique.

Question 4.b.1 : Nombre de pages pour tables à deux niveaux

Avec tables de pages sur 4 octets, et adressage 32 bits, la structure est :

• Bits pour niveau 1, niveau 2, et déplacement
• Calcul du nombre de pages nécessaires pour les tables

Réponse : Le nombre exact dépend de la division des bits, non précisé ici.

Question 4.b.2 : Pages de niveau 2 chargées

Pour code entre 2 Mo et 6 Mo-1, et données entre 12 Mo et 21 Mo-1, calculer pages de niveau 2 nécessaires pour ces plages.

Réponse : Impossible sans plus d’informations sur la structure exacte des tables.

Question 4.c : Taille table inversée

Bits 12 à 31 pour numéro de page, donc 20 bits, soit 2^20 pages virtuelles.

Table inversée contient une entrée par cadre physique.

Mémoire physique 1 Mo / 4 Ko = 256 cadres.

Réponse : La table inversée contient 256 entrées.

Exercice 5 : Remplacement de pages

4 cases mémoire occupées, avec données sur temps de chargement, dernier accès, bits R, M, P.

Question 5.1 : Page remplacée selon algorithmes

• a) LRU : remplacer la page la moins récemment utilisée (plus ancien dernier accès)
• b) FIFO : remplacer la page chargée la plus ancienne (plus ancien t chargement)
• c) Horloge : parcourir les cases en cercle, donner une seconde chance si R=1

Réponse : Identifier la page selon ces critères dans le tableau donné.

Question 5.2 : Calcul du temps d’accès moyen

Temps accès mémoire = 100 ns

Temps défaut page :

• 10 ms si page à retirer non modifiée ou case libre
• 20 ms si page modifiée

Taux défaut page = 35%

70% des défauts concernent page modifiée

Calcul :

Temps moyen = (1 - 0,35) * 100 ns + 0,35 * (0,7 * 20 ms + 0,3 * 10 ms)

= 0,65 * 100 ns + 0,35 * (14 ms + 3 ms)

= 65 ns + 0,35 * 17 ms = 65 ns + 5,95 ms ≈ 5,95 ms

Réponse : Temps d’accès moyen ≈ 5,95 ms.

Question 5.3 : Adresse physique d’une donnée

Processus P avec segments S1 (16 Ko), S2 (8 Ko), S3 (4 Ko).

Pages chargées :

• S1 pages 2 et 3 dans cases 2 et 0
• S2 page 2 dans case 9
• S3 page 1 dans case 12

Donnée à l’adresse décimale 8212 :

• a) Segment : S1 (car 16 Ko = 16384 octets, 8212 < 16384)
• b) Numéro de page dans S1 : 8212 / 4096 = 2 (pages de 4 Ko)
• c) Déplacement dans page : 8212 % 4096 = 20
• d) Numéro de case : page 2 de S1 chargée dans case 2
• e) Déplacement dans case = 20
• f) Adresse physique = case 2 * 4096 + 20 = 2*4096 + 20 = 8212

Réponse : Segment S1, page 2, déplacement 20, case 2, adresse physique 8212.

Exercice 6 : Pagination et anomalie de Belady

I.a) Taille espace logique et bits

• Code 1024 octets, vecteur 1000 octets
• Mémoire réelle 1 Mo
• Page 512 octets
• Adresse 24 bits

Calculs :

1. Taille espace logique = 2^24 octets = 16 Mo
2. Bits déplacement = log2(512) = 9 bits
3. Bits numéro page virtuelle = 24 - 9 = 15 bits
4. Bits adresse réelle = log2(1 Mo) = 20 bits
5. Bits numéro page réelle = 20 - 9 = 11 bits
6. Nombre entrées table pages = 2^15 = 32768

Réponse : Espace logique 16 Mo, 9 bits déplacement, 15 bits page virtuelle, 20 bits adresse réelle, 11 bits page réelle, 32768 entrées table pages.

I.b) Fragmentation interne

La taille de page est 512 octets, donc chaque page est allouée en entier même si utilisée partiellement. Le vecteur de 1000 octets occupe 2 pages (1024 octets), donc 24 octets inutilisés dans la dernière page.

Réponse : Oui, il y a fragmentation interne due à l’allocation par pages fixes.

II) Format adresse virtuelle 32 bits, pages 256 octets, table 3 niveaux

Page = 256 octets = 2^8 octets → 8 bits déplacement

Adresse virtuelle 32 bits → 32 - 8 = 24 bits pour index tables

3 niveaux → chaque table indexée par 8 bits (24/3)

Nombre de tables = 3, chaque table a 2^8 = 256 entrées.

Réponse : Adresse virtuelle : 8 bits niveau 1 + 8 bits niveau 2 + 8 bits niveau 3 + 8 bits déplacement. 3 tables de 256 entrées chacune.

III.a) Anomalie de Belady pour FIFO

Vecteur ω = {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5}

Pour m=3 cadres, défauts de page = 9

Pour m=4 cadres, défauts de page = 10 (plus grand que pour 3 cadres)

Réponse : L’anomalie de Belady est démontrée car augmenter le nombre de cadres augmente le nombre de défauts.

III.b) FIFO n’est pas un algorithme à pile

La propriété d’inclusion M(m,r) ⊆ M(m+1,r) n’est pas respectée car certains états avec 3 cadres ne sont pas inclus dans ceux avec 4 cadres.

Réponse : FIFO viole la propriété d’inclusion, donc n’est pas un algorithme à pile.

Méthode : Techniques récompensées et erreurs pénalisées

Ce sujet valorise :

• La compréhension précise des concepts de gestion mémoire (pagination, segmentation, fragmentation)
• La rigueur dans le calcul des tailles, des bits et des adresses
• L’application correcte des algorithmes d’allocation et de remplacement
• La capacité à justifier qualitativement les choix d’architecture mémoire
• La présentation claire des étapes de raisonnement, avec calculs intermédiaires

Les erreurs pénalisées sont :

• Confusion entre fragmentation interne et externe
• Omissions des étapes de calcul ou de conversion d’adresses
• Non-respect des conventions données (ex : taille des pages, formats d’adresse)
• Réponses sans justification ou sans démonstration
• Incohérences dans les calculs ou résultats contradictoires avec les données

Il est essentiel de suivre strictement les définitions et hypothèses du sujet, de montrer chaque étape et de vérifier la cohérence des résultats.