// Use lock-free data structures
// Example: Atomic counter instead of mutex-protected counter

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

void increment() {
    atomic_fetch_add(&counter, 1);  // No mutex needed
}

// Acquire ALL locks at once, or none

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

bool acquire_all(resource_t *resources[], int count) {
    // Try to lock all
    for (int i = 0; i < count; i++) {
        if (pthread_mutex_trylock(&resources[i]->mutex) != 0) {
            // Failed to acquire one, release all held
            for (int j = 0; j < i; j++) {
                pthread_mutex_unlock(&resources[j]->mutex);
            }
            return false;  // Retry later
        }
    }
    return true;  // Got all resources
}

// If can't get resource, release what you have

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
        }
        
        // Can't get m2, release m1 (preempt self)
        pthread_mutex_unlock(m1);
        
        // Back off to avoid livelock
        usleep(random() % 1000);
    }
}

// Always acquire locks in consistent order

// Define global ordering by resource address
void safe_lock_two(pthread_mutex_t *a, pthread_mutex_t *b) {
    if (a < b) {
        pthread_mutex_lock(a);
        pthread_mutex_lock(b);
    } else {
        pthread_mutex_lock(b);
        pthread_mutex_lock(a);
    }
}

// Or use explicit priority
#define LOCK_PRIORITY_DB 1
#define LOCK_PRIORITY_CACHE 2
#define LOCK_PRIORITY_LOG 3

// Always lock in priority order: DB → Cache → Log

// System state
int n_processes, n_resources;
int available[n_resources];          // Available resources
int max[n_processes][n_resources];   // Maximum demand
int allocation[n_processes][n_resources];  // Currently allocated
int need[n_processes][n_resources];  // max - allocation

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)!