SyntaxPilot
Courses/CS Fundamentals for Placements/Lesson 25
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

CS Fundamentals for Placements · Lesson 25 of 90

Synchronization 2: hardware support and locks

atomic operationtest-and-setcompare-and-swapfetch-and-addspinlockbusy waitingmutex locklock contentionmemory barrier/fenceinstruction reorderinglock-free programmingABA problem

These are the notes for CS Fundamentals for Placements, episode 25. In episode 24 our simple lock variable failed, because checking the lock and taking it were two separate steps, and another thread could run in between. Today we ask the hardware for help. You will meet atomic operations and fetch-and-add, build a spinlock from test-and-set, measure live how a spinlock wastes the CPU (busy waiting), replace it with a mutex lock, see lock contention slow four threads down, update shared data with no lock at all using compare-and-swap (lock-free programming), and learn two traps: the ABA problem and instruction reordering, which memory barriers (fences) prevent. Every term is explained in plain words the first time it appears, and there is a full glossary at the end.

All program outputs below are real: every C program was compiled with gcc 13.3 -O2 -Wno-unused-result (the SyntaxPilot compiler's flags) and run on Linux x86-64 with 2 CPUs on 3 November 2026, three runs each. Where the output changes from run to run, the notes say so and show one run.

Refresher: a thread is a flow of execution inside a process; threads of one process share global variables. pthread_create starts a thread running a function and pthread_join waits for it to finish (episode 20). A critical section is code that touches shared data, and a correct solution needs mutual exclusion (at most one thread inside), progress and bounded waiting (episode 24).

The six problems

Problem What it teaches
Check and set in one step Atomic operations, fetch-and-add
A lock for a whole section Test-and-set, spinlock
Waiting burns the CPU Busy waiting, mutex lock, spinlock vs mutex
Everyone wants the lock Lock contention, and how to reduce it
Update without a lock Compare-and-swap, lock-free programming
Same value, different thing ABA problem, instruction reordering, memory barriers

Problem 1: check and set in one step (atomic operations)

Real-life example: the bank's token machine. You press one button and get token 47. Inside, the machine reads the last number, adds one and prints it, but to you it is one press: nobody can step in halfway. If two people press together, one gets 47 and the other 48, never two 47s.

An atomic operation is an operation that happens completely or not at all, and no other thread can see it half-done or run in the middle of it. ("Atomic" comes from the Greek for uncuttable.) Example: an atomic increment of a counter.

Modern CPUs provide atomic instructions. Fetch-and-add atomically reads a memory location, adds a number to it and writes it back, and returns the old value (like the token telling you your number). In C (since the C11 standard), the header <stdatomic.h> gives atomic types such as atomic_int and functions such as atomic_fetch_add.

#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>

atomic_int counter = 0;             // an atomic integer

void *work(void *arg) {
    for (int i = 0; i < 10000000; i++)
        atomic_fetch_add(&counter, 1);  // one unbreakable step
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL);
    pthread_join(b, NULL);
    printf("expected 20000000, got %d\n", counter);
    return 0;
}

Output (every run):

expected 20000000, got 20000000

Compare with episode 24, where plain counter++ lost millions of updates: here the CPU does load, add and store as one indivisible step. We checked the assembly gcc produces (gcc -O2 -S): on x86-64 the loop body becomes the single instruction lock addl $1, counter(%rip) (gcc uses lock xadd instead when the returned old value is used). The lock prefix makes the core hold that memory location for the whole read-modify-write.

Problem 2: a lock for a whole section (test-and-set and the spinlock)

One atomic step is not always enough. Moving 1 rupee from account A to account B is two updates that must happen together:

a_acc -= 1;
b_acc += 1;     // both, or neither!

Even if each line were atomic, a thread looking between them would see one rupee missing. We still need a lock around the whole critical section, and the lock itself must be taken in one atomic step.

Real-life example: one key on a hook at hotel reception. You reach and grab. In that one movement you learn whether the key was there, and if it was, it is now in your hand. Nobody can take it between your look and your grab.

Test-and-set is an atomic instruction that sets a memory location to 1 (true) and returns its old value:

// what test_and_set(&lock) does, as ONE atomic step:
old = lock;
lock = 1;
return old;
  • Old value 0: the lock was free, and you have just taken it. Enter.
  • Old value 1: someone holds it. Your set changed nothing (it was already 1). Try again.

A spinlock is a lock where a waiting thread keeps trying in a tight loop ("spins") until it gets the lock. In C, the simplest atomic type is atomic_flag, which is either clear (free) or set, with atomic_flag_test_and_set and atomic_flag_clear:

#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>

atomic_flag lock = ATOMIC_FLAG_INIT;   // clear = free
long a_acc = 1000000, b_acc = 0;       // two bank accounts

void *transfer(void *arg) {
    for (int i = 0; i < 500000; i++) {
        while (atomic_flag_test_and_set(&lock)) { }  // spin
        a_acc -= 1;                    // critical section:
        b_acc += 1;                    //   move 1 rupee
        atomic_flag_clear(&lock);      // release
    }
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, transfer, NULL);
    pthread_create(&t2, NULL, transfer, NULL);
    pthread_join(t1, NULL); pthread_join(t2, NULL);
    printf("A = %ld, B = %ld, total = %ld\n", a_acc, b_acc, a_acc + b_acc);
    return 0;
}

Output (every run):

A = 0, B = 1000000, total = 1000000

Not a rupee lost. (10 lakh = 1,000,000.) A working lock, built on one hardware instruction: in the assembly, gcc turns atomic_flag_test_and_set into xchgb (an x86 exchange, which is always atomic on memory), and the CAS loop of Problem 5 into lock cmpxchgl.

Homework solution: a spinlock from compare-and-swap

Any atomic read-modify-write instruction can build a lock. With compare-and-swap (Problem 5): "if the lock is 0, make it 1".

#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>

atomic_int lock = 0;                   // 0 = free, 1 = taken
long a_acc = 1000000, b_acc = 0;

void spin_lock(atomic_int *l) {
    int expected = 0;
    while (!atomic_compare_exchange_weak(l, &expected, 1))
        expected = 0;                  // CAS wrote the 1 it saw: reset
}
void spin_unlock(atomic_int *l) { atomic_store(l, 0); }

void *transfer(void *arg) {
    for (int i = 0; i < 500000; i++) {
        spin_lock(&lock);
        a_acc -= 1; b_acc += 1;
        spin_unlock(&lock);
    }
    return NULL;
}

int main(void) {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, transfer, NULL);
    pthread_create(&t2, NULL, transfer, NULL);
    pthread_join(t1, NULL); pthread_join(t2, NULL);
    printf("A = %ld, B = %ld, total = %ld\n", a_acc, b_acc, a_acc + b_acc);
    return 0;
}

Output (every run):

A = 0, B = 1000000, total = 1000000

On failure, atomic_compare_exchange_weak writes the value it actually found (1) into expected, so we reset it to 0 before trying again.

What happens with no lock at all

Remove the two lock lines from the transfer program (and make the accounts volatile so the compiler really reads memory every time). The total is no longer guaranteed. Three real runs:

A = 0, B = 1000000, total = 1000000
A = 0, B = 500000, total = 500000
A = 0, B = 500000, total = 500000

Half a million rupees vanished in two of the three runs, and the first run was correct, which is exactly why race conditions slip through testing.

Problem 3: waiting burns the CPU (busy waiting and the mutex)

Real-life example: calling the plumber. He says "I'll come when I'm free". You call: "Free yet?" No. Call again. And again. Your phone dies and your day is gone. Better: "Call me when you're free", and get on with your day.

Busy waiting means waiting by repeatedly checking a condition in a loop, keeping the CPU busy while doing nothing useful. A spinlock busy-waits. Measured live: main holds the spinlock for 2 seconds, and the waiter reports how much CPU time it used, using clock_gettime(CLOCK_THREAD_CPUTIME_ID, ...), the CPU clock of the calling thread:

#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>
#include <unistd.h>
#include <time.h>
atomic_flag lock = ATOMIC_FLAG_INIT;

double cpu_used(void) {               // CPU seconds this thread used
    struct timespec t; clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}
void *waiter(void *arg) {
    while (atomic_flag_test_and_set(&lock)) { }   // spin...
    printf("waiter got the lock, CPU used: %.2f s\n", cpu_used());
    return NULL;
}
int main(void) {
    pthread_t w;
    atomic_flag_test_and_set(&lock);   // main takes the lock
    pthread_create(&w, NULL, waiter, NULL);
    sleep(2);                          // and holds it for 2 seconds
    atomic_flag_clear(&lock);
    pthread_join(w, NULL);
}

Output (one run; between 1.85 and 1.96 s in our runs):

