Re[12]: Concurrency & Linearizability
От: remark Россия http://www.1024cores.net/
Дата: 25.10.10 08:50
Оценка:
Здравствуйте, Jolly Roger, Вы писали:

R>>Хорошо, как можно "исправить" мою очередь, что бы она получила "хорошее" с твоей т.з. поведение?


JR>По-моему, это можно решить счётчиком производителей. Будет два дополнительных CAS в enqueue, вне цикла. Тогда dequeue сможет возвращать одно из значений перечисления — OK, empty, busy, а внешний код, соответственно, реагировать либо повтором попытки, либо переходом к другим занятиям. Немного замедлится enqueue, но зато, возможно, получится выигрыш во внешнем по отношению к очереди коде.


Счётчики уже есть — это enqueue_ и dequeue_, через их разницу можно понять. Но речь не об этом, речь о том, что сделать это можно, но это будет бессмысленное усложнение АПИ. Если есть другая работать поделать, то делаем её, зачем вообще ждать. Иначе, попробовать ещё несколько раз имеет смысл *всегда*, т.к. это дешевле переключения потока. Пробовать бесконечное число раз не имеет смысл *никогда*, т.к. это чрезмерно прожигает такты.
З.ы. а за два дополнительных CAS можно поиметь и lock-free очередь без таких нюансов... только это будет еже компромиссное решение относительно мьютекса — медленнее, но lock-free. Моя же очередь win-win относительно мьютекса — и быстрее, и по по гарантиям прогресса лучше.


1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[13]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 25.10.10 09:02
Оценка:
Здравствуйте, remark, Вы писали:

R>Здравствуйте, vf, Вы писали:


vf>>Абсолютно не с тем же, вероятность получить облом при наличии элементов в очереди очень небольшая и она ни как не равна вероятности появления новых объектов в пустой очереди. Я даже уверен, что в реальном приложении будет довольно сложно попасть на такое поведение очереди, но ситуация должна обрабатываться на мой взгляд.


R>Вероятность вероятностью, а обрабатывать-то ты будешь одинаково — ждать доступности сообщения, или занять поток другой работой. И зачем тебе этот признак?


Нет, я же писал, что я буду обрабатывать по разному, если элементы есть то в твоей терминалогии я буду "ждать доступности сообщения", а если их нет "занять поток другой работой".

R>>>Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.


Если он заблокируется на бесконечных попытках — то да это фигня, но это проблемы очереди, но я все же считаю что такое маловероятно, и при малом числе повторных попыток получить элемент поток его все таки получит. Ты же предлагаешь менять архитектуру приложения под очередь, причем под маловероятное событие в этой очереди. Во первых не всегда возможно, во вторых в данном случае не обосновано.

R>Или ты хочешь вставить в код:

R>
R>if (message_is_unavailable_but_the_queue_is_not_empty)
R>  be_happy_most_likely_I_will_get_a_message_soon();
R>


Вот так, причем хочу я его вставить в саму очередь:

while (message_is_unavailable_but_the_queue_is_not_empty)
  item = queue.get();



R>>>Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно...


vf>>Из двух примеров, один — про пул объектов — не абстрактный. И в обоих примерах я вижу необходимость различной обработки. Что то мы переливаем из пустого в порожнее, предлагаю каждому остаться при своем мнении.


R>Ну так ты покажи, как бы у тебя код различался.


while(x == null)
{
if(queue.isEmpty)
x = create_expensive_object();
else
x = queue.cheap_try_to_get_item();
}
Re[13]: Concurrency & Linearizability
От: Jolly Roger  
Дата: 25.10.10 09:07
Оценка:
Здравствуйте, remark, Вы писали:

R>Счётчики уже есть — это enqueue_ и dequeue_, через их разницу можно понять.


Ну да, можно и так

R>Но речь не об этом, речь о том, что сделать это можно, но это будет бессмысленное усложнение АПИ.


