001 program disksim(input,output,outdata);
002 
003 (* written by Dan Joyce
004    Villanova University
005    March 1988
006    for use with the Investigation of Disk Scheduling Algorithms Lab
007 
008    updated May 1997
009    to include output of data only file
010 *)
011 
012 (* Fulfills part of the Disk Scheduling Simulation Specification.
013 
014    Fulfills everything except it does not simulate the LOOK algorithm.
015    To include the LOOK algorithm in the simulation you should fill out
016    the current look function with the appropriate code, 'uncomment'
017    the line related to the look algorithm in the simulate procedure,
018    and change the upper bound of the 'for algnum' loop in the main
019    program from 1 to 3.
020 *)
021 
022 
023 const     c = 199;    (* top cylinder number *)
024         st1 =  25;    (* seek time to move one cylinder *)
025         stc = 130;    (* seek time to move 'c' cylinders *)
026           t =  25;    (* disk rotation time *)
027     numarrt =   4;    (* number of simulated arrival rates *)
028     lowarrt =  10;    (* lowest arrival rate ... arrival per second *)
029     incarrt =  10;    (* increment of arrival rates *)
030     numobsv = 500;    (* number of observations for each arrival rate *)
031 
032           a = 16807;        (* used by random number generator *)
033      ulimit = 2147483647;   (* used by random number generator *)
034           q = 127773;       (* used by random number generator *)
035           r = 2836;         (* used by random number generator *)
036 
037 
038 type reqrec = record  (* request record *)
039                arrtime:  integer;    (* arrival time in milleseconds *)
040                cylinder: integer;    (* requested cylinder *)
041                fintime:  integer;    (* fimish time in milleseconds *)
042               end;    
043 
044 var       m: integer; (* number of sectors per track *)
045        mnum: integer; (* index of m for loop control *)
046     reqfreq: integer; (* number of requests per second *)
047      algnum: integer; (* algorithm number: 1=FCFS, 2=SSTF, 3=LOOK *)
048 
049       count: integer; (* index of arrate for loop control *)
050      arrate: integer; (* current arrival rate ... per second *)
051 
052         est: real;    (* expected service time *)
053           w: real;    (* expected waiting time *)
054        sdwt: real;    (* standard deviation of waiting time *)
055 
056        time: integer; (* current time in milleseconds *)
057      curcyl: integer; (* current cylinder *)
058     nextreq: integer; (* index of next request to be satisfied *)
059   direction: (up,down); (* direction of head movement for LOOK *)
060   sumsktime: integer; (* sum of the seek times *)
061 
062    requests: array[1..numarrt,1..numobsv] of reqrec;     
063 
064     latency: integer; (* t/2 + t/m *)
065       slope: real;    (* for calculating seek time *)
066   intercept: real;    (* for calculating seek time *)
067 
068   rand,seed: integer; (* for random number generator *)
069 
070     outdata: text;    (* raw output data *)
071 
072 (************************************************************************)
073 
074 procedure dumprequests(dim1,dim2:integer);
075 (* used for debugging
076    will dump the values in the requests array from 1..dim1,1..dim2
077 *)
078 var i,j: integer;
079 
080 begin
081 writeln;
082 writeln('A dump of the requests array from 1..',dim1:1,',1..',dim2:1);
083 writeln;
084 for i := 1 to dim1 do
085    begin
086    writeln;
087    writeln('First dimension is: ',i:1);
088    writeln('Values are:');
089    writeln;
090    for j := 1 to dim2 do
091       begin
092       with requests[i,j] do
093          write(arrtime:5,' ',cylinder:3,' ',fintime:5,';');
094       if (j mod 4) = 0 then writeln;
095       end;  (* for j *)
096    writeln;
097    end; (* for i *)
098 
099 end; (* dumprequests *)
100 
101 (************************************************************************)
102 
103 function random:integer;
104 (* returns a random number in the range 0..'ulimit'. 
105    see Park and Miller, CACM 10/88
106  *)
107 var lo, hi, test: integer;
108 begin
109 hi := seed div q;
110 lo := seed mod q;
111 test := a * lo - r * hi;
112 if test > 0 then
113   seed := test
114 else
115   seed := test + ulimit;
116 random := seed;
117 end;
118 
119 (***************************************************************************)
120 
121 procedure genarrivals;
122 (* - generates the interarrival times
123    - uses them to initialize the arrtime field of the 'requests' array
124 *)
125 
126 var i,j: integer;
127     arrrate: integer;  (* arrival rate per second *)
128     lambda: integer;   (* average inter-arrival time in milleseconds *)
129     cur: integer;
130     intarrtime: integer;
131     randreal: real;
132 
133 begin
134 for j := 1 to numarrt do
135     begin
136     arrrate := lowarrt + ((j-1)*incarrt);
137     if arrrate <= 0 then writeln('****ERROR*** in genarrivals: arrrate <= 0!!');
138     lambda := round((1/arrrate)*1000);
139     cur := 0;
140     for i:= 1 to numobsv do
141         begin
142         rand := random;
143         randreal := rand/ulimit;
144         intarrtime := round(-lambda*ln(randreal));
145         cur := cur + intarrtime;
146         requests[j,i].arrtime := cur;
147         end;
148     end;
149 end;    (* genarrivals *)
150 
151 (***************************************************************************)
152 
153 
154 procedure gencylreqs;
155 (* - generates the cylinder requests
156    - uses them to initialize the cylinder field of the requests array
157 *)
158 
159 var i,j: integer;
160     cylinder: integer;
161 
162 begin
163 for j:= 1 to numarrt do
164   for i:= 1 to numobsv do
165     begin
166     rand := random;
167     requests[j,i].cylinder := rand mod (c+1);
168     end;
169 end;    (* gencylreqs *)
170 
171 (***************************************************************************)
172 
173 procedure initialize;
174 
175 (* initializes all the global variables as pertain to a single
176    simulation run *)
177 
178 var i: integer;
179 
180 begin
181 
182 curcyl := 0;
183 nextreq := 0;
184 direction := up;
185 sumsktime := 0;
186 
187 for i := 1 to numobsv do requests[count,i].fintime := 0;
188 
189 est := 0;
190 w := 0;
191 sdwt := 0;
192 time := 0;
193 
194 end; (* initialize *)
195 
196 (***************************************************************************)
197 
198 function fcfs:integer;
199 (* returns the index of the next request to be served based on the 
200    first come first serve disk scheduling algorithm *)
201 
202 begin
203 fcfs := nextreq + 1;
204 end; (* fcfs *)
205 
206 (***************************************************************************)
207 
208 function sstf: integer;
209 (* returns the index of the next request to be served based on the 
210    the shortest seek time first disk scheduling algorithm *)
211 
212 var closestdist: integer;    (* closest distance so far *)
213     closestreq: integer;     (* index of the closest request *)
214     curcheck: integer;       (* index of the request currently being tested *)
215     keeplooking: boolean;    (* loop control *)
216 
217 begin
218 
219 closestdist := c+2;   (* maximium + 1 *)
220 closestreq := 0;
221 curcheck := 1;
222 keeplooking := requests[count,curcheck].arrtime <= time;
223 
224 while keeplooking do
225    begin
226    if ((abs(curcyl - requests[count,curcheck].cylinder) < closestdist)
227                                  and
228                  (requests[count,curcheck].fintime = 0))
229       then begin
230            closestdist := abs(curcyl - requests[count,curcheck].cylinder);
231            closestreq := curcheck;
232            end;
233    curcheck := curcheck + 1;
234    if (curcheck > numobsv) then keeplooking := false;
235    if keeplooking then if requests[count,curcheck].arrtime > time
236       then keeplooking := false;
237    end;
238 
239 if closestreq = 0     (* only happens if at current time no requests exist *)
240  then closestreq := curcheck;(* curcheck indexes earliest outstanding request *)
241  
242 sstf := closestreq;
243 
244 end; (* sstf *)
245 
246 (***************************************************************************)
247 
248 function look: integer;
249 (* returns the index of the next request to be served based on the 
250    look disk scheduling algorithm *)
251 
252 begin
253 
254 (* not yet implemented *)
255 
256 look := 0;
257 
258 end; (* look *)
259 
260 (***************************************************************************)
261 
262 procedure satisfy(nextreq:integer);
263 (* Simulates the servicing of the request indexed by 'nextreq'.
264    
265    Globals changed: curcyl ... updated to reflect head movement.
266                     sumsktime ... updated to reflect head movement.
267                     time ... updated to reflect head movement and latency.
268                          ... also updated to reflect idle time if necessary.
269                     requests[count,nextreq].fintime ... set to finish time.
270 *)
271 
272 var sktime: integer;  (* seek time for this request in milleseconds *)
273     numcyl: integer;  (* number of cylinders traveled for this request *)
274 
275 begin
276 with requests[count,nextreq] do
277    begin
278    if time < arrtime then time := arrtime;    (* idle time *)
279    numcyl := abs(cylinder-curcyl);
280    if numcyl = 0 then sktime := 0
281                  else sktime := round((slope*numcyl) + intercept);
282    sumsktime := sumsktime + sktime;
283    time := time + sktime + latency;
284    fintime := time;
285    curcyl := cylinder;
286    end; (* with *)
287 end; (* satisfy *)
288 
289 (***************************************************************************)
290 
291 procedure simulate;
292 (* simulates the current algorithm *)
293 
294 var i: integer;
295 
296 begin
297 for i := 1 to numobsv do
298    begin
299    case algnum of                       (* call appropriate procedure *)
300       1: nextreq := fcfs;
301       2: nextreq := sstf;
302 (*    3: nextreq := look;   *)
303       end;  (* case *)
304    satisfy(nextreq);
305    end; (* for *)
306 end; (* simulate *)
307 
308 (***************************************************************************)
309 
310 procedure getstats;
311 (* computes the culminated statistics of a simulation run *)
312 
313 var sumwtime: integer;
314            i: integer;
315   sumdiffsqr: real;
316         
317 begin
318 
319 est := (sumsktime/numobsv) + latency;
320 
321 sumwtime := 0;
322 for i:= 1 to numobsv do
323    sumwtime := sumwtime + requests[count,i].fintime - requests[count,i].arrtime;
324 
325 w := sumwtime/numobsv;
326 
327 sumdiffsqr := 0.0;
328 for i:= 1 to numobsv do
329    sumdiffsqr := sumdiffsqr + 
330               sqr(w - (requests[count,i].fintime - requests[count,i].arrtime));
331 
332 sdwt := sqrt(sumdiffsqr/numobsv);
333 
334 end; (* getstats *)
335 
336 (***************************************************************************)
337 
338 procedure printinfo;
339 (* prints out all the info from the current previous simulation *)
340 
341 begin
342 writeln;
343 
344 writeln('Results of the simulation with:');
345 writeln;
346 
347 writeln(' * arrival rate = ',arrate:1);
348 write(outdata, arrate:2, ' ');
349 writeln(' * sectors/track = ',m:1);
350 write(outdata, m:2, ' ');
351 writeln(' * latency = ',latency:1);
352 write(outdata, latency:2, ' ');
353 
354 write(' * Algorithm = ');
355 case algnum of
356           1: writeln('fcfs');
357           2: writeln('sstf');
358           3: writeln('look');
359           end;  (* case *)
360 write(outdata, algnum:2, ' ');
361 writeln;
362 
363 writeln(' * Expected service time = ',est:8:2);
364 write(outdata, est:8:2, ' ');
365 writeln(' * Expected waiting time = ',w:8:2);
366 write(outdata, w:8:2, ' ');
367 writeln(' * Stand Dev of wait tme = ',sdwt:8:2);
368 writeln(outdata, sdwt:8:2);
369 
370 writeln;
371 writeln('**********************************************************');
372 writeln;
373 
374 end; (* printinfo *)
375 
376 (***************************************************************************)
377 
378 begin (* main *)
379 
380 (* NOTE: if using Turbo Pascal place an Assign statement here to
381    assign outdata to a specific file
382    e.g. 'Assign (outdata, 'b:outdata.dat')' *)
383  
384 rewrite(outdata);
385 
386 writeln('Input seed'); 
387 read(seed);
388 writeln;
389 writeln('The seed was: ',seed:1);
390 writeln(outdata,seed:1);
391 
392 rand := seed;
393 writeln;
394 genarrivals;
395 gencylreqs;
396 
397 (* values for seek time equation *)
398 slope := (stc-st1)/(c-1);
399 intercept := st1-slope;
400 writeln('slope = ',slope:1:1,' intercept = ',intercept:1:1);
401 writeln(outdata, slope:1:1, ' ', intercept:1:1);
402 
403 (* write out constants *)
404 writeln;
405 writeln('Top cylinder number = ',c:1,'.');
406 writeln('Seek time to move 1 cylinder = ',st1:1, ' milleseconds.');
407 writeln('Seek time to move ',c:1,' cylinders = ',stc:1, ' milleseconds.');
408 writeln('Disk rotation time = ',t:1,' milleseconds.');
409 writeln('Number of observations = ',numobsv:1,'.');
410 writeln(outdata, c:1, ' ', st1:1, ' ', stc:1, ' ', t:1, ' ', numobsv:1);
411 
412 for count := 1 to numarrt do                  (* for each arrival rate *)
413    begin
414    arrate := lowarrt + ((count-1)*incarrt);   (* initialize the arrival rate *)
415    for mnum := 1 to 2 do                      (* for each value of m *)
416       begin
417       case mnum of                            (* initialize the m *)
418          1: m :=  4;
419          2: m := 50;
420          end; (* case *)
421       latency := round((t/2) + (t/m));
422       for algnum := 1 to 2 do                 (* for each algorithm *)
423          begin
424          initialize;                          (* initialize globals *)
425          simulate;                            (* simulate the current algorithm *)
426          getstats;                            (* collect statistics *)
427          printinfo;                           (* print out stats *)
428          end; (* for algnum *)
429       end; (* for mnum *)
430    end; (* for count *)
431 
432 end.