您的位置: 首页  >  文章  >  经典的哲学家就餐问题笔记

经典的哲学家就餐问题笔记

分类: 文章 • 2024-08-31 11:35:58

以哲学家问题来总结归纳解决死锁问题的各种方法，哲学家进餐问题是一个经典的进程之间的同步互斥问题。
经典的哲学家就餐问题笔记
问题描述就是：
1、有五个哲学家围坐在一圆桌旁，桌*有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子

2、每个哲学家的行为是思考，感到饥饿，然后吃通心粉

3、为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或者后边去取筷子（筷子的互斥使用、不能出现死锁的现象）

问题模型：
应用程序中并发线程执行过程时，协调处理共享资源

哲学家就餐问题第一种解决方案 

semaphore fork[5] = {1};
int i ;
void philosopher(int i)
{
      while(true){
              think();
              p(fork[i]);
              p(fork[(i+1) mod 5]);
              eat();
              V(fork[(i+1) mod 5]);
              V(fork[i]);
      }
}
void main()
{
      parbegin (philosopher(0),philosopher(1),philosopher(2),philosopher(3),philosopher(4));
}

这种方案是把筷子当做一个信号量来处理，因此要去拿筷子的时候就去对信号量进行P操作，相当于申请一只筷子，先申请了左边的筷子，在申请了右边的筷子，那么在申请下会出现死锁呢？也就说当每个哲学家都拿到了右边的筷子，都等待拿左边的筷子的时候就会出现死锁，
p(fork[i]);
p(fork[(i+1) mod 5]);
当一个哲学家拿到一双筷子后他被切换下CPU了，然后另外一个哲学家也拿到他右边的筷子，那么如果非常巧，每个哲学家都刚好拿到了右边的筷子，又在等待左边的筷子，那么系统、哲学家就无限等待下去了。

为防止死锁发生可采取的措施

1、最多允许4个哲学家同时坐在桌子周围（也就是说他在思考问题的时候可以在四处溜达，当他感到饥饿的时候在坐在桌子旁边）

2、仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（这样就会一次拿到两只筷子）

3、给所以哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之

哲学家就餐问题第二种解决方案

以最多允许4个哲学家同时坐在桌子周围为例。

semaphore fork[5] = {1};
int i ;
void philosopher(int i)
{
      while(true){
              think();
              p(room);
              p(fork[i]);
              p(fork[(i+1) mod 5]);
              eat();
              V(fork[(i+1) mod 5]);
              V(fork[i]);
              V(room);
      }
}
void main()
{
      parbegin (philosopher(0),philosopher(1),philosopher(2),philosopher(3),philosopher(4));
}

增加了一个新的信号量room,room的最大值是4,因此，当哲学家饥饿了，要先坐到桌子旁边，如果用p(room);来表示他能不能坐到桌子旁边，那么就最多允许4个哲学家坐到桌子旁边，就不会出现死锁问题了，因为有4个哲学家坐到桌子旁边吗，有5只筷子，肯定有一个哲学家可以拿到两只筷子去吃。

哲学家就餐问题第三种解决方案

使用管程解决哲学家就餐问题

