1

OPERATING SYSTEMS AND

CONCURRENT PROGRAMMING
 2

CHAPITRE 6. Gestion de Mémoire

Partie I: Mémoire Physique

• Introduction
• Concepts fondamentaux
• Allocation contigue
• Algorithmes de placement 1 : First Fit, Best Fit et Worst Fit
• Algorithmes de placement 2 : Buddy System

• Segmentation
• Pagination
• Swapping
 3

Introduction

• Structure simplifiée d‟un micro-ordinateur

Bus de contrôle

Sous-système
Microprocesseur Mémoire
d ‟E/S

Unité centrale
de traitement Bus de données

Bus d ‟adresses
 4

Introduction
 Mémoire centrale :
 Rôle : toutes les informations transitent par la MC
 Pour qu‟un programme puisse être exécuté, il doit être place en MC
(Code, données..).

 Caractéristiques de la MC :
 Type de mémoire : RAM/ROM (volatile/non volatile)
 Méthode d‟accès : direct (temps d‟accès constant)
 Mémoire à contenu adressable
 Format des mots et des adresses
 Le processeur accède aux de la MC par le biais de 2 Registres :
Adresse, Données (lecture/Ecriture)
 Capacité : nombre total d‟octets

 Nécessite d‟une gestion optimale de la MC : fondamentale

 En dépit de sa grande disponibilité, elle n‟est, en général, jamais suffisante.
Ceci en raison de la taille continuellement grandissante des programmes.
 5

Introduction

• Mémoire Centrale – Tableau linéaire d‟octets (bytes)

• Contient des programmes O.S. et des programmes utilisateurs

(processus)

• Rappel, chaque processus est défini par un espace d‟adresse, comportant

du texte (code), data, et pile d‟exécution.

• Exécution des Processus

• CPU “fetch” les instructions de la zone text suivant la valeur du program
counter (PC).
 6

Notion de multiprogrammation (Rappel)

• Le concept de multiprogrammation s‟oppose à celui de monoprogrammation
Un seul processus en mémoire, en attente de ressource le processeur ne
fait rien.
 Plusieurs processus en mémoire  partage du processeur
• Multiprogrammation: Technique permettant d‟optimiser le taux d‟utilisation du
processeur en réduisant notamment les attentes sur les E/S.
 Activité du processeur : 400 ms sur 520 ms, soit 77%

Processus P1

Processus P2

 Conséquences de multiprogrammation et gestion de mémoire :

 Définir un espace indépendant pour chaque processus
 Protéger les espaces d’adressages des processus entre eux
 Allouer de la mémoire physique à chaque espace d’adressage
 7

CHAPITRE 6. Gestion de Mémoire

Partie I: Mémoire Physique

• Introduction
• Concepts fondamentaux
• Allocation contigue
• Algorithmes de placement 1 : First Fit, Best Fit et Worst Fit
• Algorithmes de placement 2 : Buddy System

• Segmentation
• Pagination
• Swapping
 8

Production d’un programme exécutable

0 1000
Library Library
Routines Routines

Prog P P: 0 P: 100 P: 1100 P:

: : : : :
: push ... push ... push ... push ...
foo() jmp _foo jmp 75 jmp 175 jmp 1175
: : : : :
:
End P foo: ... 75 foo: ... 175 foo: ... 1175 foo: ...

Compilation Assembly Linking Loading

 9

Production d’un programme exécutable

• Avant d'être exécuté un programme doit passer par plusieurs étapes :
 Edition du programme dans un langage source (par exemple C).
 Compilation: transformation en un module objet (langage binaire)
Le code produit est, en général, relogeable, commençant à l‟adresse 0000 et
pouvant se translater à n‟importe quel endroit de la mémoire.
Référence initiale = le registre de base; les adresses représentent alors le
décalage par rapport à ce registre.
 Edition de liens: rassembler les modules objets.
 Chargement (statique/dynamique): modifier le code exécutable pour effectuer les
liaisons nécessaires (appels système avec le noyau) et puis chargement en
mémoire.

0000 :
P1 0010 :

1004 :

MEMOIRE
0000 : CENTRALE
0010 :
P2
0150 :
Système
 10

Protection des Processus

 La gestion de la mémoire est presque impossible sans l‟aide du matériel pour

assurer la protection.

 Dans la MC, on a 2 types de processus (système, utilisateur)

 Différentes fonctionnalités/droits
 Problème : coexistence de processus de nature différentes
 Solution : interdire à un utilisateur d‟accéder n‟importe comment au noyau
du système, ou aux autres programmes des utilisateurs.

 Protection fondamentale: en général, chaque processeur dispose de 2

registres.
 BASE : contient l ‟adresse début de la zone utilisateur.
 LIMITE: contient l ‟adresse fin de la zone utilisateur.
 Comparer les adresses émises par le processus à ces 2 registres
 Si LIMITE < l„adresse référencée < BASE
Alors génération d‟une interruption de violation de protection mémoire.
 11

Protection des Processus

• Memory Management Unit (MMU) - convertit dynamiquement les

adresses logiques en adresses physiques.

• MMU contient registre d‟adresse de base pour exécuter un processus.

Relocation register for process i

Max Mem

1000 Max addr

process i
0
Program generated
address
+ Physical memory
address
MMU
Operating
system
0
 12

Multiprogrammation avec les registres limite et de base

• Multiprogrammation: une partition distincte par processus.

• Que se passe-t-il lors d‟une commutaion de contexte?

• Enregistrer les valeurs des registres de base et limite du
processus A.
• Charger des nouvelles valeurs dans les registres de base et
limite pour processus B.

