Gestion de la mémoire

Importance de la mémoire principale (RAM)

• La mémoire principale, ou RAM, est essentielle pour le stockage des données et des programmes.
• Elle doit impérativement être gérée avec prudence.
• Même si la capacité de la mémoire augmente avec le temps, la taille des programmes s'accroît aussi.
• Pour qu'un programme s'exécute, ses instructions et ses données doivent se trouver en mémoire centrale.
• En mode multiprogrammation, la mémoire centrale doit être utilisée et partagée entre les différents processus.
• La RAM est un "tableau de mots" (octets) avec sa propre adresse.
• C'est une mémoire volatile, ce qui signifie que son contenu est perdu lorsqu'elle n'est plus alimentée électriquement.
• Le CPU extrait les instructions en fonction de la valeur d'un compteur d'instructions.
• Le système de gestion de la mémoire gère la hiérarchie de stockage.
• Le système suit les parties de la mémoire utilisées ou inutilisées, alloue et libère l'espace mémoire aux processus, et contrôle les échanges entre la mémoire principale et le disque.

Gestion de la mémoire par un système monoprogrammation

• La méthode la plus simple consiste à exécuter un seul programme à la fois.
• La mémoire est divisée en deux : une partition pour le système (en mémoire basse) et une autre pour les processus utilisateur (en mémoire haute).
• Le programme accède directement aux cases mémoires en utilisant les adresses physiques.
• Il était initialement utilisé par MS-DOS.

Adressage de la mémoire principale

• L'unité de gestion de la mémoire (MMU) convertit les adresses virtuelles en adresses physiques.
• L'adresse physique est l'adresse réelle vue par l'unité de mémoire.
• L'adresse logique (adresse virtuelle) est l'adresse générée par le CPU.
• Le programme utilisateur traite les adresses logiques.

Gestion avec partition fixe pour un système multiprogrammation

• La plupart des systèmes modernes permettent l'exécution de processus multiples.
• Quand un processus est bloqué en attente d'une E/S, un autre processus utilise le processeur.
• La mémoire est divisée en n partitions de taille fixe où chaque partition contient exactement un processus.
• Le système maintient une table des parties de la mémoire disponibles et celles qui sont occupées.
• Un trou (hole) représente un bloc de mémoire disponible.
• L'usage de partitions fixes entraîne une perte d'espace inutilisé.
• Une fragmentation interne est possible, car la mémoire allouée peut être légèrement plus grande que nécessaire.

Swapping avec partition fixe pour un système multiprogrammation

• La mémoire principale peut être insuffisante pour maintenir tous les processus courants actifs.
• Le swap consiste alors à conserver les processus supplémentaires sur le disque.
• Le swap transfère temporairement un processus de la mémoire principale à une mémoire auxiliaire.
• Le processus est ensuite ramené en mémoire pour continuer son exécution.
• Le processus à transférer doit être inactif.
• La mémoire auxiliaire est un disque rapide assez grand pour ranger les copies des images mémoire de tous les utilisateurs.

Gestion avec partition variable pour un système multiprogrammation

• La quantité de mémoire allouée au processus est la quantité requise exactement.
• Le placement des petits processus dans les petites partitions réduit la fragmentation interne.
• La libération et l'allocation de mémoire sont plus compliquées.
• Un compactage est nécessaire, ce qui peut engendrer une consommation de temps et des pertes de temps CPU.
• Une fragmentation externe est possible, ce qui signifie qu'il existe un espace mémoire total suffisant pour satisfaire une requête, mais l'espace n'est pas contigu.

Algorithmes de placement

• Best-fit : choisir la partition la plus proche en taille de la demande, produisant la plus petite fragmentation, mais nécessitant souvent un compactage.
• First-fit : scruter la mémoire à partir du début et choisir la première partition libre pouvant contenir le processus, ce qui est rapide.
• Next-fit : similaire à First-fit mais commence à chercher l'espace libre à partir de l'endroit où la recherche s'était arrêtée précédemment.

Gestion de la mémoire : mémoire virtuelle et pagination

• Les programmes peuvent être plus grands que la mémoire physique.
• Le système d'exploitation conserve uniquement les parties nécessaires des programmes en mémoire et le reste sur le disque (swap).
• Il en résulte une séparation entre la mémoire logique du programme utilisateur et la mémoire physique.
• Une solution est la pagination à la demande.

Pagination

• La mémoire est divisée en morceaux de petite taille fixe appelés cadres de page (frames).
• Les processus sont découpés en morceaux de même taille, appelés pages.
• Le processus est chargé en mémoire.
• Toutes les pages du processus sont chargées dans des cadres de pages disponibles, mais pas nécessairement contigus.
• Une table des pages du processus est établie.
• Il peut y avoir un espace perdu en mémoire correspondant à la partie de la dernière page du processus (fragmentation interne).

Représentation des adresses

• Les adresses symboliques représentent les noms des objets dans le code source.
• Les adresses logiques (virtuelles) sont la traduction des adresses symboliques après la compilation.
• Les adresses physiques représentent l'emplacement physique des adresses logiques lors de l'exécution du programme.
• La traduction des adresses logiques en adresses physiques est effectuée par l'unité de traduction d'adresses (MMU).

Pagination et translation d'adresses

