next up previous contents
suivant: Définition d'une area monter: Mémoire physique précédent: Le gestionnaire de mémoire   Table des matières

Choix de l'algorithme

Pour le choix de notre algorithme de gestion de la mémoire physique, nous nous sommes basés sur les recherches théoriques menées en la matière par Andrew Tannenbaum dans son livre ``Operating System Version 2''. Les solutions présentées pouvant être utilisées dans Koinkoin étaient les suivantes:

La gestion par tableaux de bits utilise un tableau de n bits pour décrire l'état d'une mémoire de 32n bits, un bit à '1' marquant la mémoire comme occupée, '0' comme libre. Cette solution est la plus simple à implémenter, mais ``lorsqu'un processus de k unités est chargé en mémoire, le gestionnaire de mémoire doit parcourir le tableau de bits pour trouver une séquence de k bits consécutifs dont la valeur est 0. Or cette recherche est une opération lente (parce que cette zone peut enjamber des mots frontières dans la table), et cela constitue un argument contre les tables de bits''4.2. Nous n'avons donc pas opté pour cet algorithme.

La deuxième solution consiste en une liste chaînée unique décrivant l'intégralité de la mémoire. Chaque élément de la liste décrit une zone mémoire (adresse de début, nombre de pages), en la marquant comme libre ou non. Cette solution est plus performante et plus intéressante que la précédente, mais une allocation mémoire requiert de parcourir tous les éléments de la liste, qu'ils soient libres ou non, ce qui représentent des opérations inutiles.

La dernière solution permet une optimisation sur ce point. On utilise alors deux listes distinctes, l'une contenant les éléments décrivant les zones libres, l'autre les zones occupées, permet ainsi une accélération dans l'allocation. De plus les éléments de la liste libre sont triés par taille, du plus petit au plus grand. Ainsi le gestionnaire de mémoire parcourt la liste libre jusqu'à trouver une zone suffisament grande, qui sera par conséquence la plus petite possible, rendant la recherche optimale.

Nous avons donc opté fort logiquement pour la gestion à l'aide de deux listes chaînées distinctes, malgré sa forte complexité.


next up previous contents
suivant: Définition d'une area monter: Mémoire physique précédent: Le gestionnaire de mémoire   Table des matières
nicolas 2006-07-30