Partition E

limit Partition D

base Partition C
Partition B

Partition A
OS
 13

Principe de Gestion
Les méthodes d‟allocation mémoire peuvent être divisées en deux grandes familles:

• Allocation contiguë:
• Programme = ensemble de mots contigus insécables - espace d‟adressage linéaire.
• Allocation en partitions fixes ou variables.

• Allocation non contiguë

• Programme = ensemble de mots sécables, c- à-d le programme peut être divisé en
plus petits morceaux, chaque morceau étant lui même un ensemble de mots
contigus.
• Chaque morceau peut alors être alloué de manière indépendante  Mécanismes
de Segmentation et de Pagination.

• Dans beaucoup de cas, il n‟est pas possible de faire tenir tous les processus
ensemble en mémoire. Parfois même, la taille d ‟un programme est trop importante.

• Mettre en œuvre une stratégie de recouvrement (overlay).

• Restructurer le programme sous forme arborescente est très fastidieux.

• L‟OS s‟en occupe et décharge le programmeur de cette tâche en mettant en œuvre:

• le swapping (manque de mémoire pour héberger plusieurs programmes).
• la mémoire virtuelle (taille d ‟un programme dépasse la taille de la mémoire).
 14

CHAPITRE 6. Gestion de Mémoire

Partie I: Mémoire Physique

• Introduction
• Concepts fondamentaux
• Allocation contigue
• Algorithmes de placement 1 : First Fit, Best Fit et Worst Fit
• Algorithmes de placement 2 : Buddy System

• Segmentation
• Pagination
• Swapping
 15

Allocation Contiguë
• La mémoire physique est découpée en zones disjointes: Nécessité de connaître
l'état de la mémoire (zones libres/occupées).
• Disposer d‟une stratégie d‟allocation et de procédures de libération.

• 2 types d‟allocation :
 Statique: la MC est découpée en zones fixes -- partitions (nombre fixe)
 Dynamique: la MC est constituée de zones fixes/variables -- régions (nombre
variable).

1. Allocation Statique
• Un programme est considéré comme un espace d‟adresses insécable; Les partitions
sont de taille fixe, non nécessairement identiques;
 Allocation d‟un seul tenant: une partition ne peut contenir qu‟un seul processus.
 16

1. Allocation Statique (suite)

• Etant données la taille(partition) et la taille(processus), 3 cas se présentent:

 Cas 1: taille(partition) = taille(processus) Aucune perte de mémoire

 Cas 2: taille(partition) > taille(processus) => fragmentation interne -- perte
de mémoire.
 Cas 3: taille(partition) < taille(processus) => fragmentation externe.

• Inconvénient : Fragmentation -
Par4
 Récupérer les fragments et faire un tassement (bas/haut)
Garbage Collector
Par3
5Ko
 Les partitions restent fixes jusqu‟au prochain tassement.
Par2
• Avantages : 2Ko
 Protection assez simple à réaliser
Par1
 Adaptée aux systèmes temps réel
1Ko
partitionnement fixe car les programmes sont toujours les mêmes
SE
 17

2. Allocation dynamique de la Mémoire

• Allocation en fonction de la taille du programme à exécuter

 le nombre et la taille des zones varient dynamiquement
 Il faut prévoir des protections entre processus car ils fonctionnent dans le même
espace, et tout débordement de l‟un risquerait de perturber le fonctionnement
des autres

P3 P3

P2 P2
P1 P1 P1 P1
SE SE SE SE SE

Initialement Chargement de P1 Chargement de P2 Chargement de P3 Terminaison de P2

 Représenter la mémoire par des listes chaînées (libres/occupées)

 Libération de zones libres si zones adjacentes alors fusionner sinon chaîner
 Risque de fragmentation externe compactage/tassement (coûteux).
 la récupération est une condition nécessaire et non suffisante
 18

Problème de Fragmentation
64K 64K
P3 P3
576K 352K 288K 288K

896K P2 224K P2 224K 224K

P1 320K P1 320K P1 320K P1 320K

O.S. 128K O.S. 128K O.S. 128K O.S. 128K O.S. 128K

64K 64K 64K 64K

P3 P3 P3 P3
288K 288K 288K 288K
96K 96K 96K 96K
???
P4 128K P4 128K P4 128K P4 128K P6 128K
96K 96K
P1 320K 320K
P5 224K P5 224K

O.S. 128K O.S. 128K O.S. 128K O.S. 128K

 19

Compactage

• Compactage - D‟un temps à autre, décaler les processus pour mettre

tout l‟espace libre disponible dans un seul bloc contigu.

• Overhead dû à la copie d‟une mémoire à une autre.

• Copie mémoire vers disk vers mémoire pour compactage via swapping.

64K
256K
P3
288K
96K P3
??? 288K
P4 128K 128K P6
P6
96K P4 128K

P5 224K P5 224K

O.S. 128K O.S. 128K

 20

Gestion de la Mémoire

• Chaque morceau de mémoire est soit:

• Utilisé par un ceratin processus ou inutilisé (“free”)

• Opérations
• Allouer un morceau inutilisé de mémoire suffisament large pour
supporter un nouveu processus.
• Libérer un morceau de mémoire en le retuournant à la free pool
après que le processus ait terminé ou est swapped out.

• Il existe deux techniques de gestion de mémoire:

• Technique du Bit Mapping.
• Technique de la Liste Chaînée.
 21

Gestion de la Mémoire -1- Bit Mapping

• Problème - Comment suivre of la mémoire utilisée et non-utilisée?

