共享内存并发算法与互斥锁/信号量之间的关系

Question

我想弄清楚基于共享内存的并发算法（Peterson's/Bakery）与使用信号量和互斥锁之间的关系。

在第一种情况下，我们有一个没有操作系统干预的系统，进程可以使用共享内存和繁忙的等待来同步自己。

在第二种情况下，OS为进程/线程提供了阻塞能力，而不必忙于等待。

除了信号量之外，我们是否还想过使用共享内存（以确保公平性/缺乏饥饿），还是操作系统提供了更好的方法来实现这一点？ （我想知道一般的概念，但特定于POSIX/Win32/JAVA线程的答案也很有趣）。

非常感谢！

Answer 1

我想不出任何情况下，你真正想要的是忙碌的等待。繁忙的等待只消耗处理器时间而没有任何实现。这并不是说“忙等待”算法没有用（它们是），但“忙等待”部分不是所需的属性，它只是是所需的属性的必要结果。

Peterson的锁定算法和Lamport的面包房算法基本上只是互斥概念的实现。操作系统设施提供了相同概念的实现，但具有不同的折衷。

互斥体的“理想”实现将具有“零开销”---如果获取互斥锁上的锁并不需要任何时间，如果当前不拥有它，等待的线程会唤醒先前的所有者释放了锁，同时，等待的线程不会消耗任何处理器时间。

“忙等待”或“自旋锁定”算法会交换等待线程使用的处理器时间，以缩短唤醒时间。如果线程当前是在一个处理器上进行调度的，则繁忙服务器将以与处理器传输获取锁和同步线程所需的数据一样快的速度唤醒，但在等待时它将占用其处理器时间的最大分配。如果线程数量超过了可用处理器的数量，那么从当前拥有该互斥量的线程中很可能需要时间，从而使等待时间更长。但是，在某些情况下，解锁和锁定之间的低延迟值得进行折衷。

另一方面，使用OS设施使等待线程进入睡眠的“阻塞”互斥量具有不同的折衷。在这种情况下，解锁互斥锁和获取它的等待线程之间的时间可能非常长，可能比忙等待算法大几百倍。好处是等待线程在等待时确实不消耗处理器时间，因此操作系统可以在线程正在等待时安排其他工作。这因此可以潜在地减少整体等待时间，并且增加系统的整体吞吐量。

一些互斥实现使用忙等待和阻塞的组合：它们忙等待很短的时间，然后在短时间内无法获取锁时切换到阻塞状态。如果锁在线程开始等待后不久就释放，则具有快速唤醒的优点，而如果线程必须等待很长时间，则不消耗处理器时间。它还具有处理器短暂等待的高处理器使用率和长时间等待的缓慢唤醒的缺点。