Да я-то с Вами согласен. Просто хотел сказать, что раз уж vf непременно это нужно, то, в принципе, можно и сделать относительно недорого.
"Нормальные герои всегда идут в обход!"
Re[14]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 25.10.10 09:16
Оценка:
Здравствуйте, vf, Вы писали:

R>>Вероятность вероятностью, а обрабатывать-то ты будешь одинаково — ждать доступности сообщения, или занять поток другой работой. И зачем тебе этот признак?


vf>Нет, я же писал, что я буду обрабатывать по разному, если элементы есть то в твоей терминалогии я буду "ждать доступности сообщения", а если их нет "занять поток другой работой".


Если есть другая работа, то надо занимать ей поток сразу. Вероятность вероятностью, а можно очень долго ждать сообщения, которое вроде как в очереди; и с другой стороны можно очень быстро получить сообщение, которого ещё нет в очереди. Это действительно не должно делать принципиальной разницы.



R>>>>Иии где разница? В обоих случаях ждём пока следующее сообщение не станет доступно. Только если мы заблокируем поток на бесконечных попытках будет фигня, что пока он мог бы заняться чем-то другим полезным (например взять сообщение из другой очереди), но будет зазря прожигать такты.


vf>Если он заблокируется на бесконечных попытках — то да это фигня, но это проблемы очереди, но я все же считаю что такое маловероятно, и при малом числе повторных попыток получить элемент поток его все таки получит. Ты же предлагаешь менять архитектуру приложения под очередь, причем под маловероятное событие в этой очереди. Во первых не всегда возможно, во вторых в данном случае не обосновано.


Я не предлагаю менять архитектуру, наоборот, я говорю, что не надо различать эти ситуации вообще.


R>>Или ты хочешь вставить в код:

R>>
R>>if (message_is_unavailable_but_the_queue_is_not_empty)
R>>  be_happy_most_likely_I_will_get_a_message_soon();
R>>


vf>Вот так, причем хочу я его вставить в саму очередь:


vf>
vf>while (message_is_unavailable_but_the_queue_is_not_empty)
vf>  item = queue.get();
vf>


Ну у тебя сейчас есть код:
while (queue_is_empty)
  item = queue.get();

который есть надмножество этого. Ничего больше делать не надо. QED.


R>>>>Ну приведи не абстрактный пример. Я пока не вижу, что это было нужно...


vf>>>Из двух примеров, один — про пул объектов — не абстрактный. И в обоих примерах я вижу необходимость различной обработки. Что то мы переливаем из пустого в порожнее, предлагаю каждому остаться при своем мнении.


R>>Ну так ты покажи, как бы у тебя код различался.


vf>while(x == null)

vf>{
vf>if(queue.isEmpty)
vf> x = create_expensive_object();
vf>else
vf> x = queue.cheap_try_to_get_item();
vf>}

Замени это на:
for (int try = 0; try != TRY_COUNT; try += 1)
{
  if (x = queue.cheap_try_to_get_item())
    break;
}
if (x == null)
  x = create_expensive_object();


и будет тебе счастье. Во-первых, даёшь некоторый шанс всё же вытащить объект из очереди даже если она пуста (хорошо — объект тяжёлый). Во-вторых, устраняешь неограниченное ожидание "мифического" объекта (хорошо — десятки потоков наяривающих в спин цикле в ожидании потока, вытесненного более высоко-приоритетным, отнюдь не весёлое зрелище). Различать ситуации нет надо. QED.


1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[11]: Concurrency & Linearizability
От: vf  
Дата: 25.10.10 09:30
Оценка:
Здравствуйте, remark, Вы писали:

R>Здравствуйте, vf, Вы писали:


R>>>Их не интересует полна она или нет, их интересует можно класть сообщения в очередь или нет. Если нельзя, то какая особо разница почему. В любом случае можно выбрасывать сообщение, или ждать пока не станет можно класть.


