面试题：并发与同步环境中死锁检测与系统运行效率的权衡

实现原理

动态调整检测频率：根据系统当前的负载情况（如CPU使用率、内存使用率、任务队列长度等）来动态调整死锁检测的频率。当系统负载较低时，增加检测频率，以便更快发现死锁；当系统负载较高时，降低检测频率，减少检测对系统性能的影响。
资源分配图算法基础：基于资源分配图算法来检测死锁。资源分配图是描述进程和资源之间关系的有向图，通过对该图进行分析来判断是否存在死锁。

关键数据结构

进程结构体（Process）：

typedef struct {
    int pid; // 进程ID
    int *allocatedResources; // 已分配的资源数组
    int *requestedResources; // 请求的资源数组
    int resourceCount; // 资源种类数
} Process;

资源结构体（Resource）：

typedef struct {
    int rid; // 资源ID
    int availableCount; // 可用资源数量
} Resource;

资源分配图（ResourceAllocationGraph）：可以用邻接表来表示，每个节点代表一个进程或资源，边表示进程对资源的请求或资源对进程的分配关系。

typedef struct GraphNode {
    int id;
    int isProcess; // 1表示进程，0表示资源
    struct GraphNode *next;
} GraphNode;

typedef struct {
    GraphNode *adjList[MAX_PROCESSES + MAX_RESOURCES];
} ResourceAllocationGraph;

算法流程

初始化：
- 初始化所有进程和资源的状态，填充进程结构体和资源结构体。
- 初始化资源分配图，根据初始的资源分配情况构建图。
动态检测频率调整：
- 定期（如每100ms）获取系统负载信息，例如CPU使用率cpuUsage、内存使用率memoryUsage等。
- 定义一个负载阈值loadThreshold，如果cpuUsage + memoryUsage > loadThreshold，则降低死锁检测频率，例如将检测间隔从1秒延长到5秒；否则，提高检测频率，例如将检测间隔从5秒缩短到1秒。
死锁检测：
- 在每次检测间隔到达时，执行死锁检测。
- 从资源分配图中找到一个没有请求边（即请求资源都已满足）的进程节点，将其从图中移除，并释放该进程占用的资源（更新资源结构体中的availableCount）。
- 重复上述步骤，直到无法找到这样的进程节点。
- 如果此时图中还有剩余节点（进程或资源），则说明存在死锁。找出这些剩余节点，即为死锁涉及的进程和资源。
死锁处理：
- 一旦检测到死锁，采取相应的处理策略，如终止死锁进程中的一个或多个，以打破死锁状态。
- 重新调整资源分配和资源分配图，恢复系统正常运行。

星途面试题库

面试题：并发与同步环境中死锁检测与系统运行效率的权衡

知识考点

面试题答案

实现原理

关键数据结构

算法流程