Golang implementation of dining philosophers variant problem

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"
)

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

Answer 1

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!

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)
}