Go solution of the Dining philosophers problem
I spent part of the sunday solving the Dining Philosophers using Go. The given solution is based in the description for the problem present in The Little Book of Semaphores:
The Dining Philosophers Problem was proposed by Dijkstra in 1965, when dinosaurs ruled the earth. It appears in a number of variations, but the standard features are a table with five plates, five forks (or chopsticks) and a big bowl of spaghetti.
There are some constraints:
- Only one philosopher can hold a fork at a time
- It must be impossible for a deadlock to occur
- It must be impossible for a philosopher to starve waiting for a fork
- It must be possible for more than one philosopher to eat at the same time
No more talk, here is my solution for the problem:
package main
import (
"fmt"
"sync"
"time"
)
type Fork struct {
sync.Mutex
}
type Table struct {
philosophers chan Philosopher
forks []*Fork
}
func NewTable(forks int) *Table {
t := new(Table)
t.philosophers = make(chan Philosopher, forks - 1)
t.forks = make([]*Fork, forks)
for i := 0; i < forks; i++ {
t.forks[i] = new(Fork)
}
return t
}
func (t *Table) PushPhilosopher(p Philosopher) {
p.table = t
t.philosophers <- p
}
func (t *Table) PopPhilosopher() Philosopher {
p := <-t.philosophers
p.table = nil
return p
}
func (t *Table) RightFork(philosopherIndex int) *Fork {
f := t.forks[philosopherIndex]
return f
}
func (t *Table) LeftFork(philosopherIndex int) *Fork {
f := t.forks[(philosopherIndex + 1) % len(t.forks)]
return f
}
type Philosopher struct {
name string
index int
table *Table
fed chan int
}
func (p Philosopher) Think() {
fmt.Printf("%s is thinking...\n", p.name)
time.Sleep(3e9)
p.table.PushPhilosopher(p)
}
func (p Philosopher) Eat() {
p.GetForks()
fmt.Printf("%s is eating...\n", p.name)
time.Sleep(3e9)
p.PutForks()
p.table.PopPhilosopher()
p.fed <- 1
}
func (p Philosopher) GetForks() {
rightFork := p.table.RightFork(p.index)
rightFork.Lock()
leftFork := p.table.LeftFork(p.index)
leftFork.Lock()
}
func (p Philosopher) PutForks() {
rightFork := p.table.RightFork(p.index)
rightFork.Unlock()
leftFork := p.table.LeftFork(p.index)
leftFork.Unlock()
}
func main() {
table := NewTable(5)
philosophers := []Philosopher{
Philosopher{"Thomas Nagel", 0, table, make(chan int)},
Philosopher{"Elizabeth Anscombe", 1, table, make(chan int)},
Philosopher{"Martin Heidegger", 2, table, make(chan int)},
Philosopher{"Peter Lombard", 3, table, make(chan int)},
Philosopher{"Gottfried Leibniz", 4, table, make(chan int)},
}
for {
for _, p := range philosophers {
go func(p Philosopher){
p.Think()
p.Eat()
}(p)
}
for _, p := range philosophers {
<-p.fed
fmt.Printf("%s was fed.\n", p.name)
}
}
}
import (
"fmt"
"sync"
"time"
)
type Fork struct {
sync.Mutex
}
type Table struct {
philosophers chan Philosopher
forks []*Fork
}
func NewTable(forks int) *Table {
t := new(Table)
t.philosophers = make(chan Philosopher, forks - 1)
t.forks = make([]*Fork, forks)
for i := 0; i < forks; i++ {
t.forks[i] = new(Fork)
}
return t
}
func (t *Table) PushPhilosopher(p Philosopher) {
p.table = t
t.philosophers <- p
}
func (t *Table) PopPhilosopher() Philosopher {
p := <-t.philosophers
p.table = nil
return p
}
func (t *Table) RightFork(philosopherIndex int) *Fork {
f := t.forks[philosopherIndex]
return f
}
func (t *Table) LeftFork(philosopherIndex int) *Fork {
f := t.forks[(philosopherIndex + 1) % len(t.forks)]
return f
}
type Philosopher struct {
name string
index int
table *Table
fed chan int
}
func (p Philosopher) Think() {
fmt.Printf("%s is thinking...\n", p.name)
time.Sleep(3e9)
p.table.PushPhilosopher(p)
}
func (p Philosopher) Eat() {
p.GetForks()
fmt.Printf("%s is eating...\n", p.name)
time.Sleep(3e9)
p.PutForks()
p.table.PopPhilosopher()
p.fed <- 1
}
func (p Philosopher) GetForks() {
rightFork := p.table.RightFork(p.index)
rightFork.Lock()
leftFork := p.table.LeftFork(p.index)
leftFork.Lock()
}
func (p Philosopher) PutForks() {
rightFork := p.table.RightFork(p.index)
rightFork.Unlock()
leftFork := p.table.LeftFork(p.index)
leftFork.Unlock()
}
func main() {
table := NewTable(5)
philosophers := []Philosopher{
Philosopher{"Thomas Nagel", 0, table, make(chan int)},
Philosopher{"Elizabeth Anscombe", 1, table, make(chan int)},
Philosopher{"Martin Heidegger", 2, table, make(chan int)},
Philosopher{"Peter Lombard", 3, table, make(chan int)},
Philosopher{"Gottfried Leibniz", 4, table, make(chan int)},
}
for {
for _, p := range philosophers {
go func(p Philosopher){
p.Think()
p.Eat()
}(p)
}
for _, p := range philosophers {
<-p.fed
fmt.Printf("%s was fed.\n", p.name)
}
}
}
Any feedback is very welcome :)
One issue is whether or not you’re guaranteed to prevent deadlock from occurring. What if all philosophers grab their right forks? They will all wait forever for their left forks, no? I examined The Little Book of Semaphores and the author raises this issue as “Deadlock #5″.
A suggestion is to consider a solution more in keeping with Go, perhaps avoiding the mutexes altogether. The built in construct for coordination is the channel. Can you think of a way to implement it without mutexes but by using channels to coordinate the forks?
You inspired me, so I wrote such a solution for myself. I’ll try to remember to check back in a week or so and perhaps post it.
Hey there, thanks for your comment!
Actually, the table object has a developers unbuffered channel of size forks – 1, so the deadlock is not possible, because when there are 5 forks, there will be only 4 forks, and if all philosophers pick up the right fork, the table still have a fork available.
But I liked your challenge, thank you! However, I can’t implement it next days, because I’m going to make a five-days trip. When I’m back, I’ll try to not limit 4 philosophers on the table and not use mutexes.