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