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

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

Я пытаюсь реализовать семафоры, которые позволяют избежать состояния гонки, описанного в ошибке 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. При пробуждении уменьшите число ожидающих, выполните цикл и повторите попытку.

Ключевым изменением операции 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 начинает ожидание, увеличивает счетчик ожидания и ожидает фьютекс.
  4. Поток 1 выполняет успешное сравнение и замену, возвращается, не разбудив официанта.

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

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

c linux race-condition pthreads semaphore
person R.. GitHub STOP HELPING ICE    schedule 02.08.2011    source источник
comment
Не могли бы вы подробнее рассказать о 1.? Мне сложно понять, как вы хотите сделать это атомарно. Что-то вроде if value then do звучит так, что всегда будет разрыв, который нужно каким-то образом защитить.   -  person Jens Gustedt    schedule 02.08.2011
comment
Только пост является безопасным для асинхронных сигналов. Подождите, нет. Ожидание в обработчике сигнала в любом случае - довольно плохая идея, но с циклами повтора CAS * trywait (вероятно, можно было бы сделать безопасным (хотя это и не обязательно).   -  person R.. GitHub STOP HELPING ICE    schedule 02.08.2011
comment
В качестве примечания относительно: независимо от того, соответствует ли это поведение спецификации или нет, в спецификации POSIX указано, что можно безопасно уничтожить инициализированный семафор, на котором в настоящее время не заблокированы никакие потоки. и Эффект от последующего использования семафора sem не определен до тех пор, пока sem не будет повторно инициализирован другим вызовом sem_init (). Этот язык похож на язык mutex_destroy; мне кажется, что такое поведение действительно должно быть разрешено, хотя я вижу, что это может быть немного неясно для случая, когда сам семафор синхронизирует свое уничтожение ...   -  person bdonlan    schedule 02.08.2011
comment
Действительно, для мьютекса POSIX делает это очень ясным и даже имеет пример разблокировки, уничтожения и освобождения мьютекса, как только возвращается pthread_mutex_lock. К счастью, эту проблему для мьютексов немного легче решить, поскольку недопустимо, чтобы несколько потоков одновременно вызывали pthread_mutex_unlock (тогда как для нескольких потоков разрешено отправлять семафор, поскольку семафоры не имеют владельцев). На самом деле исправление довольно близко к тому, что я описал для семафоров, но мне кажется, легче установить его правильность ...   -  person R.. GitHub STOP HELPING ICE    schedule 02.08.2011

Ответы (1)


arrow_upward
3
arrow_downward

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

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

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

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

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

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

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

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

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

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

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

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

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

    • At libc init and thread startup, register these thread-specific structures, and save a pointer to them in TLS data
    • По почте примите меры для подавления ошибок при подсчете количества официантов. В случае возникновения неисправности не выполняйте пробуждение (пробуждение безвредно, если соответствующая память повторно используется для другой цели)

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

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

person bdonlan    schedule 02.08.2011
comment
+1 за интересные идеи. Конечно, я бы предпочел что-то портативное, работающее с существующими ядрами и не налагающее новых ограничений. :-) - person R.. GitHub STOP HELPING ICE; 02.08.2011
comment
@R, конечно, но я бы посоветовал использовать эти методы на платформах, на которых они применимы. В частности, x86 можно очень легко исправить с помощью LOCK CMPXCHG8B (обратите внимание, что 16B недоступен на некоторых очень ранних 64-битных процессорах) - person bdonlan; 02.08.2011
comment
В любом случае 16B никогда не понадобится. Единицы измерения, с которыми работает фьютекс, всегда являются 32-битными целыми числами, даже для 64-битных целей, поэтому 2 счетчика по-прежнему равны 8 байтам. - person R.. GitHub STOP HELPING ICE; 02.08.2011
comment
Я не уверен, зачем мне нужны системы для особых случаев, которые могут обеспечивать большое сравнение и замену (CMPXCHG8B). Вы думаете, что производительность должна быть значительно лучше? Я измеряю разницу в количестве циклов 170 и 196 для моего старого (с проблемой уничтожения) и нового кода для пары trywait / post, и я подозреваю, что решение CMPXCHG8B окажется где-то посередине. Это не большая разница. Конечно, есть случаи, требующие рассмотрения, но в них будет преобладать время системного вызова. - person R.. GitHub STOP HELPING ICE; 02.08.2011
comment
@R: Ах, достаточно справедливо. Я просто не совсем уверен, что я не пропустил какую-то тонкую гонку в предложенном вами алгоритме, но с CMPXCHG8B вы легко можете доказать его правильность. - person bdonlan; 02.08.2011
comment
Я согласен, что это было бы легко доказать. Более сложная часть состоит в том, что тогда у меня будет две версии кода, которые мне нужно будет подтвердить. :-П - person R.. GitHub STOP HELPING ICE; 02.08.2011