Ever since starting the series, I’ve been looking forward to this particular post. The Wikipedia entry describes the problem as follows:
Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.
Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when he has both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After he finishes eating, he needs to put down both forks so they become available to others. A philosopher can take the fork on his right or the one on his left as they become available, but cannot start eating before getting both of them.
The Little Book of Semaphores provides a less colloquial description, but spells out the restrictions:
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.
Probably acknowledging the fact that this is more an academic problem than a description of a “real-world” scenario, Russ Cox said, in jest, that the way to solve this problem in Go is to “buy more forks.” Why? You need to ask yourself what this problem is trying to model: the philosophers are threads and the forks are resources. To move forward, the threads need two particular resources, shared with other threads. It’s not just that there’s a pool of resources somewhere and each thread needs to grab any two of those, but instead each thread needs to grab two specific resources to be able to work, and each resource is shared among exactly two threads.
The reason why this problem is interesting is because the naive solution quickly leads to a deadlock: each philosopher grabs the left fork and then grabs the right fork. The problem with this approach is that if every philosopher grabs the left fork, there are no forks left to grab on the right. And this the relevance of the problem: the naive solution is so tempting that it’s commonly found in “real world” code, maybe not in this exact form, but usually with the same misguided approach.
The naive implementation is something like this:
type Philosopher struct {
Name string
l *sync.Mutex
r *sync.Mutex
}
func (p Philosopher) eat() {
p.l.Lock()
p.r.Lock()
log.Printf("Philosopher %s eating", p.Name)
time.Sleep(10 * time.Millisecond)
p.r.Unlock()
p.l.Unlock()
}A slight modification in Philosopher.eat() causes the deadlock to
happen immediately:
func (p Philosopher) eat() {
p.l.Lock()
runtime.Gosched()
p.r.Lock()
log.Printf("Philosopher %s eating", p.Name)
time.Sleep(10 * time.Millisecond)
p.r.Unlock()
p.l.Unlock()
}To avoid any confusion, the call to runtime.Gosched() is not
necessary to cause the deadlock, it just causes it to happen more
quickly.
Traditionally, this problem is solved by limiting the philosophers that can try to eat at the same time. The deadlock happens because all five try to grab a fork simultaneously. If you limit this to four, then there’s always a free fork and the deadlock does not happen.
Another solution is to have “left-handed” and “right-handed” philosophers: the former picks the left fork first and the later the right fork first. This solves the problem because a left-handed philosopher sitting next to a right-handed one will cause one of them to get the fork and the other will have to wait.
Yet another solution is to grab two forks at once instead of just one. In other words, instead of each philosopher having exactly two forks that they can grab out of the total five, they can grab any two. This leads to starvation because a thread can keep grabbing the two forks over and over again, and another thread might never get the chance to do so.
Of these solutions, I like the asymmetric one, because it’s simple to understand and simple to implement.
In Go, we can start by having a Philosopher:
type Philosopher struct {
Name string
l ForkChannels
r ForkChannels
}ForkChannels is a structure holding two channels: one to pick the fork
up from the table and one to return it.
A Philosopher basically is an eating and thinking machine:
func (p Philosopher) run() {
for {
p.think()
p.eat()
}
}Thinking is easy:
func (p Philosopher) think() {
log.Printf("Philosopher %s thinking", p.Name)
time.Sleep(10 * time.Millisecond)
}and eating is simply a matter of picking up the forks, eating and returning them:
func (p Philosopher) eat() {
<-p.l.pickCh
<-p.r.pickCh
log.Printf("Philosopher %s eating", p.Name)
time.Sleep(10 * time.Millisecond)
p.l.returnCh <- Fork{}
p.r.returnCh <- Fork{}
}I know I said I like the asymmetric solution, but this code doesn’t seem to be doing that, as there’s a single Philosopher and there isn’t knowledge of a position on the table. It’s because I introduce the asymmetry elsewhere.
All that is missing is some set up for this whole situation:
func main() {
const N = 5
ch := make([]ForkChannels, N)
for i := 0; i < N; i++ {
ch[i].pickCh = make(chan Fork)
ch[i].returnCh = make(chan Fork)
go func(f ForkChannels) {
for {
f.pickCh <- Fork{}
<-f.returnCh
}
}(ch[i])
}
for i := 0; i < N; i++ {
l, r := i, (i+1)%N
if i%2 == 0 {
l, r = r, l
}
p := &Philosopher{
Name: fmt.Sprintf("%d", i),
l: ch[l],
r: ch[r],
}
go p.run()
}
time.Sleep(1 * time.Second)
}First, there’s a goroutine handling the forks: it sends one fork over the channel and waits for it to come back. Note that it needs two channels because two Philosophers are getting and returning forks. If one of them is returning a fork and the other one is picking it up, it might happen that instead of the handling goroutine getting it, the Philosophers might simply exchange forks among them. This is fine in principle, except that the two Philosophers should be able to think at the same time, instead of waiting for the other one to pick up the fork.
Second, there’s a goroutine for each Philosopher, and the Philosopher is set up in a way that the channels are swapped. Instead of having handedness in the Philosophers, this is implemented by reversing the channels. When the channels are swapped, a Philosophers picking from what it considers its left channel is actually using the right one, effectively swapping the order in which they pick up the forks.
The full code for the solution is here.
The other way to implement this would have been to have a “Table” that
hands out forks. The table needs to be able to service all the
Philosophers at the same time. It can be done using runtime.Select, so
that some channels are sending and some are receiving, and the number of
channels is not hardcoded.
Next week: the cigarette smokers problem.