Dining philosophers

Dining philosophers
You are encouraged to solve this task according to the task description, using any language you may know.

The dining philosophers problem illustrates non-composability of low-level synchronization primitives like semaphores. It is a modification of a problem posed by Edsger Dijkstra.

Five philosophers, Aristotle, Kant, Spinoza, Marx, and Russell (the tasks) spend their time thinking and eating spaghetti. They eat at a round table with five individual seats. For eating each philosopher needs two forks (the resources). There are five forks on the table, one left and one right of each seat. When a philosopher cannot grab both forks it sits and waits. Eating takes random time, then the philosopher puts the forks down and leaves the dining room. After spending some random time thinking about the nature of the universe, he again becomes hungry, and the circle repeats itself.

It can be observed that a straightforward solution, when forks are implemented by semaphores, is exposed to deadlock. There exist two deadlock states when all five philosophers are sitting at the table holding one fork each. One deadlock state is when each philosopher has grabbed the fork left of him, and another is when each has the fork on his right.

There are many solutions of the problem, program at least one, and explain how the deadlock is prevented.

Ada

Array of mutexes

Library: Simple components for Ada

The following solution uses an array of mutexes in order to model the forks. The forks used by a philosopher compose a subset in the array. When the the philosopher seizes his forks from the subset the array object prevents deadlocking since it is an atomic operation. <lang ada>with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random; with Ada.Text_IO; use Ada.Text_IO;

with Synchronization.Generic_Mutexes_Array;

