Гарантированы ли ложные пробуждения?
От: DTF  
Дата: 20.07.19 15:38
Оценка: -1
Коллеги, добрый вечер.

Я делаю многопоточную очередь на основе односвязного списка с фиктивным последним элементом с отдельными мьютексами для головы и хвоста.
Если очередь пуста, то head_ и tail_ равны и указывают на фиктивный элемент.
Собственно, это практически та же очередь, что описывается в c++ concurrency in action, только упрощенная (меньше методов, не забочусь об исключениях).

Полный код: https://pastebin.com/cBKZeh55

Мне кажется, что в этой очереди (и, соответственно, в той, которая описана в CiA) есть баг.

А именно, пусть у нас один поток-писатель и один поток-читатель.
Поток-читатель в методе wait_pop проверяет условие пустоты очереди (head_ == get_tail()), видит, что она пуста, и готовится ожидать на условной переменной.
Но планировщик прерывает его до начала ожидания и передает управление потоку-писателю.

Писатель вызывает push, который полностью отрабатывает. В частности, вызывается cond_var_.notify_one().

Т.е. уведомление посылается до того, как читатель начал ждать.

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

В принципе, если произойдет ложное пробуждение, то читатель увидит новые данные.


Итого, вопросы:
Гарантируется ли, что ложные пробуждения иногда происходят? Если да, то как часто?
А если нет, то почему в столь популярной книге столько времени живет очевидная ошибка?
Или в книге нет ошибки, а я что-то неправильно понял?
Re: Гарантированы ли ложные пробуждения?
От: reversecode google
Дата: 20.07.19 15:59
Оценка: +1
если бы это можно было гарантировать, то вы о них бы не узнали

ЗЫ спрашивайте то, ответы на что нельзя найти в гугле
Отредактировано 20.07.2019 16:04 Великий Реверс . Предыдущая версия .
Re: Гарантированы ли ложные пробуждения?
От: σ  
Дата: 20.07.19 16:33
Оценка: -1
Зачем ты копируешь сюда вопрос с SO шестилетней давности?
Отредактировано 20.07.2019 16:34 σ . Предыдущая версия .
Re[2]: Гарантированы ли ложные пробуждения?
От: DTF  
Дата: 20.07.19 16:50
Оценка: -1
Здравствуйте, σ, Вы писали:

σ>Зачем ты копируешь сюда вопрос с SO шестилетней давности?


Потому что я не знаю, о каком вопросе идет речь.
Искренне твой, Капитан Очевидность.
Re[3]: Гарантированы ли ложные пробуждения?
От: σ  
Дата: 20.07.19 17:03
Оценка: -2
σ>>Зачем ты копируешь сюда вопрос с SO шестилетней давности?

DTF>Потому что я не знаю, о каком вопросе идет речь.


http://rsdn.org/forum/cpp.applied/7498778
Автор: DTF
Дата: 20.07.19
Отредактировано 21.07.2019 17:03 σ . Предыдущая версия .
Re: Гарантированы ли ложные пробуждения?
От: Masterspline  
Дата: 20.07.19 17:26
Оценка:
Если у тебя один поток проверил очередь и пошел спать, а другой вставил элемент и сделал notify(), то первый либо не уснет (тут же выйдет из системного вызова ожидания), либо уснет и тут же проснется (будет поставлен в ядре в очередь планировщика для работающих потоков). Такое поведение гарантируется теми системными вызовами, на которых и основана в результате работа условной переменной. Там есть как пользовательский/библиотечный код, так и код ядра OS, т.к. засыпание потока операция не атомарная и реализовать ее на атомиках без помощи ядра не получится.

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

Ложные пробуждения — это другая тема. Они могут быть, но не гарантированы.
Re[2]: Гарантированы ли ложные пробуждения?
От: DTF  
Дата: 20.07.19 17:36
Оценка:
Здравствуйте, Masterspline, Вы писали:

M>Если у тебя один поток проверил очередь и пошел спать


Так в том-то и дело, что он еще не пошел спать. Он проверил очередь, и был приостановлен планировщиком непосредственно перед cond_var_.wait(lock).
Спать он пошел уже после того, как очередь была обновлена другим потоком.
Re[3]: Гарантированы ли ложные пробуждения?
От: Masterspline  
Дата: 20.07.19 18:47
Оценка:
M>>Если у тебя один поток проверил очередь и пошел спать

DTF>Так в том-то и дело, что он еще не пошел спать. Он проверил очередь, и был приостановлен планировщиком непосредственно перед cond_var_.wait(lock).

DTF>Спать он пошел уже после того, как очередь была обновлена другим потоком.

