// Strategy: Replace mutual exclusion with lock-free atomics.
// If no thread ever "holds" a lock, deadlock is structurally impossible.

#include <stdatomic.h>
atomic_int counter = 0;

void increment() {
    // atomic_fetch_add uses a hardware CAS loop internally --
    // no mutex, so no possibility of hold-and-wait
    atomic_fetch_add(&counter, 1);
}

// Strategy: Acquire ALL locks at once, or none.
// A thread never "holds" one lock while "waiting" for another,
// so the hold-and-wait condition is broken by construction.

typedef struct {
    pthread_mutex_t mutex;
    int id;
} resource_t;

bool acquire_all(resource_t *resources[], int count) {
    for (int i = 0; i < count; i++) {
        if (pthread_mutex_trylock(&resources[i]->mutex) != 0) {
            // Failed on lock i -- release everything we already hold
            // to avoid holding some locks while waiting for others
            for (int j = 0; j < i; j++) {
                pthread_mutex_unlock(&resources[j]->mutex);
            }
            return false;  // Caller should back off and retry
        }
    }
    return true;  // Successfully acquired all locks atomically
}

// Strategy: If you cannot get the next resource, voluntarily release
// what you already hold. This is "self-preemption" -- the thread
// gives up its own resources rather than waiting forever.

bool acquire_with_preemption(pthread_mutex_t *m1, pthread_mutex_t *m2) {
    while (1) {
        pthread_mutex_lock(m1);
        
        if (pthread_mutex_trylock(m2) == 0) {
            return true;  // Got both locks
        }
        
        // Cannot get m2 -- release m1 to break the "no preemption" condition.
        // Without this release, we would hold m1 and block on m2 = classic deadlock setup.
        pthread_mutex_unlock(m1);
        
        // Randomized backoff prevents livelock: without it, two threads
        // can release and retry in perfect lockstep forever
        usleep(random() % 1000);
    }
}

// Strategy: Always acquire locks in the SAME global order.
// If every thread acquires Lock A before Lock B, no thread can ever
// hold B while waiting for A -- the circular wait condition is impossible.

// Approach 1: Order by memory address (works when locks have no natural ordering)
void safe_lock_two(pthread_mutex_t *a, pthread_mutex_t *b) {
    // Lower address first -- deterministic, no extra metadata needed
    if (a < b) {
        pthread_mutex_lock(a);
        pthread_mutex_lock(b);
    } else {
        pthread_mutex_lock(b);
        pthread_mutex_lock(a);
    }
}

// Approach 2: Explicit priority levels (better for complex systems)
#define LOCK_PRIORITY_DB 1      // Acquired first
#define LOCK_PRIORITY_CACHE 2   // Acquired second
#define LOCK_PRIORITY_LOG 3     // Acquired last

// Rule: Always lock in ascending priority order: DB -> Cache -> Log
// Violating this order is a bug, and tools like lockdep will catch it.

// System state -- the "bank's ledger"
int n_processes, n_resources;
int available[n_resources];          // Cash on hand
int max[n_processes][n_resources];   // Maximum each process will ever need
int allocation[n_processes][n_resources];  // Currently loaned out
int need[n_processes][n_resources];  // max - allocation = remaining demand

bool is_safe_state() {
    bool finish[n_processes] = {false};
    int work[n_resources];
    memcpy(work, available, sizeof(available));
    
    int completed = 0;
    while (completed < n_processes) {
        bool found = false;
        
        for (int i = 0; i < n_processes; i++) {
            if (finish[i]) continue;
            
            // Check if process i can finish with available resources
            bool can_finish = true;
            for (int j = 0; j < n_resources; j++) {
                if (need[i][j] > work[j]) {
                    can_finish = false;
                    break;
                }
            }
            
            if (can_finish) {
                // Simulate process completing
                for (int j = 0; j < n_resources; j++) {
                    work[j] += allocation[i][j];
                }
                finish[i] = true;
                completed++;
                found = true;
            }
        }
        
        if (!found) return false;  // No process can finish
    }
    
    return true;  // Found safe sequence
}

