• 23
• 3

• 23
• 3

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 racing 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?