Dining philosophers: Difference between revisions

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

 

begin

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

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

 

begin

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

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

 

begin

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

 

=={{header|AutoHotkey}}==

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

CurrentWaitCount++

}

{{out}}

<pre style="height:40ex;overflow:scroll">Aristotle is hungry.

⋮</pre>

 

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

PROC_killtimer(tID%(I%))

NEXT

'''Sample output:'''

<pre>

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

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

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>

return 0;

}

 

=={{header|C sharp|C#}}==

using System;

using System.Collections.Generic;

class Fork { }

}

 

=={{header|C++}}==

Uses C++17

#include <array>

#include <chrono>

}};

Message("It is dark outside...");

<div style="height:10em; overflow:auto; border: 1px solid #AAA">

Dinner started!<br>

. . . .<br>

</div>

 

=={{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))

 

(stop-eating phil)

(Thread/sleep (rand-int max-think-duration)))

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*

(println (str (:name p)

": eating=" (:eating? 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).

 

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.

 

 

;;

(bt:with-lock-held (lock)

(bt:condition-wait condition lock)))))

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

:initial-bindings (cons (cons '*standard-output* *standard-output*)

bt:*default-special-bindings*))))))

{{out}}

Aristotle is hungry

Aristotle is eating

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;

 

}

}

{{out|Sample output}}

<pre>Spinoza is full.

{{Trans|Pascal}}

Just a fix of Pascal version to run in Delphi

program dining_philosophers;

uses

WaitForDinnerOver;

readln;

 

=={{header|E}}==

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)

 

i)

(define tasks (for/vector ((i 5)) (make-task philo i)))

{{out}}

(define (observe dummmy)

(writeln 'observer 'rounds= rounds)

 

(dinner)

<small>

Marx thinking about philosophy. <br>

The example uses numbers (versus names) to identify the philosophers in order to allow the user to vary the number of philosophers.

 

DINING_PHILOSOPHERS

 

end

 

PHILOSOPHER

 

valid_has_eaten_count: has_eaten_count <= round_count

 

FORK

 

end

 

 

=={{header|Elixir}}==

Implements the Chandy-Misra algorithm.

 

defmodule Philosopher do

change_state(pid)

end

 

=={{header|Erlang}}==

===Waiter-based===

%%%

%%% to compile and run:

unregister(diningRoom).

 

Output:

<pre>

</pre>

===Free-thinkers===

%%% This version uses free-running 'phil' agents (actors) and

%%% state machines representing the forks.

.

 

Output:

<pre>

 

=={{header|Euphoria}}==

sequence forks

forks = repeat(FREE,5)

while get_key() = -1 do

task_yield()

 

Sample output:

This solution avoids deadlock by employing a waiter.

 

open System

 

Console.ReadLine() |> ignore

0

 

=={{header|Go}}==

===Channels===

Goroutine synchronization done with Go channels. Deadlock prevented by making one philosopher "left handed."

 

import (

}

fmt.Println("table empty")

Output:

<pre>

 

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 (

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

}

 

 

=={{header|Haskell}}==

Using the built-in Software Transactional Memory in GHC.

 

import Control.Monad

-- All threads exit when the main thread exits.

getLine

 

==Icon and {{header|Unicon}}==

when they can't get both forks and went back to thinking instead. (Take away their grant money.)

 

 

procedure main(A)

}

}

 

A sample run, terminated after some time.

 

=={{header|J}}==

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

) ,&< ''"_) 0 6} ]))@:(,&(;:8$','))@:;

 

 

0.000: All of them start thinking.

0.097: Spinoza starts eating.

5.166: Marx starts eating.

5.915: Marx starts thinking.

 

0.000: All of them start thinking.

0.077: Nezahualcoyotl starts eating.

2.339: Marx starts waiting and thinking about hunger.

2.446: Aristotle starts thinking.

 

 

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=. @:

A`(amend o ((B P A)f))h o (B`0: h) NB. Activity: thinking

