Mardi 22 mars 2005 |
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
.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
.Memory.memory
) en
utilisant une table de pages.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).ocamlc -o main instr.ml memory.ml machine.ml system.ml main.ml |
main 0
, celui-ci doit afficher 12
et 13
.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
.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;; |
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.
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;; |
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.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. 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.
let entry_address ptable page_nb = if page_nb < ptable_size then (ptable * page_size) + (2 * page_nb) else raise Segmentation_fault;; |
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.
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;; |
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.
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 ());; |
Memory.new_ptable: unit -> int
qui retourne une nouvelle
page physique après en avoir fait une table de pages vide.
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;; |
System.init_state
afin de réserver la table des
pages du processus initial.
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 };; |
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.
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;; |
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
.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;; |
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
.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;; |
fork
.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
.
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;; |
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
.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;; |
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
.Memory.clone_ptable
pour supporter la copie
paresseuse. 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;; |
Memory.set
pour tenir compte de ce
changement. Tester vos modifications en appelant à nouveau main 1
.
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;; |
brk
en modifiant la valeur du champs ptable_size
du
processus.brk
peut diminuer la taille de la table
des pages et il faut alors désallouer les pages qui ne sont plus
accessibles.sys_Brk
.
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;; |
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
.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