Verhungernde Philosophen


Jeder, der sich mit paralleler Programmierung beschäftigt, sollte eigentlich schon einmal etwas vom Philosophenproblem gehört haben. Ich habe nicht nur davon gehört, ich verzweifle gerade daran, denn meine Philosophen verhungern am gedeckten Tisch.

Die englische Version des obigen Wikipedia-Artikels listet auch eine Lösungsmöglichkeit nach Chandy/Misra auf (die in diesem Papier vorgestellt wurde). Wikipedia fasst das ganze so zusammen:

1. For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID. Each fork can either be dirty or clean. Initially, all forks are dirty.
2. When a philosopher wants to use a set of resources (i.e. eat), he must obtain the forks from his contending neighbors. For all such forks he does not have, he sends a request message.
3. When a philosopher with a fork receives a request message, he keeps the fork if it is clean, but gives it up when it is dirty. If he sends the fork over, he cleans the fork before doing so.
4. After a philosopher is done eating, all his forks become dirty. If another philosopher had previously requested one of the forks, he cleans the fork and sends it.

Nun dachte ich in meinem jugendlichen (…ahem) Leichtsinn, dass eine Implementierung dieses Algorithmus ein perfekter Einstieg in die wundervolle Welt der Aktoren wäre, und tatsächlich lässt sich das Verfahren gut mit Aktoren umsetzen. Nur verhungern meine Philosophen trotzdem, und besonders grämt mich, dass mit Friedrich Nietzsche auch mein persönlicher Favorit betroffen ist (und das, wo doch sein Grab in Röcken nur haarscharf den Braunkohlebaggern entkommen ist).

Was hat es nun mit den Aktoren auf sich? Wer sich jemals in den Low-Level-Untiefen der Java-Synchronisation begeben hat, weiss sicher ein Lied von der Komplexität paralleler Anwendungen zu singen. Selbst wenn etwas „läuft“, heißt es noch lange nicht, dass es auch wirklich korrekt ist. Eine andere CPU, eine andere JVM oder ein paar parallele Zugriffe mehr können Probleme zu Tage fördern, die auf dem Entwickler-Rechner nicht auftreten. Nun kann man versuchen, das Chaos durch High-Level-Konstrukte zu zähmen, wie etwa das Java Executor Framework. Oder man geht dem Problem auf den Grund, denn die letztendliche Ursache der unüberschaubaren Komplexität ist die schlichte Tatsache, dass sich mehrere parallele Prozesse gemeinsamen Speicher teilen. Semaphore und Locks sind die grimmigen Wächter dieser brodelnden Hölle herrenlosen Speichers.

Die funktionalen Sprachen – allen voran Erlang – haben eine andere Lösung zur Realisierung von Parallelität gefunden: unveränderliche Botschaften. Wenn ich einem anderen Prozess eine unveränderliche Liste sende, kann ich sie ohne Probleme weiterverwenden – sie ist ja unveränderlich. Und so wurde das Aktor-Konzept entwickelt, bei dem jeder Aktor unabhängig von den anderen läuft, und nur über unveränderliche Botschaften kommuniziert. Aktoren sehen dementsprechend ein bisschen so aus wie Server, die in einer Endlosschleife an IP-Ports lauschen. Natürlich sind Aktoren nicht die Antwort auf alle Parallelitäts-Probleme, aber sie haben viele Vorteile gegenüber Threads. Beispielsweise kann man Aktoren mit Threads implementieren, muss es aber nicht. Andere Techniken wie eventbasierte Implementierungen erlauben es, dass Tausende von Aktoren gleichzeitig aktiv sein können, und das auf ganz normaler Hardware. Scala hat sich bei den Aktoren an Erlang (wo sie fester Bestandteil der Sprache sind) orientiert und bringt eine Standard-Aktor-Bibliothek mit. Diese soll für Scala 2.8 verbessert werden, es gibt aber auch andere Implementierungen (z.B. hat das Lift-Webframework vor kurzem auf eine eigene Variante gewechselt).

Damit das aber alles etwas anschaulicher wird, hier mein gescheiterter Code. Vielleicht hat ja noch jemand eine zündende Idee, wie wir Nietzsche und seine Freunde vor dem Verhungern retten können…

//Scala 2.8
//THIS CODE IS BROKEN, PHILOSOPHERS WILL STARVE
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 =>

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

    val requests = Array(false, false)

    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 handlePendingRequests {
        if(requests(0) && leftFork == DirtyFork) {
          leftFork = NoFork
          requests(0) = false
          leftNeighbor ! ForkFrom(self)
        } 
        if(requests(1) && rightFork == DirtyFork) {
          rightFork = NoFork
          requests(1) = false
          rightNeighbor ! ForkFrom(self)
        } 
      }

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

      def forkCount = (if (leftFork == NoFork) 0 else 1)+
                      (if (rightFork == NoFork) 0 else 1)
    }


    def act(){
      loop {
        receive {
          case ForkRequest(philosopher) =>
            if (philosopher == leftNeighbor)  requests(0) = true
            else if (philosopher == rightNeighbor) requests(1) = true
            else error ("Dunno that guy")
            forks.handlePendingRequests
           
          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
            forks.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 forkCount = forks.forkCount
  }

  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)

    //just a check that we don't lose any forks
    timer.scheduleAtFixedRate(new TimerTask{ def run() {
         println("" + philosophers.map(_.forkCount).reduceLeft(_+_) + " forks.") }
    }, 0, 5000)
  }
}

Als Einführung zu Aktoren sollte man natürlich nicht unbedingt ein verbuggtes Code-Fragment wie dieses heranziehen. Ich empfehle stattdessen Scala Actors: A Short Tutorial (es gibt auch die Beispiele message.scala und pingpong.scala). Tiefere Einblicke sollte das Buch Programming Scala: Tackle Multi-Core Complexity on the Java Virtual Machine vermitteln.

Viel Spaß beim Experimentieren und hoffentlich keine virtuelle Mangelernährung!

Advertisements

3 Gedanken zu “Verhungernde Philosophen

  1. Das Problem ist, dass ein Philosoph, der hungrig ist und nur eine (benutzte) Gabel hat, diese an seinen Nachbarn abgibt, wenn dieser danach verlangt, ohne sie aber wieder zurückzuverlangen. In diesem Zustand verhungert er.

    Dies kann gelöst werden indem man im Philosophen eine Zustandsvariable

        var hungry = false;
    

    definiert, die man im „case Waiting“ auf true und vor dem Aufruf von self.eat auf false setzt.

    Falls der Nachbar eine Gabel verlangt, dann fordert man diese gleich wieder zurück. Da sie jedoch sauber ist erhält man sie erst, wenn der Nachbar damit gegessen hat:

          def handlePendingRequests {
            if(requests(0) && leftFork == DirtyFork) {
              leftFork = NoFork
              requests(0) = false
              leftNeighbor ! ForkFrom(self)
              if (hungry) {
                  leftNeighbor ! ForkRequest(self)
                  println(self.name + " asks " + leftNeighbor.name + " for a fork")
              }
            }
            ...
    

    Liebe Grüsse, Dominik

  2. Vielen Dank, das probiere ich dieses Wochenende aus! Ich war wirklich frustriert, als ich das damals geschrieben hatte und den Bug einfach nicht finden konnte.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s