Hardware help: test-and-set, compare-and-swap, spinlocks

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Peterson's solution sets which variable first? from Lesson 3.1.2
2. Which requirement does strict alternation break? from Lesson 3.1.2
3. Can user programs disable interrupts? from Lesson 0.1.2

1 · The Hook

The lock-variable attempt failed only because "check" and "set" were two separate steps. What if the hardware could do both in one indivisible step? Every modern CPU has such instructions (test-and-set, compare-and-swap), and every real lock is built on them. GATE asks what these locks guarantee and where they fail.

3 · Core Concept

Predict First — the answer

No. With interrupts off there is no timer interrupt and so no pre-emption. (On several CPUs this does not work: other CPUs keep running.)

In plain words

An atomic instruction finishes completely before anything else can touch the same memory. Test-and-set reads the old value of a lock and sets it to "taken" in one go. If the old value was "free", you got the lock; otherwise try again. A lock where the waiter keeps trying in a loop is a spinlock.

1. Disabling interrupts

Works on a single CPU for short kernel code. Not usable by user programs (privileged), and useless on multiprocessors (other CPUs still run).

2. Test-and-set (TSL)

bool TestAndSet(bool *target) {   // executed atomically by the hardware
    bool old = *target;
    *target = true;
    return old;
}

while (TestAndSet(&lock)) ;   // spin until the old value was false
/* critical section */
lock = false;

• Mutual exclusion ✓ (only one caller can see false).
• Progress ✓.
• Bounded waiting ✗: an unlucky process can lose the race every single time. (A version with a waiting[] array that hands the lock to the next waiter in circular order fixes this.)

3. Swap and compare-and-swap (CAS)

• Swap(a, b) exchanges two variables atomically: key = true; while (key) Swap(&lock, &key);
• CAS(&v, expected, new): if v == expected, set v = new; always return the old value. Lock: while (CAS(&lock, 0, 1) != 0) ; and unlock with lock = 0.

4. Spinlocks: when are they good?

• Waiting costs CPU time (busy waiting) but needs no context switch.
• Good: multiprocessors and very short critical sections.
• Bad: one CPU (the lock holder can't run while you spin), or long critical sections.

5. Priority inversion

With strict priority scheduling: a low-priority process L holds a spinlock; a high-priority process H arrives and spins on it. H always gets the CPU, so L never runs to release the lock, and H spins for ever. Fix: priority inheritance (L temporarily gets H's priority until it releases the lock).

4 · Visual

Three processes racing for a TSL lock (lock = false at first)

P1: TSL -> returns false, lock = true  -> ENTERS
P2: TSL -> returns true                -> spins
P3: TSL -> returns true                -> spins
P1: lock = false
P3: TSL -> returns false, lock = true  -> ENTERS   (P2 may lose again and again)

5 · Worked Examples

Example 1 Easy

x = 5. A thread runs CAS(&x, 5, 9). What is returned, and what is x afterwards?

Solution

Returns the old value 5; since it matched, x becomes 9.

Example 2 Medium

x = 7. A thread runs CAS(&x, 5, 9). Returned value and new x?

Solution

Returns 7; 7 ≠ 5, so x stays 7.

Example 3 GATE

Why is a TSL spinlock a poor choice on a single-CPU system for a long critical section?

Solution

While the waiting process spins, the lock holder is not running (one CPU), so the spinning only wastes the waiter's time slice until the holder is scheduled again and finishes.

6 · GATE Traps

• A TSL lock gives mutual exclusion and progress, but not bounded waiting.
• CAS returns the old value, whether or not it changed anything.
• Disabling interrupts: one CPU only, kernel mode only.
• Priority inversion: high priority spins, low priority holds the lock and never runs.

7 · Memory Hook

"Check and set in one hardware step: that is all a lock needs."

8 · Connect the Dots

Chapter 3.1 is complete: we can build locks, but they all spin. Chapter 3.2 introduces the semaphore, a tool that lets a waiting process sleep instead of spinning, and can also count resources and order events.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — TSL

A lock built as while (TestAndSet(&lock)) ; guarantees:

1. (A) none of the requirements
2. (B) mutual exclusion only
3. (C) mutual exclusion and progress, but not bounded waiting
4. (D) all three requirements

Q2 · NAT · 1 mark(s) — CAS

x = 12. A thread executes CAS(&x, 12, 20). What value does the call return?

Numerical answer: ________

Q3 · NAT · 1 mark(s) — CAS

x = 4. A thread executes CAS(&x, 3, 8). What is x afterwards?

Numerical answer: ________

Q4 · MCQ · 1 mark(s) — Interrupts

Disabling interrupts to protect a critical section does not work on:

1. (A) a single-CPU system in kernel mode
2. (B) a multiprocessor system
3. (C) the OS kernel
4. (D) very short critical sections

Q5 · MCQ · 2 mark(s) — Priority inversion

Strict priority scheduling, one CPU. Low-priority L holds a spinlock; high-priority H starts spinning on the same lock. What happens?

1. (A) L finishes quickly because H waits
2. (B) H and L share the CPU equally
3. (C) The lock is released automatically
4. (D) H spins for ever because L never gets the CPU

10 · Rule Card

• Atomic instruction: finishes before anything else touches that memory.
• TSL: return old, set true; lock = spin until old is false. ME ✓, progress ✓, bounded waiting ✗.
• CAS(&v, e, n): if v == e then v = n; returns the old value. Swap exchanges atomically.
• Spinlocks: good on multiprocessors for short sections; no context switch.
• Disabling interrupts: one CPU, kernel only. Priority inversion → priority inheritance.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

atomic instructiondisabling interruptstest-and-setswapcompare-and-swapspinlockwhen to spinbounded-waiting TSLpriority inversionpriority inheritance