vf>>Разница принципиальна, один случай когда очередь переполнена, разумный выход — убить запрос. А другой случай, когда из-за ньансов реализации очереди при приемлемой нагрузке пользователи начнут получать отлуп.


R>Ну так она и есть переполнена — производители дошли до элемента, который всё ещё не закончил потреблять *самый старый* потребитель.

R>Я не понимаю, почему ты в этом пытаешься увидеть плохое. Есть очереди, основанные на мьютексах, с поведением, которое ни у кого не вызывает вопросов. Эта очередь во всех отношениях ведёт себя только лучше. Ты подумай, что было бы если у тебя в мьютекс очереди поток заснул бы посреди операции добавления под мьютексом. Правильно — всё бы встало. Эта же очередь даём там, где это можно, другим потокам спокойно поработать. Например, можно потреблять из других частей очереди, можно добавлять элементы дальше. А блокировать работу других потоков она будет только там, где без этого абсолютно не обойтись.

Вот здесь принципиальный момент — нельзя потреблять из других частей очереди, можно только добавлять!

R>Гляди, что происходит в этой очереди. Допустим очередь пустая. Приходит производитель, начинает класть сообщение в очередь, но перед тем, как установить seq, засыпает. Дальше приходит ещё один производитель и полностью кладёт сообщение в очередь (т.е. возвращается из enqueue()). Дальше приходит потребитель и не находит сообщения. Приходит ещё один потребитель и тоже не находит. Дальше первый тормозной производитель просыпается и устанавливает seq. Теперь возвращаются 2 наших потребителя и забирают сообщения. Правильно?


Правильно, только оцени затраты на ушел пришел и вероятность того что производитель заснул (скорее всего просто шестеренки не так встали), и какой смысл уходить-возвращаться потребителям в этой ситуации, когда каждый из них с очень большой вероятностью повторив попытку получить положительный ответ??? Так еще и архитектура приложения не слабо портиться из-за ушел-пришел, и ведь где-то там куда они ушли им все равно нужно будет как-то учитывать кол-во элементов, чтобы знать что нужно прийти, разве не так?

R>Теперь, что происходит в мьютекс-очереди. После того, как первый поток засыпает под мьютексом, все нафиг блокируются (первый негативный момент — второй производитель мог бы на самом деле положить сообщение). Дальше первый поток просыпается и освобождает мьютекс. Мьютекс захватывает первый потребитель и забирает сообщение (заметь не раньше чем в моей очереди! т.е. только после того, как первый производитель закончил). Теперь мьютекс захватывает второй потребитель и получает отбой — сообщений нет (второй негативный момент — в моей очереди он бы уже получил сообщение). Мьютекс захватывает второй производитель, кладёт сообщение. Мьютекс захватывает второй потребитель, берёт сообщение.


Про мьютексы никто не спорит. Если выбирать между lock vs. lock-free я за lock-free

R>Ты берёшь за отправную точку, что сообщения в очереди есть, а моя очередь такая-плохая не даёт их забирать. Это не так. Отправная точка — это когда всё нафиг обламываются, а моя очередь наоборот даёт во многих ситуациях потокам успешно отработать без блокировки.


Это не нормальное поведени для очереди в класическом ее понимании, как минимум на это нужно было указать в первом посте. Если она себя так ведет то это не совсем очередь. Помимо поток и блокировок, существуют еще данные, вот я приводил пример с сервером, приходит запрос поток пытается положить его в очередь и обламывается, что он должен сделать? Дать отлуп пользователю, при небольшой нагрузке, или куда деть данные чтобы заняться другими вещами??!

R>Когда приходит второй производитель у нас есть 2 выбора: (1) дать ему без блокировки спокойно положить сообщение и пойти заниматься другой полезной работой, или (2) заблокировать и его, не получив ничего взамен. Гляди, когда в очереди блокировки мьютекса заблокирован производитель с готовым сообщением, ты рассматриваешь это сообщение как уже произведённое? Нет? А почему? В чём отличие? Я просто вместо блокировки и переключения контекста даю ему "забуферизировать" своё сообщение.


