Free lesson · Operating Systems

Shared variable

Easy15 min readoperating-systemsosconcurrency

Why Shared Data Breaks Everything

In Module 04 you learned that processes need to communicate. Shared memory is the fastest way to do it - no kernel involvement, no data copying, nanosecond latency. But there is a cost: the moment two processes or threads can read and write the same data, correctness is no longer automatic.

Consider the simplest possible operation: incrementing a counter. A thread reads the counter value, adds one, and writes the result back. That is three instructions - load, add, store. If only one thread does this, the counter is always correct. But if two threads do it simultaneously, the counter can lose updates. You saw a preview of this in Module 04's shared memory topic. Now we are going to understand exactly why it happens, what the formal name for the problem is, and what properties a solution must have.

This is the critical section problem, and it is one of the most important concepts in all of computer science. Every synchronization mechanism you will learn in this module - mutexes, semaphores, condition variables, monitors - exists because of this problem. Every concurrency bug in production - from corrupted database rows to lost financial transactions - traces back to a violation of the rules this topic establishes.

The Counter Example in Slow Motion

Let us walk through the counter problem at the instruction level. Suppose a shared variable counter holds the value 5. Two threads, Thread A and Thread B, each want to increment it. The high-level code is counter = counter + 1. But the CPU does not execute that as a single operation. It compiles to three machine instructions:

LOAD - Read the current value of counter from memory into a CPU register
ADD - Add 1 to the value in the register
STORE - Write the register value back to counter in memory

If Thread A runs all three instructions before Thread B starts, the final value is 7 (5 → 6 → 7). That is correct. But threads are scheduled by the OS, and the OS can preempt a thread between any two instructions. Here is what happens when the timing goes wrong:

Step	Thread A	Thread B	Register A	Register B	Memory (`counter`)
1	LOAD counter	-	5	-	5
2	ADD 1	-	6	-	5
3	-	LOAD counter	6	5	5
4	-	ADD 1	6	6	5
5	STORE counter	-	6	6	6
6	-	STORE counter	6	6	6

The final value is 6 instead of 7. One increment was lost. Both threads loaded the same initial value (5), both computed 6, and both stored 6. The second store overwrote the first without incorporating it.

This is not a theoretical problem. It happens in production systems every day. Database transactions that do not use proper isolation levels lose updates exactly like this. Web servers that share counters between request-handling threads lose counts. Financial systems that process concurrent trades without proper locking miscalculate balances.

sequenceDiagram
    participant TA as Thread A
    participant MEM as Shared Memory<br/>(counter = 5)
    participant TB as Thread B
    
    TA->>MEM: LOAD counter (reads 5)
    Note over TA: Register A = 5
    Note over TA: ADD 1 → Register A = 6
    
    TB->>MEM: LOAD counter (reads 5)
    Note over TB: Register B = 5
    Note over TB: ADD 1 → Register B = 6
    
    TA->>MEM: STORE 6
    Note over MEM: counter = 6
    
    TB->>MEM: STORE 6
    Note over MEM: counter = 6
    
    Note over MEM: Expected: 7<br/>Actual: 6<br/>LOST UPDATE

This sequence diagram shows the lost update problem with a shared counter. Thread A loads the counter value of 5, adds 1 to get 6 in its register, but before it stores the result, Thread B also loads the counter value of 5 and adds 1 to get 6. Thread A stores 6, then Thread B stores 6 - overwriting Thread A's result. The final counter value is 6 instead of the expected 7. One increment was lost because the operations interleaved.

What Is a Critical Section?

Now we have the vocabulary to define the problem precisely.

