面试题：C语言多线程死锁检测机制在Linux环境下的实现

Question

请描述如何在Linux C语言多线程服务器程序中，设计并实现一个死锁检测机制，说明所需的数据结构和关键算法。

Answer 1

数据结构

1. 线程状态结构体：

typedef struct {
    pthread_t tid;
    int state; // 例如 0: 空闲, 1: 持有锁, 2: 等待锁等
    int waiting_for_lock; // 若等待锁，记录等待的锁ID
    int held_lock; // 若持有锁，记录持有的锁ID
} ThreadStatus;

2. 锁状态结构体：

typedef struct {
    pthread_mutex_t mutex;
    int is_locked;
    pthread_t owner;
} LockStatus;

3. 全局状态结构体：

typedef struct {
    ThreadStatus *threads[MAX_THREADS];
    LockStatus *locks[MAX_LOCKS];
    int thread_count;
    int lock_count;
} GlobalStatus;

关键算法

1. 初始化： 在程序启动时，初始化所有线程状态为空闲，所有锁状态为未锁定。

GlobalStatus global;
// 初始化线程状态
for (int i = 0; i < global.thread_count; i++) {
    global.threads[i]->state = 0;
    global.threads[i]->waiting_for_lock = -1;
    global.threads[i]->held_lock = -1;
}
// 初始化锁状态
for (int i = 0; i < global.lock_count; i++) {
    pthread_mutex_init(&global.locks[i].mutex, NULL);
    global.locks[i].is_locked = 0;
    global.locks[i].owner = 0;
}

2. 获取锁操作： 当一个线程尝试获取锁时，更新线程和锁的状态，并检查是否可能形成死锁。

int acquire_lock(pthread_t tid, int lock_id) {
    pthread_mutex_lock(&global.locks[lock_id].mutex);
    if (global.locks[lock_id].is_locked) {
        global.threads[tid].state = 2;
        global.threads[tid].waiting_for_lock = lock_id;
        pthread_mutex_unlock(&global.locks[lock_id].mutex);
        // 检查死锁
        if (check_deadlock(tid)) {
            // 处理死锁，例如释放所有已持有的锁
            release_all_locks(tid);
            return -1;
        }
        // 等待锁
        // 这里可以使用条件变量等机制等待锁释放
    } else {
        global.locks[lock_id].is_locked = 1;
        global.locks[lock_id].owner = tid;
        global.threads[tid].state = 1;
        global.threads[tid].held_lock = lock_id;
    }
    pthread_mutex_unlock(&global.locks[lock_id].mutex);
    return 0;
}

3. 释放锁操作： 当一个线程释放锁时，更新线程和锁的状态。

void release_lock(pthread_t tid, int lock_id) {
    pthread_mutex_lock(&global.locks[lock_id].mutex);
    if (global.locks[lock_id].is_locked && global.locks[lock_id].owner == tid) {
        global.locks[lock_id].is_locked = 0;
        global.locks[lock_id].owner = 0;
        global.threads[tid].state = 0;
        global.threads[tid].held_lock = -1;
    }
    pthread_mutex_unlock(&global.locks[lock_id].mutex);
}

4. 死锁检测算法： 可以使用深度优先搜索（DFS）算法来检测死锁。构建一个有向图，线程为节点，线程等待锁的关系为边。从当前等待锁的线程开始DFS，如果能回到起始节点，则存在死锁。

int visited[MAX_THREADS];
int dfs(pthread_t tid) {
    visited[tid] = 1;
    int waiting_lock = global.threads[tid].waiting_for_lock;
    if (waiting_lock != -1) {
        pthread_t owner = global.locks[waiting_lock].owner;
        if (owner != 0) {
            if (visited[owner]) {
                return 1; // 发现死锁
            } else {
                if (dfs(owner)) {
                    return 1;
                }
            }
        }
    }
    visited[tid] = 0;
    return 0;
}

int check_deadlock(pthread_t tid) {
    for (int i = 0; i < global.thread_count; i++) {
        visited[i] = 0;
    }
    return dfs(tid);
}

注意事项

1. 以上代码为简化的示例，实际应用中需要根据具体场景进行调整，如处理更多的错误情况，优化数据结构等。
2. 死锁检测的频率需要合理设置，过于频繁会影响性能，过于稀疏可能不能及时发现死锁。