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

### Array of mutexes

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);
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

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);
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);
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;
int   fail;
```

} Philosopher;

int running = 1;

void *PhilPhunction(Philosopher *phil ) {

```   int failed;
int tries_left;
```
```   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 = (tries_left>0)? pthread_mutex_trylock( fork_rgt )
if (failed) {
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);
}
}
return NULL;
```

}

void Ponder() {

```   const char *nameList[] = { "Kant", "Guatma", "Russel", "Aristotle", "Bart" };
Philosopher philosophers[5];
Philosopher *phil;
int i;
int failed;
```
```   for (i=0;i<5; i++) {
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];
}
```
```   sleep(40);
running = 0;
printf("cleanup time\n");
```
```   for(i=0; i<5; i++) {
phil = &philosophers[i];
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 clojure>(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
(stop-eating phil)
```

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 clojure>(def *forks* (cycle (take 5 (repeatedly #(make-fork)))))

(def *philosophers*

``` (doall (map #(make-philosopher %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 *philosophers* 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

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))))
(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),

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

end, unregister(diningRoom).</lang>

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)
putStrLn (name ++ " is done eating. Going back to thinking.")
```
``` atomically \$ do
releaseFork leftNum left
releaseFork rightNum right

delay <- randomRIO (1, 10)
```

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

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
{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
```
``` fun {RightShift Xs} %% circular
case Xs of nil then nil
else {Append Xs.2 [Xs.1]}
end
end
```
``` ShowInfo = System.showInfo
```

in

``` {Start}</lang>
```

## PicoLisp

This following solution uses the built-in fininte state machine function 'state'. Deadlocks are avoided, as each philosopher releases the first fork if he doesn't succeed to obtain the second fork, and waits for a random time.

