chapter8 练习¶

本节难度：助教自评为工作量最高一次，请尽早开始

本章任务¶

本次任务对应 lab5，也是本学期最后一次实验，祝你好运。
老规矩，先 make test BASE=1 看下啥情况。
理解框架的多线程机制，了解几种锁的运行原理。在此基础上，实现本章编程作业死锁检测。
- 如果时间有限，多线程机制的一些细节大可跳过，但至少应知道多线程基本原理和本章在任务调度粒度上的调整
- 与实验息息相关的是互斥锁(mutex)与信号量(semaphore)，条件变量(condvar)供阅读
- 框架包含 LAB5 字样的注释中给出了一个供参考的实现位置和顺序，你可以按顺序完成（下面的标号与注释中的一种）：
  
  1: 定义并初始化部分 PCB 的部分变量，包括控制死锁检测启动与死锁检测算法用到的变量，你可以先定义一部分，后面发现有需要时再做添加；
  
  2: 完成系统调用 sys_enable_deadlock_detect，只需要修改变量，不必考虑是否正确实现了死锁。完成这一步后你可以顺利跑完 ch8_sem2_deadlock，这个测例开启了死锁检测但并没有死锁；
  
  3: 尝试写一个函数实现下面提到的死锁检测算法，注释中给了供参考的函数签名。这是一个和OS独立的函数，你可以自行设计数据单独运行它以测试；
  
  4-1: 维护 mutex 相关的死锁检测变量，并调用死锁检测算法，完成后你可以顺利跑完测例 ch8_mut1_deadlock；
  
  4-2: 维护 semaphore 相关的死锁检测变量，并调用死锁检测算法，完成后你可以顺利跑完测例 ch8_sem1_deadlock；
最终，完成实验报告并 push 你的 ch8 分支到远程仓库。push 代码后会自动执行 CI，代码给分以 CI 给分为准。

编程作业¶

警告

本次实验框架变动较大，且改动较为复杂，为降低同学们的工作量，本次实验不要求合并之前的实验内容，可以直接 checkout 到助教的 ch8 框架开始实验，最终只需通过 ch8 系列的测例和前面章节的基础测例即可。

注解

本次实验实现死锁检测算法本身只需要40行左右代码，但加上系统调用实现、变量声明与初始化、以及在锁的创建、锁、释放时维护死锁检测 Available、Allocation、Request 数组，总代码量预计在100行左右。助教的参考实现约为90行。

死锁检测¶

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

定义如下三个数据结构：

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

算法运行过程如下：

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

Finish[i] == false;
Request[i,0~n-1] ≤ Work[0~n-1];

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

当线程 i 获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:

Work[0~n-1] = Work[0~n-1] + Allocation[i, 0~n-1];
Finish[i] = true;

跳转回步骤2

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

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

enable_deadlock_detect：

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

实验要求¶

完成分支: ch8。
实验目录要求不变。
通过所有测例。

问答作业¶

在我们的多线程实现中，当主线程 (即 0 号线程) 退出时，视为整个进程退出，此时需要结束该进程管理的所有线程并回收其资源。
- 需要回收的资源有哪些？
- 其他线程的 struct thread 可能在哪些位置被引用，分别是否需要回收，为什么？
对比以下两种 mutex_unlock 中阻塞锁的实现，二者有什么区别？这些区别可能会导致什么问题？（假设无论哪种实现，对应的 mutex_lock 均正确处理了 m->locked）

void mutex_unlock_v1(struct mutex *m)
{
   if (m->blocking) {
      m->locked = 0;
      struct thread *t = id_to_task(pop_queue(&m->wait_queue));
      if (t != NULL) {
         t->state = RUNNABLE;
         add_task(t);
      }
   } else ...
}

void mutex_unlock_v2(struct mutex *m)
{
   if (m->blocking) {
      struct thread *t = id_to_task(pop_queue(&m->wait_queue));
      if (t == NULL) {
         m->locked = 0;
      } else {
         t->state = RUNNABLE;
         add_task(t);
      }
   } else ...
}

报告要求¶

注意目录要求，报告命名 lab5.md 或 lab5.pdf，位于 reports 目录下。后续实验同理。

简单总结你实现的功能（200字以内，不要贴代码）及你完成本次实验所用的时间。
完成问答题。
加入荣誉准则的内容。否则，你的提交将视作无效，本次实验的成绩将按“0”分计。
推荐markdown文档格式。
(optional) 你对本次实验设计及难度/工作量的看法，以及有哪些需要改进的地方，欢迎畅所欲言。

选作题目¶

选做题目列表

（7分）基于多核的OS内核线程支持，内核支持抢占，支持多核方式下的同步互斥
（7分）提升多核的OS内核性能，实现内核中的并行性能优化（fs中的缓冲区管理并行化, 物理内存分配的并行化）
（7分）更通用的内核+应用的死锁检查（参考Linux）

提交要求

（占分比：40%）实现代码（包括基本的注释）
（占分比：50%）设计与功能/性能测试分析文档，测试用例。
（占分比：10%）鼓励形成可脱离OS独立存在的库，可以裸机测试或在用户态测试（比如easyfs那样）