A critical section is any section of code where a thread accesses shared data - reads it, writes it, or both. In the counter example, the three-instruction sequence (LOAD, ADD, STORE) is the critical section. It is "critical" because executing it incorrectly (by interleaving with another thread's execution of the same sequence) produces wrong results.

The critical section problem is the challenge of ensuring that when one thread is executing inside its critical section, no other thread is executing inside its own critical section that accesses the same shared data. If we can guarantee this, the interleaving problem disappears.

To be more precise, every thread's code can be divided into four regions:

Entry section - the code a thread executes to request permission to enter its critical section. This is where synchronization logic lives (acquiring a lock, waiting on a semaphore, etc.).

Critical section - the code that accesses the shared resource. This must execute atomically with respect to other threads' critical sections for the same resource.

Exit section - the code a thread executes after leaving its critical section to signal that other threads can now enter. This is where the lock is released or the semaphore is signaled.

Remainder section - everything else the thread does that does not involve the shared resource.

graph TD
    A["Entry Section<br/>Request permission to enter"] --> B["Critical Section<br/>Access shared resource"]
    B --> C["Exit Section<br/>Release permission"]
    C --> D["Remainder Section<br/>Non-shared work"]
    D --> A
    
    style A fill:#4f46e5,stroke:#4338ca,color:#fff
    style B fill:#dc2626,stroke:#b91c1c,color:#fff
    style C fill:#4f46e5,stroke:#4338ca,color:#fff
    style D fill:#6b7280,stroke:#4b5563,color:#fff

This diagram shows the four regions of code in a thread that uses a critical section. The thread moves through a cycle: first the Entry Section where it requests permission to enter, then the Critical Section where it accesses the shared resource, then the Exit Section where it releases permission, and finally the Remainder Section where it does work that does not involve the shared resource. After the Remainder Section, the cycle repeats back to the Entry Section.

The goal is to design the entry and exit sections so that the three properties described next are always satisfied.

The Three Requirements for a Correct Solution

Any correct solution to the critical section problem must satisfy three properties simultaneously. Missing any one of them makes the solution broken in a way that will eventually cause failures.

Mutual Exclusion

Definition: If Thread A is executing in its critical section, no other thread can be executing in its critical section for the same shared resource at the same time.

This is the most obvious requirement. It directly prevents the interleaving that caused the lost update in the counter example. Mutual exclusion means that access to the critical section is serialized - threads take turns, one at a time.

Without mutual exclusion, you get data corruption. Every race condition is a violation of mutual exclusion.

Progress

Definition: If no thread is currently executing in its critical section, and some threads want to enter their critical sections, then only the threads that are not in their remainder sections can participate in the decision of which thread enters next - and this decision cannot be postponed indefinitely.

In simpler terms: if the critical section is free, some thread must be allowed to enter it. The system cannot deadlock at the gate. A solution that prevents all threads from entering when the critical section is available violates progress.

Progress also means that threads in their remainder section (threads that are not currently trying to enter the critical section) should not block threads that are trying to enter. Only the threads competing for access participate in the decision.

This requirement eliminates a class of broken solutions where the mechanism for preventing simultaneous access accidentally prevents all access. For example, a solution that uses a single flag and always resets it to "blocked" would satisfy mutual exclusion but violate progress.

Bounded Waiting

Definition: There exists a bound on the number of times other threads are allowed to enter their critical sections after a thread has made a request to enter its critical section and before that request is granted.

In simpler terms: no thread should wait forever. If Thread A asks to enter, there must be a limit on how many times Thread B and Thread C can jump ahead of it. Bounded waiting prevents starvation.

Without bounded waiting, you can have a solution where mutual exclusion holds and progress holds, but one unlucky thread keeps getting skipped. In the scheduling module, you learned that this is analogous to starvation in priority scheduling - the mechanism works for most threads but is unfair to some.

Important: These three properties - mutual exclusion, progress, and bounded waiting - are the formal requirements that every synchronization primitive in this module must satisfy. When you learn about mutexes, semaphores, condition variables, and monitors, evaluate each one against these three criteria. In interviews, demonstrating that you know these requirements (and can identify when a proposed solution violates one of them) separates you from candidates who only know how to use pthread_mutex_lock().

Why You Cannot Solve This with Just a Variable

The first instinct most people have is to use a simple boolean flag. Set a variable lock = true when a thread enters the critical section, and check the flag before entering. This approach is intuitive, and it is wrong.

Here is the naive attempt:

# Shared variable
lock = False

# Thread A
while lock == True:    # Wait until lock is free
    pass
lock = True            # Claim the lock
# ... critical section ...
lock = False           # Release the lock

# Thread B
while lock == True:    # Wait until lock is free
    pass
lock = True            # Claim the lock
# ... critical section ...
lock = False           # Release the lock

The problem is that the check-and-set operation is not atomic. Between Thread A checking lock == True (and seeing False) and Thread A setting lock = True, Thread B can also check lock == True (and see False) and set lock = True. Now both threads think they have the lock. The race condition has moved from the counter to the lock itself.

This is a fundamental insight: you cannot solve the critical section problem using only regular memory reads and writes, because the solution requires atomic operations and memory reads and writes are not atomic at the granularity you need.

The correct solutions fall into three categories:

Software-only solutions like Peterson's Algorithm - clever arrangements of shared variables and turn-taking that achieve mutual exclusion without hardware support, but only work under specific assumptions (two threads, sequential consistency). These are historically important but not used in practice.

Hardware-supported solutions using atomic instructions like test-and-set, compare-and-swap, or fetch-and-add. These instructions are guaranteed by the CPU to execute atomically - no other thread can interleave between the read and the write. Modern synchronization primitives are built on top of these.

OS-provided solutions like mutexes and semaphores, which combine hardware atomic instructions with OS scheduling to provide efficient, correct, and fair synchronization. These are what you use in practice, and they are the subject of the remaining topics in this module.

Peterson's Algorithm: A Software Solution for Two Threads

Peterson's Algorithm is the classic software solution for mutual exclusion between exactly two threads. It uses two shared variables - a flag array and a turn variable - to achieve all three requirements (mutual exclusion, progress, bounded waiting) without any hardware atomics.

import threading
import time

# Shared state for Peterson's Algorithm
flag = [False, False]  # flag[i] = True means thread i wants to enter
turn = 0               # Whose turn it is to wait

counter = 0            # The shared resource
NUM_ITERATIONS = 100000

def peterson_thread(thread_id):
    global counter, turn
    other = 1 - thread_id
    
    for _ in range(NUM_ITERATIONS):
        # Entry section
        flag[thread_id] = True      # I want to enter
        turn = other                # But I'll let you go first
        while flag[other] and turn == other:
            pass                    # Wait while the other thread wants in AND it's their turn
        
        # Critical section
        counter += 1
        
        # Exit section
        flag[thread_id] = False     # I'm done

t0 = threading.Thread(target=peterson_thread, args=(0,))
t1 = threading.Thread(target=peterson_thread, args=(1,))
t0.start()
t1.start()
t0.join()
t1.join()

print(f"Expected: {2 * NUM_ITERATIONS}")
print(f"Actual:   {counter}")
print(f"Lost:     {2 * NUM_ITERATIONS - counter}")

How it works: Each thread first declares its intent to enter (flag[thread_id] = True), then yields priority to the other thread (turn = other). The while loop waits only if the other thread also wants to enter AND it is the other thread's turn. If only one thread wants to enter, it proceeds immediately. If both want to enter, the one that set turn last is the one that waits - because turn can only hold one value, one thread will always pass the while loop condition.

Why it satisfies all three requirements:

Mutual exclusion: Both threads cannot simultaneously pass the while loop. If both flag[0] and flag[1] are true, turn is either 0 or 1, so exactly one thread is waiting.
Progress: If only one thread wants to enter (the other's flag is false), that thread enters immediately. No unnecessary blocking.
Bounded waiting: After Thread A sets turn = 1 and waits, Thread B can enter at most once. When Thread B exits and tries again, it sets turn = 0, allowing Thread A in. Maximum one skip.

Why Peterson's Algorithm is not used in practice:

The algorithm assumes sequential consistency - that memory operations by one thread become visible to the other thread in the order they were executed. Modern CPUs reorder memory operations for performance. A CPU might execute turn = other before flag[thread_id] = True even though the code says the opposite. This reordering breaks the algorithm.

You can add memory barriers (fence instructions) to enforce ordering, but at that point you are using hardware support anyway. In practice, Peterson's Algorithm is taught for conceptual understanding - it proves that software-only solutions are possible in principle. Real systems use hardware-backed primitives.

Interview: "How would you solve the critical section problem?"

Start by naming the three requirements - mutual exclusion, progress, and bounded waiting. Then explain why naive approaches (like a simple boolean flag) fail because the check-and-set is not atomic. Mention Peterson's Algorithm as the classic software solution for two threads, but note that it relies on sequential consistency and does not work on modern hardware without memory barriers.

Then pivot to practical solutions: "In practice, we use hardware-supported atomic operations like compare-and-swap to build synchronization primitives such as mutexes and semaphores. These combine hardware atomics with OS scheduling to provide efficient, correct, and fair mutual exclusion."

Common follow-up: "What happens if you have more than two threads?"

"Peterson's Algorithm is designed for two threads. For N threads, there are generalizations like the Bakery Algorithm (Lamport, 1974), which assigns each thread a ticket number and serves them in ticket order. But in practice, hardware-backed primitives scale to any number of threads."

Hardware Atomic Instructions

Modern CPUs provide special instructions that read and modify a memory location in a single, uninterruptible operation. These are the building blocks of every practical synchronization mechanism.

Test-and-Set

The test_and_set instruction atomically reads the current value of a boolean variable, sets it to true, and returns the original value - all in one indivisible step. No other core can access that memory location between the read and the write.

// Pseudocode for the hardware instruction
// This executes as a SINGLE atomic operation
bool test_and_set(bool *target) {
    bool old_value = *target;
    *target = true;
    return old_value;
}

// Using test-and-set for mutual exclusion
bool lock = false;

void enter_critical_section() {
    while (test_and_set(&lock)) {
        // Spin - lock was already true, someone else has it
    }
    // Lock was false, we atomically set it to true - we have it
}

void exit_critical_section() {
    lock = false;
}

This solves mutual exclusion because only one thread can see lock change from false to true - the atomicity of test_and_set prevents the race condition that broke the naive flag approach. However, this simple version does not guarantee bounded waiting - a thread can spin indefinitely while others keep grabbing the lock.

Compare-and-Swap (CAS)

The compare_and_swap instruction is more flexible than test-and-set. It atomically compares a memory location to an expected value, and only modifies it if the comparison succeeds. It returns the original value so the caller can tell whether the swap happened.

// Pseudocode for the hardware instruction
// This executes as a SINGLE atomic operation
int compare_and_swap(int *target, int expected, int new_value) {
    int old_value = *target;
    if (old_value == expected) {
        *target = new_value;
    }
    return old_value;
}

// Using CAS for mutual exclusion
int lock = 0;  // 0 = free, 1 = held

void enter_critical_section() {
    while (compare_and_swap(&lock, 0, 1) != 0) {
        // Spin - someone else has the lock
    }
}

void exit_critical_section() {
    lock = 0;
}

CAS is the foundation of lock-free data structures - concurrent data structures that allow multiple threads to operate without any thread holding a lock. Java's AtomicInteger, C++'s std::atomic, and Go's sync/atomic all use CAS underneath.

Tip: In interviews, knowing the name "compare-and-swap" and its behavior is more important than knowing the exact instruction name on any specific architecture. On x86 it is CMPXCHG. On ARM it is a load-linked/store-conditional pair (LDREX/STREX). The concept is the same across all platforms.

The Problem with Spinning

Both test-and-set and compare-and-swap use busy waiting (spinning) - the thread sits in a tight loop checking the lock over and over until it becomes available. This wastes CPU cycles. While a thread spins, it consumes its full CPU time slice doing no useful work.

For short critical sections where the lock is held for microseconds, spinning is acceptable - the thread will grab the lock quickly and the wasted cycles are minimal. This is why the Linux kernel uses spinlocks for short, interrupt-level critical sections.

For longer critical sections, spinning is wasteful. A better approach is to put the waiting thread to sleep and wake it up when the lock is released. This is exactly what mutexes do - and they are the subject of Topic 3 in this module.

The tradeoff is:

Approach	When Lock Is Free	When Lock Is Held	CPU Usage While Waiting	Context Switch Cost
Spinlock (busy wait)	Immediate entry	Wastes CPU cycles	100% on one core	None
Mutex (sleep/wake)	Immediate entry	Thread sleeps	0%	Two switches (sleep + wake)

For interview purposes, the rule is: spin when you expect the wait to be shorter than two context switches. Sleep when you expect the wait to be longer.

Connecting to Real Systems

The critical section problem is not an academic exercise. Every time you use a database, a web server, or a concurrent application, the code underneath is solving this exact problem.

Database transactions use locks (and more sophisticated mechanisms like MVCC) to ensure that two concurrent transactions do not both modify the same row and lose an update. The critical section is the set of rows being modified by a transaction.

Web server request handlers that update shared state (counters, session stores, caches) must protect the update with a lock. Without it, two simultaneous requests can produce the same lost-update bug from the counter example.

File systems use locks to prevent two processes from writing to the same file simultaneously. The flock() and fcntl() system calls in Unix are the OS-level critical section solution for file access.

Concurrent data structures - thread-safe queues, hash maps, and trees - protect their internal state with fine-grained locks or lock-free algorithms built on CAS. Java's ConcurrentHashMap, Python's queue.Queue, and Go's sync.Map all solve the critical section problem internally so that you do not have to.

Understanding the critical section problem tells you what all of these mechanisms are doing and why they are necessary. Without this understanding, synchronization primitives are just black boxes you use because a tutorial told you to. With this understanding, you can reason about correctness, identify race conditions in code reviews, and design systems that are concurrent by design rather than by accident.

Exercise: Starter: Write a Python program that creates two threads incrementing a shared counter 100,000 times each (no locking). Run it 10 times and record the final counter value each time. How far off is it from the expected 200,000? Is the error consistent or random?

Intermediate: Implement Peterson's Algorithm in Python for two threads protecting a shared counter. Run the same test as above. Does it produce the correct result on your machine? (It may not - Python's GIL complicates things, and modern CPUs reorder memory operations. Try it and reason about what you observe.)

Advanced: Implement a test-and-set spinlock in C using GCC's __sync_lock_test_and_set() built-in. Create four threads that each increment a shared counter 1,000,000 times using the spinlock. Measure the total execution time. Then replace the spinlock with a pthread_mutex_t and measure again. Which is faster? Why?

Back to Operating Systems