Another solution, using the Chandy/Misra method, can be found here. <lang PicoLisp>(de dining (Name State)

```  (loop
(prinl Name ": " State)
(state 'State                       # Dispatch according to state
(thinking 'hungry)               # If thinking, get hungry
(hungry                          # If hungry, grab random fork
(if (rand T)
(and (acquire leftFork) 'leftFork)
(and (acquire rightFork) 'rightFork) ) )
(hungry 'hungry                  # Failed, stay hungry for a while
(wait (rand 1000 3000)) )
(leftFork                        # If holding left fork, try right one
(and (acquire rightFork) 'eating)
(wait 2000) )                 # then eat for 2 seconds
(rightFork                       # If holding right fork, try left one
(and (acquire leftFork) 'eating)
(wait 2000) )                 # then eat for 2 seconds
((leftFork rightFork) 'hungry    # Otherwise, go back to hungry,
(release (val State))         # release left or right fork
(wait (rand 1000 3000)) )     # and stay hungry
(eating 'thinking             # After eating, resume thinking
(release leftFork)
(release rightFork)
(wait 6000) ) ) ) )           # for 6 seconds
```

(setq *Philosophers

```  (maplist
'((Phils Forks)
(let (leftFork (tmp (car Forks))  rightFork (tmp (cadr Forks)))
(or
(fork)  # Parent: Collect child process IDs
(dining (car Phils) 'hungry) ) ) )  # Initially hungry
'("Aristotle" "Kant" "Spinoza" "Marx" "Russell")
'("ForkA" "ForkB" "ForkC" "ForkD" "ForkE" .) ) )
```

(push '*Bye '(mapc kill *Philosophers)) # Terminate all upon exit</lang> Output:

```Aristotle: hungry
Aristotle: rightFork
Kant: hungry
Kant: rightFork
Spinoza: hungry
Spinoza: rightFork
Marx: hungry
Marx: rightFork
Russell: hungry
Marx: hungry
Spinoza: hungry
Kant: hungry
Russell: hungry
Aristotle: eating
...```

## PureBasic

My Philosophers are very polite, if one can not get both forks they then put down the first and waits a few breaths, that boldly tries in the opposite order.

When compiled for Windows x86 using PureBasic 4.41 , this code is only 11 kB.

<lang PureBasic>Macro Tell(Mutex, Message) ; Make a macro to easy send info back to main thread

``` LockMutex(Mutex)
LastElement(Queue())
Queue() = Message
SignalSemaphore(Semaphore)
UnlockMutex(Mutex)
```

EndMacro

Set up a data structure to pass needed info into the threads

``` Name.s
fork1.i
fork2.i
```

EndStructure

Declare function to be used

Declare.i TryFork(n) Declare PutDownFork(n) Declare Invite(Namn.s, Fork1, Fork2) Declare _philosophers(*arg.Thread_Parameters)

Global Semaphore = CreateSemaphore() Global Mutex1 = CreateMutex() ; Eg. fork 1 Global Mutex2 = CreateMutex() ; Eg. fork 2 Global Mutex3 = CreateMutex() ; Eg. fork 3 Global Mutex4 = CreateMutex() ; Eg. fork 4 Global Mutex5 = CreateMutex() ; Eg. fork 5 Global Mutex_main = CreateMutex() ; locking communication with the main thread which do all output. Global NewList Queue.s()

If OpenConsole()

``` Invite("Aristotle",1,2)  ; Get all Philosophers activated
Invite("Kant",     2,3)
Invite("Spinoza",  3,4)
Invite("Marx",     4,5)
Invite("Russell",  5,1)
CompilerIf #PB_Compiler_OS=#PB_OS_Windows
SetConsoleTitle_("Dining philosophers, by Jofur")   ; Using a Windows-API here, so checking before
CompilerEndIf
; Wait and see if any Philosophers want to tell me anything
Repeat
WaitSemaphore(Semaphore)
LockMutex(Mutex_main)
ForEach Queue()
PrintN( Queue() )  ; Print what the Philosopher(s) told me
i-1
Next Queue()
ClearList(Queue())
UnlockMutex(Mutex_main)
ForEver
```

EndIf

Procedure TryFork(n)  ; Se is fork #n is free and if so pick it up

``` Select n
Case 1: ProcedureReturn TryLockMutex(Mutex1)
Case 2: ProcedureReturn TryLockMutex(Mutex2)
Case 3: ProcedureReturn TryLockMutex(Mutex3)
Case 4: ProcedureReturn TryLockMutex(Mutex4)
Default:ProcedureReturn TryLockMutex(Mutex5)
EndSelect
```

EndProcedure

Procedure PutDownFork(n) ; put down fork #n and free it to be used by neighbors.

``` Select n
Case 1: UnlockMutex(Mutex1)
Case 2: UnlockMutex(Mutex2)
Case 3: UnlockMutex(Mutex3)
Case 4: UnlockMutex(Mutex4)
Default:UnlockMutex(Mutex5)
EndSelect
```

EndProcedure

Procedure Invite(Namn.s, Fork1, Fork2)

``` Protected *arg.Thread_Parameters ;create the structure containing the parameters
*arg\Name = Namn
*arg\fork1 = Fork1
*arg\fork2 = Fork2
```

EndProcedure

``` Protected Iam.s=*arg\Name, j=*arg\fork1, k=*arg\fork2
Protected f1, f2
FreeMemory(*arg)
;
Repeat
Tell(Mutex_main,Iam+": Going to the table")
Repeat          ;Trying to get my two forks
f1=TryFork(j)
If f1
f2=TryFork(k)
If Not f2   ; I got only one fork
PutDownFork(j)
f1=0
EndIf
EndIf
If Not f2
Delay(Random(100))  ; Take a short breath, then try the forks in the other order
Swap j,k
EndIf
Until f1 And f2
Tell(Mutex_main,Iam+": I have fork #"+Str(j)+" & #"+Str(k)+" and I'm eating now")
Delay(Random(1500)+15)
Tell(Mutex_main,Iam+": release fork #"+Str(j)+" & #"+Str(k)+"")
Delay(Random(45)+15)
PutDownFork(j)
PutDownFork(k)
f1=0:f2=0
Tell(Mutex_main,Iam+": Thinking about the nature of the universe...")
Delay(Random(2500)+25)
ForEver
```

EndProcedure</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.
2. Deadlock is avoided by never waiting for a fork while holding a fork (locked)
3. Procedure is to do block while waiting to get first fork, and a nonblocking
4. acquire of second fork. If failed to get second fork, release first fork,
5. swap which fork is first and which is second and retry until getting both.
6. See discussion page note about 'live lock'.

```   running = True
```
```   def __init__(self, xname, forkOnLeft, forkOnRight):
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>

This program simulates the dining of the philosophers. This solution does not utilize threading so it might be more "readable". 'speed' parameter specifies time range of eating and resting.

Each seat i have two fork (i) and fork (i+1), i.e. seat 0 has fork 0 and fork 1, and seat 4 has fork 4 and fork 0. When the seat is occupied, corresponding forks will be held by the person if available. The number of forks (fork_count) held by the person in the seat is counted and updated every time unit.

Individual philosophers has one's timer (timer). If he's timer is expired, he either tries to take a seat, or if he was eating, he will take a rest.

When the program is executed, it yields a state of dining, forks, timer, and the state flag.

<lang python>""" Author: Lee Seongjoo (seongjoo.lee@gmail.com) Dept. of Computer Science at Yonsei University, Korea """

import numpy as np from random import randint import time

def dining_phils(speed=5):

```   """
The dining of philosophers
speed: time range of eating and resting
Last updated: 31 Mar 2010
"""
```
```   dining = [0,0,0,0,0] # dining status
forks = [0,0,0,0,0] # initially un-used
fork_count = [0,0,0,0,0] # number of forks for each philosophers
timer= np.array([0,0,0,0,0]) # timer for eating and resting

while True:
state_flag = 0 # state change flag initialized
# update timer with time ticks
timer -= 1
timer *= timer >0

for seat in range(len(dining)):
# if timer is expired for a philosopher
if timer[seat]==0:
# when the seat is empty
if dining[seat]==0:
# pick up avialable forks
if forks[seat]==0:
forks[seat]=1
fork_count[seat] += 1
if forks[(seat+1)%5]==0:
forks[(seat+1)%5]=1
fork_count[seat] += 1

# if both forks picked up
# start dining
if fork_count[seat]==2:
dining[seat], state_flag = 1, 1
timer[seat] = randint(1,speed)
print "one who seats at %d starts dining:" % seat
continue # move onto the next seat

# when finish eating
if dining[seat]:
# take a rest thinking about the universe
dining[seat], state_flag = 0, 1
fork_count[seat], forks[seat], forks[(seat+1)%5] = 0,0,0
timer[seat] = randint(1,speed)
print "one who seated at %d takes rest" % seat
continue # move onto the next seat

yield dining, forks, timer, state_flag</lang>
```

In order to test the program, below simulation execution program is one way of doing it. You can set the speed of the simulation speed by specifying speed and sleeptime, initially set as 5 and 0.5 sec, respectively. 'speed' parameter specifies time range of eating and resting. 'sleeptime' parameter specifies the sleep time of each execution of the simulation.

The result will be displayed in below manner:

one who seats at 0 start dining

one who seated at 3 takes rest

[1, 0, 0, 1, 0], total diner: 2

<lang python>import time def simulation(speed=5, sleeptime=0.5):

```   d = dining_phils(speed)

while 1:
dining, forks, _, state_flag = d.next()
# when all forks in use but no one is dining

for seat in range(len(dining)):
exit(1)

if state_flag:
print dining, ", total diner: %d" % sum(dining)
print '-'*30
time.sleep(sleeptime)</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

```

## Tcl

Works with: Tcl version 8.6

foreach name {Aristotle Kant Spinoza Marx Russel} {

```   lappend forks [thread::mutex create]
# 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 {
}
proc putDownFork 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::send \$t [list set name \$name]
```

}

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.

```  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")
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
Public Sub New(ByVal name As String, ByVal right As Fork, ByVal left As Fork)
m_Name = name
m_Right = right
m_Left = left
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>

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