Golang解决哲学家就餐变体问题

今天golang学习网给大家带来了《Golang解决哲学家就餐变体问题》，其中涉及到的知识点包括等等，无论你是小白还是老手，都适合看一看哦~有好的建议也欢迎大家在评论留言，若是看完有所收获，也希望大家能多多点赞支持呀！一起加油学习~

我想实现经典哲学家就餐问题的一个变体，其定义为：

通过以下约束/修改来实现哲学家就餐问题。

• 应该有 5 个哲学家共用筷子，每对相邻的哲学家之间各插一根筷子。
• 每个哲学家只能吃 3 次（而不是像我们在讲座中那样无限循环）
• 哲学家以任意顺序拿起筷子，而不是从编号最小的开始（我们在讲座中这样做）。
• 为了吃饭，哲学家必须获得在自己的 goroutine 中执行的主机的许可。
• 主持人允许最多 2 名哲学家同时用餐。
• 每位哲学家都有编号，从 1 到 5。
• 当哲学家开始吃东西时（在获得必要的锁之后），它会在一行上打印“starting to eat”，其中是哲学家的编号。
• 当哲学家吃完时（在释放锁之前），它会在一行上打印“finishing eat”，其中是哲学家的编号。

我实现了以下代码：

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
}

但是，我注意到该程序实际上在某些情况下失败了，即

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

有时哲学家们似乎不能同时吃饭，而且根据日志，簿记地图表现得很奇怪。

有人可以指出实施的哪一部分不正确吗？有什么明显错误或不好的做法吗？

正确答案

您在此处发布的代码包含数据竞争（从多个 go 例程访问 host.eatingphilos，没有任何保护）。您在将问题发布到 code review 之前解决了这些问题，这在一定程度上实现了可行的解决方案（但引入了其他问题）。

我在 code review 上完整回答了这个问题，并提供了一些反馈等。由于您在那里发布的代码与此处的代码不同，因此重复答案没有什么意义。但是，我将包括我建议的解决方案，因为它采用了与您所采用的方法截然不同的方法（为了解决一些逻辑问题）。请注意，此解决方案采用了一种简单的方法来解决“饥饿的哲学家”问题（每个哲学家都有一根筷子，因此没有人可以获得第二根筷子）。请参阅 Wikipedia page 了解其他一些更好的解决方案（但我认为您想使用 go 例程）。

警告 - 下面可能包含错误！

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

今天带大家了解了的相关知识，希望对你有所帮助；关于Golang的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~