сделать семафор удовлетворяет ограниченное ожидание - PullRequest
Новая
       5

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

7 голосов
/ 03 декабря 2010

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

1 Ответ

2 голосов
/ 30 апреля 2011

Ответ

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

Классическая реализация примитивов 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 имеет неограниченное время ожидания, даже, возможно, голодание, вызванное непрерывным входом новых процессов.

...