3.4.2 · Serialization and exclusion

A serializer makes one state transition finish before the next begins.

A lock cell and a test-and-set boundary reject overlapping entry, while a serializer wraps state-changing procedures so both updates survive one schedule.

Guiding question

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. This browser program models SICP’s atomic implementation boundary as one named operation in a finite schedule.

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 lesson records this exact schedule and final state.

SICP code468 of 1,048,576 UTF-8 bytes

(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)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The first program returns (#t #f #t #t). The second returns (80 110 90 90 #f).

Trace focus

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 fixed-limit execution trace describes these explicit sequential schedules only.

Try it yourself

Change the program and compare the result.

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 hint

A busy wrapper does not call its protected procedure. After clear!, the same wrapper can acquire and perform the update.

Complete this lesson

0 of 21 lessons complete in this chapter0%