A serializer makes one state transition finish before the next begins.
A lock cell and a test-and-set boundary can reject overlapping entry, while a serializer wraps state-changing procedures so one selected finite schedule preserves both updates.
What must be protected so that an update cannot read state and then finish after another update has changed it?
- Read test-and-set! as returning the previous lock state
- Separate acquisition failure from release and later retry
- Wrap a state-changing procedure with one shared lock
- Compare a stale-read lost update with a serialized finite schedule
The lock is a one-cell mutable list. test-and-set! reports whether the cell was already true; otherwise it changes the cell to true and reports the previous false state. The first acquisition therefore succeeds, an overlapping attempt fails, and a retry after clear! succeeds. SICP treats test-and-set! as an atomic implementation boundary. This browser program models that boundary as one named operation; it does not create threads or establish machine-level atomicity.
make-serializer accepts a shared lock and returns a procedure wrapper. The wrapper acquires before calling the state-changing procedure and clears after receiving its result. In the shipped finite schedule, the serialized deposit finishes before the withdrawal reads balance, so both updates remain in the final value 90. The comparison program does not prove fairness, deadlock freedom, exception safety, or the outcome of every possible concurrent schedule.
(begin
(define (test-and-set! cell)
(if (car cell)
#t
(begin
(set-car! cell #t)
#f)))
(define (clear! cell) (set-car! cell #f))
(define lock (list #f))
(define first-acquire (not (test-and-set! lock)))
(define overlapping-acquire (not (test-and-set! lock)))
(clear! lock)
(define retry-acquire (not (test-and-set! lock)))
(list first-acquire
overlapping-acquire
retry-acquire
(car lock)))- Output
- —
- Value
- —
- Diagnostic
- —
The first program returns (#t #f #t #t). The second returns (80 110 90 90 #f).
In the first run, locate the two set-car! transitions separated by clear!, and distinguish the overlapping call that performs no mutation. In the second, compare the two stale reads inside lost-update with the serialized wrapper that acquires, completes one balance assignment, releases, and only then lets the next wrapper read. The bounded trace describes these explicit sequential schedules only.
Change the program before you read the hint.
Set the shared lock to true immediately before serialized-deposit. Predict its result and balance, then clear the lock and call the deposit again.
Show one hint
A busy wrapper does not call its protected procedure. After clear!, the same wrapper can acquire and perform the update.