Semaphore vs Mutex — Trading Engine Priority Inversion

import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

/**
 * Demonstrates a mutex (ReentrantLock) protecting a shared bank account balance.
 * Two threads attempt concurrent withdrawals — the mutex ensures correctness.
 */
public class BankAccountWithMutex {

    private double balance;
    // ReentrantLock is Java's explicit mutex — it has ownership semantics:
    // only the thread that called lock() is allowed to call unlock().
    private final ReentrantLock balanceLock = new ReentrantLock();

    public BankAccountWithMutex(double initialBalance) {
        this.balance = initialBalance;
    }

    /**
     * Withdraws an amount if sufficient funds exist.
     * Returns true if the withdrawal succeeded, false otherwise.
     */
    public boolean withdraw(String threadName, double amount) {
        // lock() blocks until THIS thread owns the lock.
        // No other thread can enter this block simultaneously.
        balanceLock.lock();
        try {
            System.out.printf("[%s] Acquired lock. Balance: %.2f, Requesting: %.2f%n",
                    threadName, balance, amount);

            if (balance < amount) {
                System.out.printf("[%s] Insufficient funds. Withdrawal denied.%n", threadName);
                return false;
            }

            // Simulate some processing time — this is the critical section.
            // Without the mutex, two threads could both pass the balance check
            // and both withdraw, leaving the account negative.
            Thread.sleep(50); // checked exception handled by try-catch below
            balance -= amount;

            System.out.printf("[%s] Withdrew %.2f. New balance: %.2f%n",
                    threadName, amount, balance);
            return true;

        } catch (InterruptedException interruptedException) {
            Thread.currentThread().interrupt(); // restore interrupt flag — NEVER swallow this
            return false;
        } finally {
            // ALWAYS release in a finally block — if an exception is thrown above,
            // the lock MUST still be released or every other thread waits forever.
            balanceLock.unlock();
            System.out.printf("[%s] Released lock.%n", threadName);
        }
    }

    public static void main(String[] args) throws InterruptedException {
        BankAccountWithMutex account = new BankAccountWithMutex(100.00);
        ExecutorService executor = Executors.newFixedThreadPool(2);

        // Both threads attempt to withdraw 80 — only one should succeed.
        executor.submit(() -> account.withdraw("Thread-Alice", 80.00));
        executor.submit(() -> account.withdraw("Thread-Bob",   80.00));

        executor.shutdown();
        executor.awaitTermination(5, TimeUnit.SECONDS);
        System.out.printf("%nFinal balance: %.2f%n", account.balance);
    }
}

import java.util.concurrent.Semaphore;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;
import java.util.ArrayDeque;
import java.util.Queue;

/**
 * A simplified database connection pool backed by a Semaphore.
 * The semaphore acts as a ticket counter: only MAX_CONNECTIONS threads
 * can hold a connection simultaneously. Others wait until one is returned.
 *
 * This is a classic real-world semaphore use case — controlling access
 * to a fixed pool of resources where any thread can "check in" a resource.
 */
public class DatabaseConnectionPool {

    private static final int MAX_CONNECTIONS = 3;

    // Semaphore initialized with the number of available permits (connections).
    // fair=true means threads acquire in arrival order — prevents starvation
    // in production. Costs a bit of throughput due to the CLH queue overhead.
    private final Semaphore connectionPermits = new Semaphore(MAX_CONNECTIONS, true);

    // The actual pool of connection objects (simplified as strings here).
    private final Queue<String> availableConnections = new ArrayDeque<>();

    public DatabaseConnectionPool() {
        for (int i = 1; i <= MAX_CONNECTIONS; i++) {
            availableConnections.add("Connection-" + i);
        }
    }

    /**
     * Borrows a connection from the pool, blocking if none are available.
     * The semaphore enforces that at most MAX_CONNECTIONS threads
     * hold a connection at any time.
     */
    public String borrowConnection(String workerName) throws InterruptedException {
        System.out.printf("[%s] Waiting for a connection... (permits available: %d)%n",
                workerName, connectionPermits.availablePermits());

        // acquire() decrements the permit count by 1.
        // If the count is already 0, this thread parks (blocks) here
        // until another thread calls release().
        connectionPermits.acquire();

        // synchronized only on the Queue access — the semaphore already
        // guarantees at most MAX_CONNECTIONS threads reach here at once.
        String connection;
        synchronized (availableConnections) {
            connection = availableConnections.poll();
        }

        System.out.printf("[%s] Acquired %s (permits remaining: %d)%n",
                workerName, connection, connectionPermits.availablePermits());
        return connection;
    }

    /**
     * Returns a connection to the pool.
     * NOTE: Any thread can call this — the semaphore has no concept of
     * ownership. This is by design for pool scenarios, but means you
     * must ensure callers return the correct connection object.
     */
    public void returnConnection(String workerName, String connection) {
        synchronized (availableConnections) {
            availableConnections.offer(connection);
        }
        // release() increments the permit count and wakes a waiting thread.
        // Crucially: this thread does NOT need to be the one that called acquire().
        connectionPermits.release();
        System.out.printf("[%s] Returned %s (permits now: %d)%n",
                workerName, connection, connectionPermits.availablePermits());
    }

