Actor question: My philosophers are starving

Hi!

I tried to implement a solution to the Dining Philosophers problem with actors, but while things look promising first, after some time my philosophers are starving. I have next to zero experience with actors, so maybe one of you can spot my flaw.

/* The Chandy / Misra solution of the Dining Philosophers problem
 * http://en.wikipedia.org/wiki/Dining_philosophers_problem
 * http://www.cs.utexas.edu/users/misra/scannedPdf.dir/DrinkingPhil.pdf
 */

object philosophers {

  import scala.actors.Actor
  import Actor._
  import scala.util.Random
  import java.util.{Timer, TimerTask}

  val timer = new Timer
 
  case object Waiting 
  case object ReadyEating

  case class ForkRequest(philosopher:Philosopher)
  case class ForkFrom(philosopher:Philosopher)

  class Philosopher(val name:String) extends Actor {
    self =>

    class Forks {
      sealed trait Fork
      case object NoFork extends Fork
      case object DirtyFork extends Fork
      case object CleanFork extends Fork
      case object OccupiedFork extends Fork

      private var leftFork:Fork = if (name < leftNeighbor.name) DirtyFork else NoFork
      private var rightFork:Fork = if (name < rightNeighbor.name) DirtyFork else NoFork

      def tryToEat {
        if(leftFork != NoFork && rightFork != NoFork) {
          leftFork = OccupiedFork
          rightFork = OccupiedFork
          self.eat
        } 
      }

      def askForForks {
          if (leftFork == NoFork) {
              leftNeighbor ! ForkRequest(self)
              println(self.name + " asks " + leftNeighbor.name + " for a fork")
          }
          if (rightFork == NoFork) {
              rightNeighbor ! ForkRequest(self)
              println(self.name + " asks " + rightNeighbor.name + " for a fork")
        }  
      }
      
      def readyEating {
        leftFork = DirtyFork
        rightFork = DirtyFork
      }

      def tryToGive(philosopher:Philosopher) =
        if(philosopher == leftNeighbor && leftFork == DirtyFork) {
          leftFork = NoFork
          philosopher ! ForkFrom(self)
          true
        } else if(philosopher == rightNeighbor && rightFork == DirtyFork) {
          rightFork = NoFork
          philosopher ! ForkFrom(self)
          true
        } else false

      def receiveFork(philosopher:Philosopher) {
        if (philosopher == leftNeighbor && leftFork == NoFork) leftFork = CleanFork
        else if (philosopher == rightNeighbor && rightFork == NoFork) rightFork = CleanFork
        else error("Don't want this fork")
      }
    }

    lazy val forks = new Forks
    var pendingRequests:List[Philosopher] = Nil

    lazy val leftNeighbor:Philosopher = getLeftNeighbor(this)
    lazy val rightNeighbor:Philosopher = getRightNeighbor(this)

    def act(){
      loop {
        receive {
          case ForkRequest(philosopher) =>
            if (forks.tryToGive(philosopher))
              println(name + " gives " + philosopher.name + " a fork")
            else pendingRequests = philosopher :: pendingRequests
           
          case ForkFrom(philosopher) =>
            forks.receiveFork(philosopher)
            forks.tryToEat

          case Waiting =>
             println(name + " is hungry")
             forks.askForForks
             forks.tryToEat

          case ReadyEating =>
            println(name + " ate")
            forks.readyEating
            handlePendingRequests
            think
          case msg => error("unknown message " + msg)
        }
      }
    }

    def eat {
      println(name + " is eating")
      schedule(1000 + Random.nextInt(5000), this, ReadyEating)
    }

    def think {
      println(name + " thinks")
      schedule(1000 + Random.nextInt(5000), this, Waiting)
    }

    def schedule(ms:Long, actor:Actor, msg:Any) {
      timer.schedule(new TimerTask{ def run() { actor ! msg } }, ms)
    }
    
    def handlePendingRequests {
      pendingRequests = pendingRequests.foldLeft(List[Philosopher]()){ (list,neighbor) =>
        if (forks.tryToGive(neighbor)) {
          println(name + " gives " + neighbor.name + " a fork")
          list
        } else neighbor :: list
      }
    }

  }

  val philosophers = Array("Nietzsche", "Kant", "Feuerbach",
                           "Hegel", "Fichte").map(new Philosopher(_))

  def getLeftNeighbor(philosopher:Philosopher) =
    philosophers((philosophers.indexOf(philosopher) + 4) % 5)
  def getRightNeighbor(philosopher:Philosopher) =
    philosophers((philosophers.indexOf(philosopher) + 1) % 5)

  def main(args: Array[String]) {
    philosophers.foreach(_.start)
    philosophers.foreach(_.think)
  }

}

If I had to guess, I'd blame my quite stateful pendingRequests handling, but I'm not sure how to improve that part. Changing receive to react seems to let them starve just a little bit earlier.
BTW: Sorry for beeing "germanocentric" concerning the philosophers, but I think the names are not the problem :-)

Cheers, Daniel
View this message in context: Actor question: My philosophers are starving
Sent from the Scala - User mailing list archive at Nabble.com.

Hi Luc,

thanks for the pointer, I'll look into it. However, *my* philosophers
shouldn't starve, as I try to follow this paper:

http://www.cs.utexas.edu/users/misra/scannedPdf.dir/DrinkingPhil.pdf

They introduce clean and dirty forks, and prove that their "rules" can't
lead to starvation etc.

Cheers,
Daniel

Luc Duponcheel wrote:
>
> Daniel,
>
> is it not normal that the philosophers could be starving?
>
> what if they all take their 'left chopstick', resulting in a deadlock!
>
> ps:
>
> you may wish to have a look at
> http://lucdup.blogspot.com/2009/08/scala-spaces-as-scala-actors.html
> where I implement the dining philosophers using scala spaces
> (which themselves, are implemented using scala actors)
>
> Luc
>