Skip to main content
deleted 2 characters in body
Source Link

I checked the program with go build -race for racingrace 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.

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.

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.

Source Link

Golang implementation of dining philosophers variant

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?