Является ли Clojure lockfree с помощью алгоритмов lockfree?

Я продвигаюсь в квесте Clojure (около 80 проблем, разрешенных на 4clojure.com), и я продолжаю читать и кодировать и пытаюсь "получить".

Теперь я немного смущен тем, что Clojure предназначен для "блокировки concurrency". Я слишком хорошо знаю о тупиках (как в: "Я написал плохой Java-код, который оказался в тупиках", а не как "Я в эксперте по concurrency" ). Я также прочитал это:

Почему блокировка concurrency такая большая сделка (в Clojure)?

Я понимаю, насколько здорово, что программы Clojure не могут затормозить.

Но я немного смущен: это такой подвиг, который достигается благодаря реализации алгоритмов без блокировки капота или существуют потенциально "тупиковые" алгоритмы, но с использованием правильной реализации, гарантированной никогда не запираться (что-то "скрыто" ) для Clojure программистов)?

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

http://news.ycombinator.com/item?id=4103921

ссылаясь на следующую страницу "Без блокировки" на странице 1024cores.net:

http://www.1024cores.net/home/lock-free-algorithms

Я не понимаю связи между этой статьей и как concurrency работает под Clojure.

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

Ответ 1

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

Это комбинация алгоритмов, структуры данных и времени.

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

Неизменяемые структуры данных: коллекции Clojure сохраняются в смысле слова FP. Старые копии "сохраняются" после создания новых версий. таким образом, наблюдателям не нужно блокировать объекты, потому что они никогда не изменятся из-под них. Могут существовать более новые версии, основанные на версии, на которую они смотрят, хотя ничто не изменит их копию.
Функциональное программирование: чистое (или как можно ближе к нему). Функция принимает коллекцию в один момент времени и создает следующую версию без совместного использования их внутреннего состояния, поэтому блокировка не потребуется. Это также имеет много других преимуществ.
Скоординированное время: когда нужно скоординировать несколько объектов, как в случае любой интересной системы, тогда Clojure временная модель. Существуют разные механизмы для разных целей. у этого есть одна блокировка, внутренне используемая для подсчета приращений времени, так что существует ровно один раз ноль, один раз один и один раз N. Таким образом, он не является строго заблокированным. STM содержит блокировки, которые вы никогда не должны взаимодействовать с

* хорошо... почти никогда; -)

Ответ 2

Если вы grep вокруг источника Clojure и, в частности,.java файлов, вы найдете немало ссылок на пакет java.util.concurrent. Пакет java.util.concurrent является кульминацией буквально десятилетий исследований concurrency Дуга Ли в SUNY Oswego. В частности, существуют ссылки на классы атомной переменной (например, AtomicReference), которые позволяют получить доступ к "сравнению и свопированию" (также называемому "сравнить и установить" или CAS) инструкция. Инструкция CAS немного сложно объяснить (я предоставляю ссылку ниже), но правильное использование CAS лежит в основе того, что означает, что алгоритм "свободен от блокировки" (по крайней мере, в мире Java). Свободные алгоритмы в конечном итоге приводят к большей пропускной способности и меньшему соперничеству для высококонкурентных приложений; точно домен, на который нацеливается Clojure.

Для углубленного изучения этой темы прочитайте Java concurrency на практике Брайаном Гетцем. Также см. Статью статьи того же автора.

В качестве побочного примечания мне всегда было трудно использовать пакет java.util.concurrent напрямую, даже когда он развился. Для меня это было слишком низко. Замечательная вещь о Clojure заключается в том, что она предоставляет доступ к этой экспертной библиотеке concurrency, но благодаря потрясающим простым в использовании абстракциям транзакционной памяти программного обеспечения (STM). Это действительно достижение.