memmanager.cpp

LINUX 下NACHOS 系统的页面调度算法的实现

#include <errno.h>

#include "memmanager.h"
#include "translate.h"
#include "machine.h"
#include "system.h"
#include "synch.h"
#include "syscall.h"
#include "list.h"

///////////////////////////////////////////////////////////////////
//     CoreFreeMap: A frame is said to be free only if it does not belong
//     the page buffer, and does not belong to any process.
//
//     CoreOwners: If a frame has the contents of some process's page
//     then its entry in core owners points to the corresponding page
//     table entry.
///////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////
// Constructor: set the policy to use, allocate resources, etc.
//////////////////////////////////////////////////////////////////////
MemManager::MemManager (int policy_in, int hbits_in)
{
  // WARNING: coreFreeMap (and like wise swapFreeMap) bits are CLEAR 
  // when free, not set when free; 
  coreFreeMap = new BitMap (NumPhysPages);
  coreOwners = new TranslationEntry *[NumPhysPages];

  swapFreeMap = new BitMap (NumSwapPages);
  swapValidMap = new BitMap (NumSwapPages);
  swapOwners = new TranslationEntry *[NumSwapPages];

  for(int physFrame = 0; physFrame < NumPhysPages; physFrame++)
  {
    coreOwners[physFrame] = (TranslationEntry *)NULL;
  }

  for(int swapFrame = 0; swapFrame < NumSwapPages; swapFrame++)
  {
    swapOwners[swapFrame] = (TranslationEntry *)NULL;
  }

  mutex = new Semaphore("mutex for memory manager data structures", 1);

  // nachos.bs is the Nachos backing store
  ASSERT (fileSystem->Create("nachos.bs", 0)); // must be able to create...
  swapfile = fileSystem->Open("nachos.bs");
  ASSERT (swapfile != NULL); // ...and open the swapfile

  // initialize these to null for algorithms that dont use them
  hTimer = NULL;
  history = NULL;

  // sets number of bits used for aging
  hbits = hbits_in;

  //sets replacement policy
  switch (policy_in)
  {
  case 1: // 4.4.2 - NRU
    policy = PAGEREPL_NRU;
    hTimer = new Timer (PageTimer, 0, false);
    break;
  
  case 2: // 4.4.3 - FIFO
    policy = PAGEREPL_FIFO;
    fifoList = new List<int*>();
    break;
  
  case 3: // 4.4.4 - SC
    policy = PAGEREPL_SC;
    fifoList = new List<int*>();
    break;
  
  case 4: // 4.4.5 - CLOCK
    policy = PAGEREPL_CLOCK;
    clock_hand = 0; // initially consider page 0
    break;
  
  case 5: // 4.4.6 - WS
    policy = PAGEREPL_WS;
    break;
  
  case 6: // 4.4.7 - Aging
    ASSERT(hbits > 0);
    policy = PAGEREPL_AGING;
    hTimer = new Timer (PageTimer, 0, false);
    history = new unsigned int[NumPhysPages];
    memset (history, 0, sizeof (int) * NumPhysPages);
    bitmask = (1 << hbits) - 1;
    break;
  
  default:
    ASSERT(false);
    break;
  } // end switch

  return;
}

//////////////////////////////////////////////////////////////////////
// Destructor: free all the resource used by MemManager
//////////////////////////////////////////////////////////////////////
MemManager::~MemManager ()
{
  DEBUG ('a', "MemManager destroyed with %d free pages\n", memAvail ());

  delete coreFreeMap;
  delete swapFreeMap;
  delete[] coreOwners;
  delete[] swapOwners;
  delete swapValidMap;
  delete swapfile; // closes the swapfile
  
  // remove the actual swapfile
  fileSystem->Remove ("nachos.bs"); // .bs means backing store

  switch(policy)
  {
  case PAGEREPL_AGING: // 4.4.7 - AGING
    delete[] history;
  case PAGEREPL_NRU: // 4.4.2 - NRU
    delete hTimer;
    hTimer = NULL;
    break;

  case PAGEREPL_FIFO: // 4.4.3 - FIFO
  case PAGEREPL_SC:   // 4.4.4 - SC
    int *temp;
    while ((temp = (int *)fifoList->Remove())!=NULL)
    {
      delete temp;
    }
    delete fifoList;
    break;

  case PAGEREPL_CLOCK: // 4.4.5 - clock
  case PAGEREPL_WS: // 4.4.8 - WS
  default:
    break;
  }
}


///////////////////////////////////////////////////////////////////
// Total memory in pages (includes swap pages)
///////////////////////////////////////////////////////////////////
unsigned int MemManager::memAvail ()
{
  return (coreFreeMap->NumClear () + swapFreeMap->NumClear ());
}


