Из Википедии, свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

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

Монада STM [ править ]

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

Традиционный подход [ править ]

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

type  Account  =  IORef  Integertransfer  ::  Integer  ->  Account  ->  Account  ->  IO  () переводить  сумму  из  to  =  do  fromVal  <-  readIORef  from  - (A)  toVal  <-  readIORef  to  writeIORef  from  ( fromVal  -  amount )  writeIORef  to  ( toVal  +  amount )

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

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

тип  Account  =  MVar  Integercredit  ::  Integer  ->  Account  ->  IO  () кредитная  сумма  account  =  do  current  <-  takeMVar  account  putMVar  account  ( current  +  amount )debit  ::  Integer  ->  Account  ->  IO  () дебетовая  сумма  account  =  do  current  <-  takeMVar  account  putMVar  account  ( current  -  amount )

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

transfer  ::  Integer  ->  Account  ->  Account  ->  IO  () переводить  сумму  из  в  =  делать  дебетовую  сумму  из  суммы кредита  в

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

Атомарные транзакции [ править ]

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

тип  Account  =  TVar  Целое числоcredit  ::  Integer  ->  Account  ->  STM  () кредитная  сумма  account  =  do  current  <-  readTVar  account  writeTVar  account  ( current  +  amount )debit  ::  Integer  ->  Account  ->  STM  () дебетовая  сумма  account  =  do  current  <-  readTVar  account  writeTVar  account  ( current  -  amount )перевод  ::  Integer  ->  Account  ->  Account  ->  STM  () перевод  сумма  от  к  =  сделать  дебетовую  сумму  от  кредитной  суммы  до

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

перевод  ::  Integer  ->  Account  ->  Account  ->  STM  () перевод  сумма  от  к  =  сделать  fromVal  <-  readTVar  от  если  ( fromVal  -  сумма )  > =  0 ,  то  сделать  дебетовую  сумму  от  кредитной  суммы  к  другому  повторить попытку

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

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

модуль  Main  гдеimport  Control.Concurrent  ( forkIO ) import  Control.Concurrent.STM import  Control.Monad  ( навсегда ) import  System.Exit  ( exitSuccess )тип  Account  =  TVar  Целое числоОсновные  =  сделать  боб  <-  NewAccount  10000  Jill  <-  NewAccount  4000  repeatIO  2000  $  forkIO  $  атомарно  $  трансферт  1  боб  Jill  навсегда  $  сделать  bobBalance  <-  атомарно  $  readTVar  боб  jillBalance  <-  атомарно  $  readTVar  Jill  putStrLn  ( "Баланс Боба:"  ++  show  bobBalance  ++  ", баланс Джилл:"  ++  show jillBalance )  если  bobBalance  ==  8000,  то  exitSuccess  else  putStrLn  " Повторная попытка ".repeatIO  ::  Integer  ->  IO  a  ->  IO  a repeatIO  1  m  =  m repeatIO  n  m  =  m  >>  repeatIO  ( n  -  1 )  mnewAccount  ::  Integer  ->  IO  Account newAccount  amount  =  newTVarIO  amountперевод  ::  Integer  ->  Account  ->  Account  ->  STM  () перевод  сумма  от  к  =  сделать  fromVal  <-  readTVar  от  если  ( fromVal  -  сумма )  > =  0 ,  то  сделать  дебетовую  сумму  от  кредитной  суммы  к  другому  повторить попыткуcredit  ::  Integer  ->  Account  ->  STM  () кредитная  сумма  account  =  do  current  <-  readTVar  account  writeTVar  account  ( current  +  amount )debit  ::  Integer  ->  Account  ->  STM  () дебетовая  сумма  account  =  do  current  <-  readTVar  account  writeTVar  account  ( current  -  amount )

который должен распечатать «Баланс Боба: 8000, баланс Джилл: 6000». Здесь atomicallyфункция использовалась для запуска действий 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