GDB for debugging NachOS

Hi there, on this post I'll explain how we used the GDB debugger to find some errors in our NachOS.

We used GDB to find which program was causing a Segmentation Fault, which we kept getting from trying to execute two NachOS machines in two different command lines, one with: ./nachos -m 0 -o 1 &  and the other with: ./nachos -m 1 -o 0 &, this was done to test the network.

First of all, what is GDB?

"GDB, the GNU Project debugger, allows you to see what is going on `inside' another program while it executes -- or what another program was doing at the moment it crashed.

GDB can do four main kinds of things (plus other things in support of these) to help you catch bugs in the act:

• Start your program, specifying anything that might affect its behavior.
• Make your program stop on specified conditions.
• Examine what has happened, when your program has stopped.
• Change things in your program, so you can experiment with correcting the effects of one bug and go on to learn about another.

The program being debugged can be written in Ada, C, C++, Objective-C, Pascal (and many other languages)."

You can check if you already have GDB using: which gdb, on the command line. If you don't you can install it with a simple: sudo apt-get install GDB.

Example run:

Now, the important part, using it. As the description says, GDB can debug C++ programs, so we decided to use it to see if it really works, and find what in NachOS was causing that Segmentation Fault.

Like said before, there were two different machines running at the moment in two command lines, one would get a Segmentation Fault, and other an Assertion Failed. The first one to run, would be getting a Segmentation Fault, and the second an Assertion Failed, always in that order.

Segmentation Fault:

And the Assertion Fault:

So, to find the culprit, we first run gdb, executing gdb in both command lines for the NachOS executable using:  gdb nachos.

And then we run in one  ./nachos -m 0 -o 1   and the other with: ./nachos -m 1 -o 0 . This was important because if we just executed one, the conditions in which the error occurred wouldn't be the same. 

This produced the following output:

So as we can see there, gdb is telling us:

 The program received a Segmentation Fault in Lock::IsHeldByCurrentThread at 

../threads/synch.cc: 117

117       return lockHolder = currentThread;

Its telling us which line, which method, and which file caused it. So we proceeded to fix that:

Changing line:      return lockHolder = currentThread;

To:                        return lockHolder;

(Yes, as simple as that)

After modifying that, we compiled NachOS again, and proceeded to try again to test the NachOS network again, and the output was:

The message worked in both machines, and no more Segmentation Faults were produced.

And now, maybe late, we realize the importance of debugging, because at the 1st Assignment we kept getting Segmentation Faults, without realizing which program was causing, so now onward we know how to tell.

So, that's all for this post, if you have any doubts or suggestions feel free to comment. :)

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

2nd Practical Assignment - MMU

For the OS practical assignment we decided to implement a simulation of the MMU, in python programming language. In this post, I will show the code, an explanation of it, and screen captures of the results.

Page Table

As we already know, the page table is used to do memory translations from logic to physical addresses which are understandable to the drivers.

To begin, the script has as parameters first, the size of the address range, namely, the number of bits the computer has to assign addresses. The second is the size of the main memory, and the third the frame size.

The script starts verifying the parameters, to check if they meet certain conditions. Then some of these values are passed as attributes of the class PageTable and calculates the number of bits belonging to the logical address to get an idea of how many rows the page table will need.

