面试题：并发与同步视角下操作系统死锁预防的用户态内核态深度协作机制

数据结构

资源分配图：
- 用有向图表示系统中资源与进程的关系。图中的节点分为两类，一类是进程节点，另一类是资源节点。有向边从进程节点指向资源节点表示进程请求资源，从资源节点指向进程节点表示资源已分配给该进程。通过维护这个数据结构，内核可以直观地了解系统资源分配状态，便于检测死锁。
- 例如，进程P1请求资源R1，就有一条从P1到R1的边；若R1已分配给P1，则有一条从R1到P1的边。
进程控制块（PCB）：
- 在每个进程的PCB中添加与死锁预防相关的字段。如记录进程已占用的资源列表，以及进程请求但尚未分配的资源列表。这样内核可以快速获取每个进程的资源使用和需求情况。
- 比如，进程P2已占用资源R2，在其PCB中就会记录这个信息；若P2还请求资源R3，也会记录在请求资源列表中。
资源描述块（RDB）：
- 每个资源类型对应一个RDB，记录该资源类型的总数、已分配数量等信息。这有助于内核判断是否有足够的资源可分配给请求的进程，以避免死锁。
- 例如，资源类型R4总共有5个实例，已分配3个，RDB中就会记录这些数据。

信号传递过程

用户态程序请求资源：
- 用户态程序通过系统调用（如request_resource）向内核请求资源。在系统调用中，程序会传递所需资源的标识等参数。
- 内核接收到请求后，首先检查资源分配图和相关数据结构，判断是否可以安全分配资源。如果资源充足且分配不会导致死锁（例如通过资源分配图算法检测），内核将资源分配给该进程，更新资源分配图、进程PCB和资源RDB等数据结构，并向用户态程序返回成功信号。
- 例如，进程P3请求资源R5，内核检查发现R5有可用实例且分配后不会形成死锁，就将R5分配给P3，同时更新相应数据结构，并向P3返回成功信号。
资源释放：
- 用户态程序使用完资源后，通过系统调用（如release_resource）通知内核释放资源。内核接收到释放请求后，更新资源分配图、进程PCB和资源RDB等数据结构，标记该资源为可用，并向用户态程序返回成功释放信号。
- 比如，进程P4释放资源R6，内核更新数据结构后向P4返回成功信号，其他等待R6的进程可能因此被唤醒。
死锁检测与处理信号：
- 内核定期（或在特定条件下，如资源分配后）运行死锁检测算法（如银行家算法的变体）。如果检测到死锁，内核会选择一个或多个进程作为牺牲者（victim）。
- 内核向这些被选中的进程发送死锁处理信号（如SIGDEADLOCK），通知它们需要释放部分或全部资源以解除死锁。用户态程序接收到该信号后，按照预先设定的策略释放资源，然后内核重新运行死锁检测算法，直到死锁解除。
- 例如，若检测到进程P5、P6、P7形成死锁环，内核选择P5作为牺牲者，向P5发送SIGDEADLOCK信号，P5收到信号后释放资源，内核再次检测死锁情况。

错误处理机制

资源不足错误：
- 当用户态程序请求资源时，如果资源不足，内核返回错误码（如ENOMEM或自定义的资源不足错误码）给用户态程序。用户态程序接收到错误码后，可以选择等待一段时间后重新请求资源，或者调整自身的资源需求策略。
- 比如，进程P8请求资源R7，但R7已全部分配，内核返回资源不足错误码，P8可以在代码中实现如下逻辑：

int ret = request_resource(R7);
if (ret == -1 && errno == ENOMEM) {
    sleep(1); // 等待1秒
    ret = request_resource(R7);
    if (ret == -1) {
        // 再次失败，采取其他策略，如减少请求资源量
    }
}

死锁处理错误：
- 如果用户态程序在接收到死锁处理信号（如SIGDEADLOCK）后，未能按照要求释放资源，内核可以采取更严厉的措施，如终止该进程。同时，内核记录错误日志，以便后续分析问题。
- 例如，进程P9收到SIGDEADLOCK信号后，由于程序内部错误未能释放资源，内核终止P9，并在系统日志中记录：“Process P9 failed to release resources upon receiving SIGDEADLOCK, terminated.”
系统调用参数错误：
- 如果用户态程序在发起系统调用（如请求或释放资源的系统调用）时，传递的参数错误，内核返回参数错误码（如EINVAL）给用户态程序。用户态程序接收到错误码后，检查并修正参数，重新发起系统调用。
- 比如，进程P10在调用request_resource时传递了错误的资源标识，内核返回EINVAL错误码，P10的代码可以如下处理：

int ret = request_resource(invalid_RID);
if (ret == -1 && errno == EINVAL) {
    // 修正资源标识
    valid_RID = correct_resource_id(invalid_RID);
    ret = request_resource(valid_RID);
}

面试题：并发与同步视角下操作系统死锁预防的用户态内核态深度协作机制

知识考点

面试题答案

数据结构

信号传递过程

错误处理机制