Thread Scheduler

// ── Preemption is invisible and can happen anywhere ──────────────────
class SharedCounter {
    int value = 0;

    // i++ is NOT atomic — it compiles to: read value, add 1, write value
    // Preemption can occur between any of these three steps:
    void increment() {
        value++;   // read → preempt → other thread reads same value → both write same result
    }
}

SharedCounter counter = new SharedCounter();
Thread[] threads = new Thread[10];
for (int i = 0; i < threads.length; i++) {
    threads[i] = new Thread(() -> {
        for (int j = 0; j < 1_000; j++) counter.increment();
    });
    threads[i].start();
}
for (Thread t : threads) t.join();
// Expected: 10,000. Actual: anything from ~5,000 to 10,000
// Preemption between read and write causes lost updates
System.out.println("Lost updates example: " + counter.value);

// Fix: remove the race condition, not the preemption (you can't stop preemption)
AtomicInteger atomicCounter = new AtomicInteger(0);
Thread[] fixedThreads = new Thread[10];
for (int i = 0; i < fixedThreads.length; i++) {
    fixedThreads[i] = new Thread(() -> {
        for (int j = 0; j < 1_000; j++) atomicCounter.incrementAndGet();
    });
    fixedThreads[i].start();
}
for (Thread t : fixedThreads) t.join();
System.out.println("Correct count: " + atomicCounter.get());  // always 10,000

// ── Thread.sleep() — yielding CPU with a time-based wake-up ──────────
// sleep() requests that the OS remove the thread from the run queue for
// AT LEAST the specified duration. "At least" — not exactly.
long before = System.nanoTime();
Thread.sleep(100);   // request: don't schedule me for 100ms
long actualMs = (System.nanoTime() - before) / 1_000_000;
System.out.printf("Requested 100ms sleep, actual: %dms%n", actualMs);
// Typical: 100–115ms on an unloaded system
// Under load or high timer resolution jitter: 100–200ms

// sleep(0) is special: releases the time slice but immediately re-enters run queue
Thread.sleep(0);   // hint to scheduler: reschedule now if anything else wants to run

// ── LockSupport.park() — the low-level primitive behind all Java blocking
import java.util.concurrent.locks.LockSupport;

Thread parker = new Thread(() -> {
    System.out.println("Parker going to sleep via park()");
    LockSupport.park();   // blocks until unpark() is called
    System.out.println("Parker woke up");
}, "parker");

parker.start();
Thread.sleep(200);                          // let parker reach park()
System.out.println(parker.getState());      // WAITING
LockSupport.unpark(parker);                 // wake up parker
parker.join();

// park() with timeout — produces TIMED_WAITING:
Thread timedParker = new Thread(() -> {
    LockSupport.parkNanos(500_000_000L);    // 500ms in nanoseconds
    System.out.println("Timed park complete");
}, "timed-parker");
timedParker.start();
Thread.sleep(50);
System.out.println(timedParker.getState()); // TIMED_WAITING
timedParker.join();

// ── OS scheduler differences — Linux CFS vs Windows ──────────────────
// On Linux (CFS): each thread gets "fair" share of CPU proportional to its weight.
// Time slices are dynamic: fewer runnable threads = longer effective quantum.
// Thread priority maps to CFS weight (with nice values), affects share not absolute time.

// On Windows: fixed quanta (2ms desktop, 15ms server).
// Higher-priority thread preempts lower-priority thread immediately when it becomes RUNNABLE.
// This makes Windows scheduling more deterministic but also more prone to starvation.

// Neither provides real-time guarantees without RTOS configuration.

// ── Thread.sleep() — releases CPU, holds locks ───────────────────────
Object lock = new Object();

