Здравствуйте, Константин Л., Вы писали:

R>>lock-free алгоритмы — это не о производительности и масштабируемости, это исключительно о гарантиях системного прогресса. lock-free алгоритмы зачастую бывают медленнее lock-based алгоритмов. Это как best-effort против QoS, или не real-time против real-time. QoS и real-time всегда медленнее, зато дают дополнительные гарантии.

КЛ>почему медленнее и о каких гарантиях идет речь


Вначале формальные определения:

wait-free

Каждый поток продвигается вперед не зависимо от внешних факторов (конкуренции со стороны других потоков, факта блокирования других потоков). Это самая сильная гарантия. Обычно это означает, что используются только такие примитивы как atomic_exchange, atomic_increment, atomic_fetch_and_add (InterlockedExchange, InterlockedIncrement, InterlockedExchangeAdd), и в алгоритме нет циклов, на выполнение которых могут повлиять другие потоки. atomic_compare_exchange (InterlockedCompareExchange) обычно не используется, т.к. с ним обычно связан цикл вида "выполнять atomic_compare_exchange, пока он не будет выполнен успешно".
Пример wait-free алгоритма:

void increment_reference_counter(rc_base* obj)
{
  atomic_increment(obj->rc);
}

void decrement_reference_counter(rc_base* obj)
{
  if (0 == atomic_decrement(obj->rc))
    delete obj;
}

Как видно, любой поток может выполнить эти функции за конечное число шагов, не зависимо ни от чего.

lock-free

Система в целом продвигается вперед. При этом каждый отдельный поток может не совершать продвижения вперед. Это более слабая гарантия, чем wait-free. Обычно используется примитив atomic_compare_exchange (InterlockedCompareExchange).
Пример lock-free алгоритма:

void stack_push(stack* s, node* n)
{
  node* head;
  do
  {
    head = s->head;
    n->next = head;
  }
  while (!atomic_compare_exchange(s->head, head, n));
}

Как видно, любой поток может "крутиться" в этом цикле теоретически бесконечно. НО любой повтор этого цикла означает, что какой-то другой поток *успешно* выполнил свою операцию. И никакой заблокированный/прерванный поток *не* может препятствовать продвижению других потоков. Отсюда следует, что система в целом продвигается вперед не зависимо ни от чего.

obstruction-free

Поток продвигается вперед, только если не встречает конкуренции со стороны других потоков. В частности это означает, что при сильной конкуренции возможно *никакой* поток не будет совершать продвижения. Т.е. система будет находиться в т.н. live-lock. Это самая слабая гарантия. Этот класс алгоритмов может показаться немного странным, поэтому тут стоит заметить, что (1) заблокированные/прерванные потоки не могут препятствовать прогрессу других потоков, и (2) obstruction-free алгоритмы могут быть более быстрые, чем lock-free.
Простого примера тут не привести, поэтому отсылаю интересующихся к оригиналу:
Obstruction-Free Synchronization: Double-Ended Queues as an Example

lock-based

Ну и собственно все эти алгоритмы противопоставляются lock-based алгоритмам:
Система в целом может *не* продвигаться вперед. Например, поток прерван внутри критической секции, этот поток может заблокировать общесистемный прогресс, т.е. никакой выполняющийся поток не может выполнить никаких полезных действий. Или например, при использовании lock-based алгоритмов возможен т.н. dead-lock, очевидно, что при возникновении dead-lock система не совершает прогресса.

Производительность/масштабируемость

