2nd Theoretical Assignment - TLB and Page Table

Paging

In the first computers, memories were reduced and normally programs wouldn't fit in them, slow algorithms were used, and to address this problem the memory was divided in pieces and secondary memories were used to load some of this pieces of processes into the main memory, and the others into a secondary memory for later use. This is called memory overlay. 

Even so, this still brought many problems to programmers because they had to work with the address of the overlays which brought as consequence the idea of paging. Paging is a method to separate the memory space from addresses and addresses from memory in the main memory of the computers, this idea was came to be in 1961 from a group of researchers in Manchester, England.

In paging, the address space is divided in pieces, called pages and the physical memory is divided in pieces of the same size called frames which allows large spaces of memory to be reduced in small pieces.

An address space may feature a n quantity of bits which can address 2^n addresses. Dividing this address space in pieces decreases this number, which makes the administration of this address space more simple.

The address space is also divided, for example, if we have an address space of 32 bits, and frames of 4kb, which is equivalent to 2^12 physical memory addresses, the last 12 bits of the address are assigned to the addressing inside the frames, and the other 20 at the left, are assigned to the frame's address space, leaving 2^20 addresses managed by the operating system, doing a more lighter job.

 
0000 0000 0000 0000 0000  0000 0111 1111
|_____________________|   |____________|
                |                                             |
                |                                             v
                |                    Memory location within the page
                v
         Page Number

Another attribute of paging is its abstraction, which allows a logical address to point at a page even when the page is not in the range of addresses of the memory frames, this can take advantage of all the logical address space in the computer.

Page Table

The page table is a structure which  performs the translation of logical addresses into physical addresses from the memory. Besides this, the page table keeps track of the pages, and improves the security of the pages, managing the writing, reading, and executing permissions

The most common fields in a page table are:
The address of the frame in memory
Presence bit used to know tell if the page is found.
The dirty bit used to know if a file has been modified in the main memory, and must be updated in secondary memory.
Persistence bit
Writing, reading and modification bit.

To translate logical addresses into physical addresses, the logical address is divided in the number of pages and the displacement, then the number of pages is used to find it inside the page table, once the address of the page is found , the displacement is added to the memory inside the page, and that's how the physical address is found.

Despite the number of addresses managed with paging being decreased, the page tables can be extremely large, so different techniques are used to organize this tables.

Page Fault

If the presence bit in the memory marks that is not present in the main memory, the MMU responds by rising and exception(commonly called page fault). If the page is found in the swap space, the operating system will invoke an operation called page replacement, to bring the page required to the main memory. This operation takes several steps and it may be time-consuming.



TLB

Even if tables decreases the quantity of managed addresses, these can be very large and slow, so a cache memory is used. This memory can reside between the memory and the cache itself or between the cache and the main memory unit. This memory is very fast, but small. Typically the TLB has between 2 and 2048 entries. So, before accessing to the page table, the hardware looks in the TLB, if the logical address is there, so is the corresponding physical address and it's accessed directly. If it's not there, the hardware looks in the page table, and then the memory, and saves the access in the TLB

Algorithm for accessing a virtual address:

1. The MMU receives from the CPU a dir -virtual.
2. MMU searches( in parallel) dir -virtual in the TLB memory. If it's successful go to step 7.
3. Search the address in the page table. If it's successful go to step 6, if else, generate a page fault.
4. Execute a strategy of page replacement
5. Swap pages between disk-memory
6. Delete the TLB and update the page table.
7. Update the TLB
8. Generate a physical address and search for data in memory. If it's not successful, consult for data in the page table.
9. MMU returns the requested data.

References:
http://nits.com.ar/uadeclasses/clase11.html
http://viralpatel.net/taj/tutorial/paging.php
http://www.pling.org.uk/cs/ops.html
http://es.wikipedia.org/wiki/Paginaci%C3%B3n_de_memoria
http://es.wikipedia.org/wiki/Translation_Lookaside_Buffer
http://expo.itch.edu.mx/view.php?f=os_42#page6

Organización de computadoras. Un enfoque estructurado, 4ta Edición - Andrew S. Tanenbaum

Dining philosophers(Implementation)

Good Day!, in this post I'll explain how our implementation of the dining philosopher works. For this, we made 3 different versions of the problem in python to test the algorithm.