procedure Test_Dining_Philosophers is

  type Philosopher is (Aristotle, Kant, Spinoza, Marx, Russel);
  package Fork_Arrays is new Synchronization.Generic_Mutexes_Array (Philosopher);
  use Fork_Arrays;

  Life_Span : constant := 20;    -- In his life a philosopher eats 20 times
  Forks : aliased Mutexes_Array; -- Forks for hungry philosophers
  
  function Left_Of (Fork : Philosopher) return Philosopher is
  begin
     if Fork = Philosopher'First then
        return Philosopher'Last;
     else
        return Philosopher'Pred (Fork);
     end if;
  end Left_Of;

  task type Person (ID : Philosopher);
  task body Person is
     Cutlery : aliased Mutexes_Set := ID or Left_Of (ID);
     Dice    : Generator;
  begin
     Reset (Dice);
     for Life_Cycle in 1..Life_Span loop
        Put_Line (Philosopher'Image (ID) & " is thinking");
        delay Duration (Random (Dice) * 0.100);
        Put_Line (Philosopher'Image (ID) & " is hungry");
        declare
           Lock : Set_Holder (Forks'Access, Cutlery'Access);
        begin
           Put_Line (Philosopher'Image (ID) & " is eating");
           delay Duration (Random (Dice) * 0.100);
        end;
     end loop;
     Put_Line (Philosopher'Image (ID) & " is leaving");
  end Person;

  Ph_1 : Person (Aristotle); -- Start philosophers
  Ph_2 : Person (Kant);
  Ph_3 : Person (Spinoza);
  Ph_4 : Person (Marx);
  Ph_5 : Person (Russel);

begin

  null; -- Nothing to do in the main task, just sit and behold

end Test_Dining_Philosophers;</lang>

Ordered mutexes

In the following solution forks are implemented as plain mutexes. The deadlock is prevented by ordering mutexes. Philosopher tasks seize them in same order 1, 2, 3, 4, 5. <lang ada>with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random; with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Dining_Philosophers is

  type Philosopher is (Aristotle, Kant, Spinoza, Marx, Russel);
  protected type Fork is
     entry Grab;
     procedure Put_Down;
  private
     Seized : Boolean := False;
  end Fork;
  protected body Fork is
     entry Grab when not Seized is
     begin
        Seized := True;
     end Grab;
     procedure Put_Down is
     begin
        Seized := False;
     end Put_Down;
  end Fork;
  
  Life_Span : constant := 20;    -- In his life a philosopher eats 20 times
  
  task type Person (ID : Philosopher; First, Second : not null access Fork);
  task body Person is
     Dice : Generator;
  begin
     Reset (Dice);
     for Life_Cycle in 1..Life_Span loop
        Put_Line (Philosopher'Image (ID) & " is thinking");
        delay Duration (Random (Dice) * 0.100);
        Put_Line (Philosopher'Image (ID) & " is hungry");
        First.Grab;
        Second.Grab;
        Put_Line (Philosopher'Image (ID) & " is eating");
        delay Duration (Random (Dice) * 0.100);
        Second.Put_Down;
        First.Put_Down;
     end loop;
     Put_Line (Philosopher'Image (ID) & " is leaving");
  end Person;

  Forks : array (1..5) of aliased Fork; -- Forks for hungry philosophers
                                        -- Start philosophers
  Ph_1 : Person (Aristotle, Forks (1)'Access, Forks (2)'Access);
  Ph_2 : Person (Kant,      Forks (2)'Access, Forks (3)'Access);
  Ph_3 : Person (Spinoza,   Forks (3)'Access, Forks (4)'Access);
  Ph_4 : Person (Marx,      Forks (4)'Access, Forks (5)'Access);
  Ph_5 : Person (Russel,    Forks (1)'Access, Forks (5)'Access);

begin

  null; -- Nothing to do in the main task, just sit and behold

end Test_Dining_Philosophers;</lang>

Host of the dining room

Both deadlocks happen when all philosophers are in the dining room. The following solution has a host of the room who chatters the last philosopher while four of them are in the room. So there are never more than four of them in there, which prevents deadlock. Now the forks can be picked up in a "wrong" order, i.e. the left one first. <lang ada>with Ada.Numerics.Float_Random; use Ada.Numerics.Float_Random; with Ada.Text_IO; use Ada.Text_IO;

procedure Test_Dining_Philosophers is

  type Philosopher is (Aristotle, Kant, Spinoza, Marx, Russel);
  
  protected type Fork is
     entry Grab;
     procedure Put_Down;
  private
     Seized : Boolean := False;
  end Fork;
  
  protected Host is
     entry Greet;
     procedure Farewell;
  private
     Guests : Natural := 0;
  end Host;

  protected body Fork is
     entry Grab when not Seized is
     begin
        Seized := True;
     end Grab;
     procedure Put_Down is
     begin
        Seized := False;
     end Put_Down;
  end Fork;

  protected body Host is
     entry Greet when Guests < 5 is
     begin
        Guests := Guests + 1;
     end Greet;
     procedure Farewell is
     begin
        Guests := Guests - 1;
     end Farewell;
  end Host;

  Life_Span : constant := 20;    -- In his life a philosopher eats 20 times
  
  task type Person (ID : Philosopher; Left, Right : not null access Fork);
  task body Person is
     Dice : Generator;
  begin
     Reset (Dice);
     for Life_Cycle in 1..Life_Span loop
        Put_Line (Philosopher'Image (ID) & " is thinking");
        delay Duration (Random (Dice) * 0.100);
        Put_Line (Philosopher'Image (ID) & " is hungry");
        Host.Greet;
        Left.Grab;
        Right.Grab;
        Put_Line (Philosopher'Image (ID) & " is eating");
        delay Duration (Random (Dice) * 0.100);
        Left.Put_Down;
        Right.Put_Down;
        Host.Farewell;
     end loop;
     Put_Line (Philosopher'Image (ID) & " is leaving");
  end Person;

  Forks : array (1..5) of aliased Fork; -- Forks for hungry philosophers
                                        -- Start philosophers
  Ph_1 : Person (Aristotle, Forks (1)'Access, Forks (2)'Access);
  Ph_2 : Person (Kant,      Forks (2)'Access, Forks (3)'Access);
  Ph_3 : Person (Spinoza,   Forks (3)'Access, Forks (4)'Access);
  Ph_4 : Person (Marx,      Forks (4)'Access, Forks (5)'Access);
  Ph_5 : Person (Russel,    Forks (5)'Access, Forks (1)'Access);

begin

  null; -- Nothing to do in the main task, just sit and behold

end Test_Dining_Philosophers;</lang>

C

This uses a modified version of the Python algorithm version below. Uses POSIX threads. <lang C>#include <pthread.h>

1. include <stdlib.h>
2. include <unistd.h>

typedef struct philData {

   pthread_mutex_t *fork_lft, *fork_rgt;
   const char *name;
   pthread_t thread;
   int   fail;

} Philosopher;

int running = 1;

void *PhilPhunction(Philosopher *phil ) {

   int failed;
   int tries_left;
   pthread_mutex_t *fork_lft, *fork_rgt, *fork_tmp;

   while (running) {
       printf("%s is sleeping --er thinking\n", phil->name);
       sleep( 1+ rand()%8);

       fork_lft = phil->fork_lft;
       fork_rgt = phil->fork_rgt;
       printf("%s is hungry\n", phil->name);
       tries_left = 2;   /* try twice before being forceful */
       do {
           failed = pthread_mutex_lock( fork_lft);
           failed = (tries_left>0)? pthread_mutex_trylock( fork_rgt )
                                  : pthread_mutex_lock(fork_rgt);
           if (failed) {
               pthread_mutex_unlock( fork_lft);
               fork_tmp = fork_lft;
               fork_lft = fork_rgt;
               fork_rgt = fork_tmp;
               tries_left -= 1;
           }
       } while(failed && running);

       if (!failed) {
           printf("%s is eating\n", phil->name);
           sleep( 1+ rand() % 8);
           pthread_mutex_unlock( fork_rgt);
           pthread_mutex_unlock( fork_lft);
       }
   }
   return NULL;

}

void Ponder() {

   const char *nameList[] = { "Kant", "Guatma", "Russel", "Aristotle", "Bart" };
   pthread_mutex_t forks[5];
   Philosopher philosophers[5];
   Philosopher *phil;
   int i;
   int failed;

   for (i=0;i<5; i++) {
       failed = pthread_mutex_init(&forks[i], NULL);
       if (failed) {
           printf("Failed to initialize mutexes.");
           exit(1);
       }
   }

   for (i=0;i<5; i++) {
       phil = &philosophers[i];
       phil->name = nameList[i];
       phil->fork_lft = &forks[i];
       phil->fork_rgt = &forks[(i+1)%5];
       phil->fail = pthread_create( &phil->thread, NULL, PhilPhunction, phil);
   }

   sleep(40);
   running = 0;
   printf("cleanup time\n");

   for(i=0; i<5; i++) {
       phil = &philosophers[i];
       if ( !phil->fail && pthread_join( phil->thread, NULL) ) {
           printf("error joining thread for %s", phil->name);
           exit(1);
       }
   }

}

int main() {

   Ponder();
   return 0;

}</lang>

Clojure

Clojure's STM allows us to avoid low-level synchronization primitives like semaphores. In order to simulate the Dining Philosophers scenario, the forks are references to a boolean indicating whether or not it is available for use. Each philosopher (also held in a ref) has a fixed amount of food he will try to eat, first by trying to acquire both forks, eating for some period of time, releasing both forks, then thinking for some period of time; if the forks cannot be acquired, the philosopher waits for a fixed amount of time and tries again. <lang lisp>(defn make-fork []

 (ref true))

(defn make-philosopher [name forks food-amt]

 (ref {:name name :forks forks :eating? false :food food-amt}))

(defn start-eating [phil]

 (dosync
   (if (every? true? (map ensure (:forks @phil)))  ; <-- the essential solution
     (do
       (doseq [f (:forks @phil)] (alter f not))
       (alter phil assoc :eating? true)
       (alter phil update-in [:food] dec)
       true)
     false)))

(defn stop-eating [phil]

 (dosync
   (when (:eating? @phil)
     (alter phil assoc :eating? false)
     (doseq [f (:forks @phil)] (alter f not)))))

(defn dine [phil retry-interval max-eat-duration max-think-duration]

 (while (pos? (:food @phil))
   (if (start-eating phil)
     (do
       (Thread/sleep (rand-int max-eat-duration))
       (stop-eating phil)
       (Thread/sleep (rand-int max-think-duration)))
     (Thread/sleep retry-interval))))</lang>

The second line of the start-eating function contains the essential solution: by invoking ensure on every fork reference, we are guaranteed that the state of the forks will not be modified by other transactions, thus we can rely on those values for the rest of the transaction. Now we just need to run it: <lang lisp>(def *forks* (cycle (take 5 (repeatedly #(make-fork)))))

(def *philosophers*

 (doall (map #(make-phil %1 [(nth *forks* %2) (nth *forks* (inc %2))] 1000)
             ["Kant" "Jasay" "Locke" "Nozick" "Rand"] 
             (range 5))))

(defn start []

 (doseq [phil * philosophers*] 
   (.start (Thread. #(dine phil 5 100 100)))))

(defn status []

 (dosync
   (doseq [i (range 5)]
     (let [f @(nth *forks* i)
           p @(nth *phils* i)]
       (println (str "fork: available=" f))
       (println (str (:name p) 
                     ": eating=" (:eating? p) 
                     " food=" (:food p)))))))</lang>

The status function inspects the data structures within a transaction so as to give consistent results (e.g., every unavailable fork has exactly one "eating" philosopher adjacent).

Common Lisp

Library: Bordeaux Threads

This is a translation of the Python solution with small improvements.

Random times are calculated based upon a normal distribution; the main loop doesn't sleep to wait for all philosophers to end dining, it uses a condition variable instead.

<lang lisp>(defvar *philosophers* '(Aristotle Kant Spinoza Marx Russell))

(defclass philosopher ()

 ((name :initarg :name :reader name-of)
  (left-fork :initarg :left-fork :accessor left-fork-of)
  (right-fork :initarg :right-fork :accessor right-fork-of)
  (meals-left :initarg :meals-left :accessor meals-left-of)))

(defclass fork ()

 ((lock :initform (make-lock "fork") :reader lock-of)))

(defun random-normal (&optional (mean 0.0) (sd 1.0))

 (do* ((x1 #1=(1- (* 2.0d0 (random 1d0))) #1#)
       (x2 #2=(1- (* 2.0d0 (random 1d0))) #2#)
       (w  #3=(+ (* x1 x1) (* x2 x2)) #3#))
     ((< w 1d0) (+ (* (* x1 (sqrt (/ (* -2d0 (log w)) w))) sd) mean))))

(defun sleep* (time) (sleep (max time (/ (expt 10 7)))))

(defun dining-philosophers (&key (philosopher-names *philosophers*)

                                (meals 30)
                                (dining-time'(1 2))
                                (thinking-time '(1 2))
                                ((stream e) *error-output*))
 (let* ((count (length philosopher-names))
        (forks (loop repeat count collect (make-instance 'fork)))
        (philosophers (loop for i from 0
                            for name in philosopher-names collect
                              (make-instance 'philosopher
                                   :left-fork (nth (mod i count) forks)
                                   :right-fork (nth (mod (1+ i) count) forks)
                                   :name name
                                   :meals-left meals)))
        (condition (make-condition-variable))
        (lock (make-lock "main loop")) 
        (output-lock (make-lock "output lock")))
   (dolist (p philosophers) 
     (labels ((think ()
                (/me "is now thinking")
                (sleep* (apply #'random-normal thinking-time))
                (/me "is now hungry")
                (dine))
              (dine ()
                (with-lock-held ((lock-of (left-fork-of p)))
                  (or (acquire-lock (lock-of (right-fork-of p)) nil)
                      (progn (/me "couldn't get a fork and ~
                                   returns to thinking")
                             (release-lock (lock-of (left-fork-of p)))
                             (return-from dine (think))))
                  (/me "is eating")
                  (sleep* (apply #'random-normal dining-time))
                  (release-lock (lock-of (right-fork-of p)))
                  (/me "is done eating (~A meals left)"
                       (decf (meals-left-of p))))
                (cond ((<= (meals-left-of p) 0)
                       (/me "leaves the dining room")
                       (with-lock-held (lock)
                         (setq philosophers (delete p philosophers))
                         (condition-notify condition)))
                      (t (think))))
              (/me (control &rest args)
                (with-lock-held (output-lock)
                  (write-sequence (string (name-of p)) e)
                  (write-char #\Space e)
                  (apply #'format e (concatenate 'string control "~%")
                         args))))
       (make-thread #'think))) 
   (loop (with-lock-held (lock)
           (when (endp philosophers)
             (format e "all philosophers are done dining~%") 
             (return)))
         (with-lock-held (lock)
           (condition-wait condition lock)))))</lang>

E

A classic article on solving a version of this problem in E is Satan Comes to Dinner in E.

Erlang

This solution avoids deadlock by employing a waiter that only serves a plate of spaghetti when a philosopher has access to two forks. The philosophers wait until a plate is put in front of them before grabbing the forks.

<lang erlang>-module(philosophers). -export([dining/0]).

sleep(T) ->

 receive

after T -> true end.

doForks(ForkList) ->

 receive

{grabforks, {Left, Right}} -> doForks(ForkList -- [Left, Right]); {releaseforks, {Left, Right}} -> doForks([Left, Right| ForkList]); {available, {Left, Right}, Sender} ->

         Sender ! {areAvailable, lists:member(Left, ForkList) andalso lists:member(Right, ForkList)},		     
         doForks(ForkList);

{die} -> io:format("Forks put away.~n")

 end.

areAvailable(Forks) -> forks ! {available, Forks, self()}, receive {areAvailable, false} -> false; {areAvailable, true} -> true end.

processWaitList([]) -> false; processWaitList([H|T]) -> {Client, Forks} = H, case areAvailable(Forks) of true -> Client ! {served}, true; false -> processWaitList(T) end.

doWaiter([], 0, 0, false) -> forks ! {die}, io:format("Waiter is leaving.~n"), diningRoom ! {allgone}; doWaiter(WaitList, ClientCount, EatingCount, Busy) -> receive {waiting, Client} -> WaitList1 = [Client|WaitList], %% add to waiting list case (not Busy) and (EatingCount<2) of true -> Busy1 = processWaitList(WaitList1); false -> Busy1 = Busy end, doWaiter(WaitList1, ClientCount, EatingCount, Busy1);

{eating, Client} -> doWaiter(WaitList -- [Client], ClientCount, EatingCount+1, false);

{finished} -> doWaiter(WaitList, ClientCount, EatingCount-1, processWaitList(WaitList)); {leaving} -> doWaiter(WaitList, ClientCount-1, EatingCount, Busy) end.

philosopher(Name, Forks, 0) -> io:format("~s is leaving.~n", [Name]),

waiter ! {leaving};

philosopher(Name, Forks, Cycle) -> io:format("~s is thinking.~n", [Name]), sleep(random:uniform(1000)),

io:format("~s is hungry.~n", [Name]), waiter ! {waiting, {self(), Forks}}, %%sit at table

receive {served}-> forks ! {grabforks, Forks}, %%grab forks waiter ! {eating, {self(), Forks}}, %%start eating io:format("~s is eating.~n", [Name]) end,

sleep(random:uniform(1000)), forks ! {releaseforks, Forks}, %% put forks down waiter ! {finished},

philosopher(Name, Forks, Cycle-1).

dining() -> AllForks = [1, 2, 3, 4, 5], Clients = 5, register(diningRoom, self()),

register(forks, spawn(fun()-> doForks(AllForks) end)), register(waiter, spawn(fun()-> doWaiter([], Clients, 0, false) end)), Life_span = 20, spawn(fun()-> philosopher('Aristotle', {5, 1}, Life_span) end), spawn(fun()-> philosopher('Kant', {1, 2}, Life_span) end), spawn(fun()-> philosopher('Spinoza', {2, 3}, Life_span) end), spawn(fun()-> philosopher('Marx', {3, 4}, Life_span) end), spawn(fun()-> philosopher('Russel', {4, 5}, Life_span) end),

receive

			{allgone} -> io:format("Dining room closed.~n")

end, unregister(diningRoom).</lang>

Haskell

Using the built-in Software Transactional Memory in GHC. <lang haskell>module Philosophers where

import Control.Monad import Control.Concurrent import Control.Concurrent.STM import System.Random

-- TMVars are transactional references. They can only be used in transactional actions. -- They are either empty or contain one value. Taking an empty reference fails and -- putting a value in a full reference fails. A transactional action only succeeds -- when all the component actions succeed, else it rolls back and retries until it -- succeeds. -- The Int is just for display purposes. type Fork = TMVar Int

newFork :: Int -> IO Fork newFork i = newTMVarIO i

-- The basic transactional operations on forks takeFork :: Fork -> STM Int takeFork fork = takeTMVar fork

releaseFork :: Int -> Fork -> STM () releaseFork i fork = putTMVar fork i

type Name = String

runPhilosopher :: Name -> (Fork, Fork) -> IO () runPhilosopher name (left, right) = forever $ do

 putStrLn (name ++ " is hungry.")
 
 -- Run the transactional action atomically.
 -- The type system ensures this is the only way to run transactional actions.
 (leftNum, rightNum) <- atomically $ do
   leftNum <- takeFork left
   rightNum <- takeFork right
   return (leftNum, rightNum)
 
 putStrLn (name ++ " got forks " ++ show leftNum ++ " and " ++ show rightNum ++ " and is now eating.")
 delay <- randomRIO (1,10)
 threadDelay (delay * 1000000) -- 1, 10 seconds. threadDelay uses nanoseconds.
 putStrLn (name ++ " is done eating. Going back to thinking.")

 atomically $ do
   releaseFork leftNum left
   releaseFork rightNum right
   
 delay <- randomRIO (1, 10)
 threadDelay (delay * 1000000)

philosophers :: [String] philosophers = ["Aristotle", "Kant", "Spinoza", "Marx", "Russel"]

main = do

 forks <- mapM newFork [1..5]
 let namedPhilosophers  = map runPhilosopher philosophers
     forkPairs          = zip forks (tail . cycle $ forks)
     philosophersWithForks = zipWith ($) namedPhilosophers forkPairs
 
 putStrLn "Running the philosophers. Press enter to quit."
 
 mapM_ forkIO philosophersWithForks
 
 -- All threads exit when the main thread exits.
 getLine

</lang>

Oz

Using first-class computation spaces as transactions on dataflow variables. Computations spaces are normally used to implement constraint search engines. But here we use them to bind two variables atomically.

<lang oz>declare

 Philosophers = [aristotle kant spinoza marx russell]
  
 proc {Start}
    Forks = {MakeList {Length Philosophers}}
 in
    {ForAll Forks NewFork}
    for
       Name in Philosophers
       LeftFork in Forks
       RightFork in {RightShift Forks}
    do
       thread
          {Philosopher Name LeftFork RightFork}
       end
    end
 end

 proc {Philosopher Name LeftFork RightFork}
    for do
       {ShowInfo Name#" is hungry."}
     
       {TakeForks [LeftFork RightFork]}
       {ShowInfo Name#" got forks."}
       {WaitRandom}
       {ReleaseFork LeftFork}
       {ReleaseFork RightFork}

       {ShowInfo Name#" is thinking."}
       {WaitRandom}
    end
 end

 proc {WaitRandom}
    {Delay 1000 + {OS.rand} mod 4000} %% 1-5 seconds
 end

 proc {TakeForks Forks}
    {ForAll Forks WaitForFork}
    case {TryAtomically proc {$}
                           {ForAll Forks TakeFork}
                        end}
    of true then
       {ForAll Forks InitForkNotifier}
    [] false then
       {TakeForks Forks}
    end
 end

 %%
 %% Fork type
 %%

 %% A fork is a mutable reference to a pair
 fun {NewFork}
    {NewCell
     unit(taken:_     %% a fork is taken by setting this value to a unique value
          notify:unit %% to wait for a taken fork

)}

 end

 proc {TakeFork F}
    (@F).taken = {NewName}
 end

 proc {InitForkNotifier F}
    %% we cannot do this in TakeFork
    %% because side effect are not allowed in subordinate spaces
    New Old
 in
    {Exchange F Old New}
    New = unit(taken:Old.taken notify:_)
 end

 proc {ReleaseFork F}
    New Old
 in
    {Exchange F Old New}
    New = unit(taken:_ notify:unit)
    Old.notify = unit %% notify waiters
 end

 proc {WaitForFork F}
    {Wait (@F).notify}  %% returns immediatly if fork is free, otherwise blocks
 end

 %%
 %% Helpers
 %%

 %% Implements transactions on data flow variables
 %% with computation spaces. Returns success.
 fun {TryAtomically P}
    try

S = {Space.new proc {$ Sync} {P} Sync = unit end}

    in

{Space.askVerbose S} \= failed = true {Wait {Space.merge S}} true

    catch _ then

false

    end
 end

 %% Calls Fun N times and returns the result as a list.
 fun {MakeN N Fun}
    case N of 0 then nil
    else {Fun}|{MakeN N-1 Fun}
    end
 end

 fun {RightShift Xs} %% circular
    case Xs of nil then nil
    else {Append Xs.2 [Xs.1]}
    end
 end

 ShowInfo = System.showInfo

in

 {Start}</lang>

Python

This solution avoids deadlock by never waiting for a fork while having one in hand. If a philosopher acquires one fork but can't acquire the second, he releases the first fork before waiting to acquire the other (which then becomes the first fork acquired). <lang python>import threading import random import time

1. Dining philosophers, 5 Phillies with 5 forks. Must have two forks to eat.
3. Deadlock is avoided by never waiting for a fork while holding a fork (locked)
4. Procedure is to do block while waiting to get first fork, and a nonblocking
5. acquire of second fork. If failed to get second fork, release first fork,
6. swap which fork is first and which is second and retry until getting both.
8. See discussion page note about 'live lock'.

class Philosopher(threading.Thread):

   running = True

   def __init__(self, xname, forkOnLeft, forkOnRight):
       threading.Thread.__init__(self)
       self.name = xname
       self.forkOnLeft = forkOnLeft
       self.forkOnRight = forkOnRight

   def run(self):
       while(self.running):
           #  Philosopher is thinking (but really is sleeping).
           time.sleep( random.uniform(3,13))
           print '%s is hungry.' % self.name
           self.dine()

   def dine(self):
       fork1, fork2 = self.forkOnLeft, self.forkOnRight

       while self.running:
           fork1.acquire(True)
           locked = fork2.acquire(False)
           if locked: break
           fork1.release()
           print '%s swaps forks' % self.name
           fork1, fork2 = fork2, fork1
       else:
           return

       self.dining()
       fork2.release()
       fork1.release()

   def dining(self):			
       print '%s starts eating '% self.name
       time.sleep(random.uniform(1,10))
       print '%s finishes eating and leaves to think.' % self.name

def DiningPhilosophers():

   forks = [threading.Lock() for n in range(5)]
   philosopherNames = ('Aristotle','Kant','Buddha','Marx', 'Russel')

   philosophers= [Philosopher(philosopherNames[i], forks[i%5], forks[(i+1)%5]) \
           for i in range(5)]

   random.seed(507129)
   Philosopher.running = True
   for p in philosophers: p.start()
   time.sleep(100)
   Philosopher.running = False
   print ("Now we're finishing.")

DiningPhilosophers()</lang>

Ruby

Translation of: Python

Works with: Ruby version 1.8.7

<lang ruby>require 'mutex_m'

class Philosopher

 def initialize(name, left_fork, right_fork)
   @name = name
   @left_fork = left_fork
   @right_fork = right_fork
   @meals = 0
 end

 def go
   while @meals < 5
     think
     dine
   end
   puts "philosopher #@name is full!"
 end

 def think
   puts "philosopher #@name is thinking..."
   sleep(rand())
   puts "philosopher #@name is hungry..."
 end

 def dine
   fork1, fork2 = @left_fork, @right_fork
   while true
     pickup(fork1, :wait => true)
     puts "philosopher #@name has fork #{fork1.fork_id}..."
     if pickup(fork2, :wait => false)
       break
     end
     puts "philosopher #@name cannot pickup second fork #{fork2.fork_id}..."
     release(fork1)
     fork1, fork2 = fork2, fork1
   end
   puts "philosopher #@name has the second fork #{fork2.fork_id}..."

   puts "philosopher #@name eats..."
   sleep(rand())
   puts "philosopher #@name belches"
   @meals += 1

   release(@left_fork)
   release(@right_fork)
 end

 def pickup(fork, opt)
   puts "philosopher #@name attempts to pickup fork #{fork.fork_id}..."
   opt[:wait] ? fork.mutex.mu_lock : fork.mutex.mu_try_lock
 end

 def release(fork)
   puts "philosopher #@name releases fork #{fork.fork_id}..."
   fork.mutex.unlock
 end

end

n = 5

Fork = Struct.new(:fork_id, :mutex) forks = Array.new(n) {|i| Fork.new(i, Object.new.extend(Mutex_m))}

philosophers = Array.new(n) do |i|

                Thread.new(i, forks[i], forks[(i+1)%n]) do |id, f1, f2|
                  ph = Philosopher.new(id, f1, f2).go
                end
              end
 

philosophers.each {|thread| thread.join}</lang>

Tcl

Works with: Tcl version 8.6

<lang tcl>package require Thread

foreach name {Aristotle Kant Spinoza Marx Russel} {

   lappend forks [thread::mutex create]
   lappend tasks [set t [thread::create -preserved {
       # Implement each task as a coroutine internally for simplicity of presentation
       # This is because we want to remain able to receive messages so we can shut
       # down neatly at the end of the program.

interp alias {} doTask {} coroutine t philosopher proc delay {expression} { yield [after [expr $expression] [info coroutine]] }

       # Forks are mutexes...
       proc pickUpFork fork {
           thread::mutex lock $fork
       }
       proc putDownFork fork {
           thread::mutex unlock $fork
       }

       # The actual implementation of the task

proc philosopher {f1 f2} { global name # Always acquire forks in order; prevents deadlock

           # Uses the "natural" order of the lexicographical order of the fork names

if {$f1 > $f2} {

               lassign [list $f1 $f2] f2 f1
           }

           # The classic "philosophers" loop

while {true} { puts "$name is thinking" delay {int(200*rand())}

puts "$name is hungry, getting fork in left hand" pickUpFork $f1 delay {int(2000*rand())} ;# Make deadlock likely if it is possible!

puts "$name is hungry, getting fork in right hand" pickUpFork $f2

puts "$name is eating" delay {int(2000*rand())}

puts "$name has finished eating; putting down forks" putDownFork $f2 putDownFork $f1

               delay 100

} } thread::wait

   }]]
   thread::send $t [list set name $name]

}

1. Set the tasks going

foreach t $tasks {f1 f2} {0 1 1 2 2 3 3 4 4 0} {

   thread::send -async $t [list \
           doTask [lindex $forks $f1] [lindex $forks $f2]]

}

1. Kill everything off after 30 seconds; that's enough for demonstration!

after 30000 puts "Completing..." foreach t $tasks {

   thread::send -async $t thread::exit

}</lang>

Visual Basic .NET

This has three modes.

• In the first mode a dead lock will occur if each philosopher picks up their left fork before any pick up their right.
• In the second mode each philosopher will put down their left fork if they cannot pick up their right. This is susceptible to live lock, where each philosopher keeps retrying but never makes any progress.
• In the third mode, each fork is numbered. The philosopher will always pick up a lower number fork before a higher number fork, thus preventing a dead-lock while guaranteeing forward progress.

<lang vbnet>Imports System.Threading Module Module1

  Public rnd As New Random

  Sub Main()
      'Aristotle, Kant, Spinoza, Marx, and Russel 
      Dim f1 As New Fork(1)
      Dim f2 As New Fork(2)
      Dim f3 As New Fork(3)
      Dim f4 As New Fork(4)
      Dim f5 As New Fork(5)

      Console.WriteLine("1: Deadlock")
      Console.WriteLine("2: Live lock")
      Console.WriteLine("3: Working")
      Select Console.ReadLine
          Case "1"
              Using _
                  Aristotle As New SelfishPhilosopher("Aristotle", f1, f2), _
                  Kant As New SelfishPhilosopher("Kant", f2, f3), _
                  Spinoza As New SelfishPhilosopher("Spinoza", f3, f4), _
                  Marx As New SelfishPhilosopher("Marx", f4, f5), _
                  Russel As New SelfishPhilosopher("Russel", f5, f1)

                  Console.ReadLine()
              End Using
          Case "2"
              Using _
                  Aristotle As New SelflessPhilosopher("Aristotle", f1, f2), _
                  Kant As New SelflessPhilosopher("Kant", f2, f3), _
                  Spinoza As New SelflessPhilosopher("Spinoza", f3, f4), _
                  Marx As New SelflessPhilosopher("Marx", f4, f5), _
                  Russel As New SelflessPhilosopher("Russel", f5, f1)

                  Console.ReadLine()
              End Using
          Case "3"
              Using _
                  Aristotle As New WisePhilosopher("Aristotle", f1, f2), _
                  Kant As New WisePhilosopher("Kant", f2, f3), _
                  Spinoza As New WisePhilosopher("Spinoza", f3, f4), _
                  Marx As New WisePhilosopher("Marx", f4, f5), _
                  Russel As New WisePhilosopher("Russel", f5, f1)

                  Console.ReadLine()
              End Using
      End Select
  End Sub

End Module</lang>

<lang vbnet>Class Fork

  Private ReadOnly m_Number As Integer
  Public Sub New(ByVal number As Integer)
      m_Number = number
  End Sub
  Public ReadOnly Property Number() As Integer
      Get
          Return m_Number
      End Get
  End Property

End Class</lang>

<lang vbnet>MustInherit Class PhilosopherBase

  Implements IDisposable

  Protected m_Disposed As Boolean
  Protected ReadOnly m_Left As Fork
  Protected ReadOnly m_Right As Fork
  Protected ReadOnly m_Name As String
  Public Sub New(ByVal name As String, ByVal right As Fork, ByVal left As Fork)
      m_Name = name
      m_Right = right
      m_Left = left
      Dim t As New Thread(AddressOf MainLoop)
      t.IsBackground = True
      t.Start()
  End Sub
  Protected Overridable Sub Dispose(ByVal disposing As Boolean)
      m_Disposed = True
  End Sub

  Public Sub Dispose() Implements IDisposable.Dispose
      Dispose(True)
      GC.SuppressFinalize(Me)
  End Sub
  Public ReadOnly Property Name() As String
      Get
          Return m_Name
      End Get
  End Property

  Public MustOverride Sub MainLoop()

End Class</lang>

Deadlock

<lang vbnet>Class SelfishPhilosopher

  Inherits PhilosopherBase
  Public Sub New(ByVal name As String, ByVal right As Fork, ByVal left As Fork)
      MyBase.New(name, right, left)
  End Sub

  Public Overrides Sub MainLoop()
      Do
          Console.WriteLine(Name & " sat down")
          SyncLock m_Left
              Console.WriteLine(Name & " picked up fork " & m_Left.Number)

              SyncLock m_Right
                  Console.WriteLine(Name & " picked up fork " & m_Right.Number)

                  Console.WriteLine(Name & " ate!!!!")

                  Console.WriteLine(Name & " put down fork " & m_Right.Number)
              End SyncLock

              Console.WriteLine(Name & " put down fork " & m_Left.Number)
          End SyncLock

          Console.WriteLine(Name & " stood up")

          Thread.Sleep(rnd.Next(0, 10000))
      Loop Until m_Disposed
  End Sub

End Class</lang>

Live Lock

<lang vbnet>Class SelflessPhilosopher

  Inherits PhilosopherBase

  Public Sub New(ByVal name As String, ByVal right As Fork, ByVal left As Fork)
      MyBase.New(name, right, left)
  End Sub

  Public Overrides Sub MainLoop()
      Do
          Console.WriteLine(Name & " sat down")
          Dim needDelay = False

TryAgain:

          If needDelay Then Thread.Sleep(rnd.Next(0, 10000))
          Try
              Monitor.Enter(m_Left)
              Console.WriteLine(Name & " picked up fork " & m_Left.Number)

              If Monitor.TryEnter(m_Right) Then
                  Console.WriteLine(Name & " picked up fork " & m_Right.Number)

                  Console.WriteLine(Name & " ate!!!!!!")

                  Console.WriteLine(Name & " put down fork " & m_Right.Number)
                  Monitor.Exit(m_Right)
              Else
                  Console.WriteLine(Name & " is going to wait")
                  needDelay = True
                  GoTo TryAgain
              End If
          Finally
              Console.WriteLine(Name & " put down fork " & m_Left.Number)
          End Try

          Console.WriteLine(Name & " stood up")

          Thread.Sleep(rnd.Next(0, 10000))

      Loop Until m_Disposed
  End Sub

End Class</lang>

Working

<lang vbnet>Class WisePhilosopher

  Inherits PhilosopherBase
  Public Sub New(ByVal name As String, ByVal right As Fork, ByVal left As Fork)
      MyBase.New(name, right, left)
  End Sub

  Public Overrides Sub MainLoop()
      Do
          Console.WriteLine(Name & " sat down")

          Dim first As Fork, second As Fork
          If m_Left.Number > m_Right.Number Then
              first = m_Left
              second = m_Right
          Else
              first = m_Right
              second = m_Left
          End If

          SyncLock first
              Console.WriteLine(Name & " picked up fork " & m_Left.Number)

              SyncLock second
                  Console.WriteLine(Name & " picked up fork " & m_Right.Number)

                  Console.WriteLine(Name & " ate!!!!")

                  Console.WriteLine(Name & " put down fork " & m_Right.Number)
              End SyncLock

              Console.WriteLine(Name & " put down fork " & m_Left.Number)
          End SyncLock

          Console.WriteLine(Name & " stood up")

          Thread.Sleep(rnd.Next(0, 10000))
      Loop Until m_Disposed
  End Sub

End Class</lang>