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

Paging.cc

//                              -*- Mode: C++ -*- 
// 
// uC++ Version 5.0.1, Copyright (C) Peter A. Buhr 1994
// 
// Paging.cc -- 
// 
// Author           : Peter Buhr
// Created On       : Wed May 11 17:03:26 1994
// Last Modified By : Peter A. Buhr
// Last Modified On : Tue Jul 22 08:37:45 2003
// Update Count     : 7
// 

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

#define Kb *1024

unsigned int uDefaultStackSize() {
    return 64 Kb;
} // uDefaultStackSize

int searchUp( int Array[], int Start, int End,  int Key ) { // linear search forward through a section of an array
    int i;
    
    for ( i = Start;; i += 1 ) {
      if ( i >= End ) break;
      if ( Array[i] == Key ) break;
    } // for
    return i;
} // searchUp

int searchDown( int Array[], int Start, int End, int Key ) { // linear search backward through a section of an array
    int i;
    
    for ( i = Start;; i -= 1 ) {
      if ( i < End ) break;
      if ( Array[i] == Key ) break;
    } // for
    return i;
} // searchDown

#define MaxPageRequests 100

uIStream *infile = &uCin;
uOStream *outfile = &uCout;

uCoroutine Replacement {
  protected:
    int *Memory, MemorySize, *PageRequests, NoOfPageRequests;
    int CurrRequest, repage;
  public:
    int replace( int CurrRequest ) {
      Replacement::CurrRequest = CurrRequest;
      uResume;
      return repage;
    } // replace
}; // Replacement

uCoroutine Optimal : public Replacement {
  protected:
    void main() {
      int Max, i, posn;

      for ( ; CurrRequest != -1; ) {
          Max = -1;
          for ( i = 0; i < MemorySize; i += 1 ) {     // for each page in the memory
            posn = searchUp( PageRequests, CurrRequest + 1, NoOfPageRequests, Memory[i] ); // look into the future
            if ( posn > Max ) {
                Max = posn;
                repage = i;
            } // if
          } // for
          uSuspend;
      } // for
    } // Optimal::main
  public:
    Optimal( int Memory[], int MemorySize, int PageRequests[], int NoOfPageRequests ) {
      Optimal::Memory = Memory;
      Optimal::MemorySize = MemorySize;
      Optimal::PageRequests = PageRequests;
      Optimal::NoOfPageRequests = NoOfPageRequests;
    } // Optimal::Optimal
}; // Optimal

uCoroutine FIFO : public Replacement {
  protected:
    void main() {
      repage = -1;
    
      for ( ; CurrRequest != -1; ) {
          repage = ( repage + 1 ) % MemorySize;
          uSuspend;
      } // for
    } // FIFO::main
  public:
    FIFO( int Memory[], int MemorySize, int PageRequests[], int NoOfPageRequests ) {
      FIFO::Memory = Memory;
      FIFO::MemorySize = MemorySize;
      FIFO::PageRequests = PageRequests;
      FIFO::NoOfPageRequests = NoOfPageRequests;
    } // FIFO::FIFO
}; // FIFO

uCoroutine LRU : public Replacement {
  protected:
    void main() {
      int Min, i, posn;
      
      for ( ; CurrRequest != -1; ) {
          Min = CurrRequest;
          for ( i = 0; i < MemorySize; i += 1 ) {     // for each page in the memory
            posn = searchDown(PageRequests, CurrRequest - 1, 0, Memory[i]); // look into the past
            if ( posn < Min ) {
                Min = posn;
                repage = i;
            } // if
          } // for
          uSuspend;
      } // for
    } // LRU::main
  public:
    LRU( int Memory[], int MemorySize, int PageRequests[], int NoOfPageRequests ) {
      LRU::Memory = Memory;
      LRU::MemorySize = MemorySize;
      LRU::PageRequests = PageRequests;
      LRU::NoOfPageRequests = NoOfPageRequests;
    } // LRU::LRU
}; // LRU

