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

Question

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

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

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

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

Сообщение:

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

Подождите:

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

Шаг 2 после операции является небезопасным.

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

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

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

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

Теперь о попытке реального решения ...

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

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

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

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

Ожидание:

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

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

Post:

1. Считывание и сохранение значения семафора.
2. Считывание и сохранение числа официантов.
3. Определение нового значения семафора (-1 становится 1, в противном случае просто увеличивается).
4. Атомное сравнение и замена для обновления значения семафора.В случае ошибки перейдите к 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 начинает ожидание,увеличивает счетчик ожидания и ожидание futex.
4. Поток 1 выполняет успешное сравнение и обмен, возвращает без пробуждения официанта.

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

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

Answer 1

Прежде всего, позвольте мне привести два альтернативных подхода, которые вы, возможно, пожелаете рассмотреть.

• Подход № 1 (специфичный для X86, быстрый): CMPXCHG8B / CMPXCHG16B.

  Платформы x86 имеют атомную операцию сравнения и обмена с шириной двойного указателя.На 32-битном это 8 байтов;в 64-битной системе есть CMPXCHG16B, который атомарно сравнивает и обменивается полными 16 байтами данных.Используя это, вы можете атомарно поменять как счетчик ожидания, так и счетчик семафоров за одну операцию.futex может ожидать только одно поле размера указателя, но в этом случае это не должно быть серьезной проблемой.

• Подход № 2 (переносимый, ограниченный): количество упаковок.

  Если допустимо ограничение в 2 ^ 16 для счетчиков официантов и семафоров, просто упакуйте оба счетчика в одно 32-битное поле.

• Подход № 3 (переносимый, имеетнекоторые накладные расходы): используйте семафор в семафоре для защиты после гонки.

  Зарезервируйте 8 битов числа семафоров для блокировки после операций.Операция post увеличивает этот счетчик (блокируя, если он переполнится) одновременно с увеличением истинного счетчика семафоров.Затем он выполнит свою работу с полем официантов, а затем атомарно уменьшит счетчик блокировки.После уменьшения, если предыдущее значение было 255, разбудите всех официантов (хотя это вызывает громоподобное стадо, это должно быть крайне редко).

  После удаления получите блокировку 255 раз (вы можете увеличить более чем наодин в один шаг), блокировка при необходимости.Как только блокировка была получена 255 раз, вы знаете, что все записи завершены, и удалить блокировку безопасно.

  Недостаток: для публикаций теперь требуется два атомных обмена-сравнения, и максимальное количество семафоров равно 2^ 24-1.Кроме того, рекурсивный ввод обработчика асинхронного сигнала 255 раз приведет к взаимоблокировке.

Эти подходы проще, легче доказать правильность и, вероятно, быстрее.Однако их ограничения могут означать, что они неприемлемы для вашего случая (однако подход CMPXCHG8B должен хорошо работать на x86).И вот еще один:

• Подход № 4 (своего рода независимый от арки; сложный; быстрый): Изменить ядро ​​

  Один из вариантов здесь будет изменить ядро ​​наразрешить безопасный способ чтения поля официанта с минимальными издержками, не приводя к segfault в случае освобождения памяти.Например, вы можете добавить системный вызов, который регистрирует специфичную для потока структуру данных;на этой странице данных, относящейся к потоку, у вас может быть «адрес перехода обработчика ошибок».В случае, если программа segfaults, если адрес перехода отличен от нуля, ядро ​​просто переходит туда вместо вызова SIGSEGV.С другой стороны, у вас мог бы быть подобный механизм, чтобы просто подавить некорректную инструкцию.

  Теперь все, что вам нужно сделать, это:

  • При запуске libc init и thread зарегистрируйте эти специфичные для потокаструктуры и сохраните указатель на них в данных TLS
  • В посте организуйте устранение неисправностей на счетчике официантов.Если происходит сбой, не выполняйте пробуждение (пробуждение безвредно, если рассматриваемая память используется повторно для другой цели)

  И вот вы - быстрый алгоритм, ноВы также получаете защиту от гонки удаления.Но для этого нужно взломать обработчики ядра segv.Возможно, стоит взглянуть на SEH в Windows;подобный механизм будет очень хорошо работать здесь.

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