Golang implementation of dining philosophers variant

Question

I would like to implement a variant of the classical dining philosophers problem which has the definition as:

Implement the dining philosopher’s problem with the following constraints/modifications.

• There should be 5 philosophers sharing chopsticks, with one chopstick between each adjacent pair of philosophers.
• Each philosopher should eat only 3 times (not in an infinite loop as we did in lecture)
• The philosophers pick up the chopsticks in any order, not lowest-numbered first (which we did in lecture).
• In order to eat, a philosopher must get permission from a host which executes in its own goroutine.
• The host allows no more than 2 philosophers to eat concurrently.
• Each philosopher is numbered, 1 through 5.
• When a philosopher starts eating (after it has obtained necessary locks) it prints "starting to eat " on a line by itself, where is the number of the philosopher.
• When a philosopher finishes eating (before it has released its locks) it prints "finishing eating " on a line by itself, where is the number of the philosopher.

I implemented the following code:

package main
import (
 "fmt"
 "sync"
 "time"
)
// define variables
var numPhilo int = 5
var numCS int = 5
var eatTimes int = 3
var numEatingPhilo int = 2
type Host struct {
 // channel for allowed philosopher for eating
 eatingChannel chan *Philo
 // channel for submitting request to host
 requestChannel chan *Philo
 // channel for terminate signal for the daemon
 quitChannel chan int
 // bookkeeping of the current eating philosophers
 eatingPhilos map[int]bool
 // mutex to lock the modification of the eatingPhilos variable
 mu sync.Mutex
}
// daemon function to manage the allowed philosophers
func (pHost *Host) manage() {
 // daemon serving in the backend and only exits for terminate signal
 for {
 select {
 // handle submitted request
 case pPhilo := <-pHost.requestChannel:
 fmt.Printf("%d submitted request\n", pPhilo.idx)
 select {
 // channel is not full
 case pHost.eatingChannel <- pPhilo:
 pHost.eatingPhilos[pPhilo.idx] = true
 // channel is full
 default:
 finished := <-pHost.eatingChannel
 pHost.eatingChannel <- pPhilo
 currEating := make([]int, 0, numPhilo)
 // update bookkeeping table
 for tmpIdx, eating := range pHost.eatingPhilos {
 if eating {
 currEating = append(currEating, tmpIdx)
 }
 }
 fmt.Printf("%v have been eating, clearing up %d for %d\n", currEating, finished.idx, pPhilo.idx)
 pHost.eatingPhilos[finished.idx] = false
 pHost.eatingPhilos[pPhilo.idx] = true
 }
 case <-pHost.quitChannel:
 fmt.Println("stop hosting")
 return
 }
 }
}
type ChopS struct {
 mu sync.Mutex
}
type Philo struct {
 // index of the philosopher
 idx int
 // number of times the philosopher has eaten
 numEat int
 leftCS, rightCS *ChopS
 host *Host
}
func (pPhilo *Philo) eat(wg *sync.WaitGroup) {
 for pPhilo.numEat < eatTimes {
 // once the philosopher intends to eat, lock the corresponding chopsticks
 pPhilo.leftCS.mu.Lock()
 pPhilo.rightCS.mu.Lock()
 // reserve a slot in the channel for eating
 // if channel buffer is full, this is blocked until channel space is released
 pPhilo.host.requestChannel <- pPhilo
 pPhilo.numEat++
 fmt.Printf("starting to eat %d for %d time\n", pPhilo.idx, pPhilo.numEat)
 time.Sleep(time.Millisecond)
 fmt.Printf("finishing eating %d for %d time\n", pPhilo.idx, pPhilo.numEat)
 pPhilo.rightCS.mu.Unlock()
 pPhilo.leftCS.mu.Unlock()
 wg.Done()
 }
}
func main() {
 var wg sync.WaitGroup
 host := Host{
 eatingChannel: make(chan *Philo, numEatingPhilo),
 requestChannel: make(chan *Philo),
 quitChannel: make(chan int),
 eatingPhilos: make(map[int]bool),
 }
 CSticks := make([]*ChopS, numCS)
 for i := 0; i < numCS; i++ {
 CSticks[i] = new(ChopS)
 }
 philos := make([]*Philo, numPhilo)
 for i := 0; i < numPhilo; i++ {
 philos[i] = &Philo{idx: i + 1, numEat: 0, leftCS: CSticks[i], rightCS: CSticks[(i+1)%5], host: &host}
 }
 go host.manage()
 wg.Add(numPhilo * eatTimes)
 for i := 0; i < numPhilo; i++ {
 go philos[i].eat(&wg)
 }
 wg.Wait()
 host.quitChannel <- 1
}

