Mis à jour le 21 mars 2006
TD 9

TD 9

Mardi 22 mars 2005

L'objectif de ce td est d'ajouter un tas, géré par un mécanisme simple de mémoire virtuelle, à la machine virtuelle que nous développée lors du td précédent.

Commencez par copier dans votre répertoire de travail les fichiers instr.ml, machine.ml, system.ml et main.ml qui correspondent, à de petites différences près, à la solution du td précédent et à des exemples de code permettant de tester les accès mémoire.

Afin de permettre la simulation de l'accès à une mémoire, deux instructions ont été ajoutées à la machine virtuelle. L'instruction Load (addr, r) qui copie la valeur présente à l'adresse mémoire addr dans le registre r et l'instruction Store (r, addr) qui copie la valeur contenue dans le registre r à l'adresse addr.

Un fichier memory.ml a été ajouté. Il contient le code relatif à la gestion de la mémoire. Pour l'instant, ce fichier ne contient qu'une gestion directe de la mémoire sans mécanisme de mémoire virtuelle. Les fonctions get et set de ce module sont appelées par les instructions Load et Store de la machine pour accéder à la mémoire. Dans cette version, Memory.get et Memory.set accèdent donc directement aux cases du tableau Memory.memory.

Le but du td est donc de remplacer cette implantation pour utiliser un mécanisme de mémoire virtuelle, i.e. de traduire au vol les adresses virtuelles en adresses réelles (physiques, dans Memory.memory) en utilisant une table de pages.

Le système stocke le numéro de la page (en mémoire) physique qui contient la table des pages de chaque processus dans son registre preg.(pt). Cette table a la taille d'une page (Memory.page_size). Chaque entrée de la table des pages est constituée de deux entiers. Le premier représente le mode d'accès à la page du processus : UN non chargée en mémoire; RW chargée avec accès en lecture/écriture et COW chargée, mais doit être copiée avant la première écriture. Le second entier de l'entrée correspond au numéro de la page en mémoire physique (si cela a un sens).

Pour compiler, lancer :
      
ocamlc -o main instr.ml memory.ml machine.ml system.ml main.ml
Si vous lancez main 0, celui-ci doit afficher 12 et 13.

1  Gestion des pages

Dans cette partie, on se prépare à la gestion des pages physiques.

Définir un tableau Memory.free_pages qui permet de connaître, pour chaque page, le nombre de processus qui référencent cette page. Écrire également une fonction Memory.new_page : unit -> int qui recherche une page vide dans la mémoire (suite à des désallocations la mémoire peut se retrouver fragmentée), la réserve, la remplit de 0, puis retourne le numéro de cette page. Si la mémoire est pleine, lever une exception Out_of_memory.

(corrigé)
      
exception Out_of_memory;;

let free_pages = Array.make page_number 0;;

let clear_page page_nb =
  let offset = page_nb * page_size in
  Array.fill memory offset page_size 0;;

let find_modulo f modulo from =
  let stop = from + modulo in
  let rec find k =
    if k < stop then
      let k' = k mod modulo in if f k' then k' else find (k+1)
    else raise Not_found  in
  find from

let next_page = ref 0;;

let new_page () =
  try
    let is_free p = free_pages.(p) = 0 in
    let page_nb = find_modulo is_free page_number !next_page in
    next_page := page_nb + 1;
    free_pages.(page_nb) <- 1;
    clear_page page_nb;
    page_nb
  with Not_found -> raise Out_of_memory;;
En utilisant, les informations du tableau Memory.free_pages réécrire une fonction Memory.used_page : unit -> bool valide qui retourne false si toutes les pages sont libres. Cette fonction est utilisée dans main.ml pour vérifier à la fin que vous avez bien libéré la mémoire de chaque processus. Vérifiez que le programme de test main 0 n'affiche pas qu'il y a des pages non libérées.
(corrigé)
      
let used_page () =
  let rec used_page_from i =
    i < page_number && (free_pages.(i) <> 0 || used_page_from (i + 1)) in
  used_page_from 0;;

