Dining philosophers: Difference between revisions
m
→{{header|Wren}}: Changed to Wren S/H
m (→{{header|Wren}}: Changed to Wren S/H) |
|||
| (43 intermediate revisions by 19 users not shown) | |||
Line 13:
{{libheader|Simple components for Ada}}
The following solution uses an array of [[mutex]]es 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.
<
with Ada.Text_IO; use Ada.Text_IO;
Line 62:
begin
null; -- Nothing to do in the main task, just sit and behold
end Test_Dining_Philosophers;</
===Ordered mutexes===
In the following solution forks are implemented as plain [[mutex]]es. The deadlock is prevented by ordering mutexes. Philosopher tasks seize them in same order 1, 2, 3, 4, 5.
<
with Ada.Text_IO; use Ada.Text_IO;
Line 117:
begin
null; -- Nothing to do in the main task, just sit and behold
end Test_Dining_Philosophers;</
===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.
<
with Ada.Text_IO; use Ada.Text_IO;
Line 194:
begin
null; -- Nothing to do in the main task, just sit and behold
end Test_Dining_Philosophers;</
=={{header|AutoHotkey}}==
Line 202:
Starvation will only occur if one (or more) of the philosophers never stops eating.
Try changing EnoughForks to 4 and fork supply per philosopher to 2.
<
SetWorkingDir, %A_ScriptDir%
FileDelete, output.txt
Line 343:
CurrentWaitCount++
}
}</
{{out}}
<pre style="height:40ex;overflow:scroll">Aristotle is hungry.
Line 447:
⋮</pre>
=={{header|
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
This avoids deadlocks using the same strategy as the C solution (one of the philosophers picks up the left fork first).
<
nSeats% = 5
Line 515 ⟶ 516:
PROC_killtimer(tID%(I%))
NEXT
ENDPROC</
'''Sample output:'''
<pre>
Line 552 ⟶ 553:
=={{header|C}}==
Avoid deadlocks by making each philosopher have a different order of picking up forks. As long as one person waits for left fork first and another waits for right first, cycles can't form.
<
#include <stdio.h>
#include <stdlib.h>
Line 646 ⟶ 647:
/* wait forever: the threads don't actually stop */
return pthread_join(tid[0], 0);
}</
This uses a modified version of the Python algorithm version below. Uses POSIX threads.
<
#include <stdio.h>
#include <stdlib.h>
Line 742 ⟶ 743:
Ponder();
return 0;
}</
This version uses C11 threads and the approach of making one of the philosophers left-handed to avoid deadlock.
<
#include <threads.h>
#include <stdlib.h>
Line 805 ⟶ 806:
return 0;
}
</syntaxhighlight>
=={{header|C sharp|C#}}==
<
using System;
using System.Collections.Generic;
Line 1,444 ⟶ 1,058:
class Fork { }
}
</syntaxhighlight>
=={{header|C++}}==
Uses C++17
<syntaxhighlight lang="cpp">#include <algorithm>
#include <array>
#include <chrono>
#include <iostream>
#include <mutex>
#include <random>
#include <string>
#include <string_view>
#include <thread>
const int timeScale = 42; // scale factor for the philosophers task duration
void Message(std::string_view message)
{
// thread safe printing
static std::mutex cout_mutex;
std::scoped_lock cout_lock(cout_mutex);
std::cout << message << std::endl;
}
struct Fork {
std::mutex mutex;
};
struct Dinner {
std::array<Fork, 5> forks;
~Dinner() { Message("Dinner is over"); }
};
class Philosopher
{
// generates random numbers using the Mersenne Twister algorithm
// for task times and messages
std::mt19937 rng{std::random_device {}()};
const std::string name;
Fork& left;
Fork& right;
std::thread worker;
void live();
void dine();
void ponder();
public:
Philosopher(std::string name_, Fork& l, Fork& r)
: name(std::move(name_)), left(l), right(r), worker(&Philosopher::live, this)
{}
~Philosopher()
{
worker.join();
Message(name + " went to sleep.");
}
};
void Philosopher::live()
{
for(;;) // run forever
{
{
//Aquire forks. scoped_lock acquires the mutexes for
//both forks using a deadlock avoidance algorithm
std::scoped_lock dine_lock(left.mutex, right.mutex);
dine();
//The mutexes are released here at the end of the scope
}
ponder();
}
}
void Philosopher::dine()
{
Message(name + " started eating.");
// Print some random messages while the philosopher is eating
thread_local std::array<const char*, 3> foods {"chicken", "rice", "soda"};
thread_local std::array<const char*, 3> reactions {
"I like this %s!", "This %s is good.", "Mmm, %s..."
};
thread_local std::uniform_int_distribution<> dist(1, 6);
std::shuffle( foods.begin(), foods.end(), rng);
std::shuffle(reactions.begin(), reactions.end(), rng);
constexpr size_t buf_size = 64;
char buffer[buf_size];
for(int i = 0; i < 3; ++i) {
std::this_thread::sleep_for(std::chrono::milliseconds(dist(rng) * timeScale));
snprintf(buffer, buf_size, reactions[i], foods[i]);
Message(name + ": " + buffer);
}
std::this_thread::sleep_for(std::chrono::milliseconds(dist(rng)) * timeScale);
Message(name + " finished and left.");
}
void Philosopher::ponder()
{
static constexpr std::array<const char*, 5> topics {{
"politics", "art", "meaning of life", "source of morality", "how many straws makes a bale"
}};
thread_local std::uniform_int_distribution<> wait(1, 6);
thread_local std::uniform_int_distribution<> dist(0, topics.size() - 1);
while(dist(rng) > 0) {
std::this_thread::sleep_for(std::chrono::milliseconds(wait(rng) * 3 * timeScale));
Message(name + " is pondering about " + topics[dist(rng)] + ".");
}
std::this_thread::sleep_for(std::chrono::milliseconds(wait(rng) * 3 * timeScale));
Message(name + " is hungry again!");
}
int main()
{
Dinner dinner;
Message("Dinner started!");
// The philosophers will start as soon as they are created
std::array<Philosopher, 5> philosophers {{
{"Aristotle", dinner.forks[0], dinner.forks[1]},
{"Democritus", dinner.forks[1], dinner.forks[2]},
{"Plato", dinner.forks[2], dinner.forks[3]},
{"Pythagoras", dinner.forks[3], dinner.forks[4]},
{"Socrates", dinner.forks[4], dinner.forks[0]},
}};
Message("It is dark outside...");
}</syntaxhighlight>
<div style="height:10em; overflow:auto; border: 1px solid #AAA">
Dinner started!<br>
Aristotle started eating.<br>
It is dark outside...<br>
Plato started eating.<br>
Aristotle: Mmm, soda...<br>
Aristotle: This chicken is good.<br>
Plato: I like this soda!<br>
Aristotle: I like this rice!<br>
Aristotle finished and left.<br>
Plato: Mmm, chicken...<br>
Socrates started eating.<br>
Socrates: I like this soda!<br>
Plato: This rice is good.<br>
Plato finished and left.<br>
Democritus started eating.<br>
Socrates: Mmm, rice...<br>
Democritus: Mmm, soda...<br>
Aristotle is pondering about politics.<br>
Aristotle is pondering about meaning of life.<br>
Democritus: I like this chicken!<br>
Socrates: This chicken is good.<br>
Democritus: This rice is good.<br>
Democritus finished and left.<br>
Plato is pondering about source of morality.<br>
Socrates finished and left.<br>
Pythagoras started eating.<br>
Plato is pondering about how many straws makes a bale.<br>
Socrates is pondering about politics.<br>
Pythagoras: I like this chicken!<br>
Aristotle is hungry again!<br>
Aristotle started eating.<br>
Aristotle: This chicken is good.<br>
Socrates is pondering about art.<br>
Pythagoras: This soda is good.<br>
Pythagoras: Mmm, rice...<br>
Aristotle: I like this soda!<br>
Pythagoras finished and left.<br>
Socrates is hungry again!<br>
Aristotle: Mmm, rice...<br>
Democritus is pondering about source of morality.<br>
Plato is pondering about how many straws makes a bale.<br>
Aristotle finished and left.<br>
Socrates started eating.<br>
Democritus is hungry again!<br>
Democritus started eating.<br>
Plato is pondering about art.<br>
Socrates: Mmm, chicken...<br>
Democritus: This soda is good.<br>
Socrates: I like this rice!<br>
Democritus: I like this rice!<br>
Pythagoras is pondering about source of morality.<br>
Aristotle is pondering about source of morality.<br>
Socrates: This soda is good.<br>
Democritus: Mmm, chicken...<br>
Socrates finished and left.<br>
Democritus finished and left.<br>
Plato is pondering about politics.<br>
Aristotle is pondering about art.<br>
Pythagoras is pondering about source of morality.<br>
Socrates is pondering about source of morality.<br>
Plato is hungry again!<br>
Plato started eating.<br>
Plato: Mmm, rice...<br>
Plato: I like this soda!<br>
Plato: This chicken is good.<br>
Aristotle is hungry again!<br>
Aristotle started eating.<br>
Plato finished and left.<br>
Democritus is pondering about politics.<br>
Aristotle: Mmm, chicken...<br>
Aristotle: I like this rice!<br>
Pythagoras is pondering about art.<br>
Aristotle: This soda is good.<br>
Socrates is pondering about politics.<br>
Aristotle finished and left.<br>
Pythagoras is pondering about source of morality.<br>
Socrates is pondering about politics.<br>
Democritus is pondering about politics.<br>
Pythagoras is pondering about art.<br>
Plato is pondering about art.<br>
Aristotle is pondering about art.<br>
Socrates is pondering about source of morality.<br>
Democritus is pondering about meaning of life.<br>
Pythagoras is pondering about how many straws makes a bale.<br>
. . . .<br>
</div>
Uses C++14
Without threads, uses state machine.
<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <random>
#include <memory>
#include <cassert>
using namespace std;
struct Fork {
static const int ON_TABLE = -1;
int holder = ON_TABLE;
int request = ON_TABLE;
int id;
bool dirty = true;
Fork(int id) {
this->id = id;
}
bool isRequest() {
return request != Fork::ON_TABLE;
}
void process(int &forkCount, int &dirtyCount) {
if (holder == id) {
forkCount++;
if (isRequest()) {
if (dirty) {
forkCount--;
dirty = false;
holder = request;
}
request = Fork::ON_TABLE;
}
}
else
if (holder == Fork::ON_TABLE) {
holder = id;
forkCount++;
assert(dirty);
dirtyCount++;
assert(request == Fork::ON_TABLE);
} else {
request = id;
}
}
};
class Table;
enum State { Have0Forks, Have1Fork,Have01Fork, Have2Forks, Eat, AfterEat, Pon };
class Philosopher {
int id;
Table *table;
public:
Fork* left;
Fork* right;
int eatStarts = 0;
Philosopher(Table *table, int id);
void naive();
void ChandyMisra();
State state;
void selectState(int forkCount, int dirtyCount);
};
class Table {
mt19937 mt_rand;
std::uniform_real_distribution<> dis;
unique_ptr<std::uniform_int_distribution<>> disint;
public:
static const int PhilCount = 5;
vector<unique_ptr<Philosopher>> philosophers;
vector<unique_ptr<Fork>> forks;
Table() {
mt_rand.seed(1234);
disint = make_unique<std::uniform_int_distribution<>>(0, PhilCount-1);
for (int i=0; i<PhilCount; i++)
forks.push_back(make_unique<Fork>(i));
for (int i=0; i<PhilCount; i++)
philosophers.push_back(make_unique<Philosopher>(this, i));
}
double rand() {
return dis(mt_rand);
}
double randInt() {
return (*disint)(mt_rand);
}
void naive() {
cout << "Naive algorithm" << endl;
for (int i=0; i<Table::PhilCount; i++)
philosophers[i]->state = State::Have0Forks;
for (int i=0; i<100000; i++) {
philosophers[randInt()]->naive();
}
for (int i=0; i<Table::PhilCount; i++)
cout << i << " : " << philosophers[i]->eatStarts << endl;
}
void ChandyMisra() {
cout << "Chandy-Misra algorithm" << endl;
for (int i=0; i<Table::PhilCount; i++) {
philosophers[i]->state = State::Have01Fork;
philosophers[i]->eatStarts = 0;
philosophers[i]->left->holder = i;
}
for (int i=0; i<100000; i++) {
philosophers[randInt()]->ChandyMisra();
}
for (int i=0; i<Table::PhilCount; i++)
cout << i << " : " << philosophers[i]->eatStarts << endl;
}
};
Philosopher::Philosopher(Table *table, int id):table(table), id(id) {
left = table->forks[id].get();
right = table->forks[(id+1) % Table::PhilCount].get();
}
void Philosopher::naive() {
switch (state) {
case State::Pon:
if (table->rand()<0.2)
state = State::Have0Forks;
return;
case State::Have0Forks:
int forkCount;
forkCount = 0;
if (left->holder==Fork::ON_TABLE) {
left->holder=id;
forkCount++;
}
if (right->holder==Fork::ON_TABLE) {
right->holder=id;
forkCount++;
}
if (forkCount==1)
state = State::Have1Fork;
else if (forkCount==2)
state = State::Have2Forks;
return;
case State::Have1Fork:
Fork* forkToWait;
if (left->holder==id)
forkToWait = right;
else
forkToWait = left;
if (forkToWait->holder==Fork::ON_TABLE) {
forkToWait->holder=id;
state = State::Have2Forks;
}
return;
case State::Have2Forks:
state = State::Eat;
eatStarts++;
return;
case State::Eat:
if (table->rand()<0.2)
state = State::AfterEat;
return;
case State::AfterEat:
left->holder = Fork::ON_TABLE;
right->holder = Fork::ON_TABLE;
state = State::Pon;
return;
}
}
void Philosopher::ChandyMisra() {
switch (state) {
case State::Pon:
if (table->rand() < 0.2)
state = State::Have01Fork;
return;
case State::Have01Fork:
int forkCount;
int dirtyCount;
forkCount = 0;
dirtyCount = 0;
left->process(forkCount, dirtyCount);
right->process(forkCount, dirtyCount);
selectState(forkCount, dirtyCount);
return;
case State::Have2Forks:
state = State::Eat;
eatStarts++;
return;
case State::Eat:
if (table->rand()<0.2)
state = State::AfterEat;
return;
case State::AfterEat:
if (left->request!=Fork::ON_TABLE) {
left->dirty = false;
left->holder = left->request;
left->request = Fork::ON_TABLE;
} else {
left->holder = Fork::ON_TABLE;
left->dirty = true;
}
if (right->request!=Fork::ON_TABLE) {
right->dirty = false;
right->holder = right->request;
right->request = Fork::ON_TABLE;
} else {
right->holder = Fork::ON_TABLE;
right->dirty = true;
}
state = State::Pon;
return;
}
}
void Philosopher::selectState(int forkCount, int dirtyCount) {
if (forkCount == 2 && dirtyCount==0)
state = State::Have2Forks;
else
state = State::Have01Fork;
}
int main() {
Table table;
table.naive();
table.ChandyMisra();
return 0;
}
</syntaxhighlight>
=={{header|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 [http://clojure.org/refs 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.
<
(ref true))
Line 1,477 ⟶ 1,537:
(stop-eating phil)
(Thread/sleep (rand-int max-think-duration)))
(Thread/sleep retry-interval))))</
The second line of the <tt>start-eating</tt> function contains the essential solution: by invoking <tt>ensure</tt> 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:
<
(def *philosophers*
Line 1,498 ⟶ 1,558:
(println (str (:name p)
": eating=" (:eating? p)
" food=" (:food p)))))))</
The <tt>status</tt> 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).
Line 1,509 ⟶ 1,569:
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.
<
;;
Line 1,589 ⟶ 1,649:
(bt:with-lock-held (lock)
(bt:condition-wait condition lock)))))
</syntaxhighlight>
Alternative solution using library STMX which provides Software Transactional Memory, as well as BORDEAUX-THREADS above. Depends on Quicklisp. TAKE will wait until something is available in a TCELL, then remove it. PUT will wait for a TCELL to become empty, then add it. ATOMIC ensures STM operations in its body happen atomically.
<
(defpackage :dining-philosophers
Line 1,640 ⟶ 1,700:
:initial-bindings (cons (cons '*standard-output* *standard-output*)
bt:*default-special-bindings*))))))
</syntaxhighlight>
{{out}}
<
Aristotle is hungry
Aristotle is eating
Line 1,685 ⟶ 1,745:
Spinoza is thinking
Marx is eating
...</
=={{header|D}}==
This code is using a strict order for the forks/mutexes to prevent a deadlock.
<
core.sync.mutex;
Line 1,728 ⟶ 1,788:
}
}
}</
{{out|Sample output}}
<pre>Spinoza is full.
Line 1,743 ⟶ 1,803:
Aristotle is eating.
Aristotle is full.</pre>
=={{header|Delphi}}==
{{libheader| Classes}}
{{libheader| SysUtils}}
{{libheader| SyncObjs}}
{{Trans|Pascal}}
Just a fix of Pascal version to run in Delphi
<syntaxhighlight lang="delphi">
program dining_philosophers;
uses
Classes,
SysUtils,
SyncObjs;
const
PHIL_COUNT = 5;
LIFESPAN = 7;
DELAY_RANGE = 950;
DELAY_LOW = 50;
PHIL_NAMES: array[1..PHIL_COUNT] of string = ('Aristotle', 'Kant', 'Spinoza', 'Marx', 'Russell');
type
TFork = TCriticalSection;
// TPhilosopher = class;
TPhilosopher = class(TThread)
private
FName: string;
FFirstFork, FSecondFork: TFork;
protected
procedure Execute; override;
public
constructor Create(const aName: string; aForkIdx1, aForkIdx2: Integer);
end;
var
Forks: array[1..PHIL_COUNT] of TFork;
Philosophers: array[1..PHIL_COUNT] of TPhilosopher;
procedure TPhilosopher.Execute;
var
LfSpan: Integer;
begin
LfSpan := LIFESPAN;
while LfSpan > 0 do
begin
Dec(LfSpan);
WriteLn(FName, ' sits down at the table');
FFirstFork.Acquire;
FSecondFork.Acquire;
WriteLn(FName, ' eating');
Sleep(Random(DELAY_RANGE) + DELAY_LOW);
FSecondFork.Release;
FFirstFork.Release;
WriteLn(FName, ' is full and leaves the table');
if LfSpan = 0 then
continue;
WriteLn(FName, ' thinking');
Sleep(Random(DELAY_RANGE) + DELAY_LOW);
WriteLn(FName, ' is hungry');
end;
end;
constructor TPhilosopher.Create(const aName: string; aForkIdx1, aForkIdx2: Integer);
begin
inherited Create(True);
FName := aName;
if aForkIdx1 < aForkIdx2 then
begin
FFirstFork := Forks[aForkIdx1];
FSecondFork := Forks[aForkIdx2];
end
else
begin
FFirstFork := Forks[aForkIdx2];
FSecondFork := Forks[aForkIdx1];
end;
end;
procedure DinnerBegin;
var
I: Integer;
Phil: TPhilosopher;
begin
for I := 1 to PHIL_COUNT do
Forks[I] := TFork.Create;
for I := 1 to PHIL_COUNT do
Philosophers[I] := TPhilosopher.Create(PHIL_NAMES[I], I, Succ(I mod PHIL_COUNT));
for Phil in Philosophers do
Phil.Start;
end;
procedure WaitForDinnerOver;
var
Phil: TPhilosopher;
Fork: TFork;
begin
for Phil in Philosophers do
begin
Phil.WaitFor;
Phil.Free;
end;
for Fork in Forks do
Fork.Free;
end;
begin
Randomize;
DinnerBegin;
WaitForDinnerOver;
readln;
end.</syntaxhighlight>
=={{header|E}}==
Line 1,751 ⟶ 1,920:
We introduce a laquais who checks that no more than 4 philosophers are sitting at the same time. This prevents deadlocks. Reference : [http://greenteapress.com/semaphores/downey08semaphores.pdf The little book of semaphores].
<
(lib 'tasks)
Line 1,791 ⟶ 1,960:
i)
(define tasks (for/vector ((i 5)) (make-task philo i)))
</syntaxhighlight>
{{out}}
<
(define (observe dummmy)
(writeln 'observer 'rounds= rounds)
Line 1,804 ⟶ 1,973:
(dinner)
</syntaxhighlight>
<small>
Marx thinking about philosophy. <br>
Line 1,857 ⟶ 2,026:
[...] CTRL-C to stop. <br>
</small>
=={{header|Eiffel}}==
Line 1,869 ⟶ 2,036:
The example uses numbers (versus names) to identify the philosophers in order to allow the user to vary the number of philosophers.
<
DINING_PHILOSOPHERS
Line 1,926 ⟶ 2,093:
end
end -- class DINING_PHILOSOPHERS</
<
PHILOSOPHER
Line 2,036 ⟶ 2,203:
valid_has_eaten_count: has_eaten_count <= round_count
end -- class PHILOSOPHER</
<
FORK
Line 2,070 ⟶ 2,237:
end
end -- class FORK</
=={{header|
Implements the Chandy-Misra algorithm.
<syntaxhighlight lang="elixir">
defmodule Philosopher do
defstruct missing: [], clean: [], promised: []
def run_demo do
pid1 = spawn(__MODULE__, :init, ["Russell"])
pid2 = spawn(__MODULE__, :init, ["Marx"])
pid3 = spawn(__MODULE__, :init, ["Spinoza"])
pid4 = spawn(__MODULE__, :init, ["Kant"])
pid5 = spawn(__MODULE__, :init, ["Aristotle"])
# a chopstick is simply represented by the pid of the neighbour that shares it.
send(pid1, {:run, %Philosopher{}})
send(pid2, {:run, %Philosopher{missing: [pid1]}})
send(pid3, {:run, %Philosopher{missing: [pid2]}})
send(pid4, {:run, %Philosopher{missing: [pid3]}})
send(pid5, {:run, %Philosopher{missing: [pid1, pid4]}})
end
def init(philosopher_name) do
receive do
{:run, state} ->
spawn(__MODULE__, :change_state, [self()])
case flip_coin() do
:heads -> thinking(philosopher_name, state)
:tails -> hungry(philosopher_name, state)
end
end
end
defp thinking(philosopher_name, state) do
receive do
{:change_state} ->
hungry(philosopher_name, state)
{:chopstick_request, pid} ->
if clean?(pid, state) do
thinking(philosopher_name, promise_chopstick(philosopher_name, pid, state))
else
give_chopstick(philosopher_name, self(), pid)
%{missing: missing} = state
thinking(philosopher_name, %{state | missing: [pid | missing]})
end
end
end
defp hungry(philosopher_name, state) do
IO.puts "#{philosopher_name} is hungry."
%{missing: missing} = state
for pid <- missing, do: request_chopstick(philosopher_name, self(), pid)
wait_for_chopsticks(philosopher_name, state)
end
defp wait_for_chopsticks(philosopher_name, state) do
if has_chopsticks?(state) do
eating(philosopher_name, state)
end
receive do
{:chopstick_request, pid} ->
if clean?(pid, state) do
wait_for_chopsticks(philosopher_name, promise_chopstick(philosopher_name, pid, state))
else
give_chopstick(philosopher_name, self(), pid)
request_chopstick(philosopher_name, self(), pid)
%{missing: missing} = state
wait_for_chopsticks(philosopher_name, %{state | missing: [pid | missing]})
end
{:chopstick_response, pid} ->
%{missing: missing, clean: clean} = state
wait_for_chopsticks(philosopher_name, %{state | missing: List.delete(missing, pid), clean: [pid | clean]})
end
end
defp eating(philosopher_name, state) do
IO.puts "*** #{philosopher_name} is eating."
receive do
{:change_state} ->
%{promised: promised} = state
for pid <- promised, do: give_chopstick(philosopher_name, self(), pid)
thinking(philosopher_name, %Philosopher{missing: promised})
end
end
defp clean?(pid, state) do
%{clean: clean} = state
Enum.member?(clean, pid)
end
defp has_chopsticks?(state) do
%{missing: missing} = state
Enum.empty?(missing)
end
defp promise_chopstick(philosopher_name, pid, state) do
IO.puts "#{philosopher_name} promises a chopstick."
%{promised: promised} = state
%{state | promised: [pid | promised]}
end
defp request_chopstick(philosopher_name, snd_pid, recv_pid) do
IO.puts "#{philosopher_name} requests a chopstick."
send(recv_pid, {:chopstick_request, snd_pid})
end
defp give_chopstick(philosopher_name, snd_pid, recv_pid) do
IO.puts "#{philosopher_name} gives a chopstick."
send(recv_pid, {:chopstick_response, snd_pid})
end
defp flip_coin do
case Enum.random(0..1) do
0 -> :heads
1 -> :tails
end
end
def change_state(pid) do
Process.sleep(Enum.random(1..10) * 1000)
send(pid, {:change_state})
change_state(pid)
end
</syntaxhighlight>
=={{header|Erlang}}==
===Waiter-based===
<syntaxhighlight lang="erlang">
%%%
%%% to compile and run:
%%% $ erl
%%% > c(rosetta).
%%% {ok,rosetta}
%%% > rosetta:dining().
%%%
%%% contributor: bksteele
%%%
-module(rosetta).
-export([dining/0]).
sleep(T) ->
receive
after T ->
doForks(ForkList) ->
receive
{available, {Left,
Sender ! {areAvailable,
lists:member(Left, ForkList)
andalso lists:member(Right, ForkList)},
doForks(ForkList);
{die} -> io:format("Forks put away.~n")
end.
areAvailable(Forks) ->
processWaitList([]) -> false;
processWaitList([H|T]) ->
doWaiter([], 0, 0, false) ->
doWaiter(WaitList, ClientCount, EatingCount, Busy) ->
% add to waiting list
case (not Busy) and (EatingCount<2) of
true ->
Busy1 = processWaitList(WaitList1);
false -> Busy1 = Busy
end,
doWaiter(WaitList1, ClientCount, EatingCount, Busy1);
philosopher(Name,
waiter ! {leaving};
philosopher(Name, Forks, Cycle) ->
io:format("~s is hungry.~n", [Name]),
% sit at table
% grab forks
waiter ! {eating, {self(), Forks}},
% start eating
io:format("~s is eating.~n", [Name])
end,
forks ! {releaseforks, Forks},
waiter ! {finished},
dining() ->
register(waiter,
% run for 7 cycles
spawn(fun() -> philosopher('Spinoza', {2, 3}, Life_span) end),
spawn(fun() -> philosopher('Marx', {3, 4}, Life_span) end),
spawn(fun() -> philosopher('Russell', {4, 5}, Life_span) end),
receive
{allgone} -> io:format("Dining room closed.~n")
end,
unregister(diningRoom).
</syntaxhighlight>
Output:
<pre>
Eshell V9.2 (abort with ^G)
1> c(rosetta).
{ok,rosetta}
2> rosetta:dining().
Aristotle is thinking.
Kant is thinking.
Spinoza is thinking.
Marx is thinking.
Russell is thinking.
Russell is hungry.
Russell is eating.
Kant is hungry.
Kant is eating.
Russell is thinking.
Aristotle is hungry.
Spinoza is hungry.
Marx is hungry.
Marx is eating.
Russell is hungry.
Kant is thinking.
Aristotle is eating.
Marx is thinking.
Spinoza is eating.
Kant is hungry.
Spinoza is thinking.
Aristotle is thinking.
Kant is eating.
Marx is hungry.
Marx is eating.
Marx is thinking.
Russell is eating.
Spinoza is hungry.
Aristotle is hungry.
Marx is hungry.
Kant is thinking.
Spinoza is eating.
Russell is thinking.
Aristotle is eating.
Russell is hungry.
Spinoza is thinking.
Marx is eating.
Spinoza is hungry.
Kant is hungry.
Aristotle is thinking.
Kant is eating.
Marx is thinking.
Russell is eating.
Aristotle is hungry.
Marx is hungry.
Russell is thinking.
Marx is eating.
Russell is hungry.
Kant is thinking.
Aristotle is eating.
Aristotle is thinking.
Marx is thinking.
Russell is eating.
Marx is hungry.
Spinoza is eating.
Aristotle is hungry.
Spinoza is thinking.
Spinoza is hungry.
Spinoza is eating.
Spinoza is thinking.
Spinoza is hungry.
Spinoza is eating.
Kant is hungry.
Russell is thinking.
Aristotle is eating.
Aristotle is thinking.
Spinoza is thinking.
Kant is eating.
Aristotle is hungry.
Marx is eating.
Russell is hungry.
Kant is thinking.
Aristotle is eating.
Kant is hungry.
Marx is thinking.
Spinoza is hungry.
Spinoza is eating.
Spinoza is thinking.
Aristotle is thinking.
Kant is eating.
Aristotle is hungry.
Russell is eating.
Spinoza is hungry.
Marx is hungry.
Kant is thinking.
Spinoza is eating.
Russell is thinking.
Aristotle is eating.
Spinoza is leaving.
Marx is eating.
Marx is thinking.
Marx is hungry.
Marx is eating.
Russell is hungry.
Aristotle is thinking.
Kant is hungry.
Kant is eating.
Marx is leaving.
Russell is eating.
Kant is thinking.
Russell is thinking.
Aristotle is hungry.
Aristotle is eating.
Aristotle is leaving.
Russell is hungry.
Russell is eating.
Kant is hungry.
Kant is eating.
Russell is leaving.
Kant is leaving.
Waiter is leaving.
Forks put away.
Dining room closed.
true
3> halt().
</pre>
===Free-thinkers===
<syntaxhighlight lang="erlang">
%%% This version uses free-running 'phil' agents (actors) and
%%% state machines representing the forks.
%%%
%%% Usage to compile and run:
%%% $ erl
%%% > c(dining).
%%% {ok,dining}
%%% > dining:start().
%%%
-module( dining).
-export(
[ start/0
]).
-vsn( 1).
-date( '6/2020').
-author( bksteele).
-email( 'drbenkman@gmail.com').
%% fork messages: grab | drop | quit
%% a quit message is accepted only when State = available
%% @param Id numeric identification of object
%% @param State: available | in_use
fork( Id, available ) ->
receive
{ From, Who, grab} ->
From ! { self(), Who, Id}
, fork( Id, in_use)
;
{ From, quit} ->
From ! { quit}
, ok
end
;
fork( Id, in_use ) ->
receive
{ From, Who, drop} ->
From ! { self(), Who, Id}
, fork( Id, available)
end
.
%% sleep/1 : Integer -> ok
%% sleep pauses a process for T milliseconds.
%% @param T milliseconds for the time period
sleep(T) ->
receive
after T -> true
end
.
%% grab/2 : Pid String -> ()
%% Fork is the shared resource (a process object).
%% Who is the name of the acting process.
%% grab encapsulates message transmission.
%% @param Fork pid to which to send messages
%% @param Who name of the sender
grab( Fork, Who) ->
Fork ! { self(), Who, grab}
, receive
{ Fork, Who, _Id} -> ok
end
.
%% drop/2 : Pid String -> ()
%% Fork is the shared resource (a process object).
%% Who is the name of the acting process.
%% drop encapsulates message transmission.
%%
%% @param Fork pid to which to send messages
%% @param Who name of the sender
drop( Fork, Who) ->
Fork ! { self(), Who, drop}
, receive
{ Fork, Who, _Id} -> ok
end
.
%% phil/3 : String List{Id,Pid} Integer -> ok
%% phil/3 philosopher process uses a fork process.
%% phil uses two fork objects for n eating cycles.
%% A phil needs the pids of resource to communicate,
%% and the names of the fork resources it uses.
%% @param Name the string name of the philosopher
%% @param List{Id, Pid} 2 pairs of Id and Fork
%% @param Cycle the number of cycles to run
phil( Name, [{LId, Left}, {RId, Right}], Cycle)
when LId > RId ->
% swap so that process picks numerically lower first.
% the swap introduces asymmetry to prevent deadlock.
phil( Name, {RId, Right}, {LId, Left}, Cycle)
;
phil( Name, [{LId, Left}, {RId, Right}], Cycle) ->
phil( Name, {LId, Left}, {RId, Right}, Cycle).
%% phil/4 : String {LId,LeftF} {RId,RightF} Integer -> ok
%% phil/4 philosopher process uses a fork process.
%% phil uses two fork objects for n eating cycles.
%% A phil needs pids of resource to communicate
%% and the names of the fork resources it uses.
%% @param Name the string name of the philosopher
%% @param {LeftId, Fork} pair of Id and Fork pid
%% @param {RightId, Fork} pair of Id and Fork pid
%% @param Cycle the number of cycles to run
phil( Name, _LFork, _RFork, 0) ->
io:format( "~s is done.~n", [Name])
;
phil( Name, {LId, Left}, {RId, Right}, Cycle) ->
io:format( "~s is thinking.~n", [Name])
, sleep( rand:uniform( 1000))
, io:format( "~s is hungry.~n", [Name])
, grab( Left, Name)
, grab( Right, Name)
, io:format( "~s is eating.~n", [Name])
, sleep( rand:uniform( 1000))
, drop( Left, Name)
, drop( Right, Name)
, phil( Name, [{LId, Left}, {RId, Right}]
, Cycle - 1)
.
%% make_forks/1 : N -> List{Id, Fork}
make_forks( N) when N > 0 -> make_forks( N, []).
%% make_forks/2 : N List{Id, Fork}
make_forks( 0, Forks ) -> lists:reverse( Forks)
;
make_forks( N, Forks) ->
% create and run the fork processes
Pair = { N, spawn(
fun() -> fork( N, available) end) }
, make_forks( N-1
, lists:append( Forks, [Pair] ))
.
%% make_phils/2 : Names, ForkList -> List{String}
make_phils( Names, Forks)
when length( Names) > 0 ->
make_phils( Names, Forks, [])
.
%% make_phils/3 : Names Forks PL -> List{Fun}
%% make_phil/3 hard-codes the eat cycle count to 7
make_phils( [], _Forks, PhilList) -> PhilList
;
make_phils( [Hn|Tn], [Lf, Rf |FList], PhilList) ->
% create a phil process function but do not run yet
Phil = fun() -> phil( Hn, [Lf, Rf], 7) end
, make_phils( Tn, rot( [Lf, Rf |FList], 1)
, lists:append( PhilList, [Phil]))
.
%% rot/2 : List Num -> List
%% rotate or roll a list by N slots, and return new list
rot( List, 0 ) -> List
;
rot( [H], 1 ) -> [H]
;
rot( [H|List], N ) ->
rot( lists:append( List, [H]), N - 1)
.
%% start free-running philosopher agents competing for Forks
%% start is fixed with N = 5 philosophers and 5 forks.
start() ->
% create Fork list
N = 5
, Forks = make_forks( N)
, Names = [ "Aristotle", "Kant"
, "Spinoza", "Marx", "Russell"]
, Phils = make_phils( Names, Forks)
% run the philosophers now
, [spawn( P) || P <- Phils]
, ok
.
</syntaxhighlight>
Output:
<pre>
Eshell V9.2 (abort with ^G)
1> c(dining).
{ok,dining}
2> dining:start().
Aristotle is thinking.
Kant is thinking.
Spinoza is thinking.
Marx is thinking.
Russell is thinking.
ok
Kant is hungry.
Kant is eating.
Marx is hungry.
Marx is eating.
Marx is thinking.
Spinoza is hungry.
Aristotle is hungry.
Russell is hungry.
Marx is hungry.
Marx is eating.
Aristotle is eating.
Kant is thinking.
Spinoza is eating.
Marx is thinking.
Aristotle is thinking.
Russell is eating.
Kant is hungry.
Russell is thinking.
Marx is hungry.
Russell is hungry.
Russell is eating.
Kant is eating.
Spinoza is thinking.
Aristotle is hungry.
Kant is thinking.
Russell is thinking.
Marx is eating.
Aristotle is eating.
Russell is hungry.
Aristotle is thinking.
Kant is hungry.
Kant is eating.
Kant is thinking.
Aristotle is hungry.
Spinoza is hungry.
Kant is hungry.
Spinoza is eating.
Marx is thinking.
Russell is eating.
Marx is hungry.
Russell is thinking.
Kant is eating.
Spinoza is thinking.
Marx is eating.
Spinoza is hungry.
Marx is thinking.
Russell is hungry.
Marx is hungry.
Marx is eating.
Aristotle is eating.
Kant is thinking.
Spinoza is eating.
Marx is thinking.
Spinoza is thinking.
Spinoza is hungry.
Spinoza is eating.
Kant is hungry.
Aristotle is thinking.
Russell is eating.
Russell is thinking.
Marx is hungry.
Kant is eating.
Spinoza is thinking.
Marx is eating.
Aristotle is hungry.
Russell is hungry.
Aristotle is eating.
Kant is thinking.
Kant is hungry.
Marx is thinking.
Marx is hungry.
Marx is eating.
Aristotle is thinking.
Kant is eating.
Spinoza is hungry.
Marx is done.
Russell is eating.
Kant is thinking.
Spinoza is eating.
Spinoza is thinking.
Aristotle is hungry.
Kant is hungry.
Kant is eating.
Russell is thinking.
Aristotle is eating.
Kant is done.
Russell is hungry.
Spinoza is hungry.
Spinoza is eating.
Aristotle is thinking.
Russell is eating.
Aristotle is hungry.
Russell is thinking.
Aristotle is eating.
Russell is hungry.
Spinoza is thinking.
Aristotle is thinking.
Russell is eating.
Spinoza is hungry.
Spinoza is eating.
Aristotle is hungry.
Spinoza is done.
Russell is done.
Aristotle is eating.
Aristotle is done.
3> halt().
</pre>
=={{header|Euphoria}}==
<
sequence forks
forks = repeat(FREE,5)
Line 2,234 ⟶ 2,993:
while get_key() = -1 do
task_yield()
end while</
Sample output:
Line 2,286 ⟶ 3,045:
This solution avoids deadlock by employing a waiter.
<
open System
Line 2,339 ⟶ 3,098:
Console.ReadLine() |> ignore
0
</syntaxhighlight>
=={{header|Go}}==
===Channels===
Goroutine synchronization done with Go channels. Deadlock prevented by making one philosopher "left handed."
<
import (
Line 2,427 ⟶ 3,186:
}
fmt.Println("table empty")
}</
Output:
<pre>
Line 2,498 ⟶ 3,257:
One more concurrency technique actually used in both solutions is to use the log package for output rather than the fmt package. Output from concurrent goroutines can get accidentally interleaved in some cases. While neither package makes claims about this problem, the log package historically has been coded to avoid interleaved output.
<
import (
Line 2,556 ⟶ 3,315:
dining.Wait() // wait for philosphers to finish
fmt.Println("table empty")
}</
=={{header|Groovy}}==
Deadlocks are avoided by always getting locks on forks with lower numbers first.
<
import java.util.concurrent.locks.Lock
Line 2,615 ⟶ 3,374:
}
diningPhilosophers(['Aristotle', 'Kant', 'Spinoza', 'Marx', 'Russell'])</
=={{header|Haskell}}==
Using the built-in Software Transactional Memory in GHC.
<
import Control.Monad
Line 2,684 ⟶ 3,443:
-- All threads exit when the main thread exits.
getLine
</syntaxhighlight>
==Icon and {{header|Unicon}}==
Line 2,695 ⟶ 3,454:
when they can't get both forks and went back to thinking instead. (Take away their grant money.)
<
procedure main(A)
Line 2,723 ⟶ 3,482:
}
}
end</
A sample run, terminated after some time.
Line 2,778 ⟶ 3,537:
=={{header|J}}==
===Using Threading Primitives===
Currently, this only works under jconsole. (Unfortunately, QT requires all GUI interactions occur on the main thread, and as of j9.4, jqt has not been updated force this behavior, so do not use jqt here.)
Here, to prevent deadlock, philosophers always pick up forks in a specific order and always lay down their forks in the reverse order. This means that one philosopher (Marx) will use the opposite left/right order from the rest of the philosophers.
<syntaxhighlight lang=J>reqthreads=: {{ 0&T.@''^:(0>.y-1 T.'')0 }}
dispatchwith=: (t.'')every
newmutex=: (; 10&T.@0)@>
lock=: 11&T.@{:
unlock=: 13&T.@{:
dl=: 6!:3
dine=: {{
'forkA forkB'=. <"1 /:~ n
announce=. m {{ echo m,' ',y }}
announce 'will use fork ',(":;{.forkA),' first and put it down last'
announce 'will use fork ',(":;{.forkB),' second and put it down first'
dl 1
while. do.
announce 'is hungry'
lock forkA
announce 'picked up fork ',":;{.forkA
lock forkB
announce 'picked up fork ',":;{.forkB
announce 'is eating'
dl 2+(?3e3)%1e3
announce 'has finished eating'
unlock forkB
announce 'has put down fork ',":;{.forkB
unlock forkA
announce 'has put down fork ',":;{.forkA
announce 'has left the room'
dl 4+(?1e4)%1e3
end.
y
}}
start=: {{
echo 'Hit enter to exit'
dl 1
reqthreads 5
forks=. newmutex i.5
for_philosopher.;:' Aristotle Kant Spinoza Marx Russell' do.
forks=. 1|.forks
(;philosopher) dine (2{.forks) dispatchwith EMPTY
end.
exit 1!:1]1
}}
</syntaxhighlight>
Sample session:
<syntaxhighlight lang=J>
start''
Hit enter to exit
Aristotle will use fork 1 first and put it down last
Kant will use fork 2 first and put it down last
Marx will use fork 0 first and put it down last
Spinoza will use fork 3 first and put it down last
Russell will use fork 0 first and put it down last
Aristotle will use fork 2 second and put it down first
Kant will use fork 3 second and put it down first
Marx will use fork 4 second and put it down first
Spinoza will use fork 4 second and put it down first
Russell will use fork 1 second and put it down first
Spinoza is hungry
Marx is hungry
Aristotle is hungry
Aristotle picked up fork 1
Spinoza picked up fork 3
Marx picked up fork 0
Kant is hungry
Aristotle picked up fork 2
Spinoza picked up fork 4
Aristotle is eating
Spinoza is eating
Russell is hungry
Aristotle has finished eating
Spinoza has finished eating
Aristotle has put down fork 2
Kant picked up fork 2
Spinoza has put down fork 4
Marx picked up fork 4
Aristotle has put down fork 1
Spinoza has put down fork 3
Kant picked up fork 3
Marx is eating
Aristotle has left the room
Spinoza has left the room
Kant is eating
Kant has finished eating
Marx has finished eating
Kant has put down fork 3
Marx has put down fork 4
Kant has put down fork 2
Marx has put down fork 0
Russell picked up fork 0
Kant has left the room
Marx has left the room
Russell picked up fork 1
Russell is eating</syntaxhighlight>
===Older Emulations===
These philosophers are very smart and polite: they figured out immediately that at most two of them can eat simultaneously (take the floor of n divided by 2 for n philosophers); so, when they are hungry and it is necessary, they wait in line. (In general, for n > 1, because they are very smart and polite, when a philosopher seats he leaves exactly one empty seat between himself and one of the philosophers which are already eating if any.)
J does not support concurrency; so, this is a discrete-event simulation (DES). The time spent thinking and eating is assumed to be exponentially distributed, respectively, at the rates of 1 and 0.5 per time unit.
====The simulation code====
The simulation is defined in terms of fixed tacit (stateless point-free) code (a Turing complete dialect of J; see, https://rosettacode.org/wiki/Universal_Turing_machine#J),
<
simulate=.
Line 2,811 ⟶ 3,674:
) ,&< ''"_) 0 6} ]))@:(,&(;:8$','))@:;
)</
====Simulation of 11 chronological events for five philosophers====
<
0.000: All of them start thinking.
0.097: Spinoza starts eating.
Line 2,831 ⟶ 3,694:
5.166: Marx starts eating.
5.915: Marx starts thinking.
5.915: Spinoza starts eating.</
====Simulation of 22 chronological events for eight philosophers====
<
0.000: All of them start thinking.
0.077: Nezahualcoyotl starts eating.
Line 2,864 ⟶ 3,727:
2.339: Marx starts waiting and thinking about hunger.
2.446: Aristotle starts thinking.
2.446: Marx starts eating.</
====The structured derivation of the verb (function)====
The fixed tacit code of the verb (simulate) was produced by means of an unorthodox tacit toolkit; however, the verb produced is orthodox (compliant):
<
o=. @:
Line 2,914 ⟶ 3,777:
S - Starting time for the new activity
Q - Queue
U - Upper bound for the number of philosophers
P - Active philosopher
E - Elapsed Time (only for information purposes)
Line 2,924 ⟶ 3,787:
thinktime=. _1 * ^. o ? o 0: NB. Exponentially distributed at a rate of one
eattime =. _2 * ^. o ? o 0: NB. Exponentially distributed at a rate of one
j=. ,&<
Line 2,932 ⟶ 3,795:
(N Q)`((;: o N) j (''c)) h NB. Boxing the names, empty queue
(A T)`((0:items j thinktime&>) o N) h NB. All start thinking
(E U)`(0 ; <. o (2 %~ # o N)) h NB.
[ echo o (time , 'All of them start thinking.'c)
)
Line 2,963 ⟶ 3,826:
A`(amend o ((B P A)f))h o (B`0: h) NB. Activity: thinking
[ echo o ( time , ' starts thinking.' ,~ P {:: N)
dequeue ^: (1 <: # o Q) NB.
)
Line 2,985 ⟶ 3,848:
NB. The simulation code is produced by the sentence,
NB. 77 (-@:[ ]\ 5!:5@<@:]) 'simulate'</
=={{header|Java}}==
This Java implementation uses a token system. If a philosopher's number is on the token, they pick up their left and right forks. Passing the token to their immediate neighbor would be pointless, so they increment the token by 2, passing it to the philosopher after their neighbor. The +2 works well for odd numbers of philosophers. With wait down at 1 millisecond I get about 1.5M eats/sec running 5 philosophers, down to about 0.5M eats/sec running 25. The single token generates good availability for 80% of 5 forks, but a much lower availability % of 25 forks.
<syntaxhighlight lang="java">
package diningphilosophers;
Line 3,103 ⟶ 3,966:
}
}
</syntaxhighlight>
{{out}}
<pre>
|Eat|Get|Eat|Get|Get| |P00|P00|P02|P02|P04|
|Eat|Get|Get|Get|Get| |P00|P00| | | |
|Get|Get|Get|Get|Get| | | | | | |
|Get|Pon|Get|Pon|Get| |P00| | | | |
|Eat|Get|Get|Get|Get| |P00|P00| | | |
|Get|Eat|Get|Get|Pon| | |P01|P01| | |
|Pon|Get|Eat|Get|Eat| |P04| |P02|P02|P04|
|Get|Get|Get|Get|Pon| | | | |P03| |
|Pon|Get|Eat|Pon|Get| | | |P02|P02|P04|
|Get|Eat|Pon|Get|Eat| |P04|P01|P01| | |
|Get|Pon|Get|Get|Get| | | | |P03| |
|Eat|Get|Get|Pon|Get| |P00|P00| | | |
|Get|Pon|Get|Get|Get| |P00| | | | |
|Get|Get|Eat|Get|Eat| |P04|P01|P02|P02|P04|
|Pon|Pon|Eat|Get|Get| | | |P02|P02| |
P00: ate 59 times, 3/sec
P01: ate 59 times, 3/sec
P02: ate 59 times, 3/sec
P03: ate 59 times, 3/sec
P04: ate 59 times, 3/sec
</pre>
=={{header|JoCaml}}==
Line 3,120 ⟶ 4,007:
*The mean time of waiting while hungry is not bounded and grows very slowly (logarithmically) with time.
<
let print s m = Printf.printf "philosopher %s is %s\n" s m; flush(stdout);;
let will_eat s = print s "eating"; random_wait 10;;
Line 3,140 ⟶ 4,027:
and e() = will_think "Russell"; eh()
;;
spawn fab() & fbc() & fcd() & fde() & fea() & a() & b() & c() & d() & e();;</
Sample output:
<pre>philosopher Aristotle is thinking
Line 3,176 ⟶ 4,063:
This solution is logically the same as the "minimal simple" solution above, but now the timing information is printed. Statistical information is also printed on hungry waiting time before eating: average among all instances of eating, and maximum time ever waited by anyone.
<
let random_wait n = Unix.sleep (Random.int n);;
Line 3,222 ⟶ 4,109:
(* now we need to wait and do nothing; nobody will be able to inject godot() *)
def wait_forever() & godot() = reply () to wait_forever in wait_forever();;</
Sample output (excerpt):
<pre>t=2: philosopher Aristotle is thinking
Line 3,265 ⟶ 4,152:
This solution implements "fairness" -- if two neighbors are hungry, the one who waited more will eat first. The waiting time for each philosopher is bounded by twice the maximum eating time.
<
(* eating and thinking between 0 and this-1 *)
Line 3,341 ⟶ 4,228:
(* now we need to wait and do nothing; nobody will be able to inject godot() *)
def wait_forever() & godot() = reply () to wait_forever in wait_forever();;</
Sample output:
Line 3,371 ⟶ 4,258:
and the others take the right fork first. The forks are represented by 5 channels.
One lefty's taking left fork before right prevents deadlocks (see C solution).
<
mutable struct Philosopher
name::String
Line 3,455 ⟶ 4,342:
runall(tasks)
</syntaxhighlight>
{{output}}
Aristotle is out of the dining room for now.
Line 3,532 ⟶ 4,419:
{{trans|Groovy}}
As noted in the Groovy entry, deadlocks are avoided by always getting locks on forks with lower numbers first.
<
import java.util.Random
Line 3,589 ⟶ 4,476:
val names = listOf("Aristotle", "Kant", "Spinoza", "Marx", "Russell")
diningPhilosophers(names)
}</
=={{header|Logtalk}}==
Works when using SWI-Prolog, XSB, or YAP as the backend compiler:
<
% chopstick actions (picking up and putting down) are synchronized using a notification
Line 3,748 ⟶ 4,635:
right_chopstick(cs5). % in different order from the other philosophers
:- end_object.</
=={{header|M2000 Interpreter}}==
Version 2.1
Improved program. Choose random Sequential or Concurrent plan. In Concurrent statements in blocks { } are executed sequential (without other part of other thread executed).
At the beginning one of philosopher get a longer trigger period for entry.
Also ranδomly the program choose if philosophers can change the order of picking.
Each philosopher has an energy, starting from 50. If thinking then energy drop, and can die if energy<1.
When philosopher thinking and energy is above 70 then he leave back any fork and drop to 60
Each time he get two forks get a counter on a random value of 4 to 8. So for 4 to 8 "cycles" hold two forks and gain 4 to 8 energy units. With this we have various eating time.
To avoid deadlock we have to put back a fork in thinking phase as the rule bellow:
If a philosopher thinking and has energy>70 or the common critical>5 then he place any fork back
if energy>70 then energy drop to 60 (so we make a dead zone of 10 units for this automation)
The critical variable get new value from another thread the Main.Task. Some times critical may get a value of 7 and then the thinking philosopher found it and place his fork back (if has any).
<syntaxhighlight lang="m2000 interpreter">
Module Dining_philosophers (whichplan) {
Form 80, 32
Const MayChangePick=Random(True, False)
dim energy(1 to 5)=50
Document Doc$
const nl$={
}
Print $(,12), ' set column width to 12
Pen 14
Pen 15 {
Doc$="Dining Philosophers"+nl$
\\ we can change thread plan only if no threads defined
if whichplan=1 then
Doc$="Sequential threads - to execute exclusive one threads code"+nl$
thread.plan sequential
\\ need time_to_think>time_to_eat, but time_to_appear maybe the same for all
time_to_think=150 ' one or more intervals
time_to_eat=100 ' one interval to eat only
time_to_appear=(150,150,150,150,150)
Return time_to_appear, random(0,3):=300
else
Doc$="Concurrent threads - to execute a statement or a block of code"+nl$
thread.plan concurrent
time_to_think=100 ' one or more intervals
time_to_eat=50 ' one interval to eat only
time_to_appear=(100,100,100,100,100)
Return time_to_appear, random(1,4):=200
end if
Print #-2,Doc$
Print @(0,2),"Press left mouse button to exit"
Print Part $(1), time_to_appear
Print under
}
Pen 13 {Print "Aristotle", "Kant", "Spinoza", "Marx", "Russell"}
enum philosopher {
Aristotle, Kant, Spinoza, Marx, Russell
}
global enum forks {NoFork, Fork}
RoundTable =(Fork, Fork, Fork, Fork, Fork)
Getleft=lambda RoundTable (ph as philosopher) -> {
where=(ph+4) mod 5
= RoundTable#val(where)
Return RoundTable, where:=NoFork
}
GetRight=lambda RoundTable (ph as philosopher) -> {
where=ph mod 5
=RoundTable#val(where)
Return RoundTable, where:=NoFork
}
PlaceForks=lambda RoundTable (ph as philosopher) -> {
Return RoundTable, (ph+4) mod 5:=Fork,ph mod 5:=Fork
}
PlaceAnyFork=lambda RoundTable (ph as philosopher, &ForkL, &ForkR) -> {
If ForkL=Fork then Return RoundTable, (ph+4) mod 5:=Fork : ForkL=NoFork
If ForkR=Fork Then Return RoundTable, ph mod 5:=Fork : ForkR=NoFork
}
ShowTable=lambda RoundTable -> {
m=each(RoundTable)
while m
print if$(array(m)=NoFork->"No Fork", "Fork"),
end while
Print
}
noforks=lambda RoundTable -> {
k=0
m=each(RoundTable)
while m
if array(m)=NoFork then k++
end while
=k=5
}
def critical as long, basetick
Document page$
m=each(philosopher)
while m {
\\ we make 5 threads
\\ a thread has module scope (except for own static variables, and stack of values)
thread {
if energy(f)<1 then {
call PlaceAnyFork(f, ForkL, ForkR)
energy(f)=0
Page$=format$("{0::-12} - ",tick-basetick)+eval$(f)+" - Die"+nl$
thread this erase
} else {
Page$=format$("{0::-12} - ",tick-basetick)+eval$(f)
Page$=if$(ForkL=Nofork or ForkR=Nofork->" thinking", " eating"+str$(eatcount))
Page$=if$(R->"- R", " - L")+nl$
}
if not think then
{ \\ a block always run blocking all other threads
energy(f)++
eatcount--
if eatcount>0 then exit
Call PlaceForks(f) : ForkL=Nofork:ForkR=NoFork
eatcount=random(4,8)
if MayChangePick then R=random(-1,0)
think=true :thread this interval time_to_think*random(1,5)
}
else.if energy(f)>70 or critical>5 then
{
call PlaceAnyFork(f, &ForkL, &ForkR)
if energy(f)>70 then energy(f)=60
}
else.if R then
if ForkR=Nofork then ForkR=GetRight(f)
if ForkR=fork and ForkL=Nofork then ForkL=GetLeft(f)
if ForkL=fork then think=false:thread this interval time_to_eat else energy(f)--
else
if ForkL=Nofork then ForkL=GetLeft(f)
if ForkL=fork and ForkR=Nofork then ForkR=GetRight(f)
if ForkR=fork then think=false:thread this interval time_to_eat else energy(f)--
end if
} as a interval time_to_appear#val(m^)
\\ a is a variable which hold the number of thread (as returned from task manager)
\\ so we can get 5 times a new number.
\\ for each thread we make some static variables (only for each thread)
\\ this statement execute a line of code in thread a
thread a execute {
\\ this executed on thread execution object
static f=eval(m), think=true, ForkL=NoFork
static ForkR=NoFork, eatcount=random(2,5)
static R=-1
if MayChangePick then R=Random(-1,0)
}
}
cls ,5 ' set split screen from fifth row
\\ Main.Task is a thread also. Normaly exit if no other threads running in background
\\ also serve a the wait loop for task manager (we can use Every 200 {} but isn't a thread, is a kind of a wait statement)
\\ tick return the counter from task manager which used to triger threads
basetick=tick
\\ 4hz display results
MaxCritical=0
Main.Task 1000/4 {
{ \\ a block always run blocking all other threads
cls
Print Part $(1),$("####;\D\I\E;\D\I\E"),energy()
Print Under
Print "Table:"
Call ShowTable()
if noforks() then critical++ else critical=0
MaxCritical=if(MaxCritical<critical->critical,MaxCritical)
Print "noforks on table counter:";critical, "Max:";MaxCritical
Print #-2,Page$
Doc$=Page$
Clear Page$
}
if critical>40 or keypress(1) then exit
}
threads erase
Clipboard Doc$
}
Dining_philosophers Random(1,2)
</syntaxhighlight>
{{out}}
<pre style="height:30ex;overflow:scroll">
Dining Philosophers
Concurrent threads - to execute a statement or a block of code
3 - Kant thinking - L
4 - Spinoza thinking- R
5 - Marx thinking- R
8 - Aristotle thinking - L
60 - Russell thinking- R
77 - Marx thinking- R
514 - Spinoza eating 4- R
729 - Kant thinking - L
734 - Aristotle thinking - L
736 - Spinoza eating 3- R
737 - Marx thinking- R
738 - Russell thinking- R
1058 - Aristotle thinking - L
1059 - Kant thinking - L
1060 - Spinoza eating 2- R
..................................
6182 - Aristotle thinking- R
6195 - Kant thinking - L
6196 - Spinoza eating 8 - L
6227 - Marx thinking- R
6228 - Russell eating 3- R
6238 - Spinoza eating 7 - L
6260 - Aristotle thinking- R
6303 - Kant thinking - L
6306 - Russell eating 2- R
6340 - Spinoza eating 6 - L
6342 - Russell eating 1- R
</pre >
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">names = <|1 -> "Aristotle", 2 -> "Kant", 3 -> "Spinoza", 4 -> "Marx", 5 -> "Russell"|>;
n = Length[names];
rp := Pause[RandomReal[4]];
PrintTemporary[Dynamic[Array[forks, n]]];
Clear[forks]; forks[_] := Null;
With[{nf = n},
ParallelDo[
With[{i1 = i, i2 = Mod[i + 1, nf, 1]},
Do[Print[names[i], " thinking"]; rp; Print[names[i], " hungry"];
CriticalSection[{forks[i1], forks[i2]},
Print[names[i], " eating"]; rp],
{2}]],
{i, nf}]];</syntaxhighlight>
{{out}}
<pre>Aristotle thinking
Kant thinking
Spinoza thinking
Marx thinking
Russell thinking
Russell hungry
Russell eating</pre>
=={{header|Modula-3}}==
Line 3,767 ⟶ 4,884:
While this implementation is not a translation of the [[#Eiffel|Eiffel]] solution, it still owes it a heads-up for the basic principle. Bertrand Meyer's ACM Webinar on [https://en.wikipedia.org/wiki/SCOOP_(software) SCOOP] directed my attention to this problem, and probably influenced the solution.
<
IMPORT IO, Random, Thread;
Line 3,867 ⟶ 4,984:
EVAL Thread.Join(thread[i]);
END;
END DiningPhilosophers.</
{{out}}
Line 3,887 ⟶ 5,004:
=={{header|Nim}}==
Prevents deadlocks by ordering the forks. Compile with <code>nim --threads:on c diningphilosophers.nim</code>
<
# to call randomize() as a seed, need to import random module
randomize()
Line 3,933 ⟶ 5,050:
createThread(threads[i], run, phils[i])
joinThreads(threads)</
=={{header|OxygenBasic}}==
<
'=========================
class RoundTableWith5Seats
Line 4,038 ⟶ 5,155:
'4 dining 8 1 1
'5 thinks 0 1 0
</syntaxhighlight>
=={{header|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.
<
Philosophers = [aristotle kant spinoza marx russell]
Line 4,159 ⟶ 5,276:
ShowInfo = System.showInfo
in
{Start}</
=={{header|Pascal}}==
This FreePascal implementation uses the idea of ordered resourses, each fork is numbered by index in the array.
In order to avoid deadlocks each member first takes fork with lower number.
<syntaxhighlight lang="pascal">
program dining_philosophers;
{$mode objfpc}{$H+}
uses
{$IFDEF UNIX}
cthreads,
{$ENDIF}
Classes, SysUtils, SyncObjs;
const
PHIL_COUNT = 5;
LIFESPAN = 7;
DELAY_RANGE = 950;
DELAY_LOW = 50;
PHIL_NAMES: array[1..PHIL_COUNT] of string = ('Aristotle', 'Kant', 'Spinoza', 'Marx', 'Russell');
type
TFork = TCriticalSection;
TPhilosopher = class;
var
Forks: array[1..PHIL_COUNT] of TFork;
Philosophers: array[1..PHIL_COUNT] of TPhilosopher;
type
TPhilosopher = class(TThread)
private
FName: string;
FFirstFork, FSecondFork: TFork;
protected
procedure Execute; override;
public
constructor Create(const aName: string; aForkIdx1, aForkIdx2: Integer);
end;
procedure TPhilosopher.Execute;
var
LfSpan: Integer = LIFESPAN;
begin
while LfSpan > 0 do
begin
Dec(LfSpan);
WriteLn(FName, ' sits down at the table');
FFirstFork.Acquire;
FSecondFork.Acquire;
WriteLn(FName, ' eating');
Sleep(Random(DELAY_RANGE) + DELAY_LOW);
FSecondFork.Release;
FFirstFork.Release;
WriteLn(FName, ' is full and leaves the table');
if LfSpan = 0 then
continue;
WriteLn(FName, ' thinking');
Sleep(Random(DELAY_RANGE) + DELAY_LOW);
WriteLn(FName, ' is hungry');
end;
end;
constructor TPhilosopher.Create(const aName: string; aForkIdx1, aForkIdx2: Integer);
begin
inherited Create(True);
FName := aName;
if aForkIdx1 < aForkIdx2 then
begin
FFirstFork := Forks[aForkIdx1];
FSecondFork := Forks[aForkIdx2];
end
else
begin
FFirstFork := Forks[aForkIdx2];
FSecondFork := Forks[aForkIdx1];
end;
end;
procedure DinnerBegin;
var
I: Integer;
Phil: TPhilosopher;
begin
for I := 1 to PHIL_COUNT do
Forks[I] := TFork.Create;
for I := 1 to PHIL_COUNT do
Philosophers[I] := TPhilosopher.Create(PHIL_NAMES[I], I, Succ(I mod PHIL_COUNT));
for Phil in Philosophers do
Phil.Start;
end;
procedure WaitForDinnerOver;
var
Phil: TPhilosopher;
Fork: TFork;
begin
for Phil in Philosophers do
begin
Phil.WaitFor;
Phil.Free;
end;
for Fork in Forks do
Fork.Free;
end;
begin
Randomize;
DinnerBegin;
WaitForDinnerOver;
end.
</syntaxhighlight>
The next variant exploits the idea of a single left-handed philosopher.
<syntaxhighlight lang="pascal">
program dining_philosophers2;
{$mode objfpc}{$H+}
uses
{$IFDEF UNIX}
cthreads,
{$ENDIF}
Classes, SysUtils, SyncObjs;
const
PHIL_COUNT = 5;
LIFESPAN = 7;
DELAY_RANGE = 950;
DELAY_LOW = 50;
PHIL_NAMES: array[1..PHIL_COUNT] of string = ('Aristotle', 'Kant', 'Spinoza', 'Marx', 'Russell');
type
TFork = TCriticalSection;
TPhilosopher = class;
var
Forks: array[1..PHIL_COUNT] of TFork;
Philosophers: array[1..PHIL_COUNT] of TPhilosopher;
type
TPhilosopher = class(TThread)
private
FName: string;
FLeftFork, FRightFork: TFork;
FLefty: Boolean;
procedure SetLefty(aValue: Boolean);
procedure SwapForks;
protected
procedure Execute; override;
public
constructor Create(const aName: string; aForkIdx1, aForkIdx2: Integer);
property Lefty: Boolean read FLefty write SetLefty;
end;
procedure TPhilosopher.SetLefty(aValue: Boolean);
begin
if Lefty = aValue then
exit;
FLefty := aValue;
SwapForks;
end;
procedure TPhilosopher.SwapForks;
var
Fork: TFork;
begin
Fork := FLeftFork;
FLeftFork := FRightFork;
FRightFork := Fork;
end;
procedure TPhilosopher.Execute;
var
LfSpan: Integer = LIFESPAN;
begin
while LfSpan > 0 do
begin
Dec(LfSpan);
WriteLn(FName, ' sits down at the table');
FLeftFork.Acquire;
FRightFork.Acquire;
WriteLn(FName, ' eating');
Sleep(Random(DELAY_RANGE) + DELAY_LOW);
FRightFork.Release;
FLeftFork.Release;
WriteLn(FName, ' is full and leaves the table');
if LfSpan = 0 then
continue;
WriteLn(FName, ' thinking');
Sleep(Random(DELAY_RANGE) + DELAY_LOW);
WriteLn(FName, ' is hungry');
end;
end;
constructor TPhilosopher.Create(const aName: string; aForkIdx1, aForkIdx2: Integer);
begin
inherited Create(True);
FName := aName;
FLeftFork := Forks[aForkIdx1];
FRightFork := Forks[aForkIdx2];
end;
procedure DinnerBegin;
var
I: Integer;
Phil: TPhilosopher;
begin
for I := 1 to PHIL_COUNT do
Forks[I] := TFork.Create;
for I := 1 to PHIL_COUNT do
Philosophers[I] := TPhilosopher.Create(PHIL_NAMES[I], I, Succ(I mod PHIL_COUNT));
Philosophers[Succ(Random(5))].Lefty := True;
for Phil in Philosophers do
Phil.Start;
end;
procedure WaitForDinnerOver;
var
Phil: TPhilosopher;
Fork: TFork;
begin
for Phil in Philosophers do
begin
Phil.WaitFor;
Phil.Free;
end;
for Fork in Forks do
Fork.Free;
end;
begin
Randomize;
DinnerBegin;
WaitForDinnerOver;
end.
</syntaxhighlight>
Another way to avoid deadlock: if a philosopher takes left fork but cannot take the right fork, he returns the left fork.
<syntaxhighlight lang="pascal">
program dining_philosophers3;
{$mode objfpc}{$H+}
uses
{$IFDEF UNIX}
cthreads,
{$ENDIF}
Classes, SysUtils, SyncObjs;
const
PHIL_COUNT = 5;
LIFESPAN = 7;
DELAY_RANGE = 950;
DELAY_LOW = 50;
PHIL_NAMES: array[1..PHIL_COUNT] of string = ('Aristotle', 'Kant', 'Spinoza', 'Marx', 'Russell');
type
TFork = TCriticalSection;
TPhilosopher = class;
var
Forks: array[1..PHIL_COUNT] of TFork;
Philosophers: array[1..PHIL_COUNT] of TPhilosopher;
type
TPhilosopher = class(TThread)
private
FName: string;
FLeftFork, FRightFork: TFork;
protected
procedure Execute; override;
public
constructor Create(const aName: string; aForkIdx1, aForkIdx2: Integer);
end;
procedure TPhilosopher.Execute;
var
LfSpan: Integer = LIFESPAN;
begin
while LfSpan > 0 do
begin
Dec(LfSpan);
WriteLn(FName, ' sits down at the table');
repeat
FLeftFork.Acquire;
if not FRightFork.TryEnter then
begin
FLeftFork.Release;
Sleep(Random(DELAY_RANGE));
continue;
end;
break;
until False;
WriteLn(FName, ' eating');
Sleep(Random(DELAY_RANGE) + DELAY_LOW);
FRightFork.Release;
FLeftFork.Release;
WriteLn(FName, ' is full and leaves the table');
if LfSpan = 0 then
continue;
WriteLn(FName, ' thinking');
Sleep(Random(DELAY_RANGE) + DELAY_LOW);
WriteLn(FName, ' is hungry');
end;
end;
constructor TPhilosopher.Create(const aName: string; aForkIdx1, aForkIdx2: Integer);
begin
inherited Create(True);
FName := aName;
FLeftFork := Forks[aForkIdx1];
FRightFork := Forks[aForkIdx2];
end;
procedure DinnerBegin;
var
I: Integer;
Phil: TPhilosopher;
begin
for I := 1 to PHIL_COUNT do
Forks[I] := TFork.Create;
for I := 1 to PHIL_COUNT do
Philosophers[I] := TPhilosopher.Create(PHIL_NAMES[I], I, Succ(I mod PHIL_COUNT));
for Phil in Philosophers do
Phil.Start;
end;
procedure WaitForDinnerOver;
var
Phil: TPhilosopher;
Fork: TFork;
begin
for Phil in Philosophers do
begin
Phil.WaitFor;
Phil.Free;
end;
for Fork in Forks do
Fork.Free;
end;
begin
Randomize;
DinnerBegin;
WaitForDinnerOver;
end.
</syntaxhighlight>
And the last: deadlock can only happen if all the members are seated at the table.
This variant tries to avoid this situation.
<syntaxhighlight lang="pascal">
program dining_philosophers4;
{$mode objfpc}{$H+}
uses
{$IFDEF UNIX}
cthreads,
{$ENDIF}
Classes, SysUtils, SyncObjs;
const
PHIL_COUNT = 5;
LIFESPAN = 7;
DELAY_RANGE = 950;
DELAY_LOW = 50;
PHIL_NAMES: array[1..PHIL_COUNT] of string = ('Aristotle', 'Kant', 'Spinoza', 'Marx', 'Russell');
type
TFork = TCriticalSection;
TPhilosopher = class;
var
Forks: array[1..PHIL_COUNT] of TFork;
Philosophers: array[1..PHIL_COUNT] of TPhilosopher;
StilDining: Integer = 0;
procedure WaitForPlaceFree;
begin
repeat
if InterlockedIncrement(StilDining) > Pred(PHIL_COUNT) then
begin
InterlockedDecrement(StilDining);
Sleep(Random(DELAY_LOW));
continue;
end;
exit;
until False;
end;
procedure FreePlace;
begin
InterLockedDecrement(StilDining);
end;
type
TPhilosopher = class(TThread)
private
FName: string;
FLeftFork, FRightFork: TFork;
protected
procedure Execute; override;
public
constructor Create(const aName: string; aForkIdx1, aForkIdx2: Integer);
end;
procedure TPhilosopher.Execute;
var
LfSpan: Integer = LIFESPAN;
begin
while LfSpan > 0 do
begin
Dec(LfSpan);
WaitForPlaceFree;
WriteLn(FName, ' sits down at the table');
FLeftFork.Acquire;
FRightFork.Acquire;
WriteLn(FName, ' eating');
Sleep(Random(DELAY_RANGE) + DELAY_LOW);
FRightFork.Release;
FLeftFork.Release;
FreePlace;
WriteLn(FName, ' is full and leaves the table');
if LfSpan = 0 then
continue;
WriteLn(FName, ' thinking');
Sleep(Random(DELAY_RANGE) + DELAY_LOW);
WriteLn(FName, ' is hungry');
end;
end;
constructor TPhilosopher.Create(const aName: string; aForkIdx1, aForkIdx2: Integer);
begin
inherited Create(True);
FName := aName;
FLeftFork := Forks[aForkIdx1];
FRightFork := Forks[aForkIdx2];
end;
procedure DinnerBegin;
var
I: Integer;
Phil: TPhilosopher;
begin
for I := 1 to PHIL_COUNT do
Forks[I] := TFork.Create;
for I := 1 to PHIL_COUNT do
Philosophers[I] := TPhilosopher.Create(PHIL_NAMES[I], I, Succ(I mod PHIL_COUNT));
for Phil in Philosophers do
Phil.Start;
end;
procedure WaitForDinnerOver;
var
Phil: TPhilosopher;
Fork: TFork;
begin
for Phil in Philosophers do
begin
Phil.WaitFor;
Phil.Free;
end;
for Fork in Forks do
Fork.Free;
end;
begin
Randomize;
DinnerBegin;
WaitForDinnerOver;
end.
</syntaxhighlight>
=={{header|Perl}}==
This solution requires that perl have been compiled with threads enabled.
Line 4,166 ⟶ 5,733:
grab their forks in opposite orders.
<syntaxhighlight lang="perl">
use threads;
use threads::shared;
Line 4,217 ⟶ 5,784:
print "Done\n";
__END__
</syntaxhighlight>
====One solution based on Coro and AnyEvent====
To prevent deadlock the philosophers must not start eating at the same time and the time between getting the first fork and getting second one must be shorter as possible.
<syntaxhighlight lang="perl">
#!/usr/bin/perl
use common::sense;
Line 4,234 ⟶ 5,801:
my @fork_sem;
$fork_sem[$_] =
Line 4,263 ⟶ 5,830:
EV::loop;
</syntaxhighlight>
=={{header|Phix}}==
Line 4,386 ⟶ 5,838:
If you uncomment the sleep(1)s you will probably want do the same to the terminate checks, otherwise after keying 'Q' or Escape it could take 20 seconds per diner to finish.
<!--<syntaxhighlight lang="phix">(notonline)-->
<span style="color: #008080;">without</span> <span style="color: #008080;">js</span> <span style="color: #000080;font-style:italic;">-- threads</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">fork1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">init_cs</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">fork2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">init_cs</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">fork3</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">init_cs</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">fork4</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">init_cs</span><span style="color: #0000FF;">(),</span>
<span style="color: #000000;">fork5</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">init_cs</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">terminate</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- control flag</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">person</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">name</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">left_fork</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">right_fork</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (except Russell, who gets left and right the other way round)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">terminate</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">enter_cs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">left_fork</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">enter_cs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">right_fork</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">name</span> <span style="color: #0000FF;">&</span> <span style="color: #008000;">" grabs forks.\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- if terminate then exit end if</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">name</span> <span style="color: #0000FF;">&</span> <span style="color: #008000;">" is eating.\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- sleep(1)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">name</span> <span style="color: #0000FF;">&</span> <span style="color: #008000;">" puts forks down and leaves the dinning room.\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">leave_cs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">left_fork</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">leave_cs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">right_fork</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">rand</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000080;font-style:italic;">-- if terminate then exit end if</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">name</span> <span style="color: #0000FF;">&</span> <span style="color: #008000;">" is thinking.\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- sleep(1)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">name</span> <span style="color: #0000FF;">&</span> <span style="color: #008000;">" becomes hungry.\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">r_person</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"person"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">threads</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">create_thread</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r_person</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"Aristotle"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fork1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fork2</span><span style="color: #0000FF;">}),</span>
<span style="color: #000000;">create_thread</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r_person</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"Kant"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fork2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fork3</span><span style="color: #0000FF;">}),</span>
<span style="color: #000000;">create_thread</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r_person</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"Spinoza"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fork3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fork4</span><span style="color: #0000FF;">}),</span>
<span style="color: #000000;">create_thread</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r_person</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"Marx"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fork4</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fork5</span><span style="color: #0000FF;">}),</span>
<span style="color: #000080;font-style:italic;">-- create_thread(r_person,{"Russell",fork5,fork1})} -- this will deadlock!</span>
<span style="color: #000000;">create_thread</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r_person</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"Russell"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fork1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fork5</span><span style="color: #0000FF;">})}</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">ESC</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">#1B</span>
<span style="color: #008080;">while</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_key</span><span style="color: #0000FF;">(),{</span><span style="color: #000000;">ESC</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'q'</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'Q'</span><span style="color: #0000FF;">})</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">sleep</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">terminate</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">wait_thread</span><span style="color: #0000FF;">(</span><span style="color: #000000;">threads</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (not strictly necessary)</span>
<span style="color: #000000;">delete_cs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fork1</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- ""</span>
<span style="color: #000000;">delete_cs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fork2</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">delete_cs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fork3</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">delete_cs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fork4</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">delete_cs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fork5</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
=={{header|PicoLisp}}==
Line 4,444 ⟶ 5,899:
Another solution, using the Chandy/Misra method, can be found
[http://logand.com/sw/phil.l here].
<
(loop
(prinl Name ": " State)
Line 4,479 ⟶ 5,934:
'("ForkA" "ForkB" "ForkC" "ForkD" "ForkE" .) ) )
(push '*Bye '(mapc kill *Philosophers)) # Terminate all upon exit</
Output:
<pre>Aristotle: hungry
Line 4,501 ⟶ 5,956:
using Pike Backend call_out(), this solution avoids deadlocks by adding a 20% chance that a philosopher drops the fork if he can't pick up both.
<
{
string name;
Line 4,594 ⟶ 6,049:
call_out(philosophers[4]->take_forks, random(5));
return -1;
}</
=={{header|Prolog}}==
Line 4,600 ⟶ 6,055:
Use the same solution as in Erlang (a waiter gives the forks to philosophers).<br>
Bonus : the code of an animation in XPCE is given, and statistics are displayed at the end of the process.
<
new(D, window('Dining philosophers')),
new(S, window('Dining philosophers : statistics')),
Line 5,049 ⟶ 6,504:
:- pce_end_class.
</syntaxhighlight>
[[File:Prolog-Philosophers-1.png|500px|thumb|center]]<br><br> [[File:Prolog-Philosophers-3.png|450px|thumb|center]]
Line 5,057 ⟶ 6,512:
put down the first and waits a few breaths, then boldly tries in the opposite order.
<
LockMutex(Mutex)
LastElement(Queue())
Line 5,173 ⟶ 6,628:
Delay(Random(2500)+25)
ForEver
EndProcedure</
=={{header|Python}}==
===With the threading library===
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).
<
import random
import time
Line 5,233 ⟶ 6,691:
def DiningPhilosophers():
forks = [threading.Lock() for n in range(5)]
philosopherNames = ('Aristotle','Kant','
philosophers= [Philosopher(philosopherNames[i], forks[i%5], forks[(i+1)%5]) \
Line 5,245 ⟶ 6,703:
print ("Now we're finishing.")
DiningPhilosophers()</
===With the multiprocessing library===
This version uses the multiprocessing library to achieve concurrency on multiple CPUs. (Threads run on a single CPU and are run in "turns". The Python threading library simulate concurrency.)
Some other improvements and modifications: configurable number of philosophers, "more deterministic" randomization by pre-allocating the thinking and dining schedules, time scaling to allow faster runs producing results that are essentially the same, collect statistics on wait times, attempt to check for deadlock, adds more algorithms, including a naive to demonstrate deadlock and two symmetry breaking one versions.
Changed forks to chopsticks. Sorry Edsger, nobody (not even philosophers) need two forks to eat with. Furthermore, using 'fork' may cause confusion, since fork has a meaning in the context of concurrent programming.
<syntaxhighlight lang="python">
"""Dining philosophers with multiprocessing module."""
import multiprocessing as mp
import random
import time
# Dining philosophers. See also comments at the threading
# version. Improvements, modifications:
# Support variable number of philosophers.
# "More deterministic" randomization by prealocating the schedules.
# Use scaling to allow faster runs producing results that are
# essentially the same.
# Collect statistics on wait times.
SCALE = 0.2
THINK = (3, 13)
DINE = (1, 10)
class Philosopher(mp.Process):
"""Independently running philosopher processes."""
def __init__(self, idx, name, run_flag, chopstick_left, chopstick_right,
stats, schedule_think, schedule_dine):
mp.Process.__init__(self)
self.idx = idx
self.name = name
self.run_flag = run_flag
self.chopstick_left = chopstick_left
self.chopstick_right = chopstick_right
self.stats = stats
self.schedule_think = schedule_think
self.schedule_dine = schedule_dine
self.counter = 0
self.num_dined = 0
self.hungry_time_total = 0.0
self.hungry_time_max = 0.0
def run(self):
while self.run_flag.value and self.counter < len(self.schedule_think):
# Philosopher is thinking (but really is sleeping).
time.sleep(self.schedule_think[self.counter]*SCALE)
duration = -time.perf_counter()
print(f'{self.name} is hungry', flush=True)
self.get_chopsticks2()
duration += time.perf_counter()
self.hungry_time_total += duration
self.hungry_time_max = max(self.hungry_time_max, duration)
self.dining()
# Populate self.stats:
self.stats.put({'name': self.name,
'num_dined': self.num_dined,
'hungry_time_total': self.hungry_time_total,
'hungry_time_max': self.hungry_time_max})
def get_chopsticks(self):
"""Use swaps and do not hold on to chopsticks."""
chopstick1, chopstick2 = self.chopstick_left, self.chopstick_right
while True:
chopstick1.acquire(True)
locked = chopstick2.acquire(False)
if locked:
return
chopstick1.release()
print(f'{self.name} swaps chopsticks', flush=True)
chopstick1, chopstick2 = chopstick2, chopstick1
def get_chopsticks0(self):
"""Naive greedy implementation to trigger deadlock."""
self.chopstick_left.acquire(True)
time.sleep(0.1)
self.chopstick_right.acquire(True)
def get_chopsticks1(self):
"""Break the symmetry by having one philosopher to be left handed."""
if self.idx == 0:
chopstick1, chopstick2 = self.chopstick_left, self.chopstick_right
else:
chopstick1, chopstick2 = self.chopstick_right, self.chopstick_left
chopstick1.acquire(True)
locked = chopstick2.acquire(False)
if not locked:
chopstick1.release()
chopstick2.acquire(True)
chopstick1.acquire(True)
def get_chopsticks2(self):
"""Break the symmetry by having the even numbered philosophers to be
left handed."""
if self.idx == 0:
chopstick1, chopstick2 = self.chopstick_left, self.chopstick_right
else:
chopstick1, chopstick2 = self.chopstick_right, self.chopstick_left
chopstick1.acquire(True)
locked = chopstick2.acquire(False)
if not locked:
chopstick1.release()
chopstick2.acquire(True)
chopstick1.acquire(True)
def dining(self):
"""Dining with two chopsticks."""
print(f'{self.name} starts eating', flush=True)
self.num_dined += 1
time.sleep(self.schedule_dine[self.counter]*SCALE)
self.counter += 1
print(f'{self.name} finishes eating and leaves to think.', flush=True)
self.chopstick_left.release()
self.chopstick_right.release()
def performance_report(stats):
"""Print some stats about the wait times."""
print("Performance report:")
for queue in stats:
data = queue.get()
print(f"Philosopher {data['name']} dined {data['num_dined']} times. ")
print(f" Total wait : {data['hungry_time_total'] / SCALE}")
print(f" Max wait : {data['hungry_time_max'] / SCALE}")
if data['num_dined'] > 0:
print(f" Average wait: "
f"{data['hungry_time_total'] / data['num_dined']/SCALE}")
def generate_philosophers(names, run_flag, chopsticks, stats, max_dine):
"""Gebnerate a list of philosophers with random schedules."""
num = len(names)
philosophers = [Philosopher(i, names[i], run_flag,
chopsticks[i % num],
chopsticks[(i+1) % num],
stats[i],
[random.uniform(THINK[0], THINK[1])
for j in range(max_dine)],
[random.uniform(DINE[0], DINE[1])
for j in range(max_dine)])
for i in range(num)]
return philosophers
def generate_philosophers0(names, run_flag, chopsticks, stats,
schedule_think, schedule_dine):
"""Allows the use of a predetermined thinking and dining schedule.
This may aid in triggering a deadlock."""
num = len(names)
philosophers = [Philosopher(i, names[i], run_flag,
chopsticks[i % num],
chopsticks[(i+1) % num],
stats[i],
schedule_think[i],
schedule_dine[i])
for i in range(num)]
return philosophers
def dining_philosophers(philosopher_names=(('Aristotle', 'Kant',
'Buddha', 'Marx', 'Russel')),
num_sec=100, max_dine=100):
"""Main routine."""
num = len(philosopher_names)
chopsticks = [mp.Lock() for n in range(num)]
random.seed(507129)
run_flag = mp.Value('b', True)
stats = [mp.Queue() for n in range(num)]
philosophers = generate_philosophers(philosopher_names, run_flag,
chopsticks, stats, max_dine)
# Use the following when trying to trigger a deadlock in conjunction with
# get_chopsticks0():
#philosophers = generate_philosophers0(philosopher_names, run_flag,
# chopsticks, stats, [3]*max_dine,
# [5]*max_dine)
for phi in philosophers:
phi.start()
time.sleep(num_sec*SCALE)
run_flag.value = False
print("Now we're finishing.", flush=True)
# We want to allow the philosophers to finish their meal. In fact,
# we even allow them to still start eating if they are presently
# hungry. This means we may need to wait at most num*DINE[1].
wait_time = num*DINE[1]
while wait_time >= 0 and sum(p.is_alive() for p in philosophers) > 0:
time.sleep(1)
wait_time -= 1.0
if wait_time < 0:
for phi in philosophers:
if phi.is_alive():
print(f"Ooops, {phi.name} has not finished!!")
phi.terminate()
return 1
performance_report(stats)
if __name__ == '__main__':
dining_philosophers()
</syntaxhighlight>
=={{header|Racket}}==
<
#lang racket
Line 5,337 ⟶ 6,997:
(run)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|rakudo|2015-09-09}}
We use locking mutexes for the forks, and a lollipop to keep the last person who finished eating from getting hungry until the next person finishes eating, which prevents a cycle of dependency from forming. The algorithm should scale to many philosophers, and no philosopher need be singled out to be left-handed, so it's fair in that sense.
<syntaxhighlight lang="raku" line>class Fork {
has $!lock = Lock.new;
method grab($who, $which) {
say "$who grabbing $which fork";
$!lock.lock;
}
method drop($who, $which) {
say "$who dropping $which fork";
$!lock.unlock;
}
}
class Lollipop {
has $!channel = Channel.new;
method mine($who) { $!channel.send($who) }
method yours { $!channel.receive }
}
sub dally($sec) { sleep 0.01 + rand * $sec }
sub MAIN(*@names) {
@names ||= <Aristotle Kant Spinoza Marx Russell>;
my @lfork = Fork.new xx @names;
my @rfork = @lfork.rotate;
my $lollipop = Lollipop.new;
start { $lollipop.yours; }
my @philosophers = do for flat @names Z @lfork Z @rfork -> $n, $l, $r {
start {
sleep 1 + rand*4;
loop {
$l.grab($n,'left');
dally 1; # give opportunity for deadlock
$r.grab($n,'right');
say "$n eating";
dally 10;
$l.drop($n,'left');
$r.drop($n,'right');
$lollipop.mine($n);
sleep 1; # lick at least once
say "$n lost lollipop to $lollipop.yours(), now digesting";
dally 20;
}
}
}
sink await @philosophers;
}</syntaxhighlight>
{{out}}
<pre>Aristotle grabbing left fork
Aristotle grabbing right fork
Aristotle eating
Marx grabbing left fork
Marx grabbing right fork
Marx eating
Spinoza grabbing left fork
Aristotle dropping left fork
Aristotle dropping right fork
Russell grabbing left fork
Kant grabbing left fork
Kant grabbing right fork
Spinoza grabbing right fork
Marx dropping left fork
Marx dropping right fork
Aristotle lost lollipop to Marx, now digesting
Spinoza eating
Spinoza dropping left fork
Spinoza dropping right fork
Kant eating
Russell grabbing right fork
Russell eating
Marx lost lollipop to Spinoza, now digesting
Kant dropping left fork
Kant dropping right fork
Spinoza lost lollipop to Kant, now digesting
Russell dropping left fork
Russell dropping right fork
Kant lost lollipop to Russell, now digesting
Spinoza grabbing left fork
Spinoza grabbing right fork
Spinoza eating
Aristotle grabbing left fork
Aristotle grabbing right fork
Aristotle eating
Aristotle dropping left fork
Aristotle dropping right fork
Russell lost lollipop to Aristotle, now digesting
Spinoza dropping left fork
Spinoza dropping right fork
Aristotle lost lollipop to Spinoza, now digesting
Russell grabbing left fork
Marx grabbing left fork
Russell grabbing right fork
Russell eating
Marx grabbing right fork
Kant grabbing left fork
Kant grabbing right fork
Kant eating
Russell dropping left fork
Russell dropping right fork
Spinoza lost lollipop to Russell, now digesting
Marx eating
Spinoza grabbing left fork
Kant dropping left fork
Kant dropping right fork
Russell lost lollipop to Kant, now digesting
Spinoza grabbing right fork
^C</pre>
=={{header|REXX}}==
Programming notes: This REXX version allows a specification of the names and numbers of dining philosophers (but no check was made
Deadlocks are eliminated by the method of acquiring the resources (forks): both forks are (attempted to be) grabbed at the same time (by both hands).
<
signal on halt /*branches to HALT: (on Ctrl─break).*/
parse arg seed diners /*obtain optional arguments from the CL*/
if datatype(seed, 'W') then call random ,, seed /*this allows for random repeatability.*/
if diners= '' then diners = 'Aristotle, Kant, Spinoza, Marx, Russell'
tell=
diners= space( translate(diners, , ',') )
#= words(diners); @.=
eatL= 15; eatH=
thinkL= 30; thinkH=
forks.=
do tic=1 /*'til halted.*/
end /*tic*/
/* [↓] this REXX program was halted,*/
halt: say ' ··· REXX program halted!' /*probably by Ctrl─Break or equivalent.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
fork: parse arg x 1 ox; x= abs(x) ;
if ox<0 then do; forks.L= 1; forks.x=1; return; end /*drop the forks.
got2= forks.L & forks.x
if got2 then do; forks.L= 0; forks.x=0; end /*obtained 2 forks
return got2 /*return with success ··· or failure. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
grabForks: do person=1 for # /*see if any person can grab two forks.*/
if @.person.state\==0 then iterate /*this diner ain't in a waiting state. */
if \fork(person) then iterate /*
@.person.state= 'eating' /*
@.person.dur= random(eatL, eatH)
end /*person*/ /* [↑] process the dining philosophers*/
return /*all the diners have been examined. */
Line 5,386 ⟶ 7,162:
call fork -p /*drop the darn forks. */
@.p.state= 'thinking' /*status.*/
@.p.dur= random(thinkL, thinkH)
end /* [↓] a diner goes ──► the table. */
else if @.p.state=='thinking' then @.p.state=0
end /*p*/ /*[↑] P (person)≡ dining philosophers.*/
return /*now, have some human beans grab forks*/</syntaxhighlight>
{{out|output|text= (some middle and end portions have been elided):
<pre>
Line 5,420 ⟶ 7,196:
{{works with|Ruby|1.8.7}}
<
class Philosopher
Line 5,489 ⟶ 7,265:
end
philosophers.each {|thread| thread.join}</
=={{header|Rust}}==
A Rust implementation of a solution for the Dining Philosophers Problem. We prevent a deadlock by using Dijkstra's solution of making a single diner "left-handed." That is, all diners except one pick up the chopstick "to their left" and then the chopstick "to their right." The remaining diner performs this in reverse.
<
use std::sync::{Mutex, Arc};
Line 5,556 ⟶ 7,332:
h.join().unwrap();
}
}</
=={{header|Simula}}==
<
! DEADLOCK IS PREVENTED BY REVERSING THE ORDER OF TAKING THE CHOPSTICKS FOR THE LAST PHILOSOPHER.
! THAT MEANS ALL PHILOSOPHERS FIRST TAKE THE LEFT CHOPSTICK, THEN THE RIGHT CHOPSTICK.
Line 5,719 ⟶ 7,496:
END;
END.</
{{in}}
<pre>
Line 5,821 ⟶ 7,598:
This solution is similar to the Python solution, except this uses Semaphore instances for forks and an OrderedCollection to hold sequence of forks and philosophers around the table. The method #pickUpForks releases and retries after a small delay till it has both. <b>Special note:</b> Smalltalk concurrent processes are created by sending the message #fork to a block. Do not confuse this method name with the forks of the problem domain.
<
Object subclass: #Philosopher
instanceVariableNames: 'table random name seat forks running'
Line 5,918 ⟶ 7,695:
#('Aristotle' 'Kant' 'Buddha' 'Marx' 'Russel' )
do: [:aName | Philosopher new beginDining: aName at: diningTable]! !
</syntaxhighlight>
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<
foreach name {Aristotle Kant Spinoza Marx Russel} {
Line 5,989 ⟶ 7,766:
foreach t $tasks {
thread::send -async $t thread::exit
}</
=={{header|VBA}}==
Line 5,995 ⟶ 7,772:
philosopher separately, as if in separate threads. Program terminates after max count is reached. Statistics show how many
program ticks are spent at each step at the dining table.
<
'(HOLDON=True) and all philosophers start
'with same hand (DIJKSTRASOLUTION=False) leads
Line 6,090 ⟶ 7,867:
dine
show
End Sub</
<pre>Stats Gets Gets Eats Puts Puts Thinks
First Second Spag- First Second About
Line 6,100 ⟶ 7,877:
Erasmus 5998 1556 5891 550 550 5455
</pre>
=={{header|Visual Basic .NET}}==
Line 6,108 ⟶ 7,886:
* 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.
<
Module Module1
Public rnd As New Random
Line 6,157 ⟶ 7,935:
End Sub
End Module</
<
Private ReadOnly m_Number As Integer
Public Sub New(ByVal number As Integer)
Line 6,169 ⟶ 7,947:
End Get
End Property
End Class</
<
Implements IDisposable
Line 6,201 ⟶ 7,979:
Public MustOverride Sub MainLoop()
End Class</
=== Deadlock ===
<
Inherits PhilosopherBase
Public Sub New(ByVal name As String, ByVal right As Fork, ByVal left As Fork)
Line 6,235 ⟶ 8,013:
End Sub
End Class</
=== Live Lock ===
<
Inherits PhilosopherBase
Line 6,278 ⟶ 8,056:
End Sub
End Class</
=== Working ===
<
Inherits PhilosopherBase
Public Sub New(ByVal name As String, ByVal right As Fork, ByVal left As Fork)
Line 6,321 ⟶ 8,099:
End Sub
End Class</
=={{header|Wren}}==
This is loosely based on the Kotlin entry.
However, Wren uses co-operatively scheduled fibers rather than threads for concurrency and, as long as a philosoper waits until he can pick up both forks to eat, deadlock is impossible because only one fiber can run at a time.
<syntaxhighlight lang="wren">import "random" for Random
import "scheduler" for Scheduler
import "timer" for Timer
var Rand = Random.new()
var ForkInUse = List.filled(5, false)
class Fork {
construct new(name, index) {
_name = name
_index = index
}
index { _index }
pickUp(philosopher) {
System.print(" %(philosopher) picked up %(_name)")
ForkInUse[index] = true
}
putDown(philosopher) {
System.print(" %(philosopher) put down %(_name)")
ForkInUse[index] = false
}
}
class Philosopher {
construct new(pname, f1, f2) {
_pname = pname
_f1 = f1
_f2 = f2
}
delay() { Timer.sleep(Rand.int(300) + 100) }
eat() {
(1..5).each { |bite| // limit to 5 bites say
while (true) {
System.print("%(_pname) is hungry")
if (!ForkInUse[_f1.index] && !ForkInUse[_f2.index]) {
_f1.pickUp(_pname)
_f2.pickUp(_pname)
break
}
System.print("%(_pname) is unable to pick up both forks")
// try again later
delay()
}
System.print("%(_pname) is eating bite %(bite)")
// allow time to eat
delay()
_f2.putDown(_pname)
_f1.putDown(_pname)
// allow other philospohers time to pick up forks
delay()
}
}
}
var diningPhilosophers = Fn.new { |names|
var size = names.count
var forks = List.filled(size, null)
for (i in 0...size) forks[i] = Fork.new("Fork %(i + 1)", i)
var philosophers = []
var i = 0
for (n in names) {
var i1 = i
var i2 = (i + 1) % size
if (i2 < i1) {
i1 = i2
i2 = i
}
var p = Philosopher.new(n, forks[i1], forks[i2])
philosophers.add(p)
i = i + 1
}
// choose a philosopher at random to start eating
var r = Rand.int(size)
// schedule the others to eat later
for (i in 0...size) if (i != r) Scheduler.add { philosophers[i].eat() }
philosophers[r].eat()
}
var names = ["Aristotle", "Kant", "Spinoza", "Marx", "Russell"]
diningPhilosophers.call(names)</syntaxhighlight>
=={{header|zkl}}==
The model used here is five seats, each with two forks. Sn:(Fn,Fn+1). Seat(n+1) shares a fork with seat n and so on. Fork are represented by an atomic bool, a bool that changes state atomically. Each philosopher is a thread. Each philosopher is ambidextrous, leading with a random hand. If the trailing hand can not get a fork, the already in hand fork is put down.
<
seats=(5).pump(List,'wrap(n){ List(forks[n],forks[(n+1)%5]) });
fcn sitAndEat(name,n){ // assigned seating
Line 6,350 ⟶ 8,219:
sitAndEat(name,seat);
}
}</
The setIf method atomically sets the bool to the first value if it is currently the second value.
<
.apply(philo.launch);
Atomic.sleep(100000); // hang out in the REPL, aka thread keep alive</
{{out}}
<pre>
| |||