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

Question

В прошлом вопросе я спрашивал о реализации барьеров pthread без рас уничтожения:

Как можно разрушить барьеры, как только pthread_barrier_wait вернется?

и получен отМайкл Барр (Michael Burr) с идеальным решением для локальных барьеров процесса, но не для общих барьеров процесса.Позже мы проработали некоторые идеи, но так и не пришли к удовлетворительному выводу и даже не стали вдаваться в случаи сбоев ресурсов.

Возможно ли в Linux создать барьер, отвечающий этим условиям:

• Процесс с общим доступом (может быть создан в любой совместно используемой памяти).
• Безопасное удаление или удаление барьера из любого потока сразу после возврата из функции ожидания барьера.
• Невозможносбой из-за сбоя при распределении ресурсов.

Попытка Майкла решить общий процесс (см. связанный вопрос) имеет прискорбное свойство: во время ожидания должен быть выделен какой-то системный ресурс, то естьждать может потерпеть неудачу.И неясно, что может разумно делать вызывающий объект, когда ожидание барьера не удается, поскольку весь смысл барьера в том, что небезопасно продолжать работу, пока оставшиеся потоки N-1 не достигнут его ...

Ядро-Космическое решение может быть единственным выходом, но даже это сложно из-за возможности сигнала прервать ожидание без надежного способа его возобновить ...

Answer 1

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

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

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

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

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

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

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

Однако один из возможных способов работы - это расширение модели с ключом *1018* в NT API. В случае событий с ключами потоки освобождаются от блокировки попарно; если у вас есть «release» без «wait», вызов «release» блокирует «wait».

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

Answer 2

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

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

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

Answer 3

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

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

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 на ложь и N на количество потоков, которые ожидает барьер.

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

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

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