Можно ли реализовать в Linux правильный отказоустойчивый общий барьер процессов?

Это невозможно с Linux futex API, и я думаю, что это тоже можно доказать.

По сути, у нас есть сценарий, в котором N процессов должны быть надежно разбужены одним последним процессом, и, кроме того, ни один процесс не может касаться какой-либо общей памяти после окончательного пробуждения (поскольку она может быть уничтожена или повторно использована асинхронно). Хотя мы можем достаточно легко пробудить все процессы, фундаментальное состояние гонки находится между пробуждением и ожиданием; если мы вызовем пробуждение перед ожиданием, отставший никогда не проснется.

Обычное решение для чего-то подобного состоит в том, чтобы отставший проверял переменную состояния атомарно с ожиданием; это позволяет вообще не спать, если пробуждение уже произошло. Однако здесь мы этого сделать не можем — как только пробуждение становится возможным, трогать общую память небезопасно!

Еще один подход состоит в том, чтобы фактически проверить, все ли процессы уже перешли в спящий режим. Однако это невозможно с API фьютекса Linux; единственным показателем количества ожидающих является возвращаемое значение FUTEX_WAKE; если он возвращает меньшее количество официантов, чем вы ожидали, вы знаете, что некоторые из них еще не спали. Однако, даже если мы обнаружим, что разбудили недостаточное количество официантов, уже слишком поздно что-либо предпринимать — один из проснувшихся процессов, возможно, уже разрушил барьер!

Так что, к сожалению, этот тип примитива, который можно немедленно уничтожить, нельзя создать с помощью API фьютекса Linux.

Обратите внимание, что в конкретном случае с одним официантом, одним бодрствующим, может быть возможно обойти проблему; если FUTEX_WAKE возвращает ноль, мы знаем, что никто еще не проснулся, поэтому у вас есть шанс восстановиться. Однако превратить это в эффективный алгоритм довольно сложно.

Сложно добавить надежное расширение к модели фьютекса, которое исправило бы это. Основная проблема заключается в том, что нам нужно знать, когда N потоков успешно вошли в режим ожидания, и атомарно пробудить их все. Однако любой из этих потоков может выйти из ожидания для запуска обработчика сигнала в любое время — действительно, поток пробуждения также может выйти из ожидания для обработчиков сигналов.

Однако одним из возможных способов является расширение модели ключевого события в NT API. При событиях с ключом потоки освобождаются от блокировки парами; если у вас есть «релиз» без «ожидания», вызов «релиз» блокируется для «ожидания».

Этого самого по себе недостаточно из-за проблем с обработчиками сигналов; однако, если мы позволим вызову 'release' указать количество потоков, которые должны быть разбужены атомарно, это сработает. У вас просто есть каждый поток в барьере, уменьшающий счетчик, а затем «ждите» события с ключом по этому адресу. Последний поток "освобождает" N - 1 поток. Ядро не позволяет обрабатывать какие-либо события пробуждения до тех пор, пока все потоки N-1 не перейдут в это состояние события с ключом; если какой-либо поток покидает вызов фьютекса из-за сигналов (включая освобождающий поток), это вообще предотвращает любые пробуждения, пока все потоки не вернутся.

После долгого обсуждения с bdonlan в чате SO я думаю, что нашел решение. По сути, мы разбиваем проблему на две проблемы самосинхронизированного освобождения памяти: операцию уничтожения и размаппинг.

Обработка разрушения проста: просто заставьте функцию pthread_barrier_destroy ждать, пока все официанты перестанут проверять барьер. Это можно сделать с помощью счетчика использования в барьере, атомарно увеличивающегося/уменьшающегося при входе/выходе в функцию ожидания, и заставляя функцию уничтожения вращаться, ожидая, когда счетчик достигнет нуля. (Здесь также можно использовать фьютекс, а не просто вращение, если вы вставите флаг ожидания в старший бит счетчика использования или что-то подобное.)

Обработка отмены сопоставления также проста, но нелокальна: убедитесь, что munmap или mmap с флагом MAP_FIXED не может произойти, пока ожидающие барьера находятся в процессе выхода, добавив блокировку в оболочки системных вызовов. Для этого требуется специальный вид блокировки чтения-записи. Последний ожидающий, достигший барьера, должен захватить блокировку чтения на munmap rw-lock, которая будет освобождена, когда последний ожидающий выйдет (когда уменьшение счетчика пользователей приводит к счетчику, равному 0). munmap и mmap можно сделать реентерабельными (как могут ожидать некоторые программы, даже если POSIX этого не требует), сделав блокировку записи рекурсивной. На самом деле, тип блокировки, в котором читатели и писатели полностью симметричны, и каждый тип блокировки исключает блокировку противоположного типа, но не того же типа, должен работать лучше всего.

Ну, я думаю, что я могу сделать это с неуклюжим подходом...

Пусть «барьер» будет собственным процессом, прослушивающим сокет. Реализуйте барьер_ожидание как:

open connection to barrier process
send message telling barrier process I am waiting
block in read() waiting for reply

Как только N потоков находятся в ожидании, барьерный процесс сообщает им всем о продолжении. Затем каждый официант закрывает свое соединение с барьерным процессом и продолжает работу.

Реализуйте барьер_дестрой как:

open connection to barrier process
send message telling barrier process to go away
close connection

Как только все соединения закрыты и процессу барьера было приказано прекратить работу, он завершается.

[Редактировать: конечно, это выделяет и уничтожает сокет как часть операций ожидания и освобождения. Но я думаю, что вы можете реализовать тот же протокол и без этого; увидеть ниже.]

Первый вопрос: действительно ли этот протокол работает? Я думаю, что это так, но, возможно, я не понимаю требований.

Второй вопрос: если это работает, можно ли это смоделировать без накладных расходов на дополнительный процесс?

Я считаю, что ответ "да". Вы можете сделать так, чтобы каждый поток «взял на себя роль» барьерного процесса в соответствующее время. Вам просто нужен главный мьютекс, удерживаемый тем потоком, который в настоящее время «берет на себя роль» барьерного процесса. Детали, детали... Итак, барьер_ожидание может выглядеть так:

lock(master_mutex);
++waiter_count;
if (waiter_count < N)
    cond_wait(master_condition_variable, master_mutex);
else
    cond_broadcast(master_condition_variable);
--waiter_count;
bool do_release = time_to_die && waiter_count == 0;
unlock(master_mutex);
if (do_release)
    release_resources();

Здесь master_mutex (мьютекс), master_condition_variable (переменная условия), waiter_count (целое число без знака), N (другое целое число без знака) и time_to_die (логическое значение) — все они являются общим состоянием, выделяемым и инициализируемым барьером_инициализации. waiter_count инициализируется нулем, time_to_die — значением false, а N — количеством потоков, которых ожидает барьер.

Тогда барьер_дестрой будет:

lock(master_mutex);
time_to_die = true;
bool do_release = waiter_count == 0;
unlock(master_mutex);
if (do_release)
    release_resources();

Не уверен во всех деталях, касающихся обработки сигнала и т. д. Но основная идея «последний выключает свет», я думаю, работоспособна.