STRUCTURE ET
ORGANISATION DES
MÉMOIRES
1. Hiérarchie des mémoires
La grande variété de systèmes de stockage dans un système informatique peut être organisée
dans une hiérarchie selon leur vitesse et leur coût.
- Les niveaux supérieurs sont chers mais rapides. Au fur et à mesure que nous descendons
dans la hiérarchie, le coût par bit diminue alors que le temps d'accès augmente.
- En plus de la vitesse et du coût des divers systèmes de stockage, il existe aussi le
problème de la volatilité de stockage. Le stockage volatile perd son contenu quand
l'alimentation électrique du dispositif est coupée.
- La mémoire cache (antémémoire) : La mise en mémoire cache est un principe important
des systèmes informatiques autant dans le matériel que dans le logiciel. Quand une
information est utilisée, elle est copiée dans un système de stockage plus rapide, la
mémoire cache, de façon temporaire. Quand on a besoin d'une information particulière,
on vérifie d'abord si elle se trouve dans la mémoire cache, sinon on ira la chercher à la
source et on mémorise une copie dans la mémoire cache, car on suppose qu'il existe
une grande probabilité qu'on en aura besoin une autre fois.
1
2. Adressage logique / Adressage physique
- 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
Adressage logique / Adressage physique
Une adresse générée par le processeur est appelée adresse logique. Tandis qu'une adresse vue
par l'unité mémoire, c'est à dire celle qui est chargée dans le registre d'adresse de la mémoire,
est appelée adresse physique. Il est nécessaire au moment de l'exécution de convertir les
adresses logiques en adresses physiques. - Étapes de chargement
- Trouver de la mémoire libre pour un module de chargement
- 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.
2
Les politiques de gestion
de la mémoire avec
partitions multiples
contigües
1. Partitions contiguës fixes
Principe
Dans cette stratégie la mémoire est divisée en n partitions de tailles fixes (si possible inégales).
Ce partitionnement se fait au démarrage du système. Le système d'exploitation maintient une
table de description des partitions.
Cette forme d'allocation 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 disque.
- Mémoire principale subdivisée en régions distinctes: partitions
- 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
espace est fragmenté de façon non contiguë.
- Fragmentation interne : espace entre les partitions
- Fragmentation externe : espace dans les partitions
Méthode : Allocation de partitions fixes : files d'attente séparées
Quand un processus arrive, il peut être placé dans la file d'attente des entrées de la plus petite
des partitions assez larges pour le contenir.
3
Partitions contiguës dynamiques
Méthode : Allocation de partitions fixes : file d'attente commune
Une autre organisation possible consiste à gérer une seule file d'attente. Dès qu'une partition
devient libre, toute tâche placée en tête de file d'attente et dont la taille convient peut être
chargée dans cette partition vide et exécutée.
2. Partitions contiguës dynamiques
Principe
Dans cette stratégie la mémoire est partitionnée dynamiquement selon la demande. Lorsqu'un
processus se termine sa partition est récupérée pour être réutilisée (complètement ou partiellement)
par d'autres processus.
Mais comment allouer un espace de taille n à un processus à partir d'une liste de trous libres ? On
peut utiliser l'un des trois algorithmes suivant : first-fit, best-fit, worst-fit.
Le lancement des processus dans les partitions se fait selon différentes stratégies. Pour cela le
gestionnaire de la mémoire doit garder trace des partitions occupées et/ou des partitions libres.
On distingue les stratégies de placement suivantes:
- Stratégie du premier qui convient (First Fit): La liste des partitions libres est triée par
ordre des adresses croissantes. La recherche commence par la partition libre de plus
basse adresse et continue jusqu'à la rencontre de la première partition dont la taille est
au moins égale à celle du processus en attente. On alloue au processus le premier bloc
suffisamment grand.
- Stratégie du meilleur qui convient (Best Fist): On alloue la plus petite partition dont la
taille est au moins égale à celle du processus en attente. La table des partitions libres
est de préférence triée par tailles croissantes. Cet algorithme nécessite le parcours de
toute la liste des espaces libres.
- Stratégie du pire qui convient (Worst Fit): On alloue au processus la partition de plus
grande taille. Cet algorithme nécessite le parcours de toute la liste des espaces libres.
Des expériences ont prouvé que l'algorithme de First-fit est la meilleure.
4
Exemple : Allocation de partitions dynamiques contigües
Soit une MC dont la table des partitions libres est la suivante :
Soit les demandes suivantes P4 (24K), P5 (128K), P6 (256K) .
Evolution de la table des partitions libres:
Partitions contiguës Siamoises (Buddy system)
3. Partitions contiguës Siamoises (Buddy system)
C'est un compromis entre partitions de tailles fixes et partitions de tailles variables. La
mémoire est allouée en unités qui sont des puissances de 2. Initialement, il existe une seule
unité comprenant toute la mémoire. Lorsque de la mémoire doit être attribuée à un processus,
ce dernier reçoit une unité de mémoire dont la taille est la plus petite puissance de 2 supérieure
à la taille du processus. S'il n'existe aucune unité de cette taille, la plus petite unité disponible
supérieure au processus est divisée en deux unités "siamoises" de la moitié de la taille de
l'original. La division se poursuit jusqu'à l'obtention de la taille appropriée. De même deux
unités siamoises libres sont combinées pour obtenir une unité plus grande.
(cf. p.22) (cf. p.22)
*
5
Les politiques de gestion
de la mémoire avec
partitions multiples non
contiguës
La traduction dynamique d'adresse réalisée par l'emploi d'un registre de base impose que les
programmes soient chargés en mémoire principale dans des cellules contiguës. Nous avons
vu que les techniques d'allocation associées conduisent à la fragmentation de la mémoire.
Pour l'éviter, il faut pouvoir implanter un programme dans plusieurs zones non contiguës.
Plusieurs techniques proposent d'allouer des espaces mémoire non-contiguës pour les
processus : Pagination et Segmentation
1. La Pagination
La solution apportée par les mécanismes de pagination consiste à découper l'espace
adressable, ou espace logique d'un processus en zones de taille fixe appelée pages. La
mémoire réelle est également découpée en cases ou cadre (frame en anglais) ayant la taille
d'une page de sorte que chaque page peut être implantée dans n'importe quelle case de la
mémoire réelle.
- Conséquences:
- un processus peut être éparpillé n'importe où dans la mémoire physique.
- la fragmentation externe est éliminée
- Principe et fonctionnement
Adressage
Une adresse est divisée en deux parties : un numéro de page p et un déplacement à l'intérieur
de la page d. La taille de la page (et donc de la case) est une puissance de 2 variant
généralement entre 512 et 8192 octets selon les architectures. Le choix de tailles de puissance
2 permet de simplifier la division nécessaire pour calculer le numéro de page et le
déplacement à partir d'une adresse logique, ainsi :
Si la taille de l'espace d'adressage logique est 2m et la taille d'une page est 2n
(octets ou mots): - Les m-n bits de poids fort d'une adresse paginée
désignent le numéro de page ; et - Les n bits de poids faible désignent le
déplacement dans le page.
La Pagination
6
Si T est la taille d'une page et A une adresse logique, l'adresse paginée (p, d) est déduite à
partir des formules :
- p = A div T
- d = A modulo T
L'adresse logique est égale à : A = p*T + d
La Table des pages
La traduction des adresses utilise une table des pages qui est située en mémoire centrale ou
dans des registres, et dans laquelle les entrées successives correspondent aux pages virtuelle
consécutives. La p-ième entrée de la table des pages contient le numéro r de la case où est
implantée la case p, et éventuellement des indicateurs supplémentaires
Exemple
L'exemple suivant montre un système ayant une mémoire logique de 4 pages et une mémoire physique de 8
pages.
7
- 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.
- Avec la pagination, il n y a plus de fragmentation externes (s'il y a suffisamment de
mémoire (de pages) non allouée à un programme il les aura), par contre la fragmentation
interne persiste: si un programme nécessite 2 pages et 1 octet, il aura 3 pages.
La Traduction d'adresse
L'adresse réelle (f,d) d'un mot d'adresse virtuelle (p,d) est obtenue en remplaçant le numéro
de page p par le numéro de case f trouvé dans la p-ième entrée.
La segmentation
- Exemple
8
Page partagée
Un autre avantage de la pagination est la possibilité de partager du code commun. Cette
caractéristique est particulièrement importante dans un environnement partagé. Imaginons un
système qui supporte 40 utilisateurs, chacun d'eux exécutant un éditeur de textes. Si l'éditeur
est constitué de 150 Ko de code et 50 Ko de données, on aura besoin de 8000 Ko pour
satisfaire les 40 utilisateurs. Cependant si le code est réentrant, il peut être partagé comme le
montre le schéma suivant :
Le schéma précédant montre que les 3 pages de code de l'éditeur de textes sont partagées par les 3
processus. Chaque processus, par contre, possède sa propre page de code.
Le code réentrant (encore appelé code pur) est un code invariant ; c'est à dire qu'il ne change
jamais pendant l'exécution. Ainsi, deux ou plusieurs processus peuvent exécuter le même
code en même temps. Chaque processus possède sa propre copie de registres et son stockage
de données. On doit maintenir en mémoire physique une seule copie de l'éditeur. La table de
pages de chaque processus correspond à la même structure physique de l'éditeur, mais les
cadres de pages sont transformés à des cadres de pages différents. Ainsi, pour supporter 40
utilisateurs nous n'avons besoin que d'une copie de l'éditeur (ie 150 Ko), plus 40 copies de
l'espace de données de 50 Ko par utilisateur. L'espace requis est donc de 2150 Ko au lieu de
8000 Ko.
2. La segmentation
La segmentation est analogue à la pagination sauf que la taille d'un segment est variable.
L'espace d'adressage logique est divisé en un ensemble de segments.
L'avantage de la segmentation par rapport à la pagination, est que les segments peuvent
refléter une vision logique du programme. - Principe
- Table de segments
La segmentation consiste à découper l'espace logique en un ensemble de segments.
Chacun des segments est de longueur variable ; la taille dépend de la nature du segment
dans le programme.
Segmentation paginée
9
Une adresse logique est dite segmentée. Elle comprend un numéro de segment
(s) et un déplacement dans le segment (d). (s) est utilisé comme index dans la
table de segments. La table de segments est généralement implantée par des
registres rapides. Si d > limite : alors erreur de débordement (fameux
Segmentation fault). Pour cibler une zone mémoire spécifique, on doit donc
désigner deux paramètres : un numéro de segment et un déplacement. :
De ce point de vue, la segmentation est différente de la pagination, puisque dans la pagination,
l'utilisateur ne spécifie qu'une seule adresse qui est décodée par le SE en un numéro de page
et un déplacement.
En segmentation la conversion d'une adresse logique en une adresse physique est faite grâce
à une table de segments. Chaque entrée de la table de segment possède deux valeurs :
- La base : c'est l'adresse de début du segment en mémoire.
- La limite : spécifie la taille du segment.
L'espace d'adressage physique correspondant peut ne pas être contigu.
Traduction d'adresse
Illustration
Soit un espace d'adressage logique contenant quatre segments
10
Faisons la conversion des adresses logiques suivantes en adresses physiques :
- Remarque : Segmentation et fragmentation externe
Avec la segmentation la taille des segments est variable ce qui peut engendrer une
fragmentation externe. Ceci peut être résolu en combinant la segmentation et la pagination.
3. Segmentation paginée
C'est une combinaison de la segmentation et de la pagination
- Adressage en segmentation paginée L'adressage est composé de deux niveaux :
Application
- Le niveau segment
- Le niveau page
Chaque segment est un espace linéaire d'adressage logique. Il est découpé en pages. Une adresse
est formée de trois parties : (s, p, d')
- s : numéro du segment
- p : numéro de page
- d' : déplacement dans la page
Méthode : Table de page
11
La table de page est divisée en portions. Chaque portion concerne un segment bien précis. La base
permet de retrouver la portion concernant le segment donné, et p donne le numéro de page dans cette
portion.
4. Application
Exemple 1
- 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
sur la table des pages et en le remplaçant par l 'adresse f trouvée depuis la table. d ne
change pas.
Exemple 2
- 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 8196
12
13
14