Gestion de la

Mémoire Pagination,
Partitionnement,
Segmentation
Gestion de la Mémoire

CONCEPTS
DE BASE
 Gestion de la
Mémoire
Concepts de Base
• La mémoire est une ressource importante et limitée qui
doit être gérer d’une façon optimale.
• Plusieurs types de mémoires peuvent être utilisés lors
de l’exécution d’un programme.
▪ Mais, pour s’exécuter, un programme doit être placé en
mémoire centrale.
(swappin

volatile
Mem.
• La gestion de la mémoireRegistre
peut se faire avec ou sans
s UC
g).

stockage
Capacité de
va-et-vient

d’accès
Vitesse
Cache
RAM/
ROM
volatile
Mem. Non
Disqu

es

Band
 Gestion de la Mémoire Centrale:
Objectifs
Concepts de Base
• Optimisation de l ’utilisation de la mémoire principale
(RAM)
• Les plus grand nombre possible de processus actifs
doit y être gardé, de façon à optimiser le
fonctionnement du système en
multiprogrammation
▪ Garder le système le plus occupé possible, surtout l’UCT
▪ S’adapter aux besoins de mémoire de l ’usager
▪ Allocation dynamique au besoin
• Concepts
▪ Adresse physique et adresse logique
▪ Remplacement
▪ Allocation contiguë (partitions fixes et variables)
▪ Pagination
▪ Segmentation
Mémoire Physique et Mémoire
Logique
Concepts de Base
• Mémoire physique:
▪ La mémoire principale RAM de la machine
▪ Adresses physiques: les adresses de cette mémoire

• Mémoire logique: l’espace d’adressage d’un

programme
▪ Adresses logiques: les adresses dans cet espace

• Il faut séparer ces concepts car normalement, les

programmes sont chargés de fois en fois dans des
positions différentes de la mémoire
▪ Donc adresse physique ≠ adresse logique

Dr. Ghada GASMI- Dr. Lilia SFAXI

Traduction Adresses Physiques &
Logiques
Concepts de Base

MMU: Memory
Management Unit
 Chargement d’un Module en
Mémoire
Concepts de Base
• Étapes de chargement
▪ Trouver de la mémoire libre pour un module de chargement
o Contiguë ou non contiguë
▪ Traduire les adresses du programme et effectuer les liaisons par
rapport aux adresses où le module est chargé
• Dans les premiers systèmes, un programme était toujours
chargé dans la même zone mémoire
• La multiprogrammation et l’allocation dynamique ont
engendré le besoin de charger un programme dans
différentes positions
▪ Au début, ceci était fait par le chargeur (loader) qui changeait
les adresses avant de lancer l ’exécution
▪ Aujourd’hui, ceci est fait par le MMU au fur et à mesure que le
programme est exécuté
• Ceci ne cause pas d’hausse de temps d ’exécution, car
le MMU agit en parallèle avec d’autres fonctions d’UCT
▪ Par ex. l ’MMU peut préparer l ’adresse d’une instruction en
même temps que l’UCT exécute l ’instruction précédente
 Permutation
(Swapping)
Concepts de Base
• Un programme, ou une partie de programme,
peut être
temporairement enlevé de mémoire pour
permettre l’exécution d’autres programmes
▪ Il est mis dans la mémoire secondaire, normalement le
disque
 Allocation en
Mémoire
Concepts de Base
• Plusieurs types d’allocation
▪ Contiguë
: Le processus est chargé en entier dans la mémoire,
dans un bloc contigu
o L’allocation contiguë n’est plus utilisée aujourd’hui pour la
mémoire centrale, mais les concepts que nous verrons sont
encore utilisés pour l’allocation de fichiers sur disques

▪ Non-Contiguë
: Le processus est subdivisé et éparpillé dans
la RAM, et un mécanisme est défini pour retrouver les
différentes briques une fois le programme chargé
• La mémoire peut être:
▪ Partitionnée
: subdivisée depuis le démarrage en partitions
fixes
▪ Non-partitionnée
: les partitions seront créées au fur et à
mesure que les programmes sont chargés et déchargés de
la mémoire
Gestion de la Mémoire