1st
This class is the core of the program, its the base of what every philosopher does with his "forks". In this version of the dining philosophers, all they do is take the left fork, and then the right fork, and eat in case they are hungry.This is the most basic logic of what the philosophers would do. This behavior causes some deaths, or a DeadLock to generate.

class filosofo:

 def darVida(self):
  while(True):
   if self.hambre > self.limiteHambre :
    self.tenedorIzquierdo.acquire()
    self.actual[0]=1
    self.tenedorDerecho.acquire()
    self.actual[1]=1
    while self.hambre > self.limiteComer :
     self.noHagoNada()
    self.tenedorIzquierdo.release()
    self.actual[0]=0
    self.tenedorDerecho.release()
    self.actual[1]=0
   time.sleep(1.0)

2nd
This is the code for the algorithm using turns, which makes every philosopher wait for his own turn, if its the turn of philosopher A, then he will eat until he feels satisfied, and if he doesn't he will just pass his turn. This logic works to avoid deadlocks or the deaths of some philosophers depending on the philosophers on the table. Should the number of philosophers increase, every philosopher would have to wait more time and eventually will die.


class filosofo:


def darVida(self):
while(True):
if self.hambre > self.limiteHambre :
if self.ficha > 0 :
self.tenedorIzquierdo.acquire()
self.actual[0]=1
#print( "Soy el filosofo %d y tengo mi tenedor izquierdo :D"%(self.identidad) )
self.tenedorDerecho.acquire()
self.actual[1]=1
while self.hambre > self.limiteComer :
self.noHagoNada()
#print( "Soy el filosofo %d estoy comiendo :D"%(self.identidad) )
self.tenedorIzquierdo.release()
self.actual[0]=0
self.tenedorDerecho.release()
self.actual[1]=0

if self.identidad < len(mesa.filosofos) and self.ficha == 1:
self.mesa.filosofos[self.identidad+1].darFichaT()
self.ficha=0
elif self.identidad == 5 and self.ficha == 1:
self.mesa.filosofos[0].darFichaT()
self.ficha=0
time.sleep(1.0)

def noHagoNada(self):
time.sleep(1.0)
return;

3rd.
The next implementation is alternate tokens, in which every two or three philosophers are assigned with alternate tokens. They can eat for an amount of time(which we call turn). Every turn, the philosophers who posses a token have to pass the token to the one at his right. This will cause the philosophers to alternate their turns,and subsequently, less time to wait . The parameters that affect this solution are the speed in which each philosopher eats in his turn, and the speed in which each philosopher will be hungry again, in case of getting more hungry in one turn in which the token is lost, then at some point the philosophers will die. Otherwise if the eating speed is more than the speed of digestion, then they will be always on a common range of hunger.

class filosofo:


def darVida(self):
while(True):
if self.hambre > self.limiteHambre :
if self.ficha > 0 :
self.tenedorIzquierdo.acquire()
self.actual[0]=1
#print( "Soy el filosofo %d y tengo mi tenedor izquierdo :D"%(self.identidad) )
self.tenedorDerecho.acquire()
self.actual[1]=1
while self.hambre > self.limiteComer and self.contadorFicha < self.turnos:
self.noHagoNada()
self.contadorFicha = self.contadorFicha + 1
#print( "Soy el filosofo %d estoy comiendo :D"%(self.identidad) )
self.tenedorIzquierdo.release()
self.actual[0]=0
self.tenedorDerecho.release()
self.actual[1]=0
if self.ficha > 0 :
if self.contadorFicha < self.turnos :
self.contadorFicha = self.contadorFicha + 1
else:
if self.identidad < 5:
self.mesa.filosofos[self.identidad+1].darFichaT()
self.ficha=0
self.contadorFicha=0
elif self.identidad == 5:
self.mesa.filosofos[0].darFichaT()
self.ficha=0
self.contadorFicha=0
time.sleep(1.0)

And here the links to the codes:
http://maxkalavera.iblogger.org/filosofos_base.py
http://maxkalavera.iblogger.org/filosofos_ficha.py
http://maxkalavera.iblogger.org/filosofos_alternados.py

See Ya!

OS 1st Practical Assignment

Os Practical Assignment 1

View more presentations from Emmanuel Garcia.

Implementation of Locks and Condition Variables(Example)

