Systèmes d’Exploitations Avancés

Chapitre VI :

Gestion de la mémoire

Amine DHRAIEF

Mastère professionnel en Modélisation, Bases de

Données et Intégration des Systèmes

ESEN, Univ. Manouba

Introduction

Les programmes s’accroissent pour

remplir la mémoire disponible qui leur

est réservée

12/15/16

Introduction

• Souhaits des programmeurs

– Une mémoire infiniment grande

– Une mémoire infiniment rapide

– Non volatile

– Bon marché !

– Frein technologique → hiérarchie de la mémoire

• hiérarchie de la mémoire

– Quelques MB de mémoire cache volatile, rapide et chère

– Quelques GB de mémoire rapidité moyenne, prix moyen

– Quelques TB de mémoire non volatile, lente, mémoire de

masse

12/15/16

Introduction

• Gestionnaire de la mémoire :Entité

du S.E qui gère hiérarchie de la

mémoire

– Garde trace de la partie de la mémoire qui est

en cours d’utilisation et celle qui ne l’est pas

– Allouer de la mémoire au processus

– Libérer la mémoire à la fin de l’exécution des

processus

12/15/16

Abstraction de la mémoire ?

• Avant 1980: on ne disposait pas d’abstraction

– MOV REGISTER1, 1000

– on fait passer le contenu de l’emplacement mémoire 1000 dans

le registre REGISTER1

– Il n’était pas possible d’exécuter deux programmes en même

temps

• Le modèle de mémoire présenté au programmeur

correspondait tout simplement à la mémoire physique

– Un ensemble d’adresse numérotées de 0 à une valeur maximale

– Chaque adresse désignant une cellule contenant un certain

nombre de bit (8 bits)

12/15/16

Abstraction de la mémoire ?

• Même si le modèle ne reflète que la mémoire physique, il peut exister

plusieurs variantes

– (a) S.E en bas de la mémoire vive RAM (n’est plus utilisé)

– (b) S.E en haut de la ROM (système embarqué)

– (c) gestionnaire des périphérique en haut de la ROM (BIOS), S.E en RAM

(MSDOS)

• Le modèle (c) représente un inconvénient majeur: un bogue dans un

programme utilisateur peut engendrer des conséquences

désastreuse sur le S.E.

12/15/16

Abstraction de la mémoire ?

• Un seul processeur peut s’exécuter à la fois. Dès

que l’utilisateur tape une commande

– Le S.E copie le programme demandé depuis le

disque vers la mémoire et l’exécute

– Lorsque le processus se termine, le S.E affiche le

prompt et attend une nouvelle commande

– Quand il reçoit la commande, il charge un nouveau

programme en mémoire en écrasant le précédent

12/15/16

L’exécution de plusieurs programmes

sans abstraction de mémoire

• Même sans abstraction de la mémoire, il est

cependant possible d’exécuter quasi

simultanément plusieurs programmes.

• Le S.E. doit alors recopier sur disque

l’intégralité du contenu de la mémoire avant

de charger et d’exécuter le programme suivant

• C’est le va-et-vient ou swapping

12/15/16

UNE ABSTRACTION DE LA MÉMOIRE:

LE ESPACES D’ADRESSAGE

12/15/16

Contexte

• Faire voire aux processus la mémoire physique

présente plusieurs inconvénients

– Risque de plantage générale, même avec un seul

programme qui s’exécute

– Lourdeur pour exécuter plusieurs programmes à la

fois

• Besoin d’abstraction de la mémoire

12/15/16

La notion d’espace d’adressage

• De la même façon qu’un processus crée une

UC abstraite exécutant un programme, l’espace

d’adressage est une sorte de mémoire abstraite

d’un programme prêt à l’exécution

• C’est l’ensemble des adresses qu’un processus

peut utiliser pour adresser la mémoire

• Chaque processus a son propre espace

d’adressage, indépendant de celui des autres

12/15/16

La notion d’espace d’adressage

• Il est difficile de donner à chaque

programme son propre espace

d’adressage

– C’est-à-dire de faire en sorte que l’adresse

(abc) de l’un correspond à un emplacement

différent de l’adresse (abc) de l’autre

