Параллельный Haskell - Concurrent Haskell - Wikipedia

Параллельный Haskell расширяет[1] Haskell 98 с явным параллелизм. Его две основные концепции:

  • Примитивный тип Мвар α реализация ограниченного / одноместного асинхронный канал, который либо пуст, либо содержит значение типа α.
  • Возможность создавать одновременно нить через forkIO примитивный.

Поверх этого построен набор полезных абстракций параллелизма и синхронизации.[2] Такие как неограниченные каналы, семафоры и выборочные переменные.

Потоки Haskell имеют очень низкие накладные расходы: создание, переключение контекста и планирование являются внутренними для среды выполнения Haskell. Эти потоки уровня Haskell отображаются на настраиваемое количество потоков уровня ОС, обычно по одному на ядро процессора.

Программная транзакционная память

В программная транзакционная память (STM) расширение[3] к GHC повторно использует примитивы процесса разветвления Concurrent Haskell. Однако СТМ:

  • избегает Мварs в пользу TVarс.
  • вводит повторить попытку и orElse примитивы, позволяющие альтернативу атомные действия быть составлен вместе.

Монада СТМ

СТМ монада[4] это реализация программной транзакционной памяти на Haskell. Он реализован в GHC и позволяет изменять изменяемые переменные в сделки.

Традиционный подход

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

тип Счет = IORef Целое числопередача :: Целое число -> Счет -> Счет -> IO ()передача количество из к = делать    fromVal <- readIORef из  - (А)    toVal   <- readIORef к    writeIORef из (fromVal - количество)    writeIORef к (toVal + количество)

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

Традиционное решение такой проблемы - запирание. Например, могут быть наложены блокировки на модификации учетной записи, чтобы гарантировать, что кредиты и дебетования происходят атомарно. В Haskell блокировка выполняется с помощью MVars:

тип Счет = Мвар Целое числокредит :: Целое число -> Счет -> IO ()кредит количество учетная запись = делать    Текущий <- takeMVar учетная запись    putMVar учетная запись (Текущий + количество)списание средств :: Целое число -> Счет -> IO ()списание средств количество учетная запись = делать    Текущий <- takeMVar учетная запись    putMVar учетная запись (Текущий - количество)

Использование таких процедур гарантирует, что деньги никогда не будут потеряны или получены из-за неправильного чередования операций чтения и записи в любой индивидуальной учетной записи. Однако, если кто-то пытается составить их вместе, чтобы создать такую ​​процедуру, как передача:

передача :: Целое число -> Счет -> Счет -> IO ()передача количество из к = делать    списание средств количество из    кредит количество к

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

Атомарные транзакции

Чтобы избежать этого, можно использовать монаду STM, которая позволяет писать атомарные транзакции. Это означает, что все операции внутри транзакции полностью завершены, без каких-либо других потоков, изменяющих переменные, которые использует наша транзакция, или происходит сбой, и состояние откатывается до того места, где оно было до начала транзакции. Короче говоря, атомарные транзакции либо завершаются полностью, либо как будто они никогда не выполнялись вообще. Код на основе блокировки, приведенный выше, переводится относительно просто:

тип Счет = TVar Целое числокредит :: Целое число -> Счет -> СТМ ()кредит количество учетная запись = делать    Текущий <- readTVar учетная запись    writeTVar учетная запись (Текущий + количество)списание средств :: Целое число -> Счет -> СТМ ()списание средств количество учетная запись = делать    Текущий <- readTVar учетная запись    writeTVar учетная запись (Текущий - количество)передача :: Целое число -> Счет -> Счет -> СТМ ()передача количество из к = делать    списание средств количество из    кредит количество к

Типы возврата СТМ () может означать, что мы составляем скрипты для транзакций. Когда приходит время фактически выполнить такую ​​транзакцию, функция атомарно :: STM a -> IO a используется. Вышеупомянутая реализация гарантирует, что никакие другие транзакции не влияют на переменные, которые она использует (от и до) во время ее выполнения, позволяя разработчику быть уверенным, что условия гонки, подобные приведенным выше, не встречаются. Можно внести дополнительные улучшения, чтобы убедиться, что другие "бизнес-логика "поддерживается в системе, то есть транзакция не должна пытаться забрать деньги со счета, пока на нем не будет достаточно денег:

передача :: Целое число -> Счет -> Счет -> СТМ ()передача количество из к = делать    fromVal <- readTVar из    если (fromVal - количество) >= 0        тогда делать               списание средств количество из               кредит количество к        еще повторить попытку

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

Пример программы, использующей передаточную функцию, может выглядеть так:

модуль Главный кудаимпорт Control.Concurrent (forkIO)импорт Control.Concurrent.STMимпорт Control.Monad (навсегда)импорт System.Exit (exitSuccess)тип Счет = TVar Целое числоглавный = делать    боб <- новый аккаунт 10000    Джилл <- новый аккаунт 4000    повторение 2000 $ forkIO $ атомарно $ передача 1 боб Джилл    навсегда $ делать        bobBalance <- атомарно $ readTVar боб        jillBalance <- атомарно $ readTVar Джилл        putStrLn ("Баланс Боба:" ++ Показать bobBalance ++ ", Баланс Джилл:" ++ Показать jillBalance)        если bobBalance == 8000            тогда exitSuccess            еще putStrLn «Попытка снова».повторение :: Целое число -> IO а -> IO аповторение 1 м = мповторение п м = м >> повторение (п - 1) мновый аккаунт :: Целое число -> IO Счетновый аккаунт количество = новыйTVarIO количествопередача :: Целое число -> Счет -> Счет -> СТМ ()передача количество из к = делать    fromVal <- readTVar из    если (fromVal - количество) >= 0        тогда делать               списание средств количество из               кредит количество к        еще повторить попыткукредит :: Целое число -> Счет -> СТМ ()кредит количество учетная запись = делать    Текущий <- readTVar учетная запись    writeTVar учетная запись (Текущий + количество)списание средств :: Целое число -> Счет -> СТМ ()списание средств количество учетная запись = делать    Текущий <- readTVar учетная запись    writeTVar учетная запись (Текущий - количество)

который должен распечатать "баланс Боба: 8000, баланс Джилл: 6000". Здесь атомарно функция использовалась для запуска действий STM в монаде ввода-вывода.

Рекомендации

  1. ^ Саймон Пейтон Джонс, Эндрю Д. Гордон, и Зигбьерн Финн. Параллельный Haskell. Симпозиум ACM SIGPLAN-SIGACT по принципам языков программирования (PoPL). 1996. (Некоторые разделы устарели относительно текущей реализации.)
  2. ^ В Иерархические библиотеки Haskell, Control.Concurrent В архиве 2012-08-02 в Archive.today
  3. ^ Тим Харрис, Саймон Марлоу, Саймон Пейтон Джонс и Морис Херлихи. Составные транзакции памяти. ACM Симпозиум по принципам и практике параллельного программирования 2005 (PPoPP'05). 2005 г.
  4. ^ Control.Concurrent.STM