• L'association d'une page logique avec une page physique est décrite dans une table appelée table de pages.
• La translation des adresses logiques en physique est à la charge de la MMU.
• Chaque adresse logique générée par l'UC est divisée en un numéro de page(p) et un déplacement dans la page(d).
• Pour un espace d'adressage logique de 2^m octets et des pages de 2^n octets, les m-n premiers bits correspondent au numéro de page et le n bits restants correspondent au déplacement dans la page.

Pagination - Algorithmes de remplacement des pages

• Les programmes sont chargés partiellement en mémoire à la demande.
• Un défaut de page survient quand une page requise pour l'exécution n'est pas en mémoire.
• Recherche de page sur le disque dur, copie en mémoire, mise à jour de la table des pages, ou remplacement d'une page en déterminant quelle page sera remplacée.

Algorithmes de remplacement

• L'objectif est de minimiser le taux de défauts de pages.
• Un défaut de page entraîne une surcharge (choix de la page à remplacer, E/S des pages, commutation du processus).
• La probabilité de référencer une page absente pendant l'exécution d'un processus doit être minimisée.
• Les politiques implémentées incluent les politiques de chargement, de placement et de remplacement.

Politiques de chargement et de placement

• La politique de chargement détermine quand une page doit être chargée en mémoire principale.
• Chargement à la demande : une page est chargée seulement si une référence à un emplacement de celle-ci est faite.
• Chargement anticipatif : des pages autres que celles concernées par un défaut de page peuvent être chargées.
• La politique de placement détermine où, en mémoire principale, un processus doit résider.

Politique de remplacement

• Elle détermine quelle page en mémoire doit être sélectionnée pour être remplacée lorsqu'une nouvelle page doit être chargée.
• Elle décide du nombre de cadres de pages à allouer à chaque processus actif (allocation fixe ou variable).
• Elle définit l'ensemble des pages concernées par le remplacement (limité aux pages du processus ayant provoqué un défaut de page ou à l'ensemble des cadres de pages, soit remplacement local ou global).
• Elle détermine quelle page sera sélectionnée pour le remplacement parmi l'ensemble des pages concernées.

Algorithmes de remplacement spécifiques

• Optimal (OPT) : Sélectionne la page qui sera référencée le plus tardivement, minimisant les défauts de pages.
• First-In-First-Out (FIFO) : Considère les cadres de pages alloués comme un tampon circulaire simple, mais pas très efficace.
• Least Recently Used (LRU) : Remplace la page en mémoire la plus anciennement référencée/utilisée.
• Clock : Quand un défaut de page survient, la page pointée est testée. Si le bit R de la page vaut 0, la page est retirée. Si bit R=1, le bit R est mis à 0 et le pointeur est avancé.

Problème : écroulement (tashing)

• L'écroulement (tashing) est caractérisé par une activité de pagination élevée où un processus passe plus de temps à paginer qu'à exécuter.
• Il est lié à une diminution de l'utilisation du CPU.
• Pour le prévenir, il faut fournir à un processus autant de cadres qu'il en a besoin.
• La stratégie de l'ensemble de travail (Working Set) commence par la définition du modèle de localisation de l'exécution d'un processus.
• Un programme est constitué de localisations qui peuvent se chevaucher.

Ensemble de travail (Working Set)

• L'ensemble du travail est une fenêtre sur les accès aux pages.
• Le nombre de pages contenues dans la fenêtre varie.
• La fenêtre est mise à jour périodiquement.
• L'ensemble de travail est la totalité des pages référencées durant l'exécution du programme.
• Si la demande en mémoire dépasse la mémoire totale, le système d'exploitation arrête un processus.
• Les algorithmes de remplacement de page tiennent compte du working set pour limiter les défauts de page.

Segmentation

• Un processus est composé d'un ensemble d'unités logiques (codes, données, pile d'exécution).
• La pagination peut couper des portions de code ou de données, entraînant des chargements inutiles de données.
• La segmentation est une stratégie de gestion mémoire qui reproduit le découpage mémoire tel qu'il est logiquement décrit.
• Chaque segment possède un nom (numéro) et une longueur et est représenté par une adresse logique <numéro de segment, déplacement>.

Segmentation et translation d'adresses

• Une adresse logique est un couple (S, d) où S est numéro de segment et d le déplacement dans le segment.
• Une table segments décrit l'association d'une adresse logique à une physique.
• Chaque entrée dans la table possède un segment de base (adresse physique de début du segment) et une limite (sa longueur).

Fragmentation et segmentation

• Possibilité de fragmentation externe, nécessitant un compactage.

Segmentation vs. pagination

• Segmentation : le programmeur en est conscient, il existe plusieurs espaces d’adresses linéaires, l’espace d’adressage peut dépasser la mémoire physique, permet de distinguer les différents espaces, permet le partage des procédures entre les utilisateurs.
• La pagination permet d’avoir un grand espace d’adressage linéaire sans avoir à acheter beaucoup de mémoire.

Segmentation paginée

• Si la taille d'un segment est importante, le temps de chargement peut être long.
• Les programmes sont divisés en segments puis en pages.
• Chaque processus a une table de segments et une table de pages.
• Chaque adresse de segment n'est pas une adresse mémoire, mais une adresse au tableau de pages du segment.
• Une adresse logique (S, D) est transformée en un triplet (S, p, d).