Programmer 7500/MAX_PROGRAMMERS.iso/PROGRAMS/UTILS/DSKCACHE/EVALCACH.ZIP/EVAL.PAS

Pascal/Delphi Source File | 1989-10-26 | 21.1 KB | 719 lines

{
**************************************************************************
EVAL.PAS -- Disk Cache Strategy Performance Evaluator
**************************************************************************

This program estimates the effectiveness of disk caching strategies using
a log of up to 8196 actual disk transactions from your first physical hard
disk. The TSR program SNOOP.COM maintains the log in memory.

This version of the program compares the performance of a simple write-
through cache to the performance you'd get from no cache at all. It bases
its speed estimates on hard disk characteristics you enter, rather than on
the actual characteristics of your machine, so you can see how drive
characteristics affect both system and cache performance. You can test your
own cache strategies by defining objects of the type CacheStrategy. You can
also observe the performance effects of cache size. As a simple experiment,
try reducing the cache size to 64K or 128K and press G to simulate the
results. You should notice a dramatic drop in cache performance.

This program is Copyright (C) 1989 by L. Brett Glass. It may be freely
redistributed for non-commercial purposes only. It may not be made part of any
hardware or software product without the express written consent of the
copyright owner. This program is supplied on an "as-is" basis. The author
assumes no responsibility for its correctness or its fitness for a given
purpose, nor for consequential damages which may arise from its use.
You may contact the author at one of the following electronic mail addresses:

Usenet: apple!well!rogue
ARPANET: well![e-mail]
BIX: glass
CompuServe: [72267,3673] (Also reachable from MCIMail)

**************************************************************************
}

program Eval;
{$A-} {No word alignment}

uses DOS, Snoop, CRT, CharScrn, Boxes, HBars, Controls;

{ The typed constant below contains information on how to draw the box
  that greets the user when the program starts up. }

const
  bigBox : Box = (x : 1; y : 1;
                  color : WHITE;
                  dirty : TRUE;
                  title : 'Disk Cache Strategy Performance Evaluator --'+
                          ' Copyright L. Brett Glass 1989';
                  width : 80; height : 24;
                  boxType : THINBOX;
                  hDividers : [6,11,21];
                  vDividers : []);

const
  MAXBARWIDTH = SCREENWIDTH - 6; {Maximum width of bar graphs}

{ Text controls for the user interface. These are simplistic controls
  that can be selected with a single keystroke and can change internal
  variables in a safe manner. See the unit Controls for the code that
  runs them. }

  adjSeek : WordCtrl =
                     (x : 3; y : 14;
                      color : WHITE;
                      dirty : TRUE;
                      title: 'T)rack-to-track seek (adjacent): ';
                      next : NIL;
                      value : 5;
                      fieldSize : 2;
                      max : 20;
                      min : 1;
                      increment : 1;
                      bigIncrement: 10;
                      unitStr : 'ms');

  avgSeek : WordCtrl =
                      (x : 3; y : 15;
                       color : WHITE;
                       dirty : TRUE;
                       title: 'A)verage seek time (all tracks): ';
                       next : NIL;
                       value : 40;
                       fieldSize : 3;
                       max : 120;
                       min : 1;
                       increment : 1;
                       bigIncrement : 10;
                       unitStr : 'ms');

   numCyl : WordCtrl =
                      (x : 3; y : 16;
                       color : WHITE;
                       dirty : TRUE;
                       title : 'N)umber of cylinders: ';
                       next : NIL;
                       value : 615;
                       fieldSize : 4;
                       max : 2048;
                       min : 128;
                       increment : 1;
                       bigincrement : 10;
                       unitStr : '');

   rotSpeed : WordCtrl =
                      (x : 3; y : 17;
                       color : WHITE;
                       dirty : TRUE;
                       title : 'R)otational speed: ';
                       next : NIL;
                       value : 3600;
                       fieldSize : 4;
                       max : 8000;
                       min : 1200;
                       increment : 100;
                       bigIncrement : 1000;
                       unitStr : 'RPM');

   numHeads : WordCtrl =
                      (x : 3; y : 18;
                       color : WHITE;
                       dirty : TRUE;
                       title : 'D)isk heads: ';
                       next : NIL;
                       value : 4;
                       fieldSize : 2;
                       max : 32;
                       min : 1;
                       increment : 1;
                       bigIncrement : 10;
                       unitStr : '');

   secsPerTrack : WordCtrl =
                      (x : 3; y : 19;
                       color : WHITE;
                       dirty : TRUE;
                       title : 'S)ectors per track: ';
                       next : NIL;
                       value : 17;
                       fieldSize : 2;
                       max : 99;
                       min : 1;
                       increment : 1;
                       bigIncrement : 10;
                       unitStr : '');

   interleave : WordCtrl =
                      (x : 3; y : 20;
                       color : WHITE;
                       dirty : TRUE;
                       title : 'I)nterleave factor: ';
                       next : NIL;
                       value : 1;
                       fieldSize : 2;
                       max : 99;
                       min : 1;
                       increment : 1;
                       bigIncrement : 10;
                       unitStr : ': 1');

   cacheSize : WordCtrl =
                      (x : 45; y : 14;
                       color : WHITE;
                       dirty : TRUE;
                       title : 'C)ache size : ';
                       next : NIL;
                       value : 1024;
                       fieldSize : 4;
                       max : 4096;
                       min : 64;
                       increment : 64;
                       bigIncrement : 256;
                       unitStr : 'Kbytes');

   help : ButtonCtrl =
                      (x : 45; y : 18;
                       color : WHITE;
                       dirty : TRUE;
                       title : 'P)rogram information';
                       next : NIL);

   go : ButtonCtrl =
                      (x : 45; y : 19;
                       color : WHITE;
                       dirty : TRUE;
                       title : 'G)o (recalculate estimates)';
                       next : NIL);

   quit : ButtonCtrl =
                      (x : 45; y : 20;
                       color : WHITE;
                       dirty : TRUE;
                       title : 'Q)uit program';
                       next : NIL);


