The Art Of Atomics

Section 1: CPUs Go BRRR, Threads Go Vroom!

At the heart of whatever device you are holding to read this lies a tiny, delicate piece of silicon (literally), called the CPU. It doesn't think, it doesn't reason. It executes instructions. That's all it does. Inside it are cores, the units that actually run your code. But here's where things get interesting: a single core doesn't just run one stream of instructions. It can run multiple.

That's what we call threads. And they are not separate machines. A thread is simply one such stream of instructions being executed. Even a single core running one program is executing a thread.

On Intel this is called Hyper-Threading, on AMD, Simultaneous Multithreading (SMT). What SMT gives us is the ability to run more than one of these streams on the same core at the same time. They are not two cores. They share the same execution engine, the same pipelines, and the same caches. The hardware is the same — only the architectural state is duplicated. So these threads don't run independently. They compete.

These threads don't just share execution resources, they also operate on the same memory.

Say, you stored your bank balance in some sneaky variable in RAM. Thread A would update it when you performed a transaction, and Thread B can also read that value (ahem, your account balance). This is how threads communicate, by reading and writing data.

At first glance, it's all sunshine and rainbows. But it isn't.

Even if two threads are running on the same machine, they are not stepping through instructions in lockstep.

One thread might be ahead. Another might be behind. They may observe changes at different times.

There is no single, global timeline that all threads agree on.

Section 2: Two Threads Walk Into a Bar...

Suppose I opened a company and decided to build a stock exchange for my shares. Naturally, I'd use multiple threads to make it fast. More threads, more performance… right?

Let's see how that turns out.

Say, all my shares are stored in a variable called m_TotalShares storing the total shares I own (450,000 to be exact). An investor wants to buy my shares, she requests 100 shares. A thread is created that is meant to retrieve and verify if the requested amount of shares can be bought. The thread happily waddles along, checks and returns true. No issues whatsoever. She buys my shares.

Now two brothers come to buy some shares, one wants 200,000 the other wants 300,000, but I only have about 450K of them. Both request the shares. You would guess, one of those requests will fail, of course it will fail. But whose request?

Is it brother A, or brother B?

Assuming both threads run concurrently, both requests will be fulfilled.

if(m_TotalShares >= requested) {
    m_TotalShares -= requested; // Subtract the shares
    return true;
}

But wait, 300,000 + 200,000 -> 500,000. (Didn't know I had secret shares!). That's more than 450,000, which is wrong. You'd think one of the threads got it wrong.

It didn't.

Both threads are actually correct locally, but wrong globally.

This isn't a rare edge case. The moment two threads read and write the same memory without coordination, this goes wrong.

Suppose we have a ticket counter with a variable m_Counter. This looks like a simple increment, but it isn't.

The operation behaves like this
-> Read counter's value
-> Modify the value
-> Write back the value

When two threads perform the increment, both read the same value, modify it, and write back. One update is lost.

(One thread basically just got yeeted out of existence.)

Now consider this.

transactions++;
balance -= 100;

Another thread in the background performs

if (transactions > 0)
    print(balance);

It is possible that the background thread can swoop in like a superhero and observe the updated transactions, but an old balance, a partial update.

We have:

• Lost updates
• Inconsistent reads
• Correct code
• Incorrect results

Nothing here is obviously wrong. And yet, everything breaks.

So what does "correct" even mean here?

• Should threads see updates immediately?
• Should operations appear in order?
• Should all threads agree on what happened?

Right now, we have no way to answer that. We need rules.

Section 3: Maybe this is correct....?

Obviously, we are doing something wrong. Let's try to "engineer" our way through it.

Experiment 1

Maybe, since both threads are entering the check at the same time, we need to prevent that from happening!

while(busy) {
    // Cutie-patootie thread waiting
}

busy = true; // Thread takes over the world!

if (m_TotalShares >= requested) {
    m_TotalShares -= requested;
}

busy = false; // Thread reconsidered its choices

This seems promising. The while block prevents any other threads from entering, while only one thread performs a change (if any).

But, wait! The busy variable now faces the same issue. If 2 threads hit the while block at the same time, find it to be false, they can just skip it and perform the change. Great! Back to square one.

Experiment 2

You know what, let's make our lives a bit easier. Bye Bye Multithreading.

It works perfectly! Only one thread runs and performs the requests. On the other side, all investors can submit their requests and it can be stored in a queue.

investorQueue.pushRequest(request);

The single worker thread now runs this loop

// The chosen one....
while(true){
    auto nextRequest = investorQueue.getNextRequest();

    if(nextRequest.shares <= m_TotalShares){
        m_TotalShares -= nextRequest.shares;
    }
}

Yes this is good, we have an amazing solution. But we also lost the biggest advantage of multithreading. Suppose a thousand investors want to buy my shares (I'll be rich!), and each transaction costs a minute of work (We chose a simplified model to prevent mental trauma), then it would take 1000 minutes, or 16.666667 hours.

Application works, but painfully slow. Those investors are gonna have a real bad time.

Experiment 3

Alright, let's get our thinking cap on. You might already know what I am about to say. In experiment 2 we used a queue to push requests so the worker thread can poll them and perform them.

But here's the kicker, the queue is a shared structure and is not coordinated with all the threads that might try to access it. We could have 100 threads interfering with each other and corrupting the queue, only because they were so unlucky that they hit the queue at the exact same time.

Lets stop sharing memory (no more of sharing is caring). Each thread has its own queue.

// N Threads , N Queues.
// No sharing
motherQueue<RequestQueue>[MAX_THREADS];

Now a mother thread will iterate over all queues, and fulfil all requests one by one.

while(true){
    for(each : motherQueue){
        while(!each.isEmpty()){
            // Perform the check and transactions.
        }
    }
}

But hold on. We made it serialized. Again! The order in which the mother thread processes queues now decides who gets the shares.

Process A first → B might fail

Process B first → A might fail

Which one is correct? We still don't know.

We need some order, some rules, something that guarantees how data is shared safely.

Else we'll be running in circles, fixing concurrent read-writes at 3 am.

Section 4: Hardware Gods Incarnate: TSO (Total Store Ordering)

Clearly, the Gods above (named x86) blessed us with some rules. A bit too lenient, to be honest.

Let's see what the scriptures say....

Suppose we have 2 variables A and B.

A = 1;
B = 2;

The scriptures say that if a thread ran the above code, then for any threads looking at it, this order will be preserved. A is set to 1, and then B is set to 2, no excuses!

Similarly, if I were to set A and B to two variables x and y....

x = A;
y = B;

Again, the order of executing them is preserved.

What if it was this?

r = B;
A = 1;

Ordering is preserved.

Pretty simple, right? Now the weird part.

But if we had this?

A = 1;
r = B;