On dispose d'un système doté d'une pagination à la demande, suivant deux algorithmes A₁ et A₂. Au cours de son exécution, un programme accède successivement aux pages 1, 5, 2, 5, 1, 4, 1, 5, 3. Le système alloue à ce programme un espace de trois pages.

Avec l'algorithme A₁, on constate que l'on a successivement en mémoire les pages suivantes:

		1	1	1	1	1	 2	1	1	1
			5	2	2	2	 4	2	4	3
				5	5	5	5	4	5	5

Avec l'algorithme A₂, on constate que l'on a successivement en mémoire les pages suivantes:

		1	1	1	1	1	1	1	1	1
			5	2	2	2	4	4	4	3
				5	5	5	5	5	5	5

A- A votre avis, lequel des deux algorithmes correspondrait à l'algorithme FIFO, et lequel correspondrait à LRU? Justifiez votre raisonnement.

B- Déterminer dans chacun des cas le nombre de défauts de pages.

Le principe d'une pagination à la demande est le suivant: le système attribue au processus un certain nombre de pages (ici 3) lorsque le processus tente d'accéder à une page qui n'est pas présente en mémoire, il se produit un déroutement, et le système choisit suivant un algorithme de remplacement déterminé, la page qui doit être supprimée de la mémoire pour y être remplacée par celle qui est demandée. L'algorithme FIFO remplace la page qui est la plus ancienne en mémoire, alors que l'algorithme LRU remplace la page qui est la plus ancienne référencée.

Dans le cas de l'algorithme A₁, on constate que 4 remplace 1 qui est la plus ancienne présente en mémoire et la plus récemment référencée, il ne peut donc s'agir de LRU. En poursuivant l'analyse, 1 remplace 5 qui est maintenant la plus ancienne, puis 5 remplace 2, troisième entrée, et enfin 3 remplace 4, quatrième entrée. L'algorithme A₁ peut donc être FIFO.

Dans le cas de l'algorithme A₂, on constate que 4 remplace 2 dernière amenée en mémoire, ce ne peut donc être FIFO. Par contre 2 est alors la plus ancienne référencée, puisque les dernières références sont 1 puis 5. De même par la suite, 3 remplace 4 qui est aussi à ce moment la plus ancienne référencée. L'algorithme A₂ peut donc être LRU. Notons que cet algorithme pourrait aussi être LFU.

Les défauts de pages sont les déroutements provoqués par le processus qui référence une page qui n'est pas présente en mémoire. Le défaut entraîne un remplacement, donc un changement de l'ensemble des pages présentes en mémoire.

Avec l'algorithme A₁, les changements sont les suivants, indiqués par *:

		*	*	*			*	*	*	*
		1	1	1	1	1	2	1	1	1
			5	2	2	2	4	2	4	3
				5	5	5	5	4	5	5

Il y a donc 7 défauts de pages.

Avec l'algorithme A₂, les changements sont les suivants, indiqués par *:

		*	*	*			*			*
		1	1	1	1	1	1	1	1	1
			5	2	2	2	4	4	4	3
				5	5	5	5	5	5	5

Il y a donc 5 défauts de pages.