{ Variables used in the estimation process. Some of these are Real
  copies of Word variables that eliminate the need for repeated
  conversions. }

var
  elapsedTime : Real;
  currCyl : Word;
  avgLatency, maxLatency, seekConst, realNumCyl : Real;
  realAdjSeek, realInterleaveDelay, realSecsPerTrack : Real;
  maxTime : Real;

procedure PrepareFactors;
  { This routine prepares factors for use in the estimation process.
    In some cases, this amounts to floating-point conversion; in
    others, there's a small amount of arithmetic to be done.}
  begin {PrepareFactors}
  avgLatency := 30000.0/rotSpeed.value;
  maxLatency := 60000.0/rotSpeed.value;
  seekConst := avgSeek.value - adjSeek.value;
  realNumCyl := numCyl.value;
  realAdjSeek := adjSeek.value;
  realInterleaveDelay := Pred(interleave.value);
  realSecsPerTrack := secsPerTrack.value;
  end;  {PrepareFactors}

procedure SimulateSeek(endCyl : Word);
  { Simulate a seek from "currCyl" to "endCyl". "currCyl" is a global
    that the simulator uses to keep track of the current head position. }
  var
    distance : LongInt;
  begin {SimulateSeek}
  {To estimate seek time, start with adjacent track time. Then add
   a fraction of the average time such that a seek crossing 1/3 of
   the tracks takes the average time.}
  distance := Abs(LongInt(endCyl) - currCyl);
  if distance > 0 then
    elapsedTime := elapsedTime + realAdjSeek +
                   (distance * 3.0 * seekConst) / realNumCyl;
  currCyl := endCyl
  end;  {SimulateSeek}

procedure SimulateReadWrite(cyl,head,sec,numSec : Word);
  { Simulate a read or a write operation. A large portion of the overhead
    of such operations is caused by rotational latency. }
  var
    currSec, currHead, i : Word;
  begin {SimulateReadWrite}
  {To estimate read/write time, assume a latency of 1/2 rotation. Then
   add the time to write numSec sectors. If a seek is required for a
   multiple-sector operation, add in the time for that as well.}
  if currCyl <> cyl then {Get to cylinder}
    SimulateSeek(cyl);
  elapsedTime := elapsedTime + avgLatency; {Latency}
  currSec := sec;
  currHead := head;
  i := 1;
  repeat
    elapsedTime := elapsedTime + maxLatency/realsecsPerTrack *
                                                         realInterleaveDelay;
    if i = numSec then
      Exit;
    Inc(i);
    Inc(currSec);
    if currSec > secsPerTrack.value then {Move from head to head, cyl to cyl}
      begin
      currSec := 1;
      Inc(currHead);
      if currHead > numHeads.value then
        begin
        currHead := 1;
        SimulateSeek(Succ(currCyl));
        end
      end
    until FALSE;
  end;  {SimulateReadWrite}



{ The object type CacheStrategy is defined here. Each strategy can use
  the snooper's data tables to estimate total elapsed time for disk
  operations, and can prepare to display a titled bar graph showing
  the result. An object of the type CacheStrategy uses a "null" strategy
  -- that is, no caching actually occurs. Other caching strategies should
  be defined as decendents of this type. }

type
  CacheStrategyPtr = ^CacheStrategy;
  CacheStrategy = object (HBar)
    time : Real;
    next : CacheStrategyPtr;
    procedure Estimate(var s : SnoopObject); virtual;
    procedure PrepareBarDisplay;
    end;

procedure CacheStrategy.PrepareBarDisplay;
  var
    sec : String[12];
  begin {CacheStrategy.PrepareBarDisplay}
  size := Round((time/maxTime)* MAXBARWIDTH * 2);
  Delete(title,Pos('=',title) + 2, 255);
  Str(time/1000.0:0:2,sec);
  title := title + sec + ' sec';
  end;  {CacheStrategy.PrepareBarDisplay}

procedure CacheStrategy.Estimate(var s : SnoopObject);
  var
    t : Transaction;
  begin {CacheStrategy.Estimate}
  PrepareFactors;
  elapsedTime := 0.0;
  currCyl := 0;
  if s.GetFirstTransaction(t) then
    repeat
      with t do
        SimulateReadWrite(cylNum,headNum,secNum,sectors);
      until not s.GetNextTransaction(t);
  time := elapsedTime;
  end;  {CacheStrategy.Estimate}

{ An object of type WriteThroughCache implements a simple write-through
  cache. The caching strategy used in this implementation is designed
  to be straightforward, not optimal. A multi-sector read that includes
  even one uncached sector is treated as a complete miss (as it is,
  ironically, in some commercial disk cache programs. }

type
  WriteThroughCache = object (CacheStrategy)
    procedure Estimate(var s : SnoopObject); virtual;
    end;
  LRUCacheRecPtr = ^LRUCacheRec;
  LRUCacheRec = record
    older,younger : LRUCacheRecPtr;
    nextHash,prevHash : LRUCacheRecPtr;
    head : Byte;
    sector : Byte;
    cylinder : Byte;
    end;

{ The write-through cache is fully associative and uses a true LRU
  algorithm. Records representing cache data are maintained as a linked
  list from "youngest" to "oldest" -- each sector is also indexed (via
  a simple hashing scheme) to make it easy to determine that it's in the
  cache. }


const
  youngestCacheRec : LRUCacheRecPtr = NIL;
  oldestCacheRec : LRUCacheRecPtr = NIL;
  numCacheRecs : Word = 0;
  maxCacheRecs : Word = 256;

var
  lruHashTable : array [0..2047] of LRUCacheRecPtr;

function HashFunction(hd,cyl,sec : Word) : Word;
  begin {HashFunction}
  HashFunction := (sec + hd shl 4 + cyl shl 6) and 2047
  end;  {HashFunction}

function FindCacheRecord(hd,cyl,sec : Word) : LRUCacheRecPtr;
  var
    rec : LRUCacheRecPtr;
    hash : Word;
  begin {FindCacheRecord}
  {First search hash table for existing data}
  hash := HashFunction(hd,cyl,sec);
  rec := lruHashTable[hash];
  {Statement below uses short-circuit Booleans} {$B-}
  while (rec <> NIL) and ((rec^.head <> hd) or
                          (rec^.cylinder <> cyl) or
                          (rec^.sector <> sec)) do
    rec := rec^.nextHash;
  FindCacheRecord := rec;
  end;  {FindCacheRecord}

procedure DumpCache; {For debugging; not used otherwise}
  var
    rec : LRUCacheRecPtr;
    hash : Word;
    bin : Word;
  begin {DumpCache}
  Writeln;
  Writeln('Cache dump:');
  for bin := 0 to 2047 do
    begin
    rec := lruHashTable[bin];
    Writeln('BIN #',bin,':');
    while (rec <> NIL) do
      begin
      Writeln(' head: ',rec^.head,
              ' cylinder: ',rec^.cylinder,
              ' sector: ',rec^.sector);

      rec := rec^.nextHash
      end
    end
  end;  {DumpCache}

procedure ClearCache;
  var
    rec1,rec2 : LRUCacheRecPtr;
  begin {ClearCache}
  {Dispose of all storage in the cache, if any}
  rec1 := youngestCacheRec;
  while rec1 <> NIL do
    begin
    rec2 := rec1^.older;
    Dispose(rec1);
    rec1 := rec2
    end;
  {Clear the hash table}
  FillChar(lruHashTable,SizeOf(lruHashTable),0);
  numCacheRecs := 0;
  youngestCacheRec := NIL;
  oldestCacheRec := NIL
  end;  {ClearCache}

procedure RecordToFront(rec : LRUCacheRecPtr);
  begin {RecordToFront}
  with rec^ do
    begin
    if younger <> NIL then
      begin
      if rec = oldestCacheRec then
        oldestCacheRec := younger;
      younger^.older := older;
      if older <> NIL then
        older^.younger := younger;
      younger := NIL;
      older := youngestCacheRec;
      youngestCacheRec := rec
      end
    end
  end;  {RecordToFront}

function UnlinkOldest : LRUCacheRecPtr;
  var
    hash : Word;
  begin {UnlinkOldest}
  UnlinkOldest := oldestCacheRec;
  with oldestCacheRec^ do
    begin
    {Remove from end of chronological chain}
    younger^.older := NIL;
    {Remove from hash "bucket"}
    if prevHash <> NIL then
      prevHash^.nextHash := nextHash
    else
      begin
      hash := HashFunction(head,cylinder,sector);
      lruHashTable[hash] := nextHash
      end;
    if nextHash <> NIL then
      nextHash^.prevHash := prevHash
    end;
  oldestCacheRec := oldestCacheRec^.younger
  end;  {UnlinkOldest}

procedure AddNewRecord(hd,cyl,sec : Word);
  var
    rec : LRUCacheRecPtr;
    hash : Word;
  begin {AddNewRecord}
  if numCacheRecs < maxCacheRecs then
    begin
    New(rec);
    Inc(numCacheRecs)
    end
  else
    rec := UnlinkOldest;
  {Add to the hash table}
  hash := HashFunction(hd,cyl,sec);
  with rec^ do
    begin
    head := hd;
    sector := sec;
    cylinder := cyl;
    nextHash := lruHashTable[hash];
    lruHashTable[hash] := rec;
    prevHash := NIL;
    if nextHash <> NIL then
      nextHash^.prevHash := rec;
    {Also chain onto front of list}
    older := youngestCacheRec;
    if youngestCacheRec <> NIL then
      youngestCacheRec^.younger := rec
    else
      oldestCacheRec := rec;
    youngestCacheRec := rec;
    younger := NIL
    end;
  end;  {AddNewRecord}


procedure WriteThroughCache.Estimate(var s : SnoopObject);
  var
    max, count, hash : Word;
    rec : LRUCacheRecPtr;
    sec, hd, cyl : Word;
    t : Transaction;
    i : Word;
    missFlag : Boolean;
  begin {WriteThroughCache.Estimate}
  PrepareFactors;
  maxCacheRecs := cacheSize.value * 2;
  ClearCache;
  elapsedTime := 0.0;
  currCyl := 0;
  if s.GetFirstTransaction(t) then
    repeat
      with t do
        begin
        missFlag := FALSE;
        hd := headNum;
        cyl := cylNum;
        sec := secNum;
        for i := 1 to sectors do
          begin
          rec := FindCacheRecord(hd,cyl,sec);
          if rec <> NIL then {Found the record. Move it to front of list.}
            RecordToFront(rec)
          else
            begin
            AddNewRecord(hd,cyl,sec);
            missFlag := TRUE;
            end;
          Inc(sec);
          if sec > secsPerTrack.value then
            begin
            sec := 1;
            Inc(hd);
            if hd > numHeads.value then
              begin
              hd := 1;
              Inc(cyl)
              end
            end
          end;
        {Access disk if any sector in a group missed, or on write}
        if missFlag or (requestType = 3) then
          SimulateReadWrite(cylNum,headNum,secNum,sectors);
        end
      until not s.GetNextTransaction(t);
  time := elapsedTime;
  end;  {WriteThroughCache.Estimate}

{ Here are the objects that are used to represent the cache strategies.
  They contain graphic and textual information that tells them how to
  display their own results when "asked." }

const
  none : CacheStrategy =
    (x : 3; y : 3;
     color : WHITE;
     dirty : TRUE;
     title : 'Estimated time without cache = ';
     size : 15;
     maxWidth : MAXBARWIDTH;
     time : 0.0);

  writeThrough : WriteThroughCache =
    (x : 3; y : 8;
     color : WHITE;
     dirty : TRUE;
     title : 'Estimated time with simple write-through cache = ';
     size : 15;
     maxWidth : MAXBARWIDTH;
     time : 0.0);

var
  strategy : CacheStrategyPtr; { This pointer is used to scan the list of
                                 caching strategies and use each in turn. }

{ Display, help, and exit routines follow }

procedure Display(calc : Boolean);
  { Display the bounding box, bar graphs, etc. }
  begin {Display}
  {Prepare the screen}

  ClrScr;
  SetCursorMode(CURSOROFF);
  LowVideo;
  bigBox.color := TextAttr;
  bigBox.Draw;

  GoToXY(20,12);
  HighVideo;
  Write('-- Disk Drive and Cache Parameters --');

  DrawChain(@adjSeek);

  if calc then
    begin
    HighVideo;
    Inc(TextAttr,BLINK);
    GoToXY(35,8);
    Write('Working....');
    Dec(TextAttr,BLINK);

    {Do the calculations}

    strategy := @none;
    maxTime := 0;
    repeat
      with strategy^ do
        begin
        Estimate(snooper);
        if time > maxTime then
          maxTime := time
        end;
      strategy := strategy^.next
      until strategy = NIL;

    FillBox(35,8,11,1,' '); {Clear away text}
    end;

  {Scale and show the bar graphs}

  strategy := @none;
  repeat
    with strategy^ do
      begin
      PrepareBarDisplay;
      Draw
      end;
    strategy := strategy^.next
    until strategy = NIL;
  end;  {Display}

{$F+}
procedure Helper;
  { Display the help file upon request }
  var
    f : Text;
    s : String;
  begin {Helper}
  {$I-}
  LowVideo;
  ClrScr;
  Assign(f,'EVAL.HLP');
  Reset(f);
  if IOResult <> 0 then
    Writeln('Help file EVAL.HLP not found.')
  else
    while (not Eof(f)) and (IOResult = 0) do
      begin
      Readln(f,s);
      Writeln(s)
      end;
  Close(f);
  if IOResult <> 0 then; {Ignore errors}
  Writeln;
  HighVideo;
  Writeln('Press a key to return to the main program.');
  if ReadKey = #0 then {Wait for a key. Absorb second code if special.}
    if ReadKey = #0 then;
  {$I+}
  Display(FALSE)
  end;  {Helper}

procedure Recalc;
  { Recalculate estimates and display them. Triggered by G)o command. }
  begin {Recalc}
  Display(TRUE)
  end;  {Recalc}

procedure Finis;
  { End the program and leave the screen in a known state. }
  begin {Finis}
  ClrScr;
  SetCursorMode(cursorOn);
  Halt;
  end;  {Finis}

{$F-}

begin

{Link together the text controls}

adjSeek.next := @avgSeek;
avgSeek.next := @numCyl;
numCyl.next := @rotSpeed;
rotSpeed.next := @secsPerTrack;
secsPerTrack.next := @numHeads;
numHeads.next := @interleave;
interleave.next := @cacheSize;
cacheSize.next := @help;
help.next := @go;
go.next := @quit;

{Bind procedures to the button controls}

help.proc := Helper;
go.proc := Recalc;
quit.proc := Finis;

{Set up help lines to appear on lines 23, 24}

firstHelpLine := 22;

{Link the strategies we'll try into a list}

none.next := @writeThrough;
writeThrough.next := NIL;

{Do the initial display}

Display(TRUE);

{Check each character as it comes in to see if it's a command.
 Each control object is responsible for recognizing the keys
 it responds to, and forwarding the ones it doesn't use on to
 the remaining ones.}


repeat
  adjSeek.CheckChar(UpCase(readKey))
  until FALSE;

end.