4.4 Hardware Synchronization: Test-and-Set Lock (TSL) & Swap Instructions

Back to Operating Systems Notes

📚Module 04: Process Synchronization & ConcurrencyTopic 4.4⏱️14 min read

🎯High-Yield For:Computer Science Foundations • Systems Engineering • Technical Interviews

💡 Core Intuition

🍳 The Everyday Analogy: The Single-Action Deadbolt Latch

Imagine a private conference room door fitted with a spring-loaded mechanical deadbolt latch (the Hardware Atomic Instruction):

Architecture Flow

The Mechanical Deadbolt Analogy Pipeline

Mapping atomic hardware latches to CPU synchronization instructions

💡 Hover or click any card for deep-dive operational details

🚪Approach

Grab Handle

Read Old Lock State

A manager grabs the handle to test if the room is locked.

→

Atomic Twist

🔒Atomic Action

Single Mechanical Twist

Test-and-Set in 1 Clock Cycle

Turning the handle tests the latch AND throws the bolt in one movement.

→

Inspection

🔑Admission

Grant or Deny Access

Return Old State

If it was previously unlocked, enter; if locked, wait outside.

• The Software Dilemma: In software, checking a flag (while(lock == 1)) and setting it (lock = 1) are two separate instructions. A timer interrupt between them allows two threads to enter simultaneously.
• The Hardware Solution: Build a silicon-level instruction that reads the old value AND sets the new value in a single indivisible clock cycle on the memory bus.

---

💻 Bridging to Computer Science

Modern computer architectures provide hardware instructions that execute atomically—meaning their execution cannot be interrupted by any timer, context switch, or competing CPU core.

• Disabling Interrupts: A simple uniprocessor technique used by operating system kernels.
• Test-and-Set Lock (TSL): An atomic read-modify-write memory instruction.
• Swap / Compare-and-Swap (CAS): An atomic value exchange primitive that forms the foundation of all modern lock-free algorithms.

---

📑Table of Contents

• 💡 Core Intuition
• 📚 Core Deep-Dive & Concepts
  • 1. Approach 1: Disabling Hardware Interrupts
  • 2. Approach 2: Test-and-Set Lock (TSL)
  • 3. Formal Properties of Test-and-Set Lock
  • 4. Approach 3: The Swap (Compare-and-Swap) Instruction
  • 5. Architectural Invariant: The Stack Pointer & Subroutines
• 📐 Architecture / Visual Blueprint
  • Hardware Memory Bus Locking Architecture
• 🏭 In The Real World: Production Case Study
  • Lock-Free High-Frequency Trading & std::atomic in C++
• 🎯 Exam & Interview Pitfall Check

---

📚 Core Deep-Dive & Concepts

1. Approach 1: Disabling Hardware Interrupts

Definition: Before entering its Critical Section, a process executes a privileged instruction to disable all hardware interrupts. Upon exiting its Critical Section, it re-enables interrupts.

void process_with_disabled_interrupts() {
    while (true) {
        /* Initial Section */
        
        /* Entry Section */
        disable_interrupts(); // Privileged CPU instruction (cli on x86)
        
        /* === CRITICAL SECTION === */
        // Runs uninterrupted without timer preemption...
        
        /* Exit Section */
        enable_interrupts();  // Privileged CPU instruction (sti on x86)
        
        /* Remainder Section */
    }
}

Disabling Interrupts: Uniprocessor vs. Multiprocessor Reality

Why interrupt masking works inside kernels but fails across modern multicore hardware

Uniprocessor Kernel

Single-Core OS Kernels: Effective

🛡️

Dominant Architecture / DomainGuarantees Non-Preemption

• •Timer Interrupt Suppression: The CPU timer tick cannot fire while interrupts are disabled.
• •Zero Preemption: The running thread cannot be context-switched out.
• •Simple & Fast: Requires only a single hardware instruction (cli).

"This solution is only used by the OS for tiny internal kernel updates."

Multiprocessor Flaw

Multicore Systems: Completely Invalid

❌

Dominant Architecture / DomainDoes Not Stop Other Cores

• •Local Effect Only: Disabling interrupts on CPU Core 0 has zero effect on CPU Core 1.
• •Concurrent Access: Core 1 continues executing user code and accesses shared RAM simultaneously.
• •System Freeze Danger: If a user process disables interrupts and enters an infinite loop, the entire OS hangs.

