通过哲学家进餐问题学习线程间协作(代码实现以leetcode1226为例)-阿里云开发者社区

通过哲学家进餐问题学习线程间协作(代码实现以leetcode1226为例)

2023-05-19 113

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 通过哲学家进餐问题学习线程间协作(代码实现以leetcode1226为例)

(代码实现以leetcode1226为例)

提到多线程和锁解决问题，就想到了os中哲学家进餐问题。

问题场景

回想该问题产生场景，五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替的进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐完毕，放下筷子继续思考。

解决思路

由于五位哲学家应相互独立，因此可以创建五个线程分别代表五位哲学家，相互独立（异步），依次编号为0~4。

对于资源（筷子），应该认为这是五种临界资源，而不是一种临界资源。因为每位哲学家只能使用自己面前的两个筷子。同样对五只筷子进行资源编号0~4，并且定义第i位哲学家左侧的筷子编号为i，哲学家右侧的筷子编号为（i+1）%5（这里要注意对编号为0的进行特殊处理）。

临界资源的定义，一次只允许一个线程使用的公共资源。所以当一只筷子被一位哲学家使用时应该加锁。

形成一种解决思路如下：

while(1){
    think()
    hungry()
    p(左筷子)
    p(右筷子)
    eat()
    v(左筷子)
    v(右筷子)
}

显而易见这种解决办法会出现死锁问题，即当每位哲学家获取左筷子后，永久陷入了等待右筷子状态，且每个人都不会主动放弃获取的临界资源。

解决死锁问题

①我们可以只允许四个哲学家都拿起同一边的筷子，这样会保证一位哲学家可以得到两边筷子完成进食，释放临界资源，保证别的哲学家可以进行相应的线程。

这里要新增一个信号量，控制拿起同一边筷子的哲学家数量。

修改后的解决思路如下：

while(1){
    think()
    hungry()
    p(还可以拿起一边筷子)
    p(左筷子)
    p(右筷子)
    eat()
    v(左筷子)
    v(拿起一边筷子的名额)
    v(右筷子)
}

②采用AND信号量机制，即当一个线程要执行时一次性将所需的资源全部给他，否则不分给他资源。

新的解决思路如下：

while(1){
  think()
  hungry()
  Swait(左筷子，右筷子)
  eat()
  Spost(左筷子，右筷子)
}

针对不用的代码语言，当不支持and信号量机制时，可以考虑增加新的互斥信号量来实现。全局互斥信号量，当一个哲学家企图拿筷子时候，就将全部资源锁住。

修改后的解决思路如下：

while(1){
  think()
  hungry()
  p(lock)
  p(左筷子)
    p(右筷子)
    v(lock)
    eat()
    v(左筷子)
    v(右筷子)
}

③区分奇数偶数哲学家，规定奇数号哲学家先拿起他左边的筷子，然后再去拿他右边的筷子，而偶数号的哲学家则相反，这样的话总能保证一个哲学家能获得两根筷子完成进餐，从而释放其所占用的资源。

解决思路如下：

while(1){
  think(i)
  hungry(i)
  if(i % 2 == 0){
        p(左筷子)
        p(右筷子)
        eat()
        v(右筷子)
        v(左筷子)
    }
    else{
      p(右筷子)
      p(左筷子)
        eat()
        v(左筷子)
        v(右筷子)
    }
}

代码实现

c++

①只允许四个哲学家都拿起同一边的筷子 room信号量4

#include<semaphore.h>
class DiningPhilosophers {
public:
    DiningPhilosophers() {
        fork = vector<sem_t>(5);
        sem_init(&room,0,4);
        for(int i = 0;i < 5;i++){
            sem_init(&(fork[i]),0,1);
        }
    }
    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        sem_wait(&room);
        sem_wait(&(fork[philosopher]));
        sem_wait(&(fork[(philosopher+1)%5]));
        pickLeftFork();
        pickRightFork();
        eat();
        putRightFork();
        putLeftFork();
        sem_post(&(fork[(philosopher+1)%5]));
        sem_post(&(fork[philosopher]));
        sem_post(&room);
    }
    vector<sem_t> fork;
    sem_t room;
};

②AND信号量方式

