解决哲学家用餐问题中的饥饿现象：使用反向信号量

• 下载演示项目 - 8.62 KB
• 下载源代码 - 22.17 KB

引言

哲学家就餐问题是一个非常古老且众所周知的问题，最初由 Edgar Dijkstra 提出。这个问题是计算中并发的一个例子。有关该问题本身的更多信息，可以在 Wikipedia 上找到。 Dr. Sai 在同一网站上也有出色的文章：Dr. Sai。

问题定义

哲学家就餐问题有许多解决方案，但其中一些解决方案存在一个问题，称为饥饿。

让我们定义它；当某个哲学家没有机会定期进食时，就会发生饥饿，可能会出现一个哲学家过度进食，最终导致另一个哲学家饥饿的情况，即使这解决了死锁问题。 Dr.Sai 撰写的文章中也发生了类似的事情。

解决方案

本文中提出的解决方案使用了所谓的反向信号量。
信号量是一个同步对象，当计数大于零时被发出信号，当计数为零时未发出信号。

可能存在您希望相反的情况，就像在这种情况下，我们试图解决哲学家就餐问题一样。

我有一个名为 CInverseSemaphore 的类，它实现了反向 信号量 并且可以令人满意地解决这个问题。

正如反向 信号量 类的类图所示，我们正在使用一个 临界区 和一个 事件，这两个都由构造函数初始化，并在析构函数中释放。

构造函数用于初始化 信号量 的最大计数 (m_MaxCount)。 UnGuard 函数用于递减计数，类似于 ReleaseSemaphore，但区别在于一旦计数达到零，事件就会发出信号，并且 WaitForSingleObject 将在 Event 句柄上等待，该句柄由该类的 GetHandle 函数返回。

逻辑

有五个线程，每个哲学家一个线程，还有一个 监视器 线程。
在 CInverseSemaphore 对象 (invsema) 中是一个全局变量，因此将首先初始化。计数设置为 2。

进入标准

每个哲学家都在等待一个 事件，并且此 事件 由 监视器 线程设置。
监视器 线程充当调度程序，它调度下一组哲学家开始进食。

//Entry Criteria
dwEvent =WaitForSingleObject(hndEvent[4],INFINITE);

退出标准

哲学家线程释放它所持有的餐具，并调用 UnGuard 函数，该函数设置 事件 对象，该对象由 监视器 线程使用。下面的代码讲述了同样的故事……

// Exit Criteria
EnterCriticalSection(&cs);
{
    sp[1] = 1;
    sp[0] = 1;

    invsema.UnGuard();
}
LeaveCriticalSection(&cs);

一旦 事件 对象在 监视器 线程中发出信号，顺便说一下，这仅发生在两个线程（或哲学家）调用 UnGuard 函数时。

监视器线程

监视器 线程等待 InverseSempahore 事件，该事件如上所述在退出标准中设置。

// Monitor waiting on the event found in inverse semaphore class
dwEvent = WaitForSingleObject(invsema.GetHandle(),INFINITE);

invsema.GetHandle() 函数返回 事件 句柄供 监视器 等待。

结论

这带我们到了文章的结尾。希望您觉得它有用。请让我知道您的评论/想法/建议，这些可以用来更新本文。

历史

• 2008年6月2日：最初的帖子