Synchronization

Wikipedia · Synchronization · CC BY-SA 4.0

Synchronization primitives enforce order on concurrent access to shared resources. Mutexes give exclusive access. Semaphores generalize to counting. Monitors bundle the lock with the data. The classic problems (producer-consumer, dining philosophers) test whether your primitive is strong enough.

Mutexes

A mutex (mutual exclusion lock) has two operations: lock and unlock. Only one thread can hold the lock. Others block until it is released. Simple, effective, and the foundation of most synchronization.

Semaphores

A semaphore is an integer with two atomic operations: wait (decrement, block if zero) and signal (increment). A binary semaphore acts like a mutex. A counting semaphore controls access to a pool of resources.

Scheme

; Semaphore simulation
; wait: if count > 0, decrement; else block (we simulate by returning 'blocked)
; signal: increment

(define (make-semaphore initial)
  (list initial))

(define (sem-value s) (car s))

(define (sem-wait! s)
  (if (> (car s) 0)
      (begin (set-car! s (- (car s) 1)) 'acquired)
      'blocked))

(define (sem-signal! s)
  (set-car! s (+ (car s) 1))
  'signaled)

; Binary semaphore (mutex)
(define mutex (make-semaphore 1))
(display "Initial: ") (display (sem-value mutex)) (newline)
(display "Wait: ") (display (sem-wait! mutex)) (newline)
(display "Value: ") (display (sem-value mutex)) (newline)
(display "Wait again: ") (display (sem-wait! mutex)) (newline)
(display "Signal: ") (display (sem-signal! mutex)) (newline)
(display "Value: ") (display (sem-value mutex))

Producer-Consumer

One thread produces items into a bounded buffer. Another consumes them. Two semaphores coordinate: one counts empty slots, one counts full slots. A mutex protects the buffer itself.

Scheme

; Producer-consumer with a bounded buffer
; Simulated step-by-step (no real threads)

(define buffer '())
(define buffer-size 3)

(define (produce item buf)
  (if (>= (length buf) buffer-size)
      (begin (display "Buffer full, cannot produce ") (display item) (newline) buf)
      (let ((new-buf (append buf (list item))))
        (display "Produced: ") (display item)
        (display "  Buffer: ") (display new-buf) (newline)
        new-buf)))

(define (consume buf)
  (if (null? buf)
      (begin (display "Buffer empty, cannot consume") (newline) buf)
      (let ((item (car buf)) (rest (cdr buf)))
        (display "Consumed: ") (display item)
        (display "  Buffer: ") (display rest) (newline)
        rest)))

(define b '())
(set! b (produce 'A b))
(set! b (produce 'B b))
(set! b (produce 'C b))
(set! b (produce 'D b))  ; full!
(set! b (consume b))
(set! b (consume b))
(set! b (produce 'D b))
(set! b (consume b))

Dining Philosophers

Five philosophers sit around a table, each needing two forks to eat. If every philosopher picks up their left fork simultaneously, nobody can pick up their right fork. Deadlock. Solutions: limit diners, impose ordering, or use a waiter.

Monitors

A monitor bundles the shared data, the operations on it, and the synchronization into one construct. Only one thread can be active inside the monitor at a time. Condition variables let threads wait inside the monitor for specific events.

Neighbors

🔢 Discrete Math Ch.4 — graph theory: the happens-before relation for synchronization primitives is a directed acyclic graph
🔗 Abstract Algebra Ch.1 — groups and atomicity: mutex operations are the OS implementation of atomic group actions on shared state
✎ Proofs Ch.7 — equivalence relations: linearizability defines an equivalence between concurrent and sequential executions

Foundations (Wikipedia)

← Threads and Concurrency by june.kim Deadlock →