Dining philosophers: Difference between revisions
→{{header|Oz}}: Removed unused helper function |
|||
Line 717: | Line 717: | ||
catch _ then |
catch _ then |
||
false |
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 |
||
end |
end |
Revision as of 01:30, 14 February 2010
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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
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>
- include <stdlib.h>
- 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
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
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
- Dining philosophers, 5 Phillies with 5 forks. Must have two forks to eat.
- Deadlock is avoided by never waiting for a fork while holding a fork (locked)
- Procedure is to do block while waiting to get first fork, and a nonblocking
- acquire of second fork. If failed to get second fork, release first fork,
- swap which fork is first and which is second and retry until getting both.
- 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
<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
<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]
}
- 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]]
}
- 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>