Systèmes d'Exploitation II

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

4/28/19

25

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.

4/28/19

26

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

4/28/19

27

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)

4/28/19

28

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

4/28/19

29

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

• Une unité de 4 octets (32bits) n’aura 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

4/28/19

30

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 0.

4/28/19

31

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

4/28/19

32

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

4/28/19

33

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.

4/28/19

34

Gérer la mémoire avec des listes

chaînées

• Quand les processus et les trous sont indiqués

dans une liste triée 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

4/28/19

35

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

4/28/19

36

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

Next Fit

• Algorithme de la première zone libre

suivante

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

recherche commence au dernier espace libre

trouvé.

– Les performance sont légèrement meilleures

(en terme de rapidité)

4/28/19

37

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

4/28/19

38

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.

4/28/19

39

Gérer la mémoire avec des listes

chaînées

• Un 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

4/28/19

40

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.

4/28/19

41

Source : William Stallings, « OPERATING SYSTEMS INTERNALS AND

DESIGN PRINCIPLES SEVENTH EDITION » , Chapter 7 Memory

Management, Prentice Hall, 2012

4/28/19

Example Memory Configuration before and after Allocation of 16-Mbyte

Block

42

Application #1

4/28/19

43

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.

4/28/19

44

Solution Application #1

● First fit : on cherche le premier espace

qui convient

@

a

b

c

d

e

f

g

h

Lg

10k

4k

20k

18k

7k

9k

12k

15k

@

a

b

c

d

e

f

g

h

Lg

10k

4k

8k

18k

7k

9k

12k

15k

4/28/19

A

12k

B

10k

@

b

c

d

e

f

g

h

Lg

4k

8k

18k

7k

9k

12k

15k

C

9k

@

b

c

d

e

f

g

h

Lg

4k

8k

9k

7k

9k

12k

15k

45

Solution Application #1

● Next Fit : on cherche l’espace suivant

qui convient

@

a

b

c

d

e

f

g

h

Lg

10k

4k

20k

18k

7k

9k

12k

15k

@

a

b

c

d

e

f

g

h

Lg

10k

4k

8k

18k

7k

9k

12k

15k

@

a

b

c

d

e

f

g

h

Lg

10k

4k

8k

8k

7k

9k

12k

15k

4/28/19

A

12k

B

10k

C

9k

@

a

b

c

d

e

g

h

Lg

10k

4k

8k

8k

7k

12k

15k

46

Solution Application #1

● Best fit : on cherche l’espace qui laisse

le plus petit trou

@

a

b

c

d

e

f

g

h

Lg

10k

4k

20k

18k

7k

9k

12k

15k

4/28/19

A

12k

@

a

b

c

d

e

f

h

Lg

10k

4k

20k

18k

7k

9k

15k

B

10k

@

b

c

d

e

f

h

Lg

4k

20k

18k

7k

9k

15k

C

9k

@

b

c

d

e

h

Lg

4k

20k

18k

7k

15k

47

Solution Application #1

● Worst fit : on cherche l’espace qui

laisse le plus grand vide

@

a

b

c

d

e

f

g

h

Lg

10k

4k

20k

18k

7k

9k

12k

15k

@

a

b

c

d

e

f

g

h

Lg

10k

4k

8k

18k

7k

9k

12k

15k

@

a

b

c

d

e

f

g

h

Lg

10k

4k

8k

8k

7k

9k

12k

15k

4/28/19

A

12k

B

10k

C

9k

@

a

b

c

d

e

f

g

h

Lg

10k

4k

8k

8k

7k

9k

12k

6k

48

LA MÉMOIRE VIRTUELLE

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 Go

– Windows 10 (min 2 GB de RAM pour la version 64 bits)

• 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

4/28/19

50

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

4/28/19

51

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.

4/28/19

52

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

4/28/19

53

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

4/28/19

54

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.

4/28/19

55

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

4/28/19

56

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

4/28/19

57

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.

4/28/19

58

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 ????

4/28/19

59

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

suivante:

– 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.

4/28/19

60

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)

4/28/19

61

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

4/28/19

62

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

4/28/19

63

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

4/28/19

64

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

4/28/19

65

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

4/28/19

66

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

4/28/19

67

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 pluô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

4/28/19

68

Application #2

4/28/19

69

Exercice 2 : 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).

⁶ octets de mémoire

– Combien de bits se trouvent dans une adresse virtuelle ?

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

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

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

– 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)

4/28/19

70

Solution Exercice 2 : 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

⁴ octets. Pour couvrir cet espace d’adressage,

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

de page ?

– 4096 octets

4/28/19

71

Solution Exercice 2 : 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 de mémoire

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.

⁴ octets. Pour couvrir cet espace d’adressage,

⁶ octets de mémoire

● 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.

4/28/19

72

Exercice 3

● Considérer un système monoprocesseur avec une gestion de

mémoire par pagination pure et des tables de pages à un

niveau.

● La mémoire physique est composée de 4 cadres. La taille de

chaque cadre est de 4 KO. L'adresse virtuelle est codée sur 16

bits.

● Supposez que 2 processus P1 et P2, composés respectivement

de 7 et 5 pages, arrivent dans le système, l'un à la suite de

l'autre.

● Le système charge dans l'ordre, les pages 0 et 1 de P1 dans les

cadres 1 et 2, et la page 1 de P2 dans le cadre 3, avant de

commencer l'exécution des processus P1 et P2.

4/28/19

73

Exercice 3

1)Proposer une structure d'une adresse

virtuelle ?

2)Donner l'adresse physique de l'adresse

virtuelle: 0001 0011 0111 1000 si P1

référence cette adresse virtuelle ?

3)Donner l'adresse physique de l'adresse

virtuelle: 0001 0011 0111 1000 si P2

référence cette adresse virtuelle ?

4/28/19

74

Correction Exercice 3

1)Proposer une structure d'une adresse

virtuelle ?

La taille d'une page est 4kiO. Le

déplacement est donc codé sur 12 bits.

L'adresse virtuelle est sur 16 bits : 4 bits

pour le numéro de page et 12 bits pour le

déplacement dans la page.

4/28/19

75

Correction Exercice 3

2)Donner l'adresse physique de l'adresse

virtuelle: 0001 0011 0111 1000 si P1

référence cette adresse virtuelle ?

P1 : 00 01 00 11 01 11 10 00 => il s'agit de

la page 1 de P1. Cette page est chargée

dans le cadre 2 => L'adresse physique

est : 10 00 11 01 11 10 00

4/28/19

76

Correction Exercice 3

3)Donner l'adresse physique de l'adresse

virtuelle: 0001 0011 0111 1000 si P2

référence cette adresse virtuelle

P2 : 00 01 00 11 01 11 10 00 => il s'agit de

la page 1 de P2. Cette page est chargée

dans le cadre 3 => L'adresse physique

est : 11 00 11 01 11 10 00

4/28/19

77

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

4/28/19

78

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

4/28/19

79

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...