Example using locks and condition variables:
  

So in this code, like in the title said, we are showing how our locks and c. v. work. It's a basic consumer-producer program(with 2 consumers) where each consumer will "consume" 3 units if available, if not then he will go to sleep, until the producer finishes producing 'i' quantity units. The units are represented with a counter, and can be modified to try different results, in this examples, the consumer consumes 3, and the producer produces 4.

Code:

#include "example.h"
using namespace std;
Thread *t;
Lock *l;
Condition *c;
int avail = 0;
int p, i=0;

static void consumer(int n) {
  for(int j = 0; j< 3; j++){
    l->Acquire();
    if (avail == 0) {
      cout <<"Consumer "<< n << " Sleeping" << endl;
      c->Wait(l);
    }
    cout <<"Consumer "<< n << " Consuming something - Total :" << avail << endl;
    avail--;
    l->Release();
    i--;
  }
}

static void producer(int n) {
  while (i!=4) {
    l->Acquire();
    avail++;
    cout <<"Producer " << n << " Producing something - Total :" << avail << endl;
    c->Signal(l);
    l->Release();
    i++;
  }
}
Example::Example() {
  l = new Lock("l");
  c = new Condition("c",l);
  t = new Thread("consumer");
  t->Fork((VoidFunctionPtr)consumer, (void *)1);
  t = new Thread("consumer");
  t->Fork((VoidFunctionPtr)consumer, (void *)2);
  t = new Thread("producer");
  t->Fork((VoidFunctionPtr)producer, (void *)1);
}


 Screen Capture:

OS 1st Theoretical Presentation

Os theoretical presentation

View more presentations from Adan Cuellar.

Notes:

• The implementation of the locks, condition variables, and tests using the consumer-producer example will be explained in the practical part.

• Also our version of the Dining Philosopher's problem code will be presented in the practical part, we are planning to do it in python, to test the algorithm and prove it actually works, because NachOS threads can't handle methods, just functions. But we'll also try to do it in C++.

Implementation of Locks and Condition Variables

Our NachOS distribution:

Previously we stated that we were going to work with NachOS 4.0, and we actually tried to do a lot of things with that distribution, but we couldn't use semaphores or locks on our own code, although they were already implemented, so we tried a different distribution, NachOS 3.4.

In NachOS 3.4, semaphores were already implemented, so we tried to use them right away in our own code.
And surprise, it worked!, we could use them in a little consumer-producer test. So the next thing was to try locks and condition variables. Then we found out that they weren't implemented, just the definition of empty methods. So we decided to try implement it, using NachOS 4.0 as a guide, copy-paste wasn't an option since the 4.0 distribution had different classes to use interrupts, and adding that to NachOS 3.4 was a bit hard.

The changes we made were at the synch.cc and synch.h files as follows(added code is marked in red):

In the synch.cc file:

Lock::Lock(const char* debugName) {
    name = debugName;
    semaphore = new Semaphore("lock", 1);
    lockHolder = NULL;
}

Lock::~Lock() {
    delete semaphore;
}

void Lock::Acquire() {
    semaphore->P();
    lockHolder = currentThread;
}

bool Lock::IsHeldByCurrentThread(){
    return lockHolder == currentThread;
}

void Lock::Release() {
    ASSERT(IsHeldByCurrentThread());
    lockHolder = NULL;
    semaphore->V();
}

Condition::Condition(const char* debugName, Lock* conditionLock) {
    name = debugName;
    waitQueue = new List<Semaphore *>;
}

void Condition::Wait(Lock *conditionLock) {
    Semaphore *waiter;
    ASSERT(conditionLock->IsHeldByCurrentThread());
   
    waiter = new Semaphore("condition", 0);
    waitQueue->Append(waiter);
    conditionLock->Release();
    waiter->P();
    conditionLock->Acquire();
    delete waiter;
 }
void Condition::Signal(Lock *conditionLock) {
    Semaphore *waiter;
    ASSERT(conditionLock->IsHeldByCurrentThread());

    if(!waitQueue->IsEmpty()){
        waiter = waitQueue->Remove();
        waiter->V();
    }
}
void Condition::Broadcast(Lock *conditionLock) {
    while(!waitQueue->IsEmpty()){
        Signal(conditionLock);
    }
}


In the  synch.h file:

