Программирование без блокировки в Haskell

Кто-нибудь знает, можно ли сделать программирование без блокировки в Haskell? Меня интересует как вопрос о том, доступны ли соответствующие низкоуровневые примитивы, так и (если они есть) любая информация о том, что работает с точки зрения использования их для построения работающих крупномасштабных систем в чисто функциональном контексте. (Я никогда раньше не занимался программированием без блокировки в чисто функциональном контексте.) Например, как я понимаю, контроль.Параллельный.Каналы Чан построены поверх MVars, которые (как я понимаю) используют замки - - - можно ли в принципе построить версии примитива Chan, которые внутренне свободны от блокировки? Какой прирост производительности можно было бы надеяться получить?

Я также должен сказать, что я знаком с существованием TVars, но не понимаю их внутреннюю реализацию-мне дали понять, что они в основном свободны от блокировки, но я не уверен, что они полностью свободны от блокировки. Так что любая информация о внутренней реализации Тварс было бы также полезно!

(этот Поток предоставляет некоторую дискуссию, но мне интересно, есть ли что-нибудь более современное/более всеобъемлющее.)

3 8
haskell lock-free

3 ответа:

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

Для реального программирования без блокировки вы хотите использовать IORefs напрямую, вместе с atomicModifyIORef.

Edit: Что касается черных дыр, насколько я помню, реализация свободна от блокировки, но я не могу поручиться за подробности. Механизм описан в разделе "Поддержка среды выполнения для многоядерного Haskell": http://research.microsoft.com/en-us/um/people/simonpj/papers/parallel/multicore-ghc.pdf

Но эта реализация претерпела некоторые изменения, я думаю, как описано в докладе Саймона Марлоу 2010 Haskell Implementors Workshop "планирование ленивой оценки на многоядерных процессорах": http://haskell.org/haskellwiki/HaskellImplementorsWorkshop/2010 . слайды, к сожалению, находятся в автономном режиме, но видео должно быть все еще работают.
5

Программирование без блокировки является тривиальным в Haskell. Самый простой способ иметь общий фрагмент данных, который должен быть изменен многими потоками, - это начать с любого нормального типа haskell (список, карта, возможно, все, что вам нужно) и поместить его в IORef. Как только вы это сделаете, у вас будет возможность использовать atomicModifyIORef для выполнения изменений на месте, которые гарантированно не займут много времени.

type MyDataStructure = [Int]
type ConcMyData = IORef MyDataStructure

main = do
    sharedData <- newIORef []
    ...
    atomicModifyIORef sharedData (\xs -> (1:xs,()))

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

Вывод из этого состоит в том, что такого рода абстракция легко реализуется только в чистом языке, где значение вещей никогда не меняется (за исключением, конечно, когда это происходит, с типами типа IORef, MVars и STM). Природа копирования на запись структур данных Haskell означает, что модифицированные структуры могут совместно использовать много данных с исходной структурой, выделяя только то, что является новым для структуры.

Не думаю, что я очень хорошо объяснил, как это работает, но я вернусь завтра и уточню свой ответ.

Для получения дополнительной информации смотрите слайды для выступлениямногоядерное программирование в Haskell Саймона Марлоу из Microsoft Research (и одного из основных разработчиков GHC).

4

Загляните в stm, а именно в его тип TChan.

2