2
\$\begingroup\$

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?

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

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)
}
\$\endgroup\$
3
  • \$\begingroup\$ 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. \$\endgroup\$ Aug 5 at 21:12
  • \$\begingroup\$ 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? \$\endgroup\$ Aug 5 at 21:14
  • \$\begingroup\$ 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! \$\endgroup\$
    – Brits
    Aug 5 at 21:22
0
\$\begingroup\$

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
}

```
New contributor
Vincent Wen is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.