Karthik Gangula 1. Coarse-Grained Synchronization (Blocking Stack)
Every operation must acquire the exact same lock before touching the internal data. This means that only 1 operation can execute at any given time. The only upside to this compared to a regular stack is that there are multiple threads accessing this, its thread safe, but the threads still have to wait their turn. And under high contention, threads waiting for the lock will get put to sleep by the OS, which triggers expensive context switches and cpu cache invalidation (false sharing).
False sharing is when separate threads modify the independent variables sitting in the same cache line, causing it to constantly invalidate and this forces the CPU hardware to get trapped in a loop of updating the cache lines of different cores.
The implementation is give below:
#include <vector>
#include <mutex>
#include <thread>
#include <condition_variable>
#include <iostream>
template <typename T>
class BlockingStack{
private:
std::vector<T> stack;
mutable std::mutex mtx;
mutable std::condition_variable cv;
public:
BlockingStack() = default;
~BlockingStack() = default;
BlockingStack(const BlockingStack&) = delete;
BlockingStack& operator=(const BlockingStack&) = delete;
void push(T item){
{
std::lock_guard<std::mutex> lock(mtx);
stack.push_back(item);
}
cv.notify_one();
}
T pop(){
std::unique_lock<std::mutex> lock(mtx);
cv.wait(lock, [this]{ return !stack.empty(); });
T tmp = std::move(stack.back());
stack.pop_back();
return tmp;
}
T peek() const{
std::unique_lock<std::mutex> lock(mtx);
cv.wait(lock, [this]{return !stack.empty() ;});
return stack.back();
}
size_t size() const{
std::unique_lock<std::mutex> lock(mtx);
return stack.size();
}
};
I’ll also give some notes on this. So when implementing the stack class, there’s 4 methods that we need which is push, pop, peek and size. The next step is to define the mutex, conditional variable and vector itself. The problem here is that we cannot create a new object by copying an existing one since mutex and conditional variable cannot be copied as this would lead to undefined locking behavior. This is why we include the
BlockingStack(const BlockingStack&) = delete; // prevents anyone from creating a new object by copying an existing one or passing it by value into a function
BlockingStack& operator=(const BlockingStack&) = delete; // prevents from copying using the assignment = operatorThe next is push, here we use lock guard, its nice since it holds the lock until it goes out of scope. In other places you might notice that I used unique_lock, its because we would need to unlock in order to let other threads perform an operation. This is done through the help of condition variable.
Inside the pop we also used std::move. This is done so that its cast to an rvalue reference (tmp val).
One more thing is that you might notice the implementation of cv.wait over there. Actually, without it there will be a race condition between the code that calls empty and stack.back(). This is because you can have one thread call back() and another thread call back and pop before that thread goes to pop, and it will cause an error. To avoid this we use cv.wait. This is actually an interface design problem and its dealt in way more detail in cpp concurrency in action section 2.3 and 3.2.3.
2. Fine-Grained / Split-Lock Stack
An improvement over coarse-grained locking that attempts to reduce contention by allowing independent operations to proceed concurrently. The shared mutex here allows different threads to read the top variable but at the same time unique lock ensures that during push and pop there are no read operations happening.
#include <mutex>
#include <shared_mutex>
#include <memory>
#include <stdexcept>
template <typename T>
class FineGrainedStack {
private:
struct Node {
T data;
std::unique_ptr<Node> next;
Node(T val) : data(std::move(val)), next(nullptr) {}
};
std::unique_ptr<Node> head;
mutable std::shared_mutex mtx;
public:
FineGrainedStack() = default;
~FineGrainedStack() = default;
// Prevent copying
FineGrainedStack(const FineGrainedStack&) = delete;
FineGrainedStack& operator=(const FineGrainedStack&) = delete;
// Push an item onto the stack (requires exclusive write lock)
void push(T item) {
auto new_node = std::make_unique<Node>(std::move(item));
std::unique_lock<std::shared_mutex> lock(mtx);
new_node->next = std::move(head);
head = std::move(new_node);
}
// Pop the top item off the stack (requires exclusive write lock)
T pop() {
std::unique_lock<std::shared_mutex> lock(mtx);
if (!head) throw std::runtime_error("Stack is empty !");
T tmp = std::move(head->data);
head = std::move(head->next);
return tmp;
}
// View the top item without removing it (allows concurrent readers using shared lock)
T peek() const {
std::shared_lock<std::shared_mutex> lock(mtx);
if (!head) throw std::runtime_error("Stack is empty");
return head->data;
}
};
3. Lock-Free Stack (Treiber Stack)
A singly linked list where the head pointer is managed atomically (std::atomic<Node*>), entirely abandoning OS-level locks and mutexes. It relies on Compare-And-Swap (CAS). The CPU atomically checks if a memory location matches an expected value. If it does, it overwrites it with a desired value and returns true. If someone else changed it, the CAS fails and returns false. This structure is lock-free, at least one thread is guaranteed to make progress, and no threads are ever put to sleep by the OS.
However, one of the problem with this is the ABA problem.
For example, when Thread 1 and Thread 2 are operating on the same bank account.
When Thread 1 wants to withdraw some money, it reads the actual balance to use that value for comparing the amount in the CAS operation later. However, for some reason, Thread 1 is a bit slow — maybe it’s blocked.
In the meantime, Thread 2 performs two operations on the account using the same mechanism while Thread 1 is suspended. First, it changes the original value, which has already been read by Thread 1, but then, it changes it back to the original value.
Once Thread 1 resumes, it will appear as if nothing has changed, and CAS will succeed. The problem here is that the data read is no longer valid and thread 1 has no way of telling and will corrupt the data structure.
The ABA problem is particularly prevalent in algorithms that use free lists or other-wise recycle nodes rather than returning them to the allocator. To prevent this, modern systems use tagged pointers (combining the data pointer with a monotonically increasing counter/version number).
Even if the value returns to $100, the counter increments every single time the memory is modified (e.g., from version 1 to version 3). Because the version changed, the CAS check will safely fail, forcing Thread 1 to recognize that an intervening modification occurred and retry its operation.
#include <iostream>
#include <atomic>
#include <memory>
template <typename T>
class TreiberStack{
private:
struct Node {
T data;
std::shared_ptr<Node> next;
explicit Node(T item): data(std::move(item)), next(nullptr), {};
}
std::atomic<std::shared_ptr<Node>> head;
public:
TreiberStack = default;
~TreiberStack = default;
TreiberStack(const TreiberStack) = delete;
TreiberStack& operator=(const TreiberStack&) = delete;
void push(T item){
auto newNode = std::make_shared<Node>(std::move(item));
auto oldHead = head.load(std::memory_order_relaxed);
do {
newNode->next = oldHead;
} while (!head.compare_exchange_weak(oldHead, newNode, std::memory_order_release, std::memory_order_relaxed));
}
bool pop(T& out_item){
auto oldHead = head.load(std::memory_order_relaxed);
std::shared_ptr<Node> newHead;
do {
if (!oldHead) return false;
newHead = oldHead->next;
} while (!head.compare_exchange_weak(oldHead, newHead,
std::memory_order_release,
std::memory_order_relaxed));
out_item = std::move(oldHead->data);
return true;
}
bool isEmpty() const{
return head.load(std::memory_order_relaxed) == nullptr;
}
};
make_shared is used here instead of make_unique, earlier i mentioned about the ABA problem, one way to avoid it is to maintain a counter. The counter is already built into make shared as it has a control block to keep track of all the references. When the counter reaches 0, the object is deleted.
Another thing to note here was memory order, CPU/compiler often change the order of code execution to speed things up. memory_order_relaxed helps to provide atomicity for the read without enforcing any unncessary ordering on surrounding codes.
For the CAS loop atomic swap, it was attemped using compare_exchange_weak. If the swap succeeds, the memory order constraints are released else we maintain on memory_order_relaxed and try again. We also used compare_exchange_weak instead of compare_exchange_strong.
Many modern CPU architectures (most notably ARM, which powers Apple Silicon, smartphones, and many modern cloud servers, as well as PowerPC) do not have a single, magical “Compare-and-Swap” hardware instruction.
Instead, they implement it using a pair of instructions:
- Load-Linked / Load-Reserved (LL/LR): Reads a memory address and tells the CPU to watch it for changes.
- Store-Conditional (SC): Tries to write the new value, but it only succeeds if no other core touched that memory address in between.
Because the Store-Conditional can fail for many hardware-level reasons (such as a cache line being invalidated, a background interrupt, or a context switch), the hardware itself is inherently “weak”, it can fail even if the value technically matched.
If you call compare_exchange_strong on an ARM processor, the CPU or compiler has to wrap that hardware instruction in a hidden internal retry loop to guarantee it never fails spuriously.
When you write compare_exchange_weak inside your own do-while loop (like the one in a Treiber stack), you are already providing a loop. If you use compare_exchange_strong, you end up with a loop inside a loop, which adds unnecessary overhead on architectures like ARM.
4. Elimination-Backoff Stack
You might be thinking this is just gonna try the CAS loop and then do a wait in time backoff or something before retrying and burning CPU cycles. It’s partly true but it doesnt just do backoff in time but also in space.
It creates an array called the elimination array with slots 0 to n, where n is typically the number of threads that you are running. When the thread cannot push the data onto the stack it will come here and put its data in a random slot. Now it waits for an opposing thread (pop() thread) to come and then the data gets eliminated. In this way, we dont even need to go back to the treiber stack. If the backoff timer expires and no partner shows up at the slot, the thread just takes the item back to the treiber stack.
#include <iostream>
#include <atomic>
#include <memory>
#include <chrono>
#include <random>
#include <thread>
#include <vector>
#include <optional>
template<typename T>
class Exchanger {
private:
enum class State { EMPTY, WAITING, BUSY, COMPLETE };
std::atomic<State> state{State::EMPTY};
std::optional<T> slot_value;
public:
Exchanger() = default;
bool exchange(std::optional<T>& value, std::chrono::nanoseconds timeout) {
State expected = State::EMPTY;
if (state.atomic_compare_exchange_weak(expected, State::WAITING, std::memory_order_acq_rel)){
slot_value = std::move(value);
auto start = std::chrono::steady_clock::now();
while (std::chrono::steady_clock::now() - start < timeout){
if (state.load(std::memory_order_acquire) == State::COMPLETE){
value = std::move(slot_value);
state.store(State::EMPTY, std::memory_order_release);
return true;
}
std::this_thread::yield();
}
expected = State::WAITING;
if (state.atomic_compare_exchange_weak(expected, State::EMPTY, std::memory_order_acq_rel)){
return false;
} else {
while (state.load(std::memory_order_acquire) != State::COMPLETE){
std::this_thread::yield();
}
value = std::move(slot_value);
state.store(State::EMPTY, std::memory_order_release);
return true;
}
}
else if (expected == State::WAITING){
if (slot_value.has_value() == value.has_value()){
return false;
}
State wait_state = State::WAITING;
if (state.atomic_compare_exchange_weak(wait_state, State::BUSY, std::memory_order_acq_rel)){
std::optional<T> temp = std::move(slot_value);
slot_value = std::move(value);
value = std::move(temp);
state.store(State::COMPLETE, std::memory_order_release);
return true;
}
}
return false;
}
};
template <typename T, size_t capacity = 8>
class EliminationArray {
private:
Exchanger<T> exchangers[capacity];
size_t getRandomIndex() {
thread_local std::mt19937 rng(std::random_device{}());
std::uniform_int_distribution<size_t> dist(0, capacity - 1);
return dist(rng);
}
public:
bool visit(std::optional<T>& value, std::chrono::nanoseconds timeout) {
return exchangers[getRandomIndex()].exchange(value, timeout);
}
};
template <typename T>
class EliminationBackoffStack {
private:
struct Node {
T data;
std::shared_ptr<Node> next;
explicit Node(T item) : data(std::move(item)), next(nullptr) {}
};
std::shared_ptr<Node> head{nullptr};
EliminationArray<T> eliminationArray;
public:
EliminationBackoffStack() = default;
~EliminationBackoffStack() = default;
EliminationBackoffStack(const EliminationBackoffStack&) = delete;
EliminationBackoffStack& operator=(const EliminationBackoffStack&) = delete;
void push(T item) {
auto new_node = std::make_shared<Node>(std::move(item));
auto old_head = std::atomic_load(&head);
do {
new_node->next = old_head;
if (std::atomic_compare_exchange_weak(&head, &old_head, new_node)){
return ;
}
std::optional<T> val_copy(new_node->data);
if (eliminationArray.visit(val_copy, std::chrono::nanoseconds(100))){
return;
}
} while (true);
}
bool pop(T& out_item) {
auto curr_head = std::atomic_load(&head);
std::shared_ptr<Node> new_head;
do {
if (curr_head == nullptr){
std::optional<T> val;
if (eliminationArray.visit(val, std::chrono::nanoseconds(50))){
out_item = std::move(*val);
return true;
}
return false;
}
auto new_head = curr_head->next;
if (std::atomic_compare_exchange_weak(&head, &curr_head, new_head)){
out_item = std::move(curr_head->data);
return true;
}
std::optional<T> val_copy;
if (eliminationArray.visit(val_copy, std::chrono::nanoseconds(100))){
out_item = std::move(*val_copy);
return true;
}
} while (true);
}
bool isEmpty() const {
return std::atomic_load(&head) == nullptr;
}
};
int main() {
EliminationBackoffStack<int> stack;
std::vector<std::thread> threads;
for (int i = 0; i < 4; ++i) {
threads.emplace_back([&stack, i]() {
for (int j = 0; j < 500; ++j) {
stack.push(i * 1000 + j);
}
});
}
for (int i = 0; i < 4; ++i) {
threads.emplace_back([&stack]() {
int val;
for (int j = 0; j < 500; ++j) {
while (!stack.pop(val)) {
std::this_thread::yield();
}
}
});
}
for (auto& t : threads) {
t.join();
}
std::cout << "Elimination-Backoff Stack compiled and executed successfully!" << std::endl;
return 0;
}
Threads don’t just pick a random slot once and give up forever. If Thread A picks Slot 3 and finds nobody there, its timeout triggers almost instantly (e.g., after 100 nanoseconds). It loops back, fails its stack CAS again, and picks a new random slot (maybe Slot 6). Because threads are cycling through random slots at blindingly fast speeds (millions of times per second), pushing and popping threads naturally “intersect” and crash into each other across the array slots.
If you assign fixed slots instead like having pushing threads go to 0 - 3 and popping threads go to 4 -7, threads would still bottleneck and collide at the boundaries of those rules. True randomness ensures that traffic is uniformly distributed across the entire array. It prevents hot-spots and ensures that wherever a cluster of threads is failing, they bounce around until they stumble into a slot where an opposing thread is waiting.
5. Memory Management & Safe Memory Reclamation (SMR)
One thing worth mentioning here is on hazard pointers. Looking at a scenario:
Imagine Thread A and Thread B are interacting with a lock-free stack:
- Thread A wants to
pop()the head node. It reads the head pointer and looks athead->next. - Right at that exact microsecond, Thread B comes along, pops that same node, and immediately calls
delete node;to free the memory. - Thread A now tries to look at
node->next, but that memory has already been deleted and potentially reused by the OS. Thread A crashes or reads garbage data (a Use-After-Free bug).
You can’t use standard std::shared_ptr everywhere because atomic operations on shared pointers have heavy performance penalties or aren’t supported on raw lock-free memory addresses across all platforms.
Every thread has a publicly visible pointer slot assigned to it (a “hazard pointer”). Before a thread reads or touches a node pointer, it publishes that node’s address into its hazard pointer slot, telling other nodes not to delete it. When a thread removes a node and wants to delete it, it scans all threads’ hazard pointer slots. If someone is currently looking at it, the thread puts the node into a private “to-be-deleted-later” retirement list and moves on. Any node that is no longer guarded by any thread’s hazard pointer is finally safe to delete. The thread loops through them and calls delete (or free) in a batch. If Thread A had to stand around waiting for Thread B to finish looking at a node, it would ruin the lock-free nature of the data structure and cause massive performance bottlenecks.
Languages like Java or Go handle this automatically via Garbage Collection (GC). C and C++ don’t have built-in GC, so hazard pointers give you a high-performance, lock-free way to safely recycle memory without letting other threads step on active pointers.