Где забуферизировать?! У нас очередь для этого, ты предлагаешь городить другой паралельный механизм? Не проще ли повторить попытку?

R>Хорошо, как можно "исправить" мою очередь, что бы она получила "хорошее" с твоей т.з. поведение? Можно заблокировать второго производителя, что бы он вместо того, что бы положить сообщение в очередь и пойти заниматься полезным делом, бесполезно болтался на мьютексе. Тогда ты не будешь считать, что сообщение "уже произведено", правильно? И? Что ты получил кроме ухудшения ран-тайм свойств? Ничего. Мы стали чаще блокировать потоки, только для того, что бы ты не называл очередь такой-секой, не отдающий уже произведенные сообщения.


Я предлагаю не блокировать, я предлагаю повторять попытки.
Каким полезным делом куда потоку данные пристроить? Выкнуть?

R>Т.е. всё, что мы будем делать, — это дополнительно задерживать некоторые потоки в некоторых местах, только что бы поведение выглядело более логичным для "однопоточного мозга программиста". Совершенно не будет такого, что какие сообщения вдруг станут доступны раньше, ничего подобного, дополнительные задержки не могу к этому привести.


R>Если ты привык работать с алгоритмами, основанными на мьютексах (которые под всеми имеющими смысл взглядами — однопоточные алгоритмы), то тебе надо немного поломать свой мозг, что бы понять как вещи происходят в действительно concurrent системах. Тут зачастую нету порядка между событиями, или сообщение потока может появиться в очереди через долго после того, как он вышел из enqueue() (мы просто не будет задерживать его до этого момента в enqueue()), и т.д.


Ну.. я привык считать приложения с несколькими потоками — многопоточными, а мьютексы или lock-free это лишь способы синхронизации.
Re[10]: О lock-free алгоритмах (+бонус)
От: Lexey Россия  
Дата: 25.10.10 09:40
Оценка:
Здравствуйте, vf, Вы писали:

vf>Я разбираюсь с алгоритмом, увидел случай который мне показался подозрительным, попытался продемонстрировать когда может возникать, использовал разумные упрощения и допущения. О чем ты споришь???? Я что предлагал в программе заменить size_t на что-то еще?!


Да не спорю я уже не о чем. Просто то, что ты считал подозрительным, для меня было самоочевидным. Зато уменьшение размерности рождает другие подозрения.

vf>Там нет таких случаев, если ты про ABA.


Что такое ABA?

vf>Я ничего не вношу уменьшая модуль, по крайней мере я не нашел, может ты обоснуешь то что утверждаешь, примером? Возьми минимальные модуль и покажи как это негативно отразилось на алгоритме? А то бла-бла-бла...


В том конкретном примере не вносишь, потому что у тебя размер очереди — степень двойки (важность этого момента я изначально не заметил). Если его взять нечетным (например, 15), то будет весело. В случае же нормального размера sequence_number размер очереди практически не роляет.
"Будь достоин победы" (c) 8th Wizard's rule.
Re[15]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 25.10.10 09:51
Оценка:
vf>>while(x == null)
vf>>{
vf>>if(queue.isEmpty)
vf>> x = create_expensive_object();
vf>>else
vf>> x = queue.cheap_try_to_get_item();
vf>>}

R>Замени это на:

R>
R>for (int try = 0; try != TRY_COUNT; try += 1)
R>{
R>  if (x = queue.cheap_try_to_get_item())
R>    break;
R>}
R>if (x == null)
R>  x = create_expensive_object();
R>


R>и будет тебе счастье. Во-первых, даёшь некоторый шанс всё же вытащить объект из очереди даже если она пуста (хорошо — объект тяжёлый). Во-вторых, устраняешь неограниченное ожидание "мифического" объекта (хорошо — десятки потоков наяривающих в спин цикле в ожидании потока, вытесненного более высоко-приоритетным, отнюдь не весёлое зрелище). Различать ситуации нет надо. QED.


