GEF 435Principes des systèmes d’exploitation

Algorithmes de remplacement de pages pt II(Tanenbaum 4.4)

Revue

• Quel algorithmes de remplacement de pages avons nous vus jusqu’à maintenant?OptimalNRUPAPSSeconde chanceHorlogeMRU (avec aide du matériel)

Synopsis

• Algorithme de la page le moins récemment utilisée en logiciel (vieillissement)

• Ensemble de travail• Algorithme Horloge ET

Problèmes avec MRU

• On se souvient: MRULes deux dernières solutions ont besoin de

matériel• Registres et un genre de compteur pour les instructions,

ou

• Une matrice en matériel de grandeur n x n

La deuxième solution est particulièrement coûteuse quand le nombre de cadres augmente.

En pratique, ces deux solutions ne sont pas grandement utilisées

Est-ce que MRU peut être implémenté en logiciel?

Émulation logiciel de MRU

• Chaque page a un compteur logiciel• À chaque interruption de l’horloge, si une page a

été utilisé, on ajoute 1 à son compteurEst-ce qu’il y a des problèmes avec cette solution?

• Au lieu d’ajouter un nombre on fait un décalage logique à droite en entrant la valeur 0 ou 1, à gaucheCeci vieilli la page de façon similaire à notre estimation

du ‘processus le plus court en prochain’ dans un système interactif

Émulation logiciel de MRU

Émulation logiciel de MRU

• Est-ce qu’il y a des différences entre notre émulation du MRU et l’idéal?Parce que nous enregistrons l’utilisation par “tic” nous

ne pouvons pas discriminer entre deux pages qui ont la même valeur pour le bit le plus significatif. Dans ce cas on choisi la page avec la plus petite valeur du compteur

Avec un nombre fini de bits pour les compteurs, plusieurs pages vont aller à zéro relativement vite. À ce point, on ne peut pas dire quelle page dans le groupe de pages qui ont des compteurs à zéro est la page MRU, on doit donc prendre une des pages dans le groupe aléatoirement

L’ensemble de travail

• Jusqu’à maintenant nous avons discuté de la pagination dans sa forme ‘pure’Aussitôt que le CPU essaie d’extraire la première instruction

d’un processus un défaut de page se produit. Des autres défauts de page pour le tas et la pile suivent assez

rapidementÉventuellement, le processus a le nombre de pages dont il a

besoin et il se stabilise. Cette stratégie s’appel chargement sur demande (demand paging)

Si des processus entiers sont permutés entre le disque et la mémoire principale chaque fois qu’un processus se voit donné le CPU il va faire de l’écroulement ‘thrashing’ de façon spectaculaire pour les premières millisecondes

L’ensemble de travail (working set)

• Pour minimiser l’écroulement, beaucoup de systèmes de pagination vont tracer l’ensemble des pages qu’un processus se sert couramment. Cet ensemble de pages s’appel l’ensemble de travail et l’approche s’appel le model de l’ensemble de travailLe chargement des pages qu’un processus va

probablement avoir besoin avant de laisser le processus s’exécuter s’appel pré-pagination

• Cette approche réduit l’écroulement parce que, à un instant donné, les processus tendent à référencer un petit groupe d’adresses de mémoire

L’ensemble de travail

• Avec l’examen des référence de mémoire récentes, la grandeur de l’ensemble de travail augmenteÀ un instant t, avec k références de mémoire récentes

l’ensemble de travail est w(k,t)

L’ensemble de travail

• La fn w(k,t) est monotone croissanteQuand k est augmenté avec plus de références, la grandeur de

l’ensemble de travail doit rester constante ou augmenter

• w(k,t) croit rapidement initialement lorsque les pages initiales sont demandés et parce que les programmes exécutent en boucles, w(k,t) croit lentement quand le programme change de boucle

• Ce comportement rend possible le traçage du contenue de l’ensemble de travail pendant l’exécution et permet d’estimer les pages qui sont requises quand un processus est remis en exécution (ces pages sont pré-chargées)

L’ensemble de travail

• Comment détermine-t-on l’ensemble de travail?Dans sa forme pure, chaque référence serait entreposée

