Une technique ancienne : l'allocation contiguë

Les processus constituent un seul bloc non décomposable.

Partitions de taille fixe

SE

P1

P6

vide

P4

vide

Les propriétés :

taille du processus :

il est nécessaire de faire du recouvrement lorsque la taille du processus est supérieure à celle de la partition.

fragmentation interne :

fonction monotone de la taille de la partition.

fragmentation externe :

nulle.

liaison d'adresse :

le code doit être translatable.

Partitions de taille variable

SE

P1

P6

vide

P4

vide

Les propriétés :

taille du processus :

il est nécessaire d'estimer la taille d'un processus (code, données, tas, pile). Le dépassement est difficile à gérer.

fragmentation interne :

fonction monotone de l'estimation de la taille d'un processus

fragmentation externe :

est généralement fonction antimonotone de la taille des zones inoccupées. Cependant elle peut être réduite à zéro en effectuant régulièrement un compactage de la mémoire. Cette solution demande du code relogable et est de plus coûteuse en temps CPU.

liaison d'adresse :

le code doit être translatable.

Il faut de plus gérer la liste des zones libres. La solution retenue est généralement une liste chaînée, réalisée en utilisant le début des zones libres, et la taille; manipulée par deux algorithmes.

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 chaînée des zones libres.

Il n'existe pas d'algorithme optimal d'allocation (vis à vis de la fragmentation externe), 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.