校园内部网站建设方案,创业做软件还是做网站,机械网站建设栏目内容,贵州省住房和城乡建设厅电话哲学家进餐问题(代码实现以leetcode1226为例)问题场景解决思路解决死锁问题代码实现cgo(代码实现以leetcode1226为例)
提到多线程和锁解决问题#xff0c;就想到了os中哲学家进餐问题。
问题场景
回想该问题产生场景#xff0c;五个哲学家共用一张圆桌#xff0c;分别坐在…
哲学家进餐问题(代码实现以leetcode1226为例)问题场景解决思路解决死锁问题代码实现cgo(代码实现以leetcode1226为例)
提到多线程和锁解决问题就想到了os中哲学家进餐问题。
问题场景
回想该问题产生场景五个哲学家共用一张圆桌分别坐在周围的五张椅子上在圆桌上有五个碗和五只筷子他们的生活方式是交替的进行思考和进餐。平时一个哲学家进行思考饥饿时便试图取用其左右最靠近他的筷子只有在他拿到两只筷子时才能进餐。进餐完毕放下筷子继续思考。
解决思路
由于五位哲学家应相互独立因此可以创建五个线程分别代表五位哲学家相互独立异步依次编号为0~4。
对于资源筷子应该认为这是五种临界资源而不是一种临界资源。因为每位哲学家只能使用自己面前的两个筷子。同样对五只筷子进行资源编号0~4并且定义第i位哲学家左侧的筷子编号为i哲学家右侧的筷子编号为i1%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
#includesemaphore.h
class DiningPhilosophers {
public:DiningPhilosophers() {fork vectorsem_t(5);sem_init(room,0,4);for(int i 0;i 5;i){sem_init((fork[i]),0,1);}}void wantsToEat(int philosopher,functionvoid() pickLeftFork,functionvoid() pickRightFork,functionvoid() eat,functionvoid() putLeftFork,functionvoid() putRightFork) {sem_wait(room);sem_wait((fork[philosopher]));sem_wait((fork[(philosopher1)%5]));pickLeftFork();pickRightFork();eat();putRightFork();putLeftFork();sem_post((fork[(philosopher1)%5]));sem_post((fork[philosopher]));sem_post(room);}vectorsem_t fork;sem_t room;
};②AND信号量方式
#includesemaphore.h
class DiningPhilosophers {
public:DiningPhilosophers() {fork vectorsem_t(5);for(int i 0;i 5;i){sem_init((fork[i]),0,1);}sem_init(mutex,0,1);}void wantsToEat(int philosopher,functionvoid() pickLeftFork,functionvoid() pickRightFork,functionvoid() eat,functionvoid() putLeftFork,functionvoid() putRightFork) {sem_wait(mutex);sem_wait((fork[philosopher]));sem_wait((fork[(philosopher1)%5]));pickLeftFork();pickRightFork();sem_post(mutex);eat();putRightFork();putLeftFork();sem_post((fork[(philosopher1)%5]));sem_post((fork[philosopher]));}vectorsem_t fork;sem_t mutex;
};③奇偶数
#includesemaphore.h
class DiningPhilosophers {
public:DiningPhilosophers() {fork vectorsem_t(5);for(int i 0;i 5;i){sem_init((fork[i]),0,1);}}void wantsToEat(int philosopher,functionvoid() pickLeftFork,functionvoid() pickRightFork,functionvoid() eat,functionvoid() putLeftFork,functionvoid() putRightFork) {if(philosopher % 2 0){sem_wait((fork[philosopher]));sem_wait((fork[(philosopher1)%5]));pickLeftFork();pickRightFork();eat();putRightFork();putLeftFork();sem_post((fork[(philosopher1)%5]));sem_post((fork[philosopher]));}else{sem_wait((fork[(philosopher1)%5]));sem_wait((fork[philosopher]));pickLeftFork();pickRightFork();eat();putRightFork();putLeftFork();sem_post((fork[philosopher]));sem_post((fork[(philosopher1)%5]));}}vectorsem_t fork;
};go
奇偶数
package mainimport (fmtsync
)type DiningPhilosophers struct {getkey []chan intendsSgnal *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[(philosopher1)%5]pickRightFork(philosopher)eat(philosopher)putRightFork(philosopher)s.getkey[(philosopher1)%5] - 1putLeftFork(philosopher)s.getkey[philosopher] - 1} else {-s.getkey[(philosopher1)%5]pickRightFork(philosopher)-s.getkey[philosopher]pickLeftFork(philosopher)eat(philosopher)putLeftFork(philosopher)s.getkey[philosopher] - 1putRightFork(philosopher)s.getkey[(philosopher1)%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 : 100for 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()
}