    public static void main(String[] args) throws InterruptedException {
        DatabaseConnectionPool pool = new DatabaseConnectionPool();
        // 5 workers competing for 3 connections — 2 must always wait.
        ExecutorService executor = Executors.newFixedThreadPool(5);

        for (int workerId = 1; workerId <= 5; workerId++) {
            final String workerName = "Worker-" + workerId;
            executor.submit(() -> {
                try {
                    String conn = pool.borrowConnection(workerName);
                    // Simulate using the connection for some work.
                    Thread.sleep(200);
                    pool.returnConnection(workerName, conn);
                } catch (InterruptedException e) {
                    Thread.currentThread().interrupt();
                }
            });
        }

        executor.shutdown();
        executor.awaitTermination(10, TimeUnit.SECONDS);
        System.out.println("\nAll workers done. Pool permits: " + pool.connectionPermits.availablePermits());
    }
}

import java.util.concurrent.locks.ReentrantLock;
import java.util.concurrent.TimeUnit;

/**
 * Demonstrates deadlock caused by inconsistent lock ordering,
 * then shows the fix: always acquire locks in a globally agreed order.
 *
 * Scenario: transferring money between two accounts requires locking both.
 * Naive approach deadlocks. Fixed approach uses consistent lock ordering.
 */
public class DeadlockDemoAndFix {

    static class Account {
        final int id;
        double balance;
        final ReentrantLock lock = new ReentrantLock();

        Account(int id, double balance) {
            this.id = id;
            this.balance = balance;
        }
    }

    /**
     * BROKEN: Lock order depends on argument order.
     * Thread 1 calls transfer(accountA, accountB, 50) -> locks A, then B.
     * Thread 2 calls transfer(accountB, accountA, 30) -> locks B, then A.
     * -> Classic deadlock.
     */
    static void transferBroken(Account from, Account to, double amount)
            throws InterruptedException {
        from.lock.lock();
        System.out.printf("[%s] Locked account %d, waiting for account %d...%n",
                Thread.currentThread().getName(), from.id, to.id);
        Thread.sleep(50); // exaggerate the race window for demo purposes
        to.lock.lock();
        try {
            from.balance -= amount;
            to.balance   += amount;
        } finally {
            to.lock.unlock();
            from.lock.unlock();
        }
    }

    /**
     * FIXED: Lock order is determined by account ID — a global invariant.
     * Regardless of argument order, we always lock the lower-ID account first.
     * Both threads now agree on ordering -> deadlock is impossible.
     *
     * Uses tryLock() with timeout as an additional safety net.
     */
    static boolean transferFixed(Account first, Account second, double amount)
            throws InterruptedException {

        // Enforce consistent global lock ordering by account ID.
        Account lockFirst  = first.id < second.id ? first  : second;
        Account lockSecond = first.id < second.id ? second : first;

        // tryLock with timeout: fail fast rather than wait forever.
        // In production, you'd retry or surface an error to the caller.
        if (!lockFirst.lock.tryLock(1, TimeUnit.SECONDS)) {
            System.out.printf("[%s] Could not acquire lock on account %d — aborting transfer.%n",
                    Thread.currentThread().getName(), lockFirst.id);
            return false;
        }
        try {
            if (!lockSecond.lock.tryLock(1, TimeUnit.SECONDS)) {
                System.out.printf("[%s] Could not acquire lock on account %d — aborting transfer.%n",
                        Thread.currentThread().getName(), lockSecond.id);
                return false;
            }
            try {
                // We now hold BOTH locks safely.
                first.balance  -= amount;
                second.balance += amount;
                System.out.printf("[%s] Transfer of %.2f complete. Balances: A=%.2f, B=%.2f%n",
                        Thread.currentThread().getName(), amount, first.balance, second.balance);
                return true;
            } finally {
                lockSecond.lock.unlock();
            }
        } finally {
            lockFirst.lock.unlock();
        }
    }

    public static void main(String[] args) throws InterruptedException {
        Account accountA = new Account(1, 500.0);
        Account accountB = new Account(2, 300.0);

        System.out.println("=== Testing FIXED transfer (no deadlock) ===");

        Thread thread1 = new Thread(() -> {
            try { transferFixed(accountA, accountB, 50.0); }
            catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        }, "Thread-1");

        Thread thread2 = new Thread(() -> {
            try { transferFixed(accountB, accountA, 30.0); }
            catch (InterruptedException e) { Thread.currentThread().interrupt(); }
        }, "Thread-2");

        thread1.start();
        thread2.start();
        thread1.join();
        thread2.join();

        System.out.printf("Final — Account A: %.2f, Account B: %.2f%n",
                accountA.balance, accountB.balance);
    }
}