-3

私は次のような課題を持つ囲碁コースを取っています：

次の制約/変更を加えて、食事の哲学者の問題を実装します。

  • 箸を共有する 5 人の哲学者がいて、隣接する哲学者の各ペアの間に 1 つの箸が必要です。

  • 各哲学者は 3 回だけ食べる必要があります (講義で行ったような無限ループではありません)。

  • 哲学者は、番号の小さいものからではなく、任意の順序で箸を手に取ります (これは講義で行いました)。

  • 食べるために、哲学者は独自のゴルーチンで実行するホストから許可を得る必要があります。

  • ホストは、2 人を超える哲学者が同時に食事をすることを許可しません。

各哲学者には、1 から 5 までの番号が付けられています。

哲学者が (必要なロックを取得した後に) 食べ始めると、行に "starting to eat" と表示されます。ここに哲学者の番号が表示されます。

哲学者が (ロックを解除する前に) 食事を終えると、"finning eat" と 1 行に表示されます。どこに哲学者の番号がありますか。

私の実装:

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

単体テスト：

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

問題は、テストがランダムに失敗することです。以下は1つの実行です（行番号が追加されています）：

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 は 10 行目と 24 行目で開始し、11 行目、18 行目、28 行目で終了しています。28 行目は一致しないため、テストは正しくエラーを出します。ただし、バグを見つけるのに苦労しています。手伝ってくれますか？

4

1 に答える 1