Croisière au coeur d'un OS Etape 3 : Gestion de la mémoire physique

Gestion des listes

Implantation

Notre implantation de la gestion de la mémoire physique utilise un jeu de macros facilitant la manipulation de listes chainées. Nous commencerons par rappeler le principe de ces listes, puis nous décrirons rapidement le jeu de macros et enfin nous détaillerons notre implantation de la gestion de la mémoire physique proprement dite.

  1. Rappels sur les listes chainées
  2. Utilisation des macros
  3. Exemple
  4. Rôle des macros disponibles

1. Rappels sur les listes chainées

Le système de manipulation de listes chainées que nous utilisons gère des listes doublement chainées circulaires. Une liste (simplement) chainée est une suite d'éléments dans laquelle chaque élément connait l'élément qui le suit. Un peu comme une série de wagons pour lesquels l'attache d'un wagon est fixée au suivant : il faut être dans un wagon pour accéder au wagon suivant. Sauf que dans ces listes, seul l'élément suivant est connu et non le précédent (ie une liste simplement chainée ne peut être parcourue que dans un sens). Insérer un nouvel élément C entre 2 éléments A et B revient à connaitre A, et à remplacer le lien A ! B par deux liens A ! C et C ! B. Supprimer de la liste cet élément C, situé entre A et B, revient à retrouver à nouveau A et à faire l'opération inverse de la précédente (figure 2(a)). Tout le problème avec ces listes est que toute opération d'insertion/suppression d'éléments à un endroit précis nécessite de connaitre l'élément qui précéde l'endroit où on veut effectuer l'opération. Or, pour retrouver cet élément qui précéde, on est obligé de parcourir la liste depuis le début puisqu'elle ne peut être parcourue que dans un seul sens. Ceci peut prendre un temps proportionnel à la longueur de la liste, qui peut être très longue. Une liste doublement chainée est une suite d'éléments dans laquelle chaque élément connait à la fois l'élément qui le suit dans la liste, mais aussi a l'élément qui le précéde. Ainsi, la liste peut cette fois être parcourue dans les deux sens. Ajouter ou supprimer un élément (figure 2(b)) impliquera donc de modifier l'accès au suivant de l'élément précédent et l'accès au précédent de l'élément suivant, pour les deux éléments entourant l'élément à ajouter ou à supprimer. L'intéret de ces listes est que ceci se fait en un temps indépendant du nombre d'éléments dans la liste, au prix d'un doublement de l'espace occupé pour stocker les liens entre les éléments (2 liens au lieu d'un).

2. Utilisation des macros

Afin de faciliter la manipulation des listes doublement chainées circulaires, nous les avons implantées sous forme de macros (fichier sos/list.h). Cette implantation permet d'avoir une gestion générique pour tous les types de données, tout en s'affranchissant des transtypages (castings) inutiles et en conservant les vérifications du typage par le compilateur. Son utilisation ne sera pas limitée à la gestion de la mémoire physique.

Par défaut, ces macros de manipulation de listes supposent que les structures passées en paramètre possèdent les champs prev et next pour chainer les éléments. Il est aussi possible de donner un autre nom à ces champs : chaque macro possède un équivalent se terminant par named qui permet de spécifier des noms de champs précédent et suivant différents de ces prev/next.

3. Exemple

Avant de détailler les macros, illustrons leur utilisation au travers d'un exemple.

La première étape consiste à définir le type des éléments à chainer (struct integer), ainsi qu'un pointeur vers le premier élément de la liste (list) :

struct integer {
int val;
struct integer *prev, *next;
};
struct integer *list;

Avant de commencer à utiliser la liste, il convient de l'initialiser en indiquant par exemple qu'elle est vide :

list_init(list);

On peut ensuite insérer un élément pointé par element en tête ou en queue. Dans les deux cas, l'insertion se fera en temps constant, car la liste est circulaire et doublement chainée :

list_add_head(list, element); /* En tête */
list_add_tail(list, element); /* En queue */

Supprimer cet élement est tout aussi simple et s'effectue également en temps constant puisque la liste est doublement chainée :

list_delete(list, element);

En supposant que les champs de chainage précédent et suivant étaient nommées prev in stuff et next in stuff, le code précédent aurait dû être :

list_init(list, prev_in_stuff, next_in_stuff);
list_add_head(list, element, prev_in_stuff, next_in_stuff);
list_delete(list, element, prev_in_stuff, next_in_stuff);

Des macros existent également pour parcourir une liste :

struct integer *list;
struct integer *current;
int nb_elts;
list_foreach(list, current, nb_elts)
{
/* Faire quelque chose avec ’current’ */
}

Dans l'extrait précédent, les variables current et nb elts sont mises à jour à chaque itération.

4. Rôle des macros disponibles

Nous détaillons ci-dessous l'ensemble des macros disponibles pour la manipulation des listes chainées. Comme nous l'avons dit précédemment, chacune de ces macros comporte un ´equivalent dont le nom se détermine par named pour spécier les noms des champs de chainage.

list_init(list) Initialisation d'une liste à la liste vide
list_singleton(list,item) Initalisation d'une liste à l'élément unique item
list_is_empty(list) Indique si la liste est vide ou non
list_get_head(list) Indique l'élément en tête de liste
list_get_tail(list) Indique l'élément en queue de la liste
list_insert_after(list,after this,item) Insère l'élément item après l'élément after this dans la liste list
list_insert_before(list,before this,item) Insère l'élément item avant l'élément before this dans la liste list
list_add_head(list,item) Insère un élément en tête de la liste
list_add_tail(list,item) Insère un élément en queue de la liste
list_delete(list,item) Retire un élément de la liste (ne vérifie pas si l'élément était réellement dans la liste)
list_pop_head(list) Récupère l'élément en tête de la liste et le retire de la liste
list_foreach_forward(list,iterator,nb elements) Permet de boucler sur tous les éléments d'une liste, à partir de l'élément de tête jusqu'à l'élément de queue
list_foreach_backward(list,iterator,nb elements) Comme la précédente, sauf que le parcours se fait de l'élément de queue vers l'élément de tête
list_collapse(list,iterator) Boucle analogue à list foreach forward(), sauf qu'à l'issue de chaque itération l'élément courant est retiré de la liste

A noter que quand nous disons retire, cela signifie que la liste ne contient plus de référence à l'élément retiré de la liste. Mais l'élément retiré de la liste reste toujours présent en mémoire.

Valid XHTML 1.0!