Skip to main content

Source: Operating Systems: Three Easy Pieces (OSTEP) — Chapter 26, Arpaci-Dusseau & Arpaci-Dusseau

Concurrency: An Introduction

CPU virtualization gave us multiple virtual CPUs; memory virtualization gave each process a private address space. Now: threads — multiple points of execution inside one process.

A thread is like a process with one big difference: threads share an address space (and can touch the same data). Each thread still has its own PC, registers, and (usually) stack. Switching threads uses a TCB (thread control block); unlike a process switch, you typically do not switch page tables.

Address space with threads​

Single-threaded: one stack. Multi-threaded: one stack per thread (thread-local storage for locals, args, return addresses). Stacks carve into the shared VA layout — less “beautiful,” but usually fine if stacks stay modest.

Why threads?​

  1. Parallelism — split work across CPUs (e.g. array ops).
  2. Overlap I/O — one thread blocks on disk/network/page fault; others keep running (like multiprogramming, but inside one program).

Processes work too, but sharing in-memory data structures is much easier with threads. Prefer processes when tasks are logically separate and share little.

Thread creation (pthread sketch)​

pthread_create starts a routine on a new thread; pthread_join waits for it. After create, the new thread may run immediately, later, or (on a multiprocessor) alongside others — the scheduler decides. Creation order does not imply run order: “B” can print before “A”.

Think of create as a function call that does not wait for the callee: a new execution context runs independently.

Shared data: the plot thickens​

Two threads each do counter = counter + 1 ten million times. Expected: 20,000,000. Reality: often less, and different every run — indeterminate.

Uncontrolled scheduling​

counter++ is typically three instructions:

mov  counter, %eax
add  $1, %eax
mov  %eax, counter

If T1 loads and adds, then a timer interrupt saves eax=51 mid-update, T2 runs a full increment (50→51), then T1 stores 51 again — two increments, one visible update. That is a race condition (data race) on a critical section.

Quiz

Rank the sequence

1 / 1

Order the interleaved steps (counter starts at 50) that cause a lost update on counter++.

OrderDrag the handle to rearrange — top should be first.

  1. 1T1 loads counter (50) and adds 1, giving eax=51 in its register
  2. 2T1 stores 51 back into counter, overwriting T2's update
  3. 3T2 runs a full increment: loads 50, adds 1, stores 51
  4. 4A timer interrupt fires, saving T1's register state (eax=51) and switching to T2

Drag items into the correct order (or use ↑↓), then check.

We need mutual exclusion: only one thread in the critical section at a time (Dijkstra [D65,D68]).

The wish for atomicity​

A single memory-add that the hardware runs all-or-nothing would fix this case. In general we cannot invent an instruction per data structure. Instead: a few atomic hardware primitives + OS help → synchronization primitives (locks, etc.) that make short sequences appear atomic.

Use atomic operations

“All or nothing” shows up everywhere: concurrency, file systems, databases, distributed systems.

Another interaction: one thread must wait for another (I/O done, work produced) — later: condition variables / sleep–wake.

Why in OS class?​

The OS was the first concurrent program. Interrupts mid-write() updating bitmaps and inodes are the same class of bug. Kernel structures need synchronization from day one; user threads inherited the problem.

Key terms
  • Critical section — code that touches shared state
  • Race condition — concurrent critical-section entry → surprising result
  • Indeterminate — output varies by timing
  • Mutual exclusion — at most one thread in the CS

Crux ahead: what hardware and OS support do we need to build sync primitives correctly and efficiently?

Interactive​

Try: address spaces · create/join orderings · lost update on counter++.

Check your understanding​

Quiz

Concurrency introduction

1 / 6

Compared to a process context switch, a thread switch typically…

Pick an answer to see if you are right.

Coding challenges​

Homework lab: x86.py​

Use the OSTEP concurrency homework (x86.py and the .s traces).

Lab

Homework: x86.py thread interleavings

0/5 started

Loading lab…

Summary​

IdeaTakeaway
ThreadPC + regs + stack; shared AS with siblings
WhyParallelism + I/O overlap
RaceInterleaved critical sections → wrong / indeterminate results
NeedMutual exclusion / atomicity via sync primitives

Previous: Complete Virtual Memory Systems (end of VM arc)

Next: Locks — mutexes, test-and-set, tickets, and sleeping locks.

Further Reading​