3.4.3 · Mechanisms for controlling concurrency

A shared lock order can remove one explicit circular wait.

Model test-and-set locks, expose a two-lock deadlock schedule, and acquire account locks by stable id before performing protected transfers.

Guiding question

How can two individually serialized resources still deadlock, and what ordering rule removes that cycle?

Model successful and failed test-and-set acquisition
Recognize circular wait across two separately held locks
Distinguish mutual exclusion from deadlock avoidance
Choose a global lock order from stable account ids
Release every acquired lock after one finite protected operation

The first schedule lets a left operation acquire lock a and a right operation acquire lock b. Each then asks for the other lock and fails. Both resources are mutually excluded, yet neither modeled operation can proceed: the schedule contains a circular wait. The program represents that interleaving as explicit sequential state transitions.

The transfer program orders two account locks by numeric id before acquiring either pair. Callers may request transfers in opposite account directions, but both operations use the same lock order. The sequential demonstration completes both transfers, releases both cells, and records the full state transition of the selected locking protocol.

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

(begin
  (define (make-lock) (list #f))
  (define (try-acquire! lock)
    (if (car lock)
        #f
        (begin
          (set-car! lock #t)
          #t)))
  (define (release! lock) (set-car! lock #f))
  (define lock-a (make-lock))
  (define lock-b (make-lock))
  (define left-first (try-acquire! lock-a))
  (define right-first (try-acquire! lock-b))
  (define left-second (try-acquire! lock-b))
  (define right-second (try-acquire! lock-a))
  (list left-first
        right-first
        left-second
        right-second
        (and left-first
             right-first
             (not left-second)
             (not right-second))
        (car lock-a)
        (car lock-b)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The deadlock model returns (#t #t #f #f #t #t #t). The ordered transfer model returns ((90 50) (45 95) 95 45 #f #f).

Trace focus

In the deadlock schedule, locate the two successful first acquisitions and two failed second acquisitions. In the transfer model, record the requested account direction separately from the id-based acquisition order, then verify the reverse release order and both final false lock cells.

Try it yourself

Change the program and compare the result.

Add a third account and a protected operation that needs all three locks. Sort the account ids before acquisition, then write one deliberately inconsistent schedule and identify the circular wait it reintroduces.

Show hint

Mutual exclusion protects a resource. Deadlock avoidance requires every multi-lock operation to agree on one global ordering rule.

Complete this lesson

0 of 21 lessons complete in this chapter0%