class Lock {
  public:
  Lock(const char* debugName);

  ~Lock();          // destructor
  const char* getName() { return name; } 
  void Acquire();
  void Release();
  bool IsHeldByCurrentThread();   

  private:
    const char* name;       
    Thread *lockHolder;
    Semaphore *semaphore;
};

class Condition {
 public:
    Condition(const char* debugName, Lock* conditionLock);   
    ~Condition();   
    const char* getName() { return (name); }
    void Wait(Lock *conditionLock);    
    void Signal(Lock *conditionLock);  
    void Broadcast(Lock *conditionLock);

  private:
    const char* name;
    List<Semaphore *> *waitQueue;
};

Like stated previously, all this changes were made using NachOS 4.0 as a guide, but that distribution used some other class(kernel) to interrupt and do some other stuff, class that is not implemented in 3.4, so we had to work with something else. Using other line codes for example the semaphores, we found out how to manage the interrupts.

That's on locks, now condition variables were easy to implement based on the 4.0 distribution, because it was almost exactly the same code, just adding some missing variables to the synch.h and changing some method names.

The already modified files can be downloaded here:

http://www.mediafire.com/?ugp1uc003tcsa72 

And that's it. If you have any question, suggestion or anything, feel free to comment.

Adding our own class to NachOS

Hi there, in this post we are going to explain how we added a new class, in order to compile it and execute it using NachOS.(4.0 or 3.4 tested).

First of all, where to add the code is important. Right now we are working with semaphores, schedules, locks, threads, etc. So in this case, the new class was added to the nachos/code/threads folder, in order to include the existing libraries of semaphores and threads.

Adding a new header file:
Knowing that, we created a new file: example.h. In that class we didn't do anything special, just declared some methods, and attributes for this example, like this:

//Here is were you include libraries that you are going to use in your code like:

#include <iostream>

#include "thread.h"

#include "synch.h"

class Example{

public:
                //Constructor

Example();

//Destructor

~Example();

void testSomething(int n);

private:

int n;

};

(Note: In C++ it is not neccesary to name the file after the class)

Adding a new cc file:
After that, we proceeded to write another code, this time named: example.cc.

Here is where we are going to actually put code, methods, etc, in order to add more functionality to NachOS.

Our example.cc code is as follows:

<pre class="brush: plain text">

//First, import the header file

#include "example.h"

using namespace std;

Example::Example(){
cout << "Constructor";
}
Example::~Example(){
cout << "Destructor";
}


void Example::testSomething(int n){
for(i = 0; i < n, i++){
cout << "Print #" << n<<endl;
}
}
</pre>


Modifying the Makefile.common:
With this, the only thing left is to add the example.h and example.cc files to the Makefile.common in the nachos/code/ folder in order to compile it with the rest of the NachOS code.


To do that, we just added some lines to the already existing code. We added code to the threads folder, so the new lines had to be added in the THREAD_H, and THREAD_C sections, but also in THREAD_O. Like this:

THREAD_H =../threads/copyright.h\

../threads/list.h\

../threads/scheduler.h\

../threads/synch.h \

../threads/synchlist.h\

../threads/system.h\

../threads/thread.h\

../threads/utility.h\ ../threads/example.h\

../machine/interrupt.h\

../machine/sysdep.h\

../machine/stats.h\

../machine/timer.h

THREAD_C =../threads/main.cc\

../threads/list.cc\

../threads/scheduler.cc\

../threads/synch.cc \

../threads/synchlist.cc\

../threads/system.cc\

../threads/thread.cc\

../threads/utility.cc\

../threads/threadtest.cc\ ../threads/example.cc\

../machine/interrupt.cc\

../machine/sysdep.cc\

../machine/stats.cc\

../machine/timer.cc

THREAD_O =main.o list.o scheduler.o synch.o synchlist.o system.o thread.o \

utility.o threadtest.o interrupt.o stats.o sysdep.o timer.o example.o

Compiling and executing:
And now we are ready to compile NachOS, to to this either compile everything running make from the nachos/code folder, or just compile the threads folder doing the same, in the threads folder.
To test the code, just run the nachos executable found in the threads folder, and it should  print something like this:


(image goes here)


And thats it, thats how we added a new class to the existing nachos code, if you have any questions or suggestions, feel free to comment.