First Practical Assignment

We're using nachos 3.4 and 4.0, because we're looking the differences in the code and we are complementing nachos 3.4 with 4.0 code. 
Nachos 4.0 already has a basic structure of semaphores and locks.

We had several problems compiling, and probably broke nachos many times but finally we accomplished our goal (with a little help of the code already complemented in the Nachos 4.0 and Max, Emmanuel and Adan's Blog 

Here we show you the code we have in the Synch.cc part where we implemented locks

Lock::Lock(const char* debugName) {

  //parte agregada para candado

  semaphore = new Semaphore("lock", 1);

  lockHolder = NULL;

}

//Destructor

Lock::~Lock() {

  delete semaphore;

}

void Lock::Acquire() {

  semaphore->P();

  lockHolder = currentThread;

}

//checar esta parte que fue agregada

bool 

Lock::IsHeldByCurrentThread(){

  return lockHolder == currentThread;

}

void Lock::Release() {

  ASSERT(IsHeldByCurrentThread());

  lockHolder = NULL;

  semaphore->V();

}

bool Lock::tryAcquire(){

  if(lockHolder == NULL){

    semaphore->P();

    lockHolder = currentThread;

    return true;

  }

  else{

    return false;

  }

}

Condition::Condition(const char* debugName, Lock* conditionLock) { 

  name = debugName;

  waitQueue = new List <Semaphore *>;

}

Condition::~Condition() { 

delete waitQueue;

//}

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);

  }

}

Now we show you the code we have in the Synch.h part, where we also implemented locks


//En esta parte es donde se agregan los candados y condition variable!!
//Constructor
Lock::Lock(const char* debugName) {
  //parte agregada para candado
  semaphore = new Semaphore("lock", 1);
  lockHolder = NULL;
}


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


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


//checar esta parte que fue agregada
bool
Lock::IsHeldByCurrentThread(){
  return lockHolder == currentThread;
}


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


bool Lock::tryAcquire(){
  if(lockHolder == NULL){
    semaphore->P();
    lockHolder = currentThread;
    return true;
  }
  else{
    return false;
  }
}


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


//Condition::~Condition() {
//delete waitQueue;
//}


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);
  }
}

We did a lot of modifications in the nachos code trying to implement the producer consumer problem but we broke it several times. 

(Screenshots)
(Code)
(Video)

First Theorical Assignment

UNBOUNDED-BUFFER (PRODUCER-CONSUMER)

Producer and Consumer share a common buffer

But not everything is happiness and perfection... Problems may exist when:

• The producer tries to get to the buffer and add elements but it’s already full.

• The consumer tries to get to the buffer but it’s empty.

To solve this problem the producer must go to sleep and wake up at the moment the consumer remove elements from the buffer, or the consumer may go to sleep and wake up at the moment the producer add elements to the buffer.

Another problem may exist when:

• The consumer goes to sleep and the producer adds elements in the empty buffer.

When the buffer is not empty anymore, the consumer must be called in order to wake up and get the elements from the buffer.

The problem is when the consumer never realizes the producer already added elements to the buffer because it is awaken and never receives the call. The producer may fill the buffer with elements and then go to sleep. Both of them will sleep forever.

To solve this problem and optimize the process we can use semaphores. A semaphore will regulate the production and the consuming of the buffer, giving access to only one process at a time.


PSEUDOCODE

THIS LINK IS AN API THAT EXPLAINS THE SOLUTION OF THE PROBLEM

DINING PHILOSOPHERS

The dining philosophers is a problem that consists of 5 philosophers sitting at a table with a bowl of pasta. There is a fork placed between each philosopher. Each one of them must think and eat. When they are thinking they can’t eat and when they’re eating they can’t think.

The problem is that In order to eat, they need to use 2 forks. Therefore, they can’t eat all at the same time.

We need to find an algorithm where all the philosophers can eat and think alternately. Everyone must have the chance to eat without starving.
Here is an applet we found that explains the problem and gives us an idea of the algorithm we can use to prevent starvation and deadlocks.

DINING PHILOSOPHERS APPLET

We found in a book (Sistemas operativos modernos) a possible solution to this problem
void filosofo(
{
while(TRUE){
thinking();
takeleft_fork()
takeright_fork()
eat()
leaveleft_fork()
leaveright_fork()
}
}


This is an incorrect solution because it may produce a deadlock
A deadlock is a problem that is formed when there is more than one lock and none of the processes can do anything because they are all waiting for another lock to be released. In this particular problem, a deadlock is formed when all of the philosophers are holding a fork and they are waiting for other lock to be released. There are no forks available anymore. They can’t eat because they need two forks. This is where starvation occurs.

Here are some things you can do in order to eliminate deadlocks

• Order the locks

We can establish a time for locks to occur

• Use the TryAcquire

In the TryAcquire operation, the process tries to acquire the lock. If the lock is acquired there is no problem. If the lock is not acquired then the process will need to release all of their locks in order to let the others processes finish and release their locks (they are also waiting for locks to be released.

• We can also release all the locks that are after the lock we want to acquire. After releasing all the locks we can reacquire them in the right order.

Solution

We found in the book Sistemas Operativos Modernos a program that presents a solution to this particular problem
Ths progam uses an array named STATE to know whether the philosopher is eating, thinking or hungry (trying to acquire forks). philosopher can only eat if no one is eating.
The i neighboors of a philosopher are defined by the variables LEFT and RIGHT (if i=2 then LEFT=1 and RIGHT=3)
The program uses an array of semaphores, one for each philosopher. Hungry philosophers may block if the forks they need are already acquired by another philospher.

SR ALGORITHM
There are three components of the time used in a process:

• Spinning: It’s the time the thread takes to check whether the lock is available or not. During this time the process is not executing.
• Suspending: Is the amount of time the thread is suspended or sleeping, waiting for the lock to be available
• Resuming: Is the amount of time the thread takes to restart the execution after acquiring the lock

The optimal algorithm occurs when:

• the lock is released in less than the suspend and resume time, the process spins until it acquires the lock.

• the lock is released in more than the suspend and resume time, the process should suspend immediately.

In the case of other algorithms that spin for a different fixed amount of time and then suspend.

• if it spins for less than suspend and resume time, then suspend. The worst case is when lock is free after a thread start the suspension. The algorithm will cost the time of suspend and resume plus spinning time. In SR algorithm will cost just the spinning time.
• if it spins for more than suspend and resume time, then suspend. The worst case is when lock is free after a thread start the suspension. The SR algorithm will cost the suspend and resume time but will spin less time than this algorithm.

Bibliography

• Sistemas Operativos Modernos, Andrew S. Tanenbaum, 3rd Ed, Prentice Hall.
• Martin Rinard OS Notes
• Dining philosophers image