Thread sleepWithLock = new Thread(() -> {
    synchronized (lock) {
        System.out.println("Acquired lock, going to sleep");
        try {
            Thread.sleep(2000);   // HOLDS LOCK during sleep — other threads blocked!
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
        System.out.println("Woke from sleep, releasing lock");
    }
}, "sleep-with-lock");

Thread blockedOnLock = new Thread(() -> {
    System.out.println("Waiting for lock...");
    synchronized (lock) {   // BLOCKED for 2 seconds while sleepWithLock sleeps
        System.out.println("Finally got lock");
    }
}, "blocked-on-lock");

sleepWithLock.start();
Thread.sleep(50);
blockedOnLock.start();
blockedOnLock.join();
sleepWithLock.join();

// ── Thread.yield() — courteous spin-wait ─────────────────────────────
AtomicBoolean flag = new AtomicBoolean(false);

Thread spinner = new Thread(() -> {
    // Busy-wait with yield — courteous but still burns CPU
    while (!flag.get()) {
        Thread.yield();   // give other threads a chance to set the flag
    }
    System.out.println("Flag set, spinner done");
}, "spinner");

Thread setter = new Thread(() -> {
    try { Thread.sleep(100); } catch (InterruptedException e) {}
    flag.set(true);
    System.out.println("Flag set by setter");
}, "setter");

spinner.start();
setter.start();
spinner.join();
setter.join();

// Better alternative for most cases: LockSupport.park() / unpark()
// or blocking queues — no CPU burned at all

// ── Object.wait() — releases lock AND suspends ────────────────────────
class ProducerConsumer {
    private final Queue<String> queue = new LinkedList<>();
    private final int maxSize = 5;

    synchronized void produce(String item) throws InterruptedException {
        // WHILE loop — not IF — to handle spurious wakeups:
        while (queue.size() == maxSize) {
            System.out.println("Queue full, producer waiting");
            wait();   // atomically: releases monitor + enters WAITING
        }
        queue.add(item);
        System.out.println("Produced: " + item);
        notifyAll();  // wake consumers
    }

    synchronized String consume() throws InterruptedException {
        // WHILE loop — guards against spurious wakeup on empty queue:
        while (queue.isEmpty()) {
            System.out.println("Queue empty, consumer waiting");
            wait();   // atomically: releases monitor + enters WAITING
        }
        String item = queue.poll();
        System.out.println("Consumed: " + item);
        notifyAll();  // wake producers
        return item;
    }
}

ProducerConsumer pc = new ProducerConsumer();

Thread producer = new Thread(() -> {
    for (int i = 0; i < 10; i++) {
        try { pc.produce("item-" + i); } catch (InterruptedException e) {
            Thread.currentThread().interrupt(); break;
        }
    }
}, "producer");

Thread consumer = new Thread(() -> {
    for (int i = 0; i < 10; i++) {
        try { pc.consume(); } catch (InterruptedException e) {
            Thread.currentThread().interrupt(); break;
        }
    }
}, "consumer");

producer.start(); consumer.start();
producer.join();  consumer.join();

// ── Spurious wakeup — why while, not if ──────────────────────────────
// The Java spec explicitly permits wait() to return without notify() being called.
// The OS may wake a thread for implementation-defined reasons.
// Code that uses if instead of while is incorrect:

synchronized (lock) {
    if (queue.isEmpty()) {
        lock.wait();               // WRONG: spurious wakeup → proceeds on empty queue
    }
    String item = queue.poll();    // NullPointerException if spurious wakeup
}

synchronized (lock) {
    while (queue.isEmpty()) {
        lock.wait();               // CORRECT: re-check condition after every wakeup
    }
    String item = queue.poll();    // guaranteed: queue is non-empty here
}

// ── Non-determinism — different runs, different ordering ─────────────
for (int run = 0; run < 3; run++) {
    Thread a = new Thread(() -> System.out.print("A"), "thread-A");
    Thread b = new Thread(() -> System.out.print("B"), "thread-B");
    Thread c = new Thread(() -> System.out.print("C"), "thread-C");
    a.start(); b.start(); c.start();
    a.join(); b.join(); c.join();
    System.out.println();
}
// Possible output on different runs:
// ABC
// BAC
// ACB
// BAC  ← same as run 2 but different from run 1 and 3
// Neither order is guaranteed; any permutation is legal

// ── Non-determinism is not fixable with sleep() ───────────────────────
// WRONG: using sleep() to "ensure" ordering (broken — just widens the window)
Thread producer = new Thread(() -> { /* set shared state */ });
Thread consumer = new Thread(() -> {
    Thread.sleep(100);   // "wait for producer" — BROKEN on slow machines or GC pause
    /* read shared state */
});
// A 200ms GC pause in producer makes sleep(100) insufficient.
// The only correct fix is synchronization, not timing.

// ── Virtual threads — JVM-scheduled, not OS-scheduled ─────────────────
// Java 21+: virtual threads use Thread.ofVirtual()
Thread vt = Thread.ofVirtual().name("virtual-1").start(() -> {
    System.out.println("Running on carrier: " + Thread.currentThread());
    try { Thread.sleep(100); } catch (InterruptedException e) {}
    // During sleep: virtual thread is unmounted from carrier.
    // Carrier is free to run other virtual threads.
    System.out.println("Resumed on: " + Thread.currentThread());
});
vt.join();

// Millions of virtual threads — impossible with OS threads:
try (var executor = Executors.newVirtualThreadPerTaskExecutor()) {
    List<Future<?>> futures = new ArrayList<>();
    for (int i = 0; i < 100_000; i++) {
        futures.add(executor.submit(() -> {
            Thread.sleep(1000);   // unmounts during sleep — carrier not consumed
            return null;
        }));
    }
    for (Future<?> f : futures) f.get();
}
System.out.println("100,000 virtual threads completed");
// With OS threads: 100,000 × ~1MB stack = ~100GB — impossible
// With virtual threads: stacks in heap, carriers = num CPUs — entirely feasible

// ── What the JVM DOES guarantee for scheduling ────────────────────────
// 1. No indefinite starvation: RUNNABLE threads eventually get CPU
//    (OS starvation prevention — priority boosting on Windows, fair CFS on Linux)

// 2. sleep() minimum duration: Thread.sleep(N) sleeps for AT LEAST N ms
long start = System.nanoTime();
Thread.sleep(50);
long elapsed = (System.nanoTime() - start) / 1_000_000;
System.out.println("Slept at least 50ms: " + (elapsed >= 50));  // always true

// 3. notify() effect: a thread in wait() will eventually be woken by notify()
//    (not guaranteed to be immediate — could be delayed by scheduler)

// 4. Happens-before per JMM: synchronized, volatile, join(), start() establish
//    happens-before and prevent race conditions on correctly synchronized code

// ── What the JVM does NOT guarantee ──────────────────────────────────
// No ordering guarantee: thread A starting before thread B doesn't mean A runs first
// No latency guarantee: notify() might not wake the waiter for milliseconds
// No throughput guarantee: high-priority thread might not get more CPU on Linux
// No real-time guarantee: sleep(1) might sleep for 50ms under load
// No fairness for synchronized: blocked threads reacquire in unspecified order