1226-哲學家進餐

問題描述

https://leetcode-cn.com/problems/the-dining-philosophers/

求解思路

題目沒有提供C語言解決方案，只能采用C++，C++有一套自己封裝了POSIX的執行緒庫，然而我并不會用，只能還是呼叫底層的sem_t互斥量及其相關操作集來實作執行緒同步（又逮到一個C with class）

對于哲學家進餐問題，一共有三種方式避免死鎖：

1. 保證每個哲學家拿叉子互斥，即對哲學家拿起左右兩只叉子這個程序上鎖保護
2. 令奇數號哲學家先拿左手邊的叉子，偶數號的哲學家先拿右手邊的叉子
3. 至多允許4名哲學家同時吃飯

代碼實作

死鎖避免方式1：利用mutex保證哲學家同時拿左右兩只叉子

#include <semaphore.h>
class DiningPhilosophers {
   public:
    DiningPhilosophers() {
        for (int i = 0; i < 5; ++i) {
            sem_init(&forks[i], 0, 1);
        }
        sem_init(&mutex, 0, 1);
    }
    ~DiningPhilosophers() {
        for (int i = 0; i < 5; ++i) {
            sem_destroy(&forks[i]);
        }
        sem_destroy(&mutex);
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        int leftFork = philosopher;
        int rightFork = (philosopher + 1) % 5;
        sem_wait(&mutex);
        sem_wait(&forks[leftFork]);
        sem_wait(&forks[rightFork]);
        sem_post(&mutex);

        pickLeftFork();
        pickRightFork();

        eat();

        putLeftFork();
        putRightFork();
        sem_post(&forks[leftFork]);
        sem_post(&forks[rightFork]);
    }

   private:
    sem_t forks[5];
    sem_t mutex;
}

死鎖避免方式2：奇數號哲學家先拿左手邊的叉子，偶數號的哲學家先拿右手邊的叉子

#include <semaphore.h>

class DiningPhilosophers {
   public:
    DiningPhilosophers() {
        for (int i = 0; i < 5; ++i) {
            sem_init(&forks[i], 0, 1);
        }
    }
    ~DiningPhilosophers() {
        for (int i = 0; i < 5; ++i) {
            sem_destroy(&forks[i]);
        }
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        int leftFork = philosopher;
        int rightFork = (philosopher + 1) % 5;
        if ((philosopher & 1) == 1) {
            sem_wait(&forks[leftFork]);
            sem_wait(&forks[rightFork]);
            pickLeftFork();
            pickRightFork();
        } else {
            sem_wait(&forks[rightFork]);
            sem_wait(&forks[leftFork]);
            pickRightFork();
            pickLeftFork();
        }

        eat();

        putLeftFork();
        putRightFork();
        sem_post(&forks[leftFork]);
        sem_post(&forks[rightFork]);
    }

   private:
    sem_t forks[5];
};

死鎖避免方式3：最多允許4個哲學家同時進餐

#include <semaphore.h>

class DiningPhilosophers {
   public:
    DiningPhilosophers() {
        for (int i = 0; i < 5; ++i) {
            sem_init(&forks[i], 0, 1);
        }
        sem_init(&nums, 0, 4);
    }
    ~DiningPhilosophers() {
        for (int i = 0; i < 5; ++i) {
            sem_destroy(&forks[i]);
        }
        sem_destroy(&nums);
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        int leftFork = philosopher;
        int rightFork = (philosopher + 1) % 5;
        sem_wait(&nums);

        sem_wait(&forks[leftFork]);
        sem_wait(&forks[rightFork]);
        pickLeftFork();
        pickRightFork();

        eat();

        putLeftFork();
        putRightFork();
        sem_post(&forks[leftFork]);
        sem_post(&forks[rightFork]);

        sem_post(&nums);
    }

   private:
    sem_t forks[5];
    sem_t nums;
};

識訓和疑惑

C++提供了比函式指標更高級的函式作為引數傳遞的方式：借助function關鍵字，有時間深入學習，

有時間學習一下C++封裝好的執行緒庫，