Как работают бинарные семафоры?

Я изучал бинарные семафоры, когда возник следующий вопрос:

Предположим, что есть 3 параллельных процесса и 3 бинарных семафора... Семафоры инициализируются как S0=1, S1=0, S2=0. Процессы имеют следующий код:

Process P0:                   Process P1:                       Process P2:

while (true){                 wait(S1);                         wait(S2);
wait (S0);                    release (S0);                     release(S0);
print '0';
release (S1);
release (S2);
}

Теперь вопрос в том, сколько раз процесс будет печатать 0 ?

Позвольте мне объяснить, как я это решал... предположим, что первые три оператора трех процессов выполняются одновременно! т. е. оператор while процесса p0, ожидание (S1) процесса p1 и ожидание (S2) процесса P2. и P2 будут заблокированы. Затем будет выполнено ожидание (S0) процесса P0. Когда это происходит, значение S0 становится равным 0, а процесс P0 переходит в заблокированное состояние, в результате чего все процессы будут заблокированы и заблокированы!! Но, к сожалению, это не ответ. . Подскажите, пожалуйста, где я ошибаюсь и как продвигается решение? :|

ИЗМЕНИТЬ:

Я ошибся в своем подходе к бинарным семафорам... они могут принимать только 0 и 1!


operating-system concurrency semaphore critical-section
person Chandeep    schedule 17.10.2012    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Хорошо .. так вот я отвечаю на свой вопрос :P ..

Решение происходит следующим образом:

  1. Только процесс P0 может выполняться первым. Это связано с тем, что семафор, используемый процессом P0, т.е. S0, имеет начальное значение 1. Теперь, когда P0 вызывает ожидание S0, значение S0 становится равным 0, подразумевая, что S0 был занят P0. Что касается процессов P1 и P2, когда они вызывают ожидание на S1 и S2 соответственно, они не могут продолжать работу, потому что семафоры уже инициализированы как занятые, т.е. 0, поэтому им приходится ждать, пока S1 и S2 будут освобождены!

  2. P0 выполняется первым и печатает 0. Теперь следующие операторы освобождают S1 и S2! Когда S1 освобождается, ожидание процесса P1 заканчивается, так как значение S1 увеличивается на 1 и помечается как неиспользуемое. P1 берет S1 и делает S1 принятым. То же самое и с процессом P2.

  3. Теперь only one of P1 or P2 can execute, because either of them can be in the critical section at a given time.. Предположим, выполняется P2. Он освобождает S0 и завершает работу.

  4. Пусть P1 выполнится следующим. P1 запускает Освобождает S0 и завершает работу.

  5. Now only P0 can execute because its in a while loop whose condition is set to true, which makes it to run always. P0 выполняет печать 0 во второй раз и освобождает S1 и S2. Но P1 и P2 уже завершены, поэтому P0 вечно ждет выпуска S0.

Вот второе решение, которое печатает 0 три раза:

  1. P0 запускается, печатает 0 и отпускает S1 и S2.

  2. Пусть P2 выполняется. P2 запускается, освобождает S0 и завершает работу. После этого могут выполняться только P0 или P1.

  3. Пусть P0 выполняется. Печатает 0 во второй раз и освобождает S1 и S2. На данный момент только P1 может выполняться.

  4. Запускается P1, отпускает S0, P1 завершается. На данный момент только P0 может выполняться, потому что он находится в цикле while, условие которого установлено в true!

  5. Запускается P0, печатает 0 в третий раз и освобождает S1 и S2. Затем он ждет, пока кто-нибудь не выпустит S0, чего никогда не происходит.

Таким образом, ответ становится ровно дважды или ровно трижды, что также можно сказать «atleast twice»!

Пожалуйста, скажите мне, если я где-то ошибаюсь!!

person Chandeep    schedule 18.10.2012