-- DiskDriverSharedImpl.mesa (last edited by: Luniewski on: December 10, 1980  3:44 PM)

DIRECTORY
  DiskChannel USING [-- DiskPageNumber, -- IORequestHandle --, Cylinder --],
  DiskChannelBackend USING [GetDrive],
  DiskDriverShared USING [ScheduleHandle];

DiskDriverSharedImpl: PROGRAM
  IMPORTS DiskChannelBackend
  EXPORTS DiskDriverShared SHARES DiskChannel =
  BEGIN

  -- Useful permanent statisitics
  totalNumberOfRequests: LONG CARDINAL ← 0;
  countQueueEmptyWhenRequestArrived: LONG CARDINAL ← 0;
  -- countSequentialRequestsOnSameCylinder: LONG CARDINAL ← 0;
  -- countOtherRequestsOnCurrentCylinder: LONG CARDINAL ← 0;
  -- countRequestsNotOnCurrentCylinder: LONG CARDINAL ← 0;
  countQueueEmptyWhenRequestMade: LONG CARDINAL ← 0;

  GetSchedule: PROCEDURE [req: DiskChannel.IORequestHandle]
    RETURNS [DiskDriverShared.ScheduleHandle] = -- Fancy loophole
    INLINE BEGIN RETURN[LOOPHOLE[DiskChannelBackend.GetDrive[req.channel]]]; END;

  GetNextPendingRequest: PUBLIC PROCEDURE [
    schedule: DiskDriverShared.ScheduleHandle]
    RETURNS [req: DiskChannel.IORequestHandle] =
    -- Pick next request off of queue
    BEGIN
    IF (req ← schedule.first) = NIL THEN
      BEGIN
      countQueueEmptyWhenRequestMade ← countQueueEmptyWhenRequestMade + 1;
      -- IF collectStats THEN RememberRequest[remove, 0];
      RETURN;
      END;
    schedule.first ← req.next;
    -- make sure that previousRequest isn't pointing to something that's been removed
    -- from the queue
    -- IF schedule.first = NIL OR req = schedule.previousRequest THEN
      -- schedule.previousRequest ← NIL;
    -- IF collectStats THEN RememberRequest[remove, req.diskPage];
    END;

  InsertRequest: PUBLIC PROCEDURE [req: DiskChannel.IORequestHandle] =
    -- using a somewhat odd implementation of the elevator algorithm (FIFO NOW)
    BEGIN
    -- InsertBefore: PROCEDURE [
      -- action: {firstLarger, firstSmaller},
      -- startingPlaceForInsertion: LONG POINTER TO DiskChannel.IORequestHandle] =
      -- find the correct place in the queue for the request
      -- INLINE
      -- BEGIN
      -- last: LONG POINTER TO DiskChannel.IORequestHandle ←
      --   startingPlaceForInsertion;
      -- current: DiskChannel.IORequestHandle;
      -- DO
         -- current ← last↑;
         -- IF current = NIL OR req.address.cylinder = current.address.cylinder THEN
           -- { InsertWithinCylinder[last]; RETURN };
         -- IF
           -- (action = firstSmaller AND req.address.cylinder >
             -- current.address.cylinder) OR
           -- (action = firstLarger AND req.address.cylinder <
             -- current.address.cylinder) THEN
           -- { last↑ ← req; req.next ← current; RETURN };
         -- last ← @current.next;
         -- ENDLOOP;
      -- END;

    -- InsertWithinCylinder: PROCEDURE [
      -- startingPlaceForInsertion: LONG POINTER TO DiskChannel.IORequestHandle] =
      -- linear insert into correct position amongst entries on current cylinder
      -- BEGIN
      -- last: LONG POINTER TO DiskChannel.IORequestHandle ←
         -- startingPlaceForInsertion;
      -- current: DiskChannel.IORequestHandle;
      -- DO
         -- current ← last↑;
         -- IF current = NIL OR req.address.cylinder ~= current.address.cylinder OR
           -- req.address.head < current.address.head OR
           -- (req.address.head = current.address.head AND req.address.sector <
             -- current.address.sector) THEN
           -- { last↑ ← req; req.next ← current; RETURN };
         -- last ← @current.next;
         -- ENDLOOP;
      -- END;

    schedule: DiskDriverShared.ScheduleHandle = GetSchedule[req];
    -- currentCylinderOfDrive: DiskChannel.Cylinder = schedule.currentCylinder;
    -- IF collectStats THEN RememberRequest[insert, req.diskPage];
    -- req.next ← NIL;
    -- SELECT TRUE FROM
      -- schedule.first = NIL =>
      -- this case is also caught below, but it's useful to keep this statistic independently
        -- BEGIN
        -- schedule.first ← req;
        -- countQueueEmptyWhenRequestArrived ←
              -- countQueueEmptyWhenRequestArrived+1;
        -- END;
      -- catch the typical case of sequential requests
      -- schedule.previousRequest ~= NIL AND
      -- req.address.cylinder = schedule.previousRequest.address.cylinder AND
      -- req.diskPage = schedule.previousRequest.diskPage + 1 =>
        -- BEGIN
        -- InsertWithinCylinder[@schedule.previousRequest.next];
        -- countSequentialRequestsOnSameCylinder ←
          -- countSequentialRequestsOnSameCylinder+1;
        -- END;
      -- req.address.cylinder = currentCylinderOfDrive =>
      -- this case happens so seldom, it could probably be removed (allowing
      -- InsertWithinCylinder to become an INLINE)
         -- BEGIN
         -- InsertWithinCylinder[@schedule.first];
         -- countOtherRequestsOnCurrentCylinder ←
           -- countOtherRequestsOnCurrentCylinder + 1;
         -- END;
      -- ENDCASE =>
         -- insert before the first queue entry with a smaller (or larger) cylinder value
         -- (merge with entries with equal cylinder value)
         -- BEGIN
         -- InsertBefore[
           -- IF req.address.cylinder > currentCylinderOfDrive THEN firstLarger
           -- ELSE firstSmaller, @schedule.first];
         -- countRequestsNotOnCurrentCylinder ← countRequestsNotOnCurrentCylinder+1;
         -- END;
    -- schedule.previousRequest ← req;
    -- the above, commented out, is the elevator algorithm.  Below is a very simple disk
    -- scheduler that provides first come, first serve service.  This is believed to be
    -- sufficient due to the presence of runs of pages
    prevReq: DiskChannel.IORequestHandle ← NIL;
    req.next ← NIL;
    totalNumberOfRequests ← totalNumberOfRequests+1;
    -- Insert at the end of the queue
    FOR c: DiskChannel.IORequestHandle ← schedule.first, c.next
        WHILE c ~= NIL DO
        prevReq ← c;
        ENDLOOP;
    IF prevReq = NIL THEN
       BEGIN -- empty queue
       countQueueEmptyWhenRequestArrived ← countQueueEmptyWhenRequestArrived+1;
       schedule.first ← req;
       END
    ELSE prevReq.next ← req;
    END;

  PeekNextPendingRequest: PUBLIC PROCEDURE [
    schedule: DiskDriverShared.ScheduleHandle]
    RETURNS [req: DiskChannel.IORequestHandle] =
    -- Pick next request without removing it from queue
    BEGIN RETURN[schedule.first] END;

  -- Temporary statistics gathering stuff: commented out

  -- collectStats: BOOLEAN = TRUE;
  -- RequestDirection: TYPE = {insert, remove};
  -- maxStatsRequests: CARDINAL = 64;
  -- currentIndex: CARDINAL ← 0;
  -- totalReqs: CARDINAL ← 0;
  -- pgs: ARRAY [0..maxStatsRequests) OF DiskChannel.DiskPageNumber;
  -- dirs: ARRAY [0..maxStatsRequests) OF RequestDirection;
  -- RememberRequest: PROCEDURE [
    -- dir: RequestDirection, pNum: DiskChannel.DiskPageNumber] =
    -- BEGIN
    -- IF currentIndex >= maxStatsRequests THEN currentIndex ← 0;
    -- pgs[currentIndex] ← pNum;
    -- dirs[currentIndex] ← dir;
    -- currentIndex ← currentIndex + 1;
    -- totalReqs ← totalReqs + 1;
    -- END;

  END.
LOG
Time: January 17, 1979  4:40 PM   By: Horsley   Action: Create file
Time: March 13, 1979  6:28 PM   By: Horsley   Action: RememberRequest no longer remembers physical address
Time: July 24, 1979  2:23 PM   By: Gobbel   Action: Change format of IORequest
Time: August 17, 1979  9:39 AM   By: Redell   Action: Add USINGs; remove use of old Temporary interface
Time: February 1, 1980  9:22 AM   By: McJones   Action: Changes to DiskChannel, DiskChannelBackend, DiskDriverShared
Time: December 10, 1980  3:44 PM   By: Luniewski   Action: Comment out elevator algorithm and statistics gathering code (except for simple counts).