什么是资源

简单来说，资源可以是一种硬件设备或是一组信息。比如说，打印机是一种资源，数据库中的一条纪录也是一种资源。当一个进程获得一种资源实例(一种资源可以有多个实例，比如可以有多台打印机)的时候，其他进程是不能同时拥有同一个资源实例，其实是资源的一种排他性的表现形式。操作系统具有授权一个进程(临时)排他性地访问某一种资源的能力。

再简单点来说，资源就是随着时间的推移，必须能获得，使用以及释放的任何东西。

可抢占式资源和不可抢占式资源

资源分为两类：可抢占式资源和不可抢占式资源。
资源是具有排他性的，可以理解为一个进程在使用的时候，另一个进程是不能同时持有并使用的。但是这并不意味着，后来的进程无法从之前的进程中去获得资源。

可抢占式资源可以从拥有它的进程中抢占而不会产生任何的副作用，比如说存储器就是一种可抢占式资源。

不可抢占资源是指不引起相关的计算失败的情况下，无法把它从占有它的进程处抢占过来。

一个系统有256M的用户内存和一台打印机。如果有两个256M内存的进程都想要进行打印，进程A请求获得了打印机，但是还没有打印之前，时间片用完。进程B开始运行，并请求打印机，但是打印机已经被进程A持有，所以一直请求失败，进入到休眠状态，再次请求，直到时间片用完。进程A继续运行，其实此时进程A持有打印机需要内存，而进程B持有内存需要打印机，是存在死锁风险的。但是内存是一个可抢占式的资源，进程A运行的时候，将进程B的内存换出，使得进程A持有内存，结果就是可以运行，而不会产生死锁。

所以，一般不可抢占式的资源才会导致死锁，将死锁的时候，资源一般就是指的是不可抢占式的资源。

对于两个不可抢占式的资源，如果有以下两个进程同时运行就有可能会产生死锁。

semaphore resouce_1
samaphore resouce_2

void process_A(void){
    down(&resouce_1);
    down(&resouce_2);
    use_both_resouces();
    up(&resouce_2);
    up(&resouce_1);
}

void process_B(void){
    down(&resouce_2);
    down(&resouce_1);
    use_both_resouces();
    up(&resouce_1);
    up(&resouce_2);
}

但是如果是下面这样的两个进程就不会产生死锁。需要仔细体会不同点，获取资源的顺序不同，就会导致死锁的危险。

semaphore resouce_1
samaphore resouce_2

void process_A(void){
    down(&resouce_1);
    down(&resouce_2);
    use_both_resouces();
    up(&resouce_1);
    up(&resouce_2);
}

void process_B(void){
    down(&resouce_1);
    down(&resouce_2);
    use_both_resouces();
    up(&resouce_1);
    up(&resouce_2);
}

其实第一种会导致死锁的情况如果用图形化的表示是这样的。进程1占有了R1，同时请求R2，进程2占有R2，同时请求R1。此时，就会发生死锁。如果看过下面的死锁发生的条件的话，那么就会发现有环路就是发生死锁的条件之一。第二种情况下，无论按照什么时间顺序去运行都会产生环路，所以是没有死锁的可能的。

两种资源可能会发生的死锁

什么是死锁

死锁就是如果一个进程集合中的每一个进程都在等待只能由该进程集合中的其他进程才能引发的事件，那么，该进程集合就是死锁的。

发生(资源)死锁的四个条件：

• 互斥条件：每个资源要么已经分配给了一个进程，要么就是可用的。
• 占有和等待条件：已经得到了某个资源的进程可以再请求新的资源。
• 不可抢占条件：已经分配给了一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
• 环路等待条件。死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

死锁的检测

每种类型一个资源的死锁检测

看一个更加复杂的死锁的例子。

1. A进程持有R资源，且需要S资源。
2. B进程不持有任何资源，但需要T资源。
3. C进程不持有任何资源，且需要S资源。
4. D进程持有U资源，且需要S资源和T资源。
5. E进程持有T资源，且需要V资源。
6. F进程持有W资源，且需要S资源。
7. G进程持有V资源，且需要U资源。

如下图：

一个更加复杂的死锁的例子

可以发现这里面也是存在环路的，也是会发生死锁的，也就是D，E，G三个进程会发生死锁。那么如果检测到这个死锁的情况呢？其实就是判断有向环的情况。下面介绍其中一种算法。大概的思路是对每一个节点进行深度优先遍历。将所有遍历到的节点情况放入到一个队列中。如果队列中一但存在两个相同的节点时，其实就是可以认为是有环路存在的。如果对一个节点深度优先遍历完了，则认为没有从这个节点的环路存在，此时应该换下一个节点。

比如说上面一个例子运行这个算法，可以是这样的一个过程。
从R开始深度优先遍历到A，此时数组L中的值含有R和A，遍历到S，L=(R,A,S)。此时S无法去其他节点了。按照深度优先遍历的规则，需要回溯到A节点，同理A也没有其他节点可去，回到R，结束此次，认为此次没有环路。

接着按照这个规则从A开始，还是没有环路。

从B开始，会发现L=(B,T,E,V,G,U,D)。再往下遍历有两种情况，一种情况是到S，此时是没有环路的，L= (B,T,E,V,G,U,D,S)。往T走，L= (B,T,E,V,G,U,D,T)，此时发现数组中存在两个T，即认为存在环路了。算法到此就结束了。

那么再考虑一下，如何破坏这个死锁呢？其实就是打破上述四个条件之一就可以了。比如说可以强行让D进程抢占T资源，这样就可以在运行完释放U和T的资源，这样就破坏了死锁的条件。但是强行抢占的情况下，要考虑这样的后果。
也可以通过杀死进程恢复，比如说将D进程给杀死，此时也可以破坏死锁的条件。

具体的检测死锁的算法描述是这样的：

1. 对图中的每一个节点N，将N作为起始点执行下面5个步骤。
2. 将L初始化为空表，并清除所有的有向边标记。
3. 将当前节点添加到L的尾部，并检测节点是否在L中已出现过两次。如果是，那么该图包含了一个环(已列在L中)，算法结束。
4. 从给定的节点开始，检测是否存在没有标记的从该节点出发的弧。如果存在的话，做第5步，如果不存在，跳到第6步。
5. 随机选取一条没有标记的从该节点出发的弧，标记他。然后顺着这条弧线找到新的当前节点，返回到第3步。
6. 如果这一节点是起始节点，那么表明该图不存在任何环，算法结束。否则意着我们走进了死胡同，需要回溯到上一个节点，作为新节点，转到第3步。

从上面可以发现检测死锁的算法确实是存在的。

每种类型多个资源的死锁检测

先简单描述一下，下次再详述。

首先我们有四个东西，一个是现有资源的向量数组，一个是可用资源的向量数组，一个是当前的分配矩阵，一个是请求矩阵。

死锁检测算法：

1. 寻找一个没有标记过的进程Pi，对于他而言R矩阵的第i行向量小于或者等于A。
2. 如果找到了这样一个进程，那么将C矩阵的第i行向量添加到A中，标记该进程，并转到第1步。
3. 如果没有这样的进程，那么算法中止。

最后

死锁部分的内容还有死锁的恢复和死锁的避免，以及死锁避免的具体的算法，银行家算法，死锁的预防。

参考

现代操作系统之死锁章节。