Самое интересное — до этого момента я не сказал ни слова ни о производительности, ни о масштабируемости. Всё правильно — все эти слова ни об этом. Они о гарантиях, которые я описал выше. Так как же lock-free (wait-free, obstruction-free) соотносится с производительностью? Это зависит от конкретного алгоритма — они могут быть как быстрее/лучше масштабироваться, так и медленнее/хуже масштабироваться.
Функции increment_reference_counter()/decrement_reference_counter() скорее всего будут быстрее аналогичного lock-based алгоритма, т.к. хотя бы одну тяжелую атомарную операцию вход/выход из критической секции содержать тоже будет, но там ещё будет собственно полезная работа + возможность заблокироваться/спин-ожидание.
Зато большинство lock-free алгоритмов для сложных структур данных (двусвязные списки) будут медленнее аналогичных lock-based алгоритмов, т.к. будут содержать больше тяжелых атомарных операций (2-5). Но хотя тут сложный вопрос, т.к. lock-based алгоритм будет вызывать много блокирования под нагрузкой, но с другой стороны мьютексы можно партицировать — т.е. имеем не один "большой" мьютекс, а много "маленьких", но с другой стороны, если у нас много "маленьких" мьютексов, то и операций захвата/освобождения будет больше. Т.е. тут каждый случай надо рассматривать в отдельности.
И тут я имею в виду только операции модификации, т.к. существует такая замечательная вещь как lock-free reader pattern, которая, кстати, может сочетаться и с lock-based writer частью. Но это уже отдельная история.

atomic-free

Т.о. lock-free это не о производительности. Есть класс алгоритмов синхронизации, которые именно о производительности. Они разрабатываются именно с мыслью не обеспечения каких-то гарантий, а с мыслью обеспечения максимальной производительности и линейной масштабируемости на многопроцессорных/многоядерных системах. Как следствие такие алгоритмы вполне могут содержать и lock-based части. К сожалению общепринятого слова для них, насколько я знаю, нет. Поэтому их часто и называют lock-free, в смысле "не lock-based". Я обычно называю такие алгоритмы atomic-free, с целью подчеркнуть факт минимизации тяжелых операций. Насколько я помню, термин почерпнут в какой-то работе David Dice.
Почему я всегда вместе со словом "производительность" употребляю слово "масштабируемость". Масштабируемость — это очень важный аспект алгоритмов синхронизации в контексте многопроцессорных/многоядерных систем, но он полностью отсутствует на однопроцессорных машинах. Зачастую у примитивов синхронизации следующий паттерн поведения. На однопроцессорной машине он выполняется Х времени, на двухпроцессорной — 2*Х времени, на четырех-процессорной — 10*Х времени и т.д. Поэтому в контексте многопроцессорности очень важно, что бы алгоритм не деградировал таким образом.


Для факультативного чтения могу предложить:
Practical lock-freedom
или более свежий:
Concurrent Programming Without Locks
Обе работы написаны KEIR FRASER и TIM HARRIS, и содержат достаточно обширную "вводную часть" с освещением всех базовых вопросов.

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

R>Для факультативного чтения могу предложить:
R>Practical lock-freedom
R>или более свежий:
R>Concurrent Programming Without Locks
R>Обе работы написаны KEIR FRASER и TIM HARRIS, и содержат достаточно обширную "вводную часть" с освещением всех базовых вопросов.

Ну.. может переводами займёшься?

Обещаю что последний раз пристаю Больше не буду, честно.

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

SH>Ну.. может переводами займёшься?

Да и вообще, материала на развёрнутую обзорную статью может хватить.

Здравствуйте, Константин Л., Вы писали:

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

КЛ>[]

КЛ>>>боюсь просить, почему медленнее и о каких гарантиях идет речь

R>>http://www.rsdn.ru/Forum/message/2930849.1.aspx

Автор: remark
Дата: 27.04.08

КЛ>ну вот как раз там-то все не очень очевидно, что касается скорости. если мы постоянно проваливаемся в ядро на lock-based, то, очевидно, lock-free при куче своих atomic* будет все-таки быстрее.


А откуда это очевидно?
Сколько, по-твоему, выполняется переключение контекста и сколько атомарная RMW операция? Т.е. сколько атомарных RMW операций стоит одно переключение контекста?


R>>

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

R>Здравствуйте, Константин Л., Вы писали:

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

КЛ>>[]

КЛ>>>>боюсь просить, почему медленнее и о каких гарантиях идет речь

R>>>http://www.rsdn.ru/Forum/message/2930849.1.aspx

