STM monad problem

Question

This is just a hypothetical scenario to illustrate my question. Suppose that there are two threads and one TVar shared between them. In one thread there is an atomically block that reads the TVar and takes 10s to complete. In another thread is an atomically block that modifies the TVar every second. Will the first atomically block ever complete? Surely it will just keep going back to the beginning, because the log is perpetually in an inconsistent state?

Blaeberry

Answer 1

As others have said: in theory there is no guarantee of progress. In practice there is also no guarantee of progress:

import Control.Monad -- not needed, but cleans some things up
import Control.Monad.STM
import Control.Concurrent.STM
import Control.Concurrent
import GHC.Conc
import System.IO

main = do
    tv <- newTVarIO 0
    forkIO (f tv)
    g tv

f :: TVar Int -> IO ()
f tv = forever $ do
    atomically $ do
            n <- readTVar tv
            writeTVar tv (n + 1)
            unsafeIOToSTM (threadDelay 100000)
    putStr "."
    hFlush stdout

g :: TVar Int -> IO ()
g tv = forever $ do
    atomically $ do
            n <- readTVar tv
            writeTVar tv (n + 1)
            unsafeIOToSTM (threadDelay 1000000)
    putStrLn "Done with long STM"

The above never says "Done with long STM" in my tests.

Obviously if you think the computation is still going to be valid/pertinent then you would want to either

1. Leave the atomic block, perform expensive computation, enter the atomic block / confirm assumptions are valid / and update the value. Potentially dangerous, but no more so than most locking strategies.
2. Memoize the results in the atomic block so the still valid result will be no more than a cheap lookup after a retry.

Pesek

Excellent example. I wanted to test with something like this, but I wasn't aware of the unsafeIOToSTM function! – Blaeberry

Answer 2

STM prevents deadlock, but is still vulnerable to starvation. It is possible in a pathological case for the 1s atomic action to always aquire the resource.

However, the changes of this happening are very rare -- I don't believe I've ever seen it in practice.

For the semantics, see Composable Memory Transactions, section 6.5 "Progress". STM in Haskell guarantees only that a running transaction will successfully commit (i.e. no deadlock), but in the worst case an infinite transaction will block others.

Hairline

STMs are not necessarily non-blocking. – Galactic

Answer 3

No, it would work fine. Exactly how the two threads would interact depends on the retry logic.

For example, let's say you have:

ten tv = do
  n <- readTVar tv
  when (n < 7) retry
  writeTVar tv 0
  -- do something that takes about 10 seconds

one tv = do
  modifyTVar tv (+1)
  -- do something that takes about 1 second

So the "ten" thread will be in retry state until the TVar reaches the value 7, then it will proceed.

Note that you can't directly control how long these computations will take inside the STM monad. That would be a side-effect, and side-effects are not allowed in STM calculations. The only way to communicate with the outside world is via values passed through transactional memory.

And that means that if the "baton-passing" logic through transactional memory is correct, the program will work correctly independently of the exact amount of time any part of it takes. That's part of the guarantee of STM.

Atul

I'm really thinking of a worst case scenario. Let's forget retrys for a moment and just think of two threads, and consider the execution of the STM 'ten'. It reads the TVar, and commits that value to the log. Meanwhile, the other thread changes that TVar always during the execution of 'ten'. So, at the end of the execution of 'ten', the value in the real TVar is not the same as the value initially read in 'ten', forcing 'ten' to re-initialize the log and re-execute every time. – Blaeberry

As Yitz said, it depends. Yes, it is possible to construct a situation where a transaction can never complete. Or more formally, STM doesn't guarantee progress. – Cocainism