TD 12 - GC Stop & Copy

L'objectif de ce TD est de programmer en OCaml un GC de type stop & copy, en suivant ce qui est décrit dans le cours. On écrira le code demandé dans un fichier stop_and_copy.ml.

La mémoire

On modélise la mémoire de manière très simple, comme un tableau d'entiers de taille ram :

  let ram = 100
  let memory = Array.make ram 0

Un bloc de taille n situé à l'adresse p est représenté de la manière suivante : memory.(p) contient n (la taille du bloc) et memory.(p+1), ..., memory.(p+n) contiennent les n champs. On note en particulier que n+1 éléments du tableau memory sont donc utilisés.

Les racines sont déclarées dans un tableau à part, roots :

  let max_roots = 10
  let roots = Array.make max_roots (-1)

Les valeurs contenues dans les champs et dans les racines sont interprétées de la manière suivante : tout entier compris entre 0 (au sens large) et ram au sens strict est considéré comme un pointeur ; tout autre entier est considéré comme autre chose.

Collection

Écrire une fonction

  val stop_and_copy : int -> int -> int

qui prend comme argument le début de la zone from_space et le début de la zone to_space et déplace les blocs vivants de from_space vers to_space. (On pourra supposer que les deux zones ont chacune la taille ram/2.) La valeur renvoyée est le premier emplacement libre dans to_space à l'issue de la copie.

Pour visualiser l'effet de la collection (en particulier dans les tests proposés plus loin), on pourra afficher un message du type

  mémoire occupée après collection = 15 mots

juste avant de renvoyer le résultat.

Allocation

Écrire une fonction d'allocation

  val alloc : int -> int

qui prend en argument une taille de bloc et renvoie l'emplacement du bloc alloué. Si le bloc ne peut être alloué directement, cette fonction doit appeler stop_and_copy pour libérer de la mémoire. Si le bloc ne peut toujours pas être alloué à l'issue de la collection, on lèvera l'exception Failure "out of memory".

Bien entendu, une ou deux références sont nécessaires pour contenir l'état du GC ; à vous de les choisir et de les déclarer. Pour les besoins des tests qui suivent, on écrira également une fonction

  val reset : unit -> unit

qui réinitialise le GC.

Tests

Avec une liste simplement chaînée

Afin de tester, on fournit dans tri.ml une fonction tri : int -> unit qui prend en argument un entier n, construit en mémoire une liste aléatoire de longueur n (contenant des entiers négatifs pour ne pas les confondre avec des pointeurs), l'affiche, la trie à l'aide d'un tri par insertion puis affiche le résultat. La fonction tri est appelée successivement avec n=3, n=10 et n=17 (chaque fois après un appel à reset).

Compiler avec

  ocamlopt stop_and_copy.ml tri.ml -o tri

et lancer le programme obtenu (avec ./tri). Alternativement, on pourra utiliser ce fichier dune ; lancer alors dune test.

On doit obtenir quelque chose comme

tri 3
  -624,-656,-15,
  -656,-624,-15,

tri 10
  -56,-961,-762,-299,-452,-2,-235,-356,-58,-954,
  mémoire occupée après collection = 6 mots
  mémoire occupée après collection = 21 mots
  mémoire occupée après collection = 24 mots
  -961,-954,-762,-452,-356,-299,-235,-58,-56,-2,

tri 17
  mémoire occupée après collection = 48 mots
  Fatal error: exception Failure("out of memory")

On pourra bien entendu augmenter la valeur de ram pour des tests plus poussés.

Avec des listes circulaires doublement chaînées

Tester de même avec le programme josephus.ml qui résout le problème de Josèphe en utilisant des listes circulaires doublement chaînées.

Compiler avec

  ocamlopt stop_and_copy.ml josephus.ml -o josephus

et lancer le programme obtenu (avec ./josephus). On doit obtenir quelque chose comme

josephus 7 5
  1 2 3 4 5 6 7
=> 6
josephus 5 5
  1 2 3 4 5
=> 2
josephus 5 17
  mémoire occupée après collection = 20 mots
  1 2 3 4 5
=> 4
josephus 5 2
  mémoire occupée après collection = 36 mots
  1 2 3 4 5
=> 3
josephus 6 2
  mémoire occupée après collection = 40 mots
  mémoire occupée après collection = 48 mots
  mémoire occupée après collection = 48 mots
  Fatal error: exception Failure("out of memory")

Devinette

Avec le programme de tri ci-dessus, on observe parfois le comportement étrange suivant : le GC récupère l'intégralité de la mémoire entre le moment où la liste est affichée la première fois et celui où elle est affichée triée la seconde fois. Cela se manifeste notamment pour ram=100 et n=16 :

tri 16
  -674,-68,-543,-616,-974,-733,-452,-796,-886,-938,-206,-979,-477,-434,-455,-791,
  mémoire occupée après collection = 0 mots
  mémoire occupée après collection = 18 mots
  mémoire occupée après collection = 12 mots
  mémoire occupée après collection = 30 mots
  mémoire occupée après collection = 27 mots
  mémoire occupée après collection = 24 mots
  mémoire occupée après collection = 6 mots
  mémoire occupée après collection = 27 mots
  -979,-974,-938,-886,-796,-791,-733,-674,-616,-543,-477,-455,-452,-434,-206,-68,

Comment explique-t-on ce phénomène et pourquoi la liste n'est-elle pas perdue ? (Il faut regarder le code tri.ml pour comprendre.)

solution

retour à la page du cours