In the last article, we discussed how deadlocks can occur with mutex variables, channels, and semaphores, and how problematic they can be. Therefore, in this article, we will talk about an alternative mechanism that ensures consistency and prevents deadlocks: software transactional memory (STM).

Software Transactional Memory

If you are familiar with database transactions, software transactional memory will be quite intuitive. Unlike lock-based synchronization, which limits the acquisition of shared resources to one thread and can cause deadlocks, a transaction-based strategy allows all threads to access shared resources. Instead, it ensures that the shared resources are updated without conflict and reruns the thread if a conflict occurs. STM is implemented as an STM monad, which can perform transactions as STM actions (not as IO actions).

import Control.Concurrent.STM
 
-- Convert STM action to IO action
atomically :: STM a -> IO a
 
-- Retry the transaction explicitly
retry :: STM a
 
-- Choose STM action depending on condition (often for exceptions)
orElse :: STM a -> STM a -> STM a
 
-- throw exception within STM action
throwSTM :: Exception e => e -> STM a
 
-- Transactional variable (shared memory)
data TVar a
 
-- newly create TVar
newTVar :: a -> TVar a
 
-- STM actions for reading and writing to TVar
readTVar :: TVar a -> STM ()
writeTVar :: TVar a -> a -> STM ()

There are many other functions and data types available in the STM module, but the above are the main ones that we will be focusing on. The explanation does not cover the subtleties of the definitions, so I highly recommend checking out the documentation.

It is important to note that STM actions cannot contain any IO actions, only STM actions and functions. This ensures that unwanted side effects, which cannot be rolled back, do not occur—an important aspect of transactions. Hence, the only way to extract results from an STM action is to use atomically. Then, we have retry and orElse, which allow us to control when to roll back transactions and which transaction to perform conditionally, and throwSTM for throwing exceptions within STM actions. One of the ways to use shared memory in STM is through TVar, which can be read and written in a transaction.

Example

Let's look at STM in action to understand how it works. Below is a simple multithreaded program that calculates the sum of the elements in an array using STM.

import System.IO
import Control.Concurrent
import Control.Concurrent.STM
 
-- TVar storing sum and counter
type Result = TVar (Int, Int)
 
addToResult :: Result -> Int -> STM ()
addToResult result x = do
  (sum, endCtr) <- readTVar result
  writeTVar result (sum+x, endCtr+1)
 
waitForCounter :: Result -> Int -> STM Int
waitForCounter result limit = do
  (sum, endCtr) <- readTVar result
  if endCtr < limit then retry else return sum
 
main :: IO ()
main = do
  let n = 100
  result <- newTVarIO (0, 0)
  mapM_ (forkIO . atomically . addToResult result) [1..n]
  sum <- atomically $ waitForCounter result n
  putStrLn $ "The sum is " ++ show sum

The addToResult function combines two STM actions, readTVar and writeTVar, to create an STM action that implicitly commits the operations and retries if they fail. The waitForCounter function, on the other hand, uses an if-statement to specify when to retry the transaction. The newTVIO function is equivalent to atomically . newTVar, which creates a TVar and converts it to IO with atomically.

Perfect Synergy: Haskell and STM

As mentioned earlier, when implementing STM, it is important to ensure that transactions do not have side effects (such as IO actions or mutable arguments) so that they can be rolled back. Haskell's expressive type system and pure functional nature are ideal qualities for STM in this regard, as it isolates IO actions and makes variables immutable by default. The immutablility means we do not need to monitor changes made to the inputs to the functions when rolling back a transaction and undo the changes; we can simply retry the transaction.

Exercises

This is an exercise section where you can test your understanding of the material introduced in the article. I highly recommend solving these questions by yourself after reading the main part of the article. You can click on each question to see its answer.

Resources

• Harris, T. et al. 2006. Composable Memory Transactions. Microsoft.
• Philipp, Hagenlocher. 2020. Haskell for Imperative Programmers #30 - Software Transactional Memory (STM). YouTube.