Это уже вопрос деталей, а именно величины TRY_COUNT = [1..INFINITY], а зависит она от стоимости объекта и вероятности облома при повторной попытке, я вероятность оцениваю как стремящуюся к нулю(даже в твоем примере с высоко-приоритетном потоком), и зависимость здесь обратнопропорциональная следовательно TRY_COUNT -> INF
Re[11]: О lock-free алгоритмах (+бонус)
От: ilnar Россия  
Дата: 25.10.10 09:53
Оценка: 8 (1)
Здравствуйте, Lexey, Вы писали:

L>Здравствуйте, vf, Вы писали:


vf>>Я разбираюсь с алгоритмом, увидел случай который мне показался подозрительным, попытался продемонстрировать когда может возникать, использовал разумные упрощения и допущения. О чем ты споришь???? Я что предлагал в программе заменить size_t на что-то еще?!


L>Да не спорю я уже не о чем. Просто то, что ты считал подозрительным, для меня было самоочевидным. Зато уменьшение размерности рождает другие подозрения.


vf>>Там нет таких случаев, если ты про ABA.


L>Что такое ABA?

http://en.wikipedia.org/wiki/ABA_problem

vf>>Я ничего не вношу уменьшая модуль, по крайней мере я не нашел, может ты обоснуешь то что утверждаешь, примером? Возьми минимальные модуль и покажи как это негативно отразилось на алгоритме? А то бла-бла-бла...


L>В том конкретном примере не вносишь, потому что у тебя размер очереди — степень двойки (важность этого момента я изначально не заметил). Если его взять нечетным (например, 15), то будет весело. В случае же нормального размера sequence_number размер очереди практически не роляет.
Re[3]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 25.10.10 14:59
Оценка:
Здравствуйте, remark, Вы писали:

R>Код в студию!


Здесь
Автор: vf
Дата: 25.10.10
выложил, баги вычистил вроде.
Re[9]: О lock-free алгоритмах (+бонус)
От: vf  
Дата: 25.10.10 19:52
Оценка:
Здравствуйте, remark, Вы писали:

R>>>Да, и кстати, она не фига не linearizable, как они это утверждают и даже вроде как "доказывают". Подробнее я описывал тут:

R>>>http://groups.google.com/group/comp.programming.threads/browse_frm/thread/8344b10e0deb18dc

vf>>Если это так, тогда совсем плохо.


R>Я достаточно уверен, что это так. И никто пока не оспорил, что это не так.

R>Грубо говоря, linearizablе — это "ведёт себя как аналогичная структура данных, основанная на мьютексе". Если же для некоторых программ заменить мьютекс очередь на M&S очередь, то они начнут падать.
R>Эта моя очередь тоже не linearizablе.

Прочитал этот тред, но это более частный случай, аппонент твой не согласился, да и объективно M&S гораздо ближе к linerizable. А где он конкретно спотыкается, что происходит при удалении очереди?
Re[10]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 28.10.10 03:44
Оценка:
Здравствуйте, vf, Вы писали:

R>>Я достаточно уверен, что это так. И никто пока не оспорил, что это не так.

R>>Грубо говоря, linearizablе — это "ведёт себя как аналогичная структура данных, основанная на мьютексе". Если же для некоторых программ заменить мьютекс очередь на M&S очередь, то они начнут падать.
R>>Эта моя очередь тоже не linearizablе.

vf>Прочитал этот тред, но это более частный случай, аппонент твой не согласился, да и объективно M&S гораздо ближе к linerizable. А где он конкретно спотыкается, что происходит при удалении очереди?