• Solution: ré-allocation dynamique

12/15/16

La notion d’espace d’adressage

12/15/16

Les registres de base et de limite

• Ré-allocation dynamique: mapper l’espace

d’adressage de chaque processus sur une

partie différente de la mémoire physique.

• Équiper les UC de deux registres matériels:

les registres de base et de limite.

– Les programmes sont chargés en mémoire sans

ré-allocation, là où il y a de la place pour les ranger

dans des mots mémoire consécutifs

12/15/16

Les registres de base et de limite

• À l’exécution du programme, le S.E

range dans le registre de base

l’adresse physique de début de

programme et dans le registre de limite

et celle de fin

– Les valeurs de base et de limite du premier

programme sont de 0 et 16384 (16Ko x 1024

= 16384)

– Du second programme 16384 et 32768

12/15/16

Les registres de base et de limite

• Chaque fois qu’un processus référence

la mémoire,

– que ce soit pour charger une instruction ou bien

lire ou écrire une donnée,

– le matériel de l’UC ajoute automatiquement à

l’adresse engendrée par le programme la valeur

du registre de base

– et vérifie la nouvelle adresse ainsi créée reste

bien inférieur ou égale à la valeur du registre de

limite

12/15/16

Les registres de base et de limite

• Dans le cas de la première instruction du second

programme exécute une instruction

– JMP 10

• Le matériel la traite comme si c’était

– JMP 16394

– 16394 = 16384 +10

• L’inconvénient majeur de cette méthode est qu’elle

exige une addition et une comparaison à chaque

référence mémoire

12/15/16

Le va-et-vient (swapping)

• Si la mémoire physique de l’ordinateur est

suffisamment grande pour contenir tous les

processus, les méthodes vues jusqu’ici

conviennent.

– En pratique, c’est rarement le cas

– Sur les S.E. actuelles, entre 40 et 60 processus sont

lancés au démarrage

– Sous windows, un processus de vérification de mise à

jour d’une application, lancée au démarrage occupe

entre 5 et 10 Mo!

– Firefox peut occuper facilement 270Mo de mémoire

12/15/16

Le va-et-vient (swapping)

• Deux approches de gestion de

mémoire peuvent être utilisées

– Le swapping: considérer chaque processus

dans son intégralité, exécution puis

placement sur le disque

– La mémoire virtuelle: permet au

programmes de s’exécuter même quand ils

sont partiellement en mémoire principale

12/15/16

Le va-et-vient (swapping)

• L'allocation de la mémoire change au gré des processus

qui viennent en mémoire et ceux qui quittent la mémoire

• Les zones grises indiquent la mémoire non utilisée

12/15/16

Le va-et-vient (swapping)

(a) A est en mémoire

ii.

(b,c) B et C sont crées

ou chargés depuis le

disque

iii. (d) A est transférer sur le

disque

iv. (e,f) D arrive, tandis que

B s’en va

(g) A revient

12/15/16

Le va-et-vient (swapping)

• Lorsque le swapping crée de multiples trous

dans la mémoire, il est possible de tous les

recombiner en une seule zone plus grande en

déplaçant tous les processus vers le bas de

la mémoire aussi vite que possible

– Compactage de mémoire

• N’est pas mise en œuvre car elle requiert

énormément de temps UC

– 5s pour compacter 1 Go!

12/15/16

Le va-et-vient (swapping)

• Si des processus sont crées avec une taille fixe qui

ne change jamais, l’allocation est alors simple: le

système alloue exactement la mémoire nécessaire

pas plus pas moins !

• Lorsque les segments de données des processus

doivent croître (allocation dynamique de la mémoire)

un problème surgit toutes les fois qu’un processus

essaie de s’accroître.

– Si un trou est adjacent au processus, ce trou peut lui être

alloué et le processus est autorisé à s’étendre dedans

12/15/16

Le va-et-vient (swapping)

• Si le processus est adjacent à un autre processus, le

processus croissant devra être déplacé dans un trou

suffisamment grand pour lui

• Si un processus ne peut pas croître en mémoire et que

la zone de va-et-vient sur le disque est pleine, le

processus devra attendre ou être tué

