Параллельный Haskell

Haskell Параллельное расширение Haskell 98 с явным параллелизмом . Две основные концепции, лежащие в его основе, таковы:

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

На основе этого создан набор полезных абстракций параллелизма и синхронизации. такие как неограниченные каналы , семафоры и выборочные переменные.

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

память

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

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

STM-монада

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

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

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

type Account = IORef Integer

transfer :: Integer -> Account -> Account -> IO ()
transfer amount from to = do
    fromVal <- readIORef from  -- (A)
    toVal   <- readIORef to
    writeIORef from (fromVal - amount)
    writeIORef to (toVal + amount)

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

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

type Account = MVar Integer

credit :: Integer -> Account -> IO ()
credit amount account = do
    current <- takeMVar account
    putMVar account (current + amount)

debit :: Integer -> Account -> IO ()
debit amount account = do
    current <- takeMVar account
    putMVar account (current - amount)

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

transfer :: Integer -> Account -> Account -> IO ()
transfer amount from to = do
    debit amount from
    credit amount to

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

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

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

type Account = TVar Integer

credit :: Integer -> Account -> STM ()
credit amount account = do
    current <- readTVar account
    writeTVar account (current + amount)

debit :: Integer -> Account -> STM ()
debit amount account = do
    current <- readTVar account
    writeTVar account (current - amount)

transfer :: Integer -> Account -> Account -> STM ()
transfer amount from to = do
    debit amount from
    credit amount to

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

transfer :: Integer -> Account -> Account -> STM ()
transfer amount from to = do
    fromVal <- readTVar from
    if (fromVal - amount) >= 0
        then do
               debit amount from
               credit amount to
        else retry

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

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

module Main where

import Control.Concurrent (forkIO)
import Control.Concurrent.STM
import Control.Monad (forever)
import System.Exit (exitSuccess)

type Account = TVar Integer

main = do
    bob <- newAccount 10000
    jill <- newAccount 4000
    repeatIO 2000 $ forkIO $ atomically $ transfer 1 bob jill
    forever $ do
        bobBalance <- atomically $ readTVar bob
        jillBalance <- atomically $ readTVar jill
        putStrLn ("Bob's balance: " ++ show bobBalance ++ ", Jill's balance: " ++ show jillBalance)
        if bobBalance == 8000
            then exitSuccess
            else putStrLn "Trying again."

repeatIO :: Integer -> IO a -> IO a
repeatIO 1 m = m
repeatIO n m = m >> repeatIO (n - 1) m

newAccount :: Integer -> IO Account
newAccount amount = newTVarIO amount

transfer :: Integer -> Account -> Account -> STM ()
transfer amount from to = do
    fromVal <- readTVar from
    if (fromVal - amount) >= 0
        then do
               debit amount from
               credit amount to
        else retry

credit :: Integer -> Account -> STM ()
credit amount account = do
    current <- readTVar account
    writeTVar account (current + amount)

debit :: Integer -> Account -> STM ()
debit amount account = do
    current <- readTVar account
    writeTVar account (current - amount)

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