Здравствуйте, rsdn_179b, Вы писали:
_>Интересует собственно сабж — откуда берутся эти самые "ложные пробуждения" ?
_>П.С.: Ссылки на соответствующие учёные книги приветствуются
Здравствуйте, rsdn_179b, Вы писали:
_>Интересует собственно сабж — откуда берутся эти самые "ложные пробуждения" ?
Ну, а что вы хотите от переменной с таким названием? Условно говоря, она работает. Иногда, правда, wait выходит из себя залочив мьютекс без всяких видимых на то причин, но это не страшно: мьютекс-то залочен, а значит данные не испортятся.
_>Поиск по форуму к сожалению не дал ответа на этот вопрос.
Я так понимаю, что проблема эта тянется с самого низу, с аппаратного уровня.
_>Но к сожалению не объясняет самой сути этого явления.
Суть явления: функция wait(..) может разблокироваться, даже если notify_one() никто не вызывал. Так написано в стандарте и поэтому нам с этим приходится жить.
_>Зачем крутиться в цикле и проверять какие-то условия
Затем, что wait(..) может самопроизвольно разблокироваться и функция её вызвавшая продолжит работу в любой, непредсказуемый момент. Никто notify_one() не вызывал, а она раз — и разблокировалась. Поэтому и вводят флажок, чтобы отличить самопроизвольное разблокирование от запланированного.
_>Пример кода взят с "CodeProject":
Во взятом примере выкинут важный lock вот здесь: _>
Изменение g_notified должно быть защищено.
_>Надеюсь на содержательные ответы. Всем ответившим заранее спасибо.
Содержательно jazzer уже ответил. От себя добавлю, что условные переменные — это не события. Это даже не переменные, так как никаких данных они не хранят. Это такой неудобный способ синхронизации, который нужен для сверхмеры оптимизированных алгоритмов. Лично я его напрямую не использую. Я из условной переменной делаю событие для нотификации, а данные защищаю отдельным мьютексом. Так код становится существенно проще, хотя и не для всех задач можно построить решение на событиях. Те же, кто экономит на спичках мьютексах, использует condition variables.
И каждый день — без права на ошибку...
Re: C++11: Синхронизация - Условные переменные и ложные пробужде
Здравствуйте, rsdn_179b, Вы писали:
_>Интересует собственно сабж — откуда берутся эти самые "ложные пробуждения" ?
1) Если есть несколько точек ожидания одной и той же CV — будь то один поток, интересующийся разными вещами, или несколько потоков, ворующих посылки друг у друга из-под носа
2) Если условие может меняться туда-сюда быстрее, чем заинтересованный в нём поток
Пример:
mutex m;
conditional_variable cv;
DWORD flags;
void update(DWORD set, DWORD reset)
{
scoped_lock l(m);
DWORD newflags = (flags & ~reset) | set;
// порядок извещения и изменения не важен, мы же ещё не отпустили мьютексif(flags != newflags) cv.notify_one();
flags = newflags;
}
void expect(DWORD flag, bool isset)
{
unique_lock<mutex> l(m);
while(bool(flags & flag) != isset) cv.wait(l);
}
Держать по отдельной CV на каждый бит — расточительно; цена экономии — ложные пробуждения, если поток-источник выставил не тот бит, который нам интересен.
Ещё пример
volatile unsigned ready_flag;
void update(bool flag)
{
::InterlockedExchange(&ready_flag, flag); // запись атомарная, лочить незачем
cv.notify_one(); // но известить потребителя нужно
// если поменяем на notify_all для второго сценария, - ничего не изменится
}
void take_ready() // ждёт ready_flag и опускает его
{
unique_lock<mutex> l(m); // чисто для протокола - так требует CVwhile(!::InterlockedCompareExchange(&ready_flag,false,true)) cv.wait(l);
}
// первый сценарийvoid update_nothing() { update(true); update(false); } // дёрнули, даже дважды, но пока поток-приёмник проснётся...
// второй сценарийvoid update_twice() { update(true); update(true); } // дёрнули дваждыvoid thread_one() { take_ready(); } // первый проснулся и погасилvoid thread_two() { take_ready(); } // второй проснулся, а уже погашено
_>Зачем крутиться в цикле и проверять какие-то условия
Можно и не крутиться, а один раз проверить, обломиться и бросить это занятие.
CV — это способ извещения о событии, о неком моменте, в котором, возможно, выполнилось нужное условие.
Говоря в терминах WinAPI, это PulseEvent.
Связывать CV с состоянием и экономить на проверках и булевских флажках — можно в некоторых узких рамках. (В отличие от Event, которое и событие, и булев флажок, или от семафора, который и событие, и счётчик).
Мне кажется, именно эта особенность WinAPI приучила программистов к иным сценариям синхронизации, чем во всём остальном мире. И то, проблема ложных пробуждений там тоже существует.
Перекуём баги на фичи!
Re[2]: C++11: Синхронизация - Условные переменные и ложные п
К>volatile unsigned ready_flag;
К>void update(bool flag)
К>{
К> ::InterlockedExchange(&ready_flag, flag); // запись атомарная, лочить незачем
К> cv.notify_one(); // но известить потребителя нужно
К> // если поменяем на notify_all для второго сценария, - ничего не изменится
К>}
К>void take_ready() // ждёт ready_flag и опускает его
К>{
К> unique_lock<mutex> l(m); // чисто для протокола - так требует CV
К> while(!::InterlockedCompareExchange(&ready_flag,false,true)) cv.wait(l);
К>}
К>// первый сценарий
К>void update_nothing() { update(true); update(false); } // дёрнули, даже дважды, но пока поток-приёмник проснётся...
К>// второй сценарий
К>void update_twice() { update(true); update(true); } // дёрнули дважды
К>void thread_one() { take_ready(); } // первый проснулся и погасил
К>void thread_two() { take_ready(); } // второй проснулся, а уже погашено
К>
это плохой пример по двум причинам:
1) каша из bool/unsigned. надо на чем-то одном остановиться
2) из-за того, что в void update не лочит мьютекс мы имеем race, из-за которого cv.wait(l) зависнет навечно, хотя ready_flag будет равен true. очень важно понимать, насколько мощен wait:
этот метод одновременно уходит в ожидание и разлочивает мьютекс (транзакционно). это гарантирует, что при правильном использовании (а не как в этом примере) cv, метод notify не уйдет в пустоту. гарантирует, что условие в while не может измениться, пока мы не провалимся в wait. поэтому менять данные, которые могут изменять condition, надо строго под мьютексом.
Здравствуйте, Кодт, Вы писали:
К>Держать по отдельной CV на каждый бит — расточительно; цена экономии — ложные пробуждения, если поток-источник выставил не тот бит, который нам интересен.
ТС спрашивает о spurious wakeups, а ты подменяешь понятия и ушел совсем не в ту степь
Re: C++11: Синхронизация - Условные переменные и ложные пробужде
Здравствуйте, rsdn_179b, Вы писали:
_>Здравствуйте гуру, знатоки и просто ценители C++ !
_>Интересует собственно сабж — откуда берутся эти самые "ложные пробуждения" ?
В книге "Стандартная библиотека С++" Николаи М. Джосаттис, 2 издание, 2014г., с. 1028
"... проверка условной переменной может сработать, даже если условная переменная
не осуществляла уведомление. Процитируем Энтони Уильямса (Anthony Williams)
[Williams:CondVar]:"Ложные срабатывания невозможно предсказать: с точки зрения пользователя
они являются совершенно случайными. Однако они часто происходят, когда библиотека потоков
не может гарантировать, что ожидающий поток не пропустит уведомление. Поскольку пропущенное
уведомление делает условную переменную бесполезной, библиотека потоков активизирует потоки,
чтобы не рисковать."
Все выше — цитата из переведенной книжки, кому инересно можете поискать в оригинале
Здравствуйте, rsdn_179b, Вы писали:
_>Интересует собственно сабж — откуда берутся эти самые "ложные пробуждения" ?
Они берутся из особенностей реализации обработки прерываний\сигналов на целевой платформе. Например в POSIX срабатывание сигнала в ходе ожидания I\O-примитивом "свистка" от устройства прерывает его выполнение со специальным кодом ошибки.
_>Зачем крутиться в цикле и проверять какие-то условия
Потому что в спецификации так написано...
Re[2]: C++11: Синхронизация - Условные переменные и ложные пробужде
Здравствуйте, rsdn_179b, Вы писали:
_>>Интересует собственно сабж — откуда берутся эти самые "ложные пробуждения" ?
Кстати, вот хороший кусочек из обсуждения на SO:
The pthread_cond_wait() function in Linux is implemented using the futex system call. Each blocking system call on Linux returns abruptly with EINTR when the process receives a signal. ... pthread_cond_wait() can't restart the waiting because it may miss a real wakeup in the little time it was outside the futex system call. This race condition can only be avoided by the caller checking for an invariant. A POSIX signal will therefore generate a spurious wakeup.
Summary: If a Linux process is signaled its waiting threads will each enjoy a nice, hot spurious wakeup.
коммент
This EINTR unblocking is true of all blocking system calls in Unix derived systems. This made the kernel lots simpler, but the application programmers bought the burden.
вопрос
I thought pthread_cond_wait() and friends could not return EINTR, but return zero if spuriously woken up? From: pubs.opengroup.org/onlinepubs/7908799/xsh/… "These functions will not return an error code of [EINTR]."
и ответ
That's right. The underlying futex() call returns EINTR, but that return value isn't bubbled up to the next level. The pthread caller must therefore check for an invariant. What they're saying is that when pthread_cond_wait() returns you must check your loop condition (invariant) again, because the wait might have been spuriously woken up. Receiving a signal during a system call is one possible cause, but it's not the only one.
Имхо, вполне исчерпывающе: особенности реализации плюс некоторая кривизна интерфейса (что EINTR не возвращается, даже если он является причиной вылета из блокирующего ожидания).
_>Интересует собственно сабж — откуда берутся эти самые "ложные пробуждения" ? _>П.С.: Ссылки на соответствующие учёные книги приветствуются.
Ухх! Что-то я про такое и не помнил, хотая документацию Java по wait() читал и там про это написано.
Спасибо.
Возник вопрос не по совсем теме, но всё же связанный с ней.
Сейчас нашёл разъяснение для Linux, состоящее в том, что если идёт блокирующией вызов и приходит сигнал, то вызов прерывается: http://blog.vladimirprus.com/2005/07/spurious-wakeups.html
Здравствуйте, se_sss, Вы писали:
_>В связи с этой страничкой возник вопрос. А что если у нас несколько потоков? В каком из них ошибка произошла? _>errno ведь глобальная переменная?
Использлвание errno должно быть потокобезопасно по требованиям POSIX. Например в Линуксе эта переменная thread-local http://linux.die.net/man/3/errno
Здравствуйте, Кодт, Вы писали:
_>>Интересует собственно сабж — откуда берутся эти самые "ложные пробуждения" ? К>Пример:
первый раз вижу чтобы кодт минусов нахватал
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re: C++11: Синхронизация - Условные переменные и ложные проб
Интересует собственно сабж — откуда берутся эти самые "ложные пробуждения" ?
Для POSIX: дело в устройстве самого механизма. Pthread основан на futex. В основе futex идёт (первым аргументом) адрес некоторой переменной (назовём её 'A' в некотором "подопытном" процессе). Далее внутри реализации происходит преобразование адреса переменной из "пользовательского пространства" в физический адрес (это нужно для shared операций между процессами). Далее, от полученного адреса вычисляется 32 битный хэш (так называемый jhash2). Затем вычисляется индекс: от полученного значения берётся маска, что-то типа ( hash & ((1<<20) — 1 ) ). Значение этой маски сильно зависит от системы (настроек, количества процессоров), но обычно она не превышает 1 МБ. Полученный индекс используется для индексации в глобальной таблице, описывающей все futex-объекты. В итоге, если есть в системе какой-либо другой процесс, у которого есть своя переменная 'B' и индекс, подсчитанный от этой переменной совпадёт с индексом переменной 'A' и "выставится событие" по переменой 'B' — то выставится это-же событие и для переменной 'A', т.е. для неё ('A') произойдёт "ложное пробуждение". Вероятность данного явления небольшая, но всё-же есть.
Спасибо вам большое! Наконец-то человек простым языком, без посылки далеко, объяснил откуда берутся эти "зомби" пробуждения — просто особенность реализации на основе хеш-таблицы, где возможны коллизии при попытки разбудить несколько не связанных CV из разных процессов. Аллилуйя!!!
Re[2]: C++11: Синхронизация - Условные переменные и ложные пробужде
Уж если придираться, то notify_xxx() не обязательно делать под локом, т.к. поток сидящий на wait() все-равно не сможет проснуться, пока вы не покинете область видимости locker-а.
Re[2]: C++11: Синхронизация - Условные переменные и ложные проб
Здравствуйте, kotalex, Вы писали:
K> В основе futex идёт (первым аргументом) адрес некоторой переменной (назовём её 'A' в некотором "подопытном" процессе). Далее внутри реализации происходит преобразование адреса переменной из "пользовательского пространства" в физический адрес (это нужно для shared операций между процессами). Далее, от полученного адреса вычисляется 32 битный хэш (так называемый jhash2). Затем вычисляется индекс: от полученного значения берётся маска, что-то типа ( hash & ((1<<20) — 1 ) ). Значение этой маски сильно зависит от системы (настроек, количества процессоров), но обычно она не превышает 1 МБ. Полученный индекс используется для индексации в глобальной таблице, описывающей все futex-объекты.
Вот до этого места правильно описывается одна из возможных реализаций, но дальше идёт просто фееричная чушь:
K>В итоге, если есть в системе какой-либо другой процесс, у которого есть своя переменная 'B' и индекс, подсчитанный от этой переменной совпадёт с индексом переменной 'A' и "выставится событие" по переменой 'B' — то выставится это-же событие и для переменной 'A', т.е. для неё ('A') произойдёт "ложное пробуждение". Вероятность данного явления небольшая, но всё-же есть.
То что несколько фьютексов могут отображаться в один бакет таблицы никак не делает их зависимыми. Они (как и в любой нормальной хеш-таблице без открытой адресации) просто будут оба лежать в одном бакете. Это хеширование с цепочками называется.
Вот в ядре linux есть функция match_futex, которая используется во всех операциях обхода бакета как раз для того, чтобы отфильтровать фьютексы попавшие в него из-за коллизий.
То есть тут даже не важно что используется: хеш-таблица, какое-нибудь дерево поиска, или вообще единственная глобальная очередь на всё ядро. Различия будут в производительности (очевидно, глобальная очередь будет медленновато работать из-за параллельных локов), но не в семантике операций.
---
Да и вообще, даже если допустить, что ядро не имеет возможностей отличить где чей фьютекс находится, а сравнивает их только по хешу, то тогда невозможно было бы реализовать функции вроде pthread_cond_signal, которые будят ровно один тред, а не все. Ведь вызов pthread_cond_signal мог бы разбудить своего доппельгангера (для которого бы это пробуждение выглядело как spurious wakeup), и, соответственно, не разбудить поток ожидающий на целевом фьютексе. А это, внезапно, куда большая проблема: в системе образовался поток, которому не дошел сигнал пробуждения и который завис навечно (если конечно, ещё раз не произойдёт чудо и не придёт сигнал на пробуждение от какого-то третьего неудачника с совпавшим хешом ). Вы регулярно наблюдаете такие зависшие потоки? А знаете почему нет?
Призываю не верить объяснению kotalex — оно прикольное, но совершенно неверное.
Re[3]: C++11: Синхронизация - Условные переменные и ложные проб
Здравствуйте, watchmaker, Вы писали:
W> .... W>Призываю не верить объяснению kotalex — оно прикольное, но совершенно неверное.
"Редиска" вы, watchmaker. Все выходные у меня было хорошее настроение и вот опять — мне страшно.
А если серьезно, то все используют механизм, косяки которого научились успешно обходить, и даже все работает как задумывалось, но никто не в состоянии на пальцах объяснить что происходит и почему. Везде только говориться, мол, особенность реализации и в интересах производительности.
To be continued...
Re[4]: C++11: Синхронизация - Условные переменные и ложные проб
Здравствуйте, Videoman, Вы писали:
V>"Редиска" вы, watchmaker. Все выходные у меня было хорошее настроение и вот опять — мне страшно. V>А если серьезно, то все используют механизм, косяки которого научились успешно обходить, и даже все работает как задумывалось, но никто не в состоянии на пальцах объяснить что происходит и почему. Везде только говориться, мол, особенность реализации и в интересах производительности.
V>To be continued...
Чем тебя не устраивает объяснение, что cond_wait вылетает при получении процессом сигнала ?
Здравствуйте, andyp, Вы писали:
A>Чем тебя не устраивает объяснение, что cond_wait вылетает при получении процессом сигнала ?
Не совсем устраивает, т.к. не хватает информации в общем. Я так понял:
у Linux все ожидания, всех объектов в ядре так устроены — происходит пробуждение по сигналу со специальным кодом. Т.к. в случаях не связанных с CV у нас состояние объекта присутствует в ядре, мы можем проверить код возврата, перепроверить само состояние и вернуться обратно в ожидание, если оно было ложным. В случае в CV у нас состояние в user mod-е и мы вынуждены вернуться и проверять его самостоятельно. Из всего вышесказанного делаем вывод — futex оказался слишком низкоуровневым объектом что бы его выносить в стандартную библиотеку C++. Ведь никто, слава богу, не догадался сделать spurious_read, spurious_join или spurious_lock. И все-равно остается куча вопросов:
1. Что c Windows ?
2. Если на Windows обошлись без ложных пробуждений, то почему особенности реализации POSIX на Linux "втащили" в стандартную библиотеку ?
3. Почему, например, не сделали флаг для futex-а — NO_SPURIOUS_WAKEUP для использования в высокоуровневом API ?
4. Что с вариантами wait_until и wait_for, ведь если wait_until еще как-то можно в цикле крутить, то wait_for становится весьма нетривиальным ?
Re[6]: C++11: Синхронизация - Условные переменные и ложные проб
Здравствуйте, Videoman, Вы писали: V>4. Что с вариантами wait_until и wait_for, ведь если wait_until еще как-то можно в цикле крутить, то wait_for становится весьма нетривиальным ?
Я в этой теме только первый день, но на cppreferences о wait_for нашёл следующее: "2) Equivalent to return wait_until(lock, std::chrono::steady_clock::now() + rel_time, std::move(pred));. This overload may be used to ignore spurious awakenings."
Перекуём баги на фичи!
?
