英文:
Dining philosophers problem in Go fails unit test
问题
你好!根据你提供的信息,你正在实现哲学家就餐问题,并且编写了一个测试函数来验证你的实现。测试函数会运行多个哲学家的就餐过程,并检查输出是否符合预期。
你遇到的问题是,测试函数有时会随机失败。你提供了一个失败的执行示例,其中第4个哲学家在第10行和第24行开始就餐,在第11行、第18行和第28行结束就餐。由于第28行没有匹配的开始就餐行,所以测试函数报错。
你希望找到错误所在,我将帮助你进行排查。
首先,让我们分析一下代码。你的实现中使用了goroutine和信号量来控制哲学家的并发就餐。每个哲学家都会尝试获取两个相邻筷子的锁,并在就餐前后打印相应的信息。
根据你提供的示例输出,我们可以看到问题出现在第4个哲学家身上。他在第10行和第24行之间的某个时刻开始就餐,但在第28行之前没有结束就餐。这表明第4个哲学家在某个时刻无法获取到所需的筷子锁,导致他无法就餐。
为了解决这个问题,我们需要仔细检查代码,特别是与锁相关的部分。请稍等片刻,我将仔细查看你的代码并尝试找到问题所在。
英文:
I'm taking a Go course, that has an assignment as follows:
> 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 <number>" on a line by itself, where
> <number> is the number of the philosopher.
>
> When a philosopher finishes eating (before it has released its locks)
> it prints "finishing eating <number>" on a line by itself, where
> <number> is the number of the philosopher.
My implementation:
package main
import (
"fmt"
"io"
"math/rand"
"os"
"sync"
"time"
)
const (
NumPhilosophers = 5
NumEatMaxTimes = 3
NumMaxAllowedToEat = 2
)
type chopstick struct{ sync.Mutex }
type philosopher struct {
num int
cs []*chopstick
}
func setTable() []*philosopher {
cs := make([]*chopstick, NumPhilosophers)
for i := 0; i < NumPhilosophers; i++ {
cs[i] = new(chopstick)
}
ph := make([]*philosopher, NumPhilosophers)
for i := 0; i < NumPhilosophers; i++ {
ph[i] = &philosopher{i + 1, []*chopstick{cs[i], cs[(i+1)%NumPhilosophers]}}
}
return ph
}
func (ph philosopher) eat(sem chan int, wg *sync.WaitGroup, w io.Writer) {
for i := 0; i < NumEatMaxTimes; i++ {
/* Ask host for permission to eat */
sem <- 1
/*
Pick any of the left or right chopsticks.
Notice how the methods on the Mutex can be called directly on a chopstick due to embedding.
*/
firstCS := rand.Intn(2)
secondCS := (firstCS + 1) % 2
ph.cs[firstCS].Lock()
ph.cs[secondCS].Lock()
fmt.Fprintf(w, "Starting to eat %d\n", ph.num)
x := rand.Intn(NumEatMaxTimes)
time.Sleep(time.Duration(x) * time.Second)
fmt.Fprintf(w, "Finishing eating %d\n", ph.num)
ph.cs[secondCS].Unlock()
ph.cs[firstCS].Unlock()
<-sem
}
wg.Done()
}
func main() {
run(os.Stdout)
}
func run(w io.Writer) {
var sem = make(chan int, NumMaxAllowedToEat)
rand.Seed(time.Now().UnixNano())
var wg sync.WaitGroup
allPh := setTable()
wg.Add(len(allPh))
for _, ph := range allPh {
go ph.eat(sem, &wg, w)
}
wg.Wait()
}
Unit test:
func TestRun(t *testing.T) {
var out bytes.Buffer
run(&out)
lines := strings.Split(strings.ReplaceAll(out.String(), "\r\n", "\n"), "\n")
eating := make(map[int]bool)
timesEaten := make(map[int]int)
for _, line := range lines {
if line == "" {
continue
}
fmt.Println(line)
tokens := strings.Fields(line)
i, err := strconv.Atoi(tokens[len(tokens)-1])
if err != nil {
t.Errorf("Bad line: %s", line)
}
s := strings.ToLower(tokens[0])
if s == "starting" {
if len(eating) > (NumMaxAllowedToEat - 1) {
t.Errorf("%v are eating at the same time", eating)
}
_, ok := eating[i]
if ok {
t.Errorf("%d started before finishing", i)
}
eating[i] = true
} else if s == "finishing" {
_, ok := eating[i]
if !ok {
t.Errorf("%d finished without starting", i)
}
delete(eating, i)
timesEaten[i] = timesEaten[i] + 1
}
}
for k, v := range timesEaten {
if v > NumEatMaxTimes {
t.Errorf("%d ate %d times", k, v)
}
}
if len(timesEaten) != NumPhilosophers {
t.Error("One or more didn't get to eat")
}
}
The problem is, the test randomly fails. Below is one execution (line numbers added):
1. Starting to eat 5
2. Starting to eat 2
3. Finishing eating 2
4. Finishing eating 5
5. Starting to eat 3
6. Starting to eat 1
7. Finishing eating 1
8. Finishing eating 3
9. Starting to eat 2
10. Starting to eat 4
11. Finishing eating 4
12. Starting to eat 5
13. Finishing eating 2
14. Finishing eating 5
15. Starting to eat 3
16. Finishing eating 3
17. Starting to eat 1
18. Finishing eating 4
19. Finishing eating 1
20. Starting to eat 5
21. Finishing eating 5
22. Starting to eat 3
23. Finishing eating 3
24. Starting to eat 4
25. Starting to eat 2
26. Finishing eating 2
27. Starting to eat 1
28. Finishing eating 4
29. Finishing eating 1
--- FAIL: TestRun (12.01s)
main_test.go:43: 4 finished without starting
Philosopher 4 has started on lines 10, and 24 and finished on lines 11, 18, and 28. Line 28 is unmatched, so the test correctly complains. However, I'm having a hard time finding the bug. Can you help?
答案1
得分: 1
回答我的问题后,结果表明 byes.Buffer 不是线程安全的。我最终使用了 go-fakeio 库进行测试,如下所示:
s, err := fakeio.Stderr().Stdout().Do(run)
if err != nil {
t.Errorf("%v", err)
}
其余的测试保持不变。main.run
函数不再需要一个 io.Writer
,因为 fakeio
库替换了 stderr 和 stdout。
英文:
Answering my own question, it turned out that byes.Buffer is not thread-safe. I ended up using go-fakeio library for the test as shown below.
s, err := fakeio.Stderr().Stdout().Do(run)
if err != nil {
t.Errorf("%v", err)
}
The rest of the test remains the same. main.run
function no longer needs an io.Writer
since the fakeio
library replaces stderr and stdout.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论