Systèmes d'Exploitation 1 : Correction Série TD N°7 – Gestion de la Mémoire
Allocation de Mémoire Non Contiguë (Paginage)
Exercice 1 : Optimisation des Défauts de Page
Les programmes sont structurés de manière à stocker les tableaux en mémoire ligne par ligne. Chaque élément du tableau occupe 1 mot (32 bits), et une page a une taille de 128 mots. Dans ce cas, la mémoire virtuelle est organisée comme suit :
A[0][0] A[0][1] ... A[0][127]A[1][0] A[1][1] ... A[1][127]...A[127][0] A[127][1] ... A[127][127]
Si le programme est exécuté selon l'ordre initial (colonnes puis lignes), les pages sont appelées dans la séquence suivante : page0, page1, ..., page127, page0, page1, ..., page127. Avec une mémoire physique de taille 128 pages, cela génère 128 × 128 défauts de page.
Pour réduire le nombre de défauts de page, il est proposé d'inverser les boucles for du programme. Ainsi, lorsque la page est chargée, toutes les données qu'elle contient sont lues en une seule fois, ce qui permet de la maintenir en mémoire et d'éviter de la recharger. Dans ce cas, l'ordre d'appel des pages devient : page0, page1, ..., page127. Le nombre total de défauts de page est alors 128, indépendamment de la taille de la mémoire physique.
Exercice 2 : Algorithme FIFO
Les adresses logiques sont converties en couples (page, offset) en divisant l'adresse par la taille d'une page (128 mots). Voici les résultats pour les adresses données :
| Demande | Adresse Logique | Page | Offset | Cadre | Adresse Physique |
|---|---|---|---|---|---|
| 1 | 657 | 5 | 7 | 0 | 57 |
| 2 | 523 | 4 | 19 | 1 | 323 |
| 3 | 170 | 1 | 42 | 2 | 170 |
| 4 | 725 | 5 | 77 | 3 | 725 |
| 5 | 1133 | 8 | 115 | 4 | 1133 |
| 6 | 145 | 1 | 17 | 0 | 145 |
| 7 | 190 | 1 | 62 | 1 | 190 |
| 8 | 658 | 5 | 8 | 2 | 590 |
| 9 | 573 | 4 | 45 | 3 | 573 |
| 10 | 56 | 0 | 56 | 0 | 56 |
| 11 | 598 | 4 | 70 | 1 | 598 |
| 12 | 888 | 6 | 112 | 2 | 288 |
| 13 | 1134 | 8 | 116 | 3 | 534 |
| 14 | 170 | 1 | 42 | 0 | 170 |
| 15 | 472 | 3 | 104 | 4 | 72 |
En utilisant l'algorithme FIFO (First-In-First-Out), l'ordonnancement des pages en mémoire centrale donne les résultats suivants :
Demande 1 : Cadre 0Demande 2 : Cadre 1Demande 3 : Cadre 2Demande 4 : Cadre 3Demande 5 : Cadre 4Demande 6 : Cadre 0 (remplace la page 5)Demande 7 : Cadre 1 (remplace la page 4)Demande 8 : Cadre 2 (remplace la page 2)Demande 9 : Cadre 3 (remplace la page 1)Demande 10 : Cadre 4 (remplace la page 0)Demande 11 : Cadre 0 (remplace la page 3)Demande 12 : Cadre 1 (remplace la page 2)Demande 13 : Cadre 2 (remplace la page 1)Demande 14 : Cadre 3 (remplace la page 0)Demande 15 : Cadre 4 (remplace la page 5)Nombre de défauts de page pour la demande 12 : 8Nombre total de défauts de page : 10
Exercice 3 : Algorithme LRU avec Taille de Page Optimisée
Avec une taille de page de 300 mots, les conversions d'adresses logiques en couples (page, offset) sont recalculées. Voici les résultats :
| Demande | Adresse Logique | Page | Offset | Cadre | Adresse Physique |
|---|---|---|---|---|---|
| 1 | 657 | 2 | 57 | 0 | 300 |
| 2 | 523 | 1 | 223 | 1 | 300 |
| 3 | 170 | 0 | 170 | 2 | 300 |
| 4 | 725 | 2 | 125 | 0 | 300 |
| 5 | 1133 | 3 | 233 | 1 | 300 |
| 6 | 145 | 0 | 145 | 2 | 300 |
| 7 | 190 | 0 | 190 | 0 | 300 |
| 8 | 658 | 2 | 58 | 1 | 300 |
| 9 | 573 | 1 | 273 | 2 | 300 |
| 10 | 56 | 0 | 56 | 0 | 300 |
| 11 | 598 | 1 | 298 | 1 | 300 |
| 12 | 888 | 2 | 288 | 2 | 300 |
| 13 | 1134 | 3 | 234 | 3 | 300 |
| 14 | 170 | 0 | 170 | 0 | 300 |
| 15 | 472 | 1 | 172 | 1 | 300 |
L'ordonnancement avec l'algorithme LRU (Least Recently Used) donne les résultats suivants :
Demande 1 : Cadre 0Demande 2 : Cadre 1Demande 3 : Cadre 2Demande 4 : Cadre 0 (remplace la page 2)Demande 5 : Cadre 1 (remplace la page 1)Demande 6 : Cadre 2 (remplace la page 0)Demande 7 : Cadre 0 (remplace la page 2)Demande 8 : Cadre 1 (remplace la page 0)Demande 9 : Cadre 2 (remplace la page 1)Demande 10 : Cadre 0 (remplace la page 3)Demande 11 : Cadre 1 (remplace la page 0)Demande 12 : Cadre 2 (remplace la page 1)Demande 13 : Cadre 3 (remplace la page 2)Demande 14 : Cadre 0 (remplace la page 3)Demande 15 : Cadre 1 (remplace la page 0)Nombre de défauts de page pour la demande 12 : 6Nombre total de défauts de page : 7
Exercice 4 : Réflexion sur les Algorithmes de Remplacement
Si les demandes sont mises en attente, tous les algorithmes de remplacement de page produisent le même résultat. Pour un ordre d'exécution donné, les pages déjà présentes en mémoire sont exécutées en premier, puis remplacées une par une par les pages en attente dans la file d'attente. Dans ce cas, il est préférable de choisir l'algorithme le plus simple, à savoir FIFO.
Exercice 5 : Impact de la Taille des Pages
Si une page a une taille de 10 unités (très petite par rapport à la taille du programme), le programme sera fortement fragmenté, entraînant un grand nombre de pages et donc de défauts de page. À l'inverse, une page trop grande peut aussi causer des problèmes en augmentant le nombre de défauts de page.
Conclusion : Choix de la Taille Optimale des Pages
La taille d'une page dans un système de mémoire paginée doit être ni trop grande ni trop petite. Il est essentiel de choisir une taille optimale en fonction des programmes couramment exécutés pour minimiser les défauts de page et améliorer les performances globales.
Foire Aux Questions (FAQ)
Qu'est-ce qu'un défaut de page ?
Un défaut de page survient lorsqu'un programme accède à une page qui n'est pas actuellement chargée en mémoire physique, nécessitant un chargement depuis la mémoire secondaire (disque). Cela ralentit l'exécution du programme.
Pourquoi inverser les boucles réduit-il les défauts de page ?
Inverser les boucles permet de lire toutes les données d'une même page avant de passer à la suivante, ce qui exploite la localité spatiale et réduit les rechargements inutiles, diminuant ainsi les défauts de page.
Quels sont les algorithmes de remplacement de page les plus courants ?
Les algorithmes les plus courants sont FIFO (First-In-First-Out), LRU (Least Recently Used), et LFU (Least Frequently Used). FIFO est le plus simple, tandis que LRU est souvent plus efficace.