uCoroutine Pager {
    int *Memory, MemorySize, *PageRequests, NoOfPageRequests;
    Replacement *replacement;
    int pagefaults;

    void main() {
      int RepPage, PagesUsed;
      int Results[MemorySize+1][MaxPageRequests];
      int i, j;

      for (i = 0; i < MemorySize; i += 1) Memory[i] = -1; // initialize memory to null
      PagesUsed = 0;
    
      for ( i = 0; i < NoOfPageRequests; i += 1 ) {   // for each page request
          if ( searchUp( Memory, 0, PagesUsed, PageRequests[i] ) == PagesUsed ) { // page not in memory ?
            if ( PagesUsed == MemorySize ) {    // are all pages being used ?
                RepPage = replacement->replace( i );
            } else {
                RepPage = PagesUsed;
                PagesUsed += 1;
            } // if
            Memory[RepPage] = PageRequests[i];  // insert page into memory
            Results[MemorySize][i] = -1;
          } else {
            Results[MemorySize][i] = 0;
          } // if
          
          for (j = 0; j < MemorySize; j += 1) { // store memory over time
            Results[j][i] = Memory[j];
          } // for
      } // for
      i = -1;
      replacement->replace( i );                // terminate replacement scheme

      for ( i = 0; i < MemorySize; i += 1 ) {
          for ( j = 0; j < NoOfPageRequests; j += 1 ) {
            if (Results[i][j] != -1) {
                *outfile << Results[i][j] << "|";
            } else {
                *outfile << " |";
            } // if
          } // for
          *outfile << endl;
      } // for

      pagefaults = 0;
      for ( i = 0; i < NoOfPageRequests; i += 1 ) {
          if ( Results[MemorySize][i] == -1 ) {
            *outfile << "*|";
            pagefaults += 1;
          } else {
            *outfile << " |";
          }
      } // for
      *outfile << endl;

      for ( i = 0; i < NoOfPageRequests; i += 1 ) {
          *outfile << PageRequests[i] << "|";
      } // for
      *outfile << endl;
    } // Pager::main
  public:
    Pager( int Memory[], int MemorySize, int PageRequests[], int NoOfPageRequests, Replacement *replacement ) {
      Pager::Memory = Memory;
      Pager::MemorySize = MemorySize;
      Pager::PageRequests = PageRequests;
      Pager::NoOfPageRequests = NoOfPageRequests;
      Pager::replacement = replacement;
    } // Pager::Pager

    int faults() {
      uResume;
      return pagefaults;
    } // Pager::faults
}; // Pager

void uMain::main() {
    switch ( argc ) {                           // deal with input and output file parameters
      case 3:
      outfile = new uOFStream( argv[2] ); 
      if ( outfile->fail() ) {
          uCerr << "Open error, outfile file: " << argv[2] << endl;
          uExit( -1 );
      } // if
      case 2:
      infile = new uIFStream( argv[1] );        // 1st file is input file
      if ( infile->fail() ) {
          uCerr << "Open error, infile file: " << argv[1] << endl;
          uExit( -1 );
      } // if
      case 1:
      break;
      default:
      uCerr << "Usage: " << argv[0] << " [infile-file [outfile-file]]" << endl;
      uExit( -1 );
    } // switch

    int NoValues;
    int MemorySize;
    int PageRequests[MaxPageRequests], NoOfPageRequests;
    int i, faults;

    for ( ;; ) {
      for ( NoOfPageRequests = 0;; NoOfPageRequests += 1 ) { // read page requests
          *infile >> PageRequests[NoOfPageRequests];
      if ( infile->eof() ) goto Eof;
        if ( PageRequests[NoOfPageRequests] == -1 ) break;
      } // for

      *outfile << "For page references: ";
      for ( i = 0; i < NoOfPageRequests; i += 1 ) {   // print page requests
          *outfile << PageRequests[i] << "  ";
      } // for
      *outfile << endl << endl; 
      
      for ( i = 0;; i += 1 ) {
          *infile >> MemorySize;
      if ( infile->eof() ) goto Eof;
        if ( MemorySize == -1 ) break;
          *outfile << "and a " << MemorySize << " page memory" << endl;

          int Memory[MemorySize];
          {
            Optimal optimal( Memory, MemorySize, PageRequests, NoOfPageRequests );
            Pager pager( Memory, MemorySize, PageRequests, NoOfPageRequests, &optimal );
            faults = pager.faults();
            *outfile << "Optimal paging strategy produced " << faults << " page faults" << endl << endl;
          }
          {
            FIFO fifo( Memory, MemorySize, PageRequests, NoOfPageRequests );
            Pager pager( Memory, MemorySize, PageRequests, NoOfPageRequests, &fifo );
            faults = pager.faults();
            *outfile << "FIFO paging strategy produced " << faults << " page faults" << endl << endl;
          }
          {
            LRU lru( Memory, MemorySize, PageRequests, NoOfPageRequests );
            Pager pager( Memory, MemorySize, PageRequests, NoOfPageRequests, &lru );
            faults = pager.faults();
            *outfile << "LRU paging strategy produced " << faults << " page faults" << endl << endl;
          }
          *outfile << endl;
      } // for
    } // for
  Eof:
    *outfile << "successful completion" << endl;
    if ( infile != &uCin ) {
      delete infile;          // close files
    }
    if ( outfile != &uCout ) delete outfile;
} // uMain::main
                   
// Local Variables: //
// compile-command: "u++ Paging.cc" //
// End: //

Generated by  Doxygen 1.6.0   Back to index