Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 55 ยท Operating Systems

Deadlock and Synchronization in Plain Language

Learn what a race condition is, how a lock (mutex) and a semaphore keep shared data safe, and how to avoid deadlock with a simple ordering rule, using Python.

When one program does one thing at a time, life is simple. Once several threads or processes work at the same time, a new kind of bug appears: the answer depends on who gets there first. Two threads change the same number, two programs write the same file, two clerks sell the last ticket. Nothing crashes. The result is just quietly wrong, and it may be wrong only one time in a thousand, which makes it very hard to debug.

Synchronization is the set of tools that make concurrent tasks cooperate safely. This lesson builds the intuition in plain language: first the problem (a race condition), then the two basic tools (the lock and the semaphore), and finally the danger that comes with locks (deadlock) and the simplest cure. It builds on Processes, Threads and Scheduling, which introduced threads and gave a first look at deadlock.

Safe sharing in four ideas

Race condition The result depends on timing.
Lock (mutex) One thread at a time inside.
Semaphore A counter of free slots.
Deadlock Everyone waits for everyone.

The first three are tools or problems; the fourth is what goes wrong when the tools are misused.

1 / 2

The race condition

Look at what a simple line like balance = balance + 10 really does. The CPU reads the value, adds 10, and writes the result back: three steps. If two threads run this line at the same time, their steps can interleave:

  1. Thread A reads 100.
  2. Thread B reads 100.
  3. Thread A writes 110.
  4. Thread B writes 110.

Two deposits of 10 happened, yet the balance rose by only 10. One update was lost. This is a race condition: the outcome depends on the unlucky timing of the steps. The piece of code that touches shared data is called a critical section. Python in the browser does not run true parallel threads, so the program below makes the interleaving explicit by simulating two threads whose steps are shuffled in different orders.

Python A lost update, step by step

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Of the six legal orderings, four lose an update (balance 110) and only two give the right answer, 120. Real programs have millions of such possible interleavings, so the bug appears only now and then. The cure is to make the critical section mutually exclusive: only one thread may be inside at a time.

The lock (mutex)

A lock, also called a mutex (short for mutual exclusion), works like the key to a single-person bathroom. A thread acquires the lock before entering the critical section and releases it after leaving. If the lock is taken, the next thread must wait. Because the read-add-write steps now happen without anyone else touching the balance, no update can be lost.

In real Python, using a lock looks like this (shown read-only because the browser cannot run parallel threads):

Python
import threading

lock = threading.Lock()

def deposit():
    global balance
    with lock:                      # acquire; released automatically at the end
        balance = balance + 10

The cost of a lock is that threads wait. Hold a lock for as short a time as possible, and never hold it while doing something slow such as waiting for the network, because everyone else will wait too.

The semaphore

A lock allows one thread inside. Sometimes you want several, but not unlimited: a parking lot with 3 spaces, a database that allows 5 connections, a printer pool of 2 printers. A semaphore is a counter of free slots. A thread acquires by decreasing the counter, waiting if it is zero, and releases by increasing it. A lock is simply a semaphore starting at 1.

The simulation below sends five cars to a parking lot with 2 spaces. A car that finds no space waits in a queue and enters when another leaves.

Python A semaphore as a parking lot

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the counter never goes below zero and never above 2, no matter the order of arrivals. That guarantee is what makes semaphores useful for limiting access to a pool of resources. A common companion idea is the producer-consumer problem: one task makes items and another uses them, with a bounded buffer between them. Two semaphores, one counting free slots and one counting filled slots, make each side wait politely when the buffer is full or empty.

Deadlock returns

Locks fix races but introduce a new danger. Suppose a program needs two locks, one for the printer and one for the scanner. Thread 1 takes the printer then asks for the scanner. Thread 2 takes the scanner then asks for the printer. Both end up holding one lock and waiting for the other, forever. This is deadlock, described in the previous lesson as four conditions that must hold together: mutual exclusion, hold and wait, no preemption, and circular wait.

The cheapest cure attacks the last condition. If every thread always takes locks in the same fixed order, a circle of waiting cannot form: whoever holds the earlier lock can always go on to ask for the later one. The simulation searches every reachable state of two threads that each need two locks, and reports whether both can get stuck.

Python Lock ordering removes deadlock

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first rule set can reach a state where neither thread can move; the second, with both threads taking the printer first, cannot. This is why many programs follow a documented lock order, and why a rule such as "never call unknown code while holding a lock" is common advice.

Other cures exist. A thread can try a lock with a timeout and give up everything it holds if it cannot get the second lock. Operating systems can also detect a cycle (as in the previous lesson) and end one of the processes. Prevention by ordering is usually the simplest.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is a race condition?

    When threads interleave their steps on shared data, the outcome can change from run to run.
  2. 2. What does a mutex guarantee?

    Mutual exclusion keeps the critical section to a single thread at a time.
  3. 3. A semaphore starts at 3. Four threads each try to acquire it. What happens?

    Each acquire lowers the counter; at zero, the next thread must wait for a release.
  4. 4. Which rule prevents the printer/scanner deadlock?

    A fixed order means a circular chain of waiting cannot form.
  5. 5. Why should you hold a lock for as short a time as possible?

    Waiting threads make no progress while the lock is held, so long holds slow everyone down.

Summary

  • A race condition happens when concurrent steps on shared data interleave badly, for example a lost update.
  • A lock (mutex) allows one thread at a time into a critical section; hold it briefly.
  • A semaphore is a counter that allows up to N tasks at once; a lock is a semaphore of 1.
  • Using several locks risks deadlock; taking them in one fixed order is the simplest prevention.

Continue with Memory Management.