В чем причина того, что высокоуровневые абстракции, использующие глубокое программирование без блокировки, не популярны?

Question

Из того, что я собрал на программировании без блокировки, это невероятно трудно сделать правильно ... и я согласен. От одной мысли о некоторых проблемах у меня болит голова. Но что мне интересно, так это почему Есть ли повсеместное использование высокоуровневых оболочек (например, блокировка свободной очереди и тому подобное)? Например, у boost нет свободной библиотеки без блокировок, хотя, насколько я знаю, она была предложена. Я имею в виду, я думаю, что есть много приложений, где вы не можете избежать того факта, что критический раздел является большой частью нагрузки. Так каковы причины? Это ...

1. Патенты - я слышал, что некоторые вещи, связанные с программированием без блокировки, запатентованы.
2. Производительность.
3. У Google и Microsoft есть такие внутренние библиотеки, но ни одна из них не является общедоступной ...
4. Что-то еще?

Итак, мой вопрос: почему абстракции высокого уровня, которые используют программирование без блокировки в глубине, не очень популярно, в то же время "обычное" многопоточное программирование "в"?

РЕДАКТИРОВАТЬ: boost получил lockfree lib:)

Answer 1

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

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

Герой в этой области - Клифф Клик, который создал хэш без блокировки, который он более или менее поместил в общественное достояние.

Вы можете найти мою библиотеку без блокировки здесь;

http://www.liblfds.org

Еще один набор для параллелизма Сами Бахры;

http://www.concurrencykit.org

Answer 2

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

ИМХО относительно C ++ (я не продвинут в других языках). Новый стандарт C ++ был только что выпущен, и разработчикам компилятора нужно время, чтобы реализовать его требования. Сегодня все компиляторы не поддерживают модель памяти C ++ 11 полностью, поскольку она требует значительных изменений в правилах оптимизации компилятора. Недавно Microsoft объявляет о поддержке атомарных операций, которые являются основой программирования без блокировок в VC ++ 11 Developer Preview. Это хорошая новость для нас. Как я знаю, GCC поддержит его в 4.8 (или выше).

Вторая проблема - патенты. Многие интересные алгоритмы контейнеров без блокировки запатентованы, что является препятствием для их включения в библиотеки поставщиков.

В-третьих, основная часть контейнеров без блокировок - это сбор мусора (безопасное восстановление памяти). C ++ свободен от любого GC (к счастью). Существует несколько алгоритмов GC (Hazard Pointer, Pass-the-Buck, основанных на эпохах и т. Д.), Но большинство из них также запатентованы.

В-четвертых, недостаточно инструментов, чтобы доказать правильность ограничений памяти, примененных в вашей реализации без блокировки. Теперь я знаю только одну - реляцию (http://www.1024cores.net/home/relacy-race-detector).

Я думаю, что через 2-3 года мы увидим много готовых к работе многоплатформенных библиотек C ++ без блокирующих контейнеров и алгоритмов. Эти библиотеки разрабатываются продавцами и энтузиастами.

Однако, на мой взгляд, наше будущее - это аппаратная память транзакций (HTM). Сегодня AMD, Sun (извините, Oracle), Intel (?) Исследуют HTM с очень интересными результатами. Давайте подождем.

Answer 3

К сведению. Платформа Microsoft .Net получила несколько классов без блокировки в .Net 4.0.А именно контейнерные классы в пространстве имен System.Collections.Concurrent, а именно:

ConcurrentDictionary
ConcurrentQueue
ConcurrentStack

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

Answer 4

Одна из основных проблем заключается в том, что если человек не использует чрезмерное количество барьеров памяти, трудно быть уверенным, что ему достаточно;если кто-то использует чрезмерное количество барьеров памяти, производительность, вероятно, будет хуже, чем при использовании блокировок.

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

Answer 5

Существует, по крайней мере, один популярный фреймворк без блокировки: Erlang.