семафоры удовлетворяют ограниченному ожиданию

Ответить

Теоретически это может нарушить ограниченное условие ожидания, как вы увидите ниже. На практике это сильно зависит от того, какой алгоритм планирования используется.

Классическая реализация примитивов 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() и не проходит тест «если», он ставит себя в список ожидания. Если на одном и том же семафоре заблокировано более одного процесса, все они помещаются в этот список (или они каким-то образом связаны друг с другом, как вы можете себе представить). Когда другой процесс покидает критическую секцию и вызывает signal(), один процесс в списке ожидания будет выбран для пробуждения, готовый снова конкурировать за ЦП. Однако именно планировщик решает, какой процесс выбрать из списка ожидания. Например, если планирование реализовано по принципу 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 имеет неограниченное время ожидания, даже, возможно, голодание, вызванное постоянным входом новых процессов.