However, I noticed that the program is actually failing in some cases, i.e.

starting to eat 1 for 1 time
1 submitted request
3 submitted request
starting to eat 3 for 1 time
finishing eating 3 for 1 time
starting to eat 3 for 2 time
finishing eating 1 for 1 time
3 submitted request
[1 3] have been eating, clearing up 1 for 3
1 submitted request
[3] have been eating, clearing up 3 for 1
starting to eat 1 for 2 time
finishing eating 3 for 2 time
finishing eating 1 for 2 time
starting to eat 5 for 1 time
5 submitted request
[1] have been eating, clearing up 3 for 5
finishing eating 5 for 1 time
starting to eat 5 for 2 time
5 submitted request
[5 1] have been eating, clearing up 1 for 5
finishing eating 5 for 2 time
starting to eat 4 for 1 time
4 submitted request
[5] have been eating, clearing up 5 for 4
finishing eating 4 for 1 time
starting to eat 4 for 2 time
4 submitted request
[4] have been eating, clearing up 5 for 4
finishing eating 4 for 2 time
starting to eat 3 for 3 time
3 submitted request
[4] have been eating, clearing up 4 for 3
finishing eating 3 for 3 time
starting to eat 2 for 1 time
2 submitted request
[3] have been eating, clearing up 4 for 2
finishing eating 2 for 1 time
starting to eat 2 for 2 time
2 submitted request
[3 2] have been eating, clearing up 3 for 2
finishing eating 2 for 2 time
starting to eat 1 for 3 time
1 submitted request
[2] have been eating, clearing up 2 for 1
finishing eating 1 for 3 time
starting to eat 2 for 3 time
2 submitted request
[1] have been eating, clearing up 2 for 2
5 submitted request
[2 1] have been eating, clearing up 1 for 5
starting to eat 5 for 3 time
finishing eating 2 for 3 time
finishing eating 5 for 3 time
starting to eat 4 for 3 time
4 submitted request
[5 2] have been eating, clearing up 2 for 4
finishing eating 4 for 3 time
stop hosting

where it seems sometimes two instances of the same philosopher are eating concurrently, while semaphore is locked on the chopstick level, i.e.

...
[3] have been eating, clearing up 3 for 1
...
[5] have been eating, clearing up 5 for 4
...

Also according to the logs, the bookkeeping map is acting weird, when the records are misaligned with the actual finished philosopher, i.e.

...
[4] have been eating, clearing up 5 for 4
...
[3] have been eating, clearing up 4 for 2
...

I checked the program with go build -race for race conditions detection, but it seems to be fine. Also not to mention there is only one goroutine running manage() and reading/writing to the map eatingPhilos.

Could someone please point out which part of the implementation is improper? Anything obviously wrong or bad practice?

Answer 1

To help resolve your issue lets add code to report when a philosopher has locked a chopstick and what they are waiting on (I also added an idx to ChopS to simplify this):

pPhilo.leftCS.mu.Lock()
fmt.Printf("pPhilo %d has lock on chopstick %d, waiting on %d\n", pPhilo.idx, pPhilo.leftCS.idx, pPhilo.rightCS.idx)
pPhilo.rightCS.mu.Lock()

Running this on my computer immediately generates a deadlock:

pPhilo 2 has lock on chopstick 1, waiting on 2
pPhilo 5 has lock on chopstick 4, waiting on 0
pPhilo 1 has lock on chopstick 0, waiting on 1
pPhilo 3 has lock on chopstick 2, waiting on 3
pPhilo 4 has lock on chopstick 3, waiting on 4
fatal error: all goroutines are asleep - deadlock!

Adding the Printf enables us to see what is happening but can also change the order of operation (it adds a delay which other goroutines may get some runtime). If adding a Printf leads to an issue like this it is likely there is an issue with your underlying algorithm. If you look at the output you will see that every philosopher has locked their left chopstick and is waiting on the right one (but another philosopher has that). This issue can occur whether or not the Printf is there (but having the Printf makes the situation more obvious!).

You can resolve this by doing something like:

// once the philosopher intends to eat, lock the corresponding chopsticks
for {
 pPhilo.leftCS.mu.Lock()
 // Attempt to get the right Chopstick - if someone else has it we replace the left chopstick and try
 // again (in order to avoid deadlocks)
 if pPhilo.rightCS.mu.TryLock() { // TryLock introduced in go 1.18
 break
 }
 pPhilo.leftCS.mu.Unlock()
}