#include<semaphore.h>
class DiningPhilosophers {
public:
    DiningPhilosophers() {
        fork = vector<sem_t>(5);
        for(int i = 0;i < 5;i++){
            sem_init(&(fork[i]),0,1);
        }
        sem_init(&mutex,0,1);
    }
    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        sem_wait(&mutex);
        sem_wait(&(fork[philosopher]));
        sem_wait(&(fork[(philosopher+1)%5]));
        pickLeftFork();
        pickRightFork();
        sem_post(&mutex);
        eat();
        putRightFork();
        putLeftFork();
        sem_post(&(fork[(philosopher+1)%5]));
        sem_post(&(fork[philosopher]));
    }
    vector<sem_t> fork;
    sem_t mutex;
};

③奇偶数

#include<semaphore.h>
class DiningPhilosophers {
public:
    DiningPhilosophers() {
        fork = vector<sem_t>(5);
        for(int i = 0;i < 5;i++){
            sem_init(&(fork[i]),0,1);
        }
    }
    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        if(philosopher % 2 == 0){
            sem_wait(&(fork[philosopher]));
            sem_wait(&(fork[(philosopher+1)%5]));
            pickLeftFork();
            pickRightFork();
            eat();
            putRightFork();
            putLeftFork();
            sem_post(&(fork[(philosopher+1)%5]));
            sem_post(&(fork[philosopher]));
        }
        else{
            sem_wait(&(fork[(philosopher+1)%5]));
            sem_wait(&(fork[philosopher]));
            pickLeftFork();
            pickRightFork();
            eat();
            putRightFork();
            putLeftFork();
            sem_post(&(fork[philosopher]));
            sem_post(&(fork[(philosopher+1)%5]));
        }
    }
    vector<sem_t> fork;
};

go

奇偶数

package main
import (
  "fmt"
  "sync"
)
type DiningPhilosophers struct {
  getkey    []chan int
  endsSgnal *sync.WaitGroup
}
func pickLeftFork(i int) {
  fmt.Printf("philosopher %d pickLeftFork\n", i)
}
func pickRightFork(i int) {
  fmt.Printf("philosopher %d pickRightFork\n", i)
}
func eat(i int) {
  fmt.Printf("philosopher %d eat\n", i)
}
func putLeftFork(i int) {
  fmt.Printf("philosopher %d putLeftFork\n", i)
}
func putRightFork(i int) {
  fmt.Printf("philosopher %d putRightFork\n", i)
}
func (s *DiningPhilosophers) wantsToEat(philosopher int, pickLeftFork func(int), pickRightFork func(int), eat func(int), putLeftFork func(int), putRightFork func(int)) {
  if philosopher%2 == 0 {
    <-s.getkey[philosopher]
    pickLeftFork(philosopher)
    <-s.getkey[(philosopher+1)%5]
    pickRightFork(philosopher)
    eat(philosopher)
    putRightFork(philosopher)
    s.getkey[(philosopher+1)%5] <- 1
    putLeftFork(philosopher)
    s.getkey[philosopher] <- 1
  } else {
    <-s.getkey[(philosopher+1)%5]
    pickRightFork(philosopher)
    <-s.getkey[philosopher]
    pickLeftFork(philosopher)
    eat(philosopher)
    putLeftFork(philosopher)
    s.getkey[philosopher] <- 1
    putRightFork(philosopher)
    s.getkey[(philosopher+1)%5] <- 1
  }
  s.endsSgnal.Done()
}
func main() {
  s := &DiningPhilosophers{
    getkey:    make([]chan int, 5),
    endsSgnal: &sync.WaitGroup{},
  }
  for i := 0; i < len(s.getkey); i++ {
    s.getkey[i] = make(chan int, 1)
    s.getkey[i] <- 1
  }
  n := 100
  for i := 0; i < n; i++ {
    s.endsSgnal.Add(5)
    go s.wantsToEat(0, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)
    go s.wantsToEat(1, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)
    go s.wantsToEat(2, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)
    go s.wantsToEat(3, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)
    go s.wantsToEat(4, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)
  }
  s.endsSgnal.Wait()
}

通过哲学家进餐问题学习线程间协作(代码实现以leetcode1226为例)

(代码实现以leetcode1226为例)

问题场景

解决思路

解决死锁问题

代码实现

c++

go

热门文章

最新文章

相关电子书