Next: Les algorithmes de remplacement Up: Demand Paging Previous: Demand Paging

Efficacité

Efficacité des performances de Demand Paging :

Soit ma = 500 nanosecondes, le temps moyen d'accès a une mémoire.
le temps effectif d'accès avec le Demand Paging est

temps effectif = (1-p)*ma + p * "temps de gestion de l'erreur de page"
où p est la probabilité d'occurrence d'une erreur de page (page fault).

Une erreur de page nécessite de réaliser les opérations suivantes

  1. lever une interruption pour le système
  2. sauvegarder le contexte du processus
  3. déterminer que l'interruption est une erreur de page
  4. vérifier que la page en question est une page légale de l'espace logique, déterminer où se trouve la page dans la mémoire secondaire.
  5. exécuter une lecture de la page sur une page mémoire libre (libérer éventuellement une page cf. algorithme de remplacement de page)
  6. allouer pendant ce temps-là le cpu à un autre utilisateur
  7. interruption du périphérique
  8. sauvegarde du contexte du processus courant
  9. déterminer que l'interruption était la bonne interruption (venant du périphérique)
  10. mise à jour de la table des pages et d'autres pages pour indiquer que la page demandée est en mémoire maintenant.
  11. attendre que le processus soit sélectionné de nouveau pour utiliser l'unité centrale (cpu)
  12. charger le contexte du processus !

Toutes ces instructions ne sont pas toujours réalisées (on peut en particulier supposer que l'on ne peut pas préempter l'unité centrale, mais alors quelle perte de temps pour l'ensemble du système).

Dans tous les cas, nous devons au moins réaliser les 3 actions suivantes:

Ce qui coûte le plus cher est la recherche de la page sur le disque et son transfert en mémoire, ce qui prend de l'ordre de 1 à 10 millisecondes.

Ce qui nous donne en prenant une vitesse d'accès mémoire de 1 microseconde et un temps de gestion de page de 5 millisecondes un

Une erreur de page toutes les mille pages nous donne un temps effectif onze fois plus long que l'accès standard.

Il faut réduire à moins d'une erreur de page tout les 100000 accès pour obtenir une dégradation inférieure à 10 On comprend bien que les choix à faire sur des pages qu'il faut placer en mémoire sont donc très importants.

Ces choix deviennent encore plus importants quand l'on a de nombreux utilisateurs et qu'il y a sur-allocation de la mémoire, exécution concurrente de 6 processus de la taille supérieure ou égale à la mémoire physique!

Si l'on suppose de plus que nos 6 programmes utilisent dans une petite séquence d'instructions toutes les pages de leur mémoire logique, nous nous trouvons alors dans une situation de pénurie de pages libres.

Le système d'exploitation peut avoir recoure à plusieurs solution dans ce cas-là

  1. tuer le processus fautif ...
  2. utiliser un algorithme de remplacement de page

Cet algorithme de remplacement est introduit dans notre séquence de gestion d'erreur de page là où l'on s'attribuait une page libre de la mémoire centrale.

Maintenant il nous faut sélectionner une victime, c'est-à-dire, une des pages occupées de la mémoire centrale qui sera swappée sur disque et remplacée par la page demandée.

Remarquons que dans ce cas-là notre temps de transfert est doublé, comme il faut à la fois lire une page et sauvegarder une page sur disque (le temps de transfert disque est ce qui est le plus coûteux dans la gestion d'une erreur de page).

Il est possible de réaliser des systèmes de demand segments, mais le lecteur avisé remarquera rapidement les problèmes posés par la taille variable des segments.

Next: Les algorithmes de remplacement Up: Demand Paging Previous: Demand Paging

Dominique REVUZ
Mon Feb 2 12:10:31 MET 1998
Une Bug Un mail Merci