Logo Search packages:      
Sourcecode: u++ version File versions

LOOK.cc

//                              -*- Mode: C++ -*- 
// 
// uC++ Version 5.0.1, Copyright (C) Peter A. Buhr 1994
// 
// LOOK.cc -- Look Disk Scheduling Algorithm
//
// The LOOK disk scheduling algorithm causes the disk arm to sweep
// bidirectionally across the disk surface until there are no more
// requests in that particular direction, servicing all requests in
// its path.
// 
// Author           : Peter A. Buhr
// Created On       : Thu Aug 29 21:46:11 1991
// Last Modified By : Peter A. Buhr
// Last Modified On : Sun Aug  8 08:49:47 2004
// Update Count     : 262
// 

#include <uC++.h>
#include <uIOStream.h>


typedef char Buffer[50];                                                // dummy data buffer

const int NoOfCylinders = 100;
enum IOStatus { IO_COMPLETE, IO_ERROR };

class IORequest {
  public:
      int track;
      int sector;
      Buffer *bufadr;
      IORequest() {}
      IORequest( int track, int sector, Buffer *bufadr ) {
            IORequest::track = track;
            IORequest::sector = sector;
            IORequest::bufadr = bufadr;
      } // IORequest::IORequest
}; // IORequest

class WaitingRequest : public uSeqable {                    // element for a waiting request list
      WaitingRequest( WaitingRequest & );                         // no copy
      WaitingRequest &operator=( WaitingRequest & );        // no assignment
  public:
      uCondition block;
      IOStatus status;
      IORequest req;
      WaitingRequest( IORequest req ) {
            WaitingRequest::req = req;
      }
}; // WaitingRequest

class Elevator : public uSequence<WaitingRequest> {
      int Direction;
      WaitingRequest *Current;

      Elevator( Elevator & );                                           // no copy
      Elevator &operator=( Elevator & );                          // no assignment
  public:
      Elevator() {
            Direction = 1;
      } // Elevator::Elevator

      void orderedInsert( WaitingRequest *np ) {
            WaitingRequest *lp;
            for ( lp = uHead();                                               // insert in ascending order by track number
                   lp != 0 && lp->req.track < np->req.track;
                   lp = uSucc( lp ) );
            if ( uEmpty() ) Current = np;                         // 1st client, so set Current
            uInsertBef( np, lp );
      } // Elevator::orderedInsert

      WaitingRequest *uRemove() {
            WaitingRequest *temp = Current;                             // advance to next waiting client
            Current = Direction ? uSucc( Current ) : uPred( Current );
            uSequence<WaitingRequest>::uRemove( temp );           // remove request

            if ( Current == 0 ) {                                       // reverse direction ?
                  uCout << uAcquire << "Turning" << endl << ::uRelease;
                  Direction = !Direction;
                  Current = Direction ? uHead() : uTail();
            } // if
            return temp;
      } // Elevator::uRemove
}; // Elevator

uTask DiskScheduler;

uTask Disk {
      DiskScheduler &scheduler;
      void main();
  public:
      Disk( DiskScheduler &scheduler ) : scheduler( scheduler ) {
      } // Disk
}; // Disk

uTask DiskScheduler {
      Elevator PendingClients;                                          // ordered list of client requests
      uCondition DiskWaiting;                                           // disk waits here if no work
      WaitingRequest *CurrentRequest;                                   // request being serviced by disk
      Disk disk;                                                              // start the disk
      IORequest req;
      WaitingRequest diskterm;                                          // preallocate disk termination request

      void main();
  public:
      DiskScheduler() : disk( *this ), req( -1, 0, 0 ), diskterm( req ) {
      } // DiskScheduler
      IORequest WorkRequest( IOStatus );
      IOStatus DiskRequest( IORequest & );
}; // DiskScheduler

uTask DiskClient {
      DiskScheduler &scheduler;
      void main();
  public:
      DiskClient( DiskScheduler &scheduler ) : scheduler( scheduler ) {
      } // DiskClient
}; // DiskClient

