Параллельный 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   ->   Account   ->   Account   ->   IO   () 
 перевода   сумма   от   to   =   do 
     fromVal   <-   readIORef   from    -- (A) 
     toVal     <-   readIORef   to 
     writeIORef   from   (  fromVal   -   количество  ) 
     writeIORef   to   (  toVal   +   сумма  ) 

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

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

type   Account   =   MVar   Целочисленный 

 кредит   ::   Целое   ->   Счет   ->   IO   () 
 кредита   сумма   счет   =   do 
     current   <-   takeMVar   счет 
     putMVar   счет   (  текущий   +   сумма  ) 

 дебет   ::   Целое   ->   Счет   ->   IO   () 
 дебета   сумма   счет   =   do 
     current   -   takeMVar   account 
     putMVar   account   (  текущая   сумма   )  < 

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

перевод   ::   Целое   ->   Счет   ->   Счет   ->   IO   () 
 перевода   сумма   от   до   =   сделать 
     дебета   сумму   от 
     кредита   суммы   до 

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

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

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

type   Account   =   TVar   Целочисленный 

 кредит   ::   Целое   ->   Счет   ->   STM   () 
 кредита   сумма   счет   =   do 
     current   <-   readTVar   счет 
     writeTVar   счет   (  текущий   +   сумма  ) 

 дебет   ::   Целое   ->   Счет   ->   STM   () 
 дебета   сумма   счет   =   do 
     current   <-   readTVar   account 
     writeTVar   account   (  current   -   Transfer  mount) 

 ::   Integer   -   Account   -   >   Account   ->   STM   () 
 перевода   сумма   от   до   =   сумма 
     дебета   суммы   от 
     кредита   к   > 

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

Transfer   ::   Integer   ->   Account   ->   Account   ->   STM   () 
 перевода   сумма   от   to   =   do 
     fromVal   <-   readTVar   from 
     if   (  fromVal   -   sum  )   >=   0 
         , затем   выполнить 
                дебет   суммы   из 
                кредита   суммы   , чтобы 
         еще раз   повторить попытку 

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

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

модуль   Main   где 

 импорт   Control.Concurrent   (  forkIO  ) 
 импорт   Control.Concurrent.STM 
 импорт   Control.Monad   (  навсегда  ) 
 импорт   System.Exit   (  exitSuccess  ) 

 тип   Account   =   TVar   Integer 

 main   =   do 
     bob   <-   newAccount   10000 
     jill   <-   newAccount   4000 
     повторитеIO   2000   $   forkIO   $   атомарно   $   трансфер   1   боб   jill 
     навсегда   $   do 
         bobBalance   <-   атомарно   $   readTVar   bob 
         jillBalance   <-   атомарно   $   readTVar   jill 
         putStrLn   (  "Баланс Боба: "   ++   show   bobBalance   ++   ", баланс Джилл: "   ++   show   jillBalance  ) 
         если   bobBalance   ==   8000 
             , то   exitSuccess 
             , иначе   putStrLn   "Повторная попытка." 

  повторитеIO   ::   Integer   ->   IO   a   ->   IO   a 
 повторитеIO   1   m   =   m 
 повторитеIO   n   m   =   m   >>   повторитеIO   (  n   -   1  )   m 

 newAccount   ::   Integer   ->   IO   Account 
 newAccount   sum   =   newTVarIO   сумма 

 перевода   ::   Integer   ->   Учетная запись   ->   Учетная запись   ->   STM   () 
 перевода   сумма   из   в   =   do 
     fromVal   <-   readTVar   from 
     if   (  fromVal   -   sum  )   >=   0 
         затем   выполнить 
                дебетование   суммы   из 
                кредита   суммы   в 
         противном случае   повторить 

 попытку кредита   ::   Integer   ->   Account   ->   STM   ( ) 
 кредита   сумма   счет   =   сделать 
     текущий   <-   readTVar   учетная запись 
     TVar   учетная запись   (  текущий   +   сумма  ) 

 дебет   ::   Integer   ->   Счет   ->   STM   () 
 дебета   сумма   учетная запись   сделать   текущий 
     <   -   readTVar   учетная запись 
     TVar   учетная запись   (  текущая   сумма   =  ) 

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