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:
- A threadDelay used as synchronisation: the program works on a fast machine and fails on a slow one, as in the forkIO lesson where a missing takeMVar let the program exit early.
- A read and a write separated by other work, which is the lost update of the MVar lesson; the fix is modifyMVar_ or one transaction.
- An output order that the program does not control, such as two workers printing at once; if the order matters, one thread collects the lines and prints them, which is the logger of the worker pool capstone.
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
- Fix the deadlock by taking the two MVars in the same order in both threads.
- Add a third MVar and a cycle of three threads, and run it.
- Write the two-account transfer with modifyMVar_ and explain why it still has a race.
- Replace a threadDelay with an MVar signal in one of the earlier programs.
- Explain what the runtime checks before it prints the deadlock message.
- 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.
-
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.
-
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.
-
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.
-
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 >>= printAnswer
3
The box holds 3, the take returns it and print shows it.
-
Why is
threadDelaya 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.
-
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 >>= printAnswer
7
The transaction swapped the two values, so the first TVar now holds 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.
-
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.
-
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.
-
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