Попытка понять простые вещи Haskell STM

Я застрял в понимании концепции атомарности в STM.

поясняю на примере

import Control.Concurrent
import Control.Concurrent.STM
import Control.Monad
import qualified Data.Map as Map 

main :: IO ()
main =  do
    d <- atomically$ newTVar Map.empty
    sockHandler  d 

sockHandler ::  TVar (Map.Map String Int)-> IO ()
sockHandler  d = do
    forkIO $ commandProcessor  d 1
    forkIO $ commandProcessor  d 2
    forkIO $ commandProcessor  d 3
    forkIO $ commandProcessor  d 4
    forkIO (threadDelay 1000 >> putStrLn "Hello World?")

    threadDelay 10000
    return ()

commandProcessor ::  TVar (Map.Map String Int)-> Int-> IO ()
commandProcessor  d i= do
  addCommand d i
  commandProcessor  d i 

addCommand  ::  TVar (Map.Map String Int) ->Int -> IO ()
addCommand    d i = do
  succ <- atomically $ runAdd d
  putStrLn  $"Result of add in " ++ (show i)++ " " ++( show succ)

runAdd  d =do
  dl <- readTVar d
  let (succ,g)= if   Map.member "a" dl
                  then
                      (False,dl)
                  else
                      (True,Map.insert "a" 9 dl)
  writeTVar d g
  return succ

Пример вывода будет таким:

Результат добавления в 1 True Результат добавления в 4 False Результат добавления в 1 FalseРезультат добавления в 2 FalseРезультат добавления в 3 False Hello World? Результат добавления в 4 False

Результат добавления в 1 FalseРезультат добавления в 2 False Результат добавления в 3 False Результат добавления в 4 False

Результат добавления в 1 False Результат добавления в 2 FalseРезультат добавления в 3 FalseРезультат добавления в 4 False

Результат добавления в 1 False Результат добавления в 2 FalseРезультат добавления в 3 FalseРезультат добавления в 4 False

Результат добавления в 1 False Результат добавления в 2 FalseРезультат добавления в 4 FalseРезультат добавления в 3 False

Результат добавления в 1 False Результат добавления в 4 FalseРезультат добавления в 2 FalseРезультат добавления в 3 False

Результат добавления в 1 FalseРезультат добавления в 4 False Результат добавления в 2 False Результат добавления в 3 False

Результат добавления в 1 FalseРезультат добавления в 4 False

Результат добавления в 2 FalseРезультат добавления в 3 False

Результат добавления в 1 FalseРезультат добавления в 4 False

Результат добавления в 2 FalseРезультат добавления в 3 False Результат добавления в 1 False Результат добавления в 4 False

Результат добавления в 2 FalseРезультат добавления в 3 False

Результат добавления в 1 FalseРезультат добавления в 4 False

Когда я прочитал об атомном

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

Итак, на вопрос, может ли «возврат» успеха в некоторых случаях никогда не произойти? Это может быть строка succ ‹- атомарно $ runAdd d putStrLn $"Результат добавления в " ++ (показать i)++ " " ++(показать succ)

дать вывод «Результат добавления в ?i» («как будто они вообще никогда не запускались»)


person Jonke    schedule 02.02.2011    source источник


Ответы (2)


Если транзакция откатывается, ваша программа пытается снова. Вы можете представить себе реализацию atomically примерно так:

atomically action = do varState <- getStateOfTVars
                       (newState, ret) <- runTransactionWith action varState
                       success <- attemptToCommitChangesToTVars newState
                       if success
                         then return ret
                         else atomically action -- try again

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

person Neil Brown    schedule 02.02.2011
comment
Хорошо, у вас есть ссылка на это? - person Jonke; 02.02.2011
comment
Я нахожу исходную статью по Haskell-STM очень читаемой, вы можете получить копию здесь: research.microsoft.com/en-us/um/people/simonpj/papers/stm/ Исходя из вашего примера, я думаю, что вам будет достаточно просто прочитать разделы 3 и 6. , и должно дать вам хорошее представление о том, как работает STM. - person Neil Brown; 02.02.2011
comment
Обратите внимание, что если вам нужно поведение, отличное от повторения до успеха, вы можете использовать функции из Control.Monad.STM для его реализации. - person John L; 02.02.2011

  1. threadDelay уже возвращает (), нет необходимости явно return () после этого
  2. newTVarIO — это сокращенная версия atomically . newTVar.
  3. Это более читабельно, если вы используете forever вместо того, чтобы называть себя хвостом, как это сделано в commandProcessor.

Что касается вашего вопроса, то ответ «да». Это называется живой блокировкой, в которой у вашего потока есть работа, но он не может двигаться вперед. Представьте себе очень дорогую функцию expensive и очень дешевую функцию cheap. Если они работают в конкурирующих блоках atomically на одном и том же TVar, то дешевая функция может привести к тому, что функция expensive никогда не завершится. Я построил пример для связанного с SO вопроса.

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

person Thomas M. DuBuisson    schedule 03.02.2011
comment
Технически голодание — это ситуация, когда у потока есть работа, но он не может двигаться вперед. Livelock — это ситуация, когда ни один из потоков не продвигается вперед (из-за их действий, неоднократно вызывающих прерывание всех из них), и это крайне маловероятно в системах STM с семантикой отложенного получения. - person Ben; 03.02.2011
comment
@ben Я привык определять starvation как когда поток может работать, но никогда не запускается, обычно из-за какого-то аспекта планирования. - person Thomas M. DuBuisson; 03.02.2011
comment
Итак, я мог бы получить живой замок, но launchMissile (putStrnLn) никогда не сработает. Я больше боялся, что могу получить живую блокировку и что-то в конечном итоге истечет по времени и оставит меня в состоянии запуска со случайным значением. - person Jonke; 03.02.2011
comment
@TomMD Я предпочитаю отделять голодание от блокировки в реальном времени и тупика. Голодание — это когда ограниченные ресурсы (доступ к блокировке, достаточно длинное неконкурентное окно для завершения транзакции и т. д.) распределяются между потоками неравномерно, так что некоторые из них не могут выполняться, даже если пропускная способность системы может быть хорошей. Ключевым моментом является то, что при конечной рабочей нагрузке процесс с голоданием все равно в конечном итоге завершится. - person Ben; 22.02.2011
comment
@TomMD OTOH Livelock, как и взаимоблокировка, включает в себя потоки, мешающие друг другу таким образом, что ни один из них не может добиться прогресса. Хотя пропускная способность может по-прежнему быть хорошей, если есть другие незаблокированные потоки, процесс никогда не завершится, даже при ограниченной рабочей нагрузке. - person Ben; 22.02.2011
comment
@Jonke Это основная гарантия STM. Если транзакция завершается, она будет вести себя как если бы выполнялась последовательно между другими транзакциями. Вы не получите состояния, которые другие транзакции временно создают в процессе выполнения. Есть способы позволить транзакции сделать что-то похожее на тайм-аут, а не продолжать попытки бесконечно, но тогда вы знаете, что она не удалась; он не будет претендовать на успех с мусорным выводом. - person Ben; 22.02.2011