Deadlocks and races

Two MVars, two threads

A deadlock is two threads each holding what the other waits for. With MVars it is four lines: one thread takes the left box and then the right, the other takes them in the opposite order. Neither can continue, and the runtime knows it, because no thread can run.

takeMVar left -- thread A holds left takeMVar right -- thread B holds right -- A waits for right, B waits for left

The classic fixes are a global order on the locks, a timeout on the take, or a transaction that takes both at once. The STM version below is the third: the two reads and the two writes commit together or not at all, so there is no state in which one box is held and the other is not.

A deadlock that the runtime reports

module Main (main) where import Control.Concurrent (forkIO, threadDelay) import Control.Concurrent.MVar (newMVar, putMVar, takeMVar) main :: IO () main = do left <- newMVar () right <- newMVar () _ <- forkIO $ do takeMVar left threadDelay 100000 takeMVar right putMVar right () putMVar left () takeMVar right threadDelay 100000 takeMVar left putStrLn "both took both"

ghc -Wall -O1 -threaded -o deadlock deadlock.hs
./deadlock
echo "status: $?"

deadlock: thread blocked indefinitely in an MVar operation
status: 1

The line on stderr is the runtime's deadlock detection: every thread is blocked on an MVar and no write can wake one, so the program is finished. The status is 1, and both took both never prints. Not every deadlock is detected, because a program that waits on a socket or a foreign call is not visible to this check, but the MVar case is the one a beginner meets first.

The same transfer as a transaction

module Main (main) where import Control.Concurrent.STM main :: IO () main = do left <- newTVarIO (10 :: Int) right <- newTVarIO (20 :: Int) atomically $ do a <- readTVar left b <- readTVar right writeTVar left (a - 5) writeTVar right (b + 5) readTVarIO left >>= print readTVarIO right >>= print

ghc -Wall -O1 -threaded -o stmfix stmfix.hs
./stmfix

5
25

The transfer is one transaction, so no observer can see the moment when the money has left one account and not arrived at the other, and two concurrent transfers cannot deadlock: one of them commits first and the other is retried against the new values. That is the property the pair of MVars could not give without a global order, and it is the reason STM exists.

Races and the delay in the wrong place

A race is the other failure: the program works because of a timing that is not guaranteed. Three shapes are worth recognising:

The lesson after this one starts the first capstone: a CSV report processor built over seven lessons, which reads a file, parses the lines, totals them and reports errors a user can read.

Exercises

  1. Fix the deadlock by taking the two MVars in the same order in both threads.
  2. Add a third MVar and a cycle of three threads, and run it.
  3. Write the two-account transfer with modifyMVar_ and explain why it still has a race.
  4. Replace a threadDelay with an MVar signal in one of the earlier programs.
  5. Explain what the runtime checks before it prints the deadlock message.
  6. Decide for a program of your own whether its order depends on timing.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What is a deadlock?

    Answer

    Two threads each wait for something the other holds

    Both are blocked on a resource the other one would have to release.

  2. What does the runtime print for the MVar deadlock?

    Answer

    thread blocked indefinitely in an MVar operation

    The message names the operation and the program exits with status 1.

  3. Why does the STM version not deadlock?

    Answer

    The two reads and writes are one transaction, so there is no half-held state

    The transaction commits as a whole or is retried; no lock is held between steps.

  4. What does this program print? module Main (main) where import Control.Concurrent.MVar (newMVar, takeMVar) main :: IO () main = do box <- newMVar (3 :: Int) takeMVar box >>= print

    Answer

    3

    The box holds 3, the take returns it and print shows it.

  5. Why is threadDelay a poor synchronisation?

    Answer

    The delay is a guess and a slow machine breaks it

    A signal such as an MVar or a TVar waits for the event instead of for a time.

  6. What does this program print? module Main (main) where import Control.Concurrent.STM main :: IO () main = do a <- newTVarIO (5 :: Int) b <- newTVarIO (7 :: Int) atomically $ do x <- readTVar a y <- readTVar b writeTVar a y writeTVar b x readTVarIO a >>= print

    Answer

    7

    The transaction swapped the two values, so the first TVar now holds 7.

  7. What is a race condition?

    Answer

    A result that depends on an order the program does not control

    The program works for one interleaving and fails for another.

  8. What does this program print? module Main (main) where import Control.Concurrent.MVar (newMVar, readMVar) main :: IO () main = do box <- newMVar "x" a <- readMVar box b <- readMVar box putStrLn (a ++ b)

    Answer

    xx

    readMVar puts the value back, so both reads see x.

  9. What is the simplest fix for two MVars taken in different orders?

    Answer

    Take them in one global order in every thread

    A consistent order removes the cycle that makes the deadlock.

  10. What does this program print? module Main (main) where main :: IO () main = print (sum [1 .. 5 :: Int])

    Answer

    15

    The sum of 1 to 5 is 15.

The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev