Cheat SheetsOperating SystemsSynchronization

Synchronization — Cheat Sheet

Operating Systems · 6 topics. Download the PDF or the Instagram carousel and share it.

Cheat Sheet · AiCanCode.org
Synchronization
Operating Systems6 topicsQuick revision reference
1

Race Condition & Critical Section

A race condition occurs when the outcome of concurrent operations depends on the unpredictable interleaving of thread execution, typically when multiple threads access shared mutable state without synchronization.

  • ✓Race condition: outcome depends on thread interleaving — occurs when shared mutable state is accessed without synchronization.
  • ✓Critical section requirements: mutual exclusion, progress, bounded waiting.
  • ✓Java count++ is not atomic — three bytecode instructions (read, add, write) can be interleaved.
  • ✓synchronized provides mutual exclusion using a monitor lock — simple but may cause contention.
  • ✓AtomicInteger uses hardware CAS instruction — lock-free, faster for single-variable updates.
  • ✓LongAdder uses striped counters for better throughput than AtomicLong under high contention.
Java — race condition on shared counter + fix with synchronized and AtomicInteger
// RACE CONDITION — shared counter with two threads
class RaceCounter {
    private int count = 0;

    // NOT thread-safe — count++ is 3 bytecode ops:
    // 1. GETFIELD  (read count into register)
    // 2. ICONST_1 + IADD  (add 1)
    // 3. PUTFIELD  (write back)
    // Thread A can be preempted between steps 1 and 3!
    public void increment() { count++; }
    public int get() { return count; }
}

RaceCounter counter = new RaceCounter();
int THREADS = 100, INCREMENTS_EACH = 1000;

List<Thread> threads = new ArrayList<>();
for (int i = 0; i < THREADS; i++) {
    threads.add(new Thread(() -> {
        for (int j = 0; j < INCREMENTS_EACH; j++) counter.increment();
    }));
}
threads.forEach(Thread::start);
for (Thread t : threads) t.join();

System.out.println("Expected: " + (THREADS * INCREMENTS_EACH));  // 100,000
System.out.println("Actual:   " + counter.get());  // < 100,000 due to race!

// Fix 1: synchronized method — mutex, most readable
synchronized void incrementSafe() { count++; }

// Fix 2: AtomicInteger — lock-free CAS, fastest for single variable
AtomicInteger atomicCount = new AtomicInteger(0);
atomicCount.incrementAndGet();  // atomic compare-and-swap — no race
2

Mutex vs Semaphore

A mutex is a binary lock with ownership used for mutual exclusion; a semaphore is an integer counter without ownership used for signalling and resource counting.

  • ✓Mutex: binary lock with ownership — only the locking thread can unlock; used for mutual exclusion.
  • ✓Semaphore: integer counter without ownership — any thread can signal; used for resource counting and signalling.
  • ✓ReentrantLock is Java's mutex — supports tryLock, timed lock, and fair ordering.
  • ✓Java Semaphore(n) controls access to n identical resources — blocks when permits reach 0.
  • ✓Binary semaphore (init=1) resembles a mutex but lacks ownership — a different thread can signal.
  • ✓Always release semaphores and unlock mutexes in a finally block to prevent deadlock on exception.
Java — ReentrantLock as mutex with tryLock and finally-unlock pattern
// ReentrantLock as mutex — only the locker can unlock
ReentrantLock mutex = new ReentrantLock();

// Thread-safe balance transfer
class BankAccount {
    private final ReentrantLock lock = new ReentrantLock();
    private long balance;

    BankAccount(long initial) { this.balance = initial; }

    public void transfer(BankAccount to, long amount) throws InterruptedException {
        // tryLock with timeout — avoids indefinite blocking
        if (lock.tryLock(100, TimeUnit.MILLISECONDS)) {
            try {
                if (balance >= amount) {
                    balance -= amount;
                    to.deposit(amount);
                    System.out.printf("Transferred %d — balance: %d%n", amount, balance);
                }
            } finally {
                lock.unlock();  // ALWAYS unlock in finally
            }
        } else {
            System.out.println("Could not acquire lock — skipping transfer");
        }
    }

    public synchronized void deposit(long amount) { balance += amount; }
    public long getBalance() { return balance; }
}

BankAccount alice = new BankAccount(1000);
BankAccount bob   = new BankAccount(500);
alice.transfer(bob, 200);
System.out.println("Alice: " + alice.getBalance() + "  Bob: " + bob.getBalance());
3