– Il est conseillé d’allouer un ‘peu’ de mémoire supplémentaire

chaque fois qu’un processus est chargé ou déplacé

– Si on transfert le processus sur le disque, seule la mémoire

véritablement utilisé qui doit être recopiée, inutile de recopier

la mémoire supplémentaire.

12/15/16

Gérer la mémoire libre

• Quand la mémoire est attribué

dynamiquement, le système

d’exploitation doit la gérer

• Il existe deux manière de conserver

une trace de l’utilisation de la mémoire

– À l’aide des tables bits

– À l’aide des listes

12/15/16

Gérer la mémoire avec une table de

bits

• Avec une table de bits, la mémoire est

répartie en unités d’allocation dont la

taille peut varier de quelques mots à

plusieurs kilo-octets.

• Chaque unité d’allocation correspond à

un bit du tableau de bits, lequel est 0 si

l’unit correspondante est vide et 1 si elle

est occupée (ou vice versa)

12/15/16

Gérer la mémoire avec une table de

bits

a) Une partie de la mémoire avec 5 processus, 3 trous

Les petites marques verticales indiquent les unités

d'allocation

Les zones grises sont libres

b) Le tableau de bits correspondant

c) Mêmes informations sous la forme d'une liste chaînée

12/15/16

Gérer la mémoire avec une table de

bits

• La taille de l’unité d’allocation est un élément

fondamentale dans la configuration:

– plus l’unité est petite, plus le tableau de bit est

important

• Avec une unité de 4 octets (32bits), n’auront

besoin que de 1 bit du tableau de bit

– Une mémoire de 32n bits utilisera une table de n

bits qui ne prendra pas plus de 1/33 de la mémoire

12/15/16

Gérer la mémoire avec une table de

bits

• Le tableau de bit offre un moyen simple de

garder une trace des mots mémoire dans

une quantité fixe de mémoire

• Le tableau offre un inconvénient:

– lorsqu’un processus de k unités est chargé en

mémoire, le gestionnaire de mémoire doit

parcourir le tableau de bits pour trouver une

séquence de k bit consécutifs dont la valeur est

12/15/16

Gérer la mémoire avec des listes

chaînées

• Une des manière de conserver une trace de la

mémoire est de maintenir une liste chaînée des

segments de mémoire alloués et libres

– Dans cette liste, un segment est soit un processus, soit un

trou entre deux processus

– La liste est trié par adresse, donc si un processus se

termine la mise à jour est directe

12/15/16

Gérer la mémoire avec des listes

chaînées

• Un processus qui se termine a normalement deux

voisins (excepté en début de liste/fin de liste) qui

peuvent être des processus ou des trous, ce qui

conduit à quatre combinaison possibles

12/15/16

Gérer la mémoire avec des listes chaînées

•

(a) la mise à jours de la liste

oblige à remplacer un P par un T

(b,c) deux unités sont réunies

en une seule, la liste devient

plus courte d’une unité

(d) trois entrées sont fusionnées

et deux items sont retirés de la

liste

• → Il y a avantage a utiliser une

liste de segments doublement

chaînée afin de faciliter la

recherche du nœud précédent.

12/15/16

Gérer la mémoire avec des listes

chaînées

• Quand les processus et les trous sont indiqué

dans une liste triées par adresse, plusieurs

algorithmes peuvent servir à allouer de la

mémoire à un processus nouvellement créé (ou

un processus existant chargé depuis le disque)

– First fit

– Next fit

– Best fist

– Worst fit

– Quick fit

12/15/16

Gérer la mémoire avec des listes chaînées

First Fit

• Algorithme de la première zone libre:

– On trouve le premier trou suffisamment grand

pour contenir le processus.

– Le trou est ensuite divisé en deux parties: une

pour le processus et l’autre pour la mémoire

inutilisée

• Algorithme rapide parce qu’il limite ses

recherches autant que possible

12/15/16

Gérer la mémoire avec des listes chaînées

Next Fit

• Algorithme de la première zone libre

– Identique à l’algorithme précédent sauf que la

recherche commence au dernier espace libre

trouvé.

– Les performance sont légèrement meilleures

12/15/16

