Lock free algorithm question

[Marmot]

Народ, может кто знает, никак найти не могу:
Есть 2 CAS переменные, надо сделать одновременный CAS на обе, как?

[aissp]

если они 4 байтовый то можно сделать один 8 байтовый cas а в общем чегой то не припоминается такого трюка правда я не очень долго про ети алгоритмы читал

[Marmot]

если они 4 байтовый то можно сделать один 8 байтовый cas а в общем чегой то не припоминается такого трюка правда я не очень долго про ети алгоритмы читал

А оне у меня независимые, типа есть 100К переменных, из ин их случайно(почти) выбирается пара над которой надо сделать совместный CAS...
Блин, написали всего столько про lock free алгоритмы, а такого простого случая даже никто не рассматривал
Или это в принципе невозможно...

[Anton]

Вот что нашел - даже для >2 переменных, но довольно хитро http://citeseerx.ist.psu.edu/viewdoc/su ... .1.13.7938

[Marmot]

Вот что нашел - даже для >2 переменных, но довольно хитро http://citeseerx.ist.psu.edu/viewdoc/su ... .1.13.7938

Мдя..., это называется не хитро,а через жопу, ну да ладно, бум читать и думать...
Спасибо.

[aissp]

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

[Marmot]

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

X3 если честно, только после разгребания дедлока из выстроившихся в стройную цепочку 4 потоков мне это все надоело...
Проблема в то, что у меня многопоточный скриптинг, ограничить который очень сложно, либо очень coarse grained locking с потерей производительности, либо дедлоки эти сумашедшие...
А заставлять скриптологов думать о локах и потоках, то не для этого все это делается, а совсем даже наоборот

[aissp]

стало яснее. май опинион, я бы забыл о лок фрее в такой ситуации. по результату сообщи интересно

[sobomax]

если они 4 байтовый то можно сделать один 8 байтовый cas а в общем чегой то не припоминается такого трюка правда я не очень долго про ети алгоритмы читал

А оне у меня независимые, типа есть 100К переменных, из ин их случайно(почти) выбирается пара над которой надо сделать совместный CAS...
Блин, написали всего столько про lock free алгоритмы, а такого простого случая даже никто не рассматривал
Или это в принципе невозможно...

IMHO не нужен тебе lock free. Поставь spin lock на весь массив из 100K переменных и обменяй те две что тебе надо "без шуму и пыли". Если у тебя меньше чем десять тысяч тридов и триды делают что-либо еще кроме обмена переменными то подобный лок в 99.9999% случаев срабатывать не будет а значит потери производительности тоже никакой не произойдет.

-Maxim

[Marmot]

если они 4 байтовый то можно сделать один 8 байтовый cas а в общем чегой то не припоминается такого трюка правда я не очень долго про ети алгоритмы читал

А оне у меня независимые, типа есть 100К переменных, из ин их случайно(почти) выбирается пара над которой надо сделать совместный CAS...
Блин, написали всего столько про lock free алгоритмы, а такого простого случая даже никто не рассматривал
Или это в принципе невозможно...

IMHO не нужен тебе lock free. Поставь spin lock на весь массив из 100K переменных и обменяй те две что тебе надо "без шуму и пыли". Если у тебя меньше чем десять тысяч тридов и триды делают что-либо еще кроме обмена переменными то подобный лок в 99.9999% случаев срабатывать не будет а значит потери производительности тоже никакой не произойдет.

-Maxim

Неа, те две, это только упрощенное по самое нехочу требование дял формулировки вопроса , на самом деле там таких обменов может быть мама негорюй, так что глобальный лок это несерьезно. Главная проблема в том, что решение что и как менять принимается в скриптах, на которые накладываются только очень небольшие ограничения. Т.е. или скрипты выполнять в (почти)глобальном локе, и тогда они просто все остановят, либo разбрасывать мелкие локи внутри и снаружи скриптов вокруг критичных операций с риском влетететь в дедлок ну или делать lock free...

[aissp]

еще одна возможность, выташить переменную из списка можно лок фри. вытаскиваешь обе делаешь с ними что надо вставляешь в зад

[Marmot]

еще одна возможность, выташить переменную из списка можно лок фри. вытаскиваешь обе делаешь с ними что надо вставляешь в зад

А что должен делать поток, которуму в это время тоже нужна одна, или обе из эти переменных?
ждать?

[aissp]

вставлять новые или искать их (ето так просто фантазии )

без лок фри ето рещается следующим образом. лок всей таблицы, получение пойнтеров с каунтером типа shared_ptr (чтобы ни одна собака не потрела) на интересуюшие переменные, отпускание лока таблицы, лок переменных в порядке от меньшего к большему.

[Marmot]

вставлять новые или искать их (ето так просто фантазии )

без лок фри ето рещается следующим образом. лок всей таблицы, получение пойнтеров с каунтером типа shared_ptr (чтобы ни одна собака не потрела) на интересуюшие переменные, отпускание лока таблицы, лок переменных в порядке от меньшего к большему.

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

[aissp]

ну так не тяни вола - публикуй всю задачу обещаю идею непатентовать