• Technique 1 - Bit Maps

• Une longue chaîne de bits
• Un bit par unité de mémoire
1 = utilisé
0 = libre

• Taille de l‟unité influence l‟espace requis

• Exemple: taille d‟unité = 32 bits
• overhead par bit map: 1/33 = 3%
• Exemple: taille d‟unité = 4Kbytes
• overhead par bit map: 1/32,769
 22

Gestion de la Mémoire -1- Bit Mapping

•
 23

Gestion de la Mémoire -2- Liste Chaînée

• Technique 2 – Liste Chaînée

• Garder une liste d‟éléments

• Chaque élément décrit une unité de mémoire.
• Libre / Bit utilisé (“P=processus, H=vide”)
• Adresse de début
• Longueur
• Pointeur vers l‟élément suivant
 24

Gestion de la Mémoire -2- Liste Chaînée

0
 25

Politiques d’Allocation de Mémoire

• Questions générales :
 Q1 : Quand charger ?
Chargement à demande quand on a besoin
Pré-chargement avant d‟en avoir besoin
 Q2 : Où charger en mémoire centrale ?
S‟il y a de place, quel emplacement doit-on choisir ?  Problème de
Placement
S ‟il n ‟y a pas de place quel est le processus victime à décharger pour le
charger à sa place  Problème de Remplacement (swapping).

Algorithmes de Placement 1
• La mémoire est formée d‟un ensemble de zones libres et de zones occupées
(allouées)
• Allouer un programme P de taille Taille(P) :
 Trouver une zone libre telle que Taille(zone libre) >= Taille(P)
 3 stratégies principales :
La première zone qui convient (le premier ajustement) -- First Fit
Le meilleur ajustement -- Best Fit
Le pire ajustement -- Worst Fit
 26

Algorithme 1: Allocation First Fit

• Trouver la première zone libre suffisamment grande pour pouvoir y placer le

programme

n-1 n-1

150K 150K

P6 P6

100K 80K 100K

P5 P5
40K
120K Processus P7 P7

P3 P3

60K 60K
Système Système
0 0

 Solution simple, peu coûteuse et la recherche est accélérée.

 Concentration des résidus en tête de la liste chaînée des zones libres.
 27

Algorithme 2: Allocation Best Fit

• Chercher dans toute la liste des zones libre, et choisir la plus petite zone libre qui
puisse contenir le programme à allouer
 Produire le plus petit trou résiduel

n-1 n-1

150K 150K

P6 P6

100K 80K 20K P7

P5 P5
120K
120K Processus P7

P3 P3

60K 60K
Système Système
0 0

 Parcourir toute la liste chaînée de zones libre pas assez efficace

 Trier (ordre croissant) la liste selon les tailles des zones libres
 Génération de trous inutilisables
 28

Algorithme 3: Allocation Worst Fit

• Politique du plus grand résidu(reste)
• Chercher à placer un programme dans la zone libre la plus grande
 Possibilité d‟utiliser le fragment pour le chargement du prochain programme
n-1 n-1
70K
150K
P7

P6 P6

100K 80K 100K

P5 P5
120K
120K Programme P7

P3 P3

60K 60K
Système Système
0 0

 Combattre l‟émiettement en réutilisant les résidus

 Amélioration de la méthode : fixer une limite inférieure à la taille des résidus
 Si Taille(résidu) ≥ Taillemin Alors création d‟une zone libre
Sinon le résidu ne fait pas partie des zones libres
 Fragmentation interne
 29

Algorithmes de Placement 2 -- Buddy System

• Système Compagnon
 Subdiviser la mémoire en zones dont les tailles (nombre de mots) forment
une suite croissante.
 Les tailles des zones sont quantifiées
Quantification = multiple d‟une certaine unité
 L‟allocation se fait par une relation de récurrence
Stratégie Best Fit
• Essentiellement deux algorithmes :
 Système binaire (1, 2, 4, 8, 16, 32, 64, ...)
Un bloc (zone mémoire) Si+1 = 2*Si
 Suite de Fibonacci (1, 2, 3, 5, 8, 13, 21, ...)
Un bloc Si+1 = Si + Si-1

• Allocation: Soit une demande de taille Si

 Cas 1: bloc libre existe et taille satisfaisante Allocation du bloc Si
 Cas 2: le bloc Si n‟existe pas, créer le bloc par la relation de récurrence
Création par subdivision
• Libération:
 MAJ des blocs libres
 Création éventuelle d‟un nouveau bloc en consultant le „‟compagnon‟‟
 30

Buddy System -- Exercice d’application

• Soit un ordinateur utilisant la technique Buddy System pour la gestion de sa mémoire
centrale. Initialement, la mémoire a un seul bloc de 128Ko. On dispose de 4 processus
P1, P2, P3 et P4 de tailles respectives 25, 12, 4 et 28K. On désire effectuer les
demandes des processus suivantes :
Chargement de P1
Chargement de P2
Chargement de P3
Terminaison de P2
Chargement de P4
Terminaison de P1
Terminaison de P3
• En utilisant le système binaire, donnez à chaque fois l'état de la mémoire après
exécution des demandes ci-dessus.

0 64 128
Mémoire initiale
Demande de 25K P1 32K 64K
Demande de 12K P1 P2 16K 64K
Demande de 4K P1 P2 P3 4 8K 64K

Libération de P3 64K P4 32K

 31

Faiblesses de l’Allocation Contigue

 Exigence d‟allouer le programme en une zone d‟un seul tenant.

 Fragmentation

 Nécessité d‟une opération de compactage de la mémoire.

 Diviser le programme :
 en segments (code, données, pile), qui peuvent être de taille différente
 Correspond à l‟image que le programmeur a de son programme