ALLOCATION
CONTIGUË
 Partitions
FixesContiguë
Allocation
• Mémoire principale subdivisée en
régions distinctes: partitions

• Les partitions sont soit de même

taille ou de tailles inégales

• N’importe quel programme peut être

affecté à une partition qui soit
suffisamment grande
▪ Un programme doit tenir sur une seule
partition
▪ Une partition ne peut contenir
qu’un seul programme

• Problème de fragmentation: Il y’a assez

d’espace
pour exécuter un programme, mais cet
 Partitions Fixes de Tailles
Inégales
Allocation Contiguë
• Diviser la mémoire en N partitions qui peuvent être de
tailles inégales et associer à chaque partition une file
d’attente.
• Chaque nouvelle tâche est placée dans la file d’attente
de la plus petite partition qui peut la contenir.
• L’espace non utilisé dans une partition est perdu (pb de
Partition 3 Partition 3
fragmentation)
Files Problème:
multiples
Saturation des
Partition 2 files d’attente Partition 2
des petites
partitions File
Partition 1 unique Partition 1

Noyau Noyau
 Partitions
Dynamiques
Allocation Contiguë
• Initialement, la mémoire n’est pas partitionnée
• Les partitions se créent au fur et à mesure que les
processus entrent et sortent de la mémoire
▪ Ils varient en nombre, en taille et en position

B B B
A A
C C
SE SE SE SE SE SE S
E
Temps
• Utilise la technique de va-et-vient ou encore
▪ La mémoire est une ressource ne pouvant pas contenir tous les
swapping
processus. Il est alors nécessaire de déplacer quelques processus
sur le disque et de les ramener en RAM avant de les exécuter.
fragmentation externe
• Problème de
 Partitions Dynamiques:
Exemple
Allocation Contiguë

• Mémoire=1024K, OS=128K, P1=320K, P2=224K, P3=228K,

P4=128K.
• (d) Il y a un trou de 64K après avoir chargé 3 processus: pas
assez d’espace pour d’autres processus
• Si tous les processus se bloquent ([Link]. attente d’un
événement), P2 peut être permuté et P4=128K peut être chargé.
 Partitions Dynamiques:
Exemple
Allocation Contiguë

• (e-f) P2 est suspendu, P4 est chargé. Un trou de 224-128=96K est créé

(fragmentation externe)
• (g-h) P1 se termine ou il est suspendu, P2 est repris à sa place: produisant
un autre trou de 320-224=96K...
• Nous avons 3 trous petits et probablement inutiles.
▪ 96+96+64=256K de fragmentation externe
• COMPRESSION pour en faire un seul trou de 256K
 Algorithmes de
Placement
Allocation Contiguë
• Pour décider l’emplacement du
prochain processus
• But: réduire l’utilisation de la
compression qui prend du temps...
• Choix possibles:
▪ Best fit: choisir le plus petit trou
(meilleur accès)
▪ Worst fit: le plus grand (pire accès)
▪ First-fit: choisir 1er trou à partir du
début (premier accès)
▪ Next-fit: choisir 1er trou à partir du
dernier placement (prochain accès)
• En pratique, utiliser l’algorithme le plus
simple, donc FF
 Gestion de la Mémoire

ALLOCATION NON
CONTIGUË
 Allocation Non
Contiguë
Allocation Non Contiguë
• Afin de réduire la fragmentation, tous les systèmes
d’aujourd’hui utilisent l’allocation non contiguë
▪ diviser un programme en morceaux et permettre l’allocation
séparée de chaque morceau
▪ les morceaux sont beaucoup plus petits que le programme
entier et donc permettent une utilisation plus efficace de la
mémoire
o les petits trous peuvent être utilisés plus facilement
• Il y a deux techniques de base pour faire ceci: la
pagination et la segmentation
▪ La segmentation utilise des parties de programme qui ont
une valeur logique (des modules)
▪ La pagination utilise des parties de programme arbitraires
(morcellement du programmes en pages de longueur fixe).
▪ Elles peuvent être combinées
 Gestion de la Mémoire