There are other ways of resolving this but I felt that the above is fairly easy to understand. Do note the warning in the docs "Note that while correct uses of TryLock do exist, they are rare, and use of TryLock is often a sign of a deeper problem in a particular use of mutexes.".

The issue above is one of the points of the problem; as wikipedia says:

And may end up holding a left fork thinking, staring at the right side of the plate, unable to eat because there is no right fork, until they starve.

I have implemented a work around this (the philosopher puts the left fork back down) but that is not something that the rules allow. A better option might be for the philosopher to starve (perhaps ending the simulation - I've left that to you!).

the bookkeeping map is acting weird

3 submitted request
[1 3] have been eating, clearing up 1 for 3
1 submitted request

I think the issue here is that you are not expecting a philosopher who is currently eating to submit another request to eat. However there is nothing to prevent this because the philosopher does not wait for the host to inform it that it should stop eating before joining the queue again. This means that you can end up with the same philosopher eating simultaneously (this may be a metaphysical issue; consult a philosopher if in doubt).

This has an impact on your output because you end up calling eatingPhilos[greedyPhilosopherIdx] = false twice (so the second call has no impact and in your list you will ignore the philosopher).

Anyway that deals with the issue you raised but this is code review (and I suggested you moving your question here as you asked "Anything obviously wrong or bad practice?") so here are a few thoughts.

WaitGroup

You use wg.Add(numPhilo * eatTimes) and then call wg.Done for each iteration. Change this to wg.Add(numPhilo) and move the wg.Done() to the top of eat as defer wg.Done() (fewer calls and easier to understand). See my example below for another approach (I prefer to wg.Wait in the same place as the Waitgroup is created where possible because I feel it's easier to read/understand).

As this is only accessed within manage it should be declared within the function and not in the struct (leaving it in the struct makes it accessible which would lead to races).

eatingChannel & eatingPhilos Map

Same comment as above; you can simplify things by just declaring these in manage. In fact because eatingChannel is only accessed in (pHost *Host) manage() you don't really need to use a channel for this at all (channels are really only needed for communication between goroutines).

Alternative

I could provide further commentary but the big issue is addressing the need to prevent the same, greedy, philosopher from making additional request to eat before the host has changed their status. Doing this is a little tricky because it requires bi-directional communications between two goroutines. I've had a think about this and suggest something like the below (I've left properly dealing with a starving philosopher to you!). Hopefully the below provides some ideas and shows a few techniques you have not seen previously (Note: I have not really tested this and am sure it will have bugs!).

Playground

package main
import (
 "fmt"
 "math/rand"
 "sync"
 "time"
 "golang.org/x/exp/slices"
)
const (
 numPhilo = 5
 eatTimes = 3
 numEatingPhilo = 2
)
type eatRequest struct {
 who int // Who is making the request
 finishedFnChan chan func() // When approves a response will be sent on this channel with a function to call when done
}
// simulateHost - the host must provide permission before a philosopher can eat
// Exits when channel closed
func simulateHost(requestChannel <-chan eatRequest) {
 awaitRequest := requestChannel
 finishedChan := make(chan struct {
 who int
 done chan struct{}
 })
 var whoEating []int // tracks who is currently eating
 for {
 select {
 case request, ok := <-awaitRequest:
 if !ok {
 return // Closed channel means that we are done (finishedChan is guaranteed to be empty)
 }
 // Sanity check - confirm that philosopher is not being greedy! (should never happen)
 if slices.Index(whoEating, request.who) != -1 {
 panic("Multiple requests from same philosopher")
 }
 whoEating = append(whoEating, request.who) // New request always goes at the end
 fmt.Printf("%d started eating (currently eating %v)\n", request.who, whoEating)
 // Let philosopher know and provide means for them to tell us when done
 request.finishedFnChan <- func() {
 d := make(chan struct{})
 finishedChan <- struct {
 who int
 done chan struct{}
 }{who: request.who, done: d}
 <-d // Wait until request has been processed (ensure we should never have two active requests from one philosopher)
 }
 case fin := <-finishedChan:
 idx := slices.Index(whoEating, fin.who)
 if idx == -1 {
 panic("philosopher stopped eating multiple times!")
 }
 whoEating = append(whoEating[:idx], whoEating[idx+1:]...) // delete the element
 fmt.Printf("%d completed eating (currently eating %v)\n", fin.who, whoEating)
 close(fin.done)
 }
 // There has been a change in the number of philosopher's eating
 if len(whoEating) < numEatingPhilo {
 awaitRequest = requestChannel
 } else {
 awaitRequest = nil // Ignore new eat requests until a philosopher finishes (nil channel will never be selected)
 }
 }
}
// ChopS represents a single chopstick
type ChopS struct {
 mu sync.Mutex
 idx int // Including the index can make debugging simpler
}
// philosopher simulates a Philosopher (brain in a vat!)
func philosopher(philNum int, leftCS, rightCS *ChopS, requestToEat chan<- eatRequest) {
 for numEat := 0; numEat < eatTimes; numEat++ {
 // once the philosopher intends to eat, lock the corresponding chopsticks
 for {
 leftCS.mu.Lock()
 // Attempt to get the right Chopstick - if someone else has it we replace the left chopstick and try
 // again (in order to avoid deadlocks)
 if rightCS.mu.TryLock() {
 break
 }
 leftCS.mu.Unlock()
 }
 // We have the chopsticks but need the hosts permission
 ffc := make(chan func()) // when accepted we will receive a function to call when done eating
 requestToEat <- eatRequest{
 who: philNum,
 finishedFnChan: ffc,
 }
 doneEating := <-ffc
 fmt.Printf("philosopher %d starting to eat (%d feed)\n", philNum, numEat)
 time.Sleep(time.Millisecond * time.Duration(rand.Intn(200))) // Eating takes a random amount of time
 fmt.Printf("philosopher %d finished eating (%d feed)\n", philNum, numEat)
 rightCS.mu.Unlock()
 leftCS.mu.Unlock()
 doneEating() // Tell host that we have finished eating
 }
 fmt.Printf("philosopher %d is full\n", philNum)
}
func main() {
 CSticks := make([]*ChopS, numPhilo)
 for i := 0; i < numPhilo; i++ {
 CSticks[i] = &ChopS{idx: i}
 }
 requestChannel := make(chan eatRequest)
 var wg sync.WaitGroup
 wg.Add(numPhilo)
 for i := 0; i < numPhilo; i++ {
 go func(philNo int) {
 philosopher(philNo, CSticks[philNo-1], CSticks[philNo%numPhilo], requestChannel)
 wg.Done()
 }(i + 1)
 }
 go func() {
 wg.Wait()
 close(requestChannel)
 }()
 simulateHost(requestChannel)
}

• Vincent Wen: In terms of resolving the starving philosophers deadlock, as I checked on the same wiki page, and also as suggested by the statement of this problem, it seems the resolution is actually introducing an arbitrator (host/waiter) itself, for which I suppose the process is that, in the philosopher's perspective, the permission shall be first granted by the host before locking the two forks. I will experiment myself to find a way to achieve this based on your approach and post the answer if I manage.
• Vincent Wen: Hi Brits, thank you again for your thorough answer! Indeed I have learned more design patterns and go use cases in your example than in the Coursera course that led me here. I have quite some developing experience in Python but new to Go and essentially to concurrent programming. Would you have any recommendation for reading material in terms of concurrent programming in Go and common design patterns?
• Brits: Thanks. There are a number of ways of resolving the deadlock; what is valid really depends upon the rules (the approach shown here, cooperation between resource requesters, being one of many options). Go developers are generally not as focused on "patterns" as, say, Java developers; I think this is a good thing because blindly following patterns can lead unnecessary complexity. I would recommend The Go Programming Language which introduces a number of patterns (and explains the "why" well); other than that read existing code and experiment!

Answer 2

Based on Brits answer, I revised my code with a working version with some slight flaws in delayed displaying of the eating queue.

/*
Implement the dining philosopher’s problem with the following constraints/modifications.
* There should be 5 philosophers sharing chopsticks, with one chopstick between each adjacent pair of philosophers.
* Each philosopher should eat only 3 times (not in an infinite loop as we did in lecture)
* The philosophers pick up the chopsticks in any order, not lowest-numbered first (which we did in lecture).
* In order to eat, a philosopher must get permission from a host which executes in its own goroutine.
* The host allows no more than 2 philosophers to eat concurrently.
* Each philosopher is numbered, 1 through 5.
* When a philosopher starts eating (after it has obtained necessary locks) it prints "starting to eat " on a line by itself, where is the number of the philosopher.
* When a philosopher finishes eating (before it has released its locks) it prints "finishing eating " on a line by itself, where is the number of the philosopher.
*/
package main
import (
 "fmt"
 "math/rand"
 "sync"
 "time"
)
// define variables
const (
 numPhilo = 5
 numCS = 5
 eatTimes = 3
 numEatingPhilo = 2
)
type Host struct {
 // bookkeeping of the current eating philosophers
 eatingPhilos []int
}
// daemon function to manage the allowed philosophers
func (pHost *Host) manage(requestChannel <-chan *Philo, finishChannel <-chan *Philo, quitChannel <-chan bool, responseChannel chan<- bool) {
 lastQ := []int{}
 // daemon serving in the backend and only exits for terminate signal
 for {
 select {
 // remove finished philosopher
 case pPhilo := <-finishChannel:
 fmt.Printf("philosopher %d signaled finish eating\n", pPhilo.idx)
 tmpIdx := -1
 for idx, e := range pHost.eatingPhilos {
 if e == pPhilo.idx {
 tmpIdx = idx
 break
 }
 }
 if tmpIdx == -1 {
 panic("finished philosopher not found in record")
 }
 pHost.eatingPhilos = append(pHost.eatingPhilos[:tmpIdx], pHost.eatingPhilos[tmpIdx+1:]...)
 // handle submitted request
 case pPhilo := <-requestChannel:
 if len(pHost.eatingPhilos) >= numEatingPhilo {
 if !intSlicesEqual(pHost.eatingPhilos, lastQ) {
 fmt.Printf("eating queue is full with philosophers %v\nif conflicting philosphers are observed, one philosopher actually finished but delayed signaling\n", pHost.eatingPhilos)
 }
 responseChannel <- false
 lastQ = append([]int{}, pHost.eatingPhilos...)
 continue
 }
 // reserve the chopsticks
 pPhilo.rightCS.mu.Lock()
 pPhilo.leftCS.mu.Lock()
 responseChannel <- true
 pHost.eatingPhilos = append(pHost.eatingPhilos, pPhilo.idx)
 case <-quitChannel:
 fmt.Println("stop hosting")
 return
 }
 }
}
type ChopS struct {
 idx int
 mu sync.Mutex
}
type Philo struct {
 // index of the philosopher
 idx int
 // number of times the philosopher has eaten
 numEat int
 leftCS, rightCS *ChopS
 host *Host
}
func (pPhilo *Philo) eat(requestChannel chan<- *Philo, finishChannel chan<- *Philo, responseChannel <-chan bool, wg *sync.WaitGroup) {
 defer wg.Done()
 for pPhilo.numEat < eatTimes {
 // submit a request to the host and wait for response
 requestChannel <- pPhilo
 response := <-responseChannel
 // if not allowed, skip
 if !response {
 continue
 }
 pPhilo.numEat++
 fmt.Printf("philosopher %d starting to eat (%d feed)\n", pPhilo.idx, pPhilo.numEat)
 time.Sleep(time.Millisecond * time.Duration(rand.Intn(1000)))
 fmt.Printf("philosopher %d finish eating (%d feed)\n", pPhilo.idx, pPhilo.numEat)
 // release the chopsticks
 // given that we only signal finishing after releasing the chopsticks
 // there could be delay between the philosopher finishing and its signaling of the finish
 pPhilo.leftCS.mu.Unlock()
 pPhilo.rightCS.mu.Unlock()
 finishChannel <- pPhilo
 }
}
func intSlicesEqual(a, b []int) bool {
 if len(a) != len(b) {
 return false
 }
 for i, v := range a {
 if v != b[i] {
 return false
 }
 }
 return true
}
func main() {
 var wg sync.WaitGroup
 // channel for submitting request to host
 requestChannel := make(chan *Philo)
 // channel for philosopher indicating finish
 finishChannel := make(chan *Philo)
 // channel for receving feedback of the request from the host
 responseChannel := make(chan bool)
 // channel for terminate signal for the host
 quitChannel := make(chan bool)
 host := Host{
 eatingPhilos: make([]int, 0, numEatingPhilo),
 }
 CSticks := make([]*ChopS, numCS)
 for i := 0; i < numCS; i++ {
 CSticks[i] = &ChopS{idx: i}
 }
 philos := make([]*Philo, numPhilo)
 for i := 0; i < numPhilo; i++ {
 philos[i] = &Philo{idx: i + 1, numEat: 0, leftCS: CSticks[i], rightCS: CSticks[(i+1)%5], host: &host}
 }
 go host.manage(requestChannel, finishChannel, quitChannel, responseChannel)
 wg.Add(numPhilo)
 for i := 0; i < numPhilo; i++ {
 go philos[i].eat(requestChannel, finishChannel, responseChannel, &wg)
 }
 wg.Wait()
 quitChannel <- true
}
```