Shared mutable state + concurrency = bugs. Serializers ensure critical sections run atomically. But composing serializers can deadlock. There is no free lunch.
The nature of time in concurrent systems
Without concurrency, events happen in a definite order. With concurrency, operations on shared state can interleave. The result depends on timing, not just logic.
Scheme
; The classic problem: two processes both read-modify-write; Imagine balance = 100, and two withdrawals of 10 happen "at once"; Correct sequential execution:
(define balance 100)
; Withdrawal 1
(set! balance (- balance 10)) ; balance = 90; Withdrawal 2
(set! balance (- balance 10)) ; balance = 80
(display "sequential: ") (display balance) (newline)
; But with interleaving, both could read 100,; then both write 90 โ losing one withdrawal!; This is a race condition.
(display "possible concurrent result: 90 (lost update!)")
Python
# Race condition demonstrated sequentially# (real concurrency needs threads)
balance = 100# Correct sequential:
balance -= 10# 90
balance -= 10# 80print(f"sequential: {balance}")
# With interleaving (simulated):# Thread A reads 100, Thread B reads 100# Thread A writes 90, Thread B writes 90# Result: 90 instead of 80print("possible concurrent result: 90 (lost update!)")
Mechanisms for controlling concurrency
A serializer takes a procedure and returns a version that cannot interleave with other serialized procedures from the same serializer. The serializer is a higher-order function that wraps procedures with mutual exclusion.
Scheme
; Simulating a serializer concept; In real SICP, parallel-execute provides concurrency; Here we show the serializer's contract
(define (make-serializer)
(let ((locked #f))
(lambda (proc)
(lambda args
; In real implementation, this would block if locked
(set! locked #t)
(let ((result (apply proc args)))
(set! locked #f)
result)))))
(define (make-account balance)
(let ((s (make-serializer)))
(define (withdraw amount)
(if (>= balance amount)
(begin (set! balance (- balance amount))
balance)
"Insufficient funds"))
(define (deposit amount)
(set! balance (+ balance amount))
balance)
(define (dispatch m)
(cond ((eq? m 'withdraw) (s withdraw)) ; serialized!
((eq? m 'deposit) (s deposit)) ; serialized!
((eq? m 'balance) balance)
(else (error "Unknown request" m))))
dispatch))
(define acc (make-account 100))
(display ((acc 'withdraw) 25)) (newline) ; 75
(display ((acc 'deposit) 50)) (newline) ; 125
(display (acc 'balance)) ; 125
A serializer is built from a mutex (mutual exclusion). A mutex has two operations: acquire and release. A process that has acquired the mutex blocks all others until it releases.
Scheme
; Mutex: the fundamental synchronization primitive
(define (make-mutex)
(let ((cell (list #f)))
(define (the-mutex m)
(cond ((eq? m 'acquire)
(if (test-and-set! cell)
(the-mutex 'acquire))) ; busy-wait (spin)
((eq? m 'release)
(set-car! cell #f))))
the-mutex))
; test-and-set! must be atomic (hardware support)
(define (test-and-set! cell)
(if (car cell)
#t; already locked
(begin (set-car! cell #t) ; grab the lock#f))) ; success
(define m (make-mutex))
(m 'acquire)
(display "mutex acquired โ critical section") (newline)
(m 'release)
(display "mutex released")
Python
import threading
mutex = threading.Lock()
mutex.acquire()
print("mutex acquired โ critical section")
mutex.release()
print("mutex released")
# Python's Lock is implemented with OS primitives# SICP's test-and-set! maps to hardware CAS instructions
Deadlock
When two accounts need to transfer money, each must lock both accounts. If account A locks itself and waits for B, while B locks itself and waits for A, neither can proceed. This is deadlock. The classic fix: always acquire locks in a fixed global order.
Scheme
; Deadlock scenario (conceptual โ no real threads here);; Transfer needs to lock BOTH accounts:;; (define (transfer from to amount); (serialize-from; (serialize-to; (lambda (); (withdraw from amount); (deposit to amount)))));; If two transfers happen simultaneously:; Transfer A->B: locks A, waits for B; Transfer B->A: locks B, waits for A; DEADLOCK!;; Fix: order locks by account number
(define (make-numbered-account id balance)
(let ((s (make-serializer)))
(define (dispatch m)
(cond ((eq? m 'id) id)
((eq? m 'withdraw)
(lambda (amt) (set! balance (- balance amt)) balance))
((eq? m 'deposit)
(lambda (amt) (set! balance (+ balance amt)) balance))
((eq? m 'balance) balance)
((eq? m 'serializer) s)
(else (error "Unknown" m))))
dispatch))
(define (make-serializer)
(lambda (proc) proc)) ; stub for demonstration
(define a1 (make-numbered-account 1100))
(define a2 (make-numbered-account 2200))
; Safe transfer: always lock lower-numbered account first
(display "a1 before: ") (display (a1 'balance)) (newline)
(display "a2 before: ") (display (a2 'balance)) (newline)
((a1 'withdraw) 30)
((a2 'deposit) 30)
(display "a1 after: ") (display (a1 'balance)) (newline)
(display "a2 after: ") (display (a2 'balance))
Python
# Deadlock-free transfer: always lock in consistent orderimport threading
class Account:
_next_id = 0def __init__(self, balance):
self.id = Account._next_id
Account._next_id += 1
self.balance = balance
self.lock = threading.Lock()
def transfer(from_acc, to_acc, amount):
# Always lock lower id first to prevent deadlock
first, second = sorted([from_acc, to_acc], key=lambda a: a.id)
with first.lock:
with second.lock:
from_acc.balance -= amount
to_acc.balance += amount
a1 = Account(100)
a2 = Account(200)
print(f"before: a1={a1.balance}, a2={a2.balance}")
transfer(a1, a2, 30)
print(f"after: a1={a1.balance}, a2={a2.balance}")
Notation reference
SICP concept
Python
Meaning
parallel-execute
threading.Thread
Run procedures concurrently
(make-serializer)
threading.Lock()
Create mutual exclusion guard
(s proc)
with lock:
Serialize a procedure
test-and-set!
CAS / atomic op
Hardware-level atomic test-and-set
deadlock
deadlock
Circular wait on locks
Translation notes
SICP's make-serializer returns a higher-order function. Python's threading.Lock is an object with acquire/release methods, typically used via with statements.
Python's GIL (Global Interpreter Lock) means CPU-bound threads don't truly run in parallel, but I/O-bound threads and race conditions on shared state are still real.
The deadlock-prevention strategy (lock ordering) is universal across languages.
Wikipedia: Race condition