ALLOCATION NON
CONTIGUË : PAGINATION
Définiti
on
Pagination
• La mémoire est partitionnée en petits morceaux de même taille: les
pages physiques cadres frames
ou ou

• Chaque processus est aussi partitionné en petits morceaux de même

pages logiques
taille appelés (pages)

• Les pages logiques d’un processus peuvent donc être assignées

aux cadres disponibles n’importe où en mémoire principale

• Conséquences:
▪ un processus peut être éparpillé n’importe où dans la mémoire physique.
externe
▪ la fragmentation est éliminée
 le
Paginatio
n

• Supposons que le processus B se termine ou

est suspendu
Exemp
le
Pagination
• Nous pouvons maintenant transférer
en mémoire un processus D, qui
demande 5 cadres
▪ Bien qu’il n’y ait pas 5 cadres contigus
disponibles

• La fragmentation externe est limitée

au cas que le nombre de pages
disponibles n’est pas suffisant pour
exécuter un processus en attente

• Seule la dernière page d’un processus

peut souffrir de fragmentation interne
▪ En moyenne 1/2 cadre par processus
Table de
Page
Pagination

Les entrées dans la table de

pages sont aussi appelées
descripteurs de pages
 Table de
Page
Pagination
• Le SE doit maintenir une table de pages pour chaque
processus
• Chaque descripteur de pages contient le numéro de
cadre où la page correspondante est physiquement
localisée
• Une table de pages est indexée par le numéro de la
page afin d’obtenir le numéro du cadre
• Une liste de cadres disponibles est également
maintenue (free frame list)
 Traduction
d’Adresses
Pagination
• L’adresse logique est facilement traduite
en adresse physique
▪ car la taille des pages est une puissance de 2
▪ les pages débutent toujours à des adresses
qui sont des puissances de 2
▪ qui ont autant de 0 à droite que la longueur de
l’offset
▪ donc ces 0 sont remplacés par l’offset
(déplacement)

• Ex: si 16 bits sont utilisés pour les adresses

et que la taille d’une page = 1K: on a
besoin de 10 bits pour le décalage, laissant
ainsi 6 bits pour le numéro de page

• L’adresse logique (p,d) est traduite en

adresse
physique (f,d) en utilisant p comme index
Traduction
d’Adresses
Pagination
Traduction
d’Adresses
Pagination
Exercice
1
Pagination
• Hypothèses:
▪ Bus d’adresses de 16 bits
▪ Taille d’une page 4Ko =
4096 o (adresse sur
12bits)

▪ Table de page (ci contre)

• Question
▪ Calculer l’adresse physique
correspondante à l’adresse logique
(virtuelle) 8196
 Exercice 1 -
Correction
Pagination

• Adresse physique=
24580
 Exercice 2 Pagination

• Soit un ordinateur ayant :

▪ Une mémoire physique de capacité 128 Mo
▪ Une architecture 32 bits.
▪ La taille d'une page égale à 4 Ko,
▪ Une adresse virtuelle indexe un octet

• Donner la taille de la table des pages.

▪ Chaque entrée de la table (référence d’un cadre +
bit présence absence)

Slide 30
 Exercice 2: Correction Pagination
• Taille table des pages = Taille d'une entrée de la table x Nombre d'entrées de
la table
• Nombre d'entrées de la table = Taille de l'espace virtuelle / taille d'une page
• Taille de l'espace virtuelle = nombre d'adresses virtuelles possible x 1octet = 232
octets
▪ (car par défaut une adresse virtuelle indexe un octet dans la mémoire virtuelle)
• Nombre d'entrées de la table = (232 octet)/(4x1024 octet) = 220 entrées
• La taille d'une entrée de la table des pages =1 bit (d'absence/présence) + nombre
de bits utilisés pour référencer un cadre de page dans la mémoire physique.
• Pour déterminer le nombre de ces bits il faut déterminer le nombre de cadres de
page, soit égal à: (128 x 1024 ko)/(4 ko) = (27 x 210)/(22)= 215 cadres de pages
• D'où le nombre de bits nécessaires pour référencer les cadres de page est 15
taille d'une entrée de la table des pages = 1 + 15 = 16 bits
• Taille table des pages = taille d'une entrée de la table x le nombre d'entrées de la
table = 220 x 16 bits = 16 Mbits = 2 Mo
Slide 31
 Défaut de Page Pagination