dans une liste chaînée avec les duplications supprimées. La grandeur de la liste serait k

• Ceci est dispendieux en temps (pour disons, k=10,000)

Une approximation peut être faite en définissant l’ensemble de travail comme étant l’ensemble de pages utilisées dans les dernières T secondes de temps de CPU

• Parce que k augmente typiquement avec une augmentation de T ceci est une définition raisonnable

• Chaque processus a besoin de sa propre ‘horloge virtuelle’

L’ensemble de travail

• ‘L’horloge virtuelle’Chaque processus a une horloge qui mesure combien de temps

d’exécution il c’est vu allouer• ie: si un processus commence au temps 0, et qu’il a eu deux morceaux

de temps de 25ms chaque dans les dernières 300ms alors son horloge virtuelle indique 50

L’ensemble de travail est maintenant composé des pages qu’un processus a référencé dans les dernières secondes virtuelles

• On peut maintenant voir un algorithme de remplacement de page apparaître: quand on veut évincer une page, on choisi une page qui n’est pas dans l’ensemble de travailComment implémente-t-on ceci en pratique?

Algo de remplacement de pages avec ensemble de travail (ARP ET)

• Pour implémenter l’ARP ET:Chaque processus a besoin d’une horloge virtuelleChaque page en mémoire requiert les bits d’utilisation et de

modification – ces bits opèrent de la même façon qu’avantDe plus, chaque page a besoin d’une entrée pour sauvegarder le

temps virtuel approximatif écoulé depuis la dernière référence à la page

Sur les tics d’horloge toutes les pages avec la bit d’utilisation à 1 ont leurs horloges de référence ajustées au temps virtuel courrant (c’est pourquoi le temps virtuel listé pour chaque page est approximatif )

ARP ET

• Pour implémenter le ARP ET:Sur un défaut de page, on inspecte les entrées dans la table de

pages:• Si une page est utilisée, la bit d’utilisation est remise à 0 et le temps de

dernière utilisation est ajusté au temps virtuel courrant

• Si la page n’a pas été utilisé, le temps de dernière utilisation est inspecté. Si le temps virtuel courrant moins le temps de dernière utilisation du cadre est plus grand que secondes la page est enlevée

Si aucun candidat n’est trouvé alors:• On évince une page avec le temps de dernière utilisation le plus vieux

qui n’a pas été référencé dans le dernier tic d’horloge

• Si toutes les pages ont étés utilisées dans le dernier tic d’horloge, on en évince une aléatoirement

ARP ET

ARP ET

• Est-ce qu’il y a des problèmes avec cette façon de faire?La table de pages entière doit être examinée à chaque

défaut de page jusqu’à ce que l’on trouve une candidate!

• A-t-on vue un problème similaire dans le passé récent?PAPS/ARP de la seconde chance maintienne une liste

de pages dans l’ordre PAPS. Nous avons utilisé l’algorithme de l’horloge pour implémenter une solution plus rapide.

L’ARP Horloge d’Ensemble de travail

• Similaire à l’ARP de l’horloge, on garde une liste circulaire de touts les cadres de pages avec un pointeur à un de ces cadres

• Sur un défaut de page:Examine la page à laquelle on pointe. Si elle est utilisée

on met le bit à zéro, on met à jour le compteur et on avance à la prochaine entrée

Quand une entrée avec le bit d’utilisation 0 est trouvée on soustrait son temps de dernière utilisation du temps virtuel courrant. Si ce temps est plus grand que , et que la page est non modifiée, la page est écrite pardessus

L’ARP horloge ET

• Sur un défaut de page:Si une page est sale, une écriture au disque est commencée et

l’algorithme continue de chercher pour une page immédiatement disponible

• Pourquoi?

Si toutes les pages sont en ligne pour être écrites sur le disque, la main de l’horloge continue d’avancer pour trouver une page qui a été ‘nettoyée’

Si la main fait le tour complet des cadres, sans aucune écriture à être faite, cela indique que toutes les pages sont dans l’ensemble de travail

• On réclame tout simplement la première page propre qui est disponible

Quiz Time!

Questions?