next up previous index
Next: Fichiers Up: Systèmes d'exploitation (Module Maîtrise Previous: Gestion des Processus.   Index

Subsections


Gestion de la mémoire

Le problème

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.

Allocation contiguë

Les processus constituent un seul bloc non décomposable.

Partitions de taille fixe

SE P1 P6 vide P4 vide

Les défauts :

MS-DOS utilise les partitions de taille fixe. (64Ko).

Partitions de taille variable

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.

1.
Libération d'une zone occupée : fusionner les zones libres contiguës (4 cas).

2.
Allocation d'une zone libre : on scinde une zone libre en une zone allouée de la taille estimée et un reste qui est remis dans la liste chainée des zones libres.

Il n'existe pas d'algorithme optimal d'allocation, mais seulement des heuristiques :

First Fit
liste des trous par adresse. Le premier suffisamment grand est choisi.
Best Fit
liste des trous par taille croissante. Le premier suffisamment grand est choisi.
Worst Fit
liste des trous par taille décroissante. Le premier suffisamment grand est choisi.

Pour un fonctionnement correct, il faut en moyenne, que le nombre de zones libres soit la moitié du nombre de zones allouées.

Fragmentation

Interne
$\sigma{}{}(tailles processus) / \sigma{}{}(tailles allouees)$
externe
$\sigma{}{}(tailles trous) / (taille memoire)$

Va-et-vient

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.

Les problèmes

Taille d'un processus

Si un processus devient plus grand que la zone allouée, il faut soit lui trouver un nouvel emplacement, soit le tuer.

La protection

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'adresse

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 :

compilation
code absolu, non relogable.
chargement
code translatable, non relogable.
exécution
code relogable. Cela demande du matériel spécial.

La pagination : une allocation non contiguë

L'allocation contiguë est très contraignante. Une solution consiste à découper en morceaux le processus.

Mémoire virtuelle

La mémoire virtuelle est une technique autorisant l'exécution de processus pouvant ne pas être completement en mémoire.

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.

Défauts de pages

Traités par logiciel (système d'exploitation). Il faut ensuite relancer l'instruction.

Tables à plusieurs niveaux

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.

Mémoire associative

Cache; hits et miss. Machine MIPS : les échecs de recherche dans le cache sont traités par le logiciel.

Changement de contexte

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''.

Tables inverses

Pour adressage 64 bits. Une fonction de hachage permet de retrouver le numéro de page virtuel. Table des pages manquantes sur disque.


Algorithmes de pagination

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.

Algorithme optimal

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

Propriétés

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.

LRU

Est une bonne approximation de l'algorithme optimal si le principe de localité est respecté.

FIFO, horloge

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.

Compteur de références

Pour assurer le vieillisement, faire un décalage à droite, et placer R dans le bit de poids fort du compteur.

Algorithmes globaux/locaux

On peut traiter globalement toutes les pages de la mémoire, ou traiter à part les pages attribuées à un processus.

Pré-chargement

S'oppose à la pagination à la demande.

Démon

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.

La segmentation : une autre allocation non contiguë

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).


next up previous index
Next: Fichiers Up: Systèmes d'exploitation (Module Maîtrise Previous: Gestion des Processus.   Index
Alain GRIFFAULT
2000-01-04