Page prec.
Mémoire virtuelle 		Fin de page Page suiv.
Minimisation des défauts de page

Algorithmes de pagination

Introduction

    Comme nous l'avons vu, lorsque la pagination est mise en œuvre, seule une partie des pages de la mémoire virtuelle d'un processus sont présentes en mémoire physique. Un défaut de page est détecté chaque fois que le processeur tente d'accéder à une adresse virtuelle appartenant à une page virtuelle absente de la mémoire physique. Le traitement d'un défaut de page est le suivant :     Il s'agit donc d'un traitement coûteux en temps CPU.

Nombre de pages physiques allouées à un processus

Overhead

    Lorsqu'un défaut de page est détecté, c'est le noyau du système d'exploitation qui a la charge de le résoudre. Le temps qu'il y passe est du temps "perdu" par les utilisateurs. Ce temps passé par le système d'exploitation pour gérer la machine est appelé l'overhead. Il faut le diminuer le plus possible.

    Lorsque le système passe le plus clair de son temps en overhead, on dit qu'il s'écroule.  En ce qui concerne la pagination, la prolifération des processus en mémoire provoque la diminution du nombre moyen de pages affectées à chacun, donc l'augmentation du taux de défauts de page. Le S.E. ne cesse alors de déposer des requêtes de chargement de pages, mais la mémoire étant saturée, il doit en chasser d'autres pages dont l'absence va à son tour provoquer de nouveaux défauts de page et ainsi de suite.

    La mise en œuvre de la pagination nécessite donc beaucoup de soins. L'efficacité du système de gestion de la mémoire dépend du taux de défauts de pages. L'optimisation doit donc porter sur les deux points suivants:

Ensemble de travail (working set) et fenêtre

    On appelle l'ensemble de travail d'un processus (ou " working set") l'ensemble des pages référencées pendant les n dernières références à la mémoire. La taille de cet ensemble de travail dépend de plusieurs paramètres :     Le nombre de défauts de pages d'un processus dépend de plusieurs facteurs :     La mémoire virtuelle représente l'ensemble des références mémoires auxquelles peut accéder le processus au cours de son exécution. Un processus n'exécute en général pas la totalité des instructions du programme, et n'accède pas à l'ensemble de ses données au cours d'une exécution. Le nombre total de pages virtuelles nécessaires est donc en général plus réduit que le nombre total de pages virtuelles. Cependant l'utilisateur n'en est pas maître et ce nombre dépend des données traitées. Si la largeur de la fenêtre est maximale, l'ensemble de travail est donc l'ensemble des pages qui ont été nécessaires à l'exécution complète du processus. Le tableau suivant représente l'ensemble de travail et le contenu de la fenêtre au cours du déroulement d'un processus fictif pour des largeurs de fenêtre de 2, 3 et 4. La première colonne représente la succession des numéros des pages accédées.
 
N° de page accédée
 2 3 4
24
15
18
23
24
17
18
24
18
17
17
15
24
17
24
18		 24
24 - 15
15 - 18
18 - 23
23 - 24
24 - 17
17 - 18
18 - 24

18 - 17

17 - 15
15 - 24
24 - 17

24 - 18

 24
24 - 15
24 - 15 - 18
15 - 18 - 23
18 - 23 - 24
23 - 24 - 17
24 - 17 - 18
 
 
 

18 - 17 - 15
17 - 15 - 24
 

17 - 24 - 18

 24 
24 - 15
24 - 15 - 18
24 - 15 - 18 - 23

18 - 23 - 24 - 17
 
 
 
 

24 - 18 - 17 - 15
 
 
 
 

    Le contenu de la fenêtre est inscrit chaque fois qu'il est modifié, c'est-à-dire chaque fois qu'un nouveau numéro de page remplace un ancien. Cela correspond à un défaut de page. Comme on s'en doute, le nombre de défauts de pages diminue au fur et à mesure que la largeur de la fenêtre augmente, c'est à dire lorsqu'on attribue plus de pages physiques au processus.