Now to generate the page table, we use a "for" to add to a matrix the rows of the Page Table. To tell how many rows it must add, it uses the value from the logical addresses and raises the 2 to the power of that number. Maps the frames of the main memory, and when it ends, maps it again in the spare addresses, with this we achieve that any accessed logical address will have an assigned physical address.

  
 def __init__(self, tamDireccionVirtual,  memoriaP, tamFrame):
  if (memoriaP%2 != 0) or \ # El tamaño de la memoria principal debe ser un multiplo de 2
  (tamFrame%2 != 0) or \ # El tamaño de las frame debe ser un multiplo de 2
  ( memoriaP%tamFrame != 0) or \ # El tamaño de la memoria principal debe ser un multiplo de el tamaño de la frama
  ( pow(2,tamDireccionVirtual) < tamFrame) or \ # El tamaño del frame debe poder contenerse en el rango de direcciones
  ( tamDireccionVirtual%4 != 0): El rango de direcciones debe ser multiplo de 4
   print 'Error'
   return

  self.tDVirtual = tamDireccionVirtual; # bits
  self.ram = memoriaP # bytes
  self.tFrame = tamFrame # bytes
  self.numeroMaximoFrames = 300
  #[Direccion fisica, bit de presencia, bit de persistencia, dirty bit, lectura, escritura, modificacion]
  self.pageTable = []

  # Calcular el numero de direcciones logicas que se pueden tener
  self.numDireccioneslogicas = self.tDVirtual - math.log(self.tFrame,2)

  # Generar la page table
  print 'Numero de registo logico   direccion fisica'
  contadorDirFis = 0 # Este contador es utilizado para asignar las primeras direcciones a la memoria principal en la tabla
  for i in range(0, (int( pow( 2,self.numDireccioneslogicas)) - 1) ):
    if i < self.ram/tamFrame :
     self.pageTable.append([contadorDirFis, 1,0,0,0,0,0])
    else:
     self.pageTable.append([contadorDirFis, 0,0,0,0,0,0])

    if( contadorDirFis < (self.ram-self.tFrame) ):
     contadorDirFis = contadorDirFis + self.tFrame
    else :
     contadorDirFis = 0

    print "%s %s"%(i,self.pageTable[i])

  print 'Page table creada.'

The result is the following:

The Page Table is in charge of translating addresses, so to achieve this, the method obtenerDireccionFisica receives a String parameter with a hexadecimal logical address of a certain size. The method splits the address and gets from it the address of the  page in the table and the displacement in memory inside of it, and converts it into an integer.To finish, the method searches for the page in the table, and verifies that this page is found on the main memory, otherwise it raises a "Page Fault".

 
 def obtenerDireccionFisica(self, direccionLogica ):
  direccionFisica = direccionLogica[0 : int(self.numDireccioneslogicas/4)] # Parte la direccion logica y obtiene la direccion del frame en la tabla 
                # Parte la direccion logica y obtiene la direccion de desplazamiento de la frame
  desplazamiento = direccionLogica[int(self.numDireccioneslogicas/4) : int(self.tDVirtual /4)] 
  if self.pageTable[int(direccionFisica, 16)][1] == 1: "Verifica que se encuentre en la memoria principal
   return  self.pageTable[int(direccionFisica, 16)][0]  + int(desplazamiento, 16) # Convierte las direcciones a hexagesimal y obtiene la direccion
  else:
   return "Page fault"

The result is the following:

TLB

The TLB works as a cache memory to translate quicker the last used addresses, this memory is pretty quick, and all the rows are accessed simultaneously, which makes it more useful, the problem is, this memory is very small, so it works together with the Page Table to translate addresses.

The TLB receives as parameters the Page Table and the quantity of rows the TLB cache has, then it builds it   using the first rows of the Page Table.

 def __init__(self, PageTable, filas):
  self.pt = PageTable
  self.filas=filas
  self.table=[] #[ direccion de pagina, PID, sin usar, direccion fisica, N, D, V, G, vejes]

  for i in range(0,self.filas):
   self.table.append([i, 0, 0, self.pt.pageTable[i][0],0,0,0,0, 0])
   print " {} {}".format(i, self.table[i])
  print 'TLB creada'

Result:

To get the physical address, first the TLB splits the logical address in the page address and the displacement, then with a "for" cycle, searches if this address is in the TLB, if it is not there, it searches in the Page Table.

It is important to note, the page table must know which pages bring out, and which bring in the Page Table. For this every row has an "age" number which increments every time a page is brought to the TLB, so when it is necessary to take out a page, the TLB uses this number as an index to decide which one bring out, taking out one of the oldest pages.

