Round-robin CPU scheduling emulator

There has got to be a better way to run this than with this silly shell
interpreter business.  After all, this is a strongly typed language; let's
compile the goddamn thing.  Unfortunately the interpreter was easier to do
than actually reading to docs for ocamlc to figure out how to set an entry
point for the module (if that is indeed the way to do it).  So anyway, to
create the interp do:

  ocamlmktop -custom -o mocaml str.cma

(str.cma is need for regular expressions.)  Change the #! at the start of this
file to point to the mocaml file you just created.  Make sure the privleges on
rr.ml include execute.  Then do:

  ./rr.ml <file>

There is something nice about writing an ML program: you know when you're
done.  It's like the feeling that comes with fitting the last peice into place
on a jigsaw puzzle.

This file should be available at:

   http://www.cs.uvm.edu/~dvanhorn/ocaml/os/rr.ml

-d

----rr.ml----

#!/home/cs/csugrads/dvanhorn/local/bin/mocaml

(**
   Round-robin CPU scheduling emulator

   Copyright (c) 2003 David Van Horn
   Licensed under the Academic Free License version 2.0

   A work of art is a machine with an aesthetic purpose.
   -- James Boyk

   This program simulates the events in a multiprogrammed computer system
   according to the following guidelines: Round-Robin scheduling is used.
   Time Slice = 5.  The number of processes is unbounded.  A counter
   implements the logical clock.  At each increment of the counter the program
   checks if the current counter value (time) matches with an arrival time of
   any process, and enter arriving process(es) automatically into the tail of
   the ready queue.  If a process finishes completely then it leaves the
   system, and the process at the head of the ready queue is allocated the
   CPU.  If time slice is expired and the process does not finish then the
   process is inserted into the tail of the queue, and a process (possibly the
   one just inserted) at the head of the queue is allocated the CPU.

   Simulation will continue until all processes finish completely.  An input
   file includes information for all processes, their arrival times, and a
   CPU-burst.  Input lines are of four possible formats (Assume that there is
   exactly one line of input for CPU burst):

   BEGIN <process number (<=10)> <arrival time>
   CPU <CPU burst>
   END /* Process description ends */

   The following is an example:

   BEGIN 1 0
   CPU 7
   END
   BEGIN 2 5
   CPU 4
   END

   The program reports which process executes as there occurs a change, or at
   the beginning of every time slice.  For example see the output below for
   the input given above.  Events are reported in the following format:

   TIME: 0 PRO 1 EXEC
   TIME: 5 PRO 2 EXEC
   TIME: 9 PRO 1 EXEC

   @author David Van Horn
*)

module Rr =
  struct
    open List
    open Printf
    open Str

    (**
       A process (or PCB) is either the null process or consists of a process
       number, an arrival time, and burst time.
    *)
    type process =
      | Process of int * int * int
      | NullProcess	

    let arrive_now_p t = function
      | Process(_,a,_) when a=t -> true
      | _ -> false

    let time_slice = 5
	
    let print_event t p =
      printf "TIME %d PRO %d EXEC\n" t (match p with Process(n,_,_) -> n)

    (**
       The step function transitions from machine configuration to machine
       configuration.  A machine configuration is a 5-tuple consisting of a
       queue of processes that have arrived and are waiting to be swapped into
       the cpu, a process that is currently running on the cpu, the current
       time, the time slice for current process, and a list of process that
       have yet to arrive.
    *)
    let step (q,p,t,s,j) =

     (*
	We push all processes that are scheduled to arrive at the current time
	onto the queue.
     *)
      let q = append q (filter (arrive_now_p t) j) in

     (*
	We remove from the list of processes that have yet to arrive those
	processes which are scheduled to arrive at the current time.
     *)
      let j = filter (fun x -> (not (arrive_now_p t x))) j in

      match (q,p,t,s) with
	
      (*
	 If the queue is empty and the null process is currently executing
	 (the cpu is idle), we have nothing to do, so increment the time and
	 continue.
      *)
      | [], NullProcess, t, s -> [], NullProcess, t+1, s, j

      (*
	 If the queue is non-empty and the null process is currently executing
	 (the cpu is idle), we take the next process from the queue and swap
	 it into the cpu (reseting the time slice).  This operation does not
	 increment the time.
      *)
      | p::q, NullProcess, t, _ ->
	  print_event t p;
	  q, p, t, time_slice, j
	
      (*
	 If the currently executing process has exhausted its burst time, the
	 cpu becomes idle.  This operation does not increment the time.
      *)
      | q, Process(n,a,0), t, s -> q, NullProcess, t, s, j

      (*
	 If the currently executing process has exhausted its time slice, the
	 cpu becomes idle and the process is pushed onto the queue.  This
	 operation does not increment the time.
      *)
      | q, p, t, 0 -> q@[p], NullProcess, t, 0, j

      (*
	 If the current process has burst time remaining and time slice
	 remaining, we let the cpu continue to run the process, decrementing
	 the burst and time slice and incrementing the time.
      *)
      | q, Process(n,a,b), t, s -> q, Process(n,a,b-1), t+1, s-1, j

    let parse file_name =
      let in_channel = (open_in file_name) in
      let rec loop ps =
	try
	  match (split (regexp "[ \t]+") (input_line in_channel)) with
	  | ["BEGIN"; n; i] ->
	      let burst =
		match (split (regexp "[ \t]+") (input_line in_channel)) with
		| ["CPU"; b] -> (int_of_string b)
	      in
	      loop ((Process(int_of_string n, int_of_string i, burst))::ps)
	  | ["END"] -> loop ps
	with End_of_file -> ps
      in
      loop []
	
    (**
       A machine runs until it is in a final configuration, which is defined
       as a configuration with no processes in the waiting queue, an idle cpu,
       and no processes yet to arrive.
    *)
    let main file_name =
      let rec loop = function
	| [], NullProcess, _, _, [] -> ()
	| state -> loop (step state)
      in
      let proc_list = parse file_name in
      loop ([], NullProcess, 0, 0, (parse file_name))

end
;;

Rr.main(Sys.argv.(1));;