Concurrency & Deadlock Lab
A few threads each run a small program that takes locks, reads a shared counter, adds to it, and writes it back. A deterministic scheduler interleaves them step by step. Watch the thread states, the lock ownership, the shared counter, and the wait-for graph to see how a missing lock causes a race condition and how locks taken in the wrong order cause a deadlock.
Guided Experiment: Why does the counter come out wrong without a lock, and how does lock ordering prevent deadlock?
Two threads each increment a shared counter three times, so a correct program reaches six. Predict whether the no lock version always reaches six. Then predict what happens when two threads grab two locks in opposite orders, and what changes when they grab them in the same order.
Write your hypothesis in the Lab Report panel, then click Next.
Ready to run
Pick a scenario and press Run, or use Step to walk through the scheduler one decision at a time.
Controls
Run plays the precomputed interleaving step by step. Step advances one scheduler decision at a time. The interleaving is deterministic, so the same scenario and number reproduce the same trace. Try another interleaving to see a different schedule.
Shared state
This scenario uses no locks. Nothing protects the read, add, write sequence, so the threads can clobber each other.
Threads
- 1READ
- 2ADD(1)
- 3WRITE
- 4READ
- 5ADD(1)
- 6WRITE
- 7READ
- 8ADD(1)
- 9WRITE
- 1READ
- 2ADD(1)
- 3WRITE
- 4READ
- 5ADD(1)
- 6WRITE
- 7READ
- 8ADD(1)
- 9WRITE
Wait-for graph
An arrow goes from a blocked thread to the thread holding the lock it wants. A cycle of arrows means a circular wait, which is a deadlock.
No thread is waiting on a lock held by another thread right now.
Data Table
(0 rows)| # | Scenario | Outcome | Final counter | Expected | Deadlock |
|---|
Reference Guide
Threads and Interleaving
A thread is an independent stream of execution inside a program. When several threads run at once, the operating system scheduler decides whose turn it is, and it can switch between threads at almost any point. The order in which their steps are mixed together is called an interleaving.
Because the scheduler is free to choose many different orders, a threaded program can behave differently from one run to the next. A program is only correct if it gives the right answer for every possible interleaving, not just the lucky ones.
Race Conditions and Lost Updates
Incrementing a shared counter looks like one action but is really three. Read the current value into a local register, add one, then write the register back. This read, add, write sequence is not atomic, so the scheduler can interrupt it partway through.
A race condition is a bug where the result depends on timing. If two threads both read the same old value before either writes, they each write the same new value and one increment vanishes. That is a lost update, which is why the no lock scenario finishes below the expected total.
Critical Sections and Mutual Exclusion
A critical section is a piece of code that touches shared data and must not be run by two threads at the same time. A lock, also called a mutex, guards a critical section. A thread acquires the lock before entering and releases it on the way out.
Only one thread can hold a given lock at a time, which is mutual exclusion. When the increment is wrapped in a lock, one thread completes its whole read, add, write before any other thread can start, so no update is lost and the counter reaches the correct total for every interleaving.
Deadlock and the Wait-For Graph
Locks solve the race but add a new danger. A deadlock is a state where threads are stuck forever, each waiting for a resource that another stuck thread holds. The classic cause is acquiring two locks in opposite orders. Thread A takes lock one then waits for lock two, while Thread B takes lock two then waits for lock one.
A deadlock needs all four Coffman conditions at once. Mutual exclusion, hold and wait, no preemption, and circular wait. The wait-for graph draws an arrow from each blocked thread to the thread holding the lock it wants. A cycle in that graph is the signature of a deadlock. Acquiring every lock in one global order breaks the circular wait and prevents the deadlock, which is what the ordered scenario shows.