bool request_resources(int process_id, int request[]) {
    // Check if request exceeds need
    for (int j = 0; j < n_resources; j++) {
        if (request[j] > need[process_id][j]) {
            return false;  // Error: exceeds maximum claim
        }
        if (request[j] > available[j]) {
            return false;  // Must wait
        }
    }
    
    // Pretend to allocate
    for (int j = 0; j < n_resources; j++) {
        available[j] -= request[j];
        allocation[process_id][j] += request[j];
        need[process_id][j] -= request[j];
    }
    
    // Check if resulting state is safe
    if (is_safe_state()) {
        return true;  // Grant request
    }
    
    // Not safe, rollback
    for (int j = 0; j < n_resources; j++) {
        available[j] += request[j];
        allocation[process_id][j] -= request[j];
        need[process_id][j] += request[j];
    }
    
    return false;  // Deny request
}

// Similar to Banker's safety check
bool detect_deadlock() {
    bool finish[n_processes];
    int work[n_resources];
    
    memcpy(work, available, sizeof(available));
    
    // Initially, only processes with no allocation are "finished"
    for (int i = 0; i < n_processes; i++) {
        bool has_allocation = false;
        for (int j = 0; j < n_resources; j++) {
            if (allocation[i][j] > 0) {
                has_allocation = true;
                break;
            }
        }
        finish[i] = !has_allocation;
    }
    
    // Find processes that can complete
    bool changed;
    do {
        changed = false;
        for (int i = 0; i < n_processes; i++) {
            if (finish[i]) continue;
            
            bool can_finish = true;
            for (int j = 0; j < n_resources; j++) {
                if (request[i][j] > work[j]) {
                    can_finish = false;
                    break;
                }
            }
            
            if (can_finish) {
                finish[i] = true;
                for (int j = 0; j < n_resources; j++) {
                    work[j] += allocation[i][j];
                }
                changed = true;
            }
        }
    } while (changed);
    
    // Any unfinished process is deadlocked
    for (int i = 0; i < n_processes; i++) {
        if (!finish[i]) return true;  // Deadlock detected
    }
    return false;
}

void recover_by_termination() {
    // Option A: Kill all deadlocked processes (drastic)
    for (int i = 0; i < n_processes; i++) {
        if (is_deadlocked(i)) {
            kill_process(i);
        }
    }
    
    // Option B: Kill one at a time until deadlock resolved
    while (detect_deadlock()) {
        int victim = select_victim();  // Based on priority, resources, etc.
        kill_process(victim);
    }
}

int select_victim() {
    // Criteria for victim selection:
    // 1. Priority (kill lowest priority)
    // 2. Resources held (kill one with most)
    // 3. Progress (kill one with least work done)
    // 4. Resources needed (kill one needing most)
    // 5. Interactive vs batch (prefer killing batch)
}

void recover_by_preemption() {
    // Take resources from some processes, give to others
    
    while (detect_deadlock()) {
        int victim = select_victim();
        
        // Roll back victim to safe state
        rollback_process(victim);
        
        // Reallocate its resources
        for (int j = 0; j < n_resources; j++) {
            available[j] += allocation[victim][j];
            allocation[victim][j] = 0;
        }
    }
}

// LIVELOCK EXAMPLE
void thread_a() {
    while (1) {
        lock(mutex_a);
        if (trylock(mutex_b) == 0) {
            // Got both
            do_work();
            unlock(mutex_b);
            unlock(mutex_a);
            return;
        }
        unlock(mutex_a);  // Release and retry
        // Both threads keep doing this forever!
    }
}

// SOLUTION: Add randomized backoff
void thread_a_fixed() {
    while (1) {
        lock(mutex_a);
        if (trylock(mutex_b) == 0) {
            do_work();
            unlock(mutex_b);
            unlock(mutex_a);
            return;
        }
        unlock(mutex_a);
        usleep(random() % 1000);  // Random backoff
    }
}

// STARVATION EXAMPLE
// Reader-writer lock with reader preference
// Writers may starve if readers keep coming

// SOLUTION: Fair scheduling
// - Limit how long readers can hold lock
// - Give waiting writers priority after threshold
// - Use fair lock (FIFO ordering)

High priority (H):   Waiting for lock held by L
Medium priority (M): Running (doesn't need lock)
Low priority (L):    Holds lock, preempted by M

H is blocked by M (indirectly)!