Gérer la mémoire avec des listes chaînées

Best Fit

• Algorithme du meilleur ajustement

– Parcourt toute la liste et recherche le plus

petit trou pouvant contenir le processus.

– Évite de partitionner inutilement les gros trous

– Cet algorithme crée des trous minuscules

inutilisables par la suite

– Plus lent que les algorithmes précédents

12/15/16

Gérer la mémoire avec des listes chaînées

Worst Fit

• Algorithme du plus grand résidu

– On prend le plus grand trou disponible

– Le trou restant est assez grand pour être

réutilisé

– Des simulations démontrent que cette

solution n’est pas meilleure que la

précédente.

12/15/16

Gérer la mémoire avec des listes

chaînées

• On peut utiliser deux listes distinctes (zones libres et

occupées par un processus)

• Accélère les algorithmes précédents

– Si la liste des trous est triée par taille alors best-fit et first-fit sont

essentiellement équivalents.

• Ralentissement quand la mémoire est libérée

– Un segment libéré est enlevé de la liste des processus et inséré dans la

liste des trous

• On peut utiliser les zones libres elle même pour la liste des

zones libres

12/15/16

Gérer la mémoire avec des listes chaînées

Quick Fit

• Algorithme du placement rapide (quick fit)

– On gère des listes séparées pour certaines des tailles les

plus communes

– Par exemple, on peut avoir des listes de 4Ko, 8Ko, 12Ko, etc.

– Très rapide.

– Rend plus complexe le processus de libération de la

mémoire: On doit chercher les trous adjacents pour une

vérifier si une fusion est possible.

• Tous ces algorithmes souffrent du problème de la

fragmentation de la mémoire.

12/15/16

Application #1

12/15/16

Application #1

● Considérons un système de gestion de mémoire à

partitions variables avec la liste des trous suivante

(ordonnée par adresses croissantes) : 10K, 4K, 20K,

18K, 7K, 9K, 12K et 15K.

● Supposons les demandes successives d'espace

mémoire :A= 12K, B= 10K et C= 9K.

● Indiquer pour les stratégies First Fit, Next Fit, Best

Fit et Worst Fit l'état de cette liste après l'allocation

des espaces pour les demandes de A, B et C.

12/15/16

Solution Application #1

● First fit : on cherche le premier espace

qui convient

10k

20k

18k

12k

15k

10k

18k

12k

15k

12/15/16

12k

10k

18k

12k

15k

12k

15k

Solution Application #1

● Next Fit : on cherche l’espace suivant

qui convient

10k

20k

18k

12k

15k

10k

20k

12k

15k

10k

12k

15k

12/15/16

12k

10k

12k

15k

Solution Application #1

● Best fit : on cherche l’espace qui laisse

le plus petit trou

10k

20k

18k

12k

15k

12/15/16

12k

10k

20k

18k

15k

10k

20k

18k

15k

20k

18k

15k

Solution Application #1

● Worst fit : on cherche l’espace qui

laisse le plus grand vide

10k

20k

18k

12k

15k

10k

18k

12k

15k

10k

12k

15k

12/15/16

12k

10k

12k

LA MÉMOIRE VIRTUELLE

12/15/16

La mémoire virtuelle

• Si la taille des mémoires augmente, celle des

logiciels augmente encore plus vite

– Dans les années 1980, on faisait tourner en temps partagé

des dizaine d’utilisateurs sur des VAX dotés de 4Mo.

– Vista/Seven (mono-utilisateur) recommande au minimum 1

• On est sûr d’être à court de mémoire

– Le swapping n’est pas une bonne option en raison des

volumes à transférer: il faut au moins 10s pour mettre un

programme de 1 Go sur un disque SATA au débit crête de

100Mo/s

12/15/16

La mémoire virtuelle

• Le problème de programme plus gros que la mémoire

est connu depuis longtemps

• Dans les années 1960, la solution la plus courante

consistait à diviser le programme en parties, appelées

segments de recouvrement (overlay)

– Le segment 0 était exécuté en premier

– Quand cela était réalisé, il pouvait appeler un autre

segment

– Le va-et-vient est géré par le système, la division en

