使用银行家算法解决哲学家就餐问题

哲学家就餐问题

「哲学家就餐问题」是一个非常经典的线程同步互斥以及死锁问题, 问题描述如下:

• 有 5 个哲学家围坐在一个圆桌上思考.
• 相邻的两个哲学家中间有一个叉子, 所以一共有 5 个叉子.
• 而当一个哲学家饿了, 他需要拿起左右两个叉子才可以进餐.
• 哲学家在进餐完成后会放下叉子, 继续思考, 直到他再次饿了.

在这个问题描述中, 我们发现了一个可能会造成死锁的情况, 那就是当所有的哲学家都只拿到了左边/右边的叉子, 就会导致没有一个人能够进餐, 并且也没有叉子会被放下.

为了解决这个问题, 可以有非常多种办法. 但是从抽象层面来说, 叉子其实就是一种资源, 为了解决资源的缺乏而导致的死锁问题. 这里我们使用银行家算法解决哲学家就餐问题.

银行家算法

银行家算法的本质是, 系统只会确认进程所需的最大资源, 在确认分配最大资源后不会发生死锁的情况下才会对一个进程分配资源.

因此, 系统需要在分配资源之前就知道进程所需的最大资源是多少才能使用该算法. 而恰好在「哲学家就餐问题」中, 我们很明确每个哲学家最多只需要他左右两个叉子. 因此, 系统只需要判断左右两个资源(叉子)是否可用, 即可判断是否会发生死锁.

以下是使用 Go 语言对该算法进行的一个模拟:

package main

import (
    "fmt"
    "math/rand"
    "time"
)

var (
    mutex    = make(chan bool, 1)
    N        = 100
    forks    []chan struct{}
    eatCount = make([]int, N)
    randTime = func() time.Duration {
        return time.Duration(rand.Intn(5)) * time.Microsecond
    }
)

func init() {
    forks = make([]chan struct{}, N)
    for i := 0; i < N; i++ {
        forks[i] = make(chan struct{}, 1)
    }
}

func thinking() {
    time.Sleep(randTime())
}

func takeFork(i int) {
    leftFork, rightFork := (i-1+N)%N, (i+1)%N
    for {
        // have chance to take fork
        mutex <- true
        if len(forks[leftFork]) == 0 && len(forks[rightFork]) == 0 {
            forks[leftFork] <- struct{}{}
            forks[rightFork] <- struct{}{}
            // take two forks
            <-mutex
            return
        }
        // take zero forks
        <-mutex
    }
}

func eat(i int) {
    eatCount[i]++
    fmt.Printf("philosopher %v is eating %v times\n", i, eatCount[i])
    time.Sleep(randTime())
}

func putFork(i int) {
    leftFork, rightFork := (i-1+N)%N, (i+1)%N
    <-forks[leftFork]
    <-forks[rightFork]
}

func philosopher(i int) {
    for {
        // spend random time
        thinking()
        // take two forks
        takeFork(i)
        // spend random time
        eat(i)
        // put two forks
        putFork(i)
    }
}

func main() {
    for i := 0; i < N; i++ {
        go philosopher(i)
    }
    startTime := time.Now()
    for {
        time.Sleep(5 * time.Microsecond)
        flag := true
        for i := 0; i < N; i++ {
            if eatCount[i] < 200 {
                flag = false
                break
            }
        }
        if flag {
            fmt.Println(time.Since(startTime))
            return
        }
    }
}

由于需要保证在分配资源时, 不会发生同时分配资源的情况. 因此我们需要一个锁来保证同一时间仅有一个哲学家可以申请叉子.