Mardi 14 mars 2006 |
On fera cet exercice sans utiliser les notes de cours (ni les corrections de TD) ni aucune documentation.
Unix.read
correspondant à l'appel système
Unix read
.
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
.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; |
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. 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 *) } |
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é *) } |
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.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.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.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.
-v
une trace des instructions et
des appels systèmes est affichée sur la sortie d'erreur.
ocamlc -o main instr.ml machine.ml system.ml main.ml |
main 0
qui sélectionne
l'exécution du code 0
qui correspond au code que nous vous avons présenté plus haut.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.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;; |
getpid
et getppid
qui retournent
respectivement le numéro du processus et celui de son père dans le registre v0
.
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;; |
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
.
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.
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.(code) with 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.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.active_processes in if !verbose then Printf.eprintf "resuming=%d\n%!" p.pid; system_state.current <- p; machine.reg <- p.preg; run system_state;; |
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.main 2
qui doit commencer par afficher 100
, puis les entiers de 1
à 50
.
let exec system_state = let p = system_state.current in begin let pcode = p.preg.(a0) in 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;; |
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.(* 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.pid) processes; 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.(a0) in try (* on cherche le processus dans la table des processus *) let process = Hashtbl.find system_state.processes pid in if not (is_child process) then 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;; |
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). main 3
qui doit
afficher des entiers croissants de 1
à 50
puis décroissant jusqu'à 1
.
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_processes) in 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