waiter got the lock, CPU used: 1.89 s

Almost the full 2 seconds of a CPU core spent asking "is it free yet?".

The mutex lock

A mutex (short for mutual exclusion lock) is a lock provided by the operating system or thread library that puts a waiting thread to sleep instead of spinning:

  • lock(): if the mutex is free, take it (internally, with an atomic instruction). If it is held, the thread is blocked: the OS takes it off the CPU, and it uses no CPU time while waiting.
  • unlock(): release the mutex, and the OS wakes up a thread that was sleeping on it.
  • A mutex has an owner: the thread that locked it is the one that should unlock it.

In C with POSIX threads (pthreads):

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;   // a ready-to-use mutex
pthread_mutex_lock(&m);
    // critical section
pthread_mutex_unlock(&m);

The same experiment with a mutex:

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

double cpu_used(void) {               // CPU seconds this thread used
    struct timespec t; clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t);
    return t.tv_sec + t.tv_nsec / 1e9;
}
void *waiter(void *arg) {
    pthread_mutex_lock(&lock);        // sleep until it's free
    printf("waiter got the lock, CPU used: %.2f s\n", cpu_used());
    pthread_mutex_unlock(&lock);
    return NULL;
}
int main(void) {
    pthread_t w;
    pthread_mutex_lock(&lock);        // main takes the lock
    pthread_create(&w, NULL, waiter, NULL);
    sleep(2);                         // and holds it for 2 seconds
    pthread_mutex_unlock(&lock);
    pthread_join(w, NULL);
}

Output (every run):

waiter got the lock, CPU used: 0.00 s

Same 2-second wait, zero CPU wasted.

Common mistake: passing the mutex instead of its address

pthread_mutex_lock(lock);         // forgot the &

The real gcc error:

main.c: In function 'waiter':
main.c:12:24: error: incompatible type for argument 1 of 'pthread_mutex_lock'
   12 |     pthread_mutex_lock(lock);         // sleep until it's free
      |                        ^~~~
      |                        |
      |                        pthread_mutex_t
note: expected 'pthread_mutex_t *' but argument is of type 'pthread_mutex_t'

The functions need a pointer to the mutex (its address, &lock), so they can change the real lock rather than a copy.

Spinlock or mutex?

Spinlock Mutex
How it waits loops, checking (busy waiting) sleeps (blocked)
CPU while waiting burned free for other work
Cost to take after waiting none extra a sleep and a wake-up (a system call, context switches)
Best for very short waits on multicore machines; inside OS kernels longer or unknown waits; normal application code
On a single core bad: the holder can't run while you spin, until the time slice ends fine

Many real mutexes are hybrids: they spin briefly, then sleep.

Problem 4: everyone wants the lock (lock contention)

Real-life example: one billing counter and forty shoppers. The queue is the bottleneck, and it is even worse if each shopper re-joins the queue for every single item. The fix: fill your cart, then bill once.

Lock contention is when many threads want the same lock at the same time, so they spend their time waiting for each other instead of working. Heavy contention can make four threads slower than one. Live: four threads each add 2,000,000 to a shared total, first locking for every single addition, then counting privately and locking once:

#include <stdio.h>
#include <pthread.h>
#include <time.h>
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
long total = 0; int batch;          // batch: lock once per item, or once
double now(void) { struct timespec t; clock_gettime(CLOCK_MONOTONIC, &t);
                   return t.tv_sec + t.tv_nsec / 1e9; }
void *work(void *arg) {
    long mine = 0; for (int i = 0; i < 2000000; i++) {
        if (batch) { mine++; continue; }  // count privately
        pthread_mutex_lock(&m); total++; pthread_mutex_unlock(&m);
    }
    pthread_mutex_lock(&m); total += mine; pthread_mutex_unlock(&m);
    return NULL;
}
int main(void) {
    for (batch = 0; batch <= 1; batch++) {
        pthread_t t[4]; total = 0; double s = now();
        for (int i = 0; i < 4; i++) pthread_create(&t[i], NULL, work, NULL);
        for (int i = 0; i < 4; i++) pthread_join(t[i], NULL);
        printf("%s: total %ld in %.3f s\n", batch ? "lock once" :
               "lock per item", total, now() - s);
    }
}

Output (one run; the times vary):

lock per item: total 8000000 in 0.204 s
lock once: total 8000000 in 0.003 s