//////////////////////////////////////////////////////////////////////
// This will be invoked in AddrSpace destructore by a dying process.
// It cleans up all of the pages belonging to a process (both physical
// and virtual).
//////////////////////////////////////////////////////////////////////
void MemManager::clear (TranslationEntry * pageTable, int numPages)
{
  int swapFrame;

  for (int i = 0; i < numPages; i++)
  {
    if (pageTable[i].legal)
    {
      if (pageTable[i].valid)
      {
        // Free physical frames
        coreFreeMap->Clear (pageTable[i].physicalPage);
        coreOwners[pageTable[i].physicalPage] = (TranslationEntry *) NULL;
      }
      else if ((swapFrame = swapSearch (&pageTable[i])) != -1)
      {
        // Free swap frames.
        swapFreeMap->Clear (swapFrame);
        swapValidMap->Clear (swapFrame);
        swapOwners[swapFrame] = (TranslationEntry *) NULL;
      } // else if - if
    } // end if 
  } // end for

  return;
}

//////////////////////////////////////////////////////////////////////
//  Finds a free frame in the main memory. See the definition above of 
//  a free frame.
//////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
//  mark the first free page and return its index, or return -1
//  if no page is free
//////////////////////////////////////////////////////////////////////
int MemManager::locateFirst ()
{
  return coreFreeMap->Find ();
}

//////////////////////////////////////////////////////////////////////
// MP3: this is called when the memory manager cannot find a free
// physical memory frame and needs to evict a page. your job is to
// decide which page to evict based on the selected page replacement
// algorithm. hint: coreOwners[i]->use and coreOwners[i]->dirty bits
// correspond to the R and M bits in the book respectively.
//////////////////////////////////////////////////////////////////////
int MemManager::makeFreeFrame ()
{
  // victim is the number of the physical page to be swapped out
  int victim = 0;   

  switch(policy)
  {
  case PAGEREPL_NRU: // 4.4.2 - Not Recently Used
  {
    break;
  }

  case PAGEREPL_FIFO: // 4.4.3 - FIFO
  {
    int *ptr = fifoList->Remove();
    victim = *ptr;
    #ifdef CHANGE
      if(ptr!=NULL)
      	 delete ptr;
    #endif
    break;
  }

  case PAGEREPL_SC: // 4.4.4 - Second Chance
  {
    break;
  }

  case PAGEREPL_CLOCK: // 4.4.5 - Clock
  {
    break;
  }

  case PAGEREPL_WS: // 4.4.8 - Working Set
  {
    int v_timestamp = stats->totalTicks;
    break;
  }

  case PAGEREPL_AGING: // 4.4.7 - Aging
  {
    unsigned int v_bitmask = 0xFFFF;
    break;
  }

  default:
    ASSERT(false);
    break;
  } // end switch

  return victim;
}


///////////////////////////////////////////////////////////////////
// MP3: this is called when nachos is unable to find something in
// memory and requests that it be paged in from nachos backstore
///////////////////////////////////////////////////////////////////
void MemManager::faultIn (TranslationEntry * PTEntry)
{
  int physPage = coreFreeMap->Find ();

  // MP3 make any needed changed here
  if (physPage < 0) // if find returns less < 0 there are no free phys frames
  {
 
    physPage = makeFreeFrame(); // we must find one and free it
  
    if(coreOwners[physPage]->dirty) // if dirty bit, write to disk
    {
      pageOut(physPage);
    }
    else
    {
      coreOwners[physPage]->valid = FALSE; // invalidate frame
    }
  }

  pageIn (PTEntry, physPage); // swap in the frame

  if(someVerbose)
    printf("(swap: %d)%c", physPage, ( ++formatCount % 5 == 0 ? '\n' : ','));
    
  return;
}

/////////////////////////////////////////////////////////////////
// MP3: this is an interrupt service routine that handles clock
// interrupts. The given code for MP3 sets it up to be called
// periodically under these algorithms: NRU and AGING. Both of these
// algorithms require something to be done on clock interrupts.
//
// Note: arg is a dummy argument that is meaningless and should not
// be used.
/////////////////////////////////////////////////////////////////
void MemManager::doUpdation (int arg)
{
  int i;
  // MP3 - make any needed changes to this function

  if(someVerbose)
    printf("(update)%c", ( ++formatCount % 5 == 0 ? '\n' : ','));

  switch(policy)
  {
  case PAGEREPL_NRU: // Not Recently Used Section 4.4.2 
  {
    break;
  }
  case PAGEREPL_AGING: // Aging Section 4.4.7
  {
    break;
  }

  // the following don't use the timer interrupt
  case PAGEREPL_FIFO:  // not used
  case PAGEREPL_SC:    // not used
  case PAGEREPL_CLOCK: // not used
  case PAGEREPL_WS:   // not used
  default:
    break;
  } // end switch

  return;
}