• Dans la Table de Page, lorsque le bit de présence est à 0,
default de page
un se produit et le système effectue un
déroutement
pour récupérer la page manquante à partir du
disque.

• Pour remettre la page récupérée sur la RAM, il faut vider

une case de la mémoire physique en utilisant un
algorithme de remplacement de page.

Slide 32
Algorithmes de Remplacement de Page Pagination
• Les algorithmes de remplacement de pages sont (entre
autres):
▪ L’algorithme First In First Out (FIFO):
o Remplacer la page la plus ancienne dans la mémoire.

▪ L’algorithme Least Recently Used (LRU):

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

▪ L’algorithme optimal
o Retirer de la mémoire la page qui sera référencée le plus tard. C’est
un algorithme théorique car il nécessite la connaissance des
requêtes futures.
▪ L’algorithme Not Recently Used (NRU):
o Remplacer la page la non récemment utilisée; c’est une solution
matérielle.
 Technique de Segmentation
Segmentation
• La segmentation utilise des parties de programme qui
ont une valeur logique (des modules)
▪ Générés à la compilation,
▪ Un segment est un ensemble d'adresses virtuelles contiguës.
numéro S longueur
▪ Chaque segment est repéré par son et sa
variable L
.

• Contrairement à la pagination, la segmentation

est "connue" du processus
S,d
▪ Une adresse est donnée par un couple ( ),
o S est le n° du segment
o d le déplacement dans le segment, d ∈ [0 , L [ .

table Slide 34
• Pour calculer l'adresse physique, on utilise une
 Table de
Segments
Segmentation
• Le tableau des segments contient des descripteurs de
segments
▪ B
: l’adresse de base
▪ L
: la longueur du segment
▪ p
: Infos de protection

• Dans le PCB du processus il y aura un pointeur à

l’adresse en mémoire de la table de segments
▪ Il y aura aussi là dedans le nombre de segments dans le
processus

• Au moment de la commutation de contexte, ces infos

Traduction
d’Adresses
Segmentation
Traduction
d’Adresses
Segmentation
Partage de
Segments
Segmentation
 Partage de
Segments
Segmentation
R1 Données
Progra proc 1
mme +

Instruction

R2
+ Données
proc 2

• La même instruction, si elle est exécutée

▪ par le proc 1, son adresse est modifiée par le contenu du
registre 1
▪ par le proc 2, son adresse est modifiée par le contenu du
registre 2

• Ceci fonctionne même si l’instruction est exécutée par

plusieurs UCT au même instant, si les registres se
 Segmentation Simple: Avantages et
Segmentation Inconvénients

• Avantages:
▪ l’unité d’allocation de mémoire est plus petite que le
programme entier
▪ l’unité d’allocation de mémoire est une entité logique
connue par le programmeur
▪ Les segments peuvent changer de place en mémoire
▪ La protection et le partage de segments sont aisés (en
principe)

• Désavantage: le problème des partitions dynamiques

▪ Mêmes problématiques que pour l’allocation contiguë
à partitions dynamiques
▪ La fragmentation externe n’est pas éliminée:
o trous en mémoire, compression?
 Segmentation
Paginée
Segmentation

• La taille d'un segment peut être importante, d'où un temps

de chargement long qui peut en résulter. La pagination des
segments peut être une
solution.
• Une adresse virtuelle (S , d) est transformée en (S , P , d'
), où P est un numéro de page et d’ un déplacement
dans la page P.
• Exemple : avec des pages de 4 Ko, l'adresse logique
(2 , 9392) est transformée en (2 , 2, 1200)