Автор: remark
Дата: 27.04.08

КЛ>>ну вот как раз там-то все не очень очевидно, что касается скорости. если мы постоянно проваливаемся в ядро на lock-based, то, очевидно, lock-free при куче своих atomic* будет все-таки быстрее.


R>А откуда это очевидно?
R>Сколько, по-твоему, выполняется переключение контекста и сколько атомарная RMW операция? Т.е. сколько атомарных RMW операций стоит одно переключение контекста?

ты заставил меня задуматься...

интуитивно очевидно, но ты здесь, чтобы интуицию заменить фактами, так что давай!

пс: вообще забавно наблюдать за твоими изысканиями. год назад ты "ошеломил" народ всякими rcu. мы, как дилетанты, взяли флаг в руки, а тут, немного погодя, ты начинаешь чуть-ли не ратовать за lock-based. еще помню наши с тобой споры по поводу того, что лучше, лочить объекты мьютексами, или использовать cas.

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


R>>>
R>

Здравствуйте, Константин Л., Вы писали:

КЛ>пс: вообще забавно наблюдать за твоими изысканиями. год назад ты "ошеломил" народ всякими rcu. мы, как дилетанты, взяли флаг в руки, а тут, немного погодя, ты начинаешь чуть-ли не ратовать за lock-based. еще помню наши с тобой споры по поводу того, что лучше, лочить объекты мьютексами, или использовать cas.

Мьютексы могут быть реализованы с привлечением cas. Идея заключается в том, чтобы использовать cas для попытки захвата блокировки и только если захват не удался (мьютекс уже захвачен) переходить в ядро для блокировки потока.

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

Версия для многопроцессорных/многоядерных машин, может вести себя еще немного сложнее — если первоначально cas-ом не удалось захватить блокировку, делается еще несколько попыток в цикле в user mode, ожидая что поток с другого ядра отпустит блокировку, и только потом поток блокируется в ядре

Не знаю насколько это распространенное решение, я встретился с этим на Солярисах начиная с 8 версии.

КЛ>Вообще, у меня есть мнение, что лочить именно очень маленькие участки кода гораздо эффективнее, чем большие. Это в тему твоего высказывания по поводу того, что мьютексы должны ограждать много полезной работы, дабы переключение контекста по времени было заметно меньше времени работы залоченного кода. Так вот мой поинт в том, что чем меньше кода залочено, тем меньше вероятности 2м потокам одновременно в него постучаться. Что скажешь?

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

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

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

Кстати, если использовать старые Unix семафоры, все работало. Они похоже на каждую операцию лазают в ядро + подерживают очередь потоков, ктр хотять их захватить

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


RRM>Мьютексы могут быть реализованы с привлечением cas. Идея заключается в том, чтобы использовать cas для попытки захвата блокировки и только если захват не удался (мьютекс уже захвачен) переходить в ядро для блокировки потока.

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

RRM>Версия для многопроцессорных/многоядерных машин, может вести себя еще немного сложнее — если первоначально cas-ом не удалось захватить блокировку, делается еще несколько попыток в цикле в user mode, ожидая что поток с другого ядра отпустит блокировку, и только потом поток блокируется в ядре

RRM>Не знаю насколько это распространенное решение, я встретился с этим на Солярисах начиная с 8 версии.

Именно так реализовано ожидание критических секций в Windows. Так что достаточно распространено

Здравствуйте, Константин Л., Вы писали:


КЛ>>>ну вот как раз там-то все не очень очевидно, что касается скорости. если мы постоянно проваливаемся в ядро на lock-based, то, очевидно, lock-free при куче своих atomic* будет все-таки быстрее.


R>>А откуда это очевидно?
R>>Сколько, по-твоему, выполняется переключение контекста и сколько атомарная RMW операция? Т.е. сколько атомарных RMW операций стоит одно переключение контекста?

КЛ>ты заставил меня задуматься...

КЛ>интуитивно очевидно, но ты здесь, чтобы интуицию заменить фактами, так что давай!


