Gestion de la mémoire

Définitions ...........................................................................................................................................2Mémoire centrale.............................................................................................................................2Unités de mesure :............................................................................................................................2Catégories de mémoires...................................................................................................................2

Gestion de la mémoire ........................................................................................................................4Registres de protection mémoire.....................................................................................................4Gestion de la mémoire physique......................................................................................................4

Partitions de taille fixe................................................................................................................4Partitions de tailles variables.......................................................................................................5Stratégie de placement................................................................................................................6Bilan provisoire...........................................................................................................................6

Mémoire virtuelle paginée....................................................................................................................7Définitions .....................................................................................................................................7

Mémoire paginée- cadres de pages.............................................................................................7Adresse virtuelle – table des pages.............................................................................................7

Conséquences de l'adressage virtuel................................................................................................8Mémoire virtuelle............................................................................................................................9

Algorithmes de remplacement de pages.............................................................................................10Algorithme de remplacement de la page non récemment utilisée.................................................10Algorithme de remplacement de page premier entré, premier sorti..............................................11L'algorithme de remplacement de page de la seconde chance.......................................................11L'algorithme de remplacement de page de l'horloge.....................................................................12L'algorithme de remplacement de la page la moins récemment utilisée.......................................13

Groupe esaip 1 document.doc

Définitions

Mémoire centrale

La mémoire centrale des ordinateurs est la mémoire accessible directement par le processeur.Cette mémoire contient à la fois les instructions de programmes et les données manipulées par ces programmes, que ces programmes soient des programmes utilisateurs ou des programmes systèmes.

La quantité de mémoire installable sur un ordinateur dépend de plusieurs paramètres :·l'espace maximum de mémoire accessible par le processeur (20 bits d'aédresse, 32 bits, 64bits ...)·la taille du bus système, c'est à dire le sous-ensemble de l'espace adressable effectivement câblé sur la carte mère de l'ordinateur·les emplacements disponibles sur la carte mère pour l'insertion des "barrettes de mémoire"·le type de barrettes utilisées: si 3 emplacements sont disponibles, il est peut-être possible d'installer 3x128 Mo ou 3x512 Mo

Unités de mesure :

La mémoire des ordinateurs se mesure en multiples de l'octets:

1 ko (kilo) 2 10 octets 1024 octets

1 Mo (méga) 2 20 octets 1024 Ko

1 Go (giga) 2 30 octets 1024 Mo

1 To (téra) 2 40 octets 1024 Go

