program disksim(input,output,outdata);

(* written by Dan Joyce
   Villanova University
   March 1988
   for use with the Investigation of Disk Scheduling Algorithms Lab

   updated May 1997
   to include output of data only file
*)

(* Fulfills part of the Disk Scheduling Simulation Specification.

   Fulfills everything except it does not simulate the LOOK algorithm.
   To include the LOOK algorithm in the simulation you should fill out
   the current look function with the appropriate code, 'uncomment'
   the line related to the look algorithm in the simulate procedure,
   and change the upper bound of the 'for algnum' loop in the main
   program from 1 to 3.
*)


const     c = 199;    (* top cylinder number *)
        st1 =  25;    (* seek time to move one cylinder *)
        stc = 130;    (* seek time to move 'c' cylinders *)
          t =  25;    (* disk rotation time *)
    numarrt =   4;    (* number of simulated arrival rates *)
    lowarrt =  10;    (* lowest arrival rate ... arrival per second *)
    incarrt =  10;    (* increment of arrival rates *)
    numobsv = 500;    (* number of observations for each arrival rate *)

          a = 16807;        (* used by random number generator *)
     ulimit = 2147483647;   (* used by random number generator *)
          q = 127773;       (* used by random number generator *)
          r = 2836;         (* used by random number generator *)


type reqrec = record  (* request record *)
               arrtime:  integer;    (* arrival time in milleseconds *)
               cylinder: integer;    (* requested cylinder *)
               fintime:  integer;    (* fimish time in milleseconds *)
              end;    

var       m: integer; (* number of sectors per track *)
       mnum: integer; (* index of m for loop control *)
    reqfreq: integer; (* number of requests per second *)
     algnum: integer; (* algorithm number: 1=FCFS, 2=SSTF, 3=LOOK *)

      count: integer; (* index of arrate for loop control *)
     arrate: integer; (* current arrival rate ... per second *)

        est: real;    (* expected service time *)
          w: real;    (* expected waiting time *)
       sdwt: real;    (* standard deviation of waiting time *)

       time: integer; (* current time in milleseconds *)
     curcyl: integer; (* current cylinder *)
    nextreq: integer; (* index of next request to be satisfied *)
  direction: (up,down); (* direction of head movement for LOOK *)
  sumsktime: integer; (* sum of the seek times *)

   requests: array[1..numarrt,1..numobsv] of reqrec;     

    latency: integer; (* t/2 + t/m *)
      slope: real;    (* for calculating seek time *)
  intercept: real;    (* for calculating seek time *)

  rand,seed: integer; (* for random number generator *)

    outdata: text;    (* raw output data *)

(************************************************************************)

procedure dumprequests(dim1,dim2:integer);
(* used for debugging
   will dump the values in the requests array from 1..dim1,1..dim2
*)
var i,j: integer;

begin
writeln;
writeln('A dump of the requests array from 1..',dim1:1,',1..',dim2:1);
writeln;
for i := 1 to dim1 do
   begin
   writeln;
   writeln('First dimension is: ',i:1);
   writeln('Values are:');
   writeln;
   for j := 1 to dim2 do
      begin
      with requests[i,j] do
         write(arrtime:5,' ',cylinder:3,' ',fintime:5,';');
      if (j mod 4) = 0 then writeln;
      end;  (* for j *)
   writeln;
   end; (* for i *)

end; (* dumprequests *)

(************************************************************************)

function random:integer;
(* returns a random number in the range 0..'ulimit'. 
   see Park and Miller, CACM 10/88
 *)
var lo, hi, test: integer;
begin
hi := seed div q;
lo := seed mod q;
test := a * lo - r * hi;
if test > 0 then
  seed := test
else
  seed := test + ulimit;
random := seed;
end;

(***************************************************************************)

procedure genarrivals;
(* - generates the interarrival times
   - uses them to initialize the arrtime field of the 'requests' array
*)

var i,j: integer;
    arrrate: integer;  (* arrival rate per second *)
    lambda: integer;   (* average inter-arrival time in milleseconds *)
    cur: integer;
    intarrtime: integer;
    randreal: real;