В пределе, что я получал по переключению контекста — это 700 тактов. На Windows XP. 2 потока в цикле вызывали SwitchToThread() и передавали друг другу управление.

Захват reader-writer мьютекса в случае только с читателями, т.е. блокировок нет, у меня получается 500 тактов. И это же можно считать стоимостью lock-free алгоритма с двумя атомарными модификациями.

Цифры, в принципе, сравнимые.
Но в жизни, конечно, всё сложнее. Т.к. переключение контекста будет наверное дороже в общем случае. А блокировка в ядре происходит не всегда, а только иногда. А в lock-free алгоритмах, основанных на CAS могут "повторы", т.е. они под сильной нагрузкой могут деградировать ещё и за счёт этого. И т.д. и т.п.

К тому же мьютекс можно реализовать только с одним CAS — на входе, а на выходе обычное сохранение в память. И делать не блокирование на семафоре, а пассивное спин ожидание с помощью SwitchToThread(). Пока не начинаются очень частые вызовы SwitchToThread(), такой мьютекс получается достаточно быстрым.

В общем случае нельзя сказать, что быстрее. Для мьютекса цена всегда одинаковая, и не зависит от того, что мы им защищаем. А в lock-free алгоритме цена очень сильно зависит от того, что конкретно мы делаем.
Ну наверное можно сделать только такой вывод — если lock-free алгоритм использует только один CAS, то он будет не хуже, чем lock-based решение. Я по крайней мере не вижу, за счёт чего он может быть медленнее, т.к. мьютекс — это тот же lock-free алгоритм, с как минимум одним CAS.



КЛ>пс: вообще забавно наблюдать за твоими изысканиями. год назад ты "ошеломил" народ всякими rcu. мы, как дилетанты, взяли флаг в руки, а тут, немного погодя, ты начинаешь чуть-ли не ратовать за lock-based. еще помню наши с тобой споры по поводу того, что лучше, лочить объекты мьютексами, или использовать cas.


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

Тут либо ты меня не так понял, либо я не так сказал. Я не призываю использовать lock-based алгоритмы, я хочу сказать, что и тот и другой подход по сути своей очень схожи и дороги. Схожесть у них в том, что они оба основаны на постоянной модификации одних и тех же разделяемых переменных. И это у них основной источних их стоимости и немасштабируемости.


КЛ>Вообще, у меня есть мнение, что лочить именно очень маленькие участки кода гораздо эффективнее, чем большие. Это в тему твоего высказывания по поводу того, что мьютексы должны ограждать много полезной работы, дабы переключение контекста по времени было заметно меньше времени работы залоченного кода. Так вот мой поинт в том, что чем меньше кода залочено, тем меньше вероятности 2м потокам одновременно в него постучаться. Что скажешь?


Если у тебя операция под мьютексом короткая, например, добавление элемента в очередь (фактически пара манипуляций с указателями), то получается, что у тебя полезной работы 1 такт, и 500 тактов пенальти за синхронизацию. Т.е. 0.2% полезной работы и 99.8% оверхед. Это, конечно, через чур утрированно, но суть такая. И reader-writer мьютексы никак не спасают, они делают только хуже.

Смотри презентацию "Abstraction, Reality Checks, and RCU":
http://www.rdrop.com/users/paulmck/RCU/RCUintro.2005.07.26bt.pdf

Она очень хорошо вводит в курс дела по вопросам производительности, масштабиремости, мьютексов, lock-free алгоритмов и т.д.

В частности страницы 5-6: эффективность мьютекса.
Страница 7: стоимости примитивных операций.
Страница 18: почему reader-writer мьютексы на самом деле не дают выполняться читателям параллельно, и только ухудшают ситуацию.
Страница 38: производительность/масштабируемость мьютексов и того, что я назвал atomic-free подход (самый нижний график — это reader-writer мьютекс).



R>>>>
R>>

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

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

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


Это называется starvation (голодание). Это известный момент касательно блокировок.