def obtenerDireccionFisica(self, direccionLogica ):
  direccionDePagina = int( direccionLogica[0 : int(self.pt.numDireccioneslogicas/4)] , 16)
  desplazamiento = int( direccionLogica[int(self.pt.numDireccioneslogicas/4) : int(self.pt.tDVirtual /4)] , 16)

  vejes = 0
  for i in range(0,self.filas):
   if vejes  < self.table[i][8] :
    vejes = self.table[i][8]

  for i in range(0,self.filas):
   if( self.table[i][0] == direccionDePagina):
    print 'Direccion encontrada en la tlb'
    for e in range(0,self.filas):
     self.table[e][8] = self.table[e][8] + 1
    return   self.table[i][3] + desplazamiento

  print 'Direccion no encontrada en la tlb, buscando en la page table y actualizando la tlb ...'
  resultado = self.pt.obtenerDireccionFisica( direccionDePagina, desplazamiento)
  if resultado != "Page fault" :
   for i in range(0,self.filas):
    if vejes  == self.table[i][8] :
     for e in range(0,self.filas):
      self.table[e][8] = self.table[e][8] + 1
     self.table[i] = [direccionDePagina, 0, 0, self.pt.pageTable[direccionDePagina][0],0,0,0,0, 0]
     self.pt.pageTable[direccionDePagina][1] = 1
     break
   return resultado
  else:
   print "Se ha generado un {} moviendo datos y actualizando la tlb...".format(resultado)
   for i in range(0,self.filas):
    if vejes  == self.table[i][8] :
     for e in range(0,self.filas):
      self.table[e][8] = self.table[e][8] + 1
     self.table[i] = [direccionDePagina, 0, 0, self.pt.pageTable[direccionDePagina][0],0,0,0,0, 0]
     self.pt.pageTable[direccionDePagina][1] = 1
     break
   return self.pt.pageTable[direccionDePagina][0] + desplazamiento

Resultado:

2nd Practical Presentation

 

Download Links: 

• NachOS: Download

• Python MMU Code: ...

2nd Theoretical Presentation

2nd Theoretical Assignment - File Systems

Hi, in this entry i'm going to talk about performance of file systems.

As we already know a File System is a huge collection of directories and files which save all kind of information. File Systems are organized by directories which in turn can contain besides files, other directories or sub-directories.

A way of organizing a file system may be:

• Using a 'root' to signal where in the disk the 'root directory' starts.
• The 'root directory' points to 'user directories'
• An 'user directory' contains an entry for every file
• The file names need to be unique inside a certain user directory.

The system name for a file must be unique in the file system. In hierarchical file systems, the system name for a file is usually the "trajectory name" from the 'root directory' to the file.
Example: /home/ubuntu/myfile.txt

Directories in UNIX systems are organized keeping certain hierarchy as we can see in the following schematic picture:

Some utilities of File Systems according to Wikipedia are:

File systems include utilities to initialize, alter parameters of and remove an instance of the filesystem. Some include the ability to extend or truncate the space allocated to the file system.

Directory utilities create, rename and delete directory entries and alter metadata associated with a directory. They may include a means to create additional links to a directory (hard links in Unix), rename parent links (".." in Unix-like OS), and create bidirectional links to files.

File utilities create, list, copy, move and delete files, alter metadata. They may be able to truncate data, truncate or extend space allocation, append to, move, and modify files in-place. Depending on the underlying structure of the filesystem, they may provide a mechanism to prepend to, or truncate from, the beginning of a file, insert entries into the middle of a file or deletion entries from a file.

Also in this category are utilities to free space for deleted files if the filesystem provides an undelete function.

Some filesystems defer reorganization of free space, secure erasing of free space and rebuilding of hierarchical structures. They provide utilities to perform these functions at times of minimal activity. Included in this category is the infamous defragmentation utility.

There are two general strategies to store a 'n' bytes file.

1.   Assign 'n' consecutive bytes of disk space.

• Downside: If a file size increases, it will probably move in the disk, which can affect performance.

2.   Divide the file in a certain number of blocks (not necessarily adjacent)

• Generally file systems use this strategy with fixed size blocks.

Some of the most important features of files system utilities involve supervisory activities which may involve bypassing ownership or direct access to the underlying device. These include high performance backup and recovery, data replication and reorganization of various data structures and allocation tables within the filesystem.


