Mis à jour le 13 mars 2006
TD 8

TD 8

Mardi 14 mars 2006

1  Questions de cours

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 (Add, a0, a1, a0);
  Const (sys_Write, v0);
  System;
  If (Lt, a0,a2, loop);
  Const (0, a0);
  Const (sys_Exit, v0);
  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 : (int, process) Hashtbl.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é)
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é)
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é)

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é)

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é)
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é)


Ce document a été traduit de LATEX par HEVEA