Solving race conditions using atomic counters

Aditya Soni

Before I get into discussing race conditions and atomic counters and their underlying algorithms, I want to thank you folks for subscribing to <Hello World!>. When I started this newsletter more than 2 months ago, we had around 100 subscribers, and today we are at more than 350 subscribers. Thank you for sticking even when I was not writing articles regularly. Now let's get into today's topic.

Increment Operation

For the scope of today's article, we will consider a basic increment operation. Incrementing is a basic operation where the value of a variable is increased by a fixed amount, usually by one. In a multithreaded environment, incrementing a shared variable can lead to issues if not handled properly. For example, if two threads read a value simultaneously, increment it, and then write it back, one increment could be lost. This is very commonly also known as a race condition.

What is an atomic operation?

An atomic operation in programming is an operation that runs completely independently of any other operations and is indivisible. This means it cannot be interrupted or observed to be in an incomplete state by other threads. These operations are crucial in concurrent programming to prevent race conditions, where multiple threads try to modify the same variable simultaneously.

Now, simply put an atomic increment is an increment operation done atomically. But how does this ensure that we escape the good old race condition? Let's discuss!

One algorithm that takes care of atomic increments is Compare and Swap (CAS). Let's discuss it's implementation details

Compare and Swap (CAS)

CAS take three inputs

• A memory location (let's call it ptr).
• An expected old value (expected).
• A new value to set (new_value).

The CAS operation performs the following steps atomically:

• It first reads the current value at ptr.
• Then, it compares this current value with expected.
• If the current value matches expected, it means the value has not been changed by another thread since it was last read. In this case, CAS updates the value at ptr to new_value.
• If the current value does not match expected, it means some other thread has updated the value. In this case, the operation fails, and the memory is not updated and a retry is required.

CAS returns a boolean value indicating success or failure. In some implementations, it might also return the current value at ptr.

Now, let's implement the above in python3. However, please note that atomic operations like CAS are not directly accessible as built-in functions, mainly because Python's Global Interpreter Lock (GIL) already prevents multiple native threads from executing Python bytecodes at once. This below codeblock is strictly for educational purposes. We will implement the same in golang in the latter part of this article.

# Python3
import threading

class AtomicCounter:
    def __init__(self):
        self.value = 0
        self.lock = threading.Lock()

    def compare_and_swap(self, expected, new_value):
        with self.lock:
            if self.value == expected:
                self.value = new_value
                return True
            return False

    def increment(self):
        while True:
            current = self.value
            new = current + 1
            if self.compare_and_swap(current, new):
                return  # Successfully incremented, exit loop

# Example usage
counter = AtomicCounter()

# Incrementing the counter in multiple threads
def increment_counter():
    for _ in range(1000):
        counter.increment()

# Creating multiple threads
threads = [threading.Thread(target=increment_counter) for _ in range(10)]

# Starting the threads
for thread in threads:
    thread.start()

# Waiting for all threads to complete
for thread in threads:
    thread.join()

print(f"Counter value after increments: {counter.value}")
        

//golang
package main

import (
    "fmt"
    "sync"
    "sync/atomic"
)

type AtomicCounter struct {
    value int64
}

func (c *AtomicCounter) Increment() {
    for {
        // Capture the current value
        current := atomic.LoadInt64(&c.value)

        // Calculate the new value
        new := current + 1

        // Try to update the value using CAS
        if atomic.CompareAndSwapInt64(&c.value, current, new) {
            // If successful, exit the loop
            return
        }
        // If CAS fails, the loop will retry with the updated current value
    }
}

func (c *AtomicCounter) Value() int64 {
    return atomic.LoadInt64(&c.value)
}

func main() {
    var wg sync.WaitGroup
    counter := AtomicCounter{}

    // Incrementing the counter in multiple goroutines
    for i := 0; i < 10; i++ {
        wg.Add(1)
        go func() {
            defer wg.Done()
            for j := 0; j < 1000; j++ {
                counter.Increment()
            }
        }()
    }

    // Waiting for all goroutines to complete
    wg.Wait()

    fmt.Printf("Counter value after increments: %d\n", counter.Value())
}
        

How do atomic increment ensure that other threads don't read the shared memory resource without explicit locking?

An extremely important pointer to note here is if a thread is executing an atomic increment operation, other threads are not allowed to read the shared memory resource. This however, does not use typical mutexes (lock based sync). Interesting, right?

Atomic operations are executed directly by the CPU. When a CPU executes an atomic operation, it does so in a manner that ensures the entire operation (like reading a value, modifying it, and writing it back) is completed as a single, indivisible sequence.

Many atomic operations involve memory fences or barriers. These are special instructions that prevent certain types of memory reordering around the atomic operation. A memory fence ensures that all memory reads and writes before the fence are completed before any reads and writes after the fence start.

Simply put, other threads see either the state before the operation or after the operation, but never an in-between state.

How It Differs from Locking

1. No Locking Mechanism: In a lock-based system, a thread would explicitly acquire a lock, perform its operation, and then release the lock. During this time, any other thread attempting to acquire the same lock would be blocked. Atomic operations achieve thread safety without this explicit lock-and-block mechanism.
2. Non-blocking Nature: Atomic operations, especially those based on compare-and-swap (CAS), are non-blocking. If a thread's CAS operation fails (because another thread has updated the value), it can immediately retry the operation. This is more efficient than waiting on a lock.

That's it for today folks. If you learned something new today, consider subscribing to <Hello World!> and share the same with your peers. I'm constantly researching about interesting software engineering topics and try to share the same via linkedin posts and newsletters. Happy Engineering!!!