Здравствуйте, SergH, Вы писали:
SH>Здравствуйте, remark, Вы писали:
R>>Я не пророк я просто его представитель на rsdn.ru
SH>Можно ссылку? Интересная тема.
Сейчас постараюсь что-нибудь подобрать.
Думаю, начать можно с этого, т.к. тут Андрей пишет так сказать "с нуля" и всё по полочкам — хорошо подойдёт для затравки : Lock-Free Data Structures (Keeping threads moving while avoiding deadlock) by Andrei Alexandrescu
Насколько помню, это была первая статья, которую я прочитал про lock-free... вначале долго пытался понять, о чём вообще речь
Вот тоже статья Андрея и M. Michael (это очень авторитетный человек в мире lock-free): Lock-Free Data Structures with Hazard Pointers
Тут сразу приготовьтесь — чтение будет не из лёгкого
Вот ещё презентация by Andrei Alexandrescu: Lock-Free Programming
В частности там можно поглядеть зачем всё это надо:
Advantages of lock-free
— Fast (~ 4 times faster than best locks)
— Deadlock immunity
— Livelock immunity
— Thread-killing immunity
— Asynchronous signal immunity
— Reentrancy is automatic
— Priority inversion immunity
Disadvantages
— Priorities uncontrollable (Can increase contention gratuitously)
— Hard to program (GC is a big helper, Hard even with GC)
— Use locks for 98% of the code
— Use CAS for 2% of the code to increase performance by 98%
В comp.programming.threads много инфы — вот например Lock Free -- where to start
Особое внимание уделяем постам Chris Thomasson и Joe Seigh, т.к. это люди реально разбирающиеся и делающие реальные вещи.
По каким именам можно ещё искать: Chris Thomasson, Joe Seigh, Maged M. Michael, Maurice Herlihy, Mark Moir, Tim Harris, Keir Fraser...
Вот ещё пара ссылок: здесь — очень объёмная статья, точнее это докторская, поэтому там есть очень хорошее и подробное введение здесь много статей и ссылок здесь свежая статья с новыми структурами, достаточно занятная. если разобраться как это работает, то многое в этой жизни после неё покажется "орешками"...
Если интересно могу ещё кинуть ссылок на библиотеки с реальным рабочим кодом. Последнее замечание очень важно в мире lock-free
Здравствуйте, remark, Вы писали:
lock-free тема должна быть интересна в первую очередь тем кто будет иметь дело с распределенными системами, т.к. теоретически невозможно создать для них надежно работающий объект синхронизации, не говоря уж о том что удаленные вызовы вещь медленная.
про синхронизацию в сетях немного есть у таненбаума
Здравствуйте, rm822, Вы писали:
R>Здравствуйте, remark, Вы писали: R>lock-free тема должна быть интересна в первую очередь тем кто будет иметь дело с распределенными системами, т.к. теоретически невозможно создать для них надежно работающий объект синхронизации, не говоря уж о том что удаленные вызовы вещь медленная. R>про синхронизацию в сетях немного есть у таненбаума
Это совершенно неверное утверждение. lockfree алгоритмы работают строго на SMP машинах. К тому же, даже если перенести эти алгоритмы на распределённые машины, они будут работать крайне неэффективно в силу больших задержек.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, rm822, Вы писали:
R>>Здравствуйте, remark, Вы писали: R>>lock-free тема должна быть интересна в первую очередь тем кто будет иметь дело с распределенными системами, т.к. теоретически невозможно создать для них надежно работающий объект синхронизации, не говоря уж о том что удаленные вызовы вещь медленная. R>>про синхронизацию в сетях немного есть у таненбаума
R>Это совершенно неверное утверждение. lockfree алгоритмы работают строго на SMP машинах. К тому же, даже если перенести эти алгоритмы на распределённые машины, они будут работать крайне неэффективно в силу больших задержек.
Строго говоря, это не так. lockfree системы — это системы, в которых из-за остановки произвольной нити исполнения всей системе не может настать дедлок. А уж как конкретно они реализованы — на CAS/MCAS, transactional memory или голубиной почте, это отдельный разговор.
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Здравствуйте, Sergey, Вы писали:
S>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, rm822, Вы писали:
R>>>Здравствуйте, remark, Вы писали: R>>>lock-free тема должна быть интересна в первую очередь тем кто будет иметь дело с распределенными системами, т.к. теоретически невозможно создать для них надежно работающий объект синхронизации, не говоря уж о том что удаленные вызовы вещь медленная. R>>>про синхронизацию в сетях немного есть у таненбаума
R>>Это совершенно неверное утверждение. lockfree алгоритмы работают строго на SMP машинах. К тому же, даже если перенести эти алгоритмы на распределённые машины, они будут работать крайне неэффективно в силу больших задержек.
S>Строго говоря, это не так. lockfree системы — это системы, в которых из-за остановки произвольной нити исполнения всей системе не может настать дедлок. А уж как конкретно они реализованы — на CAS/MCAS, transactional memory или голубиной почте, это отдельный разговор.
Если бы это было в ветке Философия, то возможно...
Если совсем строго говоря, то и такое определение не верно, т.к. в lockfree системе при остановке нити не может настать и лайвлок, так же не может настать дедлок/лайвлок и без остановок нити. Под твоё определение подходит, например, система, основанная на мьютексах со спин-локом.
Обычно даётся следующее определение: lockfree система — это система, в которой гарантируется общесистемный прогресс.
з.ы. прогресс для каждой отдельной нити не гарантируется.
Кстати, есть ссылки на lockfree алгоритмы, основанные на голубиной почте или хотя бы для не SMP систем
Здравствуйте, remark, Вы писали:
S>>Строго говоря, это не так. lockfree системы — это системы, в которых из-за остановки произвольной нити исполнения всей системе не может настать дедлок. А уж как конкретно они реализованы — на CAS/MCAS, transactional memory или голубиной почте, это отдельный разговор.
R>Если бы это было в ветке Философия, то возможно...
R>Если совсем строго говоря, то и такое определение не верно, т.к. в lockfree системе при остановке нити не может настать и лайвлок, так же не может настать дедлок/лайвлок и без остановок нити. Под твоё определение подходит, например, система, основанная на мьютексах со спин-локом.
R>Обычно даётся следующее определение: lockfree система — это система, в которой гарантируется общесистемный прогресс. R>з.ы. прогресс для каждой отдельной нити не гарантируется.
Согласен. Подзабыл уже.
R>Кстати, есть ссылки на lockfree алгоритмы, основанные на голубиной почте или хотя бы для не SMP систем
Принимая, что существует стек TCP/IP поверх голубиной почты, наверное годится вот это: cobweb.ecn.purdue.edu/~smidkiff/ ppopp/presentations/manassiev.pdf , www.cs.brown.edu/people/mph/HerlihyS05/main.pdf
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Здравствуйте, Sergey, Вы писали:
R>>Кстати, есть ссылки на lockfree алгоритмы, основанные на голубиной почте или хотя бы для не SMP систем
S>Принимая, что существует стек TCP/IP поверх голубиной почты, наверное годится вот это: cobweb.ecn.purdue.edu/~smidkiff/ ppopp/presentations/manassiev.pdf , S>www.cs.brown.edu/people/mph/HerlihyS05/main.pdf
В принципе, если смотреть с высоты птичего полёта, то оптимистическая блокировка в БД — это тоже lockfree, основа одинаковая... но имхо не стоит так называть для путаницы, т.к. термин уже забит
Здравствуйте, remark, Вы писали:
R>>>Кстати, есть ссылки на lockfree алгоритмы, основанные на голубиной почте или хотя бы для не SMP систем
S>>Принимая, что существует стек TCP/IP поверх голубиной почты, наверное годится вот это: cobweb.ecn.purdue.edu/~smidkiff/ ppopp/presentations/manassiev.pdf , S>>www.cs.brown.edu/people/mph/HerlihyS05/main.pdf
R>В принципе, если смотреть с высоты птичего полёта, то оптимистическая блокировка в БД — это тоже lockfree, основа одинаковая... но имхо не стоит так называть для путаницы, т.к. термин уже забит
Ну не я же такое использование этого термина придумал В тех источниках, с которыми я ознакомился, STM относят к одному из направлений организации lock-free систем.
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Вот если бы контейнеры стандартной библиотеки были lock-free на малом количестве элементов и с обычной реализацией на большое, то скорость бы возрасла .
Пока что не видел реализацию стандартной библиотеке, где меняется реализация контейнеров во время выполнения
Здравствуйте, _nn_, Вы писали:
__>Здравствуйте, remark, Вы писали:
__>Вот если бы контейнеры стандартной библиотеки были lock-free на малом количестве элементов и с обычной реализацией на большое, то скорость бы возрасла . __>Пока что не видел реализацию стандартной библиотеке, где меняется реализация контейнеров во время выполнения
Я бы не был так однозначен.
А почему именно на малом lock-free, а на большом lock-based? Если ты имеешь в виду элиминацию копирования, то я не видел ни одного реального lock-free контейнера, который бы копировал бы всё своё содержимое при операциях. Даже недавний lock-free vector от Страуструпа не копирует своё содержимое.
К тому же сложность и без того сложных алгоритмов возрастёт ещё на порядок. Имхо овчинка выделки не стоит.
К тому же лишний уровень косвенности, который тут будет неизбежен, будет снижать быстродействие.
lock-free списки и стеки и так всегда будут быстрее lock-based при любых размерах, т.к. там меньше "тяжёлых" синхронизирующих инструкций — одна/ноль против двух у lock-based контейнера.
Ещё какой интересный подход я встречал — так это "писатели" работают с контейнером в стиле lock-based, т.е. по очереди, а "читатели", кто не меняют контейнер, а, например, итерируют по нему, что является достаточно распространённой операцией, работают в стиле lock-free, т.е. независимо не от других читателей, ни от писателей. Называется lock-free reader pattern. Вот это было бы имхо полезно, т.к. повышает масштабируемость/скорость, при том что синхронизацию записи всё равно надо делать на более высоком уровне нежели на уровне операций контейнера, на уровне бизнес-логики.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, _nn_, Вы писали:
__>>Здравствуйте, remark, Вы писали:
__>>Вот если бы контейнеры стандартной библиотеки были lock-free на малом количестве элементов и с обычной реализацией на большое, то скорость бы возрасла . __>>Пока что не видел реализацию стандартной библиотеке, где меняется реализация контейнеров во время выполнения
R>Я бы не был так однозначен. R>А почему именно на малом lock-free, а на большом lock-based? Если ты имеешь в виду элиминацию копирования, то я не видел ни одного реального lock-free контейнера, который бы копировал бы всё своё содержимое при операциях. Даже недавний lock-free vector от Страуструпа не копирует своё содержимое.
Честно говоря, пока не вижу особых преимуществ в использовании lock-free по сравнению с multiple-readers-single-writer-lock. выигрыш по скорости гасится копированием данных и ограничениями по применению. Да и сам автор призывает к подходу "используйте lock-based в 98% случаев, а lock-free — в оставшихся случаях, для ускорения кода на 98%". Т.е. lock-free — это узкоспециализированное решение для расшивки bottle-neck'ов, которые невозможно обойти обычным путем.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, remark, Вы писали:
R>>Здравствуйте, _nn_, Вы писали:
__>>>Здравствуйте, remark, Вы писали:
__>>>Вот если бы контейнеры стандартной библиотеки были lock-free на малом количестве элементов и с обычной реализацией на большое, то скорость бы возрасла . __>>>Пока что не видел реализацию стандартной библиотеке, где меняется реализация контейнеров во время выполнения
R>>Я бы не был так однозначен. R>>А почему именно на малом lock-free, а на большом lock-based? Если ты имеешь в виду элиминацию копирования, то я не видел ни одного реального lock-free контейнера, который бы копировал бы всё своё содержимое при операциях. Даже недавний lock-free vector от Страуструпа не копирует своё содержимое.
А>Честно говоря, пока не вижу особых преимуществ в использовании lock-free по сравнению с multiple-readers-single-writer-lock.
Навскидку:
— при самой хорошей реализации и если нет писателей одно обращение к структуре будет содержать 4 блокировки шины — это достаточно дорого, и особено дорого на многопроцессорных/ядерных машинах, которые сейчас будут применяться всё шире и шире. плохие, если не сказать ужасные реализации, строятся с использованием mutex/event/condition — это просто ужасно с т.з. производительности.
lock-free подход возможно сделать с одной блокировкой шины.
з.ы. как ни странно, но обычная блокировка, может быть даже значительно лучше multiple-readers-single-writer-lock, т.к. содержит только 2 блокировки шины.
— проблемы с делоками/лайвлоками
— проблемы с останавливанием/убиванием потоков
— при появлении писателей всё становится совсем ужасно — писатель простаивает пока не уйдут всё читатели, читатели простаивают пока не уйдёт писатель — это вносит существенные задержки
...
А>выигрыш по скорости гасится копированием данных и ограничениями по применению.
Откуда такая информация? Нет никаких копирований.
Помимо первой статьи Александреску, которая описывает копирования, я дал ещё ссылки — погляди их.
Никакие копирования внутреннее не присущи lock-free, есть некоторые учебные примеры с копированиями, но они не применяются на практике, они "учебные".
А>Да и сам автор призывает к подходу "используйте lock-based в 98% случаев, а lock-free — в оставшихся случаях, для ускорения кода на 98%". Т.е. lock-free — это узкоспециализированное решение для расшивки bottle-neck'ов, которые невозможно обойти обычным путем.
Естественно не стоит придумывать свои алгоритмы и реализовывать lock-free структуры, что бы реализовать какой-нибудь контейнер, к которому обращаются раз в полгода. Но если у тебя уже готовые структуры, то напишешь ты:
lock_based_stack<int> s;
или
lock_free_stack<int> s;
не привносит тебе никакой сложности/проблем/усилийи т.д.
Здравствуйте, remark, Вы писали:
R>Здравствуйте, _nn_, Вы писали:
__>>Здравствуйте, remark, Вы писали:
__>>Вот если бы контейнеры стандартной библиотеки были lock-free на малом количестве элементов и с обычной реализацией на большое, то скорость бы возрасла . __>>Пока что не видел реализацию стандартной библиотеке, где меняется реализация контейнеров во время выполнения
R>Я бы не был так однозначен. R>А почему именно на малом lock-free, а на большом lock-based? Если ты имеешь в виду элиминацию копирования, то я не видел ни одного реального lock-free контейнера, который бы копировал бы всё своё содержимое при операциях. Даже недавний lock-free vector от Страуструпа не копирует своё содержимое.
А как же происходит добавка элементов ? R>К тому же сложность и без того сложных алгоритмов возрастёт ещё на порядок. Имхо овчинка выделки не стоит. R>К тому же лишний уровень косвенности, который тут будет неизбежен, будет снижать быстродействие. R>lock-free списки и стеки и так всегда будут быстрее lock-based при любых размерах, т.к. там меньше "тяжёлых" синхронизирующих инструкций — одна/ноль против двух у lock-based контейнера.
R>Ещё какой интересный подход я встречал — так это "писатели" работают с контейнером в стиле lock-based, т.е. по очереди, а "читатели", кто не меняют контейнер, а, например, итерируют по нему, что является достаточно распространённой операцией, работают в стиле lock-free, т.е. независимо не от других читателей, ни от писателей. Называется lock-free reader pattern. Вот это было бы имхо полезно, т.к. повышает масштабируемость/скорость, при том что синхронизацию записи всё равно надо делать на более высоком уровне нежели на уровне операций контейнера, на уровне бизнес-логики.
Это интересная идея
R>
Здравствуйте, _nn_, Вы писали:
R>>Я бы не был так однозначен. R>>А почему именно на малом lock-free, а на большом lock-based? Если ты имеешь в виду элиминацию копирования, то я не видел ни одного реального lock-free контейнера, который бы копировал бы всё своё содержимое при операциях. Даже недавний lock-free vector от Страуструпа не копирует своё содержимое. __>А как же происходит добавка элементов ?
Ты имеешь в виду именно этот вектор или вообще?
R>>
я просто его представитель на rsdn.ru 
: Lock-Free Data Structures (Keeping threads moving while avoiding deadlock) by Andrei Alexandrescu
.
