Здравствуйте, 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>