RRM>Кстати, если использовать старые Unix семафоры, все работало. Они похоже на каждую операцию лазают в ядро + подерживают очередь потоков, ктр хотять их захватить


Windows тоже лазеет в ядро. Просто он не решал перепланироват на выполнение другой поток. Если бы приоритет второго потока был выше, то я думаю, что он мог бы сразу запускался на выполнение. Тогда бы это называлось уже не starvation, а priority inversion

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

RRM>>Не знаю насколько это распространенное решение, я встретился с этим на Солярисах начиная с 8 версии.

_>Именно так реализовано ожидание критических секций в Windows. Так что достаточно распространено

Если не вызывать InitializeCriticalSectionAndSpinCount() Windows разве использует активное спин-ожидание? Мне казалось, что нет.

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

RRM>>Кстати, если использовать старые Unix семафоры, все работало. Они похоже на каждую операцию лазают в ядро + подерживают очередь потоков, ктр хотять их захватить

R>Windows тоже лазеет в ядро. Просто он не решал перепланироват на выполнение другой поток. Если бы приоритет второго потока был выше, то я думаю, что он мог бы сразу запускался на выполнение. Тогда бы это называлось уже не starvation, а priority inversion

Решающем в том случае было, что семафор похоже поддерживает список потоков, ктр ждут его освобожденияю. При повторной попытке первый поток попадает в конец этого списка и не мешает второму потоку. Но это только преположение

R>

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

R>Если не вызывать InitializeCriticalSectionAndSpinCount() Windows разве использует активное спин-ожидание? Мне казалось, что нет.

Могу ошибаться, но мне казалось, что там есть значение для счётчика по умолчанию. А InitializeCriticalSectionAndSpinCount просто позволяет им управлять. Но не помню, откуда я это взял, в msdn на эту тему ничего не нашёл.

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

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

Можно ли ознакомиться где-то с результатами этих изыскания?

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

R>Большую часть моих "изысканий" я уже не публикую на RSDN — по опыту просто я вижу, что они не находят никакого отклика и понимания... Получается совершенно пустой труд. Тут я описываю, только самые общие вещи, т.к. сказать вводную часть, что доступно широким массам. Поэтому только по RSDN ты за моими изысканими не проследишь
Нифига не пустой труд. Я по работе на многопоточность не завязан и поэтому нету соответствующих знаний и возможности проверить/поэксперементировать. Сиплюснотые твои изыски тоже не получается применить. Но я за твоими сообщениями внимательно слежу и когда припрет, я знаю где и главное какую инфу искать. То что некому вступить в дисскусию, это не означает что все улетает в трубу. Думаю за твоими сообщения ни я один слежу, просто нам по "скудоумею" возразить, обсудить нечего Но как тока, мы так сразу

Предлагаю твои изыскания маркеровать тегом "remark"

PS Обязуюсь в дальнешем побороть лень и все интересные сообщения оценивать, дабы хоть какой то отклик был

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

[]


КЛ>>пс: вообще забавно наблюдать за твоими изысканиями. год назад ты "ошеломил" народ всякими rcu. мы, как дилетанты, взяли флаг в руки, а тут, немного погодя, ты начинаешь чуть-ли не ратовать за lock-based. еще помню наши с тобой споры по поводу того, что лучше, лочить объекты мьютексами, или использовать cas.


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

R>Тут либо ты меня не так понял, либо я не так сказал. Я не призываю использовать lock-based алгоритмы, я хочу сказать, что и тот и другой подход по сути своей очень схожи и дороги. Схожесть у них в том, что они оба основаны на постоянной модификации одних и тех же разделяемых переменных. И это у них основной источних их стоимости и немасштабируемости.

просто когды ты впервые публиковал что-то по lock-free, ты ничего не упоминал об очень дорогих atomic операциях.


