маленькая книга семафоров

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

/* rendezvous code */
mutex.wait()
count++;
mutex_signal()
if(count==n)
            sem.signal()
sem.wait()
sem.signal()

mutex.wait()
          count--;
mutex.signal()

if(count==0)
         sem.wait()

Я знаю, что два процесса могут достичь случая, когда оба видят одно и то же значение счетчика (может быть 0 или n). Благодаря этому два или более сигналов могут быть отправлены одновременно. Как может быть тупик в последнем тесте. Кажется, я этого не понимаю.
Это схема семафора типа турникета, и автор на самом деле думает, что это турникет, но это семафор, и он должен работать без взаимоблокировок. Скажите, пожалуйста, как в этом коде есть взаимоблокировка!


multithreading semaphore thread-synchronization
person aasthetic    schedule 16.02.2011    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Я попытаюсь объяснить, как я это вижу.

Все потоки, кроме последнего, придут и будут ждать первого sem.wait(). Как только прибудет последний поток, он вызовет sem.signal() (потому что count==n), что позволит продолжить выполнение одного из ожидающих потоков (скажем, T1). Затем T1, в свою очередь, выполнит sem.signal(), что позволит продолжить работу другого потока. Это что-то вроде цепной реакции. Обратите внимание, что последний проходящий поток также подаст сигнал, который сделает значение семафора равным 1. Теперь, если два потока придут и увидят, что count == 0, они попытаются выполнить sem.wait(). Но поскольку значение семафора равно 1, один поток не сможет пройти, что приведет к взаимоблокировке.

person Can't Tell    schedule 16.02.2011
comment
Но даже если один поток прибывает в точку count==0 , он также будет ждать. Следовательно, все процессы все равно будут ждать в этой точке. Приходят два потока или один, эти потоки не смогут пройти. - person aasthetic; 20.02.2011
comment
Уверены ли вы? Потому что, как я уже упоминал, последний проходящий поток также подаст сигнал, который сделает значение семафора равным 1. ТАК, если один поток достигает count==0, он сможет выполнить sem.wait() и передать эту точку. - person Can't Tell; 23.02.2011

arrow_upward
1
arrow_downward

Утверждения «if» также должны находиться внутри критических разделов, обозначенных семафором «mutex», в противном случае условия гонки могут привести к взаимоблокировке.

То есть правильный код

/* rendezvous code */
mutex.wait()
count++;
if(count==n)
        sem.signal()
mutex.signal()

sem.wait()
sem.signal()

mutex.wait()
      count--;
if(count==0)
     sem.wait()
mutex.signal()
person Vasilis    schedule 19.10.2015