实现互斥确保有界等待

Question

这是我遇到的一个面试问题，我不知道如何回答。

首先什么是一个有界的等待互斥体，你能给我一些互斥体的例子来确保有限的等待并且不能确保有界的等待吗？

其次，我不知道如何实现它，因为它似乎互斥是操作系统的内置功能。

你会如何回答这个面试问题？我可以用什么样的原子操作来实现互斥体，以及如何实现？

Answer 1

你当然可以在你的操作系统永远不会超时的互斥量上实现超时的互斥量。使用操作系统提供的互斥锁来管理对自己计数器的访问，保证始终快速释放它。

重复
...在柜台
获得OS互斥锁...检查计数器，看看> 0
......如果大于0，递减，发布OS互斥体，回报超时互斥已经获取了柜台

...发布OS互斥锁...检查是否超时
......如果超时，返回超时互斥超时
...睡一段时间
结束重复

当然，POSIX互斥锁有一个trylock函数，它使得等待循环变得微不足道。

忙碌等待当然是浪费CPU的能力。例如，更有效的实现是可能的，POSIX具有条件变量。

Answer 2

似乎有两种“有限等待”的用法。 One usage seems to be a simple time-based meaning：

任何特定进程进入其关键部分的等待时间都有限制。

Another usage seems to be a thread-count meaning：

请求进入临界段应该只需要等待其他进程进入和离开临界区的有限数量的一种方法。

---

不幸的是，我不知道如何真正回答这个问题。它似乎依赖于OS原语。也许他们正在寻找类似Peterson's solution的东西。