begin
for j := 1 to numarrt do
    begin
    arrrate := lowarrt + ((j-1)*incarrt);
    if arrrate <= 0 then writeln('****ERROR*** in genarrivals: arrrate <= 0!!');
    lambda := round((1/arrrate)*1000);
    cur := 0;
    for i:= 1 to numobsv do
        begin
        rand := random;
        randreal := rand/ulimit;
        intarrtime := round(-lambda*ln(randreal));
        cur := cur + intarrtime;
        requests[j,i].arrtime := cur;
        end;
    end;
end;    (* genarrivals *)

(***************************************************************************)


procedure gencylreqs;
(* - generates the cylinder requests
   - uses them to initialize the cylinder field of the requests array
*)

var i,j: integer;
    cylinder: integer;

begin
for j:= 1 to numarrt do
  for i:= 1 to numobsv do
    begin
    rand := random;
    requests[j,i].cylinder := rand mod (c+1);
    end;
end;    (* gencylreqs *)

(***************************************************************************)

procedure initialize;

(* initializes all the global variables as pertain to a single
   simulation run *)

var i: integer;

begin

curcyl := 0;
nextreq := 0;
direction := up;
sumsktime := 0;

for i := 1 to numobsv do requests[count,i].fintime := 0;

est := 0;
w := 0;
sdwt := 0;
time := 0;

end; (* initialize *)

(***************************************************************************)

function fcfs:integer;
(* returns the index of the next request to be served based on the 
   first come first serve disk scheduling algorithm *)

begin
fcfs := nextreq + 1;
end; (* fcfs *)

(***************************************************************************)

function sstf: integer;
(* returns the index of the next request to be served based on the 
   the shortest seek time first disk scheduling algorithm *)

var closestdist: integer;    (* closest distance so far *)
    closestreq: integer;     (* index of the closest request *)
    curcheck: integer;       (* index of the request currently being tested *)
    keeplooking: boolean;    (* loop control *)

begin

closestdist := c+2;   (* maximium + 1 *)
closestreq := 0;
curcheck := 1;
keeplooking := requests[count,curcheck].arrtime <= time;

while keeplooking do
   begin
   if ((abs(curcyl - requests[count,curcheck].cylinder) < closestdist)
                                 and
                 (requests[count,curcheck].fintime = 0))
      then begin
           closestdist := abs(curcyl - requests[count,curcheck].cylinder);
           closestreq := curcheck;
           end;
   curcheck := curcheck + 1;
   if (curcheck > numobsv) then keeplooking := false;
   if keeplooking then if requests[count,curcheck].arrtime > time
      then keeplooking := false;
   end;

if closestreq = 0     (* only happens if at current time no requests exist *)
 then closestreq := curcheck;(* curcheck indexes earliest outstanding request *)
 
sstf := closestreq;

end; (* sstf *)

(***************************************************************************)

function look: integer;
(* returns the index of the next request to be served based on the 
   look disk scheduling algorithm *)

begin

(* not yet implemented *)

look := 0;

end; (* look *)

(***************************************************************************)

procedure satisfy(nextreq:integer);
(* Simulates the servicing of the request indexed by 'nextreq'.
   
   Globals changed: curcyl ... updated to reflect head movement.
                    sumsktime ... updated to reflect head movement.
                    time ... updated to reflect head movement and latency.
                         ... also updated to reflect idle time if necessary.
                    requests[count,nextreq].fintime ... set to finish time.
*)

var sktime: integer;  (* seek time for this request in milleseconds *)
    numcyl: integer;  (* number of cylinders traveled for this request *)

begin
with requests[count,nextreq] do
   begin
   if time < arrtime then time := arrtime;    (* idle time *)
   numcyl := abs(cylinder-curcyl);
   if numcyl = 0 then sktime := 0
                 else sktime := round((slope*numcyl) + intercept);
   sumsktime := sumsktime + sktime;
   time := time + sktime + latency;
   fintime := time;
   curcyl := cylinder;
   end; (* with *)
end; (* satisfy *)

(***************************************************************************)

procedure simulate;
(* simulates the current algorithm *)

