20.1 死锁的概念

由于共享资源而导致无限期等待的现象

死锁示例： 单向通行桥梁
在交汇处相遇，都在等对方过去，就卡住了

解决的方法很简单，一辆车往后退就可以了

与此同时，也可能出现饥饿的现象，即一个方向的车一直在走，另一个方向的车走不了


进程访问资源的流程

资源分类



资源分配图示例

如下图，进程P3占用R3，用完了之后释放，P2运行；不存在死锁

下面这种就存在死锁了，P3申请R2，P2占用R2，P2请求R3，P3占用R3，出现循环等待

下图又不存在死锁，以为R1和R2都有两个实例，总会有实例被分配给P1和P2的。也就是说并非循环等待就一定死锁。

出现死锁的必要条件

20.2 死锁处理方法

在敏感区域里不允许使用任何火源，把死锁的四个必要条件中的一个完全避免掉
这样的系统资源利用效率低

不完全禁止用火，比如林区，只有有资质的才可以用火

管理不过来，居民用火，预备一个消防队，出了问题派出消防队员

死锁预防

比如打印机，送任务时是互斥的。现在在打印机加入了缓冲，在打印机内部协调谁先谁后

比如贷款时，一次把所有的钱都贷出来，不允许贷一部分然后项目做着做着钱不够用了再贷。这样的做法资源利用率低

非抢占，就像上一节的撞车问题，一旦发现这种问题就倒车，这样就不会堵死了。

按顺序申请资源，可能先申请的某一项资源最后遇到，利用率低

死锁避免

有点像去银行借款，根据征信来贷款。

这种方法的麻烦是系统必须动态判断是否安全


安全状态和死锁的关系

10.3 银行家算法（Banker’s Algorithm）

假定线程数量是n，资源种类m，

最大的需求量、已经分配的、未来需要的构成一个等式

银行家算法：安全状态判断

Work是将已分配的量做一个拷贝，然后看在这个状态下，是不是可以满足当前已经分配过资源的这些线程的总的需求。如果能满足，表示当前状态下，可以把已经分配出去的资源，在用户用完之后能够收回来

寻找线程，来看未来需要的资源的总量，是否小于当前有的这些资源总量。如果能找到，则说明当前的某个进程是可以满足未来的所有需要的

如果没找到就转4.找到了转3，把资源放回到可用资源里，然后线程结束，然后再回来继续找

最后如果所有的线程都结束了，就说明安全

每一次请求时判断请求是否安全

举例说明

那么这个状态是否安全呢？我们需要判断，未来需要的量，和我当前所剩余的这些资源比较而言，是否可以找到一个序列，最后把所有资源收回

第一个可以找到T2，正好是所有资源都能满足的，它只要R3，而此时R3还有。

此时剩余的资源可以满足剩下的三个线程中的任何一个


最后一个没画，显然肯定能收回来

下面这个例子就是不安全的

T1请求R1和R3各一个，如果同意，那么剩的资源不满足其他任何一个进程

10.4 死锁检测

死锁检测算法用到的基本数据结构是

进程数为n,资源类型为m.首先对Work和Finish初始化，与上一节讲的一样，Work是可用的资源，并判断是否还占用资源，如果占用资源Finish就是false否则是true

然后去找没有结束的线程，是不是需要的资源量小于空闲的资源量，如果找了一圈都没有找到，那么可能会发生死锁了

如果找到了，那么这个进程占用的资源迟早会被释放掉，可以视为空闲资源了，因此Work扩充，并释线程

找了一圈，还是有某个进程不能分配足够资源，那就出现死锁了

如果资源量和线程数很大，那死锁检测的开销就会是很大的
举例说明



系统通常希望已经运行时间长的进程留下来，进程交互的进程继续进行下去

死锁恢复：资源抢占

20.5 进程通信的概念

进程通信(IPC, Inter-Process Communication)

通信方式
间接通讯：
一个进程把信息发送到内核的消息队列，另一个进程从内核里读出来。这种方式A和B的生命周期不用相同，也就是说A发送时B可能不存在，B接收时A可以关闭



间接通讯的通信流程如下

发放不关心收方是谁，只关心消息队列是谁

阻塞与非阻塞

直接通讯：
使用共享信道来通讯



通信链路缓冲
进程发送的消息在链路上可能有三种缓冲方式

20.6 信号与管道

操作系统提供的两种简单通讯机制

信号（Signal）

进程间的软件中断通知和处理机制
比如在Linux系统中 Ctrl + C能让一个进程停下来，但是实际代码中没有哪个地方是响应Ctrl + C的，这个处理是在哪实现的呢？这就是信号。操作系统在编译时，就规定了这些缺省的信号处理例程


Mask体现在，登录时按Ctrl C是不能停下来的，这就是因为屏蔽了

只是用来做一种快速的响应机制，比别的通讯机制要快

信号使用示例
signal.h 是注册信号处理例程的系统调用

管道（pipe）

进程间基于内存文件的通信机制

只关心通讯的管道是谁，并不关心另一头是谁在放数据

20.7 消息队列和共享内存

消息队列

在下图可以看出，多个进程往内核里发送消息，另一个进程按先进先出接收消息

共享内存

在线程中由于同一个进程，共享相同地址空间，则这种共享内存是天然的
而进程中要共享内存，则需要手动设置


不足是需要额外的同步机制，避免读写冲突之类的麻烦

靠页表项来使两个进程对应同一块地址空间