What is a race condition, and what is the critical section problem?

Imagine a shared bank account with ₹1,000. You and your sibling both open the banking app at the same moment. Both apps read the balance as ₹1,000. You withdraw ₹200 and the app writes ₹800. Your sibling withdraws ₹300 and their app writes ₹700. The bank now shows ₹700, but ₹500 left the account. Your ₹200 withdrawal has been lost.

The problem is not the arithmetic. It is that two people were in the middle of "read, change, write" at the same time. That is a race condition, and the "read, change, write" part is the critical section.

Two threads each add 1 to a shared counter, 1,00,000 times:

int count = 0;

void *worker(void *arg) {
    for (int i = 0; i < 100000; i++) {
        count++;          // critical section
    }
    return NULL;
}

You expect 200000 at the end, but you often get less, and a different number on each run. count++ is not one step. The CPU does three:

1. load count into a register
2. add 1 to the register
3. store the register back into count

One bad interleaving:

Thread A: load  (reads 5)
Thread B: load  (reads 5)
Thread A: add, store  -> count = 6
Thread B: add, store  -> count = 6   (one increment lost)

The fix is to make the three steps happen as one, using a lock:

pthread_mutex_lock(&m);
count++;
pthread_mutex_unlock(&m);

Or an atomic operation such as atomic_fetch_add(&count, 1) from <stdatomic.h>.

Code around a critical section has four parts: the entry section (ask permission), the critical section, the exit section (give it back) and the remainder section. Any correct solution must satisfy three conditions:

1. Mutual exclusion: at most one thread is inside the critical section at a time.
2. Progress: if nobody is inside and some threads want to enter, one of them must be chosen soon; threads in their remainder section cannot block the decision.
3. Bounded waiting: after a thread asks to enter, there is a limit on how many times others can go ahead of it, so nobody waits forever.

Solutions come in layers. Peterson's solution is a classic software-only answer for two threads (it needs memory barriers on modern CPUs to work). Hardware provides atomic instructions like test-and-set and compare-and-swap. On top of those, the OS and libraries build mutexes, semaphores and monitors, which are what you use in real code.

• Two users booking the last seat on a train: the check "is the seat free?" and the update "mark it booked" must happen together, usually inside a database transaction or with SELECT ... FOR UPDATE.
• Web servers updating a shared in-memory cache from many threads.
• Inventory counts in e-commerce during a flash sale.

• Assuming a one-line statement like count++ or x += 1 is atomic.
• Protecting the write but not the read that decided it, for example checking a balance outside the lock and updating inside it.
• Making the critical section too large, which kills parallelism, or using different locks for the same data.
• Testing a few times, seeing the right answer, and assuming there is no race. Races depend on timing and may appear only under load.

• Explain Peterson's solution. Why does it need memory barriers on modern CPUs?
• What is compare-and-swap, and how are lock-free counters built with it?
• What is the difference between a race condition and a data race?
• How do databases prevent two users from booking the same seat?