Go Concurrency through Examples (Part 1): Dining Philosophers

Tram Ho

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.

Next is the struct Philosopher , which includes the variables id and leftFork , rightFork

To describe the process of eating philosophers, struct Philosopher will include 3 main methods: pickForks() , putDownForks() and dine()

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.

Therefore, the method dine() will be implemented as follows:

After running the program, the output will output as below:

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:

Rerun the program, we will have the following result:

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

Rerun the program, now deadlock is removed:

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

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 ForkCond used 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 ForkCond used 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:

Then, the putDownForks() function will signal when a philosopher has finished eating and put the plate on the table:

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.

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




Share the news now

Source : Viblo