Gestion de la Mémoire

La gestion de la mémoire est l’une des responsabilités les plus critiques d’un OS. Elle permet à plusieurs processus de coexister en mémoire de façon sûre et efficace, chacun croyant avoir accès à toute la mémoire disponible.

Mémoire physique vs mémoire virtuelle§

Mémoire physique : la RAM réelle, adressée directement par le matériel (bus d’adresses). Limitée par les barrettes installées.

Mémoire virtuelle : espace d’adressage abstrait présenté à chaque processus. Sur un système 64 bits, chaque processus voit un espace de 2⁶⁴ octets théoriques (en pratique 48 bits utilisés → 256 To). La MMU (Memory Management Unit) traduit les adresses virtuelles en adresses physiques.

Avantages de la mémoire virtuelle :

• Isolation entre processus (un processus ne peut pas lire la mémoire d’un autre)
• Chaque processus croit disposer de toute la mémoire
• Permet d’utiliser le disque comme extension de la RAM (swap)
• Facilite le partage de bibliothèques (libc partagée entre tous les processus)

Segmentation§

Division de l’espace d’adressage en segments logiques : code, données, pile, tas. Chaque segment a une base et une limite. Simple mais produit de la fragmentation externe.

Pagination§

La pagination est le mécanisme dominant sur les systèmes modernes. Elle divise la mémoire en blocs de taille fixe.

Page : bloc de mémoire virtuelle de taille fixe (4 Ko sur x86-64, jusqu’à 2 Mo ou 1 Go pour les huge pages).

Cadre de page (frame) : bloc correspondant de même taille en mémoire physique.

Table des pages : structure maintenue par l’OS pour chaque processus. Elle associe chaque numéro de page virtuelle au numéro de cadre physique correspondant.

Traduction d’adresse§

Adresse virtuelle : [ Numéro de page (VPN) | Offset dans la page ]
                           20 bits              12 bits (4 Ko = 2^12)

1. Extraire le VPN de l'adresse virtuelle
2. Chercher le VPN dans la table des pages → obtenir PFN (Physical Frame Number)
3. Adresse physique = PFN concaténé avec l'Offset

TLB — Translation Lookaside Buffer§

Chercher dans la table des pages à chaque accès mémoire serait trop lent. Le TLB est un cache matériel ultra-rapide (~1-4 ns) qui mémorise les traductions récentes.

TLB hit (~95-99% des cas) : la traduction est dans le TLB, accès en quelques cycles.

TLB miss : la traduction est absente du TLB. Il faut parcourir la table des pages en mémoire (page walk), puis stocker le résultat dans le TLB pour les prochains accès.

# Visualiser les statistiques du TLB (Linux avec perf)
perf stat -e dTLB-load-misses,dTLB-loads ./mon_programme

Pagination multiniveaux§

Sur x86-64, l’espace d’adressage de 48 bits utilise 4 niveaux de tables (PML4 → PDPT → PD → PT → Offset). Chaque niveau contient 512 entrées (9 bits). La table de premier niveau occupe seulement 4 Ko, et les tables de niveaux inférieurs ne sont allouées que si nécessaire — économie d’espace considérable.

Mémoire virtuelle et Swap§

Quand la RAM est saturée, l’OS peut déplacer des pages rarement utilisées vers le disque (zone de swap ou fichier de swap).

Swap out : copier une page de RAM vers le disque et libérer le cadre physique. Le bit “présent” dans la table des pages est mis à 0.

Page fault : un processus accède à une page non présente en RAM. Le CPU génère une interruption, l’OS charge la page depuis le swap, puis reprend l’exécution. Coût : plusieurs millisecondes (accès disque).

# Voir l'utilisation du swap
free -h
swapon --show
cat /proc/swaps

# Créer un fichier de swap
fallocate -l 4G /swapfile
chmod 600 /swapfile
mkswap /swapfile
swapon /swapfile

vm.swappiness : paramètre Linux (0-200) qui contrôle la tendance à utiliser le swap. 60 par défaut. Baisser à 10-20 pour les systèmes interactifs (préférer évincer les caches).

Algorithmes de remplacement de pages§

Quand tous les cadres sont occupés et qu’une nouvelle page doit être chargée, il faut en évincer une.

OPT — Optimal§