2  Table des pages

On désire maintenant ajouter à notre machine une gestion de mémoire virtuelle. La mémoire physique Memory.memory est découpée en Memory.page_number pages physiques. Une page physique k (donc avec 0 < k < Memory.page_number) correspond donc aux adresses physiques entre k × page_size incluse et (k+1) × page_size exclue.

Chaque processus dispose d'une table de pages qui associe à chaque page virtuelle (entrée dans la table des pages) une page physique. La table des pages est elle-même maintenue en mémoire dans une page physique dont le numéro est placé dans le registre preg.(pt). Pour l'instant on se limitera à un seul processus (le processus initial). Une adresse physique est donc déterminée univoquement par le numéro physique de la table des pages et une adresse logique.

Écrire une fonction entry_address ptable page_nb: int -> int -> int qui retourne l'adresse physique de l'entrée (mode et adresse physique) correspondant à la page logique page_nb, connaissant la page physique ptable de la table des pages.
(corrigé)
      
let entry_address ptable page_nb =
  if page_nb < ptable_size then
    (ptable * page_size) + (2 * page_nb)
  else raise Segmentation_fault;;
Modifier les fonctions Memory.get: int -> int -> int et Memory.set: int -> int -> int -> unit afin de lire ou écrire le contenu d'une adresse logique, connaissant la page physique ptable de la table des pages. Lorsque la page n'est pas réservée (UN) les fonctions lèvent l'exception Page_fault avec le numéro de la page logique en argument. On supposera pour l'instant que les pages sont soit non réservées, soit réservées en écriture.
(corrigé)
      
let check_access ptable page_nb =
  let entry = entry_address ptable page_nb in
  match mode_of_int memory.(entry) with
  | UN -> raise (Page_fault page_nb) (* unallocated *)
  | _ -> ();; (* write access *)

let get ptable address =
  let page_nb = address / page_size in
  check_access ptable page_nb;
  let offset = address mod page_size in
  let entry = entry_address ptable page_nb in
  let real_address = memory.(entry+1) * page_size + offset in
  memory.(real_address);;

let set ptable address v =
  let page_nb = address / page_size in
  check_access ptable page_nb;
  let offset = address mod page_size in
  let entry = entry_address ptable page_nb in
  let real_address = memory.(entry+1) * page_size + offset in
  memory.(real_address) <- v;;
Écrire une fonction Memory.allocate_page ptable page_nb: int -> int -> unit qui réserve une nouvelle page physique pour la page logique page_nb connaissant la page physique ptable de la table des pages.
(corrigé)
      
let set_entry entry mode page_address =
  memory.(entry) <- int_of_mode mode;
  memory.(entry+1) <- page_address;;

let allocate_page ptable page_nb =
  let entry = entry_address ptable page_nb in
  set_entry entry RW (new_page ());;
Écrire une fonction Memory.new_ptable: unit -> int qui retourne une nouvelle page physique après en avoir fait une table de pages vide.
(corrigé)
      
let new_ptable () =
  let page = new_page () in
  for i = 0 to page_size - 1 do
    memory.(page * page_size + i) <- int_of_mode UN
  done;
  page;;
Modifier la fonction System.init_state afin de réserver la table des pages du processus initial.
(corrigé)
      
let init_state i codes =
  let process =
  { pcode = i;
    preg =  Array.make register_number 0;
    quantum = 0;
    pid = 1;
    ppid = 0;
    state = Ready;
    ptable_size = ptable_size; } in
  process.preg.(pt) <- new_ptable (); (* réservation de la table des pages *)
  let pids = Hashtbl.create 13 in
  Hashtbl.add pids 1 process;
  let last_pid = ref 1 in
  let rec new_pid() =
    incr last_pid;
    try
      ignore (Hashtbl.find pids !last_pid);
      new_pid()
    with Not_found -> !last_pid in
  { processes = pids;
    active_processes =  [ process ];
    current = process;
    codes = codes;
    new_pid = new_pid
  };;
