Allocation de mémoire physique
Le principe de mémoire virtuelle paginée étudié dans le cours précédent implique des mouvements de données entre le disque dur et la mémoire centrale. Le système d'exploitation s'appuie sur un allocateur de mémoire physique lui permettant :
- de déterminer les plages d'adresses physiques qui sont disponibles ;
- de déterminer les plages d'adresses physiques qui sont occupées, et par qui, par exemple par un processus utilisateur ou le système d'exploitation lui-même ;
- d'attribuer une plage d'adresses à un processus (allocation) ;
- de marquer une plage d'adresses comme étant à nouveau disponible (libération).
La suite de cours détaille deux façons parmi les plus répandues de gérer les zones libres de la mémoire physique.
Chainage de zones libres
Ici, une plage d'adresses est représentée par une structure de données, un descripteur de plage, contenant :
- l'adresse physique du début de la plage ;
- la longueur de la plage, en octets ;
- l'adresse du descripteur de plage suivant.
Le système d'exploitation utilise cette structure pour représenter les plages d'adresses qui sont disponibles, appelées zones libres (ZL).

La mémoire physique représentée sur ce schéma comporte trois zones libres : A, B et C. Les plages grisées sont actuellement utilisées. Le chainage de descripteurs de zones libres se termine par l'adresse NULL : le dernier descripteur n'a pas de suivant.
Où stocker les descripteurs de zones libres ?
On est en train de définir des structures de données, qu'il va donc falloir stocker en mémoire, pour représenter de la mémoire. Lorsque leur taille le permet, on préfèrera stocker ces descripteurs de zones libres dans les zones libres elles-même. En revanche, lorsqu'on souhaite représenter une zone libre dont la taille est inférieure à la taille d'un descripteur, on doit procéder autrement, comme par exemple réserver une plage d'adresses physiques à l'allocateur lui-même pour stocker ces descripteurs. En procédant ainsi, on rogne un peu sur la mémoire physique allouable à un utilisateur, mais on autorise l'allocation de plages d'adresses aussi petites qu'on veut.
Allocation
Avec cette structure de données, allouer N octets revient à parcourir le chainage pour trouver une zone libre qui convient. La zone libre désignée dépend de l'algorithme d'allocation utilisé. Il en existe plusieurs, parmi lesquels :
-
first-fit : on choisit la première zone libre qui vérifie
taille(ZL) >= N. Sitaille(ZL) > N, on découpe la ZL et on crée une nouvelle ZL de tailletaille(ZL) - N; -
best-fit : on choisit la ZL dont la taille est la plus proche de
N, avec de préférencetaille(ZL) == N; -
worst-fit : on découpe toujours la ZL la plus grande.
Ces politiques d'allocation ont été introduites pour lutter contre le problème de fragmentation de la mémoire.

