Skip to content

exercise.md

Latest commit

 

History

History
98 lines (70 loc) · 4.14 KB

exercise.md

File metadata and controls

98 lines (70 loc) · 4.14 KB

chapter8 练习

编程作业

死锁检测

目前的 mutex 和 semaphore 相关的系统调用不会分析资源的依赖情况，用户程序可能出现死锁。 我们希望在系统中加入死锁检测机制，当发现可能发生死锁时拒绝对应的资源获取请求。

一种检测死锁的算法如下：

定义如下三个数据结构：

  • 可利用资源向量 Available：含有 m 个元素的一维数组，每个元素代表可利用的某一类资源的数目，其初值是该类资源的全部可用数目，其值随该类资源的分配和回收而动态地改变。Available[j] = k，表示第 j 类资源的可用数量为 k。
  • 分配矩阵 Allocation：n × m 矩阵，表示每类资源已分配给每个线程的资源数。Allocation[i,j] = g，则表示线程 i 当前己分得第 j 类资源的数量为 g。
  • 需求矩阵 Need：n × m 的矩阵，表示每个线程还需要的各类资源数量。Need[i,j] = d，则表示线程 i 还需要第 j 类资源的数量为 d。

算法运行过程如下：

  1. 设置两个向量：工作向量 Work，表示操作系统可提供给线程继续运行所需的各类资源数目，它含有 m 个元素。初始时，Work = Available；结束向量 Finish，表示系统是否有足够的资源分配给线程，使之运行完成。初始时 Finish[0..n-1] = false，表示所有线程都没结束；当有足够资源分配给线程时，设置 Finish[i] = true。

  2. 从线程集合中找到一个能满足下述条件的线程：

Finish[i] == false;
Need[i,j] <= Work[j];

若找到，执行步骤 3，否则执行步骤 4。

  1. 当线程 thr[i] 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：
Work[j] = Work[j] + Allocation[i, j];
Finish[i] = true;

跳转回步骤 2。

  1. 如果 Finish[0..n-1] 都为 true，则表示系统处于安全状态；否则表示系统处于不安全状态，即出现死锁。

出于兼容性和灵活性考虑，我们允许进程按需开启或关闭死锁检测功能。为此我们将实现一个新的系统调用：enable_deadlock_detect。

enable_deadlock_detect：

  • syscall ID: 469
  • 功能：为当前进程启用或禁用死锁检测功能。
fn enable_deadlock_detect(&self, _caller: Caller, is_enable: i32) -> isize
  • 参数：
    • is_enable: 为 1 表示启用死锁检测，0 表示禁用死锁检测。
  • 说明：
    • 开启死锁检测功能后，mutex_lock 和 semaphore_down 如果检测到死锁，应拒绝相应操作并返回 -0xDEAD（十六进制值）。
    • 简便起见可对 mutex 和 semaphore 分别进行检测，无需考虑二者（以及 waittid 等）混合使用导致的死锁。
  • 返回值：如果出现了错误则返回 -1，否则返回 0。
  • 可能的错误：
    • 参数不合法
    • 死锁检测开启失败

实验要求

  • 在 tg-rcore-tutorial-ch8 目录下完成实验。
  • 目录结构说明：
tg-rcore-tutorial-ch8/
├── Cargo.toml（内核配置文件）
├── src/（内核源代码，需要修改）
│   ├── main.rs（内核主函数，包括系统调用接口实现）
│   ├── fs.rs（文件系统相关）
│   ├── process.rs（进程结构）
│   ├── processor.rs（进程/线程管理器）
│   └── virtio_block.rs（VirtIO 块设备实现）
└── tg-rcore-tutorial-user/（用户程序，运行时自动拉取，无需修改）
    └── src/bin（测试用例）

说明：

  • tg-rcore-tutorial-user 会在运行时自动拉取到 tg-rcore-tutorial-ch8/tg-rcore-tutorial-user 目录下
  • 只需修改 tg-rcore-tutorial-ch8/src/ 目录下的内核代码
  • 运行练习测例：
cargo run --features exercise

然后在终端中输入 tg-rcore-tutorial-ch8_usertest 运行，这个测例打包了所有你需要通过的测例。

  • 测试练习测例：
./test.sh exercise

说明

  • 由于本次实验框架变动较大，且改动较为复杂，为降低同学们的工作量，本次实验不要求合并之前的实验内容，只需通过 ch8 的全部测例和其他章节的基础测例即可。