The Dining Philosophers (A Philosophers’ Dinner) problem is one of the classic problems commonly used to describe problems in concurrent processing, common problems in resource allocation without deadlock. (deadlock) and resource starvation (starvation).
1. Describe the problem
The problem is stated as follows: Have 5 philosophers sit around a round table, in front of them are plates of spaghetti, one plate each. There are 5 plates placed alternately between two philosophers sitting next to each other, depicted in the picture 
Every philosopher has two states: Eating and Thinking. When a philosopher doesn’t eat, they sit and think. When the philosopher feels hungry, he can only eat if the two plates next to him (left and right) are placed on the table. A philosopher can take only 1 plate. Note that he cannot take the plate if it is being used by another philosopher. After a philosopher has finished eating, he will put the two plates he has just used on the table and continue to think so that other philosophers can take his plate and start eating. The requirement of the problem is that every philosopher can eat or be exchanged (think and eat) without starving.
2. Implement problems with Golang
First, I will declare struct Fork , which includes 2 variables, id and channel l used to ensure that if the plate is picked up, no one else will be able to hold it until it is placed on the table.
1 2 3 4 5 | type Fork struct { id int l chan bool } |
Next is the struct Philosopher , which includes the variables id and leftFork , rightFork
1 2 3 4 5 | type Philosopher struct { id int leftFork, rightFork *Fork // 2 chiếc dĩa bên cạnh } |
To describe the process of eating philosophers, struct Philosopher will include 3 main methods: pickForks() , putDownForks() and dine()
1 2 3 4 5 6 7 8 | func (p *Philosopher) pickForks() { <-p.leftFork.l // lấy chiếc đũa bên trái khỏi channel fmt.Println(p.id, " picked left fork ", p.leftFork.id) time.Sleep(time.Second) <-p.rightFork.l // lấy chiếc đũa bên phải khỏi channel fmt.Println(p.id, " picked right fork ", p.rightFork.id) } |
1 2 3 4 5 6 7 | func (p *Philosopher) putDownForks() { p.leftFork.l <- true // chiếc đũa bên trái về trạng thái ready trong channel fmt.Println(p.id, " put down left fork ", p.rightFork.id) p.rightFork.l <- true // chiếc đũa bên phải về trạng thái ready trong channel fmt.Println(p.id, " put down right fork ", p.leftFork.id) } |
1 2 3 4 | func (p *Philosopher) dine() { //TODO } |
In the main() function, I will initialize 5 Philosophers with 5 Forks. However, for this experiment I will not feed Philosophers indefinitely and each person will only be able to eat up to 3 times.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | const ( HUNGER = 3 COUNT = 5 ) var ( wg sync.WaitGroup forks [COUNT]*Fork ) func main() { wg.Add(COUNT) for i := 0; i < COUNT; i++ { // khởi tạo forks forks[i] = &Fork{id: i, l: make(chan bool, 1)} forks[i].l <- true } philosophers := make([]*Philosopher, COUNT) for i := 0; i < COUNT; i++ { philosophers[i] = &Philosopher{ id: i, leftFork: forks[i], rightFork: forks[(i+1)%COUNT]} go philosophers[i].dine() // bắt đầu bữa tối } wg.Wait() // chờ philosophers hoàn thành bữa tối fmt.Println("Table is empty") } |
Therefore, the method dine() will be implemented as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | func (p *Philosopher) dine() { for i := 0; i < HUNGER; i++ { say("Thinking", p.id) doingStuff() say("Hungry", p.id) p.pickForks() say("Eating", p.id) doingStuff() p.putDownForks() } say("Satisfied", p.id) wg.Done() // hoàn thành bữa tối say("Leaving the table", p.id) } func doingStuff() { time.Sleep(time.Second / 10) } func say(action string, id int) { fmt.Printf("#%d is %sn", id, action) } |
After running the program, the output will output as below:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | #4 is Thinking #1 is Thinking #0 is Thinking ... #2 is Hungry 2 picked left fork 2 2 picked right fork 3 #2 is Eating #4 is Hungry 4 picked left fork 4 4 picked right fork 0 #4 is Eating ... 0 put down left fork 0 0 is Satisfied 0 is Leaving the table Table is empty |
Great! At first glance, the program ran successfully with no errors. (It means that no philosopher seems to have been starved).
But wait, what if all 5 philosophers each get 1 wand? That will result in all 5 of you waiting to get the remaining chopsticks but will never get them (Deadlock) !! 
Proceed to fix a bit of the pickForks() function:
1 2 3 4 5 6 7 8 | func (p *Philosopher) pickForks() { <-p.leftFork.l fmt.Println(p.id, " picked left fork ", p.leftFork.id) time.Sleep(time.Second) // lấy 1 chiếc đũa rồi bắt đầu sleep <-p.rightFork.l fmt.Println(p.id, " picked right fork ", p.rightFork.id) } |
Rerun the program, we will have the following result:
1 2 3 4 5 6 7 8 9 10 11 12 13 | #4 is thinking #1 is thinking ... #4 is hungry #1 is hungry ... 2 picked left fork 2 4 picked left fork 4 3 picked left fork 3 0 picked left fork 0 1 picked left fork 1 fatal error: all goroutines are asleep - deadlock! |
The result is as expected when each person takes a chopstick together, a deadlock will inevitably happen.
3. Solution for the problem
So how to solve the optimal solution to avoid deadlock for the problem? Recalling a little about deadlock, deadlock will happen only when the following 4 conditions occur:
- Mutual Exclusion : At a time, resources are not systematically allocated to a single process. Another process cannot be used until the resource is released.
- Hold and Wait : Each process in the process set is holding a resource and waiting to be allocated a new resource.
- No Preemption : A process cannot take over a resource until it is released by the process using it.
- Circular wait : Processes hold one resource and wait for another by another. They follow each other to form a circle. Waiting endlessly.
The first way to solve the problem to avoid deadlock is to eliminate the Circular Wait.
3.1. Resource decentralized solution
This solution was given by Dijstra himself, who first described the problem. Each plate will be numbered 1 – 5, and each philosopher will always give priority to the plate with the smallest number of the two to be won (philosopher 1 takes the plate 1, philosopher 2 takes the plate 2, …). So after the 4 philosophers have taken his plate, philosopher 5 will not be able to take any plate (because the smallest plate next to him has been taken). Thanks to that, the # 4 philosopher was able to take the 5th plate and start eating. Note that this solution does not matter the order in which the plate is placed. 
Proceed to modify a little function pickForks()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | func (p *Philosopher) pickForks() { if p.leftFork.id < p.rightFork.id { <-p.leftFork.l fmt.Println(p.id, " picked left fork ", p.leftFork.id) time.Sleep(time.Second) <-p.rightFork.l fmt.Println(p.id, " picked right fork ", p.rightFork.id) } else { <-p.leftFork.l fmt.Println(p.id, " picked left fork ", p.leftFork.id) time.Sleep(time.Second) <-p.rightFork.l fmt.Println(p.id, " picked right fork ", p.rightFork.id) } } |
Rerun the program, now deadlock is removed:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #4 is Thinking ... #4 is Hungry 4 picked right fork 0 ... 1 picked left fork 1 ... 2 picked left fork 2 ... 3 picked left fork 3 4 picked left fork 4 #4 is Eating ... 0 is Satisfied 0 is Leaving the table Table is empty |
Another solution to decentralizing resources is to ask the philosopher in an even position to give priority to the wand on the left, the philosopher in the odd position to give priority to the right wand increment 2 prioritizes plate 3, …) ⇒ Since then plate 2 and plate 4 will have a lower priority among the philosophers, so that philosophers with a plate in hand can take them without having to dispute .
3.2. Solution using Monitor
In order to minimize the right to dispute the plate, philosophers decide that, every time a philosopher has chopsticks, it will be a pair instead of one. This will reduce Preemption as well as Circular Wait. We will proceed to add 1 Conditional Variable ForkCond variable
1 2 | var ForkCond *sync.Cond |
The ForkCond variable is used as a monitor, ensuring that a philosopher always favors taking the left plate.
- If the left plate is placed on the table, the philosopher will pick up the plate and try to get the one on the right. The mutex variable in
ForkCondused to ensure that, once a philosopher has picked up the left plate, the one on the right will be given priority to him without being picked up by anyone else. - If the left plate is placed on the table, the philosopher will pick up the plate and try to get the one on the right. The mutex variable in
ForkCondused to ensure that, once a philosopher has picked up the left plate, the one on the right will be given priority to him without being picked up by anyone else.
Proceed to modify the pickForks() function:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | func (p *Philosopher) pickForks() { ForkCond.L.Lock() // lock mutex for { select { case <-p.leftFork.l: fmt.Println(p.id, " picked left fork ", p.leftFork.id) <-p.rightFork.l fmt.Println(p.id, " picked right fork ", p.rightFork.id) ForkCond.L.Unlock() // unlock mutex return default: ForkCond.Wait() //wait cho tới khi được signaled } } } |
Then, the putDownForks() function will signal when a philosopher has finished eating and put the plate on the table:
1 2 3 4 5 | func (p *Philosopher) putDownForks() { ... ForkCond.Signal() } |
Looking at the output of the program, the 2nd philosopher after taking the left plate number 2 will have priority to take the plate on the right number 3 without being taken away by anyone else, minimizing the problem of resource possession.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | ... 3 picked left fork 3 3 picked right fork 4 ... #2 is Hungry 2 picked left fork 2 3 put down left fork 4 3 put down right fork 3 #3 is Thinking 2 picked right fork 3 ... #1 is Satisfied #1 is Leaving the table Table is empty |
4. Conclusion
There are many solutions to the Dining Philosophers problem, but for the limitation this article only introduces the two most basic solutions. Hopefully, after reading your article, you understand how Concurrency works in Golang as well as how to solve it if you have a problem with a deadlock. Thank you for reading my article and looking forward to the next part!
Reference source
https://en.wikipedia.org/wiki/Dining_philosophers_problem
https://www.golangprograms.com/illustration-of-the-dining-philosophers-problem-in-golang.html