面试题：C语言Linux复杂场景下互斥锁死锁预防的优化

数据结构

锁状态表：
- 采用哈希表（例如C语言中的hash_table，可以自行实现或使用开源库如uthash）来记录每个互斥锁的状态。每个表项包含互斥锁的标识（如指针或唯一ID）、当前持有线程的ID（如果已被持有）以及一个标志位表示是否正在被获取（用于检测死锁过程中判断锁的临时状态）。
- 示例代码（简单示意，实际hash_table实现更复杂）：
```
struct lock_status {
    pthread_mutex_t *lock;
    pthread_t holder;
    int is_acquiring;
    UT_hash_handle hh;
};
struct lock_status *lock_table = NULL;
```

线程等待图：

使用邻接表来表示线程等待图。图中的节点是线程，边表示一个线程等待另一个线程持有的锁。每个节点包含线程ID以及一个链表，链表中存储该线程等待的锁所对应的持有线程ID。
示例代码：

struct thread_waiting_node {
    pthread_t waiting_for;
    struct thread_waiting_node *next;
};
struct thread_waiting_graph {
    pthread_t thread_id;
    struct thread_waiting_node *waiting_list;
    struct thread_waiting_graph *next;
};
struct thread_waiting_graph *waiting_graph = NULL;

算法

死锁检测算法（基于深度优先搜索DFS）：

每当一个线程尝试获取锁时，首先更新锁状态表，将该锁标记为正在被获取。
构建线程等待图，将当前线程对锁的等待关系加入图中。
从当前线程对应的节点开始进行深度优先搜索。如果在搜索过程中发现一个节点（线程）已经在当前搜索路径中，说明存在环，即发生死锁。
搜索完成后，清除为检测死锁而临时标记的状态。
示例代码（简化的DFS实现）：

int visited[1024] = {0}; // 假设最大线程数1024，实际应用需动态分配
int dfs(pthread_t thread) {
    struct thread_waiting_graph *graph_node = waiting_graph;
    while (graph_node && graph_node->thread_id != thread) {
        graph_node = graph_node->next;
    }
    if (!graph_node) return 0;
    if (visited[graph_node - waiting_graph]) return 1;
    visited[graph_node - waiting_graph] = 1;
    struct thread_waiting_node *list_node = graph_node->waiting_list;
    while (list_node) {
        if (dfs(list_node->waiting_for)) {
            return 1;
        }
        list_node = list_node->next;
    }
    visited[graph_node - waiting_graph] = 0;
    return 0;
}

死锁预防算法（资源分配图算法）：
- 为每个互斥锁分配一个唯一的编号，按照编号从小到大的顺序获取锁。
- 当一个线程请求获取多个锁时，首先检查是否可以按照编号顺序获取所有锁。如果不能，则拒绝该请求，直到其他线程释放了相关锁，使得可以按照顺序获取。

与现有代码集成

获取锁部分：

在每个模块的线程池中的获取锁函数（例如pthread_mutex_lock调用处）进行修改。在调用pthread_mutex_lock之前，先调用死锁检测和预防相关函数。如果检测到死锁风险，根据预防算法拒绝获取锁或者等待合适时机。
示例代码：

int custom_pthread_mutex_lock(pthread_mutex_t *mutex) {
    // 更新锁状态表，标记为正在获取
    struct lock_status *status;
    HASH_FIND_PTR(lock_table, &mutex, status);
    if (!status) {
        status = (struct lock_status *)malloc(sizeof(struct lock_status));
        status->lock = mutex;
        status->holder = 0;
        status->is_acquiring = 1;
        HASH_ADD_PTR(lock_table, lock, status);
    } else {
        status->is_acquiring = 1;
    }
    // 构建线程等待图
    struct thread_waiting_graph *graph_node = waiting_graph;
    while (graph_node && graph_node->thread_id != pthread_self()) {
        graph_node = graph_node->next;
    }
    if (!graph_node) {
        graph_node = (struct thread_waiting_graph *)malloc(sizeof(struct thread_waiting_graph));
        graph_node->thread_id = pthread_self();
        graph_node->waiting_list = NULL;
        graph_node->next = waiting_graph;
        waiting_graph = graph_node;
    }
    struct thread_waiting_node *new_waiting = (struct thread_waiting_node *)malloc(sizeof(struct thread_waiting_node));
    new_waiting->waiting_for = status->holder;
    new_waiting->next = graph_node->waiting_list;
    graph_node->waiting_list = new_waiting;
    // 检测死锁
    if (dfs(pthread_self())) {
        // 处理死锁，例如释放已获取锁，等待一段时间后重试
        // 恢复锁状态表
        status->is_acquiring = 0;
        return -1;
    }
    // 执行原有的pthread_mutex_lock
    int ret = pthread_mutex_lock(mutex);
    // 更新锁状态表，标记为已持有
    status->holder = pthread_self();
    status->is_acquiring = 0;
    return ret;
}

释放锁部分：

在pthread_mutex_unlock调用处，更新锁状态表，将锁的持有线程ID清零，并从线程等待图中移除相关的等待关系。
示例代码：

int custom_pthread_mutex_unlock(pthread_mutex_t *mutex) {
    struct lock_status *status;
    HASH_FIND_PTR(lock_table, &mutex, status);
    if (status && status->holder == pthread_self()) {
        status->holder = 0;
        // 从线程等待图中移除相关等待关系
        struct thread_waiting_graph *graph_node = waiting_graph;
        while (graph_node && graph_node->thread_id != pthread_self()) {
            graph_node = graph_node->next;
        }
        if (graph_node) {
            struct thread_waiting_node *list_node = graph_node->waiting_list;
            struct thread_waiting_node *prev = NULL;
            while (list_node) {
                if (list_node->waiting_for == pthread_self()) {
                    if (prev) {
                        prev->next = list_node->next;
                    } else {
                        graph_node->waiting_list = list_node->next;
                    }
                    free(list_node);
                    break;
                }
                prev = list_node;
                list_node = list_node->next;
            }
        }
    }
    return pthread_mutex_unlock(mutex);
}

对系统性能的潜在影响

时间开销：
- 死锁检测和预防机制引入了额外的计算开销。死锁检测的DFS算法和资源分配图算法都需要遍历数据结构，这会增加获取锁和释放锁的时间。特别是在并发程度高、锁数量多的情况下，检测时间可能会显著增加。
空间开销：
- 引入了锁状态表和线程等待图等数据结构，需要额外的内存空间来存储锁的状态、线程等待关系等信息。随着系统规模的扩大，这些数据结构占用的内存可能成为一个问题。
并发性能：
- 死锁预防算法可能会导致一些线程因为不能按照顺序获取锁而被阻塞，降低了系统的并发性能。然而，从长远来看，避免死锁可以防止系统出现长时间的停顿，提高系统的整体稳定性和可靠性。

星途面试题库

面试题：C语言Linux复杂场景下互斥锁死锁预防的优化

知识考点

面试题答案

数据结构

算法

与现有代码集成

对系统性能的潜在影响