Mis à jour le 13 mars 2006
TD 8

TD 8

Mardi 14 mars 2006


1  Questions de cours



Questions de cours

On fera cet exercice sans utiliser les notes de cours (ni les corrections de TD) ni aucune documentation.

Question 1.1

Quelle est la différence en ignorer un signal et bloquer une signal? Donner, si possible pour chacun des cas, un exemple où l'on voudrait l'un mais pas l'autre.

Question 1.2

On considère la fonction OCaml Unix.read correspondant à l'appel système Unix read.
  1. Donner son type.
  2. Décrire ce qu'elle fait.
  3. Donner trois raisons différentes d'échec possibles (on donnera si possible le nom des erreurs associées, mais ce n'est pas indispensable; dans tous les cas, on expliquera brièvement la raison de l'échec).


Ordonnancement des processus

L'objectif de ce td est d'étudier le mécanisme d'ordonnancement des processus d'un système en le simulant sur une machine virtuelle simpliste.

La machine virtuelle interprète un jeu d'instructions réduit et sa mémoire se restreint à un ensemble de registres. Les instructions sont décrites dans le fichier instr.ml et la machine dans le fichier machine.ml. Les registres de la machine sont représentés par un tableau d'entiers. Les instructions de la machine permettent de modifier le contenu de ces registres (Const, Move), d'effectuer des opérations arithmétiques sur ceux-ci (Bin) et de les utiliser pour influencer le déroulement du code (Label, If, Goto). Une instruction particulière System permet de déclencher un appel système dont le numéro est placé dans le registre v0. Celui-ci est simulé par la levée de l'exception Trap.

Par exemple le code suivant affiche les entiers de 1 à 50 via des appels systèmes à write, avant de se terminer par un appel système à exit.

      
  Const (50, a2);
  Const (0, a0);
  Const (1, a1);
  Label loop;
  Bin (Adda0a1a0);
  Const (sys_Writev0);
  System;
  If (Lta0,a2loop);
  Const (0, a0);
  Const (sys_Exitv0);
  System;

