使用监视器的哲学家就餐问题

操作系统是一种管理计算机的每一个方面的软件，以便其能够平稳且正确地运行。因此，操作系统必须同时执行多个任务。同时执行任务对操作系统来说并非真正的问题，但当这些同时执行的任务使用公共资源时，就会发生故障。为了克服这种情况，引入了同步机制，它基本上管理共享相同资源的进程。哲学家就餐问题是一个经典的同步问题。

什么是哲学家就餐问题？

哲学家就餐问题背后的故事是，它代表了一种场景，一群哲学家围坐在一张圆桌旁，他们一生都在思考或吃意大利面。为简便起见，让我们假设有五个哲学家坐在桌子旁。圆桌上有五个叉子。为了吃饭，每个哲学家需要两个叉子；一个在他的左边，另一个在他的右边。哲学家一次只能拿起一个筷子。他不能拿起坐在他旁边另一个哲学家手中已经有的筷子。当哲学家同时拥有两个筷子时，他开始吃饭而不放下筷子。问题在于设计一种算法来分配这些有限的资源（筷子）给进程（哲学家），而不会导致死锁或饥饿。

现在，存在一些可以解决哲学家就餐问题的算法，但可能会出现死锁情况。此外，无死锁情况并不一定无饥饿情况。在解决哲学家就餐问题时，可以使用信号量，但这可能会导致死锁。因此，为了避免这些情况，我们使用带有条件变量的监视器。

什么是监视器？

抽象数据类型 (ADT) 是一种编程概念，它将私有数据与操作数据的公共方法封装在一起。这意味着数据对外部世界是隐藏的，只能通过一组预定义的方法访问或操作。

监视器也是一种 ADT，它提供一组程序员定义的操作，这些操作在监视器内提供互斥。简单来说，监视器是一种同步概念，它在访问共享资源的并发线程或进程之间提供互斥和协调。它封装了共享资源以及一组可用于以线程安全的方式访问和修改该资源的过程。

语法

监视器的伪代码：

monitor monitor_name{
   procedure p1(…){
   …
   }
   procedure p2(…){
   …
   }
   .
   .
   .
   procedure pn(…){
   …
   }
   Initialization code (…){
   …
   }
}

什么是条件变量？

条件变量在监视器内部提供同步。如果一个进程想要休眠或允许一个等待的进程继续，在这种情况下，监视器中使用条件变量。可以在条件变量上执行两个操作：wait 和 signal

  • wait() − 调用此操作的进程将被挂起并放入该条件变量的阻塞队列中。

  • signal() − 此操作恢复挂起的进程。

什么是信号量？为什么监视器比信号量更受青睐？

信号量是一个整数变量，进程可以使用它来允许它们访问共享的公共资源。除了初始化之外，信号量只能通过两个原子操作访问：wait() 和 signal()。信号量有两种类型：

  • 二元信号量

  • 计数信号量

信号量和监视器都可以用来解决哲学家就餐问题。但是，关于哪一个更好——信号量或监视器——并没有明确的答案。这完全取决于问题的具体要求。

一方面，由于其内置的互斥和条件变量，监视器为哲学家就餐问题提供了更简单直接的解决方案。

另一方面，信号量需要更复杂的同步代码，并且由于前面解释的原因，更容易出错和死锁。

总而言之，虽然监视器和信号量都用于解决哲学家就餐问题，但监视器比信号量更方便。

使用监视器的哲学家就餐问题解决方案

使用监视器是因为它们为哲学家就餐问题提供了一个无死锁的解决方案。它用于访问所有状态变量和条件变量。应用监视器后，它施加一个限制，即哲学家只有在他左右两边的筷子都可用时才能拿起筷子。

要编写解决方案代码，我们需要区分哲学家可能处于的三种状态。

  • 思考

  • 饥饿

  • 进食

示例

以下是使用监视器实现哲学家就餐问题的代码：

monitor DiningPhilosophers {
   enum {THINKING, HUNGRY, EATING} state[5];
   condition self[5];
   void pickup(int i) {
      state[i] = HUNGRY;
      test(i);
      if (state[i] != EATING) {
         self[i].wait();
      }
   }
   void putdown(int i) {
      state[i] = THINKING;
      test((i + 4) % 5);
      test((i + 1) % 5);
   }
   void test(int i) {
      if (state[(i + 4) % 5] != EATING &&
      state[i] == HUNGRY &&
      state[(i + 1) % 5] != EATING) {
         state[i] = EATING;
         self[i].signal();
      }
   }
   initialization code() {
      for(int i=0;i<5;i++)
      state[i] = THINKING;
   }
}
DiningPhilosophers dp;

在此实现中，筷子的分配由监视器 DiningPhilosophers 控制。在开始吃饭之前，每个哲学家都必须调用 pickup() 操作。这表示哲学家很饿，意味着进程想要使用资源。它还在 test() 中仅当哲学家的左邻和右邻没有吃饭时才将状态设置为 EATING。如果哲学家无法吃饭，则调用 wait() 操作。操作成功完成后，哲学家现在可以吃饭了。

记住这一点，哲学家现在调用 putdown() 操作。放下叉子后，它会检查它的邻居。如果他们很饿并且他们的两个邻居都没有在吃饭，那么调用 signal() 并让他们吃饭。

因此，哲学家必须同时调用 pickup() 和 putdown() 操作，这确保了没有两个邻居同时吃饭，从而实现了互斥。因此，它可以防止死锁。但是，有可能其中一个哲学家可能会饿死。

优点和缺点

哲学家就餐问题可以使用监视器和信号量来实现。监视器和信号量都是并发编程中使用的同步结构。但是，对于上述现象，使用监视器而不是信号量有一些优点和缺点。

优点

  • 易于使用 − 监视器比信号量更容易使用。通过将初始化代码封装在监视器中，调试相对容易。

  • 互斥 − 通过在哲学家就餐问题中实现监视器，实现了互斥。因此，它可以防止两个相邻的哲学家同时吃饭，从而防止死锁情况。

  • 条件变量 − 监视器提供条件变量，指示线程等待特定条件满足。

缺点

  • 性能 − 监视器需要对特定资源进行锁定，这可能会导致不必要的延迟。因此，性能可能会受到影响。

  • 灵活性 − 由于问题的特定同步要求，监视器可能不如信号量灵活。在更复杂的场景中，信号量由于其灵活性而更有可能适合。

结论

哲学家就餐问题是操作系统中可能出现的同步问题的示例。但是，通过使用监视器来实现问题的解决方案，可以在共享资源上实现互斥，从而防止死锁的发生。

监视器提供了一种内置的互斥机制，它一次只允许一个进程访问一个资源。这确保了在这种情况下，哲学家（进程）需要吃饭的叉子（共享资源）不会并发访问，从而避免了死锁情况。

总的来说，通过在哲学家就餐问题中使用监视器，可以防止潜在的同步问题。

更新于：2023年4月7日

9K+ 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告