void Disk::main() {
      IOStatus status;
      IORequest work;

      status = IO_COMPLETE;
      for ( ;; ) {
            work = scheduler.WorkRequest( status );
        if ( work.track == -1 ) break;
            uCout << uAcquire << "Disk main, track:" << work.track << endl << uRelease;
            uYield( 100 );                                                    // pretend to perform an I/O operation
            status = IO_COMPLETE;
      } // for
} // Disk::main

void DiskScheduler::main() {
      uSeqGen<WaitingRequest> gen;                                // declared here because of gcc compiler bug

      CurrentRequest = NULL;                                            // no current request at start
      for ( ;; ) {
            uAccept( ~DiskScheduler ) {                                 // request from system
                  break;
            } uOr uAccept( WorkRequest ) {                              // request from disk
            } uOr uAccept( DiskRequest ) {                              // request from clients
            } // uAccept
      } // for
      
      // two alternatives for terminating scheduling server
#if 0
      for ( ; ! PendingClients.uEmpty(); ) {                      // service pending disk requests before terminating
            uAccept( WorkRequest );
      } // for
#else
      WaitingRequest *client;                                           // cancel pending disk requests before terminating

      for ( gen.uOver(PendingClients); gen >> client; ) {
            PendingClients.uRemove();                                   // remove each client from the list
            client->status = IO_ERROR;                                  // set failure status
            uSignal client->block;                                      // restart client
      } // for
#endif
      // pending client list is now empty
      
      // stop disk
      PendingClients.orderedInsert( &diskterm );                  // insert disk terminate request on list
      
      if ( ! DiskWaiting.empty() ) {                                    // disk free ?
            uSignal DiskWaiting;                                        // wake up disk to deal with termination request
      } else {
            uAccept( WorkRequest );                                     // wait for current disk operation to complete
      } // if
} // DiskScheduler::main

IOStatus DiskScheduler::DiskRequest( IORequest &req ) {
      WaitingRequest np( req );                                         // preallocate waiting list element

      PendingClients.orderedInsert( &np );                        // insert in ascending order by track number
      if ( ! DiskWaiting.empty() ) {                                    // disk free ?
            uSignal DiskWaiting;                                        // reactivate disk
      } // if

      uWait np.block;                                                         // wait until request is serviced

      return np.status;                                           // return status of disk request
} // DiskScheduler::DiskRequest

IORequest DiskScheduler::WorkRequest( IOStatus status ) {
      if ( CurrentRequest != NULL ) {                                   // client waiting for request to complete ?
            CurrentRequest->status = status;                      // set request status
            uSignal CurrentRequest->block;                              // reactivate waiting client
      } // if

      if ( PendingClients.uEmpty() ) {                            // any clients waiting ?
            uWait DiskWaiting;                                                // wait for client to arrive
      } // if

      CurrentRequest = PendingClients.uRemove();                  // remove next client's request
      return CurrentRequest->req;                                       // return work for disk
} // DiskScheduler::WorkRequest

void DiskClient::main() {
      IOStatus status;
      IORequest req( rand() % NoOfCylinders, 0, 0 );
      
      uYield( rand() % 100 );                                           // don't all start at the same time
      uCout << uAcquire << "enter DiskClient main seeking:" << req.track << endl << uRelease;
      status = scheduler.DiskRequest( req );
      uCout << uAcquire << "enter DiskClient main seeked to:" << req.track << endl << uRelease;
} // DiskClient::main

void uMain::main() {
      const int NoOfTests = 20;
      DiskScheduler scheduler;                                          // start the disk scheduler
      DiskClient *p;

      srand( getpid() );                                                      // initialize random number generator

      p = new DiskClient[NoOfTests]( scheduler );                 // start the clients
      delete [] p;                                                            // wait for clients to complete

      uCout << "successful execution" << endl;
} // uMain::main

// Local Variables: //
// tab-width: 4 //
// compile-command: "u++ LOOK.cc" //
// End: //

Generated by  Doxygen 1.6.0   Back to index