La mémoire

Introduction

La mémoire a toujours été une ressource indispensable d'un système. Elle est partagée entre tous les processus. La mémoire est une suite non structurée d'octets, le système d'exploitation ne connait donc pas la structure des informations en mémoire (qui dépendent de chaque processus).

Importance de la mémoire

Les instructions d'un programme peuvent contenir des adresses mémoires en argument, il est ainsi nécessaire qu'un processus se trouve entièrement en mémoire pour pouvoir s'exécuter. Une gestion efficace de cette mémoire est alors primordiale.

Types de mémoires

Registres

Les registres sont des zones mémoires attachées au processus, leur taille est généralement très réduite (de l'ordre de quelques Ko) mais sont extrêmement rapides, pouvant généralement être accédé en un seul cycle d'horloge du processeur.

Mémoire vive (RAM)

La mémoire vive est la mémoire principale du système. Elle est la ressource importante à gérer et est souvent présente en quantité (entre deux et 64 Go). Elle est standardisée aux normes DDR3 et DDR4. Elle est plus lente par rapport au CPU (il faut parfois plusieurs cycles d'horloge pour récupérer une information), le CPU doit donc attendre ou mettre la donnée en cache. Cependant, cette ressource reste beaucoup plus rapide qu'un disque (SSD ou HDD).

Mémoire cache

La mémoire cache a pour but d'améliorer les performances générales du système en planquant en mémoire plus rapide les données fréquemment demandées.

Il existe trois niveaux de mémoire cache, le premier niveau sert à stocker temporairement des instructions et données. Les deux autres niveaux sont présents entre la mémoire RAM et la mémoire cache de premier niveau.

Mémoire virtuelle

La mémoire virtuelle est une mémoire simulée par le système. Elle utilise le disque dur comme RAM additionnelle. Elle est seulement limitée par la taille du disque dur, mais elle est très lente.

Isolation de la mémoire

Il est essentiel que chaque processus ait une zone mémoire réservée pour éviter des problèmes de sécurité et d'intégrité des données.

Un processus ne peut donc pas écrire dans l'espace mémoire d'un autre. S'il essaye, on aura une "Segmentation Fault". La mémoire n'est de ce fait pas partagée entre les processus sauf lorsque cela est explicitement demandé. (Voir Mémoire partagée pour plus d'informations).

Translation d'adresse

Lorsqu'un programme est chargé, il est placé entièrement en mémoire à une adresse de départ. Son espace d'adressage est défini et les instructions du programme font référence à l'adresse 0.

La translation peut être effectuée à 3 moments :

– Au chargement (l'adresse de départ est choisie lors du chargement du processus par le système d'exploitation) ;

Types d'adresses

On parle d'adresse logique pour parler de l'adresse présente dans les programmes (qui se réfèrent à l'adresse 0).

On parle en revanche d'adresse physique pour parler d'une case mémoire adressable de la mémoire RAM.

La conversion entre l'adresse logique et l'adresse physique est faite par le Memory Management Unit (MMU) qui est un composant matériel spécialisé dans l'opération de translation.

Allocation

Le système d'exploitation, les processus systèmes et utilisateurs se trouvent dans la mémoire, il faut donc un mécanisme de protection pour isoler les processus. Ce mécanisme, c'est le MMU vu plus tôt.

Mono-programmation

Lorsqu'un seul processus s'exécute à la fois en même temps que le système d'exploitation, c'est le cas sur les systèmes très rudimentaires comme MS-DOS.

Étant donné qu'il n'y a qu'un seul processus à la fois, le système d'exploitation n'a pas beaucoup à faire, car il n'y a pas besoin d'isoler la mémoire (sauf pour la petite partie réservée au système d'exploitation).

Le BIOS réalise une gestion des périphériques.

Multi-programmation

Partitions fixes

On peut pré-découper la mémoire en morceaux de taille variable (les partitions). On va donc tenter de placer chaque processus dans la plus petite partition qui peut la contenir.

L'un des problèmes de ce système est qu'il va y avoir beaucoup de restes (fragmentation interne) car si un a besoin de quatre unités, mais que la seule partition que l'on peut prendre en contient 8, on a quatre unités non utilisées.

Partitions variables

On alloue l'espace selon les besoins des processus, on va créer des partitions en fonction des demandes faites par les processus.

Table de bits

La table de bits correspond à une cartographie de la mémoire découpe en blocs d'allocations de taille fixe. Pour chaque bloc, on va noter un 1 si c'est occupé, ou un 0 si le bloc est libre dans la table de bits.

Ainsi, il suffit de seulement stocker 1 bit par unité d'allocation. Cependant, le problème est que si les unités d'allocations sont petites, alors il la table sera grande, mais ce sera plus précis.

À l'inverse, si les unités d'allocations sont grandes, la table sera plus petite, mais sera moins précise (ce qui implique donc un plus grand gaspillage de mémoire).

Un autre problème est que plus la taille est grande, moins l'allocation sera rapide, car il faudra parcourir toute la table jusqu'à trouver le segment d'unités libre recherché.

Liste chainée

Une autre méthode correspond à conserver une liste chainée des partitions mémoire. Cette liste est généralement triée suivant les adresses des partitions libres, ainsi les partitions qui se suivent dans la mémoire se suivront dans la liste.

Chaque élément de la liste chainée n'a alors qu'à stocker quatre informations : si le bloc est libre ou pas, la position du début de la partition, la longueur de la partition et le lien avec la partition suivante. Par exemple P86 signifie qu'il y a un processus sur la partition en position huit d'une longueur de six unités.

Ce qui implique également de facilité la fusion de blocs libre, si un programme libère une partition, cette partition pourra être facilement fusionnée avec les éventuelles partitions libres adjacentes pour former une partition plus grande.

L'avantage est de rendre l'allocation beaucoup plus rapide, le désavantage est que cela crée de la fragmentation.

Pour en savoir plus, vous pouvez regarder sur ce site.

Choix de la partition

Lorsque l'on recherche la partition de mémoire qui pourra accueillir un programme, il y a plusieurs algorithmes possibles.

Fragmentations

Solutions à la fragmentation

Pour rassembler les zones mémoires et résoudre ce problème de fragmentation, on peut utiliser le compactage. Cela consiste à rassembler les zones mémoires occupées et les zones libres ensembles de façon à créer de grands espaces libres.

Cela est cependant uniquement possible dans le cas de la translation à l'exécution et c'est un mécanisme assez couteux en ressource.

Une autre solution est d'utiliser de la pagination que nous allons voir en détail dans la section suivante.

Swapping

Pour pouvoir s'exécuter un processus doit se trouver entièrement en mémoire, alors lorsqu'il y a beaucoup de processus en mémoire et peu de mémoire disponible, on peut mettre un processus qui ne s'exécute pas (état ready) sur le disque dur pour libérer de la mémoire (via une partition sur le disque dur ou via un fichier "swap file").

Un processus peut être swappé lorsque son quantum de temps a expiré (retour de running à ready), si le quantum est petit il y aura beaucoup de changement de processus et donc beaucoup d'accès au disque en revanche si le quantum est grand, il y aura moins de changements de processus et moins d'accès au disque.

Les performances de ce mécanisme sont de ce fait déterminées par le temps de transfert mémoire ⇆ disque.

On ne peut swap que les processus auquel on n'a pas besoin d'accéder à la mémoire, c'est-à-dire les processus en état ready car pour les processus en état waiting, le système d'exploitation doit pouvoir accéder à la mémoire du processus pour y faire les entrées-sorties.

La pagination

La pagination permet d'avoir un espace adressage en mémoire physique non contigu. Elle nécessite toute fois une modification du MMU pour intégrer la table des pages. Elle va avoir une "table des pages" pour savoir où sont les morceaux. Cette méthode est utilisée par tous les systèmes d'exploitations actuels.

Fonctionnement

On va donc diviser la mémoire logique en blocs de taille fixe (les pages), on va faire de même avec la mémoire physique (que l'on va appeler les frames). Ainsi une page correspond à une frame. De ce fait, la table des pages va lier chaque page à une frame. L'espace de stockage pour le swapping est également découpé en blocs de même taille que les frames.

Lorsqu'un processus démarre, on va donc calculer la taille nécessaire en nombre de pages, ensuite, on va regarder le nombre de frames disponibles. S'il y a suffisamment de frames disponibles le processus peut alors démarrer, sinon le processus ne peut pas démarrer. Par exemple, si on a un processus nécessitant 10 octets et que chaque page fait quatre octets, cela nécessitera 3 pages. Sauf que s'il n'y a que 2 frames disponibles le processus ne pourra pas démarrer.

Les frames sont gérées par le système d'exploitation, ce dernier va garder la liste des frames libres et occupées et le nombre de frames disponibles. Le SE doit aussi mettre en place une protection pour empêcher un processus de dépasser son espace d'adressage.

Effet sur la fragmentation

Ainsi, la fragmentation externe n'existe plus, car bien que l'adressage soit vu comme contigu au niveau du programme, elle ne l'est pas au niveau physique.

La fragmentation interne, elle sera d'en moyenne 1/2 page par processus, comme on ne peut pas assigner des demi-frames, donc si un processus nécessite 10 octets, mais qu'une frame fait 4 octets et que chaque page correspond à une frame (en conséquence chaque page fait 4 octets également), on devra alors assigner 3 pages pour le processus de 10 octets, ce qui laisse ensuite deux octets (soit une demi-page) non utilisée.

La segmentation

Un·e utilisateur·ice voit un programme comme un ensemble d'instructions, de données, de fonctions, etc. Bref, un ensemble de blocs distinct dont les données ne sont pas mélangées avec les autres.

Il convient donc de traduire cette vue à l'intérieur du système d'exploitation. Pour cela, on va diviser l'espace d'adressage du processus en segments. Chaque segment a un nom, un numéro et une taille.

Les différents segments

Ainsi dans une architecture Intel x86, on peut avoir :

De manière plus descriptive, on peut définir la mémoire du point de vue d'un programme comme ceci. À noter cependant que, cela est surtout comme ça que fonctionnaient les anciens systèmes, mais comme on va le voir dans la suite ce n'est plus exactement comme ça que cela fonctionne.

Avec la segmentation comme ceci, une adresse logique devient ainsi <segment-number, offset>.

Avantages

En utilisant la segmentation, le système offre ainsi une protection adaptée car chaque segment contient des données d'une même nature et ne peuvent donc pas intervenir dans d'autres données. On ne peut pas par exemple accéder aux instructions du programme depuis le data segment.

Également, les segments peuvent être partagés entre plusieurs processus (par exemple avec les libraires systèmes) et ainsi faire une économie d'espace.

Désavantages

Cela fait un retour à la fragmentation, étant donné que les segments sont de taille variables, on retrouve de la segmentation externe. C'est pour cela qu'il faut combiner la segmentation avec la pagination.

Segmentation et pagination

Pour combiner les avantages de la segmentation avec les avantages de la pagination, on va regarder à l'exemple du fonctionnement de l'architecture des processeurs Intel 32 bits.

Ce processeur peut gérer un maximum de 16 384 segments de maximum 4 Go. L'espace d'adressage est découpé en deux parts égales. Une partition pour les segments privés (par exemple, processus) et une autre pour les segments partagés (par exemple, librairie partagée).

Il y a également deux tables, la LDT (Logical Descriptor Table) pour la partition des segments privés, et la GDT (Global Descriptor Table) pour les segments partagés.

Conversion vers adresse physique

Pour passer de l'adresse logique à l'adresse physique, il va falloir passer par deux intermédiaires :

Unité de segmentation

L'adresse logique est composée d'un sélecteur et d'un déplacement. Le sélecteur est lui-même composé de 3 informations :

À partir de cette adresse logique, l'unité de segmentation construit l'adresse linéaire.

Unité de pagination

L'adresse linéaire est composée de 3 informations,

À partir de cette adresse linéaire, l'unité de pagination construit l'adresse physique comme vu précédemment dans le chapitre sur la Pagination.

Mémoire virtuelle

Il a été dit précédemment qu'il faut qu'un programme soit entièrement en mémoire pour pouvoir s'exécuter comme processus, alors comment faire lorsque le programme est plus gros que la taille de mémoire vive ?

Ce qui est utilisé par les systèmes aujourd'hui c'est la mémoire virtuelle, il s'agit d'utiliser le disque dur comme mémoire supplémentaire à la RAM.

Cela est bien sûr plus lent, surtout si le stockage est un disque dur (et pas un SSD), mais il permet de faire tourner de très gros programmes (ou juste énormément de processus) avec peu de RAM.

Utilisation de la pagination

Cela tombe bien, car la pagination est justement très adaptée à cela, car il suffit de lier de l'espace sur le disque à la table des pages (memory map sur le schéma). Ainsi la mémoire virtuelle sur le disque va être divisée en pages.

La table des pages doit bien sûr être adaptée pour pouvoir disposer d'un bit indiquant si la page se trouve sur le disque ou sur la mémoire physique.

Et le stockage/disque doit avoir une partie prévue pour contenir la mémoire virtuelle, celle-ci est appelée "swap device". Il s'agit d'un fichier sous Windows (Pagefile.sys), et d'un fichier ("swapfile") ou d'une partition ("swap partition") sous Linux.

Fonctionnement

Avec la mémoire virtuelle, les pages du processus à exécuter se trouvent sur le disque dur. Lors du chargement du programme, seules les pages nécessaires sont placées en mémoire physique.

Le changement entre mémoire virtuelle et mémoire physique est effectué lorsqu'une page non chargée est demandée. Lors du chargement, le système alloue quelques pages et les charge depuis le disque.

Ainsi lorsqu'une page est demandée, on regarde dans la table des pages pour voir si elle est présente en mémoire (bit valide), si oui tout va bien et tout se passe comme d'habitude. En revanche si ce n'est pas le cas (bit invalide) alors, il s'agit d'un défaut de page.

Traitement d'un défaut de page

Quand un défaut de page survient, il faut le résoudre le plus vite possible pour ne pas impacter les performances du système :

  1. On vérifie si la page demandée est présente dans l'adressage du programme, si ce n'est pas le cas alors c'est un memory overflow ce qui provoque un arrêt du processus.
  2. Si la page existe, ainsi on trouve une frame libre en mémoire physique et récupère la page depuis le disque
  3. On ajuste la table des pages pour indiquer la page comme valide et indiquer sa position dans la mémoire physique
  4. On redémarre le processus à l'instruction qui a causé l'erreur

Les défauts de pages faisant des appels d'entrée-sortie au disque, il est important d'en avoir le moins possible afin de ne pas trop impacter les performances du système.

Que faire quand il n'y a plus de frames ?

Lorsqu'un défaut de page survient, mais qu'il n'y a plus de frame disponible sur la mémoire physique, il faut alors que le système en libère une.

Pour cela, il faut que le système choisisse quelle frame remplacer, l'écrivent sur le disque et mettent à jour la table afin de libérer une frame pour résoudre le défaut de page.

Algorithmes de choix des pages victimes

Il est important d'utiliser un bon algorithme pour choisir les pages qui seront mises en mémoire virtuelle, car sinon cela risque d'augmenter le nombre de défauts de page et donc de considérablement ralentir le système.

Voici une comparaison de plusieurs algorithmes :

Amélioration des performances

Écriture retardée des pages

Pour améliorer les performances en cas de défaut de page, on peut garder un ensemble de page (appelée pool) qui sont toujours immédiatement disponibles. Ainsi, lorsqu'une page victime nécessite d'être sauvegardée (bit de modification à 1 dans l'algorithme de la seconde chance), il suffit de donner une page du pool au processus qui est donc utilisable directement. Ensuite, on sauvegarde la page victime dans la mémoire virtuelle et cette page intègre ensuite le pool.

Allocation des frames

Il faut avoir une allocation raisonnable de la mémoire physique (frames), si trop de frames sont alloués au processus, on risque de tomber vite à court de frame et ainsi faire beaucoup de défauts de pages. Si trop peu de mémoire frames sont allouées, alors on tombe vite dans des défauts de page.

Alors il faut trouver un moyen d'allouer les frames de manière à satisfaire le plus possible tous les processus.

Trashing

L'allocation des frames est ainsi un problème compliqué, si on n'alloue pas assez de frame à un processus, le processus va passer beaucoup de temps à transférer des informations. Le trashing c'est lorsqu'un processus n'a pas suffisamment de frames allouées pour s'exécuter correctement et passe ainsi plus de temps à récupérer des pages qu'à s'exécuter.

La cause de ce problème est que, comme on a vu avec les processus, pour utiliser au mieux le CPU lorsque ce dernier est peu utilisé, le système va augmenter le degré de multi-programmation, ce qui va diminuer le nombre de frames disponibles et donc augmenter le nombre de défauts de pages. Sauf que pour résoudre le défaut de page les processus concernés devront être mis dans l'état waiting en attente de l'entrée-sortie, ce qui va ainsi de nouveau réduire l'utilisation du CPU. Ainsi le cycle vicieux se répète.

Modèle de la localité

Une manière de résoudre ce problème est d'utiliser le modèle de la localité.

Une localité, c'est un ensemble de pages qui sont activement utilisées ensemble. Un programme est ainsi composé de plusieurs localités différentes qui peuvent se chevaucher. Lorsqu'un processus s'exécute, ce dernier va de localité en localité.

Par exemple, lorsqu'une fonction est appelée, cela définit une nouvelle localité et quand l'on quitte cette fonction, on entre dans une autre localité.

Ainsi si on arrive à identifier la localité en cours, on peut alors charger suffisamment de frames pour les accommoder, cela va créer des défauts de pages jusqu'à ce que toutes les pages de la localité jusqu'à ce qu'elle soit toutes en mémoire, ensuite elles ne feront plus aucun défaut de page jusqu'à ce qu'on change de localité.

Si on n'alloue pas suffisamment de frames par rapport à la localité courante le système va faire du trashing.