"If a user process disables interrupts, it can block the entire system."

---

2. Approach 2: Test-and-Set Lock (TSL)

Definition: test_and_set is a hardware instruction that atomically reads the memory word, overwrites it with true, and returns the original (old) value—all executed as a single indivisible memory bus transaction.

Conceptual Definition of the Instruction:

// Executed ATOMICALLY by hardware in a single clock cycle
boolean test_and_set(boolean *target) {
    boolean rv = *target; // 1. Read old value
    *target = true;       // 2. Set target to true
    return rv;            // 3. Return old value
}

Implementing Mutual Exclusion with TSL:

// Shared variable: boolean lock = false;

void worker_process() {
    while (true) {
        /* Entry Section: Spin until lock is acquired */
        while (test_and_set(&lock));
        
        /* === CRITICAL SECTION === */
        // Access shared data safely...
        
        /* Exit Section: Release lock */
        lock = false;
        
        /* Remainder Section */
    }
}

How the Spinlock Works Step-by-Step:

1. Initially lock = false:
   • Process $P_1$ calls test_and_set(&lock).
   • The hardware reads false, writes true into lock, and returns false.
   • The while-loop condition while(false) evaluates to false. $P_1$ breaks out and enters the Critical Section.
2. When $P_2$ attempts entry while $P_1$ is inside (lock = true):
   • Process $P_2$ calls test_and_set(&lock).
   • The hardware reads true, writes true into lock, and returns true.
   • The while-loop condition while(true) evaluates to true. $P_2$ spins and continues polling.
3. When $P_1$ exits:
   • $P_1$ sets lock = false;
   • On the next spin cycle of $P_2$, test_and_set(&lock) returns false and sets lock = true. $P_2$ enters immediately.

---

3. Formal Properties of Test-and-Set Lock

The 5 Verified Properties of Test-and-Set Lock

Formal systems analysis of the classical hardware spinlock

🔒

1. Mutual Exclusion

SATISFIED

• Guaranteed by hardware atomicity.
• Only the exact process that flips lock from false to true enters the Critical Section.
• Zero chance of simultaneous admission.

Key Abstractions / Calls

Atomic FlipSingle Winner

⚡

2. Progress

SATISFIED (Deadlock Free)

• Test and Set is strictly Deadlock Free.
• If CS is empty (lock == false), any waiting process acquires it immediately without delay.
• Uninterested processes in remainder sections have zero effect on lock.

Key Abstractions / Calls

Deadlock FreeImmediate Entry

⏳

3. Bounded Waiting

NOT SATISFIED

• Test and Set does NOT satisfy Bounded Waiting.
• When lock is released, which waiting process wins next is random and arbitrary.
• Determined by memory bus arbitration and cache line invalidation race.

Key Abstractions / Calls

Arbitrary WinnerNo Bound

⚠️

4. Starvation Free?

NOT STARVATION FREE

• Test and Set is NOT starvation free.
• A slow CPU core can be repeatedly out-competed by faster cores on the memory bus.
• An unlucky thread can spin forever in its while-loop.

Key Abstractions / Calls

Starvation PossibleUnfair Arbitration

🎲

5. Execution Order

NO GUARANTEE

• Does NOT guarantee order of execution.
• Entry does not follow FIFO arrival timestamps.
• First thread to request the lock is NOT guaranteed to enter first.

Key Abstractions / Calls

Non-FIFOUnordered Grants

---

4. Approach 3: The Swap (Compare-and-Swap) Instruction

In architectures like x86, the atomic operation is generalized into swap or Compare-And-Swap (CAS):

// Atomic Swap primitive
void swap(boolean *a, boolean *b) {
    boolean temp = *a;
    *a = *b;
    *b = temp;
}

// Spinlock using Swap:
// Shared: boolean lock = false;
void worker_swap() {
    boolean key = true;
    while (true) {
        key = true;
        while (key == true) {
            swap(&lock, &key); // Atomically swaps local key with shared lock
        }
        
        /* Critical Section */
        
        lock = false;
        
        /* Remainder Section */
    }
}

---

5. Architectural Invariant: The Stack Pointer & Subroutines

Fundamental Hardware Theorem: If in a processor architecture there is no Stack Pointer Register ($SP$), then that processor cannot implement a subroutine call instruction (such as CALL / RET).

Architectural Rationale:

