2nd Practical Assignment - Replacement Algorithm(Nachos)

Searching in the internet we found an article about virtual memory in nachos. This article explained some features of virtual memory, and how to handle them in nachos, so we based in this to try our own Page Replacement algorithm.

The important thing we learned there: the page replacement algorithm should be called when a PageFaultException is raised, so we had to modify some stuff at the "exception.cc" file (found in the userprog directory). Here we needed to handle what was going to happen when a PageFaultException was raised (the exception already existed), so we added the next lines:

  
void
ExceptionHandler(ExceptionType which)
{
    /If the exception type is a PageFaultException, call the PageFault function.
    if(which == PageFaultException){
 DEBUG('a', "Page Fault.\n");
 PageFault();        
    }
}

This will execute the PageFault function when a PageFaultException is raised, so when this happens the page replacement algorithm should also execute.

The PageFault function code will first get the page that caused the Page Fault, which is stored at the register, then call the Select_Out method from the PageReplacement class, this method takes as parameters the page which caused the exception and the address space of the current thread. Then after the algorithm was executed, the PageFault function is going to be check if the page was modified, if it was, it will write the page in the swap file(an OpenFile object defined as a global variable in the system.h and system.cc files). The page will be marked as not valid, because is not longer in the main memory, and the page table will be updated.

void
PageFault()
{
  PageReplacement *replace;
  unsigned int page;
  //Get the page who rised the exception.
  page=(machine->ReadRegister(BadVAddrReg)/PageSize);
  //Get the frame who's going to be swapped.
  TranslationEntry* swap_victim = replace->Select_Out(currentThread->space, page);
  // If the page was modified, write it in the swap file
  if (swap_victim->dirty)
    fdswap->WriteAt(
      &(machine->mainMemory[(swap_victim->physicalPage)*PageSize]),
      PageSize,
      (swap_victim->virtualPage)*PageSize);

  // Mark it as not valid, because is not longer in the main memory
  swap_victim->valid=false;

  TranslationEntry* nueva = (currentThread->space)->
    ReadEntry(page);

  fdswap->ReadAt(
      &(machine->mainMemory[(swap_victim->physicalPage)*PageSize]),
      PageSize,
      page*PageSize);

  //Update the page table
  nueva->valid = true;
  nueva->physicalPage = swap_victim->physicalPage;
}

Now what happens in the PageReplacement class (Replace.cc) code?. The Select_Out method will run the LRU algorithm that we previously tested in python to determine which page is going to be be write at swap. The method searches if the page is already in the queue, if it is, it'll just update its position. If it is not already in the queue, it's added at the beginning of the queue and the last element of the queue is swapped out. It is important to note that most of the methods used for the queue operations were implemented by us, because NachOS didn't have so much of them to work with.

TranslationEntry* PageReplacement::Select_Out(AddrSpace* space, unsigned int page)
{
 unsigned int swap;
 //Search if already in queue
 if(queue->Search(page)){
  //get the position in which is stored
  int pos = queue->IndexOf(page);
  //remove it
  queue->RemoveAt(pos);
  //put it at the beginning
  queue->Prepend(page);
 }
 else{ //if not in queue
  //remove the last element, the one who will be swapped
  queue->Prepend(page);

 }
 //The one at the end is the one who's going to be send to swap
 swap = queue->Remove();
 queue->Print();
        //Find the page table entry for the victim
 int out_entry = space->SearchPhysicalAddress(swap);
 TranslationEntry* victim = space->ReadEntry(out_entry);
  return victim;
}

Some of the implemented List methods are:

Search Method: 
Used to search for a value in the List, returns true if found, otherwise returns false.

template 
bool
List::Search(Item value)
{ 
 bool found = false;
 ListNode *ptr = first;
 while(ptr!=NULL){
  if(ptr->item == value){
   //std::cout << "Found";
   found = true;
  }
  ptr = ptr->next;
 }
 return found;
}

IndexOf Method:
Used to find the index of a given item from the list.

template 
int
List::IndexOf(Item value)
{ 
 ListNode *ptr = first;
 int index = 0;
 while(ptr!=NULL){
  if(value == ptr->item){
   return index;
  }
  index = index + 1;
  ptr = ptr->next;
 }
 return -1;
}

RemoveAt method:
Removes an item at a given index.

template 
void
List::RemoveAt(int index)
{ 
 ListNode *ptr = first;
 ListNode *ptr_next;
 int i = 0;
 if(Get(index) == last->item){
  std::cout << "Ultimo Borrado";
  last->item = NULL;
 }
 else{
  while(ptr!=NULL){
   if(index >= i){
      ptr_next = ptr->next;
      ptr->item = ptr_next->item;
  
   }
   i = i + 1;
   ptr = ptr->next;
  
  }
 }
}

Unfortunately we couldn't test this in our nachOS because we couldn't implement the TLB and PageTable, which was necessary to the performance of the algorithm.
Anyway, our NachOS code can be downloaded here:

• Download

Any doubt or suggestion, please feel free to comment.

References:
http://sopa.dis.ulpgc.es/wiki/index.php/Actividad_7:_memoria_virtual