/////////////////////////////////////////////////////////////////
// Reads in the appropriate page into the physFrame mentioned
/////////////////////////////////////////////////////////////////
void MemManager::pageIn (TranslationEntry * PTEntry, int physFrame)
{
  int swapFrame;
  int x;
  char my_buffer[PageSize];

  // Search swap file for PTEntry.
  swapFrame = swapSearch (PTEntry);

  if (swapFrame >= 0)
  { // Frame found.  Read it in from BS to temporary buffer.
    swapfile->ReadAt (my_buffer, PageSize, PageSize * swapFrame);
  }
  else
  { // Frame not found.  Read it from the source file.
    currentThread->space->ReadSourcePage (my_buffer, PTEntry->virtualPage);
  }

  PTEntry->physicalPage = physFrame;
  PTEntry->valid = TRUE;
  coreOwners[physFrame] = PTEntry;

  for (x = 0; x < PageSize; x++)
  {
    machine->WriteMem(PTEntry->virtualPage * PageSize + x, 1,
                      (int)my_buffer[x]);
  } // end for

  PTEntry->use = FALSE;
  PTEntry->dirty = FALSE;

  // MP3 - you need to make changes to the history keeping algorithms here
  // FIFO and Second Chance have been implemented for you
  switch(policy)
  {
  case PAGEREPL_FIFO:  // 4.4.3 - FIFO
  case PAGEREPL_SC:    // 4.4.4 - SC
  {
    int *ptr =new int;
    *ptr = physFrame;
    fifoList->Append(ptr);
    break;
  }

  case PAGEREPL_AGING: // 4.4.7 - AGING
  {
    break;
  }
  
  case PAGEREPL_NRU:   // 4.4.2 - NRU
  case PAGEREPL_CLOCK: // 4.4.5 - CLOCK
  case PAGEREPL_WS:   // 4.4.8 - WS
  default:
    break;
  }

  return;
}


/////////////////////////////////////////////////////////////////
// Reads the appropriate page into a swap frame. 
/////////////////////////////////////////////////////////////////
void MemManager::pageOut (int physFrame)
{
  TranslationEntry *victim_te = (TranslationEntry *) NULL;
  int my_buffer[PageSize];
  char cbuf[PageSize];
  int swapFrame;
  int check;
  int x;

  victim_te = coreOwners[physFrame];

  // Copy memory contents to temporary kernel buffer.
  // Make valid so translation works.
  victim_te->valid = TRUE;
  for (x = 0; x < PageSize; x++)
    machine->ReadMem (victim_te->virtualPage * PageSize + x, 1,
                      my_buffer + x);
  victim_te->valid = FALSE;

  // Convert Int array to char array.  This avoids endian problems.
  for (x = 0; x < PageSize; x++)
    cbuf[x] = (char) (my_buffer[x]);

  // Search for previously owned page in the swap file.
  for (swapFrame = 0;
       ((swapFrame < NumSwapPages) && (victim_te != swapOwners[swapFrame]));
       swapFrame++);

  if (swapFrame != NumSwapPages)
  { // Previous page found.
    swapFreeMap->Mark (swapFrame);      // deadbeef
  }
  else
  { // Previous page not found in swap file, so allocate one.
    swapFrame = swapFreeMap->Find ();
    ASSERT (swapFrame >= 0);
    swapOwners[swapFrame] = victim_te;
  }

  // Write Page to Backing store, because always dirty. 
  check = swapfile->WriteAt (cbuf, PageSize, PageSize * swapFrame);
  ASSERT (check == PageSize);

  // Clear dirty bit.
  victim_te->dirty = FALSE;

  // It may or may not have been changed by the paging scheme, so just for 
  //  good measure.
  victim_te->valid = FALSE;

  return;
}


/////////////////////////////////////////////////////////////////
// this method is called when a page fault occurs
/////////////////////////////////////////////////////////////////
void MemManager::PageFaultExceptionHandler (int BadVPage)
{
  mutex->P(); // enter critical section, baby

  if (BadVPage >= int(machine->pageTableSize)
      || machine->pageTable[BadVPage].legal == FALSE)
  {
    printf ("Illegal memory access by thread : %s\n",
            currentThread->getName ());
    printf ("Halting the thread : %s\n", currentThread->getName ());

    mutex->V ();
    // call SC_Exit syscall exception
    machine->WriteRegister (2, SC_Exit);
    // The exit status
    machine->WriteRegister (4, 0);
    ExceptionHandler (SyscallException);
    // The current execution of this method will never get beyond this
    // position. The thread in whose context the method is executing is
    // halted. This is the reason why the mutex is released right here.
  }

  faultIn (machine->pageTable + BadVPage);

  mutex->V(); // leave critical section
}


/////////////////////////////////////////////////////////////////
// Search through the swap pages to find the PTEntry object
/////////////////////////////////////////////////////////////////
int MemManager::swapSearch (TranslationEntry * PTEntry)
{
  int swapFrame;

  for (swapFrame = 0; swapFrame < NumSwapPages; swapFrame++)
  {
    if (swapOwners[swapFrame] == PTEntry)
    {
      return swapFrame;
    }
  }

  return -1;
}

/////////////////////////////////////////////////////////////////
// The actual timer interrupt handler. It calls doUpdation on
// the memory manage object. Uses divider to lower overhead.
/////////////////////////////////////////////////////////////////
void PageTimer (int arg)
{
  static int counter;
  int divider = 64;

  if (!(counter = (++counter % divider)))
  {
    machine->memManager->doUpdation (arg);
  }
  return;
}