lunes, 12 de septiembre de 2011

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




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.
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

5 comentarios:

  1. Una posible solución para los filosofos seria ponerlos a comer de dos en dos, cuando son un número par de filosofos no hay problema por que todos comen en dos turnos, si el número de filososfos es impar entonces k-1 filosofos comen en dos turnos (k es el número de filosofos) y si cada dos turnos cambiamos el inicio de la secuencia de comer de dos turnos al filosofo que no ha comido entonces en k vueltas de dos turnos habran comido k-1 veces los k filosofos.
    Esa podría ser una solución al problema para evitar el ponerlos aleatorios.

    ResponderEliminar
  2. si, en el pseudocodigo del problema de los filosofos que acabamos de publicar viene algo parecido a lo que nos comentaste. Muchas gracias por la observacion

    ResponderEliminar
  3. Se supone que los filósofos deben poder comer en el ritmo que se les de la gana, o sea, no que se les imponga "turnos". La bronca es poner los candados y realizar el scheduling para que se pueda hacer eso.

    ResponderEliminar
  4. +1 partial English
    +1 slides in English
    +1 visualization in slides
    +1 PC (you say unbounded, but then talk about a bounded buffer)
    +2 DF
    +2 SR
    => 8 puntos

    ResponderEliminar
  5. Muy buena tu presentación, me gusto como implementaron todas esas imagenes para poder dar una buena explicación.En el blog estaria bien que uses SyntaxHighlighter para que se vea bonito el código :)

    ResponderEliminar