void philospher[k = 0 to 4]
/* the five  philospher clients*/
{
while(true){
<think>;
get_forks(k);   /*client requests two forks via monitor*/
eat <spaghetti>;
release_forks(k);/**client releases two forks via monitor*
}
}

刚刚说到仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（这样就会一次拿到两只筷子），可以通过管程来解决这个问题，我们设点了管程之和，那么每个哲学家去取筷子的时候就有去取筷子的这么一个操作，这个操作偶的实现是在管程里面，所以他通过管程就一次拿到两只筷子，然后用完了筷子就还回去，也是通过管程。
经典的哲学家就餐问题笔记
定义了两个管程之后，可以看到取筷子的操作他先拿左边的筷子，然后再拿后边的筷子，如果中间拿不到两只筷子，他就在管程里等待就好了，管程的问题实际上就是当两只筷子都可用的时候才让他去拿，所以就是一次拿到两只筷子。

哲学家就餐问题第四种解决方案 

#define N 5
# define THINKING 0
# define HUNGRY 1
# define  EATING 2
# typedef int semaphore;
int state[N];
semaphore mutex = 1;
semaphore s[N];

这种解法，实际上是为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只筷子，否则不拿。可以看下代码

void philospher（int i）
{
      while(true)
      {
      思考；
      P(&mutex);
      state[i] = HUNGRY;
      test(i);
      V(&mutex)；
      P(&s[i]);
      拿左筷子；
      拿右筷子；
      进食；
      放左筷子；
      放右筷子；
      P(&mutex);
       state[i] = HUNGRY;
        test([i-1]%5);
        test([i+1]%5);
        V(&mutex)；
       }
}
state[i] =THINKING;
s[i] = 0;

首先，每个哲学家的行为是思考，然后他可能会感到饥饿，因此呢，他需要一个状态来进入他现在的状态 是饥饿状态，在他之前是个思考状态，那么为了进入这个状态，需要做个P操作，因为饥饿状态可以被多个哲学家进行、修改，那么我们要看看互斥，做完状态的改变后就判断能否同时拿到两双筷子，所以就是做个测试，如果测试的结果通过了，他就可以同时拿到两只筷子，他就去做拿筷子的操作，什么不能通过测试呢是看P(&s[i]);这个p操作来决定，如果拿到了两只筷子就开始去进食，然后再去把筷子放回去，然后再去改变状态，变为思考，依然要注意要有一堆PV操作互斥保护这个临界区。再来看一下，每个哲学家都要去判断一下能不能拿到两只筷子就是测试，而测试结果呢就是导致P操作（P(&s[i]);）的顺利进行，下面是测试的代码：

void test(int i)
{
   if(state[i] ==HUNGRY)
   &&(state[(i-1) % 5] != EATING)
    &&(state[(i+1) % 5] != EATING)
    {
      state[i] = EATING;
      V(&s[i]);
    }
}

测试传递进来的参数是某个哲学家的编号，比如说第2号哲学家要来测试一下，首先，他的状态是个饥饿状态，同时，他的右边是1号哲学家并没有在吃还是在吃，如果他的状态是EARING，那么条件就不成立，如果右边1号哲学家没有在吃，同时左边的3号哲学家也没有在吃，因此我们可以看到，2号哲学家想进食，同时1号和3号哲学家都没有在进食状态，那就说明2号哲学家可以拿到两只筷子可以去进食，把状态改为EATING状态。这个时候还做了个V操作，有了这个 V(&s[i]);操作和外面的P(&s[i]);对应，那么P操作操作就可以通过了去取左右筷子进食。如果2号哲学家做检查的时候，假设1号哲学家正在就餐，也就是说这个条件不成立了，所以就没有做那个 V(&s[i])；操作，那么回来走到P(&s[i]);的时候他就会被阻塞在这个P操作位置，就不能去继续拿筷子进食。

再来看假设一个哲学家换回了筷子之后，他的状态又变为思考，他还要做两件事情，因为他拿到筷子的时候可能有左右两边的哲学家都来想拿到这只筷子，但是由于他正在进食，左右两边的哲学家拿不到筷子就处于等待状态，等待在他那个哲学家所对应的P(&s[i]);信号量上，而当这个哲学家结束了进食，重新变成思考之后呢，他还要有一个测试，看看是不是要把左右两边的哲学家来释放的筷子可以分配他们，因此又做了两个测试 test([i-1]%5); test([i+1]%5);还是以2号哲学家为例，第一个是对1号哲学家做测试，同时对3号哲学家进行测试，所以当2号哲学家吃完了变成了思考状态的时候呢对1号和3号哲学家做测试，假设以3号哲学家为例，3传入到刚刚上面的那个测试代码，刚才3号哲学家是饥饿状态，但是2号哲学家正在吃，所以这个条件不满足，所以3号哲学家结束了测试之后呢就等在P(&s[i]);这个位置，那么2号做了个测试之后，释放了筷子，3号测试就满足条件了执行了V(&s[i])；，一旦执行了这个操作，就把刚才等在那的3号哲学家释放了，把他重新变成就绪，可以上CPU。

哲学家进餐问题讨论

1、何时发生死锁？

2、怎么从死锁中恢复？

3、怎样避免死锁的发生？

4、如何预防死锁？

（1）根据刚才的分析可以看到，当每个哲学家都拿到了右边的一只筷子，那么这个时候都在等左边的那个筷子，那么就是说发生了死锁

（2）发生了死锁之后如何恢复，根据以上的各种解除死锁的讨论，我们可以选择一种某个哲学家放下一只筷子，那么这样的话就解除了死锁。

（3）第一个哲学家拿到了一只筷子，被切换下了CPU，第二个哲学家也拿到了一只筷子，恰好也被切换下去，那么到了第五个哲学家来的时候，系统中还剩下最后一只筷子，而如果第五个助学家拿到了这只筷子，系统就出现死锁，所以我们知道，**根据银行家算法，**那么最后这只筷子只能分给手里已经拿到筷子的某个哲学家，那么这就是死锁避免，就是银行家算法在哲学家就餐上的应用，当系统只剩下最后一只筷子，那么一定只能分配给手里已经拿有一只筷子的某个哲学家，

（4）如何预防死锁呢，也就是在资源分配算法的时间。我们怎么设计然后让死锁不会发生，前面已经说到只能同时拿到两只筷子才让你去拿，这就是一种一次性分配的思想，那么也可以采用刚才提出的一种方案，就是说我们采用资源的有序分配法，我们给每个哲学家编个号，给每个筷子编号，我们就要求哲学家在申请筷子的时候首先要申请编号小的那只筷子，再申请编号大的那只筷子，那也就是说，大部分哲学家都是先拿右边的再拿左边的，只有最后一个哲学家比如说5号哲学家，他得先拿左边的筷子在拿右边的筷子，因为他右边的筷子比如编号是5，左边筷子的编号是1，所他是按照反的方向先拿左在拿右，其他的先拿右再拿左，这样的话就能满足资源的有序分配法，而采用资源有序分配法，那么系统中不会出现死锁。

相关推荐