Systèmes d'exploitation
TD1 / Gestion de la mémoire
1. Algorithmes de placement
Exercice 1
1. Avec un système multiprogrammation, il est nécessaire d’allouer au processus la
quantité de mémoire dont il a besoin. Donnez et expliquez le fonctionnement
des algorithmes de placement qui permettent de gérer l’allocation de partitions
variables de mémoire
2. Pagination
L’exécution d’un programme engendre une longue suite d’accès mémoire : il y a souvent
plusieurs accès pour une seule instruction et plusieurs dizaines de milliers d’instructions
exécutées. L’efficacité d’une politique de remplacement ne peut donc se juger que sur des
suites de taille significative, ce qui n’est pas le cas ici.
Pourquoi l’exécution d’un programme engendre-t-elle (souvent) des défauts de page ?
Durant un délai faible, un programme n’utilise qu’une faible partie de son espace de
travail. Il est donc inutile et coûteux de charger la totalité de cet espace. Mais en n’en
chargeant qu’une partie, il va arriver un moment où l’on accédera à un élément non
chargé :
• On peut charger cet élément à la place d’un élément déjà en mémoire : la
stratégie de remplacement va alors déterminer l’élément victime. Dans ce cas,
l’espace alloué à la tâche est de taille fixe.
• On peut aussi ajouter cet élément à l’espace de travail. La taille de celui-ci
augmente donc, mais comme on ne peut indéfiniment augmenter l’espace de
toutes les tâches, il faut à un moment supprimer certains éléments en mémoire.
La taille de l’espace peut aussi varier en fonction des besoins de la tâche, c’est le
fonctionnement des stratégies de type Working Set.
L2 Systèmes d'exploitation - TD1 / Gestion de la mémoire 1/7
Exercice 2
Algorithme optimal
Lors d’un défaut de page, on remplace la page qui sera utilisée le plus tard possible. Il est
clair que cet algorithme n’est pas réalisable, car il faudrait pour cela connaître l’avenir;
cependant, il est d’une grande utilité pour étalonner les autres algorithmes.
On suppose qu’un processus fait référence à ses pages dans l’ordre suivant:
6 0 1 3 0 3 1 4 2 5 2 3 2 1 6
1. Si on ne limite pas le nombre de cadres (frames) de mémoire alloués au
processus, combien de défauts de page sont provoqués par cette suite d’accès ?
Combien de cadres au minimum faut-il allouer au processus pour atteindre ce
nombre ?
2. Donnez l’évolution de la table des pages ainsi que le nombre de défauts de pages
si on alloue au processus 3 cadres et que l’algorithme optimal est mis en œuvre.
Algorithme FIFO
Lors d’un défaut de page, on remplace la plus ancienne page qui ait été chargée. On
suppose qu’un processus fait référence à ses pages dans l’ordre suivant:
6 0 1 3 0 3 1 4 2 5 2 3 2 1 6
3. Donnez l’évolution de la table des pages ainsi que le nombre de défauts de pages
si on alloue au processus 3 cadres et que l’algorithme FIFO est mis en œuvre.
Algorithme LRU (Least Recently Used)
Lors d’un défaut de page, on remplace la page la moins récemment utilisée. On suppose
qu’un processus fait référence à ses pages dans l’ordre suivant:
6 0 1 3 0 3 1 4 2 5 2 3 2 1 6
4. Dans le cas où on alloue au processus 3 cadres et que l’algorithme mis en œuvre
est LRU, donnez l’évolution de la liste des pages chargées classées par ordre de
dernière utilisation. Quel est le nombre de défauts de pages ?
Algorithme de l’horloge (clock)
Dans cet algorithme, on associe un bit (d’utilisation à 1 = bit de référencement R aussi
appelé bit référencé) à chaque cadre de page et on considère les cadres de pages comme
un tampon circulaire. Si la page à insérer n’est pas en mémoire, le pointeur va avancer
(jusqu’au prochain cadre avec R à 0, s’il n’y a que des cadres avec R à 1, on fait un tour
complet, tous les bits R des cadres repassent à 0). Si la page est déjà en mémoire, le
pointeur n’avance pas, le bit du cadre de la page concernée est forcé à 1.
On suppose qu’un processus fait référence à ses pages dans l’ordre suivant:
6 0 1 3 0 3 1 4 2 5 2 3 2 1 6
L2 Systèmes d'exploitation - TD1 / Gestion de la mémoire 2/7
5. Dans le cas où on alloue au processus 3 cadres et que l’algorithme mis en œuvre
est clock, donnez l’évolution de la liste des pages chargées classées par ordre de
dernière utilisation. Quel est le nombre de défauts de pages ?
Exercice 3
Dans le mécanisme de pagination, l’espace d’adressage du programme est découpé en
petits blocs de même taille appelés pages. L’espace de la mémoire physique est lui-même
découpé en blocs de taille fixe appelés cases ou cadres de page (Frame Page). La taille
d’une case est égale à la taille d’une page. Cette taille est définie par le matériel, comme
étant une puissance de 2, variant entre 512 octets et 8192 octets. Le choix d’une
puissance de 2 comme taille de page facilite la traduction d’une adresse logique en un
numéro de page et un déplacement dans la page. Les pages logiques d’un processus
peuvent donc être assignées aux cadres disponibles n’importe où en mémoire principale.
Dans ce cas, un processus peut se retrouver éparpillé n’importe où dans la mémoire
physique. Un schéma de pagination permet d’éliminer la fragmentation externe, car
toutes les pages sont de même taille. Cependant, une fragmentation interne peut se
produire si la dernière page de l’espace d’adressage logique n’est pas pleine.
Dans un système paginé, les pages font 256 mots mémoire (ici un mot = 8 bits = un octet)
et on autorise chaque processus à utiliser au plus 4 cadres de la mémoire centrale. On
considère (actuellement) la table des pages suivante pour le processus P :
Pages processus P 0 1 2 3 4 5 6 7
Cadre (en binaire) 011 000 101
Présence page en Oui Non Oui Non Non Non Oui Non
moire centrale
Les cadres en mémoire physique vont jusqu’à 111. Pour le moment, aucun autre
processus n’est présent en mémoire.
6. Indiquez quelle est la taille de l'espace d'adressage (= mémoire virtuelle) du
processus P et précisez de combien de mémoire vive (= mémoire physique)
dispose ce système
Pour convertir une adresse virtuelle en adresse réelle (= @ physique) on :
(a) calcule le numéro de la page et du déplacement dans la page.
(b) recherche dans la table de pages l’entrée qui correspond à la page, de façon à
en déduire le numéro du cadre
(c) l’adresse physique (réelle) est obtenue en ajoutant le déplacement à l’adresse
physique de début du cadre pour obtenir l’adresse réelle (=@ physique) de la
« case » mémoire à atteindre.
7. Calculez les adresses réelles correspondant aux adresses virtuelles suivantes
(vous signalerez éventuellement les erreurs d'adressage) : 240, 546, 1578, 2072,
770
L2 Systèmes d'exploitation - TD1 / Gestion de la mémoire 3/7
8. On considère l’adresse virtuelle suivante: 0000 0000 0000 0111. Sachant que les
4 bits de poids fort (les plus à gauche) désignent le numéro de page et que 12
bits suivants représentent le déplacement dans la page, donnez l’adresse
physique (exprimée en binaire) correspondant à cette adresse.
9. Quatre cadres sont alloués au processus P. Donnez, pour chaque algorithme
(optimal, FIFO, LRU, Clock), l’évolution de la table des pages ainsi que le nombre
de défauts de pages. Les pages demandées sont :
20613563206
Exercice 4
Un système qui implémente la pagination à la demande dispose de 4 cadres de mémoire
physique qui sont toutes occupées, à un instant donné, avec des pages de mémoire
virtuelle. Le tableau ci-dessous donne, pour chaque cadre de mémoire, le moment du
chargement de la page qu’elle contient (Tchargement), le temps du dernier accès à cette
page (Tdernier accès ) et l’état des bits référencé (R), modifié (M ) et présence (P) dans la
table des pages. Les temps sont donnés en tops d’horloge.
Cadre Page Tchargement Tdernier accès Bit R Bit M Bit P
0 5 126 270 0 0 1
1 3 230 255 1 0 1
2 2 110 260 1 1 1
3 4 180 275 1 1 1
10. Indiquez quelle est la page qui sera remplacée en cas d’un défaut de page si
l’algorithme de
remplacement de page est :
(a) FIFO
(b) LRU
(c) Clock
11. Dans le même système, avec pagination à la demande, le temps d’accès à une
page chargée en mémoire physique est de 100 ns. Le temps d’accès à une page
qui n’est pas en mémoire physique est de 10 ms s’il y a une case libre en
mémoire physique ou si la page qui sera retirée, pour faire place à la page
manquante, n’a pas été modifiée. Si la page qui sera retirée, pour faire place à la
page manquante, a été modifiée, le temps d’accès est de 20 ms. Sachant que le
taux de défauts de page est 35%, et que dans 70% des cas de défaut de page, la
page à retirer a été modifiée, calculez le temps d’accès moyen à la mémoire.
L2 Systèmes d'exploitation - TD1 / Gestion de la mémoire 4/7
Exercice 5
On considère un système à mémoire paginée où la taille d’une page est de 200*sizeof(int)
(autrement dit, une page peut contenir 200 entiers). Par simplification, la taille d’un
pointeur est la même que celle d’un entier.
Un petit processus X occupe la page 0 de la mémoire.
Il reste donc uniquement 3 cadres de pages de disponibles à l’instant où notre programme
arrive. Ce dernier initialise le contenu du tableau A défini par int A[][] = new int[100][100]
(cf. ci-dessous)
Quand on alloue le tableau en mémoire, le système crée un espace mémoire de 100 cases
accessible avec l’indice de gauche du tableau. Chacune de ces cases pointes sur un tableau
de 100 cases.
100 cases,
C1 C2 … … C100
chaque case pointe
sur un tableau de
100 cases
12. Sachant que ce programme est chargé dans la cadre de page numéro 1 et que les
2 autres cadres restants sont initialement libres
a) Combien de pages sont nécessaires pour stocker le tableau A ?
b) Quel est le nombre de défauts de pages expérimenté avec un remplacement
LRU et ce pour les deux programmes d’initialisation ci-dessous ? Quel est
l’algorithme le plus « efficace » ?
Algorithme 1
for (int j=0;j<100;j++) {
for (int i=0 ; i<100 ; i++) {
A[i][j]=0 ;
}
}
Algorithme 2
for (int i=0;i<100;i++) {
for (int j=0 ; j<100 ; j++) {
A[i][j]=0 ;
}
}
L2 Systèmes d'exploitation - TD1 / Gestion de la mémoire 5/7
3. Segmentation
Alors que la pagination ne prend pas en considération la structure d’un programme
comme elle est vue par l’utilisateur, la segmentation est une stratégie de gestion mémoire
qui reproduit le découpage mémoire tel qu’il est décrit logiquement par l’usager.
Dans une mémoire segmentée, chaque unité logique d’un programme est stockée dans
un bloc mémoire, appelé « segment » à l’intérieur duquel les adresses sont relatives au
début du segment. Ces segments sont de tailles différentes. Un programme sera donc
constitué d’un ensemble de segments de code et de données, pouvant être dispersé en
mémoire centrale.
Exercice 6
On considère la table des segments suivante pour un processus P :
Segment Base Limite
0 540 234
1 1244 128
2 54 328
3 2048 1024
4 976 200
13. Calculez les adresses réelles correspondant aux adresses virtuelles suivantes
(vous signalerez éventuellement les erreurs d'adressage) : (0:128), (1:100),
(4,200), (2:465), (3:888), (4:100), (4:344)
4. Segmentation paginée
Exercice 7
On considère un système avec une mémoire virtuelle segmentée paginée où la taille
d’une page est de 4Ko et une mémoire physique de 64Ko. L’espace d’adressage d’un
processus P est composé de trois segments S1, S2 et S3 de taille, respectivement 16Ko,
8Ko et 4Ko.
À un moment donné, pour le processus P, les pages 2 et 3 du segment S1, la page 2 du
segment S2 et la page 1 du segment S3 sont chargées en mémoire physique,
respectivement dans les cases 2, 0, 9, 12.
Le n° de page/cadre est exprimé sur 4 bits. Une adresse physique est exprimée sur 2
octets (16 bits) : dont 4 bits pour le numéro de cadre et 12 bits pour le déplacement dans
le cadre.
14. Pour chaque segment, donnez son nombre de cadres et de pages.
L2 Systèmes d'exploitation - TD1 / Gestion de la mémoire 6/7
15. Dans le tableau récapitulatif ci-dessous, donnez pour chaque segment dans
quelles pages et quels cadres il se situe.
Segment S1 S1 ...
Page 2
Cadre 2
16. Pour une donnée située dans l’espace d’adressage du processus P à l’adresse
décimale 8212, indiquez:
(a) le segment où la donnée est mémorisée
(b) le numéro de page dans le segment
(c) le déplacement dans la page
(d) le numéro de cadre
(e) le déplacement dans la case
(f) l’adresse physique (en décimal et en binaire)
L2 Systèmes d'exploitation - TD1 / Gestion de la mémoire 7/7
