The dining philosophers is a concurrent algorithm design problem originally presented by Edsger Djikstra to his students to clarify the notions of deadlock and starvation freedom. Tony Hoare redefined the problem in Communicating Sequential Processes, which is the basis for concurrency in Golang.

If you’re unfamiliar, the problem goes something like this:

In ancient times, a wealthy philanthropist endowed a College to accommodate five eminent philosophers. Each philosopher had a room in which he could engage in his professional activity of thinking; there was also a common dining room, furnished with a circular table, surrounded by five chairs, each labelled by the name of the philosopher who was to sit in it. The names of the philosophers were PHIL0, PHIL1, PHIL2, PHIL3, PHIL4, and they were disposed in this order clockwise around the table. To the left of each philosopher there was laid a golden fork, and in the centre stood a large bowl of spaghetti, which was constantly replenished. A philosopher was expected to spend most of his time thinking; but when he felt hungry, he went to the dining room, sat down in his own chair, picked up his own fork on his left, and plunged it into the spaghetti. But such is the tangled nature of spaghetti that a second fork is required to carry it to the mouth. The philosopher therefore had also to pick up the fork on his right. When he was finished he would put down both his forks, get up from his chair, and continue thinking. Of course, a fork can be used by only one philosopher at a time. If the other philosopher wants it, he just has to wait until the fork is available again.

Each philosopher represents a thread running some arbitrary computations. Meanwhile, each fork represents a shared resource that all threads will need to complete their computation. Only one thread can access a resource at one time, so our problem occurs when all resources try to access the same resources at once. The solution to the problem should be starvation and deadlock free.

Starvation freedom means that any philosopher wanting to enter the dining hall to eat will do so successfully.

Deadlock freedom means that two philosophers attempting to grab the same fork will be resolved when the higher priority one succeeds.

The solution to the problem has often relied on synchronization mechanisms like mutexes or semaphores, which many Golang examples use. There's nothing wrong with these approaches and they are correct programs. When Tony Hoare created Communicating Sequential Processes, he introduced synchornous communication via a new primitive. Originating from Hoare’s CSP, a channel is the data type provided by Golang to effectively communicate between any two goroutines.

Channels can be buffered or unbuffered. If unbuffered, a channel is used for synchronized communication, meaning all sends and receives are blocking actions. If we send a value over the channel, there should be a receiver waiting to receive the sent value.

Given an integer typed channel called c, the following operation causes deadlock as a value is sent without a receiver:

						c <- 1
					

Similarly, the following causes deadlock as the receiver waits indefinitely for a value:

						<-c
					

The correct program would read:

A buffered channel acts similarly to a semaphore and can be used to limit throughput. With a buffered channel you can specify a number of objects to hold in the channel regardless of if a receiver is ready. This removes the blocking nature of sends, so long as you don’t exceed the max number of the buffer, while maintaining waiting for receivers. Buffered channels are perfect for holding a predetermined finite number of shared resources.

An example:

There are many more things to understand about channels but I won't cover them here.For a comprehensive overview of channels, read this guide.

Using what was discussed above, we can setup buffered channels to hold our resources. First we'll define the fork and philosopher structs:

The fork is simply a channel with a type of an empty struct, which is the go way of saying we don't care whats in this channel. The philosopher only contains a reference to the fork on his left and right.

After setting up the structs of our philosopher and fork, we can create two buffered channels and prefill them with our shared resources:

In the above, we create a channel called diners which contains a buffer of five philosophers. We then create an array of forks, which are buffered with a size of one. The purpose of buffering the fork with a size of one is to limit only one fork per channel. This means that the first philosopher that receives from the channel gets the fork and the next philosopher to receive will block until the previous philosopher sends the fork back over the channel. A new *rand.Rand object is created to simulate some random duration for the philosophers to "think". We then send forks and philosophers to their buffers to hold until our program begins processing.

Now that we have our data structures ready, we should create a method allowing the philosopher to eat:

This method is fairly straight forward. The philosopher immediately tries to pick up their left fork then right fork. Once both forks are received, they spend a fixed duration eating and put their forks down by sending them back to their respective buffered channels. Once they're down the philosopher goes back to thinking for a random duration and then sends the philosopher back to the diner channel.

One last piece will bring this all together

A nice thing about channels is that they can be ranged over. When ranging over a channel two values are returned, the read value and a boolean signaling if the channel was closed or not. We only care about the value here, which contains our philosopher who is next in line to start eating. Once received, we create a new goroutine where the philosopher can eat.

See the full code, here