Ada_Ru форум

Обсуждение языка Ада

Lock-free list

Оставить новое сообщение

Сообщения

Vadim Godunko
Lock-free list
2009-07-16 19:17:47

Доброго времени суток!

 

Мне нужно сделать реализацию lock-free списка (односвязного или

двусвязного - не критично). Может кто подскажет толковое описание соответствующего алгоритма?

On Thu, 16 Jul 2009 23:17:47 +0400, you wrote:

 

Мне нужно сделать реализацию lock-free списка (односвязного или

двусвязного - не критично). Может кто подскажет толковое описание соответствующего алгоритма?

 

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

 

Я в свое время обкатывал идею как на Аде сделать lock-free "exchange" (надо как для списков, так и счетчиков ссылок), при этом не прибегая к машинным инструкциям (как оно обычно делается в литературе), но ничего подходящего не придумал. Если кто знает, интересно было бы обсудить.

 

--

Regards,

Dmitry A. Kazakov

http://www.dmitry-kazakov.de

Dmitry A. Kazakov wrote:

On Thu, 16 Jul 2009 23:17:47 +0400, you wrote:

 

Мне нужно сделать реализацию lock-free списка (односвязного или

двусвязного - не критично). Может кто подскажет толковое описание

соответствующего алгоритма?

 

Многое зависит от того, какие операции должны быть lock-free. Например

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

"плохо определена", это - раз. А во-вторых, очень может оказаться, что для

данного набора операций реализованных lock-free результат будет сильно хуже

чем с блокировкой, например, если итерация всего списка - lock-free

операция.

 

Я в свое время обкатывал идею как на Аде сделать lock-free "exchange" (надо

как для списков, так и счетчиков ссылок), при этом не прибегая к машинным

инструкциям (как оно обычно делается в литературе), но ничего подходящего

не придумал. Если кто знает, интересно было бы обсудить.

 

А скажите бестолковому, что такое lock-free список, или где про это

почитать? Я о чем-то таком догадываюсь, но хотелось бы точно понимать

On Fri, 17 Jul 2009 11:44:50 +0400, you wrote:

 

Dmitry A. Kazakov wrote:

On Thu, 16 Jul 2009 23:17:47 +0400, you wrote:

 

Мне нужно сделать реализацию lock-free списка (односвязного или

двусвязного - не критично). Может кто подскажет толковое описание соответствующего алгоритма?

 

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

 

Я в свое время обкатывал идею как на Аде сделать lock-free "exchange" (надо как для списков, так и счетчиков ссылок), при этом не прибегая к машинным инструкциям (как оно обычно делается в литературе), но ничего подходящего не придумал. Если кто знает, интересно было бы обсудить.

 

А скажите бестолковому, что такое lock-free список, или где про это почитать?

 

Про lock-free список или lock-free вообще? Т.к. первое не очень то хорошо определено.

 

--

Regards,

Dmitry A. Kazakov

http://www.dmitry-kazakov.de

А скажите бестолковому, что такое lock-free список, или где про это

почитать? Я о чем-то таком догадываюсь, но хотелось бы точно понимать

 

Извиняюсь за плюсы, но вот немного про lock-free: http://erdani.org/publications/cuj-2004-10.pdf

Dmitry A. Kazakov wrote:

 

Про lock-free список или lock-free вообще? Т.к. первое не очень то хорошо

определено.

 

Про то, что такое lock-free в контексте данной дискуссии

Alexey Veselovsky wrote:

 

Извиняюсь за плюсы, но вот немного про lock-free: http://erdani.org/publications/cuj-2004-10.pdf

Спасибо - оказалось примерно то самое, о чем догадывался,

но далеко не так просто, как думал :)

On Fri, 17 Jul 2009 12:11:52 +0400, you wrote:

 

Dmitry A. Kazakov wrote:

 

Про lock-free список или lock-free вообще? Т.к. первое не очень то хорошо определено.

 

Про то, что такое lock-free в контексте данной дискуссии

 

все равно не понял, но про lock-free список например:

 

http://www.cs.rpi.edu/~bushl2/portfolio/lockfree-grape/writeup/project_writeup_das.pdf

 

Идея всегда одна. Есть некий инвариант объекта, который "наблюдаем". Все кто объект дергают, либо проверяют инвариант, либо знают "по-жизни", что он не меняется в результате их и всех других действий. Первый случай заменяет блокировку на "busy waiting", что на многих ядрах может быть все равно лучше, чем глобальный семафор (в разумных пределах, конечно). Второй случай

- вообще конфетка.

 

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

 

--

Regards,

Dmitry A. Kazakov

http://www.dmitry-kazakov.de

Dmitry A. Kazakov wrote:

 

Идея всегда одна. Есть некий инвариант объекта, который "наблюдаем". Все

кто объект дергают, либо проверяют инвариант, либо знают "по-жизни", что он

не меняется в результате их и всех других действий. Первый случай заменяет

блокировку на "busy waiting", что на многих ядрах может быть все равно

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

- вообще конфетка.

 

Наблюдаемость означает, что для некоторого определенного набора действий,

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

вычитав элемент из контейнера, можно узнать был ли инвариант истинным во

время чтения. Если нет - пробуем снова. Если да, закончили. При записи та

же схема. Пишем, смотрим, откатываем, если надо восстановить инвариант,

снова пишем, и т.д.

 

То есть отказываемся от внутренней дисциплины управления

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

но это стоит (может стоить) дорого с точки зрения производительности или

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

