MOS: Modern Operating Systems
deadlock detection with one resource of each type
如果每种资源都是独一份的，可以用上面这样的图来分析资源竞争情况。
图中方块代表资源，圆形代表进程；指向进程的箭头表示资源被该进程拥有，而从进程出发的箭头表示其需要的资源。
有向图中只要存在一个闭环，就存在一个死锁
找出闭环的方法有很多种，这里给出一个比较直观的方法：
0）首先把图中所有箭头记为unmarked，初始化一个空链表L，并选中一个节点（无论是进程还是资源，这里只考虑抽象出的有向图）为当前节点
1）判断该节有没有出现在L中，如果没有则加入L尾部进入下一步；如果有则说明存在一个闭环，即发现死锁
2）当前节点如果有向外的unmarked箭头就顺着它找到下一个节点，同时将该箭头标记为marked，跳到1）；如果没有unmarked箭头进入下一步
3）没有unmarked的箭头表明已经进入死胡同，删掉当前节点，回溯到源节点，将其设置为当前节点，跳到2）
deadlock detection with multiple resources of each type
当一种资源有多个可用实体时，我们使用一种基于矩阵的算法
向量E表示m种资源目前被占用的情况，A表示m种资源剩余量
矩阵C表示n个进程目前分别占用各种资源的情况，每行代表一个进程，每列是一种资源对应的各个进程占用情况，m列求和就等于Em
矩阵R表示n个进程目前对各种资源的需求量，行列意义同上
定义向量X<=Y当且仅当X的每个分量都<=Y的对应分量
算法步骤：
0）所有进程标记为unmarked
1）找到一个unmarked进程i，其占用的资源Ri<=A，下一步；没有满足该条件的进程，跳到3）
2）A=A+Ci，进程i标记为marked，跳到1）
3）如果所有进程都是marked，表示都得到了执行，没有死锁；否则，剩余的所有unmarked进程构成了死锁