La mémoire est assimilable à un tableau :
| SE | Processus utilisateurs |
Il faut gérer les emplacements utilisés par les processus utilisateurs, en essayant d'optimiser l'espace disponible.
Les processus constituent un seul bloc non décomposable.
| SE | P1 | P6 | vide | P4 | vide |
Les défauts :
MS-DOS utilise les partitions de taille fixe. (64Ko).
| SE | P1 | P6 | vide | P4 | vide |
Les défauts :
La solution retenue est généralement une liste chaînée de zones libres, réalisée en utilisant le début des zones libres, et la taille.
Il n'existe pas d'algorithme optimal d'allocation, mais seulement des heuristiques :
Pour un fonctionnement correct, il faut en moyenne, que le nombre de zones libres soit la moitié du nombre de zones allouées.
Cela correspond à l'ordonnancement à plusieurs niveaux.
La question cruciale est la suivante : un processus doit-il toujours être dans le même emplacement mémoire ?
La réponse est : oui si le code n'est pas relogable, non sinon.
Si un processus devient plus grand que la zone allouée, il faut soit lui trouver un nouvel emplacement, soit le tuer.
Il faut controler, avant exécution que toutes les adresses accedées par le processus sont à l'intérieur de la zone allouée. Cela protège les utilisateurs entre eux, mais aussi le SE.
La liaison d'instructions et de données (adresses logiques dans le programme, adresses physiques pendant l'exécution) peut avoir lieu à n'importe quelle étape :
L'allocation contiguë est très contraignante. Une solution consiste à découper en morceaux le processus.
La mémoire logique est plus grande que la mémoire physique.
Principe de la pagination, MMU. Table des pages : chaque entrée spécifie aussi si la page est présente, protégée, modifiée, ou utilisée.
Traités par logiciel (système d'exploitation). Il faut ensuite relancer l'instruction.
Permettent de réduire considérablement la taille de la table des pages. Découpage 10-10-12 (intel 80386) pour une table à deux niveaux, 8-6-6-12 sur Sparc.
Cache; hits et miss. Machine MIPS : les échecs de recherche dans le cache sont traités par le logiciel.
Chaque processus a ses propres tables de pages ; ou bien leur sauvegarde et leur rechargement font partie du changement de contexte (lourd), ou bien la MMU gère une table de contextes (Sparc). Penser aussi à invalider les entrées de la mémoire associative, si celle-ci ne contient pas de champ ``processus''.
Pour adressage 64 bits. Une fonction de hachage permet de retrouver le numéro de page virtuel. Table des pages manquantes sur disque.
Lors d'un défaut de page, si tous les cadres sont utilisés, il faut en libérer un afin de pouvoir y mettre la nouvelle page.
Le choix de la page à évincer est crucial.
Soit une mémoire comportant 5 cadres :
| Numéro de cadre | 1 | 2 | 3 | 4 | 5 |
| Numéro de page | 7 | 2 | 5 | 1 | 9 |
et une demande pour la page 3.
La solution optimale consiste à évincer la page dont l'occurence de la prochaine utilisation est la plus éloignée dans le futur.
Supposons que la suite de références aux pages soit 3, 9, 4, 3, 2, 1, 2, 7...
La page à évincer est la page 5 qui est la seule à ne pas apparaitre dans cette liste. La nouvelle configuration mémoire est donc :
| Numéro de cadre | 1 | 2 | 3 | 4 | 5 |
| Numéro de page | 7 | 2 | 3 | 1 | 9 |
L'algorithme précédent minimise le nombre de défauts de page. Il est malheureusement non implémentable (hormis dans certaines requêtes dans un SGBD), car il fait l'hypothèse de la connaissance du futur.
Est une bonne approximation de l'algorithme optimal si le principe de localité est respecté.
Horloge: une page avec R=1 est conservée, avec remise à zéro de R. Dit aussi algorithme de la seconde chance. Variante avec deux aiguilles, qui permet de paramétrer la notion d'accès récent.
Pour assurer le vieillisement, faire un décalage à droite, et placer R dans le bit de poids fort du compteur.
On peut traiter globalement toutes les pages de la mémoire, ou traiter à part les pages attribuées à un processus.
S'oppose à la pagination à la demande.
Chargé de libérer des cadres, à intervalles réguliers, si le nombre de cadres libres tombe au-dessous d'un seuil, jusqu'à ce qu'il devienne supérieur à un autre seuil.
Un segment est une unité logique, de grande taille, caractérisé par sa base et sa taille (variable). Possède ses propres modes de protection. Rend inutile les translations d'adresses pendant le chargement du code. La segmentation est bien adaptée à la projection de fichiers en mémoire (MULTICS).