Atomic Test-and-Set: The Foundation of Hardware Synchronization - Test-and-Set Lock (TSL): Hardware-Assisted Synchronization | OneNoughtOne

0/236

Operating SystemsTest-and-Set Lock (TSL)

Test-and-Set Lock (TSL): Hardware-Assisted Synchronization

LevelIntermediate

Duration75 mins

TopicTest-and-Set Lock (TSL)

1 / 5

Atomic Test-and-Set: The Foundation of Hardware Synchronization

The Fundamental Challenge of Atomicity

Consider a deceptively simple problem: two processors attempt to acquire a lock simultaneously. Each reads the lock variable, sees it's unlocked, and writes a 'locked' value. Both believe they hold the lock. Chaos ensues—data corruption, lost updates, system crashes. This scenario isn't hypothetical; it's the fundamental challenge that plagued early multiprocessor systems and continues to threaten any concurrent program lacking proper synchronization.

The problem is atomicity, or rather, the lack of it. The 'read-then-write' sequence that seems like a single logical operation is actually multiple distinct hardware operations, and another processor can interleave its own operations between them. Software alone cannot solve this—we need hardware to guarantee that certain operations execute as indivisible units.

Enter the Test-and-Set (TAS) instruction: the first and most fundamental hardware primitive designed to solve this problem. Understanding Test-and-Set is not merely academic—it forms the conceptual foundation for nearly all modern synchronization primitives, from spinlocks to semaphores to database locks.

What You Will Learn

By the end of this page, you will understand: (1) Why atomic operations are necessary for correct synchronization, (2) The precise semantics of the Test-and-Set instruction, (3) How hardware guarantees atomicity across multiple CPUs, (4) The memory model implications of atomic operations, and (5) Why Test-and-Set became the template for all subsequent atomic primitives.

The Atomicity Problem

To appreciate why Test-and-Set exists, we must first deeply understand the problem it solves. Let's examine what happens when we try to implement a simple lock using ordinary memory operations.

The Naive Lock Attempt:

Imagine implementing a lock with a single shared variable lock that is 0 when unlocked and 1 when locked. The intuitive approach:

naive_lock.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// Shared variable
int lock = 0;
 
// Acquire: spin until we get the lock
void acquire() {
    while (lock == 1) {
        // spin - wait for lock to become 0
    }
    lock = 1;  // claim the lock
}
 
// Release: mark lock as available
void release() {
    lock = 0;
}

This looks correct at first glance. A thread waits until the lock is free (0), then sets it to locked (1). But this is fundamentally broken on any multiprocessor system, and the bug is subtle enough that it might work 99.99% of the time in testing while failing catastrophically in production.

The Race Window

Between reading lock==0 (the test) and writing lock=1 (the set), there exists a window—measured in nanoseconds—where another processor can also read lock==0. Both processors then set lock=1, both believe they hold the lock exclusively, and mutual exclusion fails. This is not a theoretical concern; on modern multi-core systems with billions of operations per second, these races occur constantly under load.

Why Software Cannot Solve This:

You might think we can fix this with more careful coding—perhaps checking the lock again after setting it? But any sequence of ordinary loads and stores has the same fundamental weakness: another processor can interleave at any point.

Consider the timeline of our broken lock with two processors:

Race Condition Timeline
Time	CPU 0	CPU 1	lock Value
T1	Read lock → sees 0	(waiting)	0
T2	(preparing to write)	Read lock → sees 0	0
T3	Write lock ← 1	(preparing to write)	1
T4	Enters critical section	Write lock ← 1	1
T5	Working on shared data	Enters critical section	1
T6	→ DATA CORRUPTION ←	→ DATA CORRUPTION ←	1

