semaphore - 做信号量满足有界等待

Question

信号量是满足有限等待还是只是为了提供互斥？

Answer 1

答案

正如您将在下面看到的那样，理论上它可能会打破有界等待条件。实际上，它在很大程度上取决于使用哪种调度算法。
wait()的经典实现和 signal()原语是这样的:

//primitive
wait(semaphore* S)
{
    S->value--;
    if (S->value < 0)
    {
        add this process to S->list;
        block();
    }
}

//primitive
signal(semaphore* S)
{
    S->value++;
    if (S->value <= 0)
    {
        remove a process P from S->list;
        wakeup(P);
    }
}

当进程调用 wait()并且未通过“if”测试，它会将自己放入等待列表中。如果在同一个信号量上阻塞了多个进程，它们都会被放入这个列表中(或者它们以某种方式链接在一起，就像你想象的那样)。当另一个进程离开临界区并调用signal()时，等待列表中的一个进程将被唤醒，准备再次竞争CPU。但是，由调度程序决定从等待列表中选择哪个进程。例如，如果以 LIFO(后进先出)方式实现调度，则某些进程可能会饿死。

示例

T1: thread 1 calls wait(), enters critical section
T2: thread 2 calls wait(), blocked in waiting list
T3: thread 3 calls wait(), blocked in waiting list
T4: thread 1 leaves critical section, calls signal()
T5: scheduler wakes up thread 3
T6: thread 3 enters critical section
T7: thread 4 calls wait(), blocked in waiting list
T8: thread 3 leaves critical section, calls signal()
T9: scheduler wakes up thread 4
..

如您所见，尽管您正确地实现/使用了信号量，但线程 2 具有无限的等待时间，甚至可能由于不断进入新进程而导致饥饿。