(données manipulées par le programme, programme principal,
procédures séparées, ...).
 en portions de taille fixe et égale à l'unité de la mémoire centrale -- les
pages.
 32

Fragmentation
• La mémoire est divisée en partitions.
• Chaque partition a une taille différente.
• Les processus sont alloués de l‟espace puis libéré.

• Après peu de temps la mémoire sera pleine de petits espaces vides

éparpillés!
• Pas d‟espace vide suffisant pour un nouveau processus bien qu‟il
ait un espace vide total suffisant.
• S‟il existe de l‟espace libre dans une partition allou ée, on parle
de fragmentation interne.
• Fragmentation:
• Fragmentation externe = Espace non-utilisé entre les partitions.
• Fragmentation interne = Espace non-utilisé dans les partitions.
 33

Solution à la Fragmentation
• Compactage nécessite un overhead élevé de copiage.
• Pourquoi pas allouer des unités mémoire non-contigues de tailles
égales et fixes?
• Pas de fragmentation externe!
• Fragmentation interne < 1 unité par processus.

• Quelles tailles choisir pour ces unités?

• Plus petite => Moins de fragmentation interne.
• Plus large => Moins d‟overhead de gestion.
 34

Utilisation de pages pour des allocations non-contigues

• Mémoire divisée en des cases de tailles fixes

• Taille d‟une case = 2n octets
• Les n bits inférieurs de l‟adresse spécifient l‟offset de la case.

• Question: Comment associer les cases aux processus?

• Et comment “mapper” les adresses mémoires dans un processus à
l‟octet correspondant de la case mémoire?

• Solution
• Processus utilisent des adresses virtuelles
• CPU utilise des adresses physiques
• Hardware supporte la translation d’adresse virtuelle en adresse
physique.
 35

CHAPITRE 6. Gestion de Mémoire

Partie I: Mémoire Physique

• Introduction
• Concepts fondamentaux
• Allocation contigue
• Algorithmes de placement 1 : First Fit, Best Fit et Worst Fit
• Algorithmes de placement 2 : Buddy System

• Segmentation
• Pagination
• Swapping
 36

Segmentation

• Le programme est divisé en segments, un segment étant un espace

d‟adressage linéaire formé d‟adresses contiguës.
• Segment = une partie logique du programme : segment de code, segment
de données, et segment de pile.
• Intérêt : faciliter la gestion par les processus de leur espace propre (exemple
le partage)
 espace à deux dimensions <N º segment, déplacement>
 simulée par éditeur de liens et chargeur
 pris en compte par le matériel sur Multics, iAPX286, iAPX386, ...

Espace S3 S2 Espace
d’adressage 180K 100K 30K d’adressage
linéaire S1 segmenté
50K

 Il faut convertir l„adresse segmentée, générée au niveau du processeur,

en une adresse physique équivalente.
 Adresse physique = adresse implantation segment + déplacement
 37

Segmentation - Mémoire Segmentée

 Allouer un segment S de taille Taille(S) :

 Trouver une zone libre telle que Taille(Zone libre) ≥ Taille(S)
 Allocations et libérations successives des segments peuvent
créer également un problème de fragmentation
 38

CHAPITRE 6. Gestion de Mémoire

Partie I: Mémoire Physique

• Introduction
• Concepts fondamentaux
• Allocation contigue
• Algorithmes de placement 1 : First Fit, Best Fit et Worst Fit
• Algorithmes de placement 2 : Buddy System

• Segmentation
• Pagination
• Swapping
 39

Pagination
 La pagination permet d‟avoir en mémoire un processus dont les adresses sont
non contiguës
 L‟espace d‟adressage du programme est découpé en morceaux linéaires
de même taille -- la page (qcq Ko).
 L‟espace de la mémoire physique est lui-même découpé en morceaux
linéaires de même taille -- la case
 Charger un programme en mémoire centrale consiste à placer les pages dans
n‟importe quelles cases disponibles. Page 4 Case 8

Page 1 Case 7

Page 2
Page 2 Case 6
Nº page Nº case
Page 3 1 2 Page 3 Case 5 Mémoire

Page 4
2 6 Case 4
3 5
Espace Case 3
4 8
d’adressage du Page 1 Case 2
programme P
Table de transcodage de P
Système Case 1
 40

La Mémoire Segmentée Paginée

Seg Depl Depl
< oui Mémoire

Registre adresse Page Depl’

Table des segments
LT @table
+
case +

< +
oui

@ table
Taille des
pages
Page 1

Système
Table des segments

 Une table de segments est définie pour chaque segment de l‟espace d‟adressage du
processus
 Chaque segment est à son tour paginé :
 Il existe une table des pages pour chaque segment
 Déplacement dans un segment = <Nºpage, Déplacement dans la page>
 41

CHAPITRE 6. Gestion de Mémoire

Partie I: Mémoire Physique

• Introduction
• Concepts fondamentaux
• Allocation contigue
• Algorithmes de placement 1 : First Fit, Best Fit et Worst Fit
• Algorithmes de placement 2 : Buddy System

• Segmentation
• Pagination
• Swapping
 42

Le Swapping

• Quand un programme est en cours d‟exécution...

• Le programme en entier doit être en mémoire.
• Chaque programme est mis dans une partition.

• Quand le programme n‟est pas en cours d‟exécution...

• Il peut rester en mémoire.
• Il peut être “swappé” hors de la MC.