[ echo o ( time , ' starts thinking.' ,~ P {:: N)

)

 

 

NB. The simulation code is produced by the sentence,

 

=={{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.

package diningphilosophers;

 

}

}

 

=={{header|JoCaml}}==

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

and e() = will_think "Russell"; eh()

;;

Sample output:

<pre>philosopher Aristotle is thinking

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

 

 

(* now we need to wait and do nothing; nobody will be able to inject godot() *)

Sample output (excerpt):

<pre>t=2: philosopher Aristotle is thinking

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

(* now we need to wait and do nothing; nobody will be able to inject godot() *)

 

 

Sample output:

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

 

runall(tasks)

{{output}}

Aristotle is out of the dining room for now.

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

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

right_chopstick(cs5). % in different order from the other philosophers

 

 

=={{header|M2000 Interpreter}}==

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

 

Module Dining_philosophers (whichplan) {

Form 80, 32

}

Dining_philosophers Random(1,2)

 

 

6342 - Russell eating 1- R

</pre >

 

=={{header|Modula-3}}==

 

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;

EVAL Thread.Join(thread[i]);

END;

 

{{out}}

=={{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()

createThread(threads[i], run, phils[i])

 

 

=={{header|OxygenBasic}}==

'=========================

class RoundTableWith5Seats

'4 dining 8 1 1

'5 thinks 0 1 0

 

=={{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]

ShowInfo = System.showInfo

in

 

=={{header|Pascal}}==

 

In order to avoid deadlocks each member first takes fork with lower number.

program dining_philosophers;

{$mode objfpc}{$H+}

WaitForDinnerOver;

end.

The next variant exploits the idea of ​​a single left-handed philosopher.

program dining_philosophers2;

{$mode objfpc}{$H+}

WaitForDinnerOver;

end.

Another way to avoid deadlock: if a philosopher takes left fork but cannot take the right fork, he returns the left fork.

program dining_philosophers3;

{$mode objfpc}{$H+}

WaitForDinnerOver;

end.

And the last: deadlock can only happen if all the members are seated at the table.

 

This variant tries to avoid this situation.

program dining_philosophers4;

{$mode objfpc}{$H+}

WaitForDinnerOver;

end.

 

=={{header|Perl}}==

grab their forks in opposite orders.

 

use threads;

use threads::shared;

print "Done\n";

__END__

 

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

 

#!/usr/bin/perl

use common::sense;

my @fork_sem;

 

 

 

 

EV::loop;

 

=={{header|Phix}}==

 

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.

 

=={{header|PicoLisp}}==

Another solution, using the Chandy/Misra method, can be found

[http://logand.com/sw/phil.l here].

(loop

(prinl Name ": " State)

'("ForkA" "ForkB" "ForkC" "ForkD" "ForkE" .) ) )

 

Output:

<pre>Aristotle: hungry

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;

call_out(philosophers[4]->take_forks, random(5));

return -1;

 

=={{header|Prolog}}==

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

 

:- pce_end_class.

[[File:Prolog-Philosophers-1.png|500px|thumb|center]]<br><br> [[File:Prolog-Philosophers-3.png|450px|thumb|center]]

 

put down the first and waits a few breaths, then boldly tries in the opposite order.

 

LockMutex(Mutex)

LastElement(Queue())

Delay(Random(2500)+25)

ForEver

 

=={{header|Python}}==

This solution avoids deadlock by never waiting for a fork while having one in hand. If

a philosopher acquires one fork but can't acquire the second, he releases the first fork

before waiting to acquire the other (which then becomes the first fork acquired).

import random

import time

def DiningPhilosophers():

forks = [threading.Lock() for n in range(5)]

 

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

print ("Now we're finishing.")

 

 

=={{header|Racket}}==

 

#lang racket

 

 

(run)

 

=={{header|Raku}}==

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

has $!lock = Lock.new;

method grab($who, $which) {

}

sink await @philosophers;

{{out}}

<pre>Aristotle grabbing left fork

 

Deadlocks are eliminated by the method of acquiring the resources (forks): &nbsp; both forks are (attempted to be) grabbed at the same time (by both hands). &nbsp;

signal on halt /*branches to HALT: (on Ctrl─break).*/

parse arg seed diners /*obtain optional arguments from the CL*/

else if @.p.state=='thinking' then @.p.state=0

end /*p*/ /*[↑] P (person)≡ dining philosophers.*/

{{out|output|text=&nbsp; &nbsp; (some middle and end portions have been elided):

<pre>

 

{{works with|Ruby|1.8.7}}

 

class Philosopher

end

 

=={{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};

 

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.

 

END;

{{in}}

<pre>

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'

#('Aristotle' 'Kant' 'Buddha' 'Marx' 'Russel' )

do: [:aName | Philosopher new beginDining: aName at: diningTable]! !

 

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

 

foreach name {Aristotle Kant Spinoza Marx Russel} {

foreach t $tasks {

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

 

=={{header|VBA}}==

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

dine

show

<pre>Stats Gets Gets Eats Puts Puts Thinks

First Second Spag- First Second About

* 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

End Sub

 

 

Private ReadOnly m_Number As Integer

Public Sub New(ByVal number As Integer)

End Get

End Property

 

Implements IDisposable

 

 

Public MustOverride Sub MainLoop()

 

=== Deadlock ===

 

Inherits PhilosopherBase

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

End Sub

 

 

=== Live Lock ===

Inherits PhilosopherBase

 

End Sub

 

 

=== Working ===

Inherits PhilosopherBase

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

End Sub

 

 

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

sitAndEat(name,seat);

}

The setIf method atomically sets the bool to the first value if it is currently the second value.

.apply(philo.launch);

 

{{out}}

<pre>