overlay est géré par le programmeur!

– Solution rapidement abandonnée

12/15/16

La mémoire virtuelle

• La méthode qui a été imaginée est connue aujourd’hui sous le

nom de mémoire virtuelle.

• La mémoire virtuelle repose sur le principe suivant: chaque

programme a son propre espace d’adressage découpé en petites

entités appelées pages, entités formées d’une suite d’adresse

contiguës

– La taille des page est fixe (typiquement entre 512 octets à 64Ko)

• Les pages sont mappées sur la mémoire physique, mais il n’est

pas obligatoire d’avoir toutes les page en mémoire physique pour

exécuter le programme.

12/15/16

La pagination

• Les adresses générées par programme sont

appelées des adresses virtuelles et elle

forment l’espace d’adressage virtuel

• Dans les ordinateurs sans mémoire virtuelle,

l’adresse est placée directement sur le bus

mémoire et provoque la lecture ou l’écriture

du mot de même adresse physique

• Dans les ordinateurs avec mémoire virtuelle,

l’adresse est placée dans une unité de

gestion mémoire (MMU Memory Mangement

Unit) qui fait correspondre les adresses

virtuelles à des adresses physiques

• La relation entre les adresses virtuelles et

physiques est indiquée dans la table des

pages

12/15/16

La pagination

• Un ordinateur peut produire de adresses

sur 16 bits avec des valeurs comprises

entre 0 et 64Ko: ce sont les adresses

virtuelles.

• Toutefois, cet ordinateur a seulement

32Ko de mémoire physique;

– par conséquent, même s’il permet d’ écrire

des programmes de 64Ko, ceux-ci ne

peuvent pas être chargés entièrement dans

la mémoire et exécutés.

– Il faut cependant qu’une copie complète de

tout le programme soit présente sur le

disque, afin que les différentes parties

puissent être récupérer quand cela est

nécessaire

12/15/16

La pagination

• L’espace d’adressage virtuel est

divisé en unités appelées pages

• Les unités correspondantes dans

la mémoire physique sont

appelées cadres de pages (pages

frames)

– Les pages et les cadres de pages

ont toujours la même taille (4Ko

dans notre exemple)

– Chaque page est indivisible: Elle est

entièrement en mémoire physique

ou elle n’y est pas du tout.

12/15/16

La pagination

• L’indication 0K-4K signifie que

les adresse virtuelles ou réelles

de la page sont situées entre 0

et 4095

• L’indication 4K-8K entre 4096-

8191

• Chaque page contient 4096

adresses qui démarrent à un

multiple de 4096 et finissent au

multiple suivant

12/15/16

La pagination

L’adresse virtuelle 0 est

transformée en adresse

physique 8192=2*4096

L’adresse virtuelle 8192=2*4096

est transformée en adresse

physique 24576=6*4096

L’adresse virtuelle

20500=5*4096+20 est

transformée en adresse

physique 12308=3*4096+20

12/15/16

La pagination

• Quand le programme essaie par exemple

d’accéder à l’adresse 0, à l’aide de

l’instruction

– MOV REG,0

• L’adresse virtuelle 0 est envoyée à la

MMU. La MMU constate que cette adresse

virtuelle tombe dans la page 0 ( de valeurs

comprises entre 0 et 4095), laquelle

correspond au cadre de la page 2 ( de

valeurs comprises entre 8192 et 12287)

– Elle transforme l’adresse en 8192 et la

présente sur le bus

• La mémoire ne sait rien de la MMU: elle

interprète seulement qu’il s’agit d’une

requête de lecture ou d’écriture à

l’adresse 8192, et elle le réalise.

12/15/16

La pagination

• Cette capacité de mettre en

correspondance les 16 pages virtuelles

sur les 8 cadres de pages ne résout pas

le problème posé par un espace

d’adressage virtuel plus grand que la

mémoire physique

• Seule 8 des pages virtuelles sont mise

en correspondance avec la mémoire

physique

• Un bit de présence/absence conserve la

trace des pages qui se trouvent

physiquement en mémoire

• Que se passe-t-il si le programme

essaye de faire appel à une page non

présente avec l’instruction MOV

REG,32780 ????

