Atomic Hardware Instructions: Test-and-Set (TSL) vs Compare-and-Swap (CAS)

Every beginner systems programmer eventually attempts to build a mutual exclusion lock using a simple global boolean flag:

volatile int lock = 0;

void acquire() {
    while (lock == 1); // 1. Spin until lock is free
    lock = 1;          // 2. Set the lock
}

void release() {
    lock = 0;
}

On paper, this looks intuitive. In production silicon, it fails catastrophically.

---

⚡ The Disastrous Race Condition

The fundamental flaw is that testing the lock and setting the lock are two separate, interruptible assembly instructions:

[ Core 1: Thread A ]                       [ Core 2: Thread B ]
         │                                          │
         ├─ 1. Reads lock (0: Free)                 │
         │  (Preempted / Interrupted!)              │
         │                                          ├─ 2. Reads lock (0: Free)
         │                                          ├─ 3. Writes lock = 1
         │                                          ├─ 4. Enters Critical Section!
         ├─ 5. Resumes! Writes lock = 1             │
         ├─ 6. Enters Critical Section! (💥 DUPLICATE ENTRY)

Both threads enter the critical section concurrently, corrupting shared memory.

---

🛡️ Atomic Hardware Instructions

To solve this, CPU chip designers introduced hardware-level instructions that perform read-modify-write operations atomically in a single indivisible bus transaction:

1. Test-and-Set Lock (TSL)

On x86 architectures (via BTS or XCHG with the LOCK prefix):

TSL Register, LockVar

In a single clock cycle, the CPU:

1. Locks the shared memory bus (or asserts cache line exclusivity via MESI protocol).
2. Copies the current value of LockVar into the CPU register.
3. Overwrites LockVar with 1.
4. Releases the bus.

Because no other CPU core can access the memory address between the read and the write, mutual exclusion is physically guaranteed!

2. Compare-and-Swap (CAS)

Represented by CMPXCHG on x86, CAS is the universal primitive behind all modern lock-free programming:

bool CAS(int *addr, int expected, int new_value) {
    if (*addr == expected) {
        *addr = new_value;
        return true;
    }
    return false;
}

If another core modified the variable in the background, CAS fails safely without locking, allowing the caller to retry in a lock-free loop.

Trace atomic memory bus locks on Binary Dose.