Évincer la page qui ne sera plus utilisée pendant le plus longtemps. Optimal mais impossible en pratique (nécessite de connaître le futur). Utilisé comme référence théorique.

FIFO — First In, First Out§

Évincer la page la plus anciennement chargée. Simple mais peu efficace (anomalie de Bélády : plus de cadres peut donner plus de page faults).

LRU — Least Recently Used§

Évincer la page la moins récemment utilisée. Bonne approximation de OPT. Difficile à implémenter exactement (nécessite un horodatage de chaque accès mémoire).

Algorithme de l’horloge (Clock)§

Approximation de LRU utilisée en pratique (Linux). Chaque page a un bit de référence. Quand une page est accédée, le bit est mis à 1. L’algorithme parcourt les pages circulairement : si le bit est 1, il le remet à 0 et continue ; si le bit est 0, la page est évincée.

LFU — Least Frequently Used§

Évincer la page la moins souvent accédée. Souffre du problème des pages “populaires mais obsolètes” (pages très accédées dans le passé mais plus utilisées).

Comparaison sur un exemple§

Pages accédées : 1 2 3 4 1 2 5 1 2 3 4 5
Cadres disponibles : 3

FIFO : 9 page faults
LRU  : 8 page faults
OPT  : 6 page faults

Thrashing§

Le thrashing survient quand l’OS passe plus de temps à échanger des pages (swap in/out) qu’à exécuter les processus.

Causes : trop de processus pour la RAM disponible, localité de référence médiocre.

Détection : utilisation CPU faible + activité disque (swap) très élevée.

Solutions : réduire le degré de multiprogrammation, ajouter de la RAM, utiliser l’algorithme du working set (garder en RAM le working set de chaque processus — ensemble des pages récemment accédées).

Allocation de mémoire en espace utilisateur§

malloc et free (C)§

// Allocation dynamique
int* tableau = malloc(100 * sizeof(int));
if (tableau == NULL) { /* gestion d'erreur */ }

// Utilisation
for (int i = 0; i < 100; i++) tableau[i] = i;

// Libération
free(tableau);
tableau = NULL;  // Bonne pratique : éviter le dangling pointer

Implémentation : malloc gère un heap interne, demande de la mémoire à l’OS via brk() ou mmap() par blocs, puis subdivise.

Stratégies d’allocation§

First-fit : allouer le premier bloc libre assez grand. Rapide mais fragmente le début du heap.

Best-fit : allouer le plus petit bloc libre assez grand. Réduit le gaspillage mais fragmente en de petits blocs inutilisables.

Worst-fit : allouer le plus grand bloc libre. Laisse de grands blocs libres mais peu efficace.

Buddy system : blocs de taille puissances de 2. Fusion facile de blocs adjacents (buddies). Utilisé dans le noyau Linux.

Fragmentation§

Fragmentation interne : la mémoire allouée est plus grande que nécessaire (ex : malloc(3) alloue 8 octets pour l’alignement).

Fragmentation externe : suffisamment de mémoire libre au total, mais pas de bloc contigu assez grand.

Garbage Collection (Python, Java, Go)§

Les langages modernes gèrent la mémoire automatiquement.

Comptage de références (Python) : chaque objet a un compteur du nombre de références qui pointent vers lui. Quand il tombe à 0, l’objet est libéré immédiatement. Problème : cycles de références (A→B→A) → détectés et nettoyés par le garbage collector cyclique.

Mark and Sweep (Java, Go) : le GC parcourt tous les objets accessibles depuis les racines (variables locales, globales), les marque, puis libère tous les non-marqués. Provoque des pauses GC.

Generational GC : la plupart des objets meurent jeunes (“infant mortality hypothesis”). On sépare la mémoire en générations (young, old). Le GC passe fréquemment sur la jeune génération (rapide) et rarement sur la vieille.

Commandes de diagnostic mémoire (Linux)§

free -h                       # Mémoire totale, utilisée, libre, swap
vmstat 1 5                    # Statistiques mémoire toutes les secondes
cat /proc/meminfo             # Informations détaillées sur la mémoire
cat /proc/PID/status          # Mémoire utilisée par un processus (VmRSS, VmPeak)
pmap -x PID                   # Carte mémoire détaillée d'un processus
valgrind --leak-check=full ./prog  # Détecter les fuites mémoire (C/C++)

# Surveiller les page faults
perf stat -e page-faults ./programme