• Dans le temps...
• Des programmes entrent en MC (swapped in).
• Des programmes quittent la MC (swapped out).
 43

Le Swapping
 Lorsque tous les processus ne peuvent pas tenir simultanément en mémoire.
 Taille des processus en cours d'exécution > Taille de la mémoire
physique.
 Déplacer temporairement certains sur une mémoire provisoire (partie
réservée du disque).

 Allocation à la demande de la zone de swapping sur disque:

 Quand un processus est déchargé de la MC, on lui cherche une place
(même gestion que celle de la MC).
 Lors d‟un déchargement, le processus est sûre d‟avoir une zone d‟attente
libre sur le disque.
 La zone de swapping doit être suffisamment grande pour contenir les
processus déchargés car l‟espace qu‟ils occupaient a été réquisitionné.

 Le swapping, s„il permet de pallier le manque de mémoire nécessaire à

plusieurs processus users, n‟autorise cependant pas l'exécution de
programme de taille supérieure à celle de la MC.
 44

Le Swapping

• Avantages du swapping:

• Autoriser plusieurs programmes à être exécutés de façon concurrente.

• … plus que ce que pourrait être accepté dans la mémoire.

Max mem

Processus i
Swap in
Processus m
Processus j

Processus k
Swap out
Operating
system
0

Mémoire Provisoire Mémoire Centrale

 45

Récapitulatif - Gestion de la Mémoire Physique

 L‟allocation en partitions ou en régions considère le programme comme un
ensemble d‟adresses insécables.
 Problème de fragmentation nécessité d‟une opération de compactage de
la mémoire centrale.
 La segmentation découpe l‟espace d‟adressage du programme en segments
correspondant à des morceaux logiques du programme.
 Une adresse générée par le processeur est de la forme <Nº segment,
déplacement>.
 La table des segments du processus permet de transformer l‟adresse
segmentée en adresse physique.

 La pagination découpe l‟espace d‟adressage du programme en pages et la

mémoire physique en cases de même taille.
 Une adresse générée par le processeur est de la forme <N º page,
déplacement>.
 La table des pages du processus permet de traduire l‟adresse paginée en
adresse physique.
 Segmentation et pagination sont très souvent associées.
 46

CHAPITRE 6. Gestion de Mémoire

Partie II: Mémoire Virtuelle

• Présentation
• Pagination – Transformation des Adresses
• Algorithmes de Remplacement
• FIFO - OPTIMAL - LRU – NRU
• Autres Considérations
• Politiques d‟Allocation (Locale/Globale)
• Ecroulement
• L‟ensemble de Travail
• Prépagination
 48

Adresses Virtuelles

• Adresses mémoire virtuelles (ce que le processus utilise)

• Numero de Page plus byte offset en page.
• Les n bits d‟ordre inférieur sont l‟octet offset.
• Les bits d‟ordre supérieur restants forment le numero de page.

bit 31 bit n-1 bit 0

20 bits 12 bits

page number offset

Exemple: 32 bit virtual address

Page size = 212 = 4KB
Address space size = 232 bytes = 4GB
 49

Adresses Physiques

• Adresses mémoire physiques (Ce que le CPU utilise)

• Numero de Case plus byte offset.
• Les n bits d‟ordre inférieur sont l‟octet offset.
• Les bits d‟ordre supérieur restants forment le numero de case.

bit 24 bit n-1 bit 0

12 bits 12 bits

frame number offset

Exemple: 24 bit physical address

Page frame size = 212 = 4KB
Max physical memory size = 224 bytes = 16MB
 50

Translation d’Adresses

• Hardware “maps” les numéros de page en numéros de case.

• L‟unité de gestion de mémoire (MMU) a plusieurs registres pour plusieurs

pages.
 51

Espaces d’Adresses Virtuelles

• Espace d‟adresses virtuelles

• (vu du processus)

Lowest address

Highest address
Virtual Addr Space
 52

Espaces d’Adresses Virtuelles

• L‟espace d‟adresse est divisé en “pages”

• Exemple: Taille de page est 8ko.

Page 0
0
1
2
3
4
Page 1
5
6
7

Une Page

Page N
N
Virtual Addr Space
 53

Espaces d’Adresses Virtuelles

• En réalité, uniquement certaines pages sont utilisées.

0
1
Non-Utilisé 2
3
4
5
6
7

N
Virtual Addr Space
 54

Mémoire Physique

• La mémoire physique est divisée en des “cases”

• (Taille de Page = Taille de Case)

0
1
2
3
4
5
6
7

N
Virtual Addr Space Physical memory
 55

Espaces d’Adresses Physiques et Virtuelles

• Quelques cases serviront à supporter les pages de ce processus.

0
1
2
3
4
5
6
7
Ces cases sont
utilisées pour ce
processus

N
Virtual Addr Space Physical memory
 56

Espaces d’Adresses Physiques et Virtuelles

• Quelques cases seront utilisées par d‟autres processus.

0
1
2
3 Used by
4 other processes
5
6
7

N
Virtual Addr Space Physical memory
 57

Espaces d’Adresses Virtuelles

• Les mappings d‟adresse spécifient quelle case a quelle page.

0
1
2
3
4
5
6
7

Virtual Addr Space Physical memory

 58

Table de Pages
• Les mappings d‟adresse sont enregistrés dans une table de pages en
mémoire.
• Une entrée par page dans la table de pages...
• Est ce que cette page en mémoire? Si c‟est le cas, dans quelle
case?
0
1
2
3
4
5
6
7

N
Virtual Addr Space Physical memory
 59

Translation et Mapping d’Adresses

