Семафор без разрушения / отмены состояния гонки

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

Я пытаюсь реализовать семафоры, которые позволяют избежать состояния гонки, описанного в ошибке glibc номер 12674:

http: //sourceware.org/bugzilla/show_bug.cgi?id=12674

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

Сообщение:

1. Значение семафора атомарного приращения
2. Проверить счетчик официантов. Если оно не равно нулю, выполнить пробуждение фьютекса.

Ждать:

1. Атомарное декремент-при положительном значении семафора (и возврат в случае успеха).
2. Если это не удалось, увеличьте число ожидающих и выполните ожидание фьютекса.
3. При пробуждении, декремент ожидания, цикл и повтор.

Шаг 2 пост-операции небезопасен.

Есть две очевидные реализации, которые позволяют избежать этой проблемы, но обе имеют серьезные проблемы:

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

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

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

А теперь перейдем к попытке реального решения ...

Здесь следует отметить, что есть несколько других требований, которые усложняют реальную реализацию. Пост-операция должна быть асинхронно-сигнально-безопасной (поэтому она в основном не может использовать блокировки), а операция ожидания требуется, чтобы разрешить прерывание сигналами, тайм-аутом или отменой потока. На практике это означает, что пост-операция должна иметь возможность безопасно «отменить» любые изменения, которые она вносит в состояние семафора. Я замалчил такие вопросы, потому что мой подход, кажется, не имеет с ними проблем, но они делают некоторые очевидные изменения / решения невозможными, поэтому любой, кто предлагает новые подходы в качестве ответа, должен знать об этих проблемах ...

У меня есть предлагаемое решение, но я не уверен, будет ли оно связано с новыми (и, возможно, худшими) условиями гонки. Я опишу это здесь и надеюсь, что некоторые боги параллелизма (или, по крайней мере, полубоги) проявят любезность проверить его на правильность.

Мой подход представляет собой что-то вроде гибрида второго «плохого» решения, которое я описал выше, и оригинальный подход (с гонкой, описанной в отчете об ошибке glibc). Он использует как счетчик официантов, так и флаг официанта (-1 хранится в значении семафора).

Ключевое изменение операции ожидания состоит в том, что он сохраняет -1 вместо 0 в значении семафора всякий раз, когда есть официанты (уже существующие официанты считать или себя как нового официанта).

Подождите:

1. Прочтите значение семафора.
2. Если значение положительное, определите новое значение семафора следующим образом: если значение равно 1 и есть ожидающие, новое значение должно быть -1; в противном случае просто уменьшите старое значение. Используйте функцию сравнения и замены, чтобы обновить значение, и вернуть успех в случае успеха.
3. В противном случае увеличьте число ожидающих, атомарно замените значение 0 на -1 и выполните ожидание фьютекса с -1 в качестве значения.
4. ] При пробуждении, уменьшите число ожидающих, цикл и повтор.

Ключевое изменение в пост-операции заключается в том, что она выполняет чтение счетчика официантов до увеличения значения семафора, а не после:

Сообщение:

1. Прочитать и сохранить значение семафора.
2. Прочитать и сохранить счетчик официантов.
3. Определить новое значение семафора (-1 становится 1, иначе просто увеличивается).
4. Атомарное сравнение и замена для обновления значения семафора. В случае ошибки goto 1.
5. Если сохраненное количество официантов было ненулевым или значение семафора было -1, выполнить пробуждение фьютекса.

Сравнение и замена на шаге 4 обеспечивает некоторую безопасность, что счет официантов все еще правильный , но все еще существует гонка ABA - между шагами 1 и 4 возможно, что другие потоки выполняют операции ожидания и публикации, которые оставляют значение семафора таким же, как его начальное значение.

При поиске случаев, когда этот алгоритм может не пробудиться официанты, нам нужно рассматривать только случаи, когда начальное считывание счетчика официантов равно 0, а считанное значение семафора не равно -1. Кроме того, если значение семафора положительное и нет уже существующих официантов, текущий пост не несет ответственности за какие-либо пробуждения, поэтому этот случай также не интересен. Нам осталось изучить случаи, когда операция ожидания начинается с нулевого значения семафора и нулевого счетчика ожидания. В этой ситуации, чтобы не иметь состояния гонки, любое событие, которое происходит между шагами 2 и 4, которое приводит к появлению новых ожидающих, должно изменить значение семафора, так что сравнение и замена на шаге 4 не удастся. Очевидно, что любой отдельный промежуточный пост или ожидание изменит значение семафора (на 1 или -1, соответственно), поэтому проблема, в частности, представляет собой последовательность операций, которые приводят к значению семафора, равному 0, но присутствию официантов.

Я считаю, что этого не может произойти из-за процедуры, выполняемой в операции ожидания, но я не убедил себя на 100%.

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

Ошибка 1: Использование чистого счетчика ожидания, отсутствие флага -1 в значении семафора. Тривиальная гонка выглядит так:

1. Значение семафора начинается с 0
2. Поток 1 начинает публикацию, считывает значение семафора 0 и счетчик ожидания 0.
3. Поток 2 начинает ожидание, увеличивает счетчик ожидания и ожидает фьютекс.
4. Поток 1 выполняет успешное сравнение и замену, возвращается, не разбудив официанта.

Ошибка 2: использование счетчика официантов и установка новых официантов значения семафора на -1, но просто уменьшение значения семафора при успешном ожидании (без установки его на - 1, если другие потоки все еще ждут):

1. Значение семафора начинается с 0
2. Поток 1 начинает публикацию, считывает значение семафора 0 и счетчик ожидания 0.
3. Потоки 2 и 3 ждут, увеличивая счетчик ожидания и ожидание фьютекса.
4. Поток 4 сообщений, установка значения семафора на 1.
5. Поток 2 пробуждает и уменьшает значение семафора до 0, счетчик ожидания до 1.
6. Поток 1 выполняет успешное сравнение и замену, возвращается без пробуждения потока 3.