面试题：C语言网络编程中多线程的死锁检测与预防

死锁发生的条件

互斥条件：资源一次只能被一个线程使用，即某个资源在一段时间内只能由一个线程占有。例如，网络套接字在某一时刻只能被一个线程进行读写操作。
占有并等待条件：一个线程已经持有了至少一个资源，但又请求新的资源，并且在等待新资源的同时，不释放已持有的资源。比如线程A持有缓冲区资源，又请求网络套接字资源，在等待套接字资源时，不释放缓冲区。
不可剥夺条件：线程已获得的资源，在未使用完之前，不能被其他线程强行剥夺，只能由该线程自己主动释放。例如线程B获得的网络连接资源，其他线程不能强行夺取。
循环等待条件：存在一个线程集合{T1, T2, ..., Tn}，其中T1等待T2占有的资源，T2等待T3占有的资源，...，Tn等待T1占有的资源，形成一个循环等待链。

通用的死锁检测机制（运行时动态检测）

资源分配图算法：
- 数据结构：
  - 用一个有向图G=(V, E)来表示资源分配状态，其中V是顶点集，由所有线程（记为P1, P2, ..., Pn）和所有资源（记为R1, R2, ..., Rm）组成；E是边集，边有两种类型，一种是从线程到资源的请求边（Pi -> Rj），表示线程Pi请求资源Rj；另一种是从资源到线程的分配边（Rj -> Pi），表示资源Rj已分配给线程Pi。
- 算法步骤：
  - 初始化资源分配图。
  - 查找图中是否存在环。可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来检测环。如果存在环，则表示发生了死锁。
  - 检测到死锁后，可以选择终止环中的某个线程，释放其占有的资源，以打破死锁。
基于时间戳的方法：
- 数据结构：为每个线程和资源分配一个时间戳。线程请求资源时，记录当前时间作为请求时间戳；资源分配时，记录分配时间戳。
- 算法步骤：
  - 当一个线程请求资源时，检查资源的分配时间戳和所有持有该资源的线程的时间戳。如果请求线程的时间戳比持有资源的所有线程的时间戳都小，说明请求线程等待时间更长，可能导致死锁。此时可以选择剥夺持有资源线程的资源，分配给请求线程。
  - 定期检查所有线程的请求状态和资源分配状态，判断是否存在死锁趋势。例如，如果某个线程长时间等待某个资源，且资源的持有线程也在等待其他资源，可能存在死锁风险。

从代码设计层面预防死锁的发生

设计原则：
- 破坏互斥条件：尽量使用可共享的资源，减少对独占资源的依赖。例如，对于网络缓冲区，可以采用无锁数据结构，多个线程可以同时访问而不需要互斥锁。
- 破坏占有并等待条件：
  - 一次性分配：让线程在启动时一次性请求并获取所有需要的资源，而不是逐步请求。例如，一个线程需要网络套接字和缓冲区，在启动时同时请求这两个资源，若不能同时获取则不启动。
  - 资源分配顺序：按照一定的顺序请求资源。例如，所有线程都按照先请求网络套接字，再请求缓冲区的顺序进行，避免循环等待。
- 破坏不可剥夺条件：设置抢占机制，当一个线程请求的资源被其他线程占用时，如果请求线程优先级更高或者等待时间更长，可以强制剥夺占用线程的资源。
- 破坏循环等待条件：使用资源分配图算法，在每次资源分配前检查是否会形成环，如果会形成环则拒绝分配。
示例代码：
- 基于资源分配顺序的预防：

#include <pthread.h>
#include <stdio.h>

// 定义两个资源的互斥锁
pthread_mutex_t socket_mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t buffer_mutex = PTHREAD_MUTEX_INITIALIZER;

void* thread_function(void* arg) {
    // 按照固定顺序获取锁
    pthread_mutex_lock(&socket_mutex);
    printf("Thread got socket mutex\n");
    pthread_mutex_lock(&buffer_mutex);
    printf("Thread got buffer mutex\n");

    // 线程工作代码
    // ......

    // 按照相反顺序释放锁
    pthread_mutex_unlock(&buffer_mutex);
    pthread_mutex_unlock(&socket_mutex);
    return NULL;
}

int main() {
    pthread_t thread;
    pthread_create(&thread, NULL, thread_function, NULL);

    pthread_join(thread, NULL);

    pthread_mutex_destroy(&socket_mutex);
    pthread_mutex_destroy(&buffer_mutex);
    return 0;
}

- **基于一次性分配的预防**：

#include <pthread.h>
#include <stdio.h>
#include <stdbool.h>

// 定义两个资源
typedef struct {
    pthread_mutex_t socket_mutex;
    pthread_mutex_t buffer_mutex;
    bool socket_allocated;
    bool buffer_allocated;
} Resources;

Resources resources = {
   .socket_mutex = PTHREAD_MUTEX_INITIALIZER,
   .buffer_mutex = PTHREAD_MUTEX_INITIALIZER,
   .socket_allocated = false,
   .buffer_allocated = false
};

void* thread_function(void* arg) {
    // 一次性请求资源
    pthread_mutex_lock(&resources.socket_mutex);
    if (!resources.socket_allocated) {
        resources.socket_allocated = true;
        pthread_mutex_lock(&resources.buffer_mutex);
        if (!resources.buffer_allocated) {
            resources.buffer_allocated = true;
            printf("Thread got both socket and buffer\n");
            // 线程工作代码
            // ......
            resources.buffer_allocated = false;
        }
        pthread_mutex_unlock(&resources.buffer_mutex);
    }
    resources.socket_allocated = false;
    pthread_mutex_unlock(&resources.socket_mutex);
    return NULL;
}

int main() {
    pthread_t thread;
    pthread_create(&thread, NULL, thread_function, NULL);

    pthread_join(thread, NULL);

    pthread_mutex_destroy(&resources.socket_mutex);
    pthread_mutex_destroy(&resources.buffer_mutex);
    return 0;
}

星途面试题库

面试题：C语言网络编程中多线程的死锁检测与预防

知识考点

面试题答案

死锁发生的条件

通用的死锁检测机制（运行时动态检测）

从代码设计层面预防死锁的发生