Principe de proximité

    En 1968, Deming a étudié le comportement des processus et ses résultats sont restés très utiles à l'optimisation de la pagination. Il a constaté que les références à la mémoire, tant en ce qui concerne le code que les données, ne sont pas du tout réparties de façon aléatoire sur tout l'espace de la mémoire virtuelle. Le processus reste localisé sur un petit nombre d'adresses virtuelles pendant un certain temps, puis brusquement change partiellement de localisation.  Les phases "stationnaires" correspondent à l'exécution du code interne à des structures répétitives et au parcours de données structurées (tableaux). Elles correspondent d'autant plus à un découpage logique et sont d'autant plus localisées que le programme est conçu selon une méthode de programmation structurée. Les phases de transition correspondent au contraire à des changements de traitement (schéma de choix, longjmp, exception, etc.). Il faut aussi remarquer que la structure des données choisie peut avoir des conséquences sur l'ensemble de travail (et donc sur le nombre de défauts de page : voir "Minimisation des défauts de page").

    En conséquence, le nombre de pages physiques accordées à un processus doit être suffisamment grand pour contenir l'ensemble des pages virtuelles en cours d'utilisation, mais un nombre trop grand ne ferait que conserver en mémoire physique des pages qui ont été utilisées dans le passé et qui ne sont plus d'aucune utilité.

    Le nombre de défauts de page dépend aussi, mais de façon complexe, de la taille des pages. A la limite, il n'y a aucun défaut de page si la page est de la taille de la mémoire virtuelle à condition qu'elle puisse entrer en mémoire physique (ce qui n'est vraisemblablement pas le cas). Sinon, il y a au contraire un défaut de page qui ne peut être résolu ! A l'autre extrême, si les pages sont réduites à une adresse virtuelle, le taux d'utilisation des adresses d'une page montée est donc de 100%. Dans la pratique, la taille optimale doit être trouvée empiriquement.

Choix d'un emplacement physique

    Si des pages physiques ne sont pas affectées, l'une d'elles est choisie pour recevoir la page virtuelle manquante. Si au contraire toutes les pages sont occupées, il faut en choisir une en cours d'utilisation, appartenant ou non au processus en défaut de page. Si la page choisie est une "page sale", c'est-à-dire dont le contenu a été modifié depuis son chargement en mémoire centrale à partir de la mémoire secondaire, il faut la sauvegarder en mémoire secondaire (zone de swap sur disque) avant d'en écraser le contenu par la nouvelle page. En conséquence il y a tout intérêt à choisir une "page propre" qui économise un transfert disque. Le processus qui effectue le choix de la page à remplacer est appelé le dérobeur de page.

    Le choix de la page à supprimer est lui aussi guidé par le principe de proximité : les pages les plus récemment utilisées sont celles qui ont la probabilité la plus grande d'être référencées, car elles font partie de l'ensemble de travail courant ou le plus récent. Au contraire, une page "ancienne" appartient probablement à un ensemble de travail qui a changé donc elle a une probabilité beaucoup plus faible d'être référencée. L'algorithme consiste donc à éliminer la page la plus ancienne. Cela nécessite un mécanisme difficile à mettre en œuvre : d'une part chaque référence à une page réelle doit actualiser la date de dernière utilisation, d'autre part le dérobeur de page doit faire une recherche coûteuse d'ancienneté de page.

Déchargement-chargement de la page choisie

    Le dérobeur de page renvoie au noyau le numéro de la page physique réceptrice qu'il a élue. Si cette page est sale, le noyau doit d'abord la recopier dans la zone de swap. Il doit donc chercher un espace de swap disponible, le verrouiller et verrouiller la page à transférer, puis déposer une requête de transfert-disque.

    Le noyau ne pourra reprendre la suite du traitement qu'après réception d'un acquittement du transfert demandé. La page physique étant libre, le noyau pourra déposer une nouvelle requête de transfert, cette fois du disque vers la mémoire principale, puis attendre un nouvel acquittement. A sa réception, le processus suspendu (en état d'attente : voir Etats d'un processus et changements d'état ) pourra de nouveau être éligible : pendant toute cette attente en effet, de nombreux autres processus auront pu se voir attribuer le processeur et auront pu eux-mêmes tomber en défaut de page (d'où effondrement du système) possible.

Mécanismes de régulation

    Le S.E. doit être prémuni contre deux phénomènes qui sont traités différemment :     Pour absorber les pics transitoires de demandes de pages, un seuil minimal de pages libres est indiqué au S.E. Dès qu'il est franchi, le système réagit. Sa réserve lui permet cependant d'absorber le pic de demandes.

    Le nombre maximal de pages physiques pour un processus donné peut être limité. S'il nécessite des pages supplémentaires, le nombre maximal qui lui est affecté est augmenté mais le processus est au préalable chassé complètement de la mémoire sur la zone de swap et sa mémoire physique entièrement récupérée par le dérobeur de pages. Ainsi, un processus gourmand en ressources mémoire ne sera rechargé que lorsque le nombre de pages physiques dont il a besoin seront disponibles simultanément.

    Il est aussi possible d'obliger le dérobeur de pages d'en prélever au processus même qui a provoqué le défaut. On peut aussi introduire des temporisations (voir Unix) imposant à un processus chassé un temps minimal (par exemple 2 ou 3 secondes) avant de pouvoir être de nouveau élu.

Page prec.
Mémoire virtuelle 		Début de page Page suiv.
Minimisation des défauts de page
Dernière mise à jour : 28/08/2001