Здравствуйте, vf, Вы писали:
vf>Начну новую ветку чтобы не путать с другим неверным подозрением связаным с переполнением.
vf>Чем больше разбираюсь тем больше мне алгоритм нра, он компактный, красивый, очень хорошо вписывается под мою задачу/требования. Есть большое желание его использовать.
vf>Два попутных вопроса: vf>1. А кто автор алгоритма, Вы?
Да.
vf>2. Нет ли c# версии?
Я его не портировал на c#.
vf>Я его конечно переписал на шарп, но где-то видать накосячил, не взлетело (хотя в одном потоке работает).
Здравствуйте, vf, Вы писали:
vf>Основной вопрос: vf>Возможна ли следующая ситуация: vf>а значит, нижний код вернет в dif==-1, и dequeue() false как будто элементов в очереди нет, но ведь он есть!
Ситуация полностью возможна. Но элемента тут в очереди ещё нет. Элемент есть в очереди [по-определению] когда производитель установил seq соотв. образом.
В теории concurrent структур данных есть такое понятие как Linearizability, и в частности Linearization point. В данном алгоритме Linearization point функции enqueue() по отношению к потребителям есть как раз модификация seq элемента. После этого момента операция считается полностью вступившей в силу. До этого же она соотв. не вступившая в силу, и все модификации надо рассматривать только как некоторые внутренние детали алгоритма.
Здравствуйте, remark, Вы писали:
vf>>Основной вопрос: vf>>Возможна ли следующая ситуация: vf>>а значит, нижний код вернет в dif==-1, и dequeue() false как будто элементов в очереди нет, но ведь он есть!
R>Ситуация полностью возможна. Но элемента тут в очереди ещё нет. Элемент есть в очереди [по-определению] когда производитель установил seq соотв. образом.
Я имел ввиду элемент добавленный вторым потоком, для него seq установлен, и функция enqueue полностью отработана. То есть меня волнует следующее развитие событий, допустим каждый поток кладет и берет один элемент в очередь в цикле, и если выше приведенная ситуация возможно, то выходит что поток положил элемент, но при попытке вытащить получает не обоснованные облом, потому что хотя бы один(его) элемент в очереди точно присутствует.
R>В теории concurrent структур данных есть такое понятие как Linearizability, и в частности Linearization point. В данном алгоритме Linearization point функции enqueue() по отношению к потребителям есть как раз модификация seq элемента.
Спасибо за ссылку, но мне кажется (я еще не вчитывался), что это не объясняет, повторюсь получается что операция над первым элементом мешает обращаться ко второму, для которого enqueue полностью отработала и linearization point пройдена, как я понимаю?
Здравствуйте, vf, Вы писали:
R>>Ситуация полностью возможна. Но элемента тут в очереди ещё нет. Элемент есть в очереди [по-определению] когда производитель установил seq соотв. образом.
vf>Я имел ввиду элемент добавленный вторым потоком, для него seq установлен, и функция enqueue полностью отработана. То есть меня волнует следующее развитие событий, допустим каждый поток кладет и берет один элемент в очередь в цикле, и если выше приведенная ситуация возможно, то выходит что поток положил элемент, но при попытке вытащить получает не обоснованные облом, потому что хотя бы один(его) элемент в очереди точно присутствует.
Извиняюсь — невнимательно прочитал.
Да, такая фигня тоже возможна. Т.е. это — *не* lock-free очередь. Терминология в этой области полностью не установлена, зачастую это называют non-blocking, хотя фактически очередь блокирующая — вот такой "зависший" производитель будет блокировать прогресс потребителей. Однако стоит отметить, что очередь на мьютексах будет гораздо хуже, т.к. "зависший" под мьютексом поток будет блокировать все операции. Тут же зависший производитель будет блокировать только потребителей, и только когда они вытащят все предыдущие элемента (т.е. пока они не дошли до этого проблемного элемента, они могут свободно потреблять другие элементы; а когда они дойдут до этого, возможно, он уже будет и полностью положен в очередь). Так же зависший производитель не блокирует других производителей (пока очередь не полностью заполнена), что достаточно приятно по сравнению с мьютексами. И такая же зеркальная ситуация будет для "зависшего" потребителя.
Что бы такого не было совсем нужно использовать lock-free очередь. Однако lock-free очередь скорее всего будет медленнее — за дополнительные гарантии надо платить.
Вывод такой. Если тебе нужны гарантии forward progress
(например, для hard real-time системы), то надо использовать lock-free/wait-free. Однако я не знаю даже lock-free алгоритма для array-bases multi-producer/multi-consumer очереди. И при этом она скорее всего будет медленнее работать.
Если тебе нужна просто производительность (например, для throughput-oriented сервера), то нужно использовать что-то типа очереди, приведённой в этом топике. Она не даёт строгих гарантий прогресса, однако быстрая.
Мьютексы же оказываются не у дел, т.к. не дают ни производительности, ни гарантий прогресса.
Здравствуйте, remark, Вы писали:
vf>>Я имел ввиду элемент добавленный вторым потоком, для него seq установлен, и функция enqueue полностью отработана. То есть меня волнует следующее развитие событий, допустим каждый поток кладет и берет один элемент в очередь в цикле, и если выше приведенная ситуация возможно, то выходит что поток положил элемент, но при попытке вытащить получает не обоснованные облом, потому что хотя бы один(его) элемент в очереди точно присутствует.
R>Да, такая фигня тоже возможна. Т.е. это — *не* lock-free очередь. Терминология в этой области полностью не установлена, зачастую это называют non-blocking, хотя фактически очередь блокирующая — вот такой "зависший" производитель будет блокировать прогресс потребителей. Однако стоит отметить, что очередь на мьютексах будет гораздо хуже, т.к. "зависший" под мьютексом поток будет блокировать все операции. Тут же зависший производитель будет блокировать только потребителей
Если бы производитель блокировал, он же не блокирует, потребителю очередь скажет что элементов нет, хотя их там может быть несколько. Так чтобы в статистику не уходить (хотя я все таки считаю что для большинства случаев это недопустимое поведение), конктретно в моей задача, это принципиальный момент, я буду создавать(уничтожать) лишний элемент когда не смогу его взять(положить) в очередь, а это тянет за собой работу GC для "старых" объектов, и тут большой вопрос что будет выгоднее тот же mutex(хотя есть и другие варианты) или работа GC.
R>Однако я не знаю даже lock-free алгоритма для array-bases multi-producer/multi-consumer очереди. И при этом она скорее всего будет медленнее работать.
Вот я находил, там по два CAS на добавление и один на получение элемента. Еще не пробовал реализовать.
R>Если тебе нужна просто производительность (например, для throughput-oriented сервера), то нужно использовать что-то типа очереди, приведённой в этом топике. Она не даёт строгих гарантий прогресса, однако быстрая. R>Мьютексы же оказываются не у дел, т.к. не дают ни производительности, ни гарантий прогресса.
Глядя на все эти ньюансы и не устаявшуюся терминалогию , майкрософтовский подход — реализовать все через спинлоки — начинает казаться самым верным.
Здравствуйте, vf, Вы писали:
vf>Если бы производитель блокировал, он же не блокирует, потребителю очередь скажет что элементов нет, хотя их там может быть несколько.
Почему не блокирует? Блокирует. Если бы это была очередь на мьютексе, считай, что потребитель вызывает try_lock(), который возвращает ему false. Трактуй это так.
vf>Так чтобы в статистику не уходить (хотя я все таки считаю что для большинства случаев это недопустимое поведение), конктретно в моей задача, это принципиальный момент, я буду создавать(уничтожать) лишний элемент когда не смогу его взять(положить) в очередь, а это тянет за собой работу GC для "старых" объектов, и тут большой вопрос что будет выгоднее тот же mutex(хотя есть и другие варианты) или работа GC.
А более конкретно можешь? Какой элемент? Для чего? Какого GC?
Здравствуйте, vf, Вы писали:
R>>Однако я не знаю даже lock-free алгоритма для array-bases multi-producer/multi-consumer очереди. И при этом она скорее всего будет медленнее работать.
vf>Вот я находил, там по два CAS на добавление и один на получение элемента. Еще не пробовал реализовать.
Каким боком M&S queue является array-based?
Плюс ещё добавь по 1 CAS на операцию на управление временем жизни узлов, т.к. алгоритм не работает без GC.
Да, и кстати, она не фига не linearizable, как они это утверждают и даже вроде как "доказывают". Подробнее я описывал тут: http://groups.google.com/group/comp.programming.threads/browse_frm/thread/8344b10e0deb18dc
R>>Если тебе нужна просто производительность (например, для throughput-oriented сервера), то нужно использовать что-то типа очереди, приведённой в этом топике. Она не даёт строгих гарантий прогресса, однако быстрая. R>>Мьютексы же оказываются не у дел, т.к. не дают ни производительности, ни гарантий прогресса.
vf>Глядя на все эти ньюансы и не устаявшуюся терминалогию , майкрософтовский подход — реализовать все через спинлоки — начинает казаться самым верным.
Это что за майкрософтовский подход? В любом случае это получается какой-то двойной стандарт. Ты думаешь свою инфраструктуру, ран-таймы, библиотеки для распараллеливания они на спинлоках делают? Отнюдь.
Здравствуйте, remark, Вы писали:
vf>>Вот я находил, там по два CAS на добавление и один на получение элемента. Еще не пробовал реализовать.
R>Каким боком M&S queue является array-based?
Нет, она не array-based, но мне почему-то кажется, что в array-based от обычной перейти всегда можно?! Ведь по логике — это скорее упрощение.
R>Плюс ещё добавь по 1 CAS на операцию на управление временем жизни узлов, т.к. алгоритм не работает без GC.
Если это так, тогда совсем плохо.
R>>>Если тебе нужна просто производительность (например, для throughput-oriented сервера), то нужно использовать что-то типа очереди, приведённой в этом топике. Она не даёт строгих гарантий прогресса, однако быстрая. R>>>Мьютексы же оказываются не у дел, т.к. не дают ни производительности, ни гарантий прогресса.
vf>>Глядя на все эти ньюансы и не устаявшуюся терминалогию , майкрософтовский подход — реализовать все через спинлоки — начинает казаться самым верным.
R>Это что за майкрософтовский подход? В любом случае это получается какой-то двойной стандарт. Ты думаешь свою инфраструктуру, ран-таймы, библиотеки для распараллеливания они на спинлоках делают? Отнюдь.
Да, где проскакивало, что в 4.0 дот нете, tread-safe коллекции сделаны на spin-lock-ах. Опять же утверждать не буду, сам я не делал и рефлектором не смотрел.
Здравствуйте, vf, Вы писали:
vf>Да, где проскакивало, что в 4.0 дот нете, tread-safe коллекции сделаны на spin-lock-ах. Опять же утверждать не буду, сам я не делал и рефлектором не смотрел.
Ну и что, это ещё не значит, что это единственный подход. В XLinq (System.Xml.Linq) XHashtable — lock-free (блокируются только записи и только при ресайзе).
Здравствуйте, remark, Вы писали:
vf>>Если бы производитель блокировал, он же не блокирует, потребителю очередь скажет что элементов нет, хотя их там может быть несколько.
R>Почему не блокирует? Блокирует. Если бы это была очередь на мьютексе, считай, что потребитель вызывает try_lock(), который возвращает ему false. Трактуй это так.
Здесь возникает не однозначность, я привык трактовать false возвращенный dequeue как отсутствие элементов в очереди. Дело даже не привычке, как различать два этих события? И тоже самое для enqueue?
vf>>Так чтобы в статистику не уходить (хотя я все таки считаю что для большинства случаев это недопустимое поведение), конктретно в моей задача, это принципиальный момент, я буду создавать(уничтожать) лишний элемент когда не смогу его взять(положить) в очередь, а это тянет за собой работу GC для "старых" объектов, и тут большой вопрос что будет выгоднее тот же mutex(хотя есть и другие варианты) или работа GC.
R>А более конкретно можешь? Какой элемент? Для чего? Какого GC?
Я могу, но мне кажется мы просто щас уйдем от темы. Таких примеров где, нужно знать что очередь пуста или полна я думаю Вы и сами можете придумать. А вот где не нужно, я не могу придумать? Пусть некий сервер, с термином throughput-oriented я не знаком, что он кладет запросы на обработку в такую очередь? А что если она заполниться, производители устроят гонку добавляя элементы, или наоборот когда пуста, как снизить кол-во "холостых" потребителей? То есть полюбому вырисовывается механизм, который будет считать число элементов, хотя бы приблизительно.
Конструктивное предложение — предлагаю добавить счетчик элеметов внутрь очереди, и нынешние функции dequeue/enqueue завернуть в цикл for(counter > 0)/for(counter<max) — тогда возвращаемы значения можно будет интерпретировать как принято для очереди.
Здравствуйте, fddima, Вы писали:
vf>>Да, где проскакивало, что в 4.0 дот нете, tread-safe коллекции сделаны на spin-lock-ах. Опять же утверждать не буду, сам я не делал и рефлектором не смотрел. F> Ну и что, это ещё не значит, что это единственный подход. В XLinq (System.Xml.Linq) XHashtable — lock-free (блокируются только записи и только при ресайзе).
Возможно. Я два поста назад, написал "все" в контексте коллекций — моя ошибка. Я не утверждаю, что это весь .нет написан таким образом. Извените что внес путаницу.
Здравствуйте, vf, Вы писали:
R>>Почему не блокирует? Блокирует. Если бы это была очередь на мьютексе, считай, что потребитель вызывает try_lock(), который возвращает ему false. Трактуй это так.
vf>Здесь возникает не однозначность, я привык трактовать false возвращенный dequeue как отсутствие элементов в очереди. Дело даже не привычке, как различать два этих события? И тоже самое для enqueue?
А точно ли их надо различать? Как будет различаться обработка этих ситуаций в твоём случае?
vf>Я могу, но мне кажется мы просто щас уйдем от темы. Таких примеров где, нужно знать что очередь пуста или полна я думаю Вы и сами можете придумать. А вот где не нужно, я не могу придумать? Пусть некий сервер, с термином throughput-oriented я не знаком, что он кладет запросы на обработку в такую очередь? А что если она заполниться, производители устроят гонку добавляя элементы,
Их не интересует полна она или нет, их интересует можно класть сообщения в очередь или нет. Если нельзя, то какая особо разница почему. В любом случае можно выбрасывать сообщение, или ждать пока не станет можно класть.
vf>или наоборот когда пуста, как снизить кол-во "холостых" потребителей?
Опять же какая разница, пуста она или нельзя получать сообщения по какой-то другой причине?
vf>То есть полюбому вырисовывается механизм, который будет считать число элементов, хотя бы приблизительно.
Приблизительно считать в этой очереди можно — просто возьми enqueue — dequeue. Для какой-то статистики этой подойдёт. Однако, если поток хочет достать сообщение для обработки, и он видит, что очередь формально не пуста, но достать сообщение не может, то какая ему разница-то?
vf>Конструктивное предложение — предлагаю добавить счетчик элеметов внутрь очереди, и нынешние функции dequeue/enqueue завернуть в цикл for(counter > 0)/for(counter<max) — тогда возвращаемы значения можно будет интерпретировать как принято для очереди.
А что будет делать поток, которому такой dequeue() вернёт false? Опять ждать появления сообщений в очереди?
Здравствуйте, vf, Вы писали:
R>>Каким боком M&S queue является array-based?
vf>Нет, она не array-based, но мне почему-то кажется, что в array-based от обычной перейти всегда можно?! Ведь по логике — это скорее упрощение.
Ага, только не в мире lock-free.
Фишка динамических структур в контексте lock-free в том, что поток вначале полностью подготавливает узел (записывает в него данные сообщения, устанавливает другие указатели), а потом атомарно добавляет его одним CASом. С массивом это не пройдёт — поток не может просто так писать данные сообщения в какой-то элемент массива — при этом он будет конфликтовать с другими производителями, которые хотят записать свои сообщения туда же, будет конфликтовать с потребителями, которые уже хотят читать этот элемент.
R>>Плюс ещё добавь по 1 CAS на операцию на управление временем жизни узлов, т.к. алгоритм не работает без GC.
vf>Я думал это общий алгоритм, возможно что он и не подходит.
Добро пожаловать в мир "академического lock-free".
Я достаточно уверен, что это так. И никто пока не оспорил, что это не так.
Грубо говоря, linearizablе — это "ведёт себя как аналогичная структура данных, основанная на мьютексе". Если же для некоторых программ заменить мьютекс очередь на M&S очередь, то они начнут падать.
Эта моя очередь тоже не linearizablе.
R>>Это что за майкрософтовский подход? В любом случае это получается какой-то двойной стандарт. Ты думаешь свою инфраструктуру, ран-таймы, библиотеки для распараллеливания они на спинлоках делают? Отнюдь.
vf>Да, где проскакивало, что в 4.0 дот нете, tread-safe коллекции сделаны на spin-lock-ах. Опять же утверждать не буду, сам я не делал и рефлектором не смотрел.
Здравствуйте, remark, Вы писали:
R>>>Почему не блокирует? Блокирует. Если бы это была очередь на мьютексе, считай, что потребитель вызывает try_lock(), который возвращает ему false. Трактуй это так.
vf>>Здесь возникает не однозначность, я привык трактовать false возвращенный dequeue как отсутствие элементов в очереди. Дело даже не привычке, как различать два этих события? И тоже самое для enqueue?
R>А точно ли их надо различать? Как будет различаться обработка этих ситуаций в твоём случае?
Создание лишнего не дешевого объекта при dequeue, и зеркально удаление того который можно было бы поместить в очередь.
vf>>Я могу, но мне кажется мы просто щас уйдем от темы. Таких примеров где, нужно знать что очередь пуста или полна я думаю Вы и сами можете придумать. А вот где не нужно, я не могу придумать? Пусть некий сервер, с термином throughput-oriented я не знаком, что он кладет запросы на обработку в такую очередь? А что если она заполниться, производители устроят гонку добавляя элементы,
R>Их не интересует полна она или нет, их интересует можно класть сообщения в очередь или нет. Если нельзя, то какая особо разница почему. В любом случае можно выбрасывать сообщение, или ждать пока не станет можно класть.
Разница принципиальна, один случай когда очередь переполнена, разумный выход — убить запрос. А другой случай, когда из-за ньансов реализации очереди при приемлемой нагрузке пользователи начнут получать отлуп.
vf>>или наоборот когда пуста, как снизить кол-во "холостых" потребителей? R>Опять же какая разница, пуста она или нельзя получать сообщения по какой-то другой причине?
Такой пример я могу придумать, пусть хотя бы потоки обработчики не будут засыпать или убиваться в неподходящий момент неверно посчитав очередь пустой.
Я не могу придумать обратных примеров — когда различать не важно.
vf>>То есть полюбому вырисовывается механизм, который будет считать число элементов, хотя бы приблизительно.
R>Приблизительно считать в этой очереди можно — просто возьми enqueue — dequeue. Для какой-то статистики этой подойдёт. Однако, если поток хочет достать сообщение для обработки, и он видит, что очередь формально не пуста, но достать сообщение не может, то какая ему разница-то?
Ведь он же доставить не может из-за особенностей очереди — повторить попытку?! Вообще я считаю такое поведение очереди ошибочным, и что она должна обрабатывать такие ситуации внутри себя.
vf>>Конструктивное предложение — предлагаю добавить счетчик элеметов внутрь очереди, и нынешние функции dequeue/enqueue завернуть в цикл for(counter > 0)/for(counter<max) — тогда возвращаемы значения можно будет интерпретировать как принято для очереди.
R>А что будет делать поток, которому такой dequeue() вернёт false? Опять ждать появления сообщений в очереди?
Это абстрактный пример, я лишь пытаюсь найти случай где такую особенность можно считать обоснованной. Конктретно по вопросам, да поведение потока должно быть различно в этих ситуациях, если запрос из очереди не получен по вине очереди нужно повторить запрос, иначе можно не знаю — заснуть на каком нить евенте или вернуться в пул потоков.
Здравствуйте, vf, Вы писали:
vf>>>Здесь возникает не однозначность, я привык трактовать false возвращенный dequeue как отсутствие элементов в очереди. Дело даже не привычке, как различать два этих события? И тоже самое для enqueue?
R>>А точно ли их надо различать? Как будет различаться обработка этих ситуаций в твоём случае?
vf>Создание лишнего не дешевого объекта при dequeue, и зеркально удаление того который можно было бы поместить в очередь.
Т.е. если не удалось достать сообщение из очереди, и сообщений там нет, то ты не будешь создавать новый объект. А если не удалось достать сообщение из очереди, и ты бы знал, что сообщение там всё же есть, то, ты бы создал какой-то новый объект. Так? А точно это не так, что если не удалось достать сообщение из очереди, то ты создаёшь новый объект?
Здравствуйте, vf, Вы писали:
R>>Приблизительно считать в этой очереди можно — просто возьми enqueue — dequeue. Для какой-то статистики этой подойдёт. Однако, если поток хочет достать сообщение для обработки, и он видит, что очередь формально не пуста, но достать сообщение не может, то какая ему разница-то?
vf>Ведь он же доставить не может из-за особенностей очереди — повторить попытку?! Вообще я считаю такое поведение очереди ошибочным, и что она должна обрабатывать такие ситуации внутри себя.
Смысл? Повторишь попытку, а он опять недоступен. С тем же успехом ты можешь повторять попытки и когда она пуста, а вдруг производитель уже вошёл в функцию enqueue() и сразу уснул? А с большим успехом, мы говорим потоку, что тут сейчас ловить нечего — иди или спи, или позанимайся чем-нибудь другим полезным.
vf>>>Конструктивное предложение — предлагаю добавить счетчик элеметов внутрь очереди, и нынешние функции dequeue/enqueue завернуть в цикл for(counter > 0)/for(counter<max) — тогда возвращаемы значения можно будет интерпретировать как принято для очереди.
R>>А что будет делать поток, которому такой dequeue() вернёт false? Опять ждать появления сообщений в очереди?
vf>Это абстрактный пример, я лишь пытаюсь найти случай где такую особенность можно считать обоснованной. Конктретно по вопросам, да поведение потока должно быть различно в этих ситуациях, если запрос из очереди не получен по вине очереди нужно повторить запрос, иначе можно не знаю — заснуть на каком нить евенте или вернуться в пул потоков.
Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.
Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно... И теперь даже если ты приведёшь такой пример, ну что ж, в той специфической ситуации придётся использовать более дорогую очередь, а на все распространенные типа той, что ты пока привёл, хватит и такой очереди.
Здравствуйте, remark, Вы писали:
R>>>Приблизительно считать в этой очереди можно — просто возьми enqueue — dequeue. Для какой-то статистики этой подойдёт. Однако, если поток хочет достать сообщение для обработки, и он видит, что очередь формально не пуста, но достать сообщение не может, то какая ему разница-то?
vf>>Ведь он же доставить не может из-за особенностей очереди — повторить попытку?! Вообще я считаю такое поведение очереди ошибочным, и что она должна обрабатывать такие ситуации внутри себя.
R>Смысл? Повторишь попытку, а он опять недоступен. С тем же успехом ты можешь повторять попытки и когда она пуста, а вдруг производитель уже вошёл в функцию enqueue() и сразу уснул?
Абсолютно не с тем же, вероятность получить облом при наличии элементов в очереди очень небольшая и она ни как не равна вероятности появления новых объектов в пустой очереди. Я даже уверен, что в реальном приложении будет довольно сложно попасть на такое поведение очереди, но ситуация должна обрабатываться на мой взгляд.
vf>>>>Конструктивное предложение — предлагаю добавить счетчик элеметов внутрь очереди, и нынешние функции dequeue/enqueue завернуть в цикл for(counter > 0)/for(counter<max) — тогда возвращаемы значения можно будет интерпретировать как принято для очереди.
R>>>А что будет делать поток, которому такой dequeue() вернёт false? Опять ждать появления сообщений в очереди?
vf>>Это абстрактный пример, я лишь пытаюсь найти случай где такую особенность можно считать обоснованной. Конктретно по вопросам, да поведение потока должно быть различно в этих ситуациях, если запрос из очереди не получен по вине очереди нужно повторить запрос, иначе можно не знаю — заснуть на каком нить евенте или вернуться в пул потоков.
R>Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.
Разница в вероятности, новое сообщение в пустой очереди и успешная попытка вытащить имющийся элемент — не равновероятны.
R>Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно...
Из двух примеров, один — про пул объектов — не абстрактный. И в обоих примерах я вижу необходимость различной обработки. Что то мы переливаем из пустого в порожнее, предлагаю каждому остаться при своем мнении.
Здравствуйте, vf, Вы писали:
R>>Их не интересует полна она или нет, их интересует можно класть сообщения в очередь или нет. Если нельзя, то какая особо разница почему. В любом случае можно выбрасывать сообщение, или ждать пока не станет можно класть.
vf>Разница принципиальна, один случай когда очередь переполнена, разумный выход — убить запрос. А другой случай, когда из-за ньансов реализации очереди при приемлемой нагрузке пользователи начнут получать отлуп.
Ну так она и есть переполнена — производители дошли до элемента, который всё ещё не закончил потреблять *самый старый* потребитель.
Я не понимаю, почему ты в этом пытаешься увидеть плохое. Есть очереди, основанные на мьютексах, с поведением, которое ни у кого не вызывает вопросов. Эта очередь во всех отношениях ведёт себя только лучше. Ты подумай, что было бы если у тебя в мьютекс очереди поток заснул бы посреди операции добавления под мьютексом. Правильно — всё бы встало. Эта же очередь даём там, где это можно, другим потокам спокойно поработать. Например, можно потреблять из других частей очереди, можно добавлять элементы дальше. А блокировать работу других потоков она будет только там, где без этого абсолютно не обойтись.
Гляди, что происходит в этой очереди. Допустим очередь пустая. Приходит производитель, начинает класть сообщение в очередь, но перед тем, как установить seq, засыпает. Дальше приходит ещё один производитель и полностью кладёт сообщение в очередь (т.е. возвращается из enqueue()). Дальше приходит потребитель и не находит сообщения. Приходит ещё один потребитель и тоже не находит. Дальше первый тормозной производитель просыпается и устанавливает seq. Теперь возвращаются 2 наших потребителя и забирают сообщения. Правильно?
Теперь, что происходит в мьютекс-очереди. После того, как первый поток засыпает под мьютексом, все нафиг блокируются (первый негативный момент — второй производитель мог бы на самом деле положить сообщение). Дальше первый поток просыпается и освобождает мьютекс. Мьютекс захватывает первый потребитель и забирает сообщение (заметь не раньше чем в моей очереди! т.е. только после того, как первый производитель закончил). Теперь мьютекс захватывает второй потребитель и получает отбой — сообщений нет (второй негативный момент — в моей очереди он бы уже получил сообщение). Мьютекс захватывает второй производитель, кладёт сообщение. Мьютекс захватывает второй потребитель, берёт сообщение.
Ты берёшь за отправную точку, что сообщения в очереди есть, а моя очередь такая-плохая не даёт их забирать. Это не так. Отправная точка — это когда всё нафиг обламываются, а моя очередь наоборот даёт во многих ситуациях потокам успешно отработать без блокировки.
Когда приходит второй производитель у нас есть 2 выбора: (1) дать ему без блокировки спокойно положить сообщение и пойти заниматься другой полезной работой, или (2) заблокировать и его, не получив ничего взамен. Гляди, когда в очереди блокировки мьютекса заблокирован производитель с готовым сообщением, ты рассматриваешь это сообщение как уже произведённое? Нет? А почему? В чём отличие? Я просто вместо блокировки и переключения контекста даю ему "забуферизировать" своё сообщение.
Хорошо, как можно "исправить" мою очередь, что бы она получила "хорошее" с твоей т.з. поведение? Можно заблокировать второго производителя, что бы он вместо того, что бы положить сообщение в очередь и пойти заниматься полезным делом, бесполезно болтался на мьютексе. Тогда ты не будешь считать, что сообщение "уже произведено", правильно? И? Что ты получил кроме ухудшения ран-тайм свойств? Ничего. Мы стали чаще блокировать потоки, только для того, что бы ты не называл очередь такой-секой, не отдающий уже произведенные сообщения.
Т.е. всё, что мы будем делать, — это дополнительно задерживать некоторые потоки в некоторых местах, только что бы поведение выглядело более логичным для "однопоточного мозга программиста". Совершенно не будет такого, что какие сообщения вдруг станут доступны раньше, ничего подобного, дополнительные задержки не могу к этому привести.
Если ты привык работать с алгоритмами, основанными на мьютексах (которые под всеми имеющими смысл взглядами — однопоточные алгоритмы), то тебе надо немного поломать свой мозг, что бы понять как вещи происходят в действительно concurrent системах. Тут зачастую нету порядка между событиями, или сообщение потока может появиться в очереди через долго после того, как он вышел из enqueue() (мы просто не будет задерживать его до этого момента в enqueue()), и т.д.
Здравствуйте, vf, Вы писали:
vf>Абсолютно не с тем же, вероятность получить облом при наличии элементов в очереди очень небольшая и она ни как не равна вероятности появления новых объектов в пустой очереди. Я даже уверен, что в реальном приложении будет довольно сложно попасть на такое поведение очереди, но ситуация должна обрабатываться на мой взгляд.
Вероятность вероятностью, а обрабатывать-то ты будешь одинаково — ждать доступности сообщения, или занять поток другой работой. И зачем тебе этот признак?
R>>Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.
vf>Разница в вероятности, новое сообщение в пустой очереди и успешная попытка вытащить имющийся элемент — не равновероятны.
Вопрос был другой — как отличается обработка?
Или ты хочешь вставить в код:
if (message_is_unavailable_but_the_queue_is_not_empty)
be_happy_most_likely_I_will_get_a_message_soon();
R>>Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно...
vf>Из двух примеров, один — про пул объектов — не абстрактный. И в обоих примерах я вижу необходимость различной обработки. Что то мы переливаем из пустого в порожнее, предлагаю каждому остаться при своем мнении.
Здравствуйте, remark, Вы писали:
R>Хорошо, как можно "исправить" мою очередь, что бы она получила "хорошее" с твоей т.з. поведение?
По-моему, это можно решить счётчиком производителей. Будет два дополнительных CAS в enqueue, вне цикла. Тогда dequeue сможет возвращать одно из значений перечисления — OK, empty, busy, а внешний код, соответственно, реагировать либо повтором попытки, либо переходом к другим занятиям. Немного замедлится enqueue, но зато, возможно, получится выигрыш во внешнем по отношению к очереди коде.
"Нормальные герои всегда идут в обход!"
