Модификация "Реализация N-барьера процесса с использованием семафоров"

Question

В последнее время я вижу эту проблему, которая очень похожа на проблему Первого читателя / писателя.

Реализация N-процессного барьера с использованием семафоров

Я пытаюсь изменить его, чтобы убедиться, что он может быть повторно использован и работает правильно.

n = the number of threads
count = 0
mutex = Semaphore(1)
barrier = Semaphore(0)


mutex.wait()
count = count + 1
if (count == n){ barrier.signal()}
mutex.signal()

barrier.wait()

mutex.wait()
count=count-1
barrier.signal()
if(count==0){ barrier.wait()}
mutex.signal()

Это правильно?

Мне интересно, существуют ли какие-то ошибки, которые я не обнаружил.

Answer 1

Ваш псевдокод правильно возвращает барьер обратно в исходное состояние. Незначительное предложение: заменить

barrier.signal()
if(count==0){ barrier.wait()}

с ИМХО более читабельным

if(count!=0){ barrier.signal()} //if anyone left pending barrier, release it

Однако на пути могут быть подводные камни, барьер используется повторно. Описанный барьер имеет два состояния:

1. Остановите каждый поток, пока все они не будут в ожидании.
2. Возобновите каждый поток, пока все они не будут запущены

Не существует защиты от их смешивания: некоторые потоки возобновляются, а другие уже достигли первой стадии. Например, у вас есть несколько потоков, которые что-то делают, а затем синхронизируются на барьере. Каждое тело потока будет:

while (!exit_condition) {
  do_some_stuff();
  pend_barrier(); // implementation from current question
}

Программист ожидает, что количество звонков для do_some_stuff() будет одинаковым для всех потоков. Что может (или не может) произойти в зависимости от времени: первая нить, выпущенная из барьера, заканчивается do_some_stuff() расчеты до того, как все потоки покинули барьер, поэтому он снова вошел в ожидание во второй раз. В результате он будет освобожден вместе с другими потоками в текущей итерации освобождения барьера и получит (как минимум) еще один вызов do_some_stuff(),