КЛ>>Вообще, у меня есть мнение, что лочить именно очень маленькие участки кода гораздо эффективнее, чем большие. Это в тему твоего высказывания по поводу того, что мьютексы должны ограждать много полезной работы, дабы переключение контекста по времени было заметно меньше времени работы залоченного кода. Так вот мой поинт в том, что чем меньше кода залочено, тем меньше вероятности 2м потокам одновременно в него постучаться. Что скажешь?


R>Если у тебя операция под мьютексом короткая, например, добавление элемента в очередь (фактически пара манипуляций с указателями), то получается, что у тебя полезной работы 1 такт, и 500 тактов пенальти за синхронизацию. Т.е. 0.2% полезной работы и 99.8% оверхед. Это, конечно, через чур утрированно, но суть такая. И reader-writer мьютексы никак не спасают, они делают только хуже.

я о том же.

R>Смотри презентацию "Abstraction, Reality Checks, and RCU":

постараюсь глянуть, спасибо.

[]

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

Здравствуйте, Константин Л., Вы писали:

КЛ>По поводу того, что дискуссии не получается ты зря, мы читаем и наматываем на ус. так что это все очень полезно.

Возможно, проблема в том, что наматывание RSDN-овцами себе на ус никак не отражается на материальном благосостоянии самого remark-а.

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

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

R>>Если не вызывать InitializeCriticalSectionAndSpinCount() Windows разве использует активное спин-ожидание? Мне казалось, что нет.

SH>Могу ошибаться, но мне казалось, что там есть значение для счётчика по умолчанию. А InitializeCriticalSectionAndSpinCount просто позволяет им управлять. Но не помню, откуда я это взял, в msdn на эту тему ничего не нашёл.
Именно так написано у Рихтера... Сначала Spin Wait затем собственно ожидание.

PS Сорри, что медленно... праздники

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

R>На месте, по крайней мере, я стоять не люблю :)
R>Большую часть моих "изысканий" я уже не публикую на RSDN — по опыту просто я вижу, что они не находят никакого отклика и понимания... Получается совершенно пустой труд. Тут я описываю, только самые общие вещи, т.к. сказать вводную часть, что доступно широким массам. Поэтому только по RSDN ты за моими изысканими не проследишь ;)

Ты пишешь преимущественно в ФП, а это опасный для здоровья форум, пиши в C++ :-)

Лично мне твои сообщения весьма интересны, но пока только теоретически, вот не являются сверхскоростные сервера моей нынешней сферой деятельности. Хотя я и хотел бы.

Можешь быть уверен, что твои исследования наматываются на усы большими лебедками, даже если мало кто осмеливается их комментировать ;-)

Кстати, а что именно разрабатываешь ты? Можно ли посмотреть на высокие технологии в действии?

Здравствуйте, Roman Odaisky, Вы писали:

RO>пиши в C++
+1

RO>Лично мне твои сообщения весьма интересны,
Присоединяюсь.

RO>Можешь быть уверен, что твои исследования наматываются на усы большими лебедками, даже если мало кто осмеливается их комментировать
+1

У меня тоже есть интерес к lock-, wait-, obstruction-, atomic-free алгоритмам. Пока наращиваю "мускульную массу", читаю вумных людей, пробую что то реализовывать и с ним играться.

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


R>Для факультативного чтения могу предложить:
R>Practical lock-freedom
R>или более свежий:
R>Concurrent Programming Without Locks
R>Обе работы написаны KEIR FRASER и TIM HARRIS, и содержат достаточно обширную "вводную часть" с освещением всех базовых вопросов.

Я понял, что основа lock-free адгоритмов — CAS, multiple-CAS и STM?

Сейчас перечитываю вторую работу, кроме того примерно 1.5 года назад прочитал пару статей по STM.
Свои мысли на этот счет я изложил здесь

Автор: RailRoadMan
Дата: 06.02.07

Больше всего сомнений/вопросов возникает по поводу достаточно длинных транзакций в связи
1) Возможно livelock — параллельные транзакции, ктр не дают закоммитить друг другу изменения

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

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

Есть ли какой-то опыт появления таких проблем в реальных приложениях или это в большей степени теоретические проблемы?