В этом случае notify() другого потока сделает так, что твой wait() даже не будет пытаться вызвать syscall для ухода в спячку. Например, там будет установлен атомарный флаг, проверив который wait() тут же завершится (возможно, сбросив его).

Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено. Т.е. ни разу не атомарный системный вызов, на основе которого реализована условная переменная при одновременном вызове wait() и notify() либо не усыпит процесс, либо усыпит, но параллельный notify() тут же его разбудит. Аналогично и в пользовательском (библиотечном) коде одновременные ни разу не атомарные wait() + notify() либо усыпят процесс и тут же разбудят, либо вообще не усыпят. И не важно, сколько раз будет прерываться wait() или notify() планировщиком процессов.
Re[4]: Гарантированы ли ложные пробуждения?
От: σ  
Дата: 20.07.19 19:07
Оценка: 12 (1)
M>Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.
Нет, не работают. Автор книги подтвердил, что в ней это баг.
Re[5]: Гарантированы ли ложные пробуждения?
От: Masterspline  
Дата: 20.07.19 19:58
Оценка:
M>>Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.
σ>Нет, не работают. Автор книги подтвердил, что в ней это баг.

А вот тут хочу подробнее. Ты утверждаешь, что если пойти на wait() в одном потоке, затем этот поток временно остановится, а другой добавит данные в очередь и сделает notify(), то после этого второй поток проснувшись уйдет в ожидание, оставив необработанными только что добавленные данные? Или сценарий какой-то другой?
Re[6]: Гарантированы ли ложные пробуждения?
От: σ  
Дата: 20.07.19 20:03
Оценка: 12 (1)
M>>>Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.
σ>>Нет, не работают. Автор книги подтвердил, что в ней это баг.

M>А вот тут хочу подробнее. Ты утверждаешь, что если пойти на wait() в одном потоке, затем этот поток временно остановится, а другой добавит данные в очередь и сделает notify(), то после этого второй поток проснувшись уйдет в ожидание, оставив необработанными только что добавленные данные?


Да. https://stackoverflow.com/questions/17984552/fine-grained-locking-queue-in-c
Re[7]: Гарантированы ли ложные пробуждения?
От: Masterspline  
Дата: 21.07.19 03:12
Оценка:
M>>>>Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.
σ>>>Нет, не работают. Автор книги подтвердил, что в ней это баг.

M>>А вот тут хочу подробнее. Ты утверждаешь, что если пойти на wait() в одном потоке, затем этот поток временно остановится, а другой добавит данные в очередь и сделает notify(), то после этого второй поток проснувшись уйдет в ожидание, оставив необработанными только что добавленные данные?


σ>Да. https://stackoverflow.com/questions/17984552/fine-grained-locking-queue-in-c


Спасибо за ссылку. Посмотрел. В том примере действительно баг. Условная переменная работает как надо при наличии блокировки, которая гарантирует, что данные не изменятся без владения mutex'ом. В том примере, во-первых, на изменение очереди (головы и хвоста) используются два mutex, во-вторых, проверка наличия данных делается не атомарно (get_tail отпускает блокировку до сравнения с head). Поэтому, данный пример не работает. Однако, когда я писал свой Futex на основе linux futex (для lockfree очереди, где такая проверка наличия данных не отработает в принципе, потому что блокировок нет и данные могут меняться параллельно потребителем и производителем), он устанавливал флаг при notify и в результате wait в таком случае не заснул бы без повторного прохода по данным. Аналогичный механизм может быть и в std::conditional_variable, тогда wait() не отработает, при успевшем отработать notify() и бага не проявится (но это уже особенности реализации, а не стандарта).

P.S. Там бага проявляется потому что wait()/notify() используют неправильно, так что если использовать единую блокировку, то гонки не будет и, таки,

wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.

Хотя, конечно, такая бага у Энтони Вильямса (если это действительно его бага, а не пример, как делать не надо) — это эпично.
Отредактировано 21.07.2019 3:19 Ssd13 . Предыдущая версия . Еще …
Отредактировано 21.07.2019 3:15 Ssd13 . Предыдущая версия .
Re[8]: Гарантированы ли ложные пробуждения?
От: a7d3  
Дата: 21.07.19 12:43
Оценка: :)
Здравствуйте, Masterspline, Вы писали:

M>>>>>Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.

σ>>>>Нет, не работают. Автор книги подтвердил, что в ней это баг.

M>>>А вот тут хочу подробнее. Ты утверждаешь, что если пойти на wait() в одном потоке, затем этот поток временно остановится, а другой добавит данные в очередь и сделает notify(), то после этого второй поток проснувшись уйдет в ожидание, оставив необработанными только что добавленные данные?


σ>>Да. https://stackoverflow.com/questions/17984552/fine-grained-locking-queue-in-c