• Les mappings d‟adresses sont enregistrés dans table de pages en

mémoire.
• Typiquement une table de page par processus.

• Translation d‟adresse est faite par le hardware (c. à. dire le MMU).

• Comment le MMU obtient-il des mappings d‟adresses?

• Soit le MMU contient la page de table entiére (très coûteux).
• Ou le MMU supporte une portion de la table de page, utilise le TLB
(Translation Look-aside Buffer).
 60

CHAPITRE 6. Gestion de Mémoire

Partie II: Mémoire Virtuelle

• Présentation
• Pagination – Transformation des Adresses
• Algorithmes de Remplacement
• FIFO - OPTIMAL - LRU – NRU
• Autres Considérations
• Politiques d‟Allocation (Locale/Globale)
• Ecroulement
• L‟ensemble de Travail
• Prépagination
 61

Pagination - Principe
• On ne charge qu‟un ensemble de pages en mémoire :
 ce sous-ensemble est appelé l‟espace physique ou réel

Page

7 3
6 X Case
5 0 3
4 X 2
3 2 1
2 1
0
1 X
Disque (MV)
0 X Processus
en MC
Espace d’adressage
Virtuel
 Ne charger que les pages utiles à un instant donné
 62

Transformation des Adresses Virtuelles

 Les adresses manipulées par le programmes sont des adresses virtuelles

 Lorsqu‟une adresse est générée, elle est transcodée, grâce à une table, pour
lui faire correspondre son équivalent en mémoire physique

Nºpage déplacement Nºcase déplacement

UC

Nº case

Table des pages Mémoire physique

 63

Table de pages niveau 1

21-bits 11-bits
page number offset

frames
in
memory
•
•
•
Single-level
page table
 64

Table de pages multi-niveaux

• Adresse Virtuelle:
10-bits 10-bits 12-bits
PT1 PT2 offset

frames
in
memory
•
•
•

Top-level
Page table

2nd-level tables
 65

Transformation des Adresses Virtuelles

 Ce transcodage est effectué par des circuits matériels de gestion : unité de

gestion de mémoire - MMU (Memory Management Unit).
Carte CPU
CPU
@ Virtuelle
MMU B. Données (lecture/écriture)
@ Physique

Mémoire Centrale

 Si l‟adresse générée correspond à une adresse mémoire physique, le MMU

transmet sur le bus l‟adresse réelle, sinon il se produit un DEFAUT DE PAGE.
 Chaque table des pages contient les champs nécessaires au transcodage, avec
notamment :
 1 bit de présence (P 1/0) pour marquer la présence de la page en mémoire
physique.
 1 bit de modification (M 0/1) pour signaler si on écrit dans la page.
 66

Bit de Présence et Défaut de Page

3 la page est sur disque

SE

 Déroutement
 P M Nº case (Défaut de page)

0


Table des pages

Case libérée  Ramener
Processus en MC la
 Restaurer la table des pages page absente

 Référence Mémoire Centrale

 Redémarrer l’instruction
 67

Exemple et Représentation d’une Table de Pages

• Codage des @ virtuelle ou réelle

 On réserve les bits de poids nécessaires pour coder les numéros des pages ou des
cases.
 Les bits de poids faibles codent le déplacement (offset).

• Si Taille(page) = 4Ko; Taille(MC) = 4 cases; Taille(processus) = 16 pages

 Combien de bits a-t-on besoin pour représenter les @ virtuelles et les @ réelles?
@ virt. 12 bits de poids faible et 4 bits pour numeros de page= Total de 16 bits.
@ Phy 12 bits de poids faible
• Chaque processus a sa propre table de pages.