12/15/16

La pagination

• MOV REG,32780 correspond à l’octet 12 de

la page virtuelle 8 (qui commence à 32768)

• La MMU remarque que la page est absente

(ce qui est indiqué par une croix dans la

figure) et fait procéder l’UC à un

déroutement, c’est-à-dire que le processeur

est restitué au système d’exploitation

• Ce déroutement, appelé défaut de page

(page fault), est réalisé de la manière

– Le système d’exploitation sélectionne un cadre

de page peu utilisé

– et écrit son contenu sur le disque;

– il transfère ensuite la page qui vient d’être

référencée dans le cadre de page libéré,

– modifie la correspondance et recommence

l’instruction déroutée.

12/15/16

La pagination

• Par exemple, si le système d’exploitation

décide de déplacer le cadre de la page 1

– Il doit charger la page virtuelle 8 à l’adresse

physique 4K et faire deux correspondance dans la

MMU.

• Tout d’abord, il doit marquer l’entrée de la

page virtuelle 1 comme étant non utilisée,

afin d’autorisé tout accès ultérieur aux

adresses virtuelles comprise entre 4K et 8K

• Ensuite il devra remplacer la croix de l’entrée

de la page 8 par la valeur 1

• Enfin, quand l’instruction déroutée sera ré-

exécutée, il mettra l’adresse virtuelle 32780

en correspondance avec l’adresse physique

4108 (4096 +12)

12/15/16

La pagination: fonctionnement interne d’une MMU

• Adresse virtuelle 8196, en

binaire 0010000000000100

est divisée en deux

parties

– Un numéro de page sur 4

bits et un décalage sur 12

bits

– Avec 4 bits pour le numéro

de page nous pouvons

avoir 16 pages

– Avec 12 bits pour le

décalage, nous pouvons

adresser l’ensemble des

4096 octets d’une page

12/15/16

La pagination: fonctionnement interne d’une MMU

• Le numéro de page est

utilisé comme un index

dans la table des pages:

– Le numéro du cadre de

page correspond à la page

virtuelle

• Si le bit de

présence/absence est à

0, un déroutement vers le

système d’exploitation

est mis en place

12/15/16

La pagination: fonctionnement interne d’une MMU

• Si le bit est à 1,

– le numéro de cadre de page trouvé

dans la table des page et copié

dans les 3 bits de poids le plus fort

du registre de sortie

– auxquels sont ajoutés les 12 bits de

décalage, qui sont copié à partir de

l’adresse virtuelle entrante sans

être modifiée

– ils forment ensemble une adresse

physique sur 15 bits

• Le registre de sortie est ensuite

placé sur le bus mémoire en tant

qu’adresse de mémoire physique

12/15/16

Les tables de pages

• Le rôle d’une table des pages est ainsi de faire

correspondre des pages virtuelles à des cadres de page

– C’est une fonction qui a comme argument le numéro de la

page virtuelle et comme résultat le cadre physique

– Le résultat de cette fonction peut servir à remplacer le champ

nommé page virtuelle d’une adresse virtuelle par un champ

nommée cadre de page et à créer ainsi une adresse mémoire

physique

• Deux problèmes:

– La table des pages peut être très grande

– Trouver l'adresse réelle à partir de l'adresse virtuelle doit se

faire très rapidement

12/15/16

Récapitulons :

• Dans le cas le plus simple, la mise en correspondance des adresses virtuelles et

des adresses physiques se déroule comme suit

– L’adresse virtuelle est séparée en deux parties

– Un numéro de page virtuelle (les bits de poids fort)

– Et un décalage (les bits de poids faible)

• Avec une adresse de 16 bits et une taille de page de 4 Ko,

– les 4 bits de poids fort peuvent spécifier une des 16 pages virtuelles,

– les 12 bits de poids faible indiqueront alors le décalage en octet ( de 0 à 4095)

• Dans la table des pages, le numéro de page virtuelle sert à trouver l’entrée de la

page virtuelle.

– S’il existe, le numéro du cadre de page est trouvé à partir de cette entrée de la table des pages

• Le numéro du cadre de page est attribué aux bits de poids fort suivi du décalage,

