操作系统简明-3:死锁 干货整理

---

先看一个程序的引入

Lock *l1, *l2;
void p() {
l1->Acquire(); l2->Acquire();
code that manipulates data that l1 and l2 protect
l2->Release(); l1->Release();
}
void q() {
l2->Acquire(); l1->Acquire();
code that manipulates data that l1 and l2 protect
l1->Release(); l2->Release();
}

考虑上述程序,如果p()和q()同步发生,p requires l1,q requires l2,然后p 等待require l2,q 等待require l1,由于p,q的交叉影响,使得程序用于这么等待下去

死锁条件

如果同时满足下列四个条件，则会发生死锁

1. 相互排斥：一次只能有一个进程可以访问资源
2. 等待： 进程拥有一些资源，但还想获取别的进程的资源
3. 不抢占：进程完成资源使用后，才能释放资源，而且只能是这个进程释放（不能被别的进程抢占）
4. 循环等待：存在待处理集合{P 0，P 1，...，P n}，使得P 0正在等待由P 1持有的资源，P 1等待由P 2持有的资源，... ，P n-1正在等待由P n持有的资源，并且P n等待由P 0保持的资源

资源分配图

当进程与资源成为一个循环时，便有可能发生死锁，如果不成循环便不会死锁

死锁预防

1. 消除相互排斥

允许每个人立刻使用资源

这个方法并不乐观，因为如果你想用打印机打印点东西，如果此时别的进程也要打印，打印出的东西会混乱不堪

2. 阻止等待

当一个进程请求资源时，不让他持有任何资源

1. 进程可能持有资源，但是不会时时刻刻再用
2. 饥饿：如果一个进程想要很大的资源，他可能要等很久,因为那些持有资源的进程不能运行（造成的结果是不能释放）

3. 阻止循环等待

每个进程要估算出需要的最大资源，系统根据这些请求决定进程执行顺序

这里介绍一个操作：TryAcquire
这个操作顾名思义，尝试获取锁，如果成功获取，就说明没有死锁，反之就要释放您尝试获取的锁之后的所有锁（要确保释放后不会有坏的影响），然后在正确顺序下获取锁

这个操作是打破了循环等待

另一个例子：
System has 12 tape drives
P0 needs max 10 has 5
P1 needs max 4 has 2
P2 needs max 9 has 2

If P1 runs first and completes, it will have 5 free tape drives. P0 can run to completion with those 5 free tape drives even if it requests max. Then P2 can complete
算法实现：

Avail[j] = number of resource j available
Max[i,j] = max number of resource j that process i will use
Alloc[i,j] = number of resource j that process i currently has
Need[i,j] = Max[i,j] - Alloc[i,j]

1: Work = Avail;
Finish[i] = False for all i; 
2: Find i s.t. Finish[i] = False && Need[i] <= Work
If no such i exists, goto 4
3: Work = Work + Alloc[i]; Finish[i] = True; goto 2
4: If Finish[i] = True for all i, system is in a safe state

这个算法很容易理解，２～３步骤是主干，主要使所有线程获取到资源，主要查看一个资源需求是否安全
如果有附加需求，那么就需要下列算法来实现

Request[i,j] = number of j resources that　process i requests
Assume process i has just requested additional　resources.

1: If Request[i] <= Need[i] goto 2. Otherwise, process
has violated its maximum resource claim.
2: If Request[i] <= Avail goto 3. Otherwise, i must
wait because resources are not available.
3: Pretend to allocate resources as follows:
Avail = Avail - Request[i]
Alloc[i] = Alloc[i] + Request[i]
Need[i] = Need[i] - Request[i]
If this is a safe state, give the process the resources.
Otherwise, suspend the process and restore the old
state.

什么时候让悬挂的线程获得资源？
当然是等其他资源被释放后，但是又出了一个饥饿问题，当你悬挂一个超级大的资源需求时，总会有小的线程获得资源，使得大资源很难继续运行

4. 资源抢占

首先给出一个判断是否是死锁的算法，这个算法跟上述的算法很相似

1: Work = Avail;
Finish[i] = False for all i;
2: Find i s.t. Finish[i] = False && Request[i] <= Work
If no such i exists, goto 4
3: Work = Work + Alloc[i]; Finish[i] = True; goto 2
4: If Finish[i] = False for some i, system is
deadlocked.
Moreover, Finish[i] = False implies that process i is
deadlocked.

• 在不杀死进程的前体下抢占一些资源：主存可以换掉磁盘，稍后再回复工作
• 如果作业提供回滚点，可以将作业恢复到获得资源之前。 稍后，从回滚点重新启动作业。 默认回滚点 - 作业开始
• 对于一些资源，只能杀死，那么一个一个的杀死，直到系统不再死锁或者只杀死死锁进程

---

对于不同的机器，有着不同的解决办法，上述４种方法要找准各自的位置，用到好处才能使操作系统更完美
另外庆祝下ＷＥ打ＳＫＴ，最后一场很精彩，无论最后的输赢，气势出来了！