var i: integer;

begin
for i := 1 to numobsv do
   begin
   case algnum of                       (* call appropriate procedure *)
      1: nextreq := fcfs;
      2: nextreq := sstf;
(*    3: nextreq := look;   *)
      end;  (* case *)
   satisfy(nextreq);
   end; (* for *)
end; (* simulate *)

(***************************************************************************)

procedure getstats;
(* computes the culminated statistics of a simulation run *)

var sumwtime: integer;
           i: integer;
  sumdiffsqr: real;
        
begin

est := (sumsktime/numobsv) + latency;

sumwtime := 0;
for i:= 1 to numobsv do
   sumwtime := sumwtime + requests[count,i].fintime - requests[count,i].arrtime;

w := sumwtime/numobsv;

sumdiffsqr := 0.0;
for i:= 1 to numobsv do
   sumdiffsqr := sumdiffsqr + 
              sqr(w - (requests[count,i].fintime - requests[count,i].arrtime));

sdwt := sqrt(sumdiffsqr/numobsv);

end; (* getstats *)

(***************************************************************************)

procedure printinfo;
(* prints out all the info from the current previous simulation *)

begin
writeln;

writeln('Results of the simulation with:');
writeln;

writeln(' * arrival rate = ',arrate:1);
write(outdata, arrate:2, ' ');
writeln(' * sectors/track = ',m:1);
write(outdata, m:2, ' ');
writeln(' * latency = ',latency:1);
write(outdata, latency:2, ' ');

write(' * Algorithm = ');
case algnum of
          1: writeln('fcfs');
          2: writeln('sstf');
          3: writeln('look');
          end;  (* case *)
write(outdata, algnum:2, ' ');
writeln;

writeln(' * Expected service time = ',est:8:2);
write(outdata, est:8:2, ' ');
writeln(' * Expected waiting time = ',w:8:2);
write(outdata, w:8:2, ' ');
writeln(' * Stand Dev of wait tme = ',sdwt:8:2);
writeln(outdata, sdwt:8:2);

writeln;
writeln('**********************************************************');
writeln;

end; (* printinfo *)

(***************************************************************************)

begin (* main *)

(* NOTE: if using Turbo Pascal place an Assign statement here to
   assign outdata to a specific file
   e.g. 'Assign (outdata, 'b:outdata.dat')' *)
 
rewrite(outdata);

writeln('Input seed'); 
read(seed);
writeln;
writeln('The seed was: ',seed:1);
writeln(outdata,seed:1);

rand := seed;
writeln;
genarrivals;
gencylreqs;

(* values for seek time equation *)
slope := (stc-st1)/(c-1);
intercept := st1-slope;
writeln('slope = ',slope:1:1,' intercept = ',intercept:1:1);
writeln(outdata, slope:1:1, ' ', intercept:1:1);

(* write out constants *)
writeln;
writeln('Top cylinder number = ',c:1,'.');
writeln('Seek time to move 1 cylinder = ',st1:1, ' milleseconds.');
writeln('Seek time to move ',c:1,' cylinders = ',stc:1, ' milleseconds.');
writeln('Disk rotation time = ',t:1,' milleseconds.');
writeln('Number of observations = ',numobsv:1,'.');
writeln(outdata, c:1, ' ', st1:1, ' ', stc:1, ' ', t:1, ' ', numobsv:1);

for count := 1 to numarrt do                  (* for each arrival rate *)
   begin
   arrate := lowarrt + ((count-1)*incarrt);   (* initialize the arrival rate *)
   for mnum := 1 to 2 do                      (* for each value of m *)
      begin
      case mnum of                            (* initialize the m *)
         1: m :=  4;
         2: m := 50;
         end; (* case *)
      latency := round((t/2) + (t/m));
      for algnum := 1 to 2 do                 (* for each algorithm *)
         begin
         initialize;                          (* initialize globals *)
         simulate;                            (* simulate the current algorithm *)
         getstats;                            (* collect statistics *)
         printinfo;                           (* print out stats *)
         end; (* for algnum *)
      end; (* for mnum *)
   end; (* for count *)

end.