Modifier maintenant la fonction System.page_fault afin de réserver une page en cas de faute de page. Tester votre programme en vérifiant qu'après utilisation de la table des pages le programme main 0 affiche le même résultat que sans table de pages.
(corrigé)
      
let rec page_fault system_state page_nb =
  let p = system_state.current in
  if !verbose then Printf.eprintf "Page %d faulted (size=%d)\n%!"
      page_nb p.ptable_size;
  allocate_page p.preg.(pt) page_nb;
  run system_state

and  run system_state =
  if !verbose then
    Printf.eprintf "pid=%d  code=%d starts running\n%!"
      system_state.current.pid
      system_state.current.pcode;
  let code = system_state.current.pcode in
  try process  system_state.codes.(code) with
    Trap -> syscall system_state
  | Signal -> signal system_state
  | Invalid_argument _ -> raise Invalid_code
  | Segmentation_fault -> segmentation_fault system_state
  | Page_fault page_nb  -> page_fault system_state page_nb

and signal system_state =
  incr time;
  if !time mod update_frequency = 0 then
    Hashtbl.iter (update_quantum system_state.current) system_state.processes;
  let p = system_state.current in
  p.quantum <- p.quantum + 1;
  if p.quantum == max_quantum then
    begin
      if !verbose then
        Printf.eprintf "pid=%d  preempted\n%!" system_state.current.pid;
      schedule system_state
    end
  else
    run system_state

and schedule system_state =
  let p = elect_process system_state in
  if !verbose then
    Printf.eprintf "resuming=%d\n%!" p.pid;
  system_state.current <- p;
  machine.reg <- p.preg;
  run system_state


and segmentation_fault system_state =
  print_endline "Segmentation fault";
  system_state.current.preg.(a0) <- 1;
  system_traps.(sys_Exit) system_state;;
Normalement, le programme de test précédent doit indiquer qu'il reste des pages non libérées. En effet, les pages allouées dynamiquement par le système en fonction des besoins doivent être désallouées à la fin des processus.

Écrire une fonction Memory.release_ptable ptable size qui libère toutes les pages associées à la table des pages dont la page physique est ptable et dont le nombre de pages est size.

(corrigé)
      
let decr_ref_page i =
  free_pages.(i) <- free_pages.(i) - 1;;

let release_ptable ptable size =
  for i = 0 to size - 1 do
    let entry = entry_address ptable i in
    match mode_of_int memory.(entry) with
    | UN -> ()
    | _ -> decr_ref_page memory.(entry + 1)
  done;
  decr_ref_page ptable;;
Modifier finalement l'appel système sys_Exit afin de libérer les pages mémoires réservées à la fin des processus. On vérifiera que toutes les pages sont bien désallouées en appelant main 0.

(corrigé)
      
let exit system_state =
  if !verbose then
    Printf.eprintf "Exit\n%!";
  let pid = system_state.current.pid in
  let rec waiting_parents process parents =
    if process.ppid == 0 then
      if parents = [] then
        raise No_waiting_parent
      else
        parents
    else
      let parent = Hashtbl.find system_state.processes process.ppid in
      match parent.state with
      | Waitpid i ->
          if i == pid then
            waiting_parents parent (parent :: parents)
          else
            waiting_parents parent parents
      | _ ->
          waiting_parents parent parents in
  let p = system_state.current in
  system_state.active_processes <-
    List.filter ((<>) p) system_state.active_processes;
  release_ptable p.preg.(pt) p.ptable_size; (* libérer la table des pages *)
  try
    let parents = waiting_parents system_state.current [] in
    let update parent =
      parent.state <- Ready;
      system_state.active_processes <-
        parent :: system_state.active_processes in
    List.iter update parents;
    remove_process p system_state.processes;
    schedule system_state
  with
    No_waiting_parent ->
      if system_state.current.ppid <> 0 then
        system_state.current.state <- Zombi p.preg.(a0)
      else
        remove_process p system_state.processes;
      schedule system_state in
system_traps.(sys_Exit) <- exit;;

3  Multi-processus

