无图/无目录/格式错误/更多相关请到上方的文章首发页面查看。
操作系统原理学习笔记目录
排版可是越来越好看了呢！
有点尴尬，突然发现连续八篇文章都忘标目录了，还好还没发布。
2021/1/3：改正一个错别字，以及更通顺的语义。
2023/11/10：一个局部最优死锁算法的复杂度似乎算错了，见文章底部。
死锁检测算法与死锁解除算法
不采取预防死锁或避免死锁的OS，可能发生死锁，因此应当提供两个算法：
- 死锁检测算法：检测OS状态，是否发生死锁。
- 死锁解除算法：OS发生死锁后，解除死锁。
死锁检测
为了检测死锁，OS需要：
- 保存有关资源的请求与分配信息。
- 提供算法，根据以上信息来检测死锁。
资源分配图(Resource Allocation Graph)
资源分配图描述系统死锁，由一组结点N与一组边E组成的对偶G=(N, E)。
- 结点N由两个互斥子集构成，分别是进程P与资源R。
- 边E表示 进程请求资源/资源分配进程，
- 如E={(P1, R2), (R2, P2), (P2, R1), (R1, P1)}表示下图的(a)图，
表示P1申请R2资源，R2资源分配给P2，P2申请R1资源，R1分配给P1资源。
注：图P124原图是如此画的，但有六条边，说示出两条请求两条分配，我不太清楚是不是说漏了。
死锁定理
通过简化资源图的方式，将进程资源分配与资源释放的过程表示出来，一步步简化，直到无E时，表示安全。
- 在上面的资源分配图(a)中，找到一不阻塞且非独立的结点P1，为其分配资源，并释放资源。
- 即，将连接结点的边去除，形成图(b)。
- 再次循环这个过程，分配并释放P2结点的资源，形成图(c)。
- 经过上述简化过程后，图中边已全部消去，此时图被完全简化。
死锁检测中的数据结构
类似银行家算法的数据结构。
下面有点怪，不像数据结构，更像流程。
- Available[]：可利用资源向量数目。
- L表：不占资源进程的集合。
- 即Allocation==0的进程集合。
- 找到Request[i, j]<=Work[j]的进程，分配并释放资源，Work[j]+=Allocation[j]。
将进程i记录L表。
- 这里的下标又乱了，书上的数组下标真成下标了，为了和前篇文章统一，这里的下标我改成数组下标。
- 若所有进程都进入L表，则资源分配图是可完全简化的，否则，则是不可完全简化的，可能发生死锁。
死锁解除
检测到死锁时，最简单的处理措施是人工处理，另一种措施是使用死锁解除算法，常用的两种方法：
- 抢占资源：从若干进程中抢占足够资源，分配给死锁进程。
- 终止进程：终止若干个死锁进程，打破循环，解除死锁状态。
终止死锁的办法
- 终止所有死锁进程。
- 最简单，但是代价极大。
- 逐个终止进程。
难以确定终止顺序，但可根据以下几点进行度量：
- 进程优先级大小？
- 进程已运行时间，剩余运行时间？
- 进程已使用资源，还需使用资源？
- 交互式还是批处理？
付出代价最小的死锁解除算法
- 一种找到付出代价最小的终止顺序，但成本高的算法：
- 先从死锁进程组中取出一个，形成第一层终止，若有n个死锁进程，则有n个第一层。
- 再从n个第一层中取一个，形成第二层终止，每个第一层又有n-1个第二层终止。
- 如此循环，直到解除死锁，将各层的总代价计算，得到最小的终止顺序。
- 注：于P126有图示，但总体来说，是多重遍历，循环次数为n!，即n(n-1)(n-2)…
- 另一种比较有效的算法：
- 找到死锁进程组中，终止代价最小的，将其从死锁进程组中删去。
- 再从新的死锁进程组中，找到终止代价最小的，删去。
- 如此循环，直到解除死锁。
- 注：书上太复杂了，差点没看懂，
实际上就是只找到局部最优，再从局部最优继续找局部最优，
n个进程最多只需要n次寻找即可。（2023/11/10注：存疑，似乎是n+(n-1)+...+1，因为第一次寻找需要n次，随后每次减少，仅在当次寻找中局部最优）