Operating Systems Cheatsheet

Synchronization

Use this Operating Systems reference while you build software engineering projects, review code for technical interview prep, or polish examples for a software engineer resume.

The Critical Section Problem

A critical section is a code segment that accesses shared resources. The goal: ensure only one process/thread executes its critical section at a time.

Requirements for a valid solution:

Requirement	Meaning
Mutual exclusion	At most one process in its CS at any time
Progress	If no one is in the CS, selection must eventually be made (no deadlock)
Bounded waiting	A process requesting entry will eventually be granted (no starvation)

Peterson's Algorithm (2 processes)

// Shared:
bool flag[2] = {false, false};
int turn;

// Process i (the other is j = 1-i):
flag[i] = true;
turn = j;
while (flag[j] && turn == j)
    ;  // busy wait
/* --- critical section --- */
flag[i] = false;

Satisfies all three requirements for 2 processes. Not directly usable on modern CPUs without memory barriers (reordering).

Hardware Synchronization Primitives

Instruction	Atomicity guarantee	Effect
test-and-set	Read + write	Returns old value, sets target to true
compare-and-swap (CAS)	Compare + conditional write	Swap if current == expected; return old
fetch-and-add	Read + increment	Returns old value, adds operand
load-link / store-conditional (LL/SC)	Conditional pair	SC succeeds only if no intervening write
memory fence / barrier	Ordering	Prevents load/store reordering

test-and-set spinlock

bool lock = false;

void acquire(bool *lock) {
    while (test_and_set(lock))   // atomic: returns old, sets true
        ;  // spin
}
void release(bool *lock) {
    *lock = false;
}

compare-and-swap (x86 `CMPXCHG`)

// atomic: if (*ptr == expected) { *ptr = new; return expected; }
//         else return *ptr;
int cas(int *ptr, int expected, int new_val);

CAS is the foundation of lock-free data structures.

Mutex (Mutual Exclusion Lock)

Sleeping lock — blocked thread is put to sleep (no busy wait).

pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&m);
/* critical section */
pthread_mutex_unlock(&m);

Property	Spinlock	Mutex
Blocked thread	Busy-waits (consumes CPU)	Sleeps (context switch)
Best for	Short CS on multicore	Longer CS or single-core
Overhead	Low (no syscall)	Higher (syscall on contention)

Semaphore

An integer counter with two atomic operations:

wait(S) (P / down): while S ≤ 0: sleep; S--
signal(S) (V / up): S++; wake one waiter

Type	Initial value	Use
Binary semaphore	1	Mutex equivalent
Counting semaphore	N	Control access to N resources

Producer-Consumer with semaphores

sem_t empty, full, mutex;
sem_init(&empty, 0, N);   // N free slots
sem_init(&full,  0, 0);   // 0 items
sem_init(&mutex, 0, 1);   // lock

// Producer:
sem_wait(&empty);          // wait for free slot
sem_wait(&mutex);
buffer[in] = item; in = (in+1) % N;
sem_post(&mutex);
sem_post(&full);           // signal item available

// Consumer:
sem_wait(&full);
sem_wait(&mutex);
item = buffer[out]; out = (out+1) % N;
sem_post(&mutex);
sem_post(&empty);

Condition Variables

Used with a mutex. A thread waits until a condition is true.

pthread_cond_t cv = PTHREAD_COND_INITIALIZER;
pthread_mutex_t mu = PTHREAD_MUTEX_INITIALIZER;

// Waiting thread:
pthread_mutex_lock(&mu);
while (!condition)                   // always in a loop (spurious wakeups)
    pthread_cond_wait(&cv, &mu);     // atomically release mu, sleep
/* use shared resource */
pthread_mutex_unlock(&mu);

// Signaling thread:
pthread_mutex_lock(&mu);
condition = true;
pthread_cond_signal(&cv);            // wake one waiter
// pthread_cond_broadcast(&cv);      // wake ALL waiters
pthread_mutex_unlock(&mu);

Always check condition in a while loop, not if — spurious wakeups exist.

Monitors

A high-level synchronization construct: shared data + procedures + one implicit mutex. Only one thread active inside the monitor at a time. Java synchronized keyword and C++ std::unique_lock + condition_variable approximate monitors.

class BoundedBuffer {
    synchronized void put(int x) throws InterruptedException {
        while (count == N) wait();
        buf[in] = x; in = (in+1)%N; count++;
        notifyAll();
    }
    synchronized int get() throws InterruptedException {
        while (count == 0) wait();
        int x = buf[out]; out = (out+1)%N; count--;
        notifyAll(); return x;
    }
}

Classic Synchronization Problems

Readers-Writers

Multiple readers can read simultaneously; writers need exclusive access.

Variant	Bias	Risk
First readers-writers	Readers preferred	Writer starvation
Second readers-writers	Writers preferred	Reader starvation
Third (fair)	Neither	FIFO with queuing

Dining Philosophers (N=5)

5 philosophers, 5 chopsticks between them.
Each needs LEFT + RIGHT chopstick to eat.

Naive "pick left then right" → deadlock (all pick left simultaneously).

Solutions:

Solution	Mechanism
Resource hierarchy	Always pick lower-numbered chopstick first
Asymmetric	Even philosophers pick L then R; odd pick R then L
Waiter/arbiter	Central semaphore; at most N−1 eat concurrently
Chandy/Misra	Message-passing, no shared memory needed

Memory Ordering and Barriers

Modern CPUs and compilers reorder memory operations for performance. Synchronization requires memory barriers:

Barrier type	Prevents
`mfence` (x86)	All loads/stores reordered across barrier
`lfence`	Load → load, load → store reordering
`sfence`	Store → store reordering
`__atomic_thread_fence(order)`	C11 fence with specified memory order

C11/C++11 memory orders for std::atomic:

Order	Guarantee
`relaxed`	No ordering; atomicity only
`acquire`	No reads/writes after can be reordered before this load
`release`	No reads/writes before can be reordered after this store
`acq_rel`	Acquire + release combined
`seq_cst`	Total order; strongest; default