Une adresse mémoire est l'adresse d'un octet en mémoire centrale (ou du premier octet d'une série d'octets d'adresses successives). Chaque octet de la mémoire a une adresse.

Catégories de mémoires

La mémoire RAM (random access mémory) est ainsi nommée car le temps d'accès à l'un quelconque des octets (choisi aléatoirement) est identique pour tous. Cette propriété n'est pas vérifiée pour les données sur disque.

La mémoire centrale peut aussi comporter une partie de mémoire ROM (read only memory) qui a surtout l'intérêt de ne pas être effacée lorsque l'ordinateur est mis hors tension. Un programme d'amorçage en mémoire ROM est nécessaire au démarrage de l'ordinateur.

Les temps d'accès à la mémoire ROM sont en général plus long que pour la mémoire RAM, il sera donc assez fréquent de recopier en mémoire RAM les informations de la mémoire ROM pour améliorer les performances. Cette mémoire qui est comme "l'ombre de la mémoire ROM" est quelquefois appelée "mémoire shadow"

Pour améliorer le temps d'accès aux données et instructions de la mémoire RAM, les processeurs disposent en général sur d'une mémoire plus rapide mais en quantité plus limitée: la mémoire cache. Cette mémoire contient les dernières informations utilisées par le processeur, et se révèle utile parce que les programmes utilisent en général plusieurs fois les mêmes instructions et données dans un brève période de temps.

Pour étendre la quantité de mémoire RAM on utilisera une partie de la mémoire de masse (en général le disque dur) pour stocker des informations de la mémoire qui ne seront pas utiles aux programmes actifs dans un horizon de temps limité. Cette mémoire s'appelle la mémoire d'échange (en anglais swap). Ceci permettra de "récupérer" l'espace RAM qu'utilisaient ces données ou instructions pour y enregistrer d'autres informations nécessaires aux programmes actuellement actifs.

Gestion de la mémoire

Registres de protection mémoireLa gestion de la mémoire centrale est réalisée par le système d'exploitation et vise à fournir aux applications l'espace de RAM nécessaire à leur exécution.

Un objectif supplémentaire mais tout aussi crucial est la protection des espaces mémoire des autres applications, et du système d'exploitation lui-même, contre la lecture ou la modification des données par un processus non autorisé.

En général un processus se verra allouer une espace de mémoire correspondant à des adresses successives: il pourra ainsi utiliser toute adresse de mémoire entre une valeur minimale et une valeur maximale; les autres adresses lui étant interdites.

Ce contrôle d'accès à la mémoire, pour être efficace, devra être réalisé par le processeur lui-même, qui disposera de 2 registres définissant les limites des adresses mémoire autorisées. Ces registres seront initialisés par l'ordonnanceur au moment où celui-ci active le processus.

Gestion de la mémoire physique

Partitions de taille fixeUne des premières méthode de gestion de la mémoire a été de définir des espaces mémoire de tailles fixes dans lesquelles seront installés les programmes d'application. Chaque programme a été compilé avec des adresses absolues en mémoire (adresses des instructions ou adresses des variables). Un programme ne peut donc être chargé que dans la partition pour laquelle il a été compilé. On définira en général autant de files d'attentes de programmes qu'il y a de partitions. Une partition ne peut contenir qu'un seul programme. Si le programme d'une partition se bloque sur une demande d'entrée/sortie, le système active le programme d'une autre partition.

Partitions de tailles variablesLa méthode précédente utilisait mal la mémoire car les programmes ne remplissaient pas en général la partition qui leur était allouée, sans que cet espace restant puisse être utilisé par un autre programme.

Deux évolutions majeures vont permettre de mieux gérer la mémoire:

·La génération de code relogeable par les compilateurs, associée à des chargeurs de code relogeable permettra de charger un programme à une adresse quelconque en mémoire.

·La définition de partitions de taille variable permettra d'adapter la taille des partitions aux besoins réels des programmes.

Stratégie de placementAu bout d'un certain temps les programmes en cours se terminent: sur l'exemple de cette figure les programmes A et C se sont terminés.

Si le choix de l'emplacement des premiers programmes n'a posé aucun problème (il suffisait de remplir la mémoire en répondant aux besoins des programmes), la question se pose dès qu'un programme se termine, en libérant un espace mémoire, du choix du meilleur emplacement disponible pour implanter en mémoire un nouveau programme.

On peut proposer 3 stratégies :

1.best-fit strategy : on choisit l'emplacement le plus petit parmi ceux qui sont assez grands pour les besoins du programme

2.first-fit strategy : on choisit le premier emplacement que l'on trouve et qui est suffisant pour satisfaire la demande (l'avantage est la rapidité de la décision)