On Fri, 17 Jul 2009 12:39:28 +0400, you wrote:

 

Dmitry A. Kazakov wrote:

 

Идея всегда одна. Есть некий инвариант объекта, который "наблюдаем". Все кто объект дергают, либо проверяют инвариант, либо знают "по-жизни", что он не меняется в результате их и всех других действий. Первый случай заменяет блокировку на "busy waiting", что на многих ядрах может быть все равно лучше, чем глобальный семафор (в разумных пределах, конечно). Второй случай - вообще конфетка.

 

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

 

То есть отказываемся от внутренней дисциплины управления

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

 

Ну как сказать, объект-то так, и так safe, т.е. наружу дисциплина остается, вернее ее и там, и там нет, она в операциях объекте упрятана (при правильном дизайне).

 

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

 

Связь с real-time и планируемостью не очевидна. Все зависит от алгоритма. dead-lock может превратиться в live-lock с тем же конечным эффектом. А иногда наоборот lock-free дает известную верхнюю границу времени исполнения и все - просто чудесно.

 

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

 

Кстати, Адова асинхронная передача управления для lock-free контейнеров - беда. Надо было давно ее выкинуть из стандарта. Где надо она все равно не работает, а геморроя - выше крыши.

 

--

Regards,

Dmitry A. Kazakov

http://www.dmitry-kazakov.de

Dmitry A. Kazakov wrote:

On Thu, 16 Jul 2009 23:17:47 +0400, you wrote:

 

Мне нужно сделать реализацию lock-free списка (односвязного или

двусвязного - не критично). Может кто подскажет толковое описание соответствующего алгоритма?

 

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

Согласен. :-) Как раз пробую составить таковой, поняв, что мало-мальски универсального решения походу не существует. Пока список таков:

 

1. Добавление в начало или конец (не критично).

 

2. Удаление из списка элемента. Всегда точно известно какой элемент удалять, проход по списку не нужен.

 

3. Каждый элемент в списке в некотором роде "привязан" к "одной" нити. Попробую пояснить. По своей физической сути с содержимым каждого

элемента списка может в один момент времени работать только одна нить (это не гарантировано, кривой программист может это нарушить, но за допустимое ограничение можно принять запросто; тем более, что в этом случае многие другие вещи затрещат по всем швам). Это не выполняется в последующих случаях, поскольку там идёт проход по списку.

 

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

 

5. Требуется иметь операцию групповой модификации. Нужен проход по всем элементам списка. Добавляемые в это время элементы не интересуют, интересующие элементы удалены быть не могут (опять же в силу (3)).

А во-вторых, очень может оказаться, что для

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

 

Может, но хочется попробовать.

 

Я в свое время обкатывал идею как на Аде сделать lock-free "exchange" (надо как для списков, так и счетчиков ссылок), при этом не прибегая к машинным инструкциям (как оно обычно делается в литературе), но ничего подходящего не придумал. Если кто знает, интересно было бы обсудить.

 

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

On Fri, 17 Jul 2009 14:12:38 +0400, you wrote:

 

Dmitry A. Kazakov wrote:

On Thu, 16 Jul 2009 23:17:47 +0400, you wrote:

 

Мне нужно сделать реализацию lock-free списка (односвязного или

двусвязного - не критично). Может кто подскажет толковое описание соответствующего алгоритма?

 

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

Согласен. :-) Как раз пробую составить таковой, поняв, что мало-мальски универсального решения походу не существует. Пока список таков:

 

1. Добавление в начало или конец (не критично).

 

2. Удаление из списка элемента. Всегда точно известно какой элемент удалять, проход по списку не нужен.

 

3. Каждый элемент в списке в некотором роде "привязан" к "одной" нити. Попробую пояснить. По своей физической сути с содержимым каждого элемента списка может в один момент времени работать только одна нить (это не гарантировано, кривой программист может это нарушить, но за допустимое ограничение можно принять запросто; тем более, что в этом случае многие другие вещи затрещат по всем швам). Это не выполняется в последующих случаях, поскольку там идёт проход по списку.

 

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

 

5. Требуется иметь операцию групповой модификации. Нужен проход по всем элементам списка. Добавляемые в это время элементы не интересуют, интересующие элементы удалены быть не могут (опять же в силу (3)).

 

Да, примерно такой набор я рассматривал одно время. Правда, одиночное удаление. И еще, мне portable-льное решение было нужно. В принципе, с копируемыми нелимитированными неконтролируемыми элементами, т.е. грубо говоря массивом, это вроде можно сделать. Даже если массив не непрерывный, по-моему, я до конца не додумывал, но похоже, что можно. Как только появляются указатели, все становится сильно сложно. Не знаю. Я тогда посчитал, что protected object не такой уж большой overhead. Сейчас я пользую только lock-free FIFO и blackboard (чтение). Списки - нет.

А во-вторых, очень может оказаться, что для

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

 

Может, но хочется попробовать.

 

А то! (:-))

 

Я в свое время обкатывал идею как на Аде сделать lock-free "exchange" (надо как для списков, так и счетчиков ссылок), при этом не прибегая к машинным инструкциям (как оно обычно делается в литературе), но ничего подходящего не придумал. Если кто знает, интересно было бы обсудить.

 

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

 

Хотелось бы 100% Ада. (:-))

 

--

Regards,

Dmitry A. Kazakov

http://www.dmitry-kazakov.de

Новое сообщение:
Страницы: 1

Чтобы оставить новое сообщение необходимо Зарегистрироваться и Войти