Monitors & Condition Variables

A monitor combines a mutex and condition variables into a single high-level construct; threads call wait() to release the lock and sleep, and notify() to wake sleeping threads.

  • ✓Monitor = mutex + condition variable + shared data combined in one construct.
  • ✓Java object intrinsic lock: synchronized acquires it; wait() releases it and parks; notify()/notifyAll() wakes.
  • ✓Spurious wakeups are permitted by the Java spec — always use while loop, never if, around wait().
  • ✓notifyAll() wakes all threads from the wait set; notify() wakes one (nondeterministically).
  • ✓ReentrantLock + Condition allows multiple named wait sets — avoids waking unrelated threads.
  • ✓Always acquire lock in try and release in finally to prevent deadlock on exception.
Java — monitor-based bounded buffer with while-loop wait pattern
// Correct monitor pattern: while loop around wait()
class BoundedBuffer<T> {
    private final Queue<T>  buffer   = new LinkedList<>();
    private final int       capacity;

    BoundedBuffer(int capacity) { this.capacity = capacity; }

    // Producer: put item, wait if buffer is full
    public synchronized void put(T item) throws InterruptedException {
        while (buffer.size() == capacity) {  // MUST be while, not if!
            wait();  // releases lock, parks thread — avoids CPU spinning
        }
        buffer.add(item);
        notifyAll();  // wake all waiting consumers (and other producers)
        System.out.println("Produced: " + item + "  buffer=" + buffer.size());
    }

    // Consumer: take item, wait if buffer is empty
    public synchronized T take() throws InterruptedException {
        while (buffer.isEmpty()) {  // MUST be while — spurious wakeup protection
            wait();
        }
        T item = buffer.poll();
        notifyAll();  // wake all waiting producers
        System.out.println("Consumed: " + item + "  buffer=" + buffer.size());
        return item;
    }
}

BoundedBuffer<Integer> buf = new BoundedBuffer<>(3);
Thread producer = new Thread(() -> {
    for (int i = 0; i < 10; i++) {
        try { buf.put(i); } catch (InterruptedException e) { break; }
    }
});
Thread consumer = new Thread(() -> {
    for (int i = 0; i < 10; i++) {
        try { buf.take(); } catch (InterruptedException e) { break; }
    }
});
producer.start(); consumer.start();
producer.join();  consumer.join();
4

Producer-Consumer Problem

The producer-consumer problem models threads that produce and consume items through a shared bounded buffer, requiring synchronization so producers wait when the buffer is full and consumers wait when it is empty.

  • ✓Producer-consumer requires: mutual exclusion on buffer state, blocking when full (producers), blocking when empty (consumers).
  • ✓synchronized + wait/notifyAll: correct but notifyAll() causes thundering herd on every state change.
  • ✓ReentrantLock + two Conditions: targeted signal() — notFull wakes producers, notEmpty wakes consumers.
  • ✓BlockingQueue (ArrayBlockingQueue): idiomatic Java solution — handles all synchronization internally.
  • ✓Poison pill: sentinel value placed by producer to signal consumers to shut down gracefully.
  • ✓SynchronousQueue: zero-capacity queue for direct handoff — each put() blocks until a take() is ready.
Java — producer-consumer with synchronized + wait/notifyAll (Solution 1)
// Producer-Consumer: synchronized + wait/notifyAll
class SharedBuffer {
    private final int[]   buffer;
    private int           count = 0, in = 0, out = 0;

    SharedBuffer(int size) { buffer = new int[size]; }

    public synchronized void produce(int item) throws InterruptedException {
        while (count == buffer.length) wait();   // full → block
        buffer[in] = item;
        in = (in + 1) % buffer.length;
        count++;
        notifyAll();  // wake sleeping consumers
    }

    public synchronized int consume() throws InterruptedException {
        while (count == 0) wait();               // empty → block
        int item = buffer[out];
        out = (out + 1) % buffer.length;
        count--;
        notifyAll();  // wake sleeping producers
        return item;
    }
}

SharedBuffer buf = new SharedBuffer(5);
Thread producer = new Thread(() -> {
    for (int i = 1; i <= 20; i++) {
        try { buf.produce(i); System.out.println("Produced: " + i); }
        catch (InterruptedException e) { break; }
    }
});
Thread consumer = new Thread(() -> {
    for (int i = 1; i <= 20; i++) {
        try { System.out.println("Consumed: " + buf.consume()); }
        catch (InterruptedException e) { break; }
    }
});
producer.start(); consumer.start();
producer.join();  consumer.join();
5

