Threads and Concurrency

Wikipedia · Thread (computing) · CC BY-SA 4.0

A thread is the smallest unit of execution within a process. Threads within the same process share code, data, and open files, but each has its own stack, registers, and program counter. Concurrency is cheap with threads. Safety is not.

Threads vs processes

Creating a new process copies the entire address space (or uses copy-on-write). Creating a thread adds a new execution context within the existing space. Threads are lighter: faster to create, faster to switch, faster to communicate. The cost is shared mutable state.

Race conditions

When two threads read-modify-write the same variable without coordination, the result depends on interleaving. This is a race condition. The outcome is non-deterministic. The fix is synchronization (next chapter).

Scheme

; Simulating a race condition
; Two "threads" both increment a shared counter
; Without synchronization, interleaving can lose updates

(define shared-count 0)

; Thread 1 reads, increments, writes
(define (thread-increment! label)
  (let ((local (+ shared-count 1)))  ; read + compute
    ; In a real race, the other thread could run here
    (set! shared-count local)         ; write
    (display label)
    (display " set count to ")
    (display shared-count)
    (newline)))

; Sequential execution: no race
(set! shared-count 0)
(thread-increment! "T1")
(thread-increment! "T2")
(display "Sequential result: ") (display shared-count) (newline)

; Simulated interleaved execution (race!)
(set! shared-count 0)
(let ((t1-read shared-count)   ; T1 reads 0
      (t2-read shared-count))  ; T2 also reads 0
  (set! shared-count (+ t1-read 1))  ; T1 writes 1
  (set! shared-count (+ t2-read 1))) ; T2 writes 1, not 2!
(display "Interleaved result: ") (display shared-count)
; Lost update: expected 2, got 1

; Simulating a race condition
; Two "threads" both increment a shared counter
; Without synchronization, interleaving can lose updates

(define shared-count 0)

; Thread 1 reads, increments, writes
(define (thread-increment! label)
  (let ((local (+ shared-count 1)))  ; read + compute
    ; In a real race, the other thread could run here
    (set! shared-count local)         ; write
    (display label)
    (display " set count to ")
    (display shared-count)
    (newline)))

; Sequential execution: no race
(set! shared-count 0)
(thread-increment! "T1")
(thread-increment! "T2")
(display "Sequential result: ") (display shared-count) (newline)

; Simulated interleaved execution (race!)
(set! shared-count 0)
(let ((t1-read shared-count)   ; T1 reads 0
      (t2-read shared-count))  ; T2 also reads 0
  (set! shared-count (+ t1-read 1))  ; T1 writes 1
  (set! shared-count (+ t2-read 1))) ; T2 writes 1, not 2!
(display "Interleaved result: ") (display shared-count)
; Lost update: expected 2, got 1

Critical sections

A critical section is the part of code that accesses shared resources. The goal: ensure that at most one thread is in its critical section at any time. Three requirements: mutual exclusion, progress (no unnecessary blocking), and bounded waiting (no starvation).

Neighbors

♟ Game Theory Ch.12 — prisoner's dilemma and race conditions: concurrent threads are like players in a game where uncoordinated choices cause data races
🪄 SICP Ch.18 — streams and delayed evaluation: threads are like lazy streams evaluated interleaved
💻 TOC Ch.1 — finite automata: concurrent thread interleavings are modeled as nondeterministic finite automata

Foundations (Wikipedia)

← Scheduling by june.kim Synchronization →