Le schéma ci-dessus illustre ce problème : ici, on a 2 octets de libre en mémoire représentés par les ZL A et B, mais l'allocation d'un bloc de taille 2 octets échoue parce qu'il n'existe pas de zone mémoire contiguë suffisamment grande pour répondre à cette requête.
On définit deux types de fragmentation mémoire :
- la fragmentation externe, telle que présentée sur le schéma, où à un instant t, la mémoire disponible est fragmentée en plusieurs zones libres représentant des plages d'adresses disjointes au lieu d'une seule plage d'adresses contiguës ;
- la fragmentation interne, qui elle représente le fait que la mémoire réservée par l'allocateur n'est pas pleinement utilisée par l'utilisateur. Il existe par exemple des allocateurs qui ne permettent pas d'allouer n'importe quelle taille : un allocateur de pages permet d'allouer des zones mémoire dont la taille est un multiple de 4096 par exemple. On se retrouve parfois à n'utiliser qu'une sous-partie de la mémoire servie par l'allocateur.
Libération
La libération consiste à créer une nouvelle zone libre, à l'ajouter au chainage en fusionnant éventuellement les zones libres représentant des plages d'adresses adjacentes.
Remarque
Le choix de la structure de données lors de l'implémentation de cette technique dans le système d'exploitation a un impact sur les performances des politiques d'allocation. Par exemple, l'utilisation d'un chainage double accélère la fusion de zones libres lors de la libération ; l'utilisation de listes triées par taille améliore les performance de la politique worst-fit, puisqu'il suffit d'enlever la tête de liste pour récupérer la zone libre la plus grande.
L'algorithme du compagnon (buddy system)
Le second allocateur présenté dans ce cours suit le principe de diviser pour régner. L'algorithme sur lequel il s'appuie a été introduit pour :
- lutter contre la fragmentation externe ;
- accélérer la fusion des zones libres, à la libération.
Principe
Initialement, la mémoire ne contient qu'une zone libre de taille \(2^{max}\).
L'allocation d'un bloc de taille \(n\) va provoquer les divisions successives d'une zone libre de taille supérieure, jusqu'à générer une zone libre de taille \(2^k\) avec \(2^{k-1} < n \leq 2^k\).
A chaque fois qu'on a besoin de diviser une zone libre de taille \(2^i\), on la coupe en deux créant deux zones libres de taille \(2^{i-1}\) considérées comme compagnons (ou buddies).
Lors de la libération d'un bloc de taille \(2^i\), on regarde si son compagnon est libre, auquel cas on fusionne la zone libérée et son compagnon pour créer une nouvelle zone libre de taille \(2^{i+1}\). L'opération de fusion est répétée jusqu'à le compagnon du bloc considéré ne soit plus libre.
Les zones libres de même taille sont chainées entre elles, comme dans l'allocateur présenté en début de cours.
Le descripteur de la première zone libre de chaque taille, de \(2^0\) à \(2^{max}\), est stocké dans une table : la TZL.
Illustration sur un exemple
Considérons pour l'exemple une mémoire physique de 64 "unités" (par exemple des octets, des pages, ...). L'allocateur buddy que nous utiliserons ici dispose d'une API simple :
p = allouer(N)permettant de réserver une plage mémoire contiguë deNunités d'adressep;liberer(p)permettant de marquer la plage mémoire d'adressepcomme étant à nouveau disponible.
On illustre le comportement de l'allocateur buddy en dessinant la TZL et la mémoire physique à chaque étape, en décomposant l'exemple de code utilisateur suivant :
p1 = allouer(16);
p2 = allouer(8);
liberer(p1);
liberer(p2);
Mémoire allouée
On commence doucement avec l'allocation d'une zone mémoire de longueur 16 :
p1 = allouer(16);
Initialement, la mémoire est vide. TZL[6] contient l'adresse de la première zone libre de taille \(2^6 = 64\).

On a \(16 = 2^4 < 2^6\), on doit donc diviser le bloc de taille 64.

Il n'existe plus à ce stade de zone libre de taille \(2^6\) (TZL[6] == NULL), mais on a créé un chainage de deux zones libre de taille 32 accessible depuis TZL[5]. On répète l'opération pour créer deux zones libres de taille 16.

Cette fois-ci, on a bien atteint notre condition d'arrêt : \(2^{k-1} < n \leq 2^k\), avec \(n = 16\) et \(k = 4\). On arrête le découpage et on retourne l'adresse de l'une des deux zones libres de taille 16 à l'utilisateur.

On cherche maintenant à allouer une zone de longueur 8 avec p2 = allouer(8). On cherche la zone libre la plus petite telle que \(taille(ZL) \geq 8\). Dans notre exemple, c'est une zone libre de longueur 16, on doit donc la découper, puisqu'on n'a pas encore atteint la condition d'arrêt (on n'a pas \(2^{3} < 8 \leq 2^4\)).

Ici, la condition d'arrêt est atteinte et on retourne l'adresse d'une des zones mémoire de longueur 8 à l'utilisateur.

Mémoire libérée, délivrée
La libération de p1 va engendrer la création d'une zone libre de longueur 16. Le buddy de cette zone n'étant pas libre, l'algorithme de libération s'arrête.

La libération de p2 va engendrer la création d'une zone libre de longueur 8.

Cette fois, le buddy de cette zone est libre, on procède donc à la fusion de cette zone libre et son buddy, ce qui a pour effet de créer une zone libre de longueur 16 !

Le buddy de la zone libre de longueur 16 nouvellement créée est libre, lui aussi. On les fusionne à nouveau en une zone libre de longueur 32.

Le buddy de la zone libre de longueur 32 nouvellement créée est libre, lui aussi. On les fusionne à nouveau en une zone libre de longueur 64, et on retombe sur la situation initiale où notre mémoire était complètement libre.

Remarques
-
Retrouver son buddy est très rapide ! Il suffit d'appliquer un ou exclusif sur l'adresse d'une zone libre et sur la longueur de la zone pour retrouver l'adresse du buddy. Ex: Soit une ZL d'adresse 16 et de taille 8. Son buddy se trouve à l'adresse
16 xor 8 = 24. La réciproque est vraie !24 xor 8 = 16, on retrouve bien l'adresse de la ZL à partir de son buddy. -
L'allocateur buddy peut engendrer de la fragmentation interne. En effet,
allouer(9)réserve par exemple un bloc de taille 16.