On désire maintenant combiner la gestion de processus et la mémoire virtuelle. Pour cela, nous allons commencer par gérer la mémoire en recopiant toutes les pages au moment de l'appel à fork.

Écrire une fonction Memory.clone_ptable ptable size qui clone la table des pages dont la page physique est passée en argument et dont le nombre de pages est donné par size.
(corrigé)
      
let copy_page from_page to_page =
  Array.blit
    memory (from_page * page_size)
    memory (to_page * page_size) page_size;;

let clone_ptable ptable size =
  let new_ptable = new_page () in
  let offset = ptable * page_size in
  let new_offset = new_ptable * page_size in
  for i = 0 to size - 1 do
    match mode_of_int memory.(offset + 2*i) with
    | RW ->
        let new_page = new_page () in
        copy_page memory.(offset + 2*i +1) new_page;
        memory.(new_offset + 2*i) <- int_of_mode RW;
        memory.(new_offset + 2*i +1) <- new_page
    | _ ->
        memory.(new_offset + 2*i) <- int_of_mode UN
  done;
  new_ptable;;
Modifier maintenant l'appel système sys_Fork pour prendre en compte l'utilisation de la mémoire virtuelle. Tester cette modification en appelant main 1 qui crée trois processus qui effectuent des accès mémoire et qui doivent normalement afficher 12, 12, 13, 12, 14, 12, 13, 12 et 14.

(corrigé)
      
let fork system_state  =
  if !verbose then
    Printf.eprintf "Fork\n%!";
  let p = system_state.current in
  let pid = system_state.new_pid () in
  if !verbose then
    Printf.eprintf "Son pid %d\n%!" pid;
  let son =
    { preg = Array.copy p.preg;
      pcode = system_state.current.pcode;
      quantum = 0;
      pid = pid;
      ppid = system_state.current.pid;
      state = Ready;
      ptable_size = p.ptable_size } in
  son.preg.(pt) <- clone_ptable p.preg.(pt) p.ptable_size;
  Hashtbl.add system_state.processes pid son;
  son.preg.(v0) <- 0;
  system_state.active_processes <- son :: system_state.active_processes;
  p.preg.(v0) <- pid;
  run system_state in
system_traps.(sys_Fork) <- fork;;

4  Copie paresseuse

Plutôt que de copier toutes les pages lors de la création d'un processus fils, la plupart des systèmes commence par partager les pages et attentent qu'ait lieu une écriture pour réaliser la copie effective (si l'accès a lieu en lecture, la copie n'est pas nécessaire). Pour cela, lors du fork les pages partagées sont marquées COW (Copy On Write) et elles sont recopiées lors d'un accès en écriture set.

Modifier les fonctions Memory.clone_ptable pour supporter la copie paresseuse.

(corrigé)
      
let incr_ref_page i =
  free_pages.(i) <- free_pages.(i) + 1;;

let clone_ptable ptable size =
  let new_ptable = new_page () in
  copy_page ptable new_ptable;
  let offset = ptable * page_size in
  let new_offset = new_ptable * page_size in
  for i = 0 to size - 1 do
    match mode_of_int memory.(offset + 2*i) with
    | RW ->
        memory.(new_offset + 2*i) <- int_of_mode COW;
        memory.(offset + 2*i) <- int_of_mode COW;
        incr_ref_page memory.(offset + 2*i + 1)
    | COW ->
        incr_ref_page memory.(offset + 2*i + 1)
    | _ -> ()
  done;
  new_ptable;;
Modifier la fonction Memory.set pour tenir compte de ce changement. Tester vos modifications en appelant à nouveau main 1.
(corrigé)
      
let write_access ptable page_nb =
  let entry = entry_address ptable page_nb in
   match mode_of_int memory.(entry) with
  | UN -> raise (Page_fault  page_nb) (* unallocated *)
  | COW -> (* copy on write *)
      let entry = entry_address ptable page_nb in
      let old_page = memory.(entry+1) in
      if free_pages.(old_page) = 1 then
        set_entry entry RW old_page
      else
        begin
          let new_page = new_page () in
          set_entry entry RW new_page;
          copy_page old_page new_page;
          decr_ref_page old_page
        end
  | _ -> ();; (* write access *)