remplaçant le numéro de page virtuelle, pour composer une adresse physique qui

peut être envoyée à la mémoire

12/15/16

Structure d’un entrée de table de page

• Le champ le plus important est le numéro de cadre de page

– L’objectif est de localiser cette valeur

• Présent/Absent:

– si 0 cela provoque un défaut de page

– Si 1, l’entrée est valide et peut être utilisé

• Protection: précise quelles sortes d’accès sont permis

– lecture, écriture, exécution

12/15/16

Structure d’un entrée de table de page

• Modifié (dirty/clean bit) :

– Si aucune modification (clean), il n’est pas nécessaire de sauvegarder sur le disque. Lors d’une

écriture (dirty), automatiquement mis à 1

• Référencé:

– Mis à 1 chaque fois qu’une page est consultée

– Permet de décider si la page peut être remplacer par une autre

– Les pages qui ne sont pas en cours d’utilisation sont de meilleures candidates que les autres

• Cache inhibée:

– Caractéristique importante pour les pages qui sont mises en correspondance dans des registres

matériel plutôt qu’en mémoire

– Utile pour les attentes de réponse d’E/S on veut accéder aux données du périphérique plutôt qu’au

cache

12/15/16

Application #2

12/15/16

Exercice 1 : Pagination Simple

Sur un système de pagination simple de 2¹ octets de

mémoire physique de 2¹² pages d'espace d'adressage

virtuel et une taille de page de 4 ko (=4096 octets).

⁶

1) Combien de bits se trouvent dans une adresse virtuelle ?

2) Combien d'octets se trouvent dans un cadre de page ?

3) Combien de bits de l'adresse physique spécifient le cadre de page ?

4) Combien d'entrées se trouvent dans la table de pages ?

5) Combien de bits sont nécessaires pour stocker une entrée dans la table de

pages (de quelle largeur est la table de pages) ?

● Hypothèse :

– Chaque entrée de table de pages contient, en plus du numéro de cadre de page, 1

bit de présence (P), 1 bit pour son référencement (R) et 1 bit pour sa modification

(M).

12/15/16

Solution Exercice 1 : Pagination Simple

● 1- Combien de bits se trouvent dans une

adresse virtuelle ?

– L’espace d’adressage logique contient 2¹² = 4096 pages de 4

ko = 2¹² octets chacune, soit un espace d’adressage total de

2¹² x 2¹² = 2² octets. Pour couvrir cet espace d’adressage,

l’adresse virtuelle sera codée sur 24 bits : 12 bits pour les

pages et 12 bits pour le déplacement dans la page

⁴

● 2- Combien d'octets se trouvent dans un cadre

de page ?

– 4096 octets

12/15/16

Solution Exercice 1 : Pagination Simple

● 3- Combien de bits de l'adresse physique spécifient le cadre de

page ?

– L’espace d’adressage physique est de 2¹ octets. Étant donné que les pages font 2¹²

⁶

octets, on peut donc écrire 2¹ = 2¹² * 2 . Ceci implique une adresse physique de 16

bits définie avec 4 bits pour les numéros des cadres et 12 bits pour le déplacement

dans une page.

⁶

⁴

● 4- Combien d'entrées se trouvent dans la table de pages ?

– La table des pages doit contenir une entrée pour chaque page. Comme il y a 2¹²

pages, la taille de la table des pages doit donc avoir une longueur de 2¹² = 4096

entrées.

● 5- Combien de bits sont nécessaires pour stocker une entrée

dans la table de pages (de quelle largeur est la table de pages) ?

– Chaque entrée contient 3 bits pour indiquer P, R et M et 4 bits pour spécifier le

numéro du cadre de page ; ce qui donne au total 3 + 4 = 7 bits par entrée.

12/15/16

Accélérer la pagination

• Tout système de pagination doit considérer deux éléments

1. La correspondance doit être rapide

2. La table des pages doit être très grande

• Accélérer la correspondance

–.La correspondance entre mémoire virtuelle et mémoire physique doit être

réalisée à chaque référence mémoire

–.Un instruction typique: un mot d’instruction + opérande mémoire

–.Chaque instruction : on fait référence à la table des pages au moins