• When a program calls a subroutine or function, the CPU must save the Return Address (the Program Counter $PC$) so it knows where to resume upon returning.
• A hardware subroutine call instruction automatically pushes the current $PC$ onto the call stack addressed by the Stack Pointer register ($SP$).
• Without an $SP$ register, the CPU has no automatic hardware mechanism to track nested call frames, recursion, or dynamic return addresses. Any return jump must be manually simulated using static registers (as in ancient architectures like early IBM mainframes).

---

📐 Architecture / Visual Blueprint

Hardware Memory Bus Locking Architecture

The blueprint below traces how the CPU memory controller asserts the physical LOCK# bus signal to serialize multi-core atomics:

Hardware Bus Locking & Atomic Cache Line Invalidation

Tracing how physical CPU cores execute Test-and-Set without bus contention

CPU Core 0

CPU Core 1

Memory Bus Arbiter

L3 Shared Cache / RAM

1

CPU Core 0→Memory Bus Arbiter

Core 0 Asserts LOCK# Signal

2

CPU Core 1→Memory Bus Arbiter

Core 1 Bus Request Stalled

3

CPU Core 0→L3 Shared Cache / RAM

Core 0 Reads & Writes in 1 Cycle

4

CPU Core 1→L3 Shared Cache / RAM

Core 1 Reads Updated State (true)

---

🏭 In The Real World: Production Case Study

Lock-Free High-Frequency Trading & std::atomic in C++

In ultra-low-latency financial trading and game engines, OS-level mutexes are strictly forbidden because entering the kernel incurs a $1{,}000\text{ ns}$ context switch penalty. Systems instead use Lock-Free Queues powered by the x86 LOCK CMPXCHG hardware instruction:

#include <atomic>

template <typename T>
class LockFreeStack {
    struct Node {
        T data;
        Node* next;
        Node(T val) : data(val), next(nullptr) {}
    };
    std::atomic<Node*> head;

public:
    void push(T val) {
        Node* new_node = new Node(val);
        // Atomically update head pointer using hardware Compare-And-Swap (CAS)
        do {
            new_node->next = head.load();
        } while (!head.compare_exchange_weak(new_node->next, new_node));
    }
};

• Zero Kernel Context Switches: Threads run 100% in user space.
• Maximum Throughput: If contention occurs, only the losing thread retries its CAS loop; the winning thread commits in under $10\text{ nanoseconds}$.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Define the test_and_set instruction. Which of the three critical section criteria are satisfied by a simple test_and_set spinlock, and which are violated? Answer:

1. Definition: test_and_set is an atomic hardware instruction that reads a memory word, sets its value to true, and returns the old value in a single indivisible memory bus operation.
2. Criteria Evaluation:
   • Mutual Exclusion: Satisfied. The atomic flip guarantees at most one process enters.
   • Progress: Satisfied. The solution is deadlock-free; if the lock is free, a waiting process enters immediately.
   • Bounded Waiting: Violated. It does not guarantee execution order or bounded waiting. A process can starve indefinitely if other cores repeatedly win the bus race.

Question 2: Why can an operating system not rely on disabling interrupts as a general-purpose synchronization solution for user applications on modern multicore systems? Answer:

1. Multicore Ineffectiveness: Disabling interrupts masks interrupts only on the local CPU core. Other physical cores continue executing and will access shared memory simultaneously.
2. System Security & Stability: Granting unprivileged user processes the ability to disable interrupts allows buggy or malicious user code to execute an infinite loop, freezing the entire operating system permanently.

Common Interview Traps

• The "Busy Waiting Wastes No CPU" Trap: A spinlock uses while(test_and_set(&lock));. While spinning, the CPU runs at 100% load burning clock cycles without doing useful work. On uniprocessor systems, spinlocks are catastrophic because the spinning process prevents the lock-holding process from running to release the lock!
• Assuming Test-and-Set Prevents Starvation: Test-and-Set guarantees deadlock freedom, but NOT starvation freedom. Never conflate deadlock freedom with starvation freedom.
• The Missing Stack Pointer Register Theorem: Remember: A CPU without a Stack Pointer register cannot execute subroutine calls (CALL/RET), because it has no mechanism to push and pop return addresses.

---

🗺️View Complete Operating Systems Roadmap & Syllabus

← Previous Topic4.3 Software Solutions: Peterson's AlgorithmNext Topic →4.5 Semaphores: Counting, Binary & Mutexes