Я делаю многопоточную очередь на основе односвязного списка с фиктивным последним элементом с отдельными мьютексами для головы и хвоста.
Если очередь пуста, то head_ и tail_ равны и указывают на фиктивный элемент.
Собственно, это практически та же очередь, что описывается в c++ concurrency in action, только упрощенная (меньше методов, не забочусь об исключениях).
Мне кажется, что в этой очереди (и, соответственно, в той, которая описана в CiA) есть баг.
А именно, пусть у нас один поток-писатель и один поток-читатель.
Поток-читатель в методе wait_pop проверяет условие пустоты очереди (head_ == get_tail()), видит, что она пуста, и готовится ожидать на условной переменной.
Но планировщик прерывает его до начала ожидания и передает управление потоку-писателю.
Писатель вызывает push, который полностью отрабатывает. В частности, вызывается cond_var_.notify_one().
Т.е. уведомление посылается до того, как читатель начал ждать.
После того, как push полностью отработал, поток читатель получает управление и ждетна условной переменной.
Т.е. он ждет данных, несмотря на то, что даные есть. Если новых данных не будет, то те, которые уже есть в очереди, не будут обработаны.
В принципе, если произойдет ложное пробуждение, то читатель увидит новые данные.
Итого, вопросы:
Гарантируется ли, что ложные пробуждения иногда происходят? Если да, то как часто?
А если нет, то почему в столь популярной книге столько времени живет очевидная ошибка?
Или в книге нет ошибки, а я что-то неправильно понял?
Если у тебя один поток проверил очередь и пошел спать, а другой вставил элемент и сделал notify(), то первый либо не уснет (тут же выйдет из системного вызова ожидания), либо уснет и тут же проснется (будет поставлен в ядре в очередь планировщика для работающих потоков). Такое поведение гарантируется теми системными вызовами, на которых и основана в результате работа условной переменной. Там есть как пользовательский/библиотечный код, так и код ядра OS, т.к. засыпание потока операция не атомарная и реализовать ее на атомиках без помощи ядра не получится.
Более того, ядро позволяет реализовать даже ожидание для lockfree очереди, когда никакой блокировки нет, т.е. один поток кладет данные в очередь, другой разбирает и без блокировки на доступ к очереди (но, это, конечно, не условная переменная).
Ложные пробуждения — это другая тема. Они могут быть, но не гарантированы.
Здравствуйте, Masterspline, Вы писали:
M>Если у тебя один поток проверил очередь и пошел спать
Так в том-то и дело, что он еще не пошел спать. Он проверил очередь, и был приостановлен планировщиком непосредственно перед cond_var_.wait(lock).
Спать он пошел уже после того, как очередь была обновлена другим потоком.
M>>Если у тебя один поток проверил очередь и пошел спать
DTF>Так в том-то и дело, что он еще не пошел спать. Он проверил очередь, и был приостановлен планировщиком непосредственно перед cond_var_.wait(lock). DTF>Спать он пошел уже после того, как очередь была обновлена другим потоком.
В этом случае notify() другого потока сделает так, что твой wait() даже не будет пытаться вызвать syscall для ухода в спячку. Например, там будет установлен атомарный флаг, проверив который wait() тут же завершится (возможно, сбросив его).
Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено. Т.е. ни разу не атомарный системный вызов, на основе которого реализована условная переменная при одновременном вызове wait() и notify() либо не усыпит процесс, либо усыпит, но параллельный notify() тут же его разбудит. Аналогично и в пользовательском (библиотечном) коде одновременные ни разу не атомарные wait() + notify() либо усыпят процесс и тут же разбудят, либо вообще не усыпят. И не важно, сколько раз будет прерываться wait() или notify() планировщиком процессов.
M>Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.
Нет, не работают. Автор книги подтвердил, что в ней это баг.
M>>Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено. σ>Нет, не работают. Автор книги подтвердил, что в ней это баг.
А вот тут хочу подробнее. Ты утверждаешь, что если пойти на wait() в одном потоке, затем этот поток временно остановится, а другой добавит данные в очередь и сделает notify(), то после этого второй поток проснувшись уйдет в ожидание, оставив необработанными только что добавленные данные? Или сценарий какой-то другой?
M>>>Суть моего предыдущего поста была в том, что wait()/notify() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено. σ>>Нет, не работают. Автор книги подтвердил, что в ней это баг.
M>А вот тут хочу подробнее. Ты утверждаешь, что если пойти на wait() в одном потоке, затем этот поток временно остановится, а другой добавит данные в очередь и сделает notify(), то после этого второй поток проснувшись уйдет в ожидание, оставив необработанными только что добавленные данные?
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() изначально рассчитаны на такие сценарии, поэтому все это учитывают и работают, как заявлено.
Хотя, конечно, такая бага у Энтони Вильямса (если это действительно его бага, а не пример, как делать не надо) — это эпично.
Здравствуйте, 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>Хотя, конечно, такая бага у Энтони Вильямса (если это действительно его бага, а не пример, как делать не надо) — это эпично.
Ну и слог — читать невозможно — не изложение мыслей, а сплошной поток сознания.
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>Ну и слог — читать невозможно — не изложение мыслей, а сплошной поток сознания.
Возможно, потому что все привыкли к односложным ответам. Но, я учту.
Здравствуйте, Masterspline, Вы писали:
M>Возможно, потому что все привыкли к односложным ответам. Но, я учту.
Приятно, что вы так относитесь к критике. Я бы не стал такое писать, если бы было иначе.
* Не пишите уточнение в скобках. Если в вашем предложении требуется такое уточнение, то предложение необходимо переформулировать.
* Не пишите длинные цепочки мыслей в одном предложении.
Например, "Однако когда..., где...., потому что...., он устанавливал... и в результате..." — это очень длинная
мысль. Ее необходимо несколько раз перечитывать, чтобы не упустить что было вначале.
Все это не связано с привычкой к односложным ответам, а скорее с особенностью человеческого восприятия.
Вам ваша мысль кристально ясна только потому, что вы сами ее и сформулировали; остальным — нет, по крайней мере не сразу.
Иногда просто полезно перечитать то, что было написано.
Все вышеизложенное не является критикой или переходом на личности. Это совет, который написан исходя из вашего благосклонного отношения к этому.
Если что не так — извините.
DTF>Итого, вопросы: DTF>Гарантируется ли, что ложные пробуждения иногда происходят? Если да, то как часто? DTF>А если нет, то почему в столь популярной книге столько времени живет очевидная ошибка? DTF>Или в книге нет ошибки, а я что-то неправильно понял?
У меня сильное подозрение, что если в спящий поток зайдёт прерывание, весьма вероятно, что ложное пробуждение будет
а в линухе и юниксоидах пробуждение сделано на вроде сигналах (но это не точно), поэтому если сигнал зайдёт по другому поводу, а не по пробуждению потока, то будет ложное пробуждение. Заради этого везде так и описано.