3.worst fit strategy : on choisit le plus grand des emplacements, mais on récupère ce qui est au-delà des besoins du programme pour en faire un nouvel emplacement libre(alors que dsans les stratégies précédentes, si le bloc alloué est plus grand que la demande, l'excédent reste indisponible et inutilisé)

Au delà de ces stratégies de placement peut se poser le choix d'une restructuration des blocs mémoire qui permettrait en déplaçant les bloc alloués de réunir en un (ou plusieurs) blocs les différents blocs libres. Si la réunion de 2 blocs libres adjacents est quasi immédiate, la réunion de blocs libres qui imposerait d'en déplacer d'autres est une opération coûteuse en terme de temps processeur; on essaiera donc de la limiter le plus possible.

Bilan provisoire

Ces techniques de gestion de la mémoire n'ont plus qu'un intérêt historique et ne correspondent plus à la plupart des systèmes modernes. Elles gardent cependant leur actualité dans 2 contextes très actuels :

1.les systèmes "à objets" utilisent très intensivement l'allocation dynamiques de variables; ces variables ont souvent une durée de vie très courte, ce qui génère rapidement un espace mémoire "rempli de trous". Le choix de l'emplacement mémoire pour une nouvelle variable, ou le regroupement des espaces libres (garbage collection) gardent ici toute leur actualité (mais au lieu de l'espace mémoire du système, il s'agit de l'espace mémoire d'une application). La machine virtuelle Java a ainsi son propre "garbage collector".

2.les systèmes embarqués disposent souvent d'un espace mémoire très restreint, qui oblige à simplifier certains algorithmes du système; en contre partie, le nombre des applications appelées à s'exécuter et leurs besoins en mémoire sont mieux prévisibles; dans ce contexte, des algorithmes simplifiés (voire simplistes) de gestion de la mémoire peuvent devenir particulièrement intéressants.

Mémoire virtuelle paginée

Définitions

Mémoire paginée- cadres de pagesLa pagination consiste à découper la mémoire centrale en espaces de tailles fixes, par exemple une page mémoire fera 1Ko. L'allocation de mémoire aux processus se fait alors page par page: la page est l'unité d'allocation de mémoire aux processus.

Tout espace mémoire appartient donc désormais à une page, indépendamment de son contenu: ce "lieu de stockage" s'appelle un "cadre de page" ou "page frame" en anglais

Adresse virtuelle – table des pagesUn processus dispose désormais d'une méthode d'adressage de la mémoire déterminée par cette organisation: une adresse en mémoire est un couple (N°de page, N° d'octet dans la page)Il devient alors possible de déterminer un espace d'adressage virtuelle pour un processus: toutes les adresses mémoire référencées dans le programme de ce processus sont déterminée par un couple (N°de page, N° d'octet dans la page), avec un numéro de page commençant toujours à zéro.

Une table des pages est donc nécessaire pour déterminer à quelle numéro de page réelle (en mémoire physique) correspond tel numéro de page virtuelle:

Indice de la table des pages

= N° de la page virtuelle

N° de la page réelle contenant cette page

virtuelle

0 102

1 250

2 205

3 46

4 32

5 310

A chaque instruction machine référençant une variable ou une instruction, il est donc nécessaire de convertir (N° de page virtuelle, N° d'octet dans la page)en (N° de page réelle, N° d'octet dans la page)

Remarquons que dans cette conversion d'adresses, le numéro d'octet dans la page n'est pas changé.

Il reste une dernière conversion à réaliser pour passer en adresse physique :

adresse physique = (N° de page réelle) * taille de la page+ N° d'octet dans la page

Ces mécanismes de conversion pour être efficaces seront implantés dans le processeurCe qui veut dire aussi qu'une telle gestion de la mémoire nécessite un processeur adapté: une "unité de gestion de la mémoire" n'existe sur les processeurs Intel qu'à partir du 80386.

Conséquences de l'adressage virtuel

L'adressage virtuel offre de nombreux avantages :

1.Il n'y a plus de stratégie de placement: toute page disponible peut être allouée à un processus, et toutes les pages sont équivalentes en terme de performance.

2.Il n'y a plus besoin d'algorithme de "récupération des espaces libres", "garbage collector", car toutes les pages sont toujours utilisables

3.L'espace alloué à un processus peut être adapté à sa demande (à la taille d'une page près) et même varier au cours de la vie du processus de manière très simple.

4.L'espace mémoire d'un processus, en termes d'adresse virtuelles est toujours constitué d'adresses successives, ce qui simplifie les mécanismes de protection mémoire (adresse virtuelle de base, ici toujours zéro, et taille de l'espace alloué)

5.Une même page de mémoire réelle peut très facilement être partagée par 2 processus (ou plus) par l'intermédiaire de la table des pages

Mémoire virtuelle

L'adressage virtuel permettra aussi de gérer de manière efficace la mémoire d'échange: extension sur le disque de la mémoire centrale.

En effet dans la table des pages, il suffira d'indiquer

·si la page virtuelle est actuellement en mémoire centrale, dans un cadre de page qui lui aura été assigné par le système

·ou si le contenu de cette page virtuelle est au contraire sur disque, dans l'espace de "swap"

Si le programme en cours d'exécution fait référence à une adresse de page virtuelle sur disque, la processeur qui réalise la conversion des adresses virtuelles en adresse physiques générera une "exception pour défaut de page": une interruption matérielle, qui aura les conséquences suivantes :

1.Blocage du processus en cours, pour une opération d'entrées/sortie particulière qui consistera à recharger la page absente en mémoire principale.

2.Démarrage d'un processus système de remplacement de page qui devra sélectionner pour la page manquante un cadre de page disponible, ou libérer un des cadres de pages occupés, en recopiant son contenu dans la mémoire d'échange. Quelle page sélectionner sera la question des algorithmes de remplacement de page décrits dans le chapitre suivant.

3. Allocation du processeur à un autre processus prêt

Lorsque la page absente sera de nouveau disponible en mémoire, le processus bloqué redeviendra prêt.

Algorithmes de remplacement de pages1

Algorithme de remplacement de la page non récemment utilisée

Afin de permettre au système d'exploitation de collecter des statistiques utiles sur le nombre de pages utilisées et le nombre de pages inutilisées, la plupart des ordinateurs avec de la mémoire virtuelle possèdent 2 bits d'état associés à chaque page. Le bit R est mis à 1 à chaque fois que la page est référencée (lue ou écrite) et le bit M est mis à 1 quand la page est ré-écrite (c'est-à-dire modifiée). Ces bits sont contenus dans chaque entrée de la table des pages.

·Il est important de réaliser que ces bits doivent être mis à jour à chaque référence mémoire, et qu'il est donc essentiel que cette mise à jour soit matérielle. ·Lorsqu'un bit a été mis à 1, il reste à 1 jusqu'à ce que le système d'exploitation le remette à 0 de manière logicielle.

Si le matériel ne dispose pas de ces bits, ils peuvent être simulés de la manière suivante. Quand un processus démarre, toutes les entrées de ses pages sont marquées comme non présentes en mémoire. Dès qu'une page est référencée, un défaut de page est généré. Le système d'exploitation met à 1 le bit R (dans ses tables internes), change l'entrée de la table des pages pour pointer sur la bonne page, avec un mode lecture seule, et recommence l'instruction. Si la page est réécrite par la suite, un autre défaut de page est généré, autorisant le système d'exploitation à mettre à 1 le bit M et à changer le mode d'accès à la page en lecture/écriture.

Les bits R et M peuvent servir à construire un algorithme simple de pagination comme décrit ci-après. Quand un processus démarre, les 2 bits de page pour toutes ses pages sont mis à 0 par le système d'exploitation. Périodiquement (par exemple à chaque interruption d'horloge), le bit R est effacé, afin de distinguer les pages qui n'ont pas été récemment référencées de celles qui l'ont été.

Quand un défaut est généré, le système d'exploitation examine toutes les pages et les sépare en deux catégories basées sur les valeurs courantes des bits R et M:

[ 0 0 ] Classe 0. Non référencée, non modifiée. [ 0 1 ] Classe 1. Non référencée, modifiée.[ 1 0 ] Classe 2. Référencée, non modifiée.[ 1 1 ] Classe 3. Référencée, modifiée.

Bien que l'existence de pages de classe 1 semble impossible elles apparaissent dans cet état lorsque le bit R d'une page de classe 3 est effacé par une interruption d'horloge. Les interruptions d'horloge n'effacent pas le bit M parce que cette information est nécessaire pour savoir si la page a été réécrite sur le disque ou pas. Si le bit R est effacé mais pas le bit M, cela aboutit à une page de classe 1.

L'algorithme de la page non récemment utilisée ou NRU (Not Recently Used) enlève une page au hasard dans la classe la plus basse non vide. Avec cet algorithme, il est implicite qu'il vaut mieux enlever une page modifiée qui n'a pas été référencée au moins dans un top (typiquement 20 ms) plutôt qu'une page bonne (clean) qui est beaucoup utilisée. L'attrait principal de l'algorithme NRU est qu'il est facile à comprendre, relativement simple à implanter, et qu'il donne des performances qui, sans être optimales, sont suffisantes.

1 Cf Andrew Tanenbaum "Systèmes d'exploitation" – ed Pearson Education

Algorithme de remplacement de page premier entré, premier sorti

Un autre algorithme de pagination est l'algorithme premier entré, premier servi ou FIFO (First-In, First-Out, premier entré, premier sorti).

Le système d'exploitation maintient une liste de toutes les pages actuellement en mémoire, la page la plus ancienne étant en tête de liste et la page la plus récente en queue. Dans le cas d'un défaut de page, la page en tête de liste est effacée et la nouvelle page ajoutée en queue de liste.

Quels inconvénients peut avoir cette politique ?

L'algorithme de remplacement de page de la seconde chance

On peut apporter une modification simple à l'algorithme FIFO afin d'éviter la suppression d'une page à laquelle on a couramment recours : il s'agit d'inspecter le bit R de la page la plus ancienne. S'il est à 0, la page est à la fois ancienne et inutilisée, elle est donc remplacée immédiatement. Si le bit R est à 1, le bit est effacé, la page est placée à la fin de la liste des pages, et son temps de chargement est mis à jour comme si elle venait d'arriver en mémoire. La recherche continue alors.

L'opération de cet algorithme, appelée seconde chance, est illustrée ci-dessous nous voyons que les pages de A à H se trouvent dans une liste chaînée, triées par leur temps d'arrivée en mémoire.

Supposons qu'un défaut de page se produise à l'instant 20. La page la plus ancienne est A, qui est arrivée à l'instant 0, quand le processus a démarré. Si le bit R de la page A est à 0, elle est évincée de la mémoire: elle est soit écrite sur le disque (si elle est modifiée), soit simplement abandonnée (si elle est restée identique à la page sur disque). D'un autre côté, si le bit R est à 1, A est placée à la fin de la liste et son temps de chargement est mis à jour avec le temps courant (20). Le bit R est aussi mis à 0. La recherche d'une page convenable continue alors avec B.

Opération de la seconde chance.(a) Pages triées dans un ordre FIFO.(b) Liste de pages lorsqu'un défaut de page se produit à l'instant 20 et que le bit R de A est à 1. Les nombres au-dessus des pages correspondent à l'instant de leur chargement.

Le travail de l'algorithme de la seconde chance consiste à chercher une ancienne page qui n'a pas été référencée dans le précédent intervalle d'horloge. Si toutes les pages ont été référencées, l'algorithme de la seconde chance dégénère en pur algorithme FIFO. Pour être concrets, imaginons que toutes les pages de la figure 4.16(a) ont leur bit R à 1. Le système d'exploitation déplace une par une les pages à la fin de la liste, effaçant le bit R chaque fois qu'il ajoute une page à la fin de la liste. Finalement, il revient à la page A, dont le bit R est maintenant à 0. À ce moment-là, A est évincée. Ainsi, cet algorithme se termine toujours.

L'algorithme de remplacement de page de l'horloge

Bien que l'algorithme de la seconde chance soit un algorithme satisfaisant, il manque d'efficacité parce qu'il déplace constamment des pages dans sa liste. Une meilleure approche consiste à garder tous les cadres de pages dans une liste circulaire formant une horloge, comme l'illustre la figure ci-dessous. Un pointeur se trouve sur la page la plus ancienne.

Quand un défaut de page survient, la page pointée est examinée. Si son bit R est à 0, la page est évincée, la nouvelle page est insérée dans l'horloge à sa place, et le pointeur est avancé d'une position. Si le bit R est à 1, il est effacé et le pointeur est avancé sur la prochaine page. Ce processus est répété jusqu'à ce qu'une page R = 0 soit trouvée. Cet algorithme de l'horloge diffère de l'algorithme de la seconde chance uniquement dans son implantation.

L'algorithme de remplacement de la page la moins récemment utilisée

Pour s'approcher au mieux de l'algorithme optimal, il faut se fonder sur l'observation suivante : les pages les plus référencées lors des dernières instructions seront probablement très utilisées dans les prochaines instructions. À l'inverse, des pages qui n'ont pas été employées depuis longtemps ne seront pas demandées avant un long moment. On peut en déduire l'algorithme suivant: quand un défaut de page se produit, c'est la page qui n'a pas été utilisée pendant le plus de temps qui est retirée.

Cette méthode est appelée pagination LRU (Least Recently Used, la moins récemment utilisée).Cet algorithme LRU est réalisable mais reste coûteux. Pour l'implanter totalement, il est nécessaire de gérer une liste chaînée de toutes les pages en mémoire, avec la page la plus récemment utilisée en tête et la moins utilisée en queue. La difficulté est que cette liste doit être mise à jour à chaque référence mémoire. La recherche d'une page dans la liste, sa destruction et son déplacement en début de liste sont des opérations coûteuses en temps, même si elles sont réalisées de manière matérielle (en supposant qu'un tel matériel existe)

Cependant, il existe d'autres manières d'implanter cet algorithme avec des composants matériels particuliers. Considérons la plus simple d'entre elle. Cette méthode nécessite d'équiper le matériel avec un compteur 64 bits, c, qui s'incrémente automatiquement après chaque instruction. Par ailleurs, chaque entrée de la table des pages doit avoir un champ assez grand pour contenir ce compteur. Après chaque référence mémoire, la valeur courante de c est enregistrée dans l'entrée de la table des pages pour l'entrée qui vient d'être référencée. Quand un défaut de page se produit, le Système d'exploitation examine tous les compteurs dans la table des pages afin de trouver le plus petit d'entre eux. Celui-ci correspond à la page la moins récemment utilisée.

Examinons à présent une deuxième solution matérielle. Pour une machine à n cadres de pages, le matériel doit gérer une matrice de n x n bits, initialement tous nuls. Quart une page k est référencée, le matériel commence par mettre à 1 tous les bits de la rangée k et tous les bits de la colonne k à 0. À chaque instant, la rangée dont la valeur binaire est la plus petite indique la page la moins récemment utilisée.