时间戳

首页 > 解决方案 > 信号量小书中的无饥饿互斥锁

multithreading - 信号量小书中的无饥饿互斥锁

问题描述

背景：

Allen B. Downey 的 The Little Book of Semaphores 讨论了防止线程饥饿所需的假设。

他指出调度程序需要保证以下内容：

属性 2：如果一个线程准备好运行，那么它等待运行的时间是有限的。

弱信号量保证：

属性 3：如果线程执行信号时有线程在信号量上等待，则必须唤醒等待的线程之一。

但是，他指出，即使具有这些属性，以下代码在运行 3 个或更多线程（线程 A、B、C）时也会导致饥饿：

while True: 
    mutex.wait()
    # critical section 
    mutex.signal()

论点是，如果 A 先执行，然后唤醒 B，A 可以在 B 释放它之前再次等待互斥锁。此时，可以再次唤醒 A 重新获取互斥体并与 B 重复此循环。C 将被饿死。

问题：

属性 2 不能保证 C 必须在有限的时间内被调度程序唤醒吗？如果是这样，那么线程 C 就不会被饿死。即使弱信号量不能保证线程C会被唤醒，调度器不应该运行它吗？

标签： multithreadingconcurrencymutexsemaphore

解决方案

我想了想，意识到属性 2是保证处于 RUNNABLE 状态的线程将在有限的时间内被调度。

书中的论点指出线程 C 永远不会进入 RUNNABLE 状态，因此属性 2 和 3 不能保证不会出现饥饿。

推荐阅读