Example of emulating a defragmentation algorithm:
http://forums.devshed.com/c-programming-42/defragmentation-algorithm-757280.html

References:
http://en.wikipedia.org/wiki/File_system
http://www.cecalc.ula.ve/bioinformatica/UNIX/node10.html

2nd Theoretical Assignment - Page Replacement

Hi there, in this post I will explain how the page replacement algorithms work.
So first, what is the page replacement algorithm for?

 In a computer operating system that uses paging for virtual memory management, page replacement algorithms decide which memory pages to page out (swap out, write to disk) when a page of memory needs to be allocated. - Wikipedia

In our nachos, the page replacement algorithm will decide which page is going to be swapped out in  order to allocate a new one. For this, Martin C. Rinard mentions two algorithms in his notes: FIFO, and LRU.

FIFO

FIFO means, like many of you may already know, First-In First-Out, so this algorithm is going to swap the first page brought into memory, regardless of whether it has been accessed recently or not.

An example would be:
Sequence: 1, 2, 3, 1, 4 (Using a 3 sized memory)
1-> [1]
2->[1, 2]
3->[1, 2, 3]
1->[1, 2, 3] #1 is accessed again
4->[2, 3, 4] #And yet is swapped in the next turn

This is a downside of the algorithm, it may eject a heavily used page.

A pseudo-code for this algorithm would be:

  
fifo(page):
   #If the memory is not full yet
    if len(memory) < memory_size:
       #And the page is not already in memory 
        if page not in memory:
            #Add the page to memory
            memory.append(page)
    #If the memory is full
    elif len(memory) == memory_size:
        #And the page is not already in memory
        if page not in memory:
           #swap out the first added page ( index 0 on the queue)
            swap_out = memory.pop(0)
           #Add the page to memory at the end
            memory.append(page)

An example run of a python script using this pseudo-code and data from the OS notes:

LRU:

LRU, Least Recently Used, works as it sounds, it will swap out the least page used. For this the algorithm uses a queue, in which the pages brought to memory will be added to the beginning of the queue. When a page fault occurs, the algorithm swaps out  the last page on the queue.

Sequence: 1, 2, 3, 1, 4 (Using a 3 sized memory)

1->[1] - [1]

2->[1, 2] - [2, 1]

3->[1, 2, 3] - [3, 2, 1]

1->[1, 2, 3] - [1, 3, 2] # 1 is accessed, the queue updates

4->[1, 4, 3] - [4, 1, 3] #a page fault occurs, 2 is the least recently used, so it's ejected.

A pseudo-code for this algorithm would be:

  
LRU(page):
    #If the memory is not full yet.
    if len(queue) < memory_size:
        #And the page is not already in the queue
         if page not in queue:
            #Add the page to the beginning of the queue.
            queue.insert(0, page)
       #else if its already in the queue
        else:
           #Pop the page out, and add it at the beginning
            queue.pop(queue.index(page))
            queue.insert(0, page)
    #If the memory is already full
    if len(queue) == memory_size:
       #And the page is not in the queue
        if page not in queue:
            #swap out the last page in the queue, and add the new one to the beginning
            swap_out = queue.pop()
            queue.insert(0, page)
       #Else if it's already in the queue
        else:
            #Pop the page out, and add it at the beginning
            queue.pop(queue.index(page))
            queue.insert(0, page)

An example run of a python script using this pseudo-code and data from the OS notes:

LRU Vs FIFO

To test the algorithm, a sequence of 20 random pages were used to obtain averages between 100 samples. Five different pages were used(from 1 to 5).

So, according to this, in average FIFO gets more page faults than LRU in every memory size bellow 7.

This also concludes an interesting fact, at n + 2 size(n being the number of different pages), both algorithms bring the same results. So in this case in which, n = 5, from 7 onwards the page faults in both LRU and FIFO will be the same providing the sequence is the same for both.

And that's all for the page replacement, if you have any doubt or observations, feel free to write in the comment section bellow. 

Download the python source

References:

http://people.csail.mit.edu/rinard/osnotes/

Wikipedia