miércoles, 14 de septiembre de 2011

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!

5 comentarios:

  1. Esta muy solito el blog :)
    Pero me gusto su presentación, bastante original ya que... ESTA EN PYTHON!!!

    Sería bueno poner alguna referencia externa (si la usaron) para contribuir a nuestra comunidad. :)

    ResponderEliminar
  2. Gracias por subir el código, a mi no me salio bien la implementacion de los filósofos, creo que con este me puedo hacer de una idea.

    Solo me queda la duda.. porque en python y no c++ para ejecutarse en nachos?

    ResponderEliminar
  3. Pues charlie las soluciones las obtuve de wikipedia:
    http://es.wikipedia.org/wiki/Problema_de_la_cena_de_los_fil%C3%B3sofos
    http://en.wikipedia.org/wiki/Dining_philosophers_problem

    Viene la descripcion y pues las soluciones son sipmles y yo supongo que conocidas me parecieron bien para los ejemplos :).

    ResponderEliminar
  4. Y para ever estaba un poco corto de tiempo para hacer los ejemplos y en pyhon no tengo que lidiar con liosos punteros o cosas asi, python me ofrecía todo lo que necesitaba en su librería de threading y me hubiera hecho mas sencilla la parte de añadirle graficos pero no lo hize por que estaba corto de tiempo :) me da gusto que te haya servido :)

    ResponderEliminar
  5. Aquí hubiera sido bueno usar syntax highlight y números de línea también. Y un chequeador de ortografía ;)

    ResponderEliminar