Both CPUs pass the while (lock == 1) test because both read the lock value before either writes to it. Software-only solutions (like Peterson's algorithm) can work for two threads on systems with sequential consistency, but they fail on modern relaxed-memory architectures and don't scale to multiple processors.

The Fundamental Requirement:

What we need is a single, indivisible operation that:

Reads the current value of a memory location
Writes a new value to that location
Returns the old value
Prevents any other processor from accessing that location between steps 1 and 3

This is precisely what Test-and-Set provides.

Defining Test-and-Set: Precise Semantics

The Test-and-Set (TAS) instruction is defined by its precise, atomic semantics. Understanding these semantics exactly is critical—any implementation that doesn't preserve them breaks the correctness guarantees.

Formal Definition:

Test-and-Set is an atomic operation that:

Reads the current value at a memory address
Writes a designated value (typically 1 or TRUE) to that address
Returns the value that was read (the old value)
All of the above happen atomically, meaning no other processor can observe an intermediate state

test_and_set_semantics.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * Test-and-Set: Semantic Definition (Pseudocode)
 * 
 * This entire function executes ATOMICALLY with respect to
 * all other memory operations in the system.
 */
bool TestAndSet(bool *target) {
    // ATOMICALLY:
    bool old_value = *target;    // 1. Read current value
    *target = true;               // 2. Set to true (locked)
    return old_value;             // 3. Return what we read
}
 
// Equivalent formulation returning int
int TestAndSetInt(int *target) {
    // ATOMICALLY:
    int old_value = *target;
    *target = 1;
    return old_value;
}

The Pseudocode Trap

This pseudocode cannot be implemented using normal C operations—it merely specifies the behavior. The atomicity guarantee must come from hardware. Writing this in actual C would NOT be atomic because each C statement compiles to multiple machine instructions that can be interleaved.

Understanding the Return Value:

The return value is crucial and often misunderstood. Test-and-Set returns what the location contained before the operation, not after. This allows the caller to determine whether they successfully acquired the lock:

If TestAndSet(&lock) returns false (0): The lock was previously unlocked, and you just locked it. Success!
If TestAndSet(&lock) returns true (1): The lock was already locked by someone else. Your write had no effect on the lock's meaning (it was already 1, you wrote 1). Failed to acquire.

tas_lock_acquisition.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Using Test-and-Set to acquire a lock
bool lock = false;  // false = unlocked
 
void acquire() {
    // Keep trying until we successfully got the lock
    while (TestAndSet(&lock) == true) {
        // TestAndSet returned true: lock was already held
        // Our write of 'true' had no effect (it was already true)
        // Keep spinning
    }
    // TestAndSet returned false: lock was previously unlocked
    // We atomically set it to true, so we now hold the lock
}
 
void release() {
    lock = false;  // Simple store is sufficient for release
}

Why the Atomic Guarantee Matters:

Let's trace through what happens when two processors try to acquire simultaneously:

Scenario: CPU 0 and CPU 1 both execute TestAndSet(&lock) on an initially unlocked lock

Because TestAndSet is atomic, these two operations are serialized—one completes entirely before the other begins. The hardware ensures this even if both processors issue the instruction at exactly the same clock cycle.

Atomic Test-and-Set: Guaranteed Serialization
Order	CPU Winner	TestAndSet Execution	Returns	Result
1st	CPU 0 (winner)	Reads 0, Writes 1	0 (false)	Acquires lock!
2nd	CPU 1	Reads 1, Writes 1	1 (true)	Fails, keeps spinning

The key insight: although both processors executed their TestAndSet at nearly the same instant, exactly one experiences the state transition from 0 to 1. The hardware serializes these operations, creating a total ordering that both processors agree upon.

Notice that CPU 1's TestAndSet still writes 1 to the lock—but this is idempotent since the lock is already 1. The distinguishing factor is the return value, which tells each CPU whether it was the one that performed the 0→1 transition.

Historical Context: The Birth of Atomic Instructions

The Test-and-Set instruction did not emerge from academic theory—it arose from practical necessity when engineers built the first multiprocessor systems in the late 1950s and early 1960s. Understanding this history illuminates why the instruction takes its particular form.

The Early Multiprocessor Challenge:

When IBM, Burroughs, and other manufacturers began connecting multiple processors to shared memory, they immediately encountered the atomicity problem. Early systems like the IBM 7090 (modified for multiprocessing) and the Burroughs B5000 needed mechanisms for processors to coordinate access to shared resources.

The Original Test-and-Set Implementation:

The earliest implementations appeared in systems like the IBM System/360 Model 65 MP (1966) and CDC 6600 (1964). These systems introduced dedicated hardware instructions that locked the memory bus while performing a read-modify-write sequence.

Why 'Test-and-Set'?

The name reflects the operation's two phases: first 'test' (read) the current value, then 'set' (write) the new value. Some architectures called it TAS (Test And Set), TSL (Test and Set Lock), or XCHG (exchange). The semantics vary slightly between implementations, but the core concept—atomic read-modify-write—remains consistent.

Evolution Across Architectures:

Different processor families implemented atomic primitives with varying syntax but equivalent power:

Test-and-Set Across Processor Architectures
Architecture	Instruction	Semantics
x86/x64	`XCHG reg, mem`	Atomically exchange register with memory. LOCK prefix implicit for memory operands.
x86/x64	`LOCK BTS mem, bit`	Bit Test and Set. Tests a bit, sets it to 1, returns old value.
ARM	`SWP Rd, Rm, [Rn]`	Swap register with memory (deprecated in ARMv8, replaced by exclusive monitors).
SPARC	`LDSTUB [addr], reg`	Load-Store Unsigned Byte. Atomically load byte and store 0xFF.
MIPS	`LL/SC` pairs	Load-Linked/Store-Conditional: different model but achieves same goals.
RISC-V	`AMOSWAP rd, rs, (addr)`	Atomic Memory Operation Swap: exchange register with memory.

The x86 XCHG Instruction:

On x86 processors, the XCHG instruction provides Test-and-Set semantics with a full exchange. When one operand is a memory location, the processor automatically asserts the LOCK signal, gaining exclusive access to the memory bus for the duration of the operation.

x86_test_and_set.s
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
; x86/x64 Assembly: Test-and-Set using XCHG
; Input: 
;   - lock_addr: address of the lock variable (in RDI on x86-64)
;   - Register to exchange (we'll use EAX)
; 
; Operation: atomically swap [lock_addr] with EAX
; Return: old value of lock (in EAX)
 
test_and_set:
    mov eax, 1          ; EAX = 1 (the value we want to set)
    xchg eax, [rdi]     ; ATOMIC: swap EAX with memory at [RDI]
                        ; Now EAX contains old value, [RDI] contains 1
    ret                 ; Return with old value in EAX
 
; Usage for spinlock:
spin_acquire:
    mov eax, 1
    xchg eax, [rdi]     ; Try to acquire
    test eax, eax       ; Was old value 0?
    jnz spin_acquire    ; No? Keep spinning
    ret                 ; Yes? We got the lock!
 
spin_release:
    mov dword [rdi], 0  ; Simple store to release
    ret

Why XCHG Is Intrinsically Atomic on x86:

For memory operands, x86 processors treat XCHG as if it had an implicit LOCK prefix. This wasn't always the case—early processors required explicit LOCK prefixes for atomicity. Modern x86 processors internally handle XCHG mem, reg as a locked operation, simplifying programming at the cost of potential performance overhead if misused.

Modern Compiler Support

You rarely need to write assembly today. Compilers provide built-in atomic operations. GCC offers __atomic_exchange_n() and C11/C++11 provide atomic_exchange() which compile to appropriate hardware instructions for each target architecture.

Memory Model Implications

Atomic Test-and-Set does more than just prevent interleaving—it also impacts the memory model, affecting how other memory operations are ordered relative to the atomic operation. Understanding these implications is essential for writing correct lock implementations.

Memory Ordering Guarantees:

Modern processors aggressively reorder memory operations for performance. A load might execute before a preceding store, or stores might become visible to other processors in a different order than they were issued. This relaxed memory model improves performance but creates correctness challenges for synchronization.

Atomic operations typically provide ordering guarantees that prevent harmful reorderings:

Memory Ordering Semantics

•Acquire semantics: No loads or stores following the atomic operation can be reordered before it. The atomic operation 'acquires' permission to access the protected data—all subsequent accesses must actually come after.
•Release semantics: No loads or stores preceding the atomic operation can be reordered after it. The atomic operation 'releases' the protected data—all prior modifications must be visible before the release.
•Full barrier (sequentially consistent): Both acquire and release semantics combined. The atomic operation cannot be reordered with any other memory operations.

Why Ordering Matters for Locks:

Consider what happens without proper ordering. A processor acquires a lock, modifies shared data, then releases the lock. Without ordering guarantees:

ordering_problem.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Shared state
int lock = 0;
int shared_data = 0;
 
// Thread 1: Producer
void producer() {
    // Acquire lock
    while (TestAndSet(&lock)) { }
    
    // Critical section: modify shared data
    shared_data = 42;
    
    // Release lock
    lock = 0;
}
 
// Thread 2: Consumer
void consumer() {
    // Acquire lock
    while (TestAndSet(&lock)) { }
    
    // Critical section: read shared data
    int local = shared_data;
    
    // Release lock
    lock = 0;
    
    printf("Read: %d
", local);  // Should print 42!
}
 
// BUG: Without memory ordering, the processor might:
// 1. Reorder 'shared_data = 42' to execute AFTER 'lock = 0'
// 2. Reorder 'local = shared_data' to execute BEFORE lock acquisition
// 
// Either could cause thread 2 to read stale data (0 instead of 42)!

The Silent Corruption

Memory reordering bugs are among the most insidious in concurrent programming. The code looks correct, tests pass most of the time, but under specific timing conditions on specific hardware, data becomes corrupted. These bugs can remain hidden for years until a different CPU microarchitecture or increased system load exposes them.

Proper Lock Semantics Required:

A correctly implemented lock must ensure:

Lock acquisition has acquire semantics: All reads/writes within the critical section must execute after the lock is successfully acquired.
Lock release has release semantics: All reads/writes within the critical section must complete before the lock is released.

On x86, the XCHG instruction used for Test-and-Set provides a full memory barrier, satisfying both requirements. On architectures with weaker memory models (ARM, POWER, RISC-V), explicit memory barrier instructions may be needed.

proper_lock_semantics.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// C11 atomic approach with explicit memory ordering
#include <stdatomic.h>
 
atomic_int lock = 0;
int shared_data = 0;
 
void acquire() {
    int expected;
    // atomic_exchange with memory_order_acquire
    // Ensures no operations can be reordered before this
    while (atomic_exchange_explicit(&lock, 1, memory_order_acquire) == 1) {
        // Spin
    }
}
 
void release() {
    // atomic_store with memory_order_release
    // Ensures all prior operations complete before this
    atomic_store_explicit(&lock, 0, memory_order_release);
}
 
// Now the ordering is guaranteed:
// 1. shared_data = 42 cannot move before acquire() completes
// 2. lock = 0 cannot happen before shared_data = 42 is visible

Hardware vs. Software Memory Barriers:

The memory ordering guarantees can come from either:

The atomic instruction itself (like x86 XCHG providing a full barrier)
Explicit memory barrier instructions (like ARM DMB, POWER sync)
Compiler barriers (preventing only compiler reordering, not hardware)

For portable code, using C11/C++11 atomics with explicit memory orderings is recommended—the compiler will generate appropriate barriers for each target architecture.

Correctness Properties of Test-and-Set

Now that we understand what Test-and-Set does and how it works, let's rigorously analyze whether a Test-and-Set based lock satisfies the fundamental requirements for correct mutual exclusion. Recall from our study of synchronization fundamentals that any valid solution must satisfy three properties:

1. Mutual Exclusion 2. Progress 3. Bounded Waiting

Property Analysis

•Mutual Exclusion: ✓ SATISFIED — At most one thread can observe Test-and-Set returning 0 for any state transition. Once a thread sees 0 and the lock becomes 1, all subsequent Test-and-Set operations will return 1 until explicit release. The atomicity guarantee ensures no gap exists where two threads both see 0.
•Progress: ✓ SATISFIED — If no thread is in the critical section (lock = 0), a thread attempting to acquire will immediately succeed. Test-and-Set on an unlocked lock returns 0 and sets the lock to 1. No external delay or other thread action is required.
•Bounded Waiting: ✗ NOT SATISFIED — A thread might wait forever while other threads repeatedly acquire and release the lock. Test-and-Set provides no fairness guarantee—the same thread can re-acquire the lock immediately after releasing it, starving others indefinitely.

Starvation is Possible

The basic Test-and-Set spinlock can lead to starvation. On a system with processors P1 and P2 competing for a lock, P1 might acquire the lock thousands of times while P2 never succeeds. This isn't theoretical—it happens in practice when cache effects give one processor an advantage.

Proof of Mutual Exclusion:

We can formally prove mutual exclusion using contradiction:

Assume two threads T1 and T2 are simultaneously in their critical sections. For this to happen:

T1 must have executed TestAndSet(&lock) and received 0, then entered the critical section
T2 must have executed TestAndSet(&lock) and received 0, then entered the critical section

Since neither has released the lock (both are in the critical section), the lock value transitions must be:

T1: lock changes from 0 → 1, T1 receives 0
T2: lock changes from 0 → 1, T2 receives 0

But TestAndSet is atomic—only one can observe the 0 → 1 transition. After T1's TestAndSet, lock = 1. T2's TestAndSet reads 1, writes 1 (idempotent), returns 1. T2 does not enter the critical section.

Contradiction. Therefore, mutual exclusion holds. ∎

Why Bounded Waiting Fails:

Consider this execution trace with two threads:

Starvation Scenario
Time	Thread 1	Thread 2	Lock Value
T1	TestAndSet → 0, Enter CS	TestAndSet → 1, Spin	1
T2	In critical section	TestAndSet → 1, Spin	1
T3	Release (lock = 0)	TestAndSet → 1, Spin	0 → 1
T4	TestAndSet → 0, Re-enter CS	TestAndSet → 1, Spin	1
T5	In critical section	TestAndSet → 1, Spin	1
...	Pattern repeats	Still spinning	...

Thread 1 can theoretically hold and re-acquire the lock indefinitely. The problem worsens with cache effects: Thread 1's TestAndSet might complete faster because the lock variable is in its L1 cache, while Thread 2 must fetch from a remote cache or main memory.

Fairness-Providing Alternatives:

To achieve bounded waiting, we need more sophisticated algorithms:

Ticket Locks: Assign sequence numbers, serve in order
MCS Locks: Queue-based locks with explicit ordering
CLH Locks: Similar to MCS with different queue structure

These will be covered in later sections. The basic Test-and-Set spinlock trades fairness for simplicity and is appropriate only when contention is low or lock hold times are very short.

Performance Characteristics

Understanding the performance profile of Test-and-Set is essential for making informed decisions about when to use it. The instruction's behavior under various contention levels reveals important characteristics.

Uncontended Case:

When a single thread acquires an unlocked lock, Test-and-Set is extremely fast—typically just a few CPU cycles for the atomic operation plus memory latency. On modern x86 processors, an uncontended XCHG might take 10-25 cycles, depending on cache state.

Test-and-Set Latency (Approximate)
Scenario	Typical Latency	Bottleneck
Lock in L1 cache, uncontended	10-25 cycles	Atomic operation overhead
Lock in L2 cache, uncontended	25-50 cycles	L2 access latency
Lock in L3 cache, uncontended	50-100 cycles	L3 access latency
Lock in remote NUMA node	100-300 cycles	Memory interconnect latency
Contended lock (spinning)	Thousands+ cycles	Cache coherence traffic

Contended Case: The Problem of Cache Line Bouncing:

When multiple processors compete for a lock using Test-and-Set, performance degrades dramatically due to cache line bouncing. Here's what happens:

Processor A holds the lock; the lock's cache line is in A's L1 cache, state Modified
Processors B, C, D continuously execute TestAndSet, each one:
- Invalidates A's cached copy (and all other copies)
- Fetches the cache line
- Modifies the cache line (writes 1)
- Immediately gets invalidated by the next processor's TestAndSet

The lock variable's cache line bounces between processors at high speed, saturating the memory interconnect with coherence traffic.

Scalability Nightmare

Under high contention, a naive Test-and-Set spinlock can generate O(N²) coherence traffic, where N is the number of competing processors. Adding processors actually SLOWS DOWN total throughput. This anti-scaling behavior has brought production systems to their knees.

test_and_test_and_set.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Improved spinlock: Test-and-Test-and-Set (TTAS)
// Also called "spin on read" or "local spinning"
 
void acquire_ttas(int *lock) {
    while (1) {
        // First: spin locally, just READING the lock
        // This doesn't cause cache invalidation!
        while (*lock == 1) {
            // Local spinning - no bus traffic
            // Other CPUs' caches are unaffected
            __builtin_ia32_pause();  // Hint for spin-wait loops
        }
        
        // Lock appears free - now try to acquire
        if (TestAndSet(lock) == 0) {
            return;  // Success!
        }
        // Failed (someone else got it first), back to spinning
    }
}
 
// Why this is better:
// 1. Spinning threads do READ-ONLY operations
// 2. Reads can be satisfied from local cache
// 3. Only when lock appears free do we attempt atomic write
// 4. Dramatically reduces cache coherence traffic

Test-and-Test-and-Set Analysis:

The TTAS optimization doesn't change correctness—it only reduces wasted coherence traffic. The key insight is separating the testing phase (which can use cached copies) from the acquiring phase (which requires an atomic operation).

TTAS Performance Benefits

•Reduced bus traffic: Spinning threads read from cache instead of issuing atomic operations
•Lower power consumption: Fewer cache invalidations means less memory controller activity
•Better scaling: Performance degrades more gracefully with increased contention
•Thundering herd remains: When lock is released, all waiting threads simultaneously attempt TestAndSet, causing a brief traffic spike

The PAUSE Instruction:

Modern processors (Intel since Pentium 4, AMD since Opteron) provide a PAUSE instruction specifically for spin-wait loops. It:

Inserts a small delay, reducing power consumption
Allows the processor to better allocate resources to other threads (SMT)
Prevents memory ordering violations when exiting the spin loop

Always use PAUSE (or its compiler intrinsic) in spin loops. Omitting it can cause correctness issues on some processor microarchitectures and wastes power.

Production Recommendation

Never use a bare Test-and-Set spinlock in production systems with any possibility of contention. At minimum, use Test-and-Test-and-Set with PAUSE. For any lock that might be contended, prefer ticket locks or queue-based locks that provide both fairness and better performance characteristics.

Summary: The Foundation of Atomic Synchronization

We have completed our deep exploration of the atomic Test-and-Set operation, establishing the foundation for understanding all hardware-assisted synchronization. Let's consolidate the key insights:

Key Takeaways

•The atomicity problem — Ordinary read-modify-write sequences can be interleaved, breaking synchronization. Hardware support is essential for correct solutions.
•Test-and-Set semantics — Atomically reads the old value, writes a new value, and returns the old value. The return value indicates success or failure of acquisition.
•Historical importance — TAS was the first hardware primitive for synchronization, appearing in the 1960s and remaining relevant across all modern architectures.
•Memory ordering — Atomic operations provide ordering guarantees (acquire/release semantics) that prevent harmful reorderings of surrounding operations.
•Correctness properties — Basic TAS spinlocks provide mutual exclusion and progress but NOT bounded waiting. Starvation is possible under contention.
•Performance profile — Excellent uncontended performance but severe scalability issues due to cache line bouncing under contention. TTAS optimization helps but doesn't eliminate the problem.

What's Next:

Having established the conceptual framework for atomic Test-and-Set, we'll next explore the hardware mechanisms that make atomicity possible. How does a processor prevent other processors from accessing a memory location? What happens at the electrical level when you execute an atomic instruction? Understanding the hardware implementation will deepen your intuition and help you reason about performance characteristics in real systems.

Page Complete

You now possess a rigorous understanding of atomic Test-and-Set—its definition, semantics, correctness properties, and performance characteristics. This knowledge forms the foundation for understanding all modern synchronization primitives and will serve you throughout your operating systems journey and professional career.