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