Both totals are correct; the lock-per-item version is many times slower because the threads were mostly queueing for the lock. (At -O2 the compiler also shortens the private counting loop, which exaggerates the gap, but the lesson holds.) Ways to reduce contention:

  • Hold locks briefly: do slow work (I/O, computation) outside the lock.
  • Lock rarely: batch updates, as above.
  • Use finer-grained locks: one lock per bank account instead of one for the whole bank.
  • Use atomic operations or per-thread data when one counter is all you need.

Problem 5: update without a lock (compare-and-swap)

Real-life example: changing a price tag. A shop assistant reads ₹100 and plans ₹110. She says: "change it to ₹110 only if it still says ₹100". If a colleague changed it to ₹105 in between, her change is refused, so she reads ₹105 and tries again (₹115).

Compare-and-swap (CAS) is an atomic instruction that compares a memory location with an expected value and, only if they are equal, replaces it with a new value; it reports whether it succeeded:

// what CAS(&x, expected, new) does, as ONE atomic step:
if (x == expected) { x = new; return true; }
else               { return false; }

Compare-and-swap "has been an integral part of the IBM 370 (and all successor) architectures since 1970"; on x86 processors (since the 80486) it is the CMPXCHG instruction, used with the LOCK prefix on multiprocessor machines. In C it is atomic_compare_exchange_weak / _strong. On failure, the C function also copies the value it found into your expected variable, ready for the retry. (_weak may occasionally fail even when the values match, which is fine inside a retry loop.)

The usual pattern is a CAS loop: read, compute the new value, CAS, and retry if someone was faster:

#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>

atomic_int counter = 0;
atomic_long retries = 0;            // how often CAS said "changed!"

void *work(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        int old = atomic_load(&counter);         // 1. read
        while (!atomic_compare_exchange_weak(&counter, &old, old + 1))
            atomic_fetch_add(&retries, 1);       // 2. lost: retry
    }                                  // (on failure, old = new value)
    return NULL;
}

int main(void) {
    pthread_t a, b;
    pthread_create(&a, NULL, work, NULL);
    pthread_create(&b, NULL, work, NULL);
    pthread_join(a, NULL); pthread_join(b, NULL);
    printf("counter = %d, retries = %ld\n", counter, retries);
}

Output (one run; the retries change every run, from 3 to over 30,000 in our runs):

counter = 2000000, retries = 30332

Lock-free programming

Lock-free programming means building shared data structures from atomic instructions like CAS, with no locks, such that at any moment at least one thread is making progress.

Locks Lock-free
A thread paused mid-update everyone waiting for its lock waits others still finish
Deadlock from locks possible impossible (no locks)
Difficulty moderate very hard beyond simple counters
Typical use almost everything queues, stacks, counters inside OSes, databases, runtimes

Problem 6: same value, different thing (ABA and memory barriers)

The ABA problem

Real-life example: your glass of water. It is half full; you look away. A friend drinks it all and refills it to exactly half from a different bottle. You look back: "unchanged!" But it isn't the same water.

The ABA problem: CAS compares only values. If a location changes from A to B and back to A while a thread wasn't looking, the thread's CAS succeeds as if nothing happened, even though the A now means something different (for example, a memory node that was freed and reused).

Classic case, a lock-free stack (top → A → B → C):

  1. T1 wants to pop: reads top = A, A->next = B. T1 is paused.
  2. T2 pops A, pops B, and pushes A back (the same node, reused). Stack: top → A → C.
  3. T1 resumes: CAS(top, A, B) succeeds, because top is A again. Now top → B, but B was already removed. The stack is corrupted.

Fix: pair the value with a version counter (a "tag") that increases on every update, and CAS the pair. (A, version 7) no longer equals (A, version 9), so the stale CAS fails and T1 retries. Other fixes: memory reclamation schemes (hazard pointers, epochs) that never reuse a node while someone may still be looking at it.

Instruction reordering and memory barriers

Instruction reordering: to run faster, CPUs and compilers may change the order of independent memory reads and writes. Episode 24's Peterson's solution lost updates because a write sat in a store buffer while a later read ran.

A memory barrier, or memory fence, is an instruction that forces every memory operation before it to finish before any operation after it: nothing moves across it. gcc's __sync_synchronize() is a full fence; C11 has atomic_thread_fence.

Good news: C11 atomic operations (with their default, sequentially consistent ordering) and pthread_mutex_lock/unlock already include the fences they need. That is why the test-and-set lock above worked: without them, a write from inside the critical section could be moved to after the unlock and become visible after another thread has already entered.

