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.
I implemented the following code:
package main
import (
"fmt"
"sync"
)
// 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
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 {
// if the channel is full, release the head of the queue
if len(pHost.requestChannel) == numEatingPhilo {
finished := <-pHost.requestChannel
currEating := make([]int, 0, numPhilo)
for tmpIdx, eating := range pHost.eatingPhilos {
if eating {
currEating = append(currEating, tmpIdx)
}
}
fmt.Printf("%v have been eating, clearing up %d\n", currEating, finished.idx)
pHost.eatingPhilos[finished.idx] = false
}
select {
case <-pHost.quitChannel:
fmt.Println("stop hosting")
return
default:
}
}
}
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.host.mu.Lock()
pPhilo.host.eatingPhilos[pPhilo.idx] = true
pPhilo.host.mu.Unlock()
pPhilo.numEat++
fmt.Printf("starting to eat %d for %d time\n", pPhilo.idx, pPhilo.numEat)
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
requestChannel := make(chan *Philo, numEatingPhilo)
quitChannel := make(chan int, 1)
host := Host{requestChannel: requestChannel, quitChannel: quitChannel, 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 5 for 1 time
finishing eating 5 for 1 time
starting to eat 2 for 1 time
finishing eating 2 for 1 time
[5 2] have been eating, clearing up 5
[2] have been eating, clearing up 2
[] have been eating, clearing up 5
starting to eat 5 for 2 time
finishing eating 5 for 2 time
starting to eat 5 for 3 time
finishing eating 5 for 3 time
[5 2] have been eating, clearing up 2
[5] have been eating, clearing up 5
starting to eat 2 for 2 time
finishing eating 2 for 2 time
[4] have been eating, clearing up 4
starting to eat 4 for 1 time
finishing eating 4 for 1 time
[] have been eating, clearing up 2
starting to eat 4 for 2 time
finishing eating 4 for 2 time
[4] have been eating, clearing up 4
starting to eat 4 for 3 time
finishing eating 4 for 3 time
starting to eat 2 for 3 time
finishing eating 2 for 3 time
starting to eat 1 for 1 time
finishing eating 1 for 1 time
[2 4 1] have been eating, clearing up 4
[2 1] have been eating, clearing up 1
[2] have been eating, clearing up 3
starting to eat 1 for 2 time
finishing eating 1 for 2 time
[1 2] have been eating, clearing up 1
starting to eat 3 for 1 time
finishing eating 3 for 1 time
starting to eat 3 for 2 time
finishing eating 3 for 2 time
[3 2] have been eating, clearing up 1
[2 3] have been eating, clearing up 3
starting to eat 3 for 3 time
finishing eating 3 for 3 time
starting to eat 1 for 3 time
finishing eating 1 for 3 time
stop hosting
where sometimes it seems the philosophers cannot eat concurrently, and also according to the logs, the bookkeeping map is acting weird.
Could someone please point out which part of the implementation is improper? Anything obviously wrong or bad practice?
The code you posted here contains data races (Host.eatingPhilos is accessed from multiple go-routines without any protection). You resolved these before posting your question on code review which went some way towards a working solution (but introduced other issues).
I answered this fully on code review and provided some feedback etc. As the code you posted there differs from what is here there is little point in duplicating the answer. However, I will include my suggested solution because it adopts a significantly different approach to that you took (in order to work around a few logic issues). Note that this solution takes an easy way out of the "starving philosopher" issue (each philosopher has one chopstick, so none can get a second). See the Wikipedia page for some other, better, solutions (but I figure you wanted to use go routines).
warning - the below may well contain bugs!
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)
}