Programmation des Systèmes
Gestion de la mémoire
Travaux Dirigés assurés par Philippe Décogné
07/12/2002
Allocation par partitions variables
Soit un système qui utilise l'allocation par partitions variables. On parle aussi d'allocation par zones quand la taille des zones allouées est variable, ou d'allocations par blocs quand la taille des blocs alloués est fixe.
L'allocation se fait selon le choix first fit. C'est-à-dire que la première zone rencontrée dont la taille est supérieure ou égale à la taille du processus à charger est celle qui est allouée au processus.
On considère à l'instant t l'état suivant de la mémoire centrale :
Représenter l'évolution de la mémoire centrale en fonction de l'arrivée des évènements suivants :
1 - Arrivée du programme G (20 K)
2 - Départ du programme B
3 - Arrivée du programme H (15 K)
4 - Départ du programme E
5 - Arrivée du programme I (40 K)
Arrivée du programme G
La première zone possible est la zone de 30 K. Les 20 premiers K sont alloués à G, le reste forme une nouvelle zone libre de 20 K.
Départ du programme B
La zone allouée à B est libérée et forme une zone libre de 20 K. Les 20 K libérés sont joints à la zone libre de 10 K qui les précèdent et forme une nouvelle zone libre de 30 K.
Arrivée du programme H
La première zone possible est la zone de 30 K. Les 15 premiers K sont alloués au programme H, le reste forme une nouvelle zone libre de 15 K.
Départ du programme E
La zone allouée à E est libérée et forme une zone libre de 5 K. Les 5 K libérés sont joints à la zone libre de 10 K qui les précèdent et ainsi qu'à celle de 15 K qui les suit, et forme une nouvelle zone libre de 30 K.
Arrivée du programme I
Il n'existe pas en l'état de zone suffisamment grande pour contenir le programme I qui réclame 40 K. Par contre, il existe globalement :
15 + 10 + 5 + 30 + 10 = 70 K
de libre. Il faut donc effectuer un compactage de la mémoire, ce qui consiste à déplacer les programmes de telle sorte que toutes les zones libres se retrouvent en un seul bloc à la fin.
De cette manière, les 40 premiers K de la nouvelle zone libre de 70 K après compactage pourront être alloués au programme I, le reste formera une nouvelle zone libre de 30 K.
Pagination
Soit la liste des pages virtuelles référencées aux instants t = 1, 2, ..., 11 :
3 5 6 8 3 9 6 12 3 6 10
La mémoire centrale est composée de 4 cases initialement vides.
Représentez l'évolution de la mémoire centrale au fur et à mesure des accès pour chacune des deux politiques de remplacement de pages FIFO et LRU. Notez les défauts de pages éventuels.
Politique FIFO
Les 4 premières pages 3, 5, 6, 8 sont chargées dans les cases 1, 2, 3, 4. Comme elles ne sont pas en mémoire à l'origine, elles génèrent un défaut de page.
La page 3 est déjà en mémoire en case 1, il n'est pas donc utile de la charger et elle ne génère pas de défaut de page.
La page 9 ne peut être chargée sans décharger une autre page, puisqu'il n'y a plus de case disponible. On choisit alors de décharger la page qui a été chargée la première, soit la page 3. On charge donc la page 9 en case 1. Elle génère, elle aussi, un défaut de page.
La page 6 est déjà en mémoire en case 3, elle ne génère donc pas de défaut de page.
Pour charger la page 12, il faut libérer la case qui correspond à la page la plus anciennement chargée. C'est la case 2. On déchargera donc la page 5 et l'on chargera la page 12 à la place. Elle génère un défaut de page.
La page 3 n'est plus en mémoire, elle a été déchargée au temps 6. Pour la recharger, il faut décharger la page la plus anciennement chargée, soit la page 6 en case 3. On charge donc la page 3 en case 3. Elle génère un défaut de page.
La page 6 n'est plus en mémoire, on vient de la décharger. Pour la recharger, il faut libérer la case correspondant à la page la plus anciennement chargée, soit la page 8 en case 4. On charge donc la page 6 en case 4. Elle génère un défaut de page.
La page 10 n'a jamais été chargée. On la charge en case 1, case correspondant à la page la plus anciennement chargée. On décharge, pour ce faire, la page 9. La page 10 génère un défaut de page.
| Temps | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Accès | 3 | 5 | 6 | 8 | 3 | 9 | 6 | 12 | 3 | 6 | 10 |
| Case 1 | 3 | 3 | 3 | 3 | 3 | 9 | 9 | 9 | 9 | 9 | 10 |
| Case 2 | 5 | 5 | 5 | 5 | 5 | 5 | 12 | 12 | 12 | 12 | |
| Case 3 | 6 | 6 | 6 | 6 | 6 | 6 | 3 | 3 | 3 | ||
| Case 4 | 8 | 8 | 8 | 8 | 8 | 8 | 6 | 6 | |||
| Défauts | D | D | D | D | D | D | D | D | D |
Politique LRU
Les 4 premières pages 3, 5, 6, 8 sont chargées dans les cases 1, 2, 3, 4. Comme elles ne sont pas en mémoire à l'origine, elles génèrent un défaut de page.
La page 3 est déjà en mémoire en case 1, il n'est pas donc utile de la charger et elle ne génère pas de défaut de page.
La page 9 ne peut être chargée sans décharger une autre page, puisqu'il n'y a plus de case disponible. On choisit alors de décharger la page la moins récemment utilisée, soit la page 5. On charge donc la page 9 en case 2. Elle génère, elle aussi, un défaut de page.
La page 6 est déjà en mémoire en case 3, elle ne génère donc pas de défaut de page.
Pour charger la page 12, il faut libérer la case qui correspond à la page la moins récemment utilisée. C'est la case 4. On déchargera donc la page 8 et l'on chargera la page 12 à la place. Elle génère un défaut de page.
La page 3 est toujours en mémoire en case 1, elle ne génère pas de défaut de page.
La page 6 est toujours en mémoire en case 3, elle ne génère donc pas de défaut de page.
La page 10 n'a jamais été chargée. On la charge en case 2, case correspondant à la page la moins récemment utilisée. On décharge, pour ce faire, la page 9. La page 10 génère un défaut de page.
| Temps | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Accès | 3 | 5 | 6 | 8 | 3 | 9 | 6 | 12 | 3 | 6 | 10 |
| Case 1 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 |
| Case 2 | 5 | 5 | 5 | 5 | 9 | 9 | 9 | 9 | 9 | 10 | |
| Case 3 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | 6 | ||
| Case 4 | 8 | 8 | 8 | 8 | 12 | 12 | 12 | 12 | |||
| Défauts | D | D | D | D | D | D | D |
Dans ce cas précis, qui est statiquement le plus courant, la politique LRU est plus efficace du point de vue des temps d'accès mémoire que la politique FIFO, puisqu'on charge moins souvent de pages en mémoire. Cela ne préjuge pas, toutefois, de l'efficience de l'utilisation du processeur.
Temps d'accès effectif
Sur un système qui a recours à la mémoire paginée à la demande, il faut 200 ns pour satisfaire une requête mémoire si la page reste en mémoire. Si tel n'est pas le cas, la requête prend 7 ms si un cache libre est disponible ou si la page à extraire n'a pas été modifiée. Il faut par contre 15 ms si la page à extraire a été modifiée.
Quel est le temps d'accès effectif si le taux de défaut de page est de 5 % et que, 60 % du temps, la page à remplacer a été modifiée ?
Petit rappel concernant les unités de mesure
1 ns = 10-9 s = 10-3 µs
1 µs = 10-6 s
1 ms = 10-3 s = 103 µs
Le temps d'accès effectif est égal à la somme pondérée par la fréquence des temps d'accès correspondant aux différents cas de figure.
Comme le taux de défaut de page est de 5 %, cela signifie que dans 95 % des cas, la page demandée est déjà en mémoire. Dans ce cas, le temps d'accès pondéré est de :
95 % x 200 x 10-3 = 0,19 µs
Dans le cas où la page est en défaut (5 % des cas) et que la page a été modifiée (60 % des cas de page en défaut), le temps d'accès pondéré est de :
5 % x 60 % x 15 x 103 = 450 µs
Dans les autres cas, cache libre disponible ou page non modifiée, qui représentent 40 % de 5 % des cas, le temps d'accès pondéré est de :
5 % x 40 % x 7 x 103 = 140 µs
Le temps d'accès effectif est donc de :
0,19 + 450 + 140 = 590,19 µs
L'algorithme de remplacement de page sous LINUX est basé sur l'algorithme de la montre, décrit ci-dessous.
Algorithme de base de la montre
À chaque case de la mémoire, on associe un bit d'utilisation u.
Quand une page est chargée pour la première fois en mémoire, le bit d'utilisation u est positionné à 1.
Dans l'algorithme de remplacement de page, on considère que les cases candidates au remplacement forment un tampon circulaire auquel est associé un pointeur.
Quand une page doit être remplacée, le système scanne le tampon à partir de la position du pointeur à la recherche d'une case dont le bit d'utilisation u est à zéro et modifie le bit d'utilisation et la position du pointeur de la manière suivante :
1 - La première case trouvée dont le bit d'utilisation u est à zéro est choisie comme case de remplacement, la page est remplacée et le pointeur avance sur la case suivante.
2 - Chaque fois qu'il rencontre une case avec bit d'utilisation u à 1, il le met à zéro et avance le pointeur sur la case suivante.
De cette manière, si toutes les pages du tampon ont un bit d'utilisation u à 1, le pointeur fera le tour complet du tampon et reviendra à sa position originale qui deviendra la case de remplacement (puisqu'elle aura à ce moment-là un bit d'utilisation u positionné à zéro).
Exemple :
Avant remplacement, le pointeur est positionné en case 1. La page correspondante 24 n'est pas éligible au remplacement puisque son bit d'utilisation est positionné à 1.
Le bit d'utilisation est positionné à 0. Le pointeur avance en case 2 où la page 66 a un bit d'utilisation positionné à 1, donc non éligible.
Le bit d'utilisation est positionné à 0. Le pointeur avance en case 3, où la page 7 a un bit d'utilisation positionné a 0. Elle est donc remplacée (et éventuellement sauvegardée avant) par la page 56 dont le bit d'utilisation est positionné à 1. Le pointeur avance en case 4.
Amélioration de l'algorithme
Dans les systèmes qui utilisent la pagination, un bit de modification m est associée à chaque page en mémoire centrale, et de là, à chaque case de la mémoire.
Ce bit de modification m sert à empêcher le remplacement d'une page modifiée avant sa sauvegarde en mémoire de stockage.
La prise en compte de ce bit de modification m dans l'algorithme de la montre permet de classifier les cases de la manière suivante :
- page anciennement référencée et non modifiée : u = 0 et m = 0
- page référencée récemment et non modifiée : u = 1 et m = 0
- page anciennement référencée et modifiée : u = 0 et m = 1
- page récemment référencée et modifiée : u = 1 et m = 1
L'algorithme de la montre fonctionne alors de la manière suivante :
1 - Le système scanne le tampon à partir de la position du pointeur à la recherche d'une case dont les bits u et m sont positionnés à zéro. La première case trouvée qui remplit ces conditions est choisie comme case de remplacement. Durant ce balayage, le bit d'utilisation n'est pas modifié.
2 - Si aucune case n'a été trouvée durant l'étape 1, le système scanne de nouveau le tampon à la recherche d'une case dont le bit u est à 0 et le bit m à 1. La première case trouvée qui remplit ces conditions est choisie comme case de remplacement. Durant ce balayage, le bit d'utilisation des cases rencontrées et non choisies est mis à 0.
3 - Si aucune case n'a été trouvée durant l'étape 2, le système recommence l'étape 1 (cette fois-ci toutes les pages ont un bit d'utilisation à 0 d'après l'étape 2) et, éventuellement, l'étape 2.
En bref, on gagne du temps en privilégiant le remplacement des pages anciennement référencées et non modifiées, puis des pages modifiées mais anciennement référencées, c'est-à-dire celles qui ont des chances statistiquement d'être les moins demandées dans un avenir proche.
Exemple :
Avant remplacement, le pointeur est positionné en case 1. Aucune page n'est éligible au remplacement puisqu'il n'existe aucune page dont les bits d'utilisation et de modification sont positionnés tous les deux à 0. Le pointeur fait un tour complet.
Au deuxième tour, les bits d'utilisation des pages 24, 66, et 7 sont mis à 0.
La page suivante possède un bit u = 0 et un bit m = 1. Elle est donc remplacée par la page 56 dont le bit d'utilisation est positionné à 1 et le bit de modification à 0.
Le pointeur avance en case 5.
Implémentation sous LINUX
Sous LINUX, le bit d'utilisation est remplacé par une variable âge sur 8 bits.
Chaque fois qu'on accède à une page, la variable âge est incrémentée.
Un processus d'arrière-plan (kswapd) scanne régulièrement les pages et décrémente la variable âge de toutes les pages chargées.
Ce processus, appelé dérobeur de pages, est réveillé dès que l'espace de mémoire libre tombe en-dessous d'une limite inférieure et libère des pages jusqu'à ce que l'espace mémoire libre passe au-dessus d'une limite supérieure.
Une page qui a un âge de 0 est candidate au remplacement.
Le swap-d sous LINUX
Structure d'une entrée de la table des pages d'un processus
V : bit de validation - indique si la page est présente ou non en mémoire centrale.
M : bit de modification - indique si la page a été modifiée en mémoire centrale.
Case : adresse physique de la page.
Accès : indique si le processus a demandé un accès à la page ou non.
Âge : compteur permettant de mémoriser l'âge de la page en mémoire centrale.
Les champs accès et âge sont utilisés par le processus dérobeur de page (kswpad) pour choisir les pages victimes (pages qui seront déchargées pour permettre à de nouvelles pages d'être chargées).
Le dérobeur de page est réveillé dès que l'espace mémoire libre tombe au-deçà d'une limite définie par le système.
Il libère des pages jusqu'à ce que le nombre de cases libres en mémoire centrale passe au-delà d'une limite définie par le système.
À chaque fois qu'une page est référencée, l'âge de la page est positionnée à zéro et le bit d'accès est mis à vrai.
À chacun des passages suivant l'algorithme de la montre, le dérobeur de page met le bit d'accès à faux et incrémente l'âge de la page.
Une page est victime si son bit d'accès est positionné à faux et si elle a atteint l'âge limite supérieur.
Exemple :
Le processus P accède à une page en mémoire centrale. Puis le dérobeur de page D y accède. De nouveau, le processus P accède à la page, etc... La limite système supérieure est 3. La page devient victime.