The whole chain

Problem Invention One line
Check and set were two steps Atomic operation, fetch-and-add One step nobody can split
A whole section needs protection Test-and-set, spinlock Grab the key, or spin
Spinning wastes the CPU Mutex Sleep until woken
Everyone wants one lock Less contention Lock rarely and briefly
Locks can block everyone CAS, lock-free code Change it only if unchanged
Values come back; CPUs reorder Version counters, fences Compare history, keep order

Common mistakes

Mistake What you see Why Fix
pthread_mutex_lock(m) without & error: incompatible type for argument 1 of 'pthread_mutex_lock' The function needs the mutex's address pthread_mutex_lock(&m)
Thinking two atomic updates make an atomic transfer totals wrong when observed in between Each step is atomic, not the pair One lock around both
Spinlock for long waits waiter CPU used ≈ the whole wait (1.89 s) Busy waiting burns a core A mutex
Spinlock on a single-core machine the program crawls The holder can't run while you spin A mutex (or disable preemption in a kernel)
Locking for every tiny update lock per item ... 0.204 s vs 0.003 s Lock contention Batch, hold briefly, finer locks
Unlocking a mutex you don't own undefined behaviour (or EPERM with an error-checking mutex) A mutex has an owner Unlock in the thread that locked
Trusting CAS when values can come back CAS succeeds on a reused node ABA Version counter / safe reclamation
Plain variables as flags between threads spin loop never ends at -O2, or reordering bugs No atomicity, no fences atomic_* types or a mutex

Mini project: build and measure three locks

Write one program that moves money between two accounts with 4 threads, using (1) an atomic_flag spinlock, (2) a CAS spinlock, (3) a pthread mutex. For each, print the total (must equal the starting money), the wall time, and the CPU time of the whole process (clock() / CLOCKS_PER_SEC). Then put a usleep(100) inside the critical section and run again: watch the spinlocks' CPU time explode while the mutex's stays low.

Practice

1. The flag starts clear. What does atomic_flag_test_and_set return on the first and second call?

Solution

0, then 1. It sets the flag and returns the old value. Real output of the quiz program: 0 1.

2. Build a spinlock from compare-and-swap instead of test-and-set.

Solution

See "Homework solution: a spinlock from compare-and-swap" above: while (!CAS(&lock, 0, 1)) expected = 0; to lock, atomic_store(&lock, 0) to unlock.

3. Why is a spinlock a bad idea on a single-core CPU?

Solution

While the waiter spins, the lock holder isn't running (there is only one core), so it can't release the lock. The waiter burns its whole time slice for nothing; only a context switch lets the holder continue. A blocking mutex hands the CPU to the holder immediately.

4. Fetch-and-add returns the old value. Two threads call fetch_add(&x, 1) once each, with x = 5. What can they get back, and what is x afterwards?

Solution

One gets 5 and the other 6 (in either order); x ends at 7. They can never both get 5.

5. Trace ABA on a 3-node stack with version numbers.

Solution

Top = (A, v1). T1 reads (A, v1), next B, then pauses. T2 pops A → (B, v2), pops B → (C, v3), pushes A → (A, v4). T1's CAS expects (A, v1) but finds (A, v4): it fails, T1 re-reads (A, v4) with next C and pops correctly → (C, v5).

6. Name two problems of locks that lock-free code avoids, and two costs it adds.

Solution

Avoids: everyone blocking when a lock holder is paused, and deadlocks caused by locks. Adds: complexity, retry loops that waste work under heavy contention, and problems like ABA and memory reclamation.

Quick quiz

atomic_flag f = ATOMIC_FLAG_INIT;   // clear
int a = atomic_flag_test_and_set(&f);
int b = atomic_flag_test_and_set(&f);
printf("%d %d", a, b);

A. 0 0 B. 0 1 C. 1 1 D. 1 0

Answer

B. 0 1. Test-and-set returns the old value: the first call finds the flag clear and sets it; the second finds it already set. That is exactly how a second thread knows to wait.

