4.16. Algorithmes de pagination

On s'intéresse aux systèmes de pagination à la demande.
A- Expliquer brièvement le principe de la pagination à la demande. Détailler les algorithmes FIFO et LRU. (au plus 20 lignes)
B- Au cours de son exécution, un programme accède successivement aux pages 0, 1, 4, 2, 0, 1, 3, 0, 1, 4, 2, 3.
B.1- On utilise l'algorithme FIFO et le système alloue à ce programme un espace de 3 pages (initialement vides). Donner la suite des pages présentes en mémoire et en déduire le nombre de défauts de page.
B.2- On utilise l'algorithme FIFO et le système alloue à ce programme un espace de 4 pages (initialement vides). Donner la suite des pages présentes en mémoire et en déduire le nombre de défauts de page.
B.3- On utilise l'algorithme LRU et le système alloue à ce programme un espace de 3 pages (initialement vides). Donner la suite des pages présentes en mémoire et en déduire le nombre de défauts de page.
B.4- On utilise l'algorithme LRU et le système alloue à ce programme un espace de 4 pages (initialement vides). Donner la suite des pages présentes en mémoire et en déduire le nombre de défauts de page.
Solution de l’exercice 4.16

4.16.1. Question A

Le principe de la pagination à la demande est le suivant. Le système attribue au processus un certain nombre de cases (ici 3 ou 4) qui peuvent recevoir des pages. Initialement toutes les cases sont vides. Lorsque le processus tente d'accéder à une page qui n'est pas présente en mémoire (elle n'est pas dans une case), il se produit un déroutement. S'il reste des cases libres, le système en choisit une quelconque, et y met la page demandée. S'il n'en reste pas, il choisit une case occupée par une page suivant un algorithme de remplacement déterminé, retire la page de la case et la remplace par celle qui est demandée.
L'algorithme de remplacement peut être FIFO. Dans ce cas, le système choisit la case qui contient la page la plus ancienne présente en mémoire.
L'algorithme de remplacement peut être LRU. Dans ce cas, le système choisit la case qui contient la page qui est la plus ancienne référencée parmi celles présentes en mémoire.

4.16.2. Question B

4.16.2.1. Question B.1

Partant d'un espace de 3 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érence		0	1	4	2	0	1	3	0	1	4	2	3
défauts		*	*	*	*	*	*	*			*	*	
			0	0	0	2	2	2	3	3	3	3	3	3
				1	1	1	0	0	0	0	0	4	4	4
					4	4	4	1	1	1	1	1	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 0, 1, 4, 2, 0, 1, 3, 4, 2. En comptant les '*', on constate qu'il y a 9 défauts de page.

4.16.2.2. Question B.2

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érence		0	1	4	2	0	1	3	0	1	4	2	3
défauts		*	*	*	*			*	*	*	*	*	*
			0	0	0	0	0	0	3	3	3	3	2	2
				1	1	1	1	1	1	0	0	0	0	3
					4	4	4	4	4	4	1	1	1	1
						2	2	2	2	2	2	4	4	4
L'algorithme FIFO implique un remplacement dans l'ordre où les pages sont amenées en mémoire, c'est-à-dire dans l'ordre 0, 1, 4, 2, 3, 0, 1, 4, 2, 3. En comptant les '*', on constate qu'il y a 10 défauts de page.
Remarque (hors sujet): on constate que le processus se comporte moins bien que précédemment, alors qu'il a plus d'espace. Cette anomalie est connue sous le nom d'anomalie de Belady.

4.16.2.3. Question B.3

Partant d'un espace de 3 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érence		0	1	4	2	0	1	3	0	1	4	2	3
défauts		*	*	*	*	*	*	*			*	*	*
			0	0	0	2	2	2	3	3	3	4	4	4
				1	1	1	0	0	0	0	0	0	2	2
					4	4	4	1	1	1	1	1	1	3
L'algorithme LRU implique lors de chaque remplacement de rechercher la page la plus anciennement référencée, parmi celles de la colonne précédente. Par exemple, la deuxième référence à la page 4 entraîne le remplacement de la page 3. En comptant les '*', on constate qu'il y a 10 défauts de page.

4.16.2.4. Question B.4

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érence		0	1	4	2	0	1	3	0	1	4	2	3
défauts		*	*	*	*			*			*	*	*
			0	0	0	0	0	0	0	0	0	0	0	3
				1	1	1	1	1	1	1	1	1	1	1
					4	4	4	4	3	3	3	3	2	2
						2	2	2	2	2	2	4	4	4
Dans ce cas, la première référence à la page 3 implique le remplacement de la page 4, et la deuxième référence à la page 4 implique le remplacement de la page 2. En comptant les '*', on constate qu'il y a 8 défauts de page.