une fois

•. La table des pages doit être très grande

–.Les adresses virtuelles courante d’au moins 32bits (souvent 64 bits)

–.Une page de 4Ko, un espace d’adressage de 32 bits a 1 Million de pages

–.Avec un 1 Million de page dans l’espace d’adressage virtuel, la table

des pages doit avoir 1 Million d’entrées

12/15/16

La mémoire associative

• Hypothèse: la table des pages est en mémoire

– Impact considérable sur les performances

– Par exemple une instruction qui copie un registre dans un autre

● En l’absence de pagination: cette instruction fait une seule

référence mémoire

● Avec la pagination: des références mémoires supplémentaires

peuvent être nécessaire pour accéder à la table des pages

• Observation:

– La plupart des programmes tendent à faire un grand nombre de

référence à un petit nombre de pages

→ Seule un petite fraction des entrées de la table des pages est

réellement lue, tout le reste sert rarement

12/15/16

La mémoire associative

• Solution

– équiper les ordinateurs avec un périphérique qui permet de mettre en

correspondance les adresses virtuelles avec les adresses physique sans passer

par la table des pages

– TLB: Translation Lookaside Buffer

– Appelé aussi mémoire associative, se trouve à l’intérieur de la MMU

• Le TLB consiste en un petit nombre d’entrées qui sont rarement

plus de 64

– Chaque entrée contient les informations d’une page:

• le numéro de la page virtuelle,

• un bit mis à 1 quand la page est modifiée,

• le code de protection (RWX)

• la cadre de page physique dans lequel la page est utilisé

• Un bit indique si l’entrée est valide (càd utilisée) ou non

– Ces champs étalissent une correspondance point à point avec les champs de la

page

12/15/16

La mémoire associative

Valide

Page virtuelle

Modifié

Protection

Cadre de page

indices

code

données

code

pile

• Un processus (boucle + tableau)

– Les données principales sont dans les pages 129,130

– Page 140 indice de parcours

– Pile 860, 861

– Code 19,20,21

12/15/16

La mémoire associative

• Quand une adresse virtuelle est présentée à la

MMU pour être traduite

– Le matériel vérifie si ce numéro de page virtuelle est

présent dans le TLB

– Si une correspondance est trouvée et si l’accès n’enfreint

pas la pas les bits de protection, le cadre de page est

pris directement dans le TLB sans passer par la table

des pages

– Si le numéro de page virtuelle est présent dans le TLB

mais l’instruction essaie d’écrire dans un cadre autorisée

en lecture seule, une erreur de protection est générée

12/15/16

La mémoire associative

• Lorsque le numéro de page virtuelle

n’est pas dans le TLB

– La MMU détecte l’erreur et parcourt

normalement la table des pages

– Elle efface une des entrées du TLB et la

remplace par l’entrée de la table des pages

trouvée

– Si cette page est réutilisée rapidement, il en

résultera cette fois un accès plutôt qu’une

erreur

12/15/16

Les tables des pages des grandes

mémoires

• On utilise les TLB pour accélérer la

traduction d’adresse virtuelles en

adresses physiques, mais ce n’est pas

le seul problème à traiter

• Il faut aussi gérer de très grandes

mémoires. Deux solutions:

1. Tables des pages multi-niveaux

2. Tables des pages inversées

12/15/16

Tables des pages multi-niveaux

• Une adresse de 32 bits est

subdivisé en

– Un champ de 10 bits nommé

PT1

– Un champ de 10 bits nommé

PT2

– Un champ de 12 bits nommé

Décalage

• Puisque les décalages

sont sur 12 bits, les pages

font 4 Ko (4*1024) et nous

avons au total 220 pages.

12/15/16

Tables des pages multi-niveaux

• Avec la méthode des tables

de pages multi-niveau, on ne

garde pas en mémoire toutes

les tables de pages en

particulier celles dont nous

n’avons pas besoin.

• Exemple: Un processus a

besoin de 12 Mo: 4Mo

inférieur pour le code, 4 Mo

pour les données, 4 Mo pour

la pile

12/15/16

Tables des pages multi-niveaux

• Le 1er niveau correspon...