Readers-Writers Problem

The readers-writers problem allows multiple readers to read shared data concurrently but requires exclusive access for writers, balancing throughput and fairness.

  • ✓Multiple readers can hold the read lock concurrently — no blocking between readers.
  • ✓A writer requires exclusive access — blocks all readers and other writers.
  • ✓First readers-writers (readers preferred): writers may starve; second (writers preferred): readers may starve.
  • ✓Java ReentrantReadWriteLock(fair=true) prevents starvation at the cost of some throughput.
  • ✓Lock downgrade (write → read) is supported; lock upgrade (read → write) is NOT and causes deadlock.
  • ✓ReadWriteLock provides significant throughput gains for read-heavy, write-rare workloads (caches, config).
Java — ReentrantReadWriteLock with concurrent reads and exclusive write
// Read-write lock: concurrent reads, exclusive writes
ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock(true); // fair=true
Lock readLock  = rwLock.readLock();
Lock writeLock = rwLock.writeLock();

Map<String, String> sharedConfig = new HashMap<>();

// Multiple readers can proceed simultaneously
Runnable reader = () -> {
    readLock.lock();
    try {
        // All reader threads proceed in parallel — no blocking between readers
        String value = sharedConfig.get("key");
        System.out.printf("[%s] Read: %s%n", Thread.currentThread().getName(), value);
        Thread.sleep(50); // simulate read processing
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    } finally {
        readLock.unlock();  // ALWAYS unlock in finally
    }
};

// Writer gets exclusive access — blocks all readers and writers
Runnable writer = () -> {
    writeLock.lock();
    try {
        sharedConfig.put("key", "value-" + System.currentTimeMillis());
        System.out.printf("[%s] Write completed%n", Thread.currentThread().getName());
        Thread.sleep(20); // simulate write processing
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    } finally {
        writeLock.unlock();
    }
};

// Throughput comparison: 10 readers, 1 writer
ExecutorService exec = Executors.newFixedThreadPool(12);
for (int i = 0; i < 10; i++) exec.submit(reader);
exec.submit(writer);
exec.submit(reader);  // this reader doesn't block other readers
exec.shutdown();
exec.awaitTermination(5, TimeUnit.SECONDS);
6

Dining Philosophers Problem

Five philosophers alternating between thinking and eating share five forks, demonstrating the deadlock problem and its solutions: ordered lock acquisition, arbitrator, and asymmetric strategies.

  • ✓Deadlock requires all four conditions: mutual exclusion, hold and wait, no preemption, circular wait.
  • ✓Dining philosophers deadlock: all pick left fork, wait for right → circular wait.
  • ✓Breaking circular wait by enforcing global lock ordering prevents deadlock.
  • ✓Asymmetric solution: always acquire locks in lower-index-first order across all threads.
  • ✓Java thread dump (jstack) identifies deadlock cycles: "Found one Java-level deadlock."
  • ✓General rule: when acquiring multiple locks, always acquire them in the same global order across all threads.
Java — deadlock-prone dining philosophers (illustrative — do not use in production)
// Deadlock-prone dining philosophers
ReentrantLock[] forks = new ReentrantLock[5];
for (int i = 0; i < 5; i++) forks[i] = new ReentrantLock();

Runnable deadlockPhilosopher(int id) {
    return () -> {
        int left  = id;
        int right = (id + 1) % 5;
        while (true) {
            // DEADLOCK: all pick up left fork, then wait for right
            forks[left].lock();   // pick up left fork
            System.out.println("P" + id + " has left fork " + left);
            try { Thread.sleep(10); } catch (InterruptedException e) { return; }
            // All 5 philosophers reach here simultaneously:
            // P0 waits for fork1 (held by P1)
            // P1 waits for fork2 (held by P2)  → CIRCULAR WAIT = DEADLOCK
            forks[right].lock();
            try {
                System.out.println("P" + id + " eating");
                Thread.sleep(50);
            } catch (InterruptedException e) {
                forks[right].unlock(); return;
            } finally {
                forks[right].unlock();
            }
            forks[left].unlock();
        }
    };
}
// Detect: jstack <pid> → "Found one Java-level deadlock"
// Shows cycle: Thread-0 waiting for lock held by Thread-1 waiting for ... Thread-4 waiting for Thread-0
Learn this free with Aria, your AI tutor → AiCanCode.org/learn/operating-systems