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.