Мой аргумент очень простой — вот пример кода, который прекрасно работает с мьютекс-очередью, заменяем её на M&S очередь — начинает падать. А это есть основное практическое следствие из linearizability — можно спокойно так заменять и не должно быть никаких видимых изменений в поведении. Они доказывали свойство linearizability в неком академическом абстрактном коне в вакууме, в котором объекты не создаются и не удаляются динамически.

struct tcp_connection
{
  queue_t q;
  ...

};

void connection_thread(tcp_connection* c)
{
  for (;;)
  {
    msg_t* m = c->dequeue();
    if (m->type == MSG_DISCONNECT)
    {
      delete c;
      return;
    }
    process(m);
  }

}

void io_dispatch_thread()
{
  for (;;)
  {
    select(...);
    for_each(SOCKET s in read_set)
    {
      recv(s, buf, size);
      tcp_connection* c = find_connection(s);
      c->enqueue(msg_t(MSG_PACKET, data, size));
    }
    for_each(SOCKET s in exception_set)
    {
      tcp_connection* c = find_connection(s);
      c->enqueue(msg_t(MSG_DISCONNECT));
    }
  }
}



1024cores — all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[9]: c# array-based Michael & Scott queue
От: vf  
Дата: 01.11.10 09:05
Оценка:
Здравствуйте, remark, Вы писали:

R>Ага, только не в мире lock-free.


http://rsdn.ru/forum/src/4019420.1.aspx собственно.
Re[10]: c# array-based Michael & Scott queue
От: vf  
Дата: 01.11.10 09:06
Оценка:
Здравствуйте, vf, Вы писали:

Урл с названием попутал

Subj
Автор: vf
Дата: 31.10.10
собственно.
Re: О lock-free алгоритмах (+бонус)
От: brankovic  
Дата: 23.04.11 12:38
Оценка:
Здравствуйте, remark, Вы писали:

R>сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера


1. Честно прочитал тред.. правильно я понял, что алгоритм формально не lock-free, и не obstruction-free? Т.е. местами возникает подобие спинлока, так? (Википедия: Lock-freedom allows individual threads to starve but guarantees system-wide throughput.)

2. В связи с этим у меня есть вопрос: насколько это продакшн-реди, тестировалась ли производительность, есть ли опыт применения? Работаю с приложением, которое почти полностью состоит из разных локовых очередей. Оно бешено свитчится и тормозит (в топ не вылазит, но обрабатывать не успевает). Думаю, реально ли перейти на локфри малой кровью.
Re: О lock-free алгоритмах (+бонус)
От: pif_pif  
Дата: 24.04.11 20:17
Оценка:
Есть подозрение, что этот алгоритм не свободет от data race. Т.е. между этой строкой
intptr_t dif = (intptr_t)seq — (intptr_t)pos;
и этой проверкой
if (dif == 0)
значение pos может быть изменено в другом потоке, и проверка будет не валидной. Intel Parallel Inspector это подтверждает:
ID Description Problem Source Function Module State
X7 Read Data race lockfree.cpp:24 load lockfree.exe Not fixed
X9 Write Data race lockfree.cpp:41 store lockfree.exe Not fixed
X6 Write Data race lockfree.cpp:48 compare_exchange_weak lockfree.exe Not fixed
X8 Allocation site Data race newaop.cpp:7 new[] lockfree.exe Information

Код для теста использовался такой:

tbb_thread* tbbthrd_en[10];
for(int i=0;i<10;i++)
{
tbbthrd_en[i]=new tbb_thread(thrd_en);
}
for(int i=0;i<10;i++)
{
tbbthrd_en[i]->join();
}
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 25.04.11 06:45
Оценка:
Здравствуйте, brankovic, Вы писали:

B>Здравствуйте, remark, Вы писали:


R>>сразу скажу о бонусе — это простой и эффективный алгоритм очереди на основе буфера фиксированного размера


B>1. Честно прочитал тред.. правильно я понял, что алгоритм формально не lock-free, и не obstruction-free? Т.е. местами возникает подобие спинлока, так? (Википедия: Lock-freedom allows individual threads to starve but guarantees system-wide throughput.)