M>Спасибо за ссылку. Посмотрел. В том примере действительно баг. Условная переменная работает как надо при наличии блокировки, которая гарантирует, что данные не изменятся без владения mutex'ом. В том примере, во-первых, на изменение очереди (головы и хвоста) используются два mutex, во-вторых, проверка наличия данных делается не атомарно (get_tail отпускает блокировку до сравнения с head). Поэтому, данный пример не работает. Однако, когда я писал свой Futex на основе linux futex (для lockfree очереди, где такая проверка наличия данных не отработает в принципе, потому что блокировок нет и данные могут меняться параллельно потребителем и производителем), он устанавливал флаг при notify и в результате wait в таком случае не заснул бы без повторного прохода по данным. Аналогичный механизм может быть и в std::conditional_variable, тогда wait() не отработает, при успевшем отработать notify() и бага не проявится (но это уже особенности реализации, а не стандарта).


M>P.S. Там бага проявляется потому что wait()/notify() используют неправильно, так что если использовать единую блокировку, то гонки не будет и, таки,

M>

wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.

M>Хотя, конечно, такая бага у Энтони Вильямса (если это действительно его бага, а не пример, как делать не надо) — это эпично.

Ну и слог — читать невозможно — не изложение мыслей, а сплошной поток сознания.
Re[9]: Гарантированы ли ложные пробуждения?
От: Masterspline  
Дата: 21.07.19 14:58
Оценка:
M>>>>>>Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.
σ>>>>>Нет, не работают. Автор книги подтвердил, что в ней это баг.

M>>>>А вот тут хочу подробнее. Ты утверждаешь, что если пойти на wait() в одном потоке, затем этот поток временно остановится, а другой добавит данные в очередь и сделает notify(), то после этого второй поток проснувшись уйдет в ожидание, оставив необработанными только что добавленные данные?


σ>>>Да. https://stackoverflow.com/questions/17984552/fine-grained-locking-queue-in-c


M>>Спасибо за ссылку. Посмотрел. В том примере действительно баг. Условная переменная работает как надо при наличии блокировки, которая гарантирует, что данные не изменятся без владения mutex'ом. В том примере, во-первых, на изменение очереди (головы и хвоста) используются два mutex, во-вторых, проверка наличия данных делается не атомарно (get_tail отпускает блокировку до сравнения с head). Поэтому, данный пример не работает. Однако, когда я писал свой Futex на основе linux futex (для lockfree очереди, где такая проверка наличия данных не отработает в принципе, потому что блокировок нет и данные могут меняться параллельно потребителем и производителем), он устанавливал флаг при notify и в результате wait в таком случае не заснул бы без повторного прохода по данным. Аналогичный механизм может быть и в std::conditional_variable, тогда wait() не отработает, при успевшем отработать notify() и бага не проявится (но это уже особенности реализации, а не стандарта).


M>>P.S. Там бага проявляется потому что wait()/notify() используют неправильно, так что если использовать единую блокировку, то гонки не будет и, таки,

M>>

wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.

M>>Хотя, конечно, такая бага у Энтони Вильямса (если это действительно его бага, а не пример, как делать не надо) — это эпично.

A>Ну и слог — читать невозможно — не изложение мыслей, а сплошной поток сознания.


Возможно, потому что все привыкли к односложным ответам. Но, я учту.
Отредактировано 21.07.2019 15:00 Ssd13 . Предыдущая версия .
Re[10]: Гарантированы ли ложные пробуждения?
От: wander  
Дата: 29.07.19 10:47
Оценка: +1
Здравствуйте, Masterspline, Вы писали:

M>Возможно, потому что все привыкли к односложным ответам. Но, я учту.


Приятно, что вы так относитесь к критике. Я бы не стал такое писать, если бы было иначе.

* Не пишите уточнение в скобках. Если в вашем предложении требуется такое уточнение, то предложение необходимо переформулировать.
* Не пишите длинные цепочки мыслей в одном предложении.
Например, "Однако когда..., где...., потому что...., он устанавливал... и в результате..." — это очень длинная
мысль. Ее необходимо несколько раз перечитывать, чтобы не упустить что было вначале.

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

Все вышеизложенное не является критикой или переходом на личности. Это совет, который написан исходя из вашего благосклонного отношения к этому.
Если что не так — извините.
Re: Гарантированы ли ложные пробуждения?
От: Molchalnik  
Дата: 23.11.19 21:40
Оценка:
Здравствуйте, DTF, Вы писали:


DTF>Итого, вопросы:

DTF>Гарантируется ли, что ложные пробуждения иногда происходят? Если да, то как часто?
DTF>А если нет, то почему в столь популярной книге столько времени живет очевидная ошибка?
DTF>Или в книге нет ошибки, а я что-то неправильно понял?

У меня сильное подозрение, что если в спящий поток зайдёт прерывание, весьма вероятно, что ложное пробуждение будет
а в линухе и юниксоидах пробуждение сделано на вроде сигналах (но это не точно), поэтому если сигнал зайдёт по другому поводу, а не по пробуждению потока, то будет ложное пробуждение. Заради этого везде так и описано.
Отредактировано 23.11.2019 21:49 Molchalnik . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.