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?