• Différentes organisations des tables de pages :

 Table des pages dans une mémoire cache:
 Très rapide/Coûteuse.

 Table des pages dans la MC :

 L‟adresse à la table est maintenue dans un registre.
 Chaque référence implique 2 accès à la MC (obtenir le numéro de page dans
la table et le 2eme concerne l ‟@ physique.
 68

CHAPITRE 6. Gestion de Mémoire

Partie II: Mémoire Virtuelle

• Présentation
• Pagination – Transformation des Adresses
• Algorithmes de Remplacement
• FIFO - OPTIMAL - LRU – NRU
• Autres Considérations
• Politiques d‟Allocation (Locale/Globale)
• Ecroulement
• L‟ensemble de Travail
• Prépagination
 69

Remplacement de Pages
• Soit une table de page normale.

• Un programme utilisateur est entrain de s‟exécuter.

• Une erreur PageInvalidFault se produit!

• La page demandée n‟est pas en mémoire.

• Sélectionez une case et supprimer la page qu‟elle contient.

• Trouver quelle page a été demandée de la “faulting address”.

• Lire la page demandée dans cette case.

• Redémarrer le processus interrompu en essayant la même

instruction.
 70

Algorithmes de Remplacement de Pages

• A la suite d‟un défaut de page (la page demandée n‟est pas en mémoire), le SE doit
retirer une page de la MC pour libérer de la place manquante.
• Problème: Quelle page choisir à décharger afin de récupérer l‟espace et minimiser
le nombre de défauts de pages?

• Plusieurs considérations doivent être tenues en compte :

• Il est - coûteux de remplacer une page qui n ‟a pas été modifiée en MC (inutile de
la recopier sur disque car elle existe déjà!).
• Une page d‟un segment de code est préférable par rapport à une page d‟un
segment de données, qui aura certainement été modifiée depuis son
chargement.
• Partage de pages entre plusieurs processus.
• Date d‟utilisation.

• Quelle case à remplacer? Plusieurs algorithmes de remplacement:

• Aléatoire
• Première entrée, première sortie -- FIFO
• Optimal
• Remplacement de la page la moins récemment utilisée -- LRU (Least Recently
Used)
• Remplacement d‟une page non récemment utilisée -- NRU (Not Recently Used)
 71

Algorithme de Remplacement -1- FIFO

• Algorithme Aléatoire - Random:
 La victime est choisie au hasard

• FIFO:
 Lors d‟un défaut de page, la page la plus anciennement chargée est la page
retirée pour être remplacée. Ceci implique la datation lors du chargement de
chaque page virtuelle.

 Facile à implanter
 Remplacement d‟une page très référencée  trop de défaut de pages.

• Exemple 1: Supposons avoir 3 cases et 4 pages avec la chaîne de référence

suivante :
ABCABDADBCB

cases\ref. A B C A B D A D B C B

1 A A A A A D D D D C C

2 B B B B B A A A A A
3 C C C C C C B B B
X X X X

(3 placements + 4 remplacements) => 7 défauts

 72

Algorithme de Remplacement -1- FIFO

• Exemple 2: Mémoire avec 4 cases

Time 0 1 2 3 4 5 6 7 8 9 10
Requests c a d b e b a b c a

Page 0 a a a a
Frames 1 b b
2 c c c c c
3 d d d

Page faults X
 73

Algorithme de Remplacement -1- FIFO

• Exemple 2: Mémoire avec 4 cases

Time 0 1 2 3 4 5 6 7 8 9 10
Requests c a d b e b a b c a

Page 0 a a a a a a
Frames 1 b b b b
2 c c c c c e e
3 d d d d d

Page faults X
 74

Algorithme de Remplacement -1- FIFO

• Exemple 2: Mémoire avec 4 cases

Time 0 1 2 3 4 5 6 7 8 9 10
Requests c a d b e b a b c a

Page 0 a a a a a a a a c c
Frames 1 b b b b b b b b
2 c c c c c e e e e e e
3 d d d d d d d d a

Page faults X X X
 75

Algorithme de Remplacement -2- Optimal

Algorithme Optimal:

 Principe:

 Repose sur la connaissance des références futures aux pages virtuelles.

 S‟il existe des pages qui ne seront plus référencées, alors remplacer l‟une
de ces pages.

Sinon remplacer la page qui sera référencée le plus tard possible.

Nécessite la connaissance, pour chacune des pages, la séquence

d‟instructions qui seront exécutées avant que la page soit référencée.

 Algorithme irréalisable dans un contexte ‟‟online‟‟.

 Connaissance des références qui seront faites.

 Intérêt : permet de comparer les performances des autres algorithmes.

 76

Algorithme de Remplacement -2- Optimal

Algorithme Optimal:

 Exemple 1: reprendre exemple 1 en appliquant optimal.

cases\ref. A B C A B D A D B C B

1 A A A A A A A A A C C

2 B B B B B B B B B B
3 C C C D D D D D D
X X

5 défauts de pages
(3 placements + 2 remplacements)
 77

Algorithme de Remplacement -2- Optimal

• Exemple 2:

Time 0 1 2 3 4 5 6 7 8 9 10
Requests c a d b e b a b c d

Page 0 a a a a a
Frames 1 b b b b b
2 c c c c c
3 d d d d d

Page faults X
 78

Algorithme de Remplacement -2- Optimal

• Exemple 2:

Time 0 1 2 3 4 5 6 7 8 9 10
Requests c a d b e b a b c d

Page 0 a a a a a a a a a a
Frames 1 b b b b b b b b b b
2 c c c c c c c c c c
3 d d d d d e e e e e

Page faults X X
 79

Algorithme de Remplacement -3- LRU

Algorithme LRU (Least Recently Used):

 Principe: remplacer la page la moins récemment utilisée (accédée) par le

processus.

Remplacer la page qui est restée inutilisée le plus de temps.

Basé sur la connaissance passée des références des pages.

 Ceci impose la datation de toutes les références.

 Théoriquement réalisable mais très coûteux.

 Nécessite des dispositifs matériels particuliers.

 Présente une bonne approximation pour l‟algorithme Optimal.

 80

Algorithme de Remplacement -3- LRU

Algorithme LRU (Least Recently Used):

 Exemple: énoncé exemple 1 + chaîne de référence A B C D A B C D A B C D.

cases\ réf. A B C D A B C D A B C D

1 A A A D D D C C C B B B

2 B B B A A A D D D C C
3 C C C B B B A A A D
X X X X X X X X x

LRU : 12 défauts de pages

Optimal: ?
 81

Algorithme de Remplacement -3- LRU

• Exemple 2:

Time 0 1 2 3 4 5 6 7 8 9 10
Requests c a d b e b a b c d

Page 0 a
Frames 1 b
2 c
3 d

Page faults
 82

Algorithme de Remplacement -3- LRU

• Exemple 2:

Time 0 1 2 3 4 5 6 7 8 9 10
Requests c a d b e b a b c d

Page 0 a a a a a a a a a a a
Frames 1 b b b b b b b b b b b
2 c c c c c e e e e e d
3 d d d d d d d d d c c

Page faults X X X
 83

Algorithme de Remplacement - 4 - NRU

Algorithme NRU (Not Recently Used):

 Idée: marquer les pages référencées.

 Principe:
 A chaque page sont associées deux bits R et M :
 R=1 chaque fois que la page est référencée (lecture/écriture), R=0
sinon
 M=1 lorsque la page a été modifiée par écriture dans la mémoire
centrale.
Au lancement d‟un processus, le SE met à zéro R et M de toutes les
pages.
Périodiquement, le bit R est remis à 0 pour différencier les pages qui n‟ont
pas été récemment référencées des autres.
Lors d‟un défaut de page, le SE retire une page au hasard dont la valeur
RM est la plus petite :
 RM = 00 : non référencée, non modifiée
 RM = 01 : non référencée, modifiée
 RM = 10 : référencée, non modifiée
 RM = 11 : référencée, modifiée
 Algorithme basé sur une solution matérielle
 84

Algorithme de Remplacement - Conclusion

• Critère de performance:

Optimal LRU NRU FIFO/Aléatoire

+ -
• La taille de la MC influe beaucoup sur les performances de l‟algorithme :
 N‟essayer pas de raffiner un algorithme, mais plutôt augmenter, si nécessaire, la
taille de la mémoire, et ce afin de minimiser le remplacement.
• Question : est-ce que le rajout de mémoire réduit toujours le nombre de défauts de
pages?
 Oui pour seulement optimal et LRU
 Non pour FIFO!

Exemple 3 (Corrigé en Classe):

(1) On dispose de 3 cases mémoires. Appliquer FIFO, Optimal et LRU à la chaîne de
références suivante. Comparer les performances de ces algorithmes.
AB C DAB EAB CD E
(2) Rajouter 1 case et reprendre l‟algorithme de remplacement FIFO, Optimal et LRU.
Comparer et Conclure quant à l‟effet de la taille de la Mémoire Physique.

FIFO: Belady‟s Anomaly (Pb[défaut de page)=f(nbre de cases) curve.

 85

Conversion d’une Adresse Virtuelle

Procédure Conversion (Entrée : advirt; Sortie : adphysique)

Début
index = advirt.page + adresse_table(processus)
Si (non index.P) /* page absente */
Alors /* Défaut de page*/
charger_page(advirt.page, adresse_case
index.P = 1
index.case = adresse_case
finsi
adphysique = adresse_case + advirt.deplacement
Fin
Procédure charger_page (E : page; S : case)
Début
Si (Non trouver_case_libre())
Alors choisir_case_à_libérer(case_à_libérer, page_victime)
Si (page_victime.M) Alors ecrire_disque(page_victime)
finsi
lire_disque(case_voila_liberer, page)
finsi
Fin
 86

CHAPITRE 6. Gestion de Mémoire

Partie II: Mémoire Virtuelle

• Présentation
• Pagination – Transformation des Adresses
• Algorithmes de Remplacement
• FIFO - OPTIMAL - LRU – NRU
• Autres Considérations
• Politiques d‟Allocation (Locale/Globale)
• Ecroulement
• L‟ensemble de Travail
• Prépagination
 87

Autres Considérations
• Politique d’allocation locale/globale:

 Remplacement de la page la plus ancienne:

 Globale -- la plus ancienne du système.
 Locale -- la plus ancienne du processus.
 En général, l‟allocation globale produit de meilleurs résultats.

• La taille d’une page? Influe sur les tables de pages utilisées par la MMU.

• Mémoire de SWAP
 où stocker les pages délogées de la MC?
 sur un ou plusieurs disques locaux
 partition de swap : + rapide, - de place pour le SGF.
 Fichier de swap : - rapide, + de place pour les autres fichiers.
 En général, le SE utilise les deux simultanément.
 Plusieurs disques = swap en parallèle.
 sur un serveur (de disques) distant :
 Net PC, TX, STB, ...
 88

Autres Considérations
• Ecroulement – thrashing
 Si le nombre de processus est très grand, l‟espace propre à chacun est
insuffisant et ils passeront leur temps à gérer des défauts de pages.
 Ecroulement du système : une haute activité de pagination.
 un processus s'écroule lorsqu‟il passe plus de temps à paginer qu‟à
s'exécuter.
• Limiter le risque d'écroulement :
Allocation
Défaut plus de page Limite supérieure
de pages

Limite inférieure
Retrait de page

Nombre de pages
 Si un processus provoque trop de défauts de pages:
 au dessus d‟une limite supérieure : on lui allouera plus de cases.
 en dessous d‟une limite inférieure : on lui en retirera.

 S‟il n‟y a plus de pages disponibles et trop de défauts de pages, on devra

suspendre un des processus.
 89

Autres Considérations

• L’ensemble de travail -- Working set (W)

 W = Les pages d‟un processus référencées sur une courte

période de temps (t2-t1).

Une allocation optimale: Allouer à un processus actif autant

de cases que nécessite W.

 Minimisation des défauts de page: Les défauts de pages

seront provoqués lors des changements d‟espace de travail.

Ce modèle n‟est utilisé que pour la pré-pagination.

 90

Autres Considérations
• Pré-pagination
 Lors du lancement d‟un processus ou lors de sa reprise après
suspension, on provoque obligatoirement un certain nombre de défauts de
page.
 Essayer de les limiter - enregistrer W avant suspension.
Au lancement d‟un programme les 1ères pages de code seront
vraisemblablement exécutées.

Conclusion
• Découpage en pages et cases de même taille.

• Les pages d‟un processus ne sont chargées en mémoire physique que

lorsque le processus y accède.
 les pages peuvent être mises dans n‟importe quelle case.

• Lorsqu‟un processus accède à une page non présente en mémoire physique,

il se produit un DEFAUT DE PAGE :
 la page manquante est alors chargée dans une case libre
 pas de case libre, le système utilise un algorithme de remplacement de
page pour choisir une case à libérer.