LES ALGORITMES DE PAGINATION
DEVOIR : Les algorithmes de pagination
Soit la chaine suivante :1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6.Faisons une meilleure représentation pour faciliter la compréhension.
ALGORITHME FIFO (first in first out)
Elle consiste à remplacer la page qui est en mémoire depuis le plus longtemps .Le système alloue à ce programme un espace de 4pages (initialement vide) donnons le nombre de défaut de pages.
Partant d'un espace de 4 pages initialement vide, la suite des pages présentes en mémoire est la suivante, où les colonnes représentent les configurations successives. Une '*' dans une colonne indique un défaut de page. Cela se présente lorsque la page référencée n'est pas dans la colonne précédente.
Références 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Défauts * * * * * * * * * * * * * *
1 1 1 1 1 1 5 5 5 5 5 3 3 3 3 3 1 1 1 1
2 2 2 2 2 2 6 6 6 6 6 7 7 7 7 7 7 3 3
3 3 3 3 3 3 2 2 2 2 2 6 6 6 6 6 6 6
4 4 4 4 4 4 1 1 1 1 1 1 2 2 2 2 2
L'algorithme FIFO implique un remplacement dans l'ordre où les pages sont amenées en mémoire, c'est-à-dire dans l'ordre 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6. En comptant les '*', on constate qu'il y a 14 défauts de page.
ALGORITHME LRU (least recently used)
Elle consiste à remplacer la page qui n’ a pas été utilisée depuis le plus longtemps.
Références 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Défauts * * * * * * * * * *
1 1 1 1 1 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 5 5 5 5 5 3 3 3 3 3 3 3 3 3
4 4 4 4 6 6 6 6 6 7 7 7 7 1 1 1 1
on constate qu'il y a 10 défauts de page.
REMPLACEMENT OPTIMAL
Elle consiste à choisir la page qui sera accédée dans un avenir le plus lointain possible.
Références 1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Défauts * * * * * * * *
1 1 1 1 1 1 1 1 1 1 1 1 7 7 7 7 1 1 1 1
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
4 4 4 5 6 6 6 6 6 6 6 6 6 6 6 6 6
on constate qu'il y a 8 défauts de page.