Interview questions

  1. What is an atomic operation? One that happens completely or not at all; no thread sees it half-done.
  2. Explain test-and-set and how a spinlock uses it. Atomically set to 1 and return the old value; loop until the old value is 0.
  3. What is compare-and-swap? Atomically: if *p == expected, set *p = new and return success; else fail.
  4. Difference between test-and-set and CAS? TAS always writes 1; CAS writes only if the value matches, and can implement any read-modify-write in a loop.
  5. What is fetch-and-add used for? Counters, ticket numbers (ticket locks), indexes into shared arrays.
  6. What is busy waiting? When is it acceptable? Looping until a condition holds; acceptable for very short waits on multicore systems (kernel spinlocks).
  7. Spinlock vs mutex? Spin vs sleep; see the table above.
  8. Mutex vs a plain lock variable? The mutex is taken atomically, blocks waiters, has an owner, and includes memory barriers.
  9. What is lock contention and how do you reduce it? Many threads wanting one lock; hold briefly, lock rarely, finer-grained locks, atomics.
  10. What is lock-free programming? Using atomic instructions instead of locks so some thread always progresses.
  11. What is the ABA problem? How is it solved? CAS can't see A→B→A changes; version counters / tagged pointers, safe memory reclamation.
  12. What is a memory barrier, and why do locks need one? It stops reordering across it; without it, critical-section writes could leak past the unlock.

Glossary

Term Meaning in plain words Example
Atomic operation Happens completely or not at all; nobody sees or interrupts it halfway the bank token machine
<stdatomic.h> C11 header with atomic types and operations atomic_int counter
atomic_int An integer whose operations are atomic the fixed counter
Fetch-and-add Atomically add to a value and return the old value atomic_fetch_add(&counter, 1)
lock prefix (x86) Makes one instruction's read-modify-write atomic across cores lock addl, lock cmpxchgl
Test-and-set Atomically set to 1 and return the old value grabbing the key off the hook
atomic_flag Simplest C atomic type: clear or set the spinlock's flag
Spinlock A lock whose waiters loop until it's free while (test_and_set(&lock)) { }
Busy waiting Waiting by repeatedly checking, burning CPU calling the plumber every 5 seconds
CPU time Time a thread actually ran on a CPU (not wall-clock time) 1.89 s while spinning
clock_gettime POSIX function to read a clock, e.g. a thread's CPU clock CLOCK_THREAD_CPUTIME_ID
Mutex lock A lock whose waiters sleep; has an owner pthread_mutex_lock(&m)
Blocked / sleeping Off the CPU, waiting for an event, using no CPU the mutex waiter
PTHREAD_MUTEX_INITIALIZER Macro that makes a ready-to-use mutex pthread_mutex_t m = ...
Pointer / address (&) Where a variable lives in memory &lock
Lock contention Many threads competing for the same lock one billing counter, 40 shoppers
Fine-grained locking Many small locks instead of one big one a lock per bank account
Compare-and-swap (CAS) Atomically: replace a value only if it equals the expected one the price tag rule
CMPXCHG The x86 compare-and-exchange (CAS) instruction used with LOCK
CAS loop Read, compute, CAS, retry on failure the lock-free counter
Retry Trying the CAS again after another thread changed the value retries in the demo
Lock-free programming No locks; some thread always makes progress lock-free stacks and queues
ABA problem A value changes A→B→A and CAS wrongly sees "unchanged" the refilled glass of water
Version counter (tag) A number bumped on every update, compared with the value (A, v7) ≠ (A, v9)
Instruction reordering CPU/compiler running independent memory steps out of order Peterson's lost updates
Store buffer A core's queue of writes not yet visible to others why reordering happens
Memory barrier / fence Nothing moves across it; earlier memory steps finish first __sync_synchronize(), atomic_thread_fence
Sequentially consistent Operations appear in program order to all threads; C11 atomics' default atomic_fetch_add
Owner (of a mutex) The thread that locked it, which should unlock it —

Summary

  • An atomic operation happens completely or not at all; fetch-and-add fixes the lost counter in one instruction.
  • Test-and-set sets a flag and returns its old value; looping on it gives a spinlock, which protects a whole critical section.
  • Spinlocks busy-wait and burn CPU (measured: almost the whole wait); a mutex puts the waiter to sleep (0.00 s). Spin only for tiny waits on multicore machines.
  • Lock contention slows threads down: hold locks briefly and rarely, and use finer-grained locks.
  • Compare-and-swap updates a value only if it is unchanged; CAS loops give lock-free code, which must watch for the ABA problem (fix: version counters).
  • CPUs and compilers reorder memory operations; memory barriers stop that, and atomics and mutexes include them.

Next episode: Semaphores and monitors: counting and binary semaphores, wait and signal, monitors and condition variables.