Concurrency Primitives (IORef, MVar, TVar)

Comparison Table

Property	IORef	MVar	TVar (STM)
Atomic read-modify-write?	NO (race condition)	YES (takeMVar/putMVar)	YES (atomically)
Wait-free?	YES (never blocks)	NO (blocks on empty/full)	NO (may retry)
Deadlock-free?	YES (trivially — never blocks)	Depends: single MVar = YES, multiple MVars = can deadlock	YES (STM uses optimistic concurrency, no locks)
Starvation-free?	YES (trivially — never blocks)	YES for single MVar (FIFO wakeup fairness), NO for multiple MVars	NO — a long transaction can be repeatedly aborted by shorter ones and re-execute indefinitely
Blocking?	No	Yes (takeMVar blocks if empty, putMVar blocks if full)	Yes (retry blocks until TVar changes)

IORef in Detail

changeIORef :: IORef Int -> IO ()
changeIORef ref = do
  currentValue <- readIORef ref       -- READ
  let newValue = currentValue * 2 + 1
  writeIORef ref newValue             -- WRITE
-- NOT atomic! Another thread can read/write between the READ and WRITE
-- Result: lost updates (race condition)

- atomicModifyIORef IS atomic for read-modify-write - casIORef (compare-and-swap) is atomic - CAS-based retry loops are typically lock-free, but not automatically wait-free - Since IORef never blocks: trivially deadlock-free and starvation-free

MVar in Detail

changeMVar :: MVar Int -> IO ()
changeMVar var = do
  currentValue <- takeMVar var   -- atomically takes value, MVar now EMPTY
  let newValue = currentValue * 2 + 1
  putMVar var newValue           -- puts new value, MVar now FULL
-- Atomic: no other thread can access between take and put
-- But: if two MVars needed, can DEADLOCK (lock ordering problem)

- takeMVar = acquire lock (blocks if empty) - putMVar = release lock (blocks if full) - Single MVar: deadlock-free AND starvation-free (GHC uses FIFO wakeup — blocked threads are woken in order) - Multiple MVars: can deadlock (circular wait) and can starve

TVar/STM in Detail

changeTVar :: TVar Int -> IO ()
changeTVar var = atomically $ do
  currentValue <- readTVar var
  let newValue = currentValue * 2 + 1
  writeTVar var newValue
-- Atomic: entire block executes as one transaction
-- Deadlock-free: STM uses optimistic concurrency, no locks
-- NOT starvation-free: a long transaction can be repeatedly aborted by
-- shorter transactions and never make progress ("livelock-like" starvation)

- retry: abort and restart transaction when a TVar changes - orElse: try first transaction, if it retries, try second - Transactions are composable (unlike locks!) - When a read-set TVar changes, blocked transactions are woken and retried - STM does not guarantee fairness or progress: a long transaction can still starve indefinitely - STM also cannot communicate why a thread is blocking; it only knows which TVars were read before retry

STM Transaction Size Tradeoffs

Choosing how to scope atomically blocks matters:

Larger transactions	Smaller transactions
More atomic (more operations together)	Less atomic (intermediate states visible)
Higher conflict rate (more TVars read/written → more retries)	Lower conflict rate
Risk of starvation if transaction is large and frequently aborted	Less starvation risk
Simpler to reason about	May require careful manual sequencing

Rule: Keep transactions as small as possible while preserving the invariants you need to be atomic. Don't include IO operations inside atomically (the type system prevents this).

Race Condition Bug Patterns (2020 Exam Style)

Check-then-act (TOCTOU — time-of-check to time-of-use):

-- BUGGY: non-atomic check + act with IORef
order :: IORef Int -> Int -> IO ()
order stockRef amount = do
  stock <- readIORef stockRef          -- CHECK
  if stock >= amount                   -- condition may become false before act
    then writeIORef stockRef (stock - amount)  -- ACT
    else return ()
-- Another thread can decrement stock between CHECK and ACT

Fix: use atomicModifyIORef, MVar, or STM.

Lost update:

-- BUGGY: read-modify-write with IORef
increment :: IORef Int -> IO ()
increment ref = do
  v <- readIORef ref   -- Thread A reads 5
  writeIORef ref (v+1) -- Thread B also reads 5, writes 6; Thread A then writes 6
                       -- Should have been 7 — one increment is lost

Atomic Operations (Hardware)

• CAS (Compare-And-Swap): atomic_compare_exchange(ptr, expected, new) → atomically: if *ptr == expected, write new, return success
• Fetch-Or: atomic_fetch_or(ptr, val) → atomically: old = *ptr; *ptr = old | val; return old
• CAS loop pattern for implementing any atomic operation:

  do {
    old = *variable;
    new = f(old);
    result = atomic_compare_exchange(variable, old, new);
  } while (!result.success);
  return result.original;
  

Lock Implementation with Fetch-Or (2024 Retake Q1)

• State: 0 = free, 1 = locked (bit values for bitwise OR)
• Acquire: while (atomic_fetch_or(&state, 1) == 1) { /* spin */ }
• If was 0: OR with 1 → becomes 1, returns 0 (was free, now locked, enter)
• If was 1: OR with 1 → stays 1, returns 1 (was locked, keep spinning)
• Release: state = 0
• Implementing fetch_or with CAS: CAS loop that reads old, computes old | arg, tries to swap