A thread executes test-and-set on a shared lock variable and the instruction returns 1. What should the thread do next?
AEnter the critical section — returning 1 means the lock is now acquired
BRelease the lock by writing 0 — returning 1 means the thread previously held it
CSpin and retry — returning 1 means the lock was already held by another thread
DBlock until the OS wakes it — test-and-set automatically suspends the thread when the lock is taken
Test-and-set atomically reads the current value and sets it to 1, returning the old value. If the old value was 0 (unlocked), the thread changed it from 0→1 and now holds the lock — proceed. If the old value was 1 (already locked), the thread changed it from 1→1 (no net change) and the lock was already held. A return of 1 means 'it was locked when I looked' — the thread must retry. Option A reverses the logic. Option D confuses test-and-set (a busy-waiting primitive) with blocking OS synchronization.
Question 2 Multiple Choice
Why can't Peterson's algorithm reliably guarantee mutual exclusion on modern multicore processors without additional hardware support?
AIt uses too many shared variables for the hardware cache to track efficiently
BModern processors may reorder memory operations, breaking the assumptions Peterson's algorithm relies on
CPeterson's algorithm requires atomic increment operations that are not available on all hardware
DIt only works for two threads, so systems with more threads require a different approach
Peterson's algorithm assumes that writes to shared memory are immediately visible to other processors in the order they were issued — sequential consistency. Modern out-of-order processors and cache coherence protocols can reorder memory operations for performance, so the careful read-write sequence that Peterson's algorithm relies on can arrive at other cores in a different order than intended, breaking the mutual exclusion guarantee. Hardware atomic primitives bypass this problem by making the read-modify-write sequence truly indivisible at the hardware level.
Question 3 True / False
The test-and-set instruction is atomic: no other processor can access the targeted memory location between the read and the write.
TTrue
FFalse
Answer: True
This is precisely what makes test-and-set useful. The processor's cache coherence protocol ensures exclusive access to the memory location for the duration of the operation — no other core can observe an intermediate state. The location transitions from old-value to 1 instantaneously from the perspective of all other processors. This hardware guarantee is what software-only solutions cannot provide on modern out-of-order hardware, and it is the foundation for all higher-level synchronization primitives.
Question 4 True / False
Compare-and-swap (CAS) and test-and-set solve exactly the same problem in exactly the same way; CAS is simply a more recent version of the same idea.
TTrue
FFalse
Answer: False
While both are atomic read-modify-write primitives, CAS is strictly more flexible. CAS takes three arguments (a location, an expected old value, and a new value) and only performs the write if the current value matches the expected value — reporting whether the swap succeeded. This conditionality enables lock-free data structures that test-and-set cannot implement. With CAS, a thread can optimistically read a value, compute an update, and atomically commit it only if no other thread changed the value in the meantime — without holding any lock.
Question 5 Short Answer
Why is hardware-provided atomicity necessary for synchronization on modern systems? Why isn't a careful sequence of software operations sufficient?
Think about your answer, then reveal below.
Model answer: Modern processors execute instructions out of order and use private caches that may not immediately propagate writes to other cores. A software sequence like 'read a variable, check its value, write a new value' is not atomic — another thread can interleave between the read and the write, creating a race condition. Hardware atomic instructions use the processor's cache coherence protocol to ensure no other core can access the target location while the operation is in progress, making the entire read-modify-write appear instantaneous to the rest of the system. This guarantee cannot be replicated purely in software on modern architectures.
The root cause is that software mutual exclusion assumes sequential consistency — that all processors see memory operations in the same order they were issued. Modern CPUs trade this for performance by reordering operations and using private caches. Hardware primitives restore a strong guarantee for specific operations: the cache coherence protocol forces all cores to serialize access to the target address for the duration of the atomic instruction. This is exactly what Peterson's algorithm assumes but cannot enforce, and what test-and-set and CAS provide directly.