Да, всё правильно. Пока поток работает с ячейкой (копирует в неё или из неё), она фактически залочена.


B>2. В связи с этим у меня есть вопрос: насколько это продакшн-реди, тестировалась ли производительность, есть ли опыт применения? Работаю с приложением, которое почти полностью состоит из разных локовых очередей. Оно бешено свитчится и тормозит (в топ не вылазит, но обрабатывать не успевает). Думаю, реально ли перейти на локфри малой кровью.


Тут нет ничего, что бы делало его не "продакш-реди". Попробуй её вставить и увидишь


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[2]: О lock-free алгоритмах (+бонус)
От: remark Россия http://www.1024cores.net/
Дата: 25.04.11 06:47
Оценка:
Здравствуйте, pif_pif, Вы писали:

_>Есть подозрение, что этот алгоритм не свободет от data race. Т.е. между этой строкой

_> intptr_t dif = (intptr_t)seq — (intptr_t)pos;
_>и этой проверкой
_> if (dif == 0)
_>значение pos может быть изменено в другом потоке, и проверка будет не валидной.

Тогда последующий CAS не сработает.

_> Intel Parallel Inspector это подтверждает:

_>ID Description Problem Source Function Module State
_>X7 Read Data race lockfree.cpp:24 load lockfree.exe Not fixed
_>X9 Write Data race lockfree.cpp:41 store lockfree.exe Not fixed
_>X6 Write Data race lockfree.cpp:48 compare_exchange_weak lockfree.exe Not fixed
_>X8 Allocation site Data race newaop.cpp:7 new[] lockfree.exe Information


Inspector не умеет проверять такой код.


1024cores &mdash; all about multithreading, multicore, concurrency, parallelism, lock-free algorithms
Re[3]: О lock-free алгоритмах (+бонус)
От: pif_pif  
Дата: 25.04.11 09:51
Оценка:
Насколько я понял код, dequeue_pos_ и enqueue_pos_ двигаются в одну сторону по buffer_ и нигде нет проверки того, что они не совпали (или dequeue_pos_ > enqueue_pos_). Parallel Inspector совершенно прав, что между enquee и dequee существует data race — из обеих функции есть несинхронизированный доступ к buffer_. Следовательно, мы можем вынимать из очереди несуществующие элементы, которые не были поставлены в очередь. Вы уверены, что такая очередь востребована?
Re[4]: О lock-free алгоритмах (+бонус)
От: pif_pif  
Дата: 25.04.11 14:33
Оценка:
Здравствуйте, pif_pif, Вы писали:

_>Насколько я понял код, dequeue_pos_ и enqueue_pos_ двигаются в одну сторону по buffer_ и нигде нет проверки того, что они не совпали (или dequeue_pos_ > enqueue_pos_). Parallel Inspector совершенно прав, что между enquee и dequee существует data race — из обеих функции есть несинхронизированный доступ к buffer_. Следовательно, мы можем вынимать из очереди несуществующие элементы, которые не были поставлены в очередь. Вы уверены, что такая очередь востребована?


Разобрался в коде, дезавуирую "мы можем вынимать из очереди несуществующие элементы, которые не были поставлены в очередь". На счет датарейсов пока сказать не могу, продолжаю анализировать.
Re: О lock-free алгоритмах (+бонус)
От: _nn_ www.nemerleweb.com
Дата: 27.04.11 08:47
Оценка:
Здравствуйте, remark, Вы писали:

R>Теперь обещанный бонус — алгоритм bounded multi-producer/multi-consumer очереди без блокировок. Контейнер не использует динамического выделения/управления памятью в процессе работы (за исключением изначального выделения фиксированного буфера).


А под какой лицензией выкладывается этот код ?
http://rsdn.nemerleweb.com
http://nemerleweb.com
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.