Почему pthread_cond_wait имеет ложные пробуждения?

Question

Чтобы процитировать man страницу:

При использовании условных переменных всегда существует логический предикат, включающий общие переменные, связанные с каждым условным ожиданием, которое имеет значение true, если поток должен продолжить. Могут возникнуть ложные пробуждения от функций pthread_cond_timedwait() или pthread_cond_wait(). Поскольку возврат из pthread_cond_timedwait() или pthread_cond_wait() ничего не подразумевает в значении этого предиката, предикат должен быть переоценен после такого возврата.

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

Почему pthread_cond_wait возвращаться с бешенством? Почему он не может гарантировать, что он проснется только тогда, когда на него правильно подали сигналы? Кто-нибудь может объяснить причину его ложного поведения?

Answer 1

Следующее объяснение дано Дэвидом Р. Бутенхофом в "Программирование с помощью потоков POSIX" (стр. 80):

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

В следующем обсуждении comp.programming.threads он расширяет концепцию дизайна:

Патрик Дойл написал: 
> В статье Том Пейн писал: 
>> Каз Кылхеку писал: 
>>: Это так, потому что реализации иногда не могут избежать вставки 
>>: эти ложные пробуждения; это может быть дорогостоящим, чтобы предотвратить их. 

>> Но почему? Почему это так сложно? Например, мы говорим о 
>> ситуации, когда время ожидания истекает, когда поступает сигнал? 

> Вы знаете, мне интересно, использовали ли разработчики pthreads такую ​​логику: 
> пользователи условных переменных должны все равно проверить условие при выходе, 
> поэтому мы не будем возлагать на них никакого дополнительного бремени, если позволим 
> ложные пробуждения; и так как это возможно, что позволяет ложным 
> пробуждения могут сделать реализацию быстрее, это может помочь, только если мы 
> Позволь им. 

> Возможно, они не имели в виду какую-то конкретную реализацию. 

Вы на самом деле совсем недалеко, за исключением того, что вы не продвинулись достаточно далеко. 

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

Мы следовали этому намерению с несколькими уровнями оправдания. Первое было 
"религиозное" использование цикла защищает приложение от собственного несовершенства 
практика кодирования. Во-вторых, абстрактно представить было несложно. 
машины и код реализации, который может использовать это требование для улучшения 
выполнение операций ожидания среднего состояния за счет оптимизации 
механизмы синхронизации. 
/ ------------------ [David.Buten... @ compaq.com] ------------------ \ 
| Компьютерная корпорация Compaq POSIX Thread Architect | 
| Моя книга: http://www.awl.com/cseng/titles/0-201-63392-2/     | 
\-----[ http://home.earthlink.net/~anneart/family/dave.html ]-----/ 

Answer 2

Есть по крайней мере две вещи, которые может означать "ложное пробуждение":

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

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

• Поток 1 только что удалил элемент из очереди и освободил мьютекс, и очередь теперь пуста. Поток делает все, что он делает с элементом, который он получил на некотором процессоре.
• Поток 2 пытается удалить элемент из очереди, но обнаруживает, что очередь пуста при проверке в мьютексе, вызывает pthread_cond_waitи блокирует вызов в ожидании сигнала / трансляции.
• Поток 3 получает мьютекс, вставляет новый элемент в очередь, уведомляет переменную условия и снимает блокировку.
• В ответ на уведомление от потока 3 запланирован запуск потока 2, который ожидал выполнения условия.
• Однако прежде чем потоку 2 удастся войти в ЦП и захватить блокировку очереди, поток 1 завершает свою текущую задачу и возвращается в очередь для дополнительной работы. Он получает блокировку очереди, проверяет предикат и обнаруживает, что в очереди есть работа. Он переходит в очередь на элемент, который был вставлен потоком 3, снимает блокировку и делает все, что делает с элементом, который был помещен в поток 3.
• Поток 2 теперь загружается в ЦП и получает блокировку, но когда он проверяет предикат, он обнаруживает, что очередь пуста. Поток 1 "украл" предмет, поэтому пробуждение кажется ложным. Поток 2 должен снова ждать состояния.

Так как вам уже всегда нужно проверять предикат в цикле, не имеет значения, могут ли базовые переменные условия иметь другие виды ложных пробуждений.

Answer 3

Раздел "Многократное пробуждение по сигналу условия" в pthread_cond_signal содержит пример реализации pthread_cond_wait и pthread_cond_signal, который включает в себя ложные пробуждения.

Answer 4

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

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

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

Answer 5

Я думаю, что основной причиной ложных пробуждений является.

EINTR Прерванный вызов функции (POSIX.1-2001); см. сигнал (7).

^{источник: https://man7.org/linux/man-pages/man3/errno.3.html}

В основном системный вызов, который вызывается, например, например,futex(2), может вернуться с . Обычно это происходит, если системный вызов, заблокированный в ядре, был прерван сигналом POSIX (см.signal(7)). См. «Каково обоснование EINTR?»на unix.stackexchange.com, почему (некоторые) операционные системы возвращаются, если системный вызов был прерван после того, как сигнал POSIX был доставлен и обработан потоком, выдающим системный вызов.

Я предполагаю, что существует потенциальное состояние гонки, когда низкоуровневый примитив операционной системы, используемый для реализации, например, возвращает . Реализацияpthread_cond_wait()не может просто повторно выполнить системный вызов, поскольку теперь условие может выполняться. Если состояние не оценивается повторно послеEINTR, то это может легко привести к тупиковой ситуации, когда приложение не будет продолжать работу.

Answer 6

Пример acm аналогичен «рисунку 30.9» в книге , где проблема в том, что планировщик запустит поток пробуждения после другого запланированного потребителя.

Но «также обрабатывается случай ложного пробуждения» в ostep threads-cv p14, где говорится, что это не совсем то же самое, что ложное пробуждение. Из определения ложного пробуждения « может вернуться более одного потока » не отражено в примере ACM (т. е. «Потоку 2 необходимо снова дождаться выполнения условия» подразумевает, что пробуждается только один поток), поэтому ostep думает, что это так. ни одного ложного пробуждения.

---

Подробности оman 3 pthread_cond_broadcastпример, который может дополнить ответ Цзинго Яо. Также см. мой комментарий выше в ответе Цзинго Яо.

ИМХО, этот пример реализации может быть предназначен только для представления, что кажется странным, поскольку оно будет продолжать работать после прерывания и cond->valueизменился вместо того, чтобы ждать.

Как говорится в ответе NPE, реализация выбрана намеренно для упрощения. ИМХО, это связано с учетом стиля Mesa , о котором также говорится в ostep threads-cvкниге OSTEP . «Стиль Меса» подразумевает использование whileперепроверить состояние после пробуждения, поэтому, возможно, это излишне , чтобы избежать ложных пробуждений внутри иpthread_cond_signal. «пользователи условных переменных в любом случае должны проверять условие при выходе » в ответе NPE также подразумеваетwhile()вне того, что рассматривается как одно из соглашений об использованииpthread_cond_wait.