La machine virtuelle est démarrée par la fonction process. Celle-ci prend en argument un code (tableau d'instructions) à interpréter. Son interprétation commence à partir de l'instruction dont l'indice dans le code est placé dans le registre machine.reg.(pc) et se termine soit par la levée de l'exception Trap en cas d'appel système, soit par la levée de l'exception Signal utilisée pour rendre la main au système à intervalles réguliers après l'exécution d'un certain nombre d'instructions.

Le système est implanté dans le fichier system.ml. Le système manipule des processus. Chaque processus précise le numéro du code qu'il doit exécuter, contient un champ preg permettant de sauver l'état de ses registres, un champ quantum utilisé par l'ordonnanceur, son numéro de processus, le numéro de processus de son père et son état :

      
type process_state = Ready | Waitpid of int | Zombie of int
type process =
    { mutable pcode : int;           (* pointeur de code *)
      mutable preg : int array;      (* sauvegarde des registres *)
      mutable quantum : int;         (* quantum restant *)
      pid : int;                     (* numéro du processus *)
      mutable ppid : int;            (* numéro du processus père *)
      mutable state : process_state  (* état du processus *)
    }

L'état du système est lui constitué d'une table d'association entre numéros de processus et processus, d'une liste de processus actifs (un seul au démarrage), du processus actif courant, d'un tableau de codes que le système peut exécuter et d'une fonction d'allocation de numéro de processus :
      
type state  =
    { processes : (intprocessHashtbl.t;  (* table des processus *)
      active_processes : process list ref;   (* liste des processus prêts *)
      mutable current : process;             (* processus éxécuté *)
      codes : instr array array;             (* tout le code *)
      mutable last_pid : int;                (* dernier PID utilisé *)
    }

La fonction init_state: process -> instr array array -> state permet d'initialiser l'état du système avec un processus initial et un tableau de codes exécutables.

La fonction syscall réalise les appels systèmes. Pour cela, elle lit dans le registre v0 de la machine un numéro d'appel système (les arguments de l'appels seront placés dans les registres a0, a1, etc.), puis retrouve dans le tableau system_traps le code de l'appel système à exécuter. À l'origine ce tableau est initialisé avec une fonction qui lève l'exception Not_implemented chaque fois qu'un appel système est réalisé. C'est ce tableau que nous allons compléter au fur et à mesure du td avec de nouveaux appels systèmes.

Le système est démarré par l'appel à run qui prend en argument l'état courant du système. Cette fonction est liée aux fonctions signal et schedule qui sont appelées respectivement chaque fois que la machine rend la main au système après un certain nombre d'instructions et chaque fois que le système veut sélectionner un nouveau processus à exécuter. Les versions de ces deux fonctions que nous vous fournissons par défaut sont simplistes. La fonction signal se contente de relancer le processus courant. La fonction schedule choisit le premier processus disponible ou lève une exception Halt si tous les processus sont terminés.

Le fichier system.ml contient également l'implantation des appels systèmes exit et write. Ceux-ci prennent en argument le contenu des registres et l'état du système. L'appel système exit se contente d'éliminer le processus courant de la liste des processus et demande à schedule de sélectionner le prochain processus à exécuter. L'appel système write écrit sur la sortie standard la valeur qui se trouve dans le registre a0 puis relance l'interprétation du processus courant.

Nous vous proposons dans le fichier main.ml un ensemble d'exemples de codes pour tester vos implantations d'appels systèmes. Avec l'option -v une trace des instructions et des appels systèmes est affichée sur la sortie d'erreur.

Copier tous les fichiers que nous venons de décrire dans un répertoire. Pour les compiler, lancer :
      
ocamlc -o main instr.ml machine.ml system.ml main.ml

Tester ensuite le système de base en appelant main 0 qui sélectionne l'exécution du code 0 qui correspond au code que nous vous avons présenté plus haut.

2  Création de processus

Ajouter au fichier system.ml l'appel système fork qui a pour numéro sys_Fork. Cet appel système crée un nouveau processus. Son numéro sera obtenu par un appel à new_pid. Après l'appel à fork, le registre v0 contient 0 dans le processus fils et le numéro de processus du fils dans le processus père.

(corrigé)
      
let fork system_state  =
  if !verbose then Printf.eprintf "Fork\n%!";
  let p = system_state.current in
  let pid = new_pid system_state 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 } in
  Hashtbl.add system_state.processes pid son;
  (* fork retourne la valeur 0 pour le fils *)
  son.preg.(v0) <- 0;
  system_state.active_processes := son :: !(system_state.active_processes);
  (* fork retourne la valeur pid pour le père *)
  p.preg.(v0) <- pid;
  (* on appelle l'ordonnanceur *)
  run system_state in
(* on enregistre le code de fork dans la table des appels système *)
system_traps.(sys_Fork) <- fork;;
Ajouter ensuite les appels systèmes getpid et getppid qui retournent respectivement le numéro du processus et celui de son père dans le registre v0.
(corrigé)
      
let getpid system_state  =
  let p = system_state.current in
  if !verbose then Printf.eprintf "Getpid\n%!";
  p.preg.(v0) <- system_state.current.pid;
  run system_state in
system_traps.(sys_Getpid) <- getpid;;

let getppid system_state  =
  let p = system_state.current in
  if !verbose then Printf.eprintf "Getppid\n%!";
  p.preg.(v0) <- system_state.current.ppid;
  run system_state in
system_traps.(sys_Getppid) <- getppid;;
Vous pourrez tester vos appels systèmes en appelant main 1 qui crée un processus et qui commence par faire afficher par les deux processus leur pid et ppid (pour les différencier on a ajouté 10000 aux pids du père et 1000 aux pids du fils). Ensuite le processus père affiche les entiers de 1 à 50 et la processus fils ceux de 101 à 150.

3  Préemption

Comme doit l'avoir montré le test précédent, le système se contente d'exécuter les processus les uns après les autres. Modifier les fonctions signal et schedule afin que les processus aient un accès équitable à la machine. Pour cela, on pourra utiliser le champ quantum que l'on augmentera chaque fois que le processus aura accès au processeur (i.e. à chaque appel à signal) et que l'on diminuera régulièrement pour tous les processus qui n'ont pas eu accès au processeur en le divisant par deux (tous les 13 appels à signal, par exemple). Lorsqu'un nouveau processus doit être sélectionné, on choisit celui ayant le quantum le plus petit. Ainsi, un processeur ayant eu récemment un accès important au processeur est moins prioritaire, mais cette «pénalité» s'estompe au cours du temps de façon logarithmique. Lorsqu'un processus est choisi, on lui remet alors son quantum à zéro; lorsqu'un processus a atteint max_quantum, on doit en choisir un autre.
(corrigé)
      
let time = ref 0;;
let update_frequency = 13;;
let update_quantum current_process _ (* pid *) process =
  if process <> current_process then
    match process.state with
    | Zombie i -> ()
    | _ -> process.quantum <- process.quantum / 2;;

let elect_process active_processes =
  let cmp p1 p2 = compare p1.quantum p2.quantum in
  (* List.sort est stable, ie. preserve l'ordre sur les clés de même valeur.
     List.rev assure un comportement FIFO  à quatum égale, ce qui évite
     les situations de famine. *)

  active_processes := List.sort cmp (List.rev !active_processes);
  match !active_processes with
  | [] -> raise Halt
  | h :: t -> h.quantum <- 0; h;;

(** system_state est inchangé *)
let rec 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.(codewith
    Trap -> syscall system_state
  | Signal -> signal system_state
  | Invalid_argument _ -> raise Invalid_code

and signal system_state =
  incr time;
  if !time mod update_frequency = 0 then
    Hashtbl.iter (update_quantum system_state.currentsystem_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.active_processes in
  if !verbose then
    Printf.eprintf "resuming=%d\n%!" p.pid;
  system_state.current <- p;
  machine.reg <- p.preg;
  run system_state;;

4  Recouvrement

Ajouter au fichier system.ml l'appel système exec qui a le numéro sys_Exec. Cet appel système entraîne le recouvrement du code du processus courant par le code dont le numéro est placé dans le registre a0. Si ce code n'existe pas, la fonction retourne la valeur -1 dans le registre v0 et elle ne retourne jamais dans le cas contraire.

On pourra tester cette fonction en appelant main 2 qui doit commencer par afficher 100, puis les entiers de 1 à 50.
(corrigé)
      
let exec system_state =
  let p = system_state.current in
  begin
    let pcode = p.preg.(a0in
    try
      ignore system_state.codes.(pcode);
      if !verbose then
        Printf.eprintf "Exec %d\n%!" pcode;
      system_state.current.pcode <- pcode;
      p.preg.(pc) <- 0;
    with Invalid_argument s ->
      if !verbose then
        Printf.eprintf "Exec error %d\n%!" pcode;
      p.preg.(v0) <- -1
  end;
  run system_state in
system_traps.(sys_Exec) <- exec;;

5  Attente de fin d'un processus

On désire maintenant ajouter un appel système permettant d'attendre la fin d'un descendant du processus courant, waitpid. Le numéro du processus attendu est lu dans le registre a0 et la valeur de retour du processus est placée dans v0 (-1 pour une erreur, 0 pour une terminaison normale, 1 pour une autre terminaison). Pour une terminaison normale, on place dans v1 le code de terminaison du processus attendu. Lors d'un tel appel système, si le processus attendu n'est pas dans l'état Zombie, le processus courant passe dans l'état Waitpid avec le numéro du processus attendu en argument. Sinon, il élimine le processus de la table des processus et continue son exécution. Il y a erreur si le processus attendu n'existe pas ou s'il n'est pas un descendant du processus courant.

(corrigé)
      
(* Lorsqu'un Zombie est finalement libéré *)
let remove_process process processes =
  (* Il rattacher ses fils aux processus 0.
     ---XXX ce n'est pas ce qui est fait. *)

  let update_ppid ppid pid pid2 process2 =
    if process2.ppid = pid then (* c'est donc un fils *)
      match process2.state with
      | Zombie i -> Hashtbl.remove processes process2.pid
      | _ -> process2.ppid <- 0 in
  Hashtbl.iter (update_ppid process.ppid process.pidprocesses;
  Hashtbl.remove processes process.pid;;

let waitpid system_state =
  let p = system_state.current in
  if !verbose then Printf.eprintf "Waitpid\n%!";
  let rec is_child process =
    process.ppid = p.pid ||
    process.ppid <> 0 &&
    is_child (Hashtbl.find system_state.processes process.ppid)
  in
  let error () = p.preg.(v0) <- -1; run system_state in
  let pid = p.preg.(a0in
  try
    (* on cherche le processus dans la table des processus *)
    let process = Hashtbl.find system_state.processes pid in
    if not (is_child processthen error ()
    else
      begin
        (* retour normal *)
        p.preg.(v0) <- 0;
        match process.state with
        | Zombie ret ->
            p.preg.(v1) <- ret;
            remove_process process system_state.processes;
            run system_state
        | _ ->
            p.state <- Waitpid p.preg.(a0);
            system_state.active_processes :=
              List.filter ((<>) p) !(system_state.active_processes);
            schedule system_state
      end
  with Not_found -> error () in
system_traps.(sys_Waitpid) <- waitpid;;
Il faut également réécrire l'appel système exit afin de réveiller les éventuels processus parents en attente du processus qui vient de terminer et mettre à jour la hiérarchie de processus (mettre à jour le numéro du processus parent).

On pourra tester ces appels systèmes en appelant main 3 qui doit afficher des entiers croissants de 1 à 50 puis décroissant jusqu'à 1.
(corrigé)
      
exception No_waiting_parent;;

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);
  try
    let parents = waiting_parents system_state.current [] in
    let update_waiting parent =
      (* placer le code de retour *)
      parent.preg.(v1) <- p.preg.(a0);
      parent.state <- Ready;
      system_state.active_processes :=
        parent :: !(system_state.active_processesin
    List.iter update_waiting 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 <- Zombie p.preg.(a0)
      else
        remove_process p system_state.processes;
      schedule system_state in
system_traps.(sys_Exit) <- exit;;



Ce document a été traduit de LATEX par HEVEA