(代码实现以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() }
