Покритикуйте пожалуйста, будет ли работать такая реализация, какие возможны проблемы?
По идее это multi-producer/multi-consumer очередь, но уж очень просто получилось, где подвох?
lock-free структуры — тема для меня совсем новая, заранее огромное спасибо за ответы!
Здравствуйте, afkos, Вы писали:
A>Покритикуйте пожалуйста, будет ли работать такая реализация, какие возможны проблемы? A>По идее это multi-producer/multi-consumer очередь, но уж очень просто получилось, где подвох? A>lock-free структуры — тема для меня совсем новая, заранее огромное спасибо за ответы!
Во-первых, очередь формально не lock-free. Если поток будет прерван между Decrement() и Increment(), то он может остановить системный прогресс:
A>
A> T * Pop()
A> {
A> if(m_Count.Decrement() < 0)
A> {
A> m_Count.Increment();
A> return 0;
A> }
A>
Например тут: A> unsigned long i = ((unsigned long)m_First.Increment() — 1) % m_BufferSize; A> return m_Buffer[i];
Представь потребитель получил какой-то индекс i, и дальше заблокировался. В это время очередь полностью освободилась и заполнилась заново. Теперь наш потребитель просыпается и считывает из m_Buffer[i] совсем не то, что он должен был вернуть.
Или опять же вот этот момент: A>
A> T * Pop()
A> {
A> if(m_Count.Decrement() < 0)
A> {
A> m_Count.Increment();
A> return 0;
A> }
A>
Допустим m_Count==0. Потребитель 1 выполняет декремент, соотв. m_Count==-1, теперь этот потребитель вытесняется ОС (т.е. инкремент он ещё не сделал). Теперь производитель кладёт элемент в очередь и увеличивает m_Count до 0. Теперь приходит потребитель 2 и выполняет декремент, m_Count опять становится равен -1, и потребитель 2 возвращает 0 вместо того, что бы вернуть элемент, который лежит в очереди. Теперь просыпается наш первый потребитель и инкрементирует счётчик до 1, но возвращает опять же 0. В общем случае это может привести к дедлоку системы, в очереди лежит элемент, но потребители не могут его вернуть.
Или допустим тут: A>
A> void Push(T * node)
A> {
A> unsigned long i = ((unsigned long)m_Last.Increment() - 1) % m_BufferSize;
A> m_Buffer[i] = node;
A> m_Count.Increment();
A> }
A>
Допустим изначально очередь пустая. Производитель 1 инкрементирует m_Last до 1, и засыпает (т.е. ещё не записал элемент в очередь). Теперь производитель 2 инкрементирует m_Last до 2, записывает свой элемент в позицию 1 очереди, и инкрементирует m_Count. Теперь приходит потребитель, видит, что в очереди лежит элемент (m_Count==1), но возвращает он элемент не из позиции 1 (где лежит реальный элемент), а из позиции 0 (где лежит мусор).
Я думаю, можно не продолжать. Да, всё действительно не так просто, как кажется на первый взгляд. Ты используешь AtomicLong, но он магическим образом не делает целые операции атомарными, он делает атомарным только одно изменение одной переменной. Тебе же нужно, что бы целые операции были атомарными, т.е. в одно неделимое действие инкрементировать m_Last, записать элемент в массив, и инкрементировать m_Count. Либо же все остальные потоки должны быть готовы к тому, что например, m_Last инкрементирован, а элемент в массив ещё не записан, и соотв. обрабатывать такие все такие ситуации.
Если ты действительно всерьёз хочешь этим заниматься и использовать такие алгоритмы в продакш-коде, то очень рекомендую использовать библиотеку Relacy Race Detector: http://groups.google.com/group/relacy
Я разработал её специально для верификации таких алгоритмов, она бы на раз вскрыла все эти гонки... и, я думаю, больше. В общем случае у меня не получается с ней соревноваться по качеству и скорости проверки алгоритмов.
Здравствуйте, remark, Вы писали:
R>Если ты действительно всерьёз хочешь этим заниматься и использовать такие алгоритмы в продакш-коде, то очень рекомендую использовать библиотеку Relacy Race Detector: R>http://groups.google.com/group/relacy R>Я разработал её специально для верификации таких алгоритмов, она бы на раз вскрыла все эти гонки... и, я думаю, больше. В общем случае у меня не получается с ней соревноваться по качеству и скорости проверки алгоритмов.
Здравствуйте, afkos, Вы писали:
A>Покритикуйте пожалуйста, будет ли работать такая реализация, какие возможны проблемы?
vector — потоко-небезопасен, следовательно при одновременном обращении из разных потоков не гарантирует консистентное состояние.
Выводы можешь сделать сам.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Здравствуйте, afkos, Вы писали:
A>>Покритикуйте пожалуйста, будет ли работать такая реализация, какие возможны проблемы?
ATP>vector — потоко-небезопасен, следовательно при одновременном обращении из разных потоков не гарантирует консистентное состояние. ATP>Выводы можешь сделать сам.
Я не думаю, что какая-либо здравая реализация вектора может создать тут проблемы. Его просто сложно реализовать т.ч. он мог создать тут проблемы. Фактически он тут используется просто как С-массив, т.е. "кусок памяти".
Например реализация MSVC явно гарантирует, что std::vector безопасен для чтения из разных потоков.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>Здравствуйте, afkos, Вы писали:
A>>>Покритикуйте пожалуйста, будет ли работать такая реализация, какие возможны проблемы?
ATP>>vector — потоко-небезопасен, следовательно при одновременном обращении из разных потоков не гарантирует консистентное состояние. ATP>>Выводы можешь сделать сам.
R>Я не думаю, что какая-либо здравая реализация вектора может создать тут проблемы. Его просто сложно реализовать т.ч. он мог создать тут проблемы. Фактически он тут используется просто как С-массив, т.е. "кусок памяти". R>Например реализация MSVC явно гарантирует, что std::vector безопасен для чтения из разных потоков.
R>
Согласен, скорее всего все будет ок.
Но в приведенном коде, насколько я понял не учитывается максимальный размер данных, следовательно пихающий поток может обернуться несколько раз через массив, пока читающий ждет, а вот это уже точно потеря консистентности данных.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Согласен, скорее всего все будет ок. ATP>Но в приведенном коде, насколько я понял не учитывается максимальный размер данных, следовательно пихающий поток может обернуться несколько раз через массив, пока читающий ждет, а вот это уже точно потеря консистентности данных.
Это не проблема вектора. Там много чего не учитывается, и те же самые проблемы будут даже если вместо вектора использовать статически выделенный блок памяти.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>Согласен, скорее всего все будет ок. ATP>>Но в приведенном коде, насколько я понял не учитывается максимальный размер данных, следовательно пихающий поток может обернуться несколько раз через массив, пока читающий ждет, а вот это уже точно потеря консистентности данных.
R>Это не проблема вектора. Там много чего не учитывается, и те же самые проблемы будут даже если вместо вектора использовать статически выделенный блок памяти.
R>
Да я понимаю, просто чего человек хотел добиться непонятно. Интерфейс неполон. Гадать без автора не хотелось бы.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>>Согласен, скорее всего все будет ок. ATP>>>Но в приведенном коде, насколько я понял не учитывается максимальный размер данных, следовательно пихающий поток может обернуться несколько раз через массив, пока читающий ждет, а вот это уже точно потеря консистентности данных.
R>>Это не проблема вектора. Там много чего не учитывается, и те же самые проблемы будут даже если вместо вектора использовать статически выделенный блок памяти.
ATP> Да я понимаю, просто чего человек хотел добиться непонятно. Интерфейс неполон. Гадать без автора не хотелось бы.
А что не понятно? Очередь fixed-size, вектору один раз в конструкторе установили размер, дальше он используется просто как кусок памяти.
В целом, конечно, было бы лучше закрыть компирование и использовать просто std::auto_ptr<T*>.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>Здравствуйте, remark, Вы писали:
R>>>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>>>Согласен, скорее всего все будет ок. ATP>>>>Но в приведенном коде, насколько я понял не учитывается максимальный размер данных, следовательно пихающий поток может обернуться несколько раз через массив, пока читающий ждет, а вот это уже точно потеря консистентности данных.
R>>>Это не проблема вектора. Там много чего не учитывается, и те же самые проблемы будут даже если вместо вектора использовать статически выделенный блок памяти.
ATP>> Да я понимаю, просто чего человек хотел добиться непонятно. Интерфейс неполон. Гадать без автора не хотелось бы.
R>А что не понятно? Очередь fixed-size, вектору один раз в конструкторе установили размер, дальше он используется просто как кусок памяти. R>В целом, конечно, было бы лучше закрыть компирование и использовать просто std::auto_ptr<T*>.
R>
Непонятно как такою очередь можно использовать не задав максимально возможный размер. Очередь ведь не должна перезатирать ранее положенные в нее элементы.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Непонятно как такою очередь можно использовать не задав максимально возможный размер. Очередь ведь не должна перезатирать ранее положенные в нее элементы.
Хороший вопрос.
Раз очередь фиксированного размера, то вариантов не много. Можно либо блокировать производителя, пока не освободится место. Либо возвращать ошибку, как в функции Pop(). Либо перетирать старый элемент (самый старый/самый новый/произвольный).
В любом случае, так как оно сейчас реализованно — работать не будет:
1. Не синхронизованны инкремент/десремент и вставка/удаление.
2. Непонятно кто управляет временем жизни объектов.
Здравствуйте, remark, Вы писали:
R>Я думаю, можно не продолжать. Да, всё действительно не так просто, как кажется на первый взгляд. Ты используешь AtomicLong, но он магическим образом не делает целые операции атомарными, он делает атомарным только одно изменение одной переменной. Тебе же нужно, что бы целые операции были атомарными, т.е. в одно неделимое действие инкрементировать m_Last, записать элемент в массив, и инкрементировать m_Count. Либо же все остальные потоки должны быть готовы к тому, что например, m_Last инкрементирован, а элемент в массив ещё не записан, и соотв. обрабатывать такие все такие ситуации.
R>Если ты действительно всерьёз хочешь этим заниматься и использовать такие алгоритмы в продакш-коде, то очень рекомендую использовать библиотеку Relacy Race Detector: R>http://groups.google.com/group/relacy R>Я разработал её специально для верификации таких алгоритмов, она бы на раз вскрыла все эти гонки... и, я думаю, больше. В общем случае у меня не получается с ней соревноваться по качеству и скорости проверки алгоритмов.
Благодарю за столь развернутый ответ и отдельное спасибо за ссылки, очень интересный материал.
To AcidTheProgrammer:
Это не production код, только маленький эксперимент.
Конечно, std::vector используется только как buffer, и как уже заметил Remark, не будет никакой разницы, если его заменить на обычный массив
В целом на все вопросы Remark уже ответил
Тогда, раз уж так всё хорошо разрешилось у меня есть вопрос к remark-у:
дело в том что я по роду своей деятельности также активно занимаюсь созданием многопоточных примитивов. Может быть вы подскажите как на платформе Intel x86 — реализуются примитивы типа LL/SC?
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Тогда, раз уж так всё хорошо разрешилось у меня есть вопрос к remark-у: ATP>дело в том что я по роду своей деятельности также активно занимаюсь созданием многопоточных примитивов. Может быть вы подскажите как на платформе Intel x86 — реализуются примитивы типа LL/SC?
На x86 для выполнения атомарных RMW (read-modify-write) операций используется инструкция LOCK CMPXCHG, которая атомарно выполняет следующее:
В некотором смысле она мощнее LL/SC, т.к. возвращает текущее актуальное значение; но с другой стороны она и слабее, т.к. допускает ABA проблему (т.е. текущее значение могло измениться со времени загрузки, но так получилось что оно равно загруженному — CMPXCHG в этом случае успешно выполнится, тогда как LL/SC провалится).
Для частных случаев можно использовать частные команды — LOCK XADD (загрузить и прибавить), LOCK ADD (прибавить), LOCK OR (или), LOCK AND (и), LOCK XCHG (загрузить и сохранить) и др. В целом они несколько быстрее, чем цикл с CMPXCHG.
Но вообще для таких операций обычно есть интринсики компилятора. Например для CMPXCHG это _InterlockedCompareExchange() в MSVC (intrin.h), __sync_compare_exchange_val() в gcc (built-in), atomic_cas_32 в сс на Solaris (atomic.h).
Здравствуйте, remark, Вы писали:
R>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>Тогда, раз уж так всё хорошо разрешилось у меня есть вопрос к remark-у: ATP>>дело в том что я по роду своей деятельности также активно занимаюсь созданием многопоточных примитивов. Может быть вы подскажите как на платформе Intel x86 — реализуются примитивы типа LL/SC?
R>На x86 для выполнения атомарных RMW (read-modify-write) операций используется инструкция LOCK CMPXCHG, которая атомарно выполняет следующее: R>
R>В некотором смысле она мощнее LL/SC, т.к. возвращает текущее актуальное значение; но с другой стороны она и слабее, т.к. допускает ABA проблему (т.е. текущее значение могло измениться со времени загрузки, но так получилось что оно равно загруженному — CMPXCHG в этом случае успешно выполнится, тогда как LL/SC провалится).
Да, нет — все понятно. Если бы всё было бы так просто я бы и не спрашивал. То что вы описываете (CMPXCHG) это и есть в обобщенном виде СAS операция. Собственно с ABA проблеммой я и борюсь. Насчет мощьности с вами полностью не согласен. Опять же из-за той самой ABA-проблеммы и из-за того что через LL/SC примитивы CAS без проблем выражается, а вот наоборот... в этом и есть мой вопрос — как выразить LL/SC примитивы через те которые поддерживаются x86.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Да, нет — все понятно. Если бы всё было бы так просто я бы и не спрашивал. То что вы описываете (CMPXCHG) это и есть в обобщенном виде СAS операция. Собственно с ABA проблеммой я и борюсь. Насчет мощьности с вами полностью не согласен. Опять же из-за той самой ABA-проблеммы и из-за того что через LL/SC примитивы CAS без проблем выражается, а вот наоборот... в этом и есть мой вопрос — как выразить LL/SC примитивы через те которые поддерживаются x86.
А, ты это имеешь в виду. Ну вобщем-то... никак. В смысле никак, что нет никакой магической инструкции.
Самый простой способ это обойти — это использовать IBM-тэги (IBM ABA-prevention tags), т.е. к указателю прилепляется монотонно инкрементируемый при каждом изменении счётчик, который участвует в CAS операции. Но тут проблема, что не на всех ранних х86-64 процессорах был 128-битный CAS. Для обхода этого был разработан ряд техник, таких как pointer-packing или allocation from pool.
Но мне лично, честно говоря, вообще такой подход с "затыканием" ABA не очень нравится, т.к. основной проблемы он не решает. А основная проблема — это управление временем жизни объектов. Если она решена, то и ABA по-определению нет.
А для решения проблемы управления временем жизни есть ряд алгоритмов, таких как Hazard Pointers (SMR), Read-Copy-Update (RCU), Proxy-Collector, VZOOM, и различные модификации и комбинации методов (SMR+RCU).
В частности вот ряд алгоритмов.
Амортизированный Proxy-Collector: http://groups.google.com/group/lock-free/browse_frm/thread/18a9f43b93a6b3f0
Scalable distributed reference counting: http://groups.google.com/group/lock-free/browse_frm/thread/46d00a0f543a758e
В архиве hash_map.zip есть реализация ещё одного Proxy-Collector и пример импользования: http://groups.google.com/group/lock-free/files
Да я читал про все эти прибамбасы — уныние сплошное. Не так все это просто элегантно как с LL/SC.
А как на 32-х битной x86 правильно атомарно заменить сразу два слова?
Здравствуйте, remark, Вы писали:
R>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>А как на 32-х битной x86 правильно атомарно заменить сразу два слова?
R>Смотря какие 2 слова, "два слова" бывают разные Слова смежные?
R>
А так и так . Мне просто интересен случай одновременного увеличение счетчика и перезапись указателя. Конкретно — реализация потокобезлпасного подсчета ссылок.
Здравствуйте, AcidTheProgrammer, Вы писали:
R>>А как с помощью LL/SC реализовать вставку элемента в очередь? Как вот такой код переписать на LL/SC?
ATP>Просто реализовать СAS через LL/SC примерно так (на C-псевдокоде)?
Нет, не СAS реализовать. А реализовать вставку в очередь на LL/SC, т.ч. ей не была бы нужна внешняя схема управления временем жизни объектов?
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>>А как на 32-х битной x86 правильно атомарно заменить сразу два слова?
R>>Смотря какие 2 слова, "два слова" бывают разные Слова смежные?
ATP>А так и так . Мне просто интересен случай одновременного увеличение счетчика и перезапись указателя. Конкретно — реализация потокобезлпасного подсчета ссылок.
Смежные слова просто, есть инструкции CMPXCHG8B/CMPXCHG16B, которыми можно менять два смежных слова.
Не смежные — никак.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, AcidTheProgrammer, Вы писали:
R>>>А как с помощью LL/SC реализовать вставку элемента в очередь? Как вот такой код переписать на LL/SC?
ATP>>Просто реализовать СAS через LL/SC примерно так (на C-псевдокоде)?
R>Нет, не СAS реализовать. А реализовать вставку в очередь на LL/SC, т.ч. ей не была бы нужна внешняя схема управления временем жизни объектов?
Видимо вы недопоняли — как через LL/SC реализовать CAS я написал, ну а дальше применяете вас же алгоритм, который вы описали выше.
Здравствуйте, AcidTheProgrammer, Вы писали:
R>>>>А как с помощью LL/SC реализовать вставку элемента в очередь? Как вот такой код переписать на LL/SC?
ATP>>>Просто реализовать СAS через LL/SC примерно так (на C-псевдокоде)?
R>>Нет, не СAS реализовать. А реализовать вставку в очередь на LL/SC, т.ч. ей не была бы нужна внешняя схема управления временем жизни объектов?
ATP>Видимо вы недопоняли — как через LL/SC реализовать CAS я написал, ну а дальше применяете вас же алгоритм, который вы описали выше.
Тот алгоритм, который я описал выше требует внешней схемы управления временем жизни узлов очереди (gc_region_enter()/gc_region_leave()). Вопрос — как реализовать этот алгоритм с помощью LL/SC, т.ч. ей не была бы нужна внешняя схема управления временем жизни объектов.
Это вопрос к тезису:
Да я читал про все эти прибамбасы — уныние сплошное. Не так все это просто элегантно как с LL/SC.
Если же этого сделать нельзя, то не понятно о какой элегантности LL/SC идёт речь. Если у нас всё равно есть схема управления временем жизни, то ABA проблемы нет как таковой.
Ну также, почти. Правда я не совсем понимаю ваш код:
Для вставки в очередь достаточно атомарной операции EXCHG или Swap, во всяком случае у меня во всех очередях используется такая операция.
(Может это моё ноу-хау Ну а EXCHG через LL/SC без проблем выводится.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>Здравствуйте, remark, Вы писали:
R>>>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>>>А как на 32-х битной x86 правильно атомарно заменить сразу два слова?
R>>>Смотря какие 2 слова, "два слова" бывают разные Слова смежные?
ATP>>А так и так . Мне просто интересен случай одновременного увеличение счетчика и перезапись указателя. Конкретно — реализация потокобезлпасного подсчета ссылок.
R>Смежные слова просто, есть инструкции CMPXCHG8B/CMPXCHG16B, которыми можно менять два смежных слова. R>Не смежные — никак.
Ну вроде как что-то припоминаю такое, а в винде его никак не вызвать (не на ассемблере)?
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Ну также, почти. Правда я не совсем понимаю ваш код: ATP>Для вставки в очередь достаточно атомарной операции EXCHG или Swap, во всяком случае у меня во всех очередях используется такая операция. ATP>(Может это моё ноу-хау Ну а EXCHG через LL/SC без проблем выводится.
Ну так через XCHG будет не lock-free очередь, а блокирующая (если я правильно понял, о чём речь).
Задача портировать на LL/SC именно такую lock-free очередь.
Здравствуйте, AcidTheProgrammer, Вы писали:
R>>Смежные слова просто, есть инструкции CMPXCHG8B/CMPXCHG16B, которыми можно менять два смежных слова. R>>Не смежные — никак.
ATP>Ну вроде как что-то припоминаю такое, а в винде его никак не вызвать (не на ассемблере)?
Здравствуйте, remark, Вы писали:
R>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>Ну также, почти. Правда я не совсем понимаю ваш код: ATP>>Для вставки в очередь достаточно атомарной операции EXCHG или Swap, во всяком случае у меня во всех очередях используется такая операция. ATP>>(Может это моё ноу-хау Ну а EXCHG через LL/SC без проблем выводится.
R>Ну так через XCHG будет не lock-free очередь, а блокирующая (если я правильно понял, о чём речь). R>Задача портировать на LL/SC именно такую lock-free очередь.
R>
Извиняюсь если не до конца понимаю терминологию. Нужно было бы конечно сначала договориться что считаем блокирующей/не блокирующей. Здесь разве есть блокирование?
// Allocate new item for future element
ItemPtr pItem = new Item;
ItemPtr pOldTail = pItem;
// Swap new item and previous tail item
EXCHG(m_pQueueTail, pOldTail);
Здравствуйте, remark, Вы писали:
R>Здравствуйте, AcidTheProgrammer, Вы писали:
R>>>Смежные слова просто, есть инструкции CMPXCHG8B/CMPXCHG16B, которыми можно менять два смежных слова. R>>>Не смежные — никак.
ATP>>Ну вроде как что-то припоминаю такое, а в винде его никак не вызвать (не на ассемблере)?
R>http://msdn.microsoft.com/en-us/library/ms683562%28VS.85%29.aspx
Она, насколько я понял, не доступна в 32-х битной версии. Для 64-х битной версии не доступна 128-бинтная и т.д. Задача используя именно примитивы разрядности = разрядности процессора обменять сразу два слова. Задачка что-то типа построить двойной СAS (DCAS) на основе одинарного и т.д.
Здравствуйте, AcidTheProgrammer, Вы писали:
R>>>>Смежные слова просто, есть инструкции CMPXCHG8B/CMPXCHG16B, которыми можно менять два смежных слова. R>>>>Не смежные — никак.
ATP>>>Ну вроде как что-то припоминаю такое, а в винде его никак не вызвать (не на ассемблере)?
R>>http://msdn.microsoft.com/en-us/library/ms683562%28VS.85%29.aspx
ATP>Она, насколько я понял, не доступна в 32-х битной версии. Для 64-х битной версии не доступна 128-бинтная и т.д. Задача используя именно примитивы разрядности = разрядности процессора обменять сразу два слова. Задачка что-то типа построить двойной СAS (DCAS) на основе одинарного и т.д.
А ну это пожалуйста, одинарный CAS присутствует — InterlockedCompareExchange.
з.ы. а где написано, что InterlockedCompareExchange64() не доступна в 32-битной версии?
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Извиняюсь если не до конца понимаю терминологию. Нужно было бы конечно сначала договориться что считаем блокирующей/не блокирующей. Здесь разве есть блокирование?
ATP>
ATP>// Allocate new item for future element
ATP>ItemPtr pItem = new Item;
ATP>ItemPtr pOldTail = pItem;
ATP>// Swap new item and previous tail item
ATP>EXCHG(m_pQueueTail, pOldTail);
ATP>
Блокироваться будет потребитель, если этот производитель прервётся в нехорошем месте (опять же, если я правильно угадал алгоритм).
Здравствуйте, remark, Вы писали:
ATP>>Извиняюсь если не до конца понимаю терминологию. Нужно было бы конечно сначала договориться что считаем блокирующей/не блокирующей. Здесь разве есть блокирование?
ATP>>
ATP>>// Allocate new item for future element
ATP>>ItemPtr pItem = new Item;
ATP>>ItemPtr pOldTail = pItem;
ATP>>// Swap new item and previous tail item
ATP>>EXCHG(m_pQueueTail, pOldTail);
ATP>>
R>Блокироваться будет потребитель, если этот производитель прервётся в нехорошем месте (опять же, если я правильно угадал алгоритм).
Дело даже не в конкретной очереди. Дело в том, что простое подавление ABA работает только в очень частных случаях, поэтому особой элегантности я в этом не вижу.
Другой пример — допустим есть хэш-таблица, один поток ищет элемент и инкрементирует счётчик в нём, другой поток может одновременно удалить элемент. Тут тоже простым подавлением ABA не обойдёшься.
Здравствуйте, remark, Вы писали:
R>>Блокироваться будет потребитель, если этот производитель прервётся в нехорошем месте (опять же, если я правильно угадал алгоритм).
EXCHG — это простой InterlockedExchange — от атомарен. Как он может прерваться? Tail есть всегда.
R>Дело даже не в конкретной очереди. Дело в том, что простое подавление ABA работает только в очень частных случаях, поэтому особой элегантности я в этом не вижу.
СAS проверяет значение элемента, а это недостаточное условие того что состояние не изменилось — следовательно начинаются пляски.
LL — ставит под контроль адрес (ячейку) памяти и если SC выполняется успешно, то значение точно не менялось. То есть, если перезапись была, но на тоже значение, то SC это замит, CAS -нет. В остальном они полностью эквивалентны.
R>Другой пример — допустим есть хэш-таблица, один поток ищет элемент и инкрементирует счётчик в нём, другой поток может одновременно удалить элемент. Тут тоже простым подавлением ABA не обойдёшься.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Здравствуйте, remark, Вы писали:
R>>>Блокироваться будет потребитель, если этот производитель прервётся в нехорошем месте (опять же, если я правильно угадал алгоритм).
ATP>EXCHG — это простой InterlockedExchange — от атомарен. Как он может прерваться? Tail есть всегда.
Ты же не весь код показал, там же ещё должно быть установление связей между элементами очереди. Вот там-то, я думаю, и будут проблемы. Насколько мне известно, сейчас lock-free очередей, которые используют XCHG в push() нет.
Здравствуйте, AcidTheProgrammer, Вы писали:
R>>>Блокироваться будет потребитель, если этот производитель прервётся в нехорошем месте (опять же, если я правильно угадал алгоритм).
ATP>EXCHG — это простой InterlockedExchange — от атомарен. Как он может прерваться? Tail есть всегда.
R>>Дело даже не в конкретной очереди. Дело в том, что простое подавление ABA работает только в очень частных случаях, поэтому особой элегантности я в этом не вижу.
ATP>СAS проверяет значение элемента, а это недостаточное условие того что состояние не изменилось — следовательно начинаются пляски. ATP>LL — ставит под контроль адрес (ячейку) памяти и если SC выполняется успешно, то значение точно не менялось. То есть, если перезапись была, но на тоже значение, то SC это замит, CAS -нет. В остальном они полностью эквивалентны.
Условие, что значение одной переменной не изменилось, тоже является недостаточным для достижения корректности многих алгоритмов. Им всё равно необходимо управление временем жизни, а раз так, то ABA проблемы нет.
... ну либо им нужен multi-word LL/SC (транзакционная память).
R>>Другой пример — допустим есть хэш-таблица, один поток ищет элемент и инкрементирует счётчик в нём, другой поток может одновременно удалить элемент. Тут тоже простым подавлением ABA не обойдёшься.
ATP>Тут соглачен. Вот тут нужен DCAS или что-то подобное.
DCAS-ом тут не обойдёшься, тут будет нежен double-LL/SC (что в простанородье уже вобщем-то называется транзакционной памятью).
Здравствуйте, remark, Вы писали:
R>Ты же не весь код показал, там же ещё должно быть установление связей между элементами очереди. Вот там-то, я думаю, и будут проблемы. Насколько мне известно, сейчас lock-free очередей, которые используют XCHG в push() нет.
template<class TYPE>
void MultiThreadQueue<TYPE>::LockFreePush(const TYPE& element, LONG lWeight)
{
// Method add element to queue
// Allocate new item for future element
ItemPtr pItem = new Item;
ItemPtr pOldTail = pItem;
// Swap new item and previous tail item
EXCHG(m_pQueueTail, pOldTail);
// Now new item became tail item
// Set element for previous item and set item chain
pOldTail->lWeight = lWeight;
pOldTail->element = element;
pOldTail->pNextItem = pItem;
}
Почему, вот мой рабочий код, который вставляет элемент в очередь
Здравствуйте, AcidTheProgrammer, Вы писали:
R>>Ты же не весь код показал, там же ещё должно быть установление связей между элементами очереди. Вот там-то, я думаю, и будут проблемы. Насколько мне известно, сейчас lock-free очередей, которые используют XCHG в push() нет.
ATP>
ATP> template<class TYPE>
ATP> void MultiThreadQueue<TYPE>::LockFreePush(const TYPE& element, LONG lWeight)
ATP> {
ATP> // Method add element to queue
ATP> // Allocate new item for future element
ATP> ItemPtr pItem = new Item;
ATP> ItemPtr pOldTail = pItem;
ATP> // Swap new item and previous tail item
ATP> EXCHG(m_pQueueTail, pOldTail);
ATP> // Now new item became tail item
ATP> // Set element for previous item and set item chain
ATP> pOldTail->lWeight = lWeight;
ATP> pOldTail->element = element;
ATP> pOldTail->pNextItem = pItem;
ATP> }
ATP>
ATP>Почему, вот мой рабочий код, который вставляет элемент в очередь
Допустим, один производитель выполнил EXCHG, и вытеснен ОС до выполнения pOldTail->pNextItem = pItem. Потом другие производители положили в очередь ещё 100 элементов.
Как потребитель будет обрабатывать такую ситуацию? Он сможет потребить эти 100 элементов? Не будет ли он фактически заблокирован до того момента пока первый производитель соизволит проснуться и доделать свою работу? А если поток первого производителя убит?
Здравствуйте, remark, Вы писали:
R>Допустим, один производитель выполнил EXCHG, и вытеснен ОС до выполнения pOldTail->pNextItem = pItem. Потом другие производители положили в очередь ещё 100 элементов. R>Как потребитель будет обрабатывать такую ситуацию?
Потребитель не увидит их пока производитель не закончит операцию.
R>Он сможет потребить эти 100 элементов?
нет
R> Не будет ли он фактически заблокирован до того момента пока первый производитель соизволит проснуться и доделать свою работу?
Он просто решит что элементов нет в очереди, но зато когда производитель завершит операцию — потребитель увидит сразу 100 элементов. Запись элементов в очередь не прервется ни при каких обстоятельствах, за исключение случая который затрагивается вами в следующем вопросе. Может быть я не совсем верно понимаю "не блокирование", ну думаю что у меня блокирование нет.
А если поток первого производителя убит?
А если все производители убиты Шучу. Вы понимаете, на практике я не работаю в режиме ядра. Для драйверов — да, этот вопрос актуален, для меня нет. Либо все потоки процесса прибьются, либо ни один.
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Здравствуйте, remark, Вы писали:
R>>Допустим, один производитель выполнил EXCHG, и вытеснен ОС до выполнения pOldTail->pNextItem = pItem. Потом другие производители положили в очередь ещё 100 элементов. R>>Как потребитель будет обрабатывать такую ситуацию?
ATP>Потребитель не увидит их пока производитель не закончит операцию.
Это и есть определение блокирования.
R>> Не будет ли он фактически заблокирован до того момента пока первый производитель соизволит проснуться и доделать свою работу?
ATP>Он просто решит что элементов нет в очереди, но зато когда производитель завершит операцию — потребитель увидит сразу 100 элементов. Запись элементов в очередь не прервется ни при каких обстоятельствах, за исключение случая который затрагивается вами в следующем вопросе. Может быть я не совсем верно понимаю "не блокирование", ну думаю что у меня блокирование нет.
Ну как же нет? Там так или иначе код типа:
void consumer(queue* q)
{
for (;;)
{
item_t* item = q->dequeue();
if (item)
consume_item(item);
else
backoff();
}
}
Что фактически есть спин-мьютекс, только несколько вывернутый на изнанку. Это по-сути аналогично:
Сама очередь, конечно, существенно лучше std::queue+mutex (например, если перед "разрывом" есть ещё элементы, то потребитель сможет их свободно потребить; или производиели всегда wait-free), но сути это не меняет: очередь — блокирующая.
ATP>А если поток первого производителя убит?
ATP>А если все производители убиты Шучу. Вы понимаете, на практике я не работаю в режиме ядра. Для драйверов — да, этот вопрос актуален, для меня нет. Либо все потоки процесса прибьются, либо ни один.
Здравствуйте, remark, Вы писали:
ATP>>А если поток первого производителя убит?
ATP>>А если все производители убиты Шучу. Вы понимаете, на практике я не работаю в режиме ядра. Для драйверов — да, этот вопрос актуален, для меня нет. Либо все потоки процесса прибьются, либо ни один.
R>Это вопрос отдельный. R>Очередь — не lock-free. Точка. R>lock-free очередь должна обеспечивать обще-системный прогресс не зависимо ни от чего: R>http://www.rsdn.ru/forum/philosophy/2930849.1.aspx
Main characteristics of the algorithm:
— intrusive
— producers: 1 XCHG, wait-free
— consumers: 1 CAS on common path, mostly lock-free (***)
— producers and consumers do not content with each other (until queue is empty)
— no need for safe memory reclamation
(***) requires additional comments. There is a small (1 machine instruction in length) window of inconsistency for producers. If producer will be preempted there he may (or may not) cause blocking of consumers (other producers are still wait-free). If producer will be terminated there he will cause system-wide stall. Taking into account length of the window, probability of these things may be considered negligible in most situations.
Получается достаточно интересно, т.к. хоть формально очередь не lock-free, но производители всегда аж wait-free. Так же "плохой" производиель не всегда блокирует потребителей; например, если в очереди всегда есть какое-то кол-во элементов, тот факт, что в конце очереди могут возникать врЕменные "дырки" никак не влияет на потребителей (если эти "дырки" будут устранены до того, как потребители до них дойдут).
Кстати, насколько я вижу, твоя очередь не интрузивная. Я так же описывал интрузивный вариант этой очереди, в ней нет необходимости отдельно выделять/освобождать память под узлы очереди, и нет необходимости 2 раза копировать пользовательские данные.
Да, в таком смысле она блокирующая. Что бы была не блокирующей, нужно что бы другой производитель завершал незаконченную операцию начатую первым, а затем делал свою. Можно изменить, но в моем случае лучше проще.
В оправдание могу сказать следующее:
1. Пихающие потоки не блокируются. А это в моих задачах и есть самое главное. Главное быстрее освободить устройство и перекинуть данные в очередь.
2. Код значительно проще для понимания — меньше возможных ошибок.
3. Потребители иногда ждут, но они в моём случае и так почти всегда ждут, т.к если данных нет, то им просто ничего другого не остается.
Кстати Дмитрий, вы я смотрю хорошо разбираетесь в look-free алгоритмах. Не могли бы вы посмотреть на предмет look-free мой простенький аллокатор в данной ветке
ATP> template<class TYPE>
ATP> void MultiThreadQueue<TYPE>::LockFreePush(const TYPE& element, LONG lWeight)
ATP> {
ATP> // Method add element to queue
ATP> // Allocate new item for future element
ATP> ItemPtr pItem = new Item;
ATP> ItemPtr pOldTail = pItem;
ATP> // Swap new item and previous tail item
ATP> EXCHG(m_pQueueTail, pOldTail);
ATP> // Now new item became tail item
ATP> // Set element for previous item and set item chain
ATP> pOldTail->lWeight = lWeight;
ATP> pOldTail->element = element;
ATP> pOldTail->pNextItem = pItem;
ATP> }
ATP>
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Кстати Дмитрий, вы я смотрю хорошо разбираетесь в look-free алгоритмах. Не могли бы вы посмотреть на предмет look-free мой простенький аллокатор в данной ветке
Ну в общем очень похоже. Я походу дела тут изобретательством велосипедов занимаюсь. Но кстати замечу, что пока сам не допрешь как сделать, в тот код, на который вы даете ссылки я бы долго врубался. А так смотришь — вот гады, у меня все идеи сперли !!!
Здравствуйте, remark, Вы писали:
R>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>Кстати Дмитрий, вы я смотрю хорошо разбираетесь в look-free алгоритмах. Не могли бы вы посмотреть на предмет look-free мой простенький аллокатор в данной ветке
Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, AcidTheProgrammer, Вы писали:
ATP>>>Кстати Дмитрий, вы я смотрю хорошо разбираетесь в look-free алгоритмах. Не могли бы вы посмотреть на предмет look-free мой простенький аллокатор в данной ветке
Да в общем-то я бы не назвал это велосипедами... по крайней мере сейчас, возможно лет через 10 это и будут называть велосипедами... ссылаясь на нас, как на первые реализации
Всё, что я публикую, насколько мне известно не имеет никакого prior art'а, т.е. это вообще нигде больше публично не описано, по-крайней мере в статьях, за всеми форумами по всему интернету конечно не уследишь, но за основными англо-язычными я слежу и там ничего подобного нет, и никто ни разу мне не указывал на prior art.
Так что это мы велосипеды не делаем, а изобретаем
Здравствуйте, remark, Вы писали:
R>Да в общем-то я бы не назвал это велосипедами... по крайней мере сейчас, возможно лет через 10 это и будут называть велосипедами... ссылаясь на нас, как на первые реализации R>Всё, что я публикую, насколько мне известно не имеет никакого prior art'а, т.е. это вообще нигде больше публично не описано, по-крайней мере в статьях, за всеми форумами по всему интернету конечно не уследишь, но за основными англо-язычными я слежу и там ничего подобного нет, и никто ни разу мне не указывал на prior art. R>Так что это мы велосипеды не делаем, а изобретаем
R>
Ну почему же не описано — описано и даже запатентовано. Видимо данная тема для кого-то все еще представляет денежный интерес.
Кстати возвращаясь к реализации Lock-Free Push-a, в чем основная идея, в двух словах. После того как я узнал что в моей очереди Push не Lock-Free стало интересно альтернативная реализация. В исходниках мне сложнее разобраться будет.
Здравствуйте, AcidTheProgrammer, Вы писали:
R>>Да в общем-то я бы не назвал это велосипедами... по крайней мере сейчас, возможно лет через 10 это и будут называть велосипедами... ссылаясь на нас, как на первые реализации R>>Всё, что я публикую, насколько мне известно не имеет никакого prior art'а, т.е. это вообще нигде больше публично не описано, по-крайней мере в статьях, за всеми форумами по всему интернету конечно не уследишь, но за основными англо-язычными я слежу и там ничего подобного нет, и никто ни разу мне не указывал на prior art. R>>Так что это мы велосипеды не делаем, а изобретаем
ATP>Ну почему же не описано — описано и даже запатентовано. Видимо данная тема для кого-то все еще представляет денежный интерес.
В этой области всё патентуется... иногда даже по несколько раз... иногда даже после того, как уже общеизвестно
А какой номер патента? Хотелось бы знать врага в лицо
ATP>Кстати возвращаясь к реализации Lock-Free Push-a, в чем основная идея, в двух словах. После того как я узнал что в моей очереди Push не Lock-Free стало интересно альтернативная реализация. В исходниках мне сложнее разобраться будет.
Здравствуйте, remark, Вы писали:
R>В этой области всё патентуется... иногда даже по несколько раз... иногда даже после того, как уже общеизвестно R>А какой номер патента? Хотелось бы знать врага в лицо
Ну мне это не очень интересно было. Как только находишь что-нибудь стоящее — сразу: патент XXX, цена YYYYYYYYYYY. Тут сразу понимаешь что лучше как я буду свой велик делать.
Например как-то нарыл мега-крутой, мега-быстрый, мега-простой (как пишут) алгоритм который якобы позволяет используя одинарные CAS делать DCAS. Так он запатентован, а что бы почитать о нем просят денег. Сам ничего простого придумать не смог. Конечно понятно, что транзакционную замену блока любой длины можно свести к замене указателя на это самый блок, но простым я бы это алгоритм не назвал бы.
R>Это классическая Michael-Scott lock-free очередь: R>http://www.cs.rochester.edu/research/synchronization/pseudocode/queues.html R>Я думаю по ней легко и статей множество нагуглить.
Да, да — он родимый и есть. Все работы обычно на него и ссылаются.
R>
Ну а EXCHG через LL/SC без проблем выводится.
