• Race Conditions and Memory Ordering
• Mutexes and Condition Variables
• Semaphores (Counting/Binary)
• Monitors
• Read–Copy–Update (RCU)
• Atomics and Lock-Free Basics
• Exercises

• Race condition: outcome depends on interleaving of concurrent operations on shared state.
• Critical section: region that must execute with mutual exclusion.
• Memory models: TSO vs. RCpc vs. C/C++ atomics; happens-before edges via locks and atomics.
• ABA problem: compare-and-swap pitfalls; use version counters or hazard pointers/epochs.

// Simple async mutex for JS environments
class Mutex {
  constructor(){ this.q = []; this.locked = false; }
  lock(){
    return new Promise(res => {
      if (!this.locked){ this.locked = true; res(this._unlock.bind(this)); }
      else this.q.push(res);
    });
  }
  _unlock(){
    if (this.q.length){ const next = this.q.shift(); next(this._unlock.bind(this)); }
    else { this.locked = false; }
  }
}

// Condition variable sketch (pair with mutex)
class CondVar {
  constructor(){ this.waiters = []; }
  wait(m){
    return new Promise(async res => { this.waiters.push(res); const unlock = await m.lock(); unlock(); });
  }
  notifyOne(){ const w = this.waiters.shift(); if (w) w(); }
  notifyAll(){ while(this.waiters.length) this.waiters.shift()(); }
}

• Fairness: FIFO mutexes avoid starvation; ticket locks on SMP.
• Condvars: wait releases the mutex atomically and sleeps; wake-up requires holding the mutex and using a predicate.

// Counting semaphore
class Semaphore {
  constructor(count){ this.count = count; this.q = []; }
  async acquire(){
    if (this.count > 0){ this.count--; return; }
    await new Promise(res => this.q.push(res));
  }
  release(){
    if (this.q.length) this.q.shift()();
    else this.count++;
  }
}

// Classic producer-consumer with bounded buffer uses two semaphores (empty/full) + a mutex

• Binary semaphore: equivalent to a mutex when used for exclusion.
• Counting semaphore: bounds concurrency/permits; perfect for pools.

• Encapsulate shared state with an implicit lock and condition variables.
• Hoare vs Mesa semantics: signal transfers control immediately (Hoare) vs wakes for future scheduling (Mesa; most systems).
• Use while-loops to wait on predicates to handle spurious wakeups and Mesa semantics.

• Idea: Readers run without locks on immutable snapshots; updaters copy, modify, then publish pointer.
• Grace period: wait until all pre-existing readers have quiesced before reclaiming old version.
• APIs (Linux): rcu_read_lock()/unlock(), synchronize_rcu(), call_rcu().
• Use cases: routing tables, inode caches—heavy reads, rare writes.

// RCU-like idea in JS (no true threads): versioned pointer swap
let ptr = {version:0, data: {}};
function rcuRead(){ return ptr; } // readers snapshot the reference
function rcuUpdate(mutator){
  const cur = ptr; const next = {version: cur.version+1, data: structuredClone(cur.data)};
  mutator(next.data);
  ptr = next; // publish
  // defer reclamation of 'cur' until all readers drop (not modeled here)
}

• Primitives: CAS, FAA, exchange; memory orders (relaxed, acquire, release, acq_rel, seq_cst).
• Progress: wait-free > lock-free > obstruction-free.
• Patterns: Treiber stack, Michael–Scott queue; hazards: ABA, reclamation (epoch/HP/RCU).

1. Implement a bounded buffer with a mutex + two semaphores; prove absence of deadlock and starvation.
2. Build a monitor-based readers–writers lock and compare throughput vs. simple mutex under read-heavy workloads.
3. Prototype an RCU-protected map with versioned snapshots and measure read latency vs. RW-lock.