let set ptable address v =
  let page_nb = address / page_size in
  write_access ptable page_nb;
  let offset = address mod page_size in
  let entry = entry_address ptable page_nb in
  let real_address = memory.(entry+1) * page_size + offset in
  memory.(real_address) <- v;;

5  Réservation de mémoire

Par défaut dans le système Unix, les processus ne peuvent pas accéder à n'importe quelle page de leur espace d'adressage. Avant de pouvoir accéder à une page, il faut d'abord qu'ils la réservent grâce à l'appel système brk en modifiant la valeur du champs ptable_size du processus.

Attention, l'appel système brk peut diminuer la taille de la table des pages et il faut alors désallouer les pages qui ne sont plus accessibles.

Écrire l'appel système sys_Brk.
(corrigé)
      
let release_page ptable page_nb =
  let offset = ptable * page_size in
  memory.(offset + page_nb*2) <- int_of_mode UN;
  decr_ref_page memory.(offset + page_nb*2 + 1);;

let brk system_state =
  if !verbose then
    Printf.eprintf "Brk\n%!";
  let p = system_state.current in
  let new_memory_size = p.preg.(a0) in
  if new_memory_size > page_size*ptable_size then
    p.preg.(v0) <- -1
  else
    begin
      let new_size = new_memory_size / page_size + 1 in
      let old_size = p.ptable_size in
      if new_size < old_size then
        for page_nb = new_size to old_size - 1 do
          release_page p.preg.(pt) page_nb
        done;
      p.ptable_size <- new_size;
      p.preg.(v0) <- 0
    end;
  run system_state in
system_traps.(sys_Brk) <- brk;;
Modifier enfin la fonction System.page_fault pour prendre en compte cette information lors d'une faute de page pour lever une exception Segmentation_fault lors de l'accès à une page hors limite. Testez vos modifications en appelant le programme de test main 2 qui doit afficher 12, 13, 12, 14, Segmentation fault, 12, 13, 12, 14, Segmentation fault.

(corrigé)
      
let rec page_fault system_state page_nb =
  let p = system_state.current in
  if !verbose then Printf.eprintf "Page %d faulted (size=%d)\n%!"
      page_nb p.ptable_size;
  if page_nb < p.ptable_size then
    begin
      allocate_page p.preg.(pt) page_nb;
      run system_state
    end
  else
    begin
      print_endline "Segmentation fault";
      p.preg.(a0) <- 1;
      system_traps.(sys_Exit) system_state
    end

and run system_state =
  if !verbose then
    Printf.eprintf "pid=%d  code=%d starts running\n%!"
      system_state.current.pid
      system_state.current.pcode;
  let code = system_state.current.pcode in
  try process  system_state.codes.(code) with
    Trap -> syscall system_state
  | Signal -> signal system_state
  | Invalid_argument _ -> raise Invalid_code
  | Segmentation_fault -> segmentation_fault system_state
  | Page_fault page_nb  -> page_fault system_state page_nb

and signal system_state =
  incr time;
  if !time mod update_frequency = 0 then
    Hashtbl.iter (update_quantum system_state.current) system_state.processes;
  let p = system_state.current in
  p.quantum <- p.quantum + 1;
  if p.quantum == max_quantum then
    begin
      if !verbose then
        Printf.eprintf "pid=%d  preempted\n%!" system_state.current.pid;
      schedule system_state
    end
  else
    run system_state

and schedule system_state =
  let p = elect_process system_state in
  if !verbose then
    Printf.eprintf "resuming=%d\n%!" p.pid;
  system_state.current <- p;
  machine.reg <- p.preg;
  run system_state


and segmentation_fault system_state =
  print_endline "Segmentation fault";
  system_state.current.preg.(a0) <- 1;
  system_traps.(sys_Exit) system_state;;


Ce document a été traduit de LATEX par HEVEA