操作系统——进程与线程（死锁）

🕗 发布于 2024-07-22 23:50 linux 运维 服务器 蓝桥杯算法

1）为什么会产生死锁？产生死锁有什么条件？

2）有什么办法解决死锁？

一、死锁

死锁:多个程序因竞争资源而造成的一种僵局（互相等待对方手里的资源），使得各个进程都被阻塞，若无外力干涉，这些进程都无法向前推进。

就好比：一座桥上，一次性只能一辆汽车通过，这时两辆汽车分别都占据了桥的左右两边，都等着对方后退，而导致两辆汽车都无法前进。

死锁状态是指每个进程都在等待一个事件，而该事件只可能由组织内的一个进程产生。

饥饿的主要原因：当系统中有多个进程同时申请某类资源时，由分配策略分配给进程的次序，有的分配策略可能是不公平的，即不能保证等待时间上界的存在。

饥饿并不代表锁死，但至少有一个进程的执行是被无限期推迟的，而死锁至少说两个或两个以上的进程。

死锁和饥饿的差别：

1.发生饥饿的进程可以只有一个，而死锁是因为循环等待对方手里的资源导致的，因此如果有死锁现象，那么发生死锁的进程就必然大于或等于两个。

2.发生饥饿的进程可能处于就绪态（长期得不到CPU，如SJF短作业优先算法的问题），也可能处于阻塞态（如长期得不到所需的I/O设备）而发生死锁的进程必定处于阻塞态。

死锁产生的原因：

1）系统资源的竞争

通常系统中拥有的不可剥夺资源（如打印机，磁带机），其数量不可以满足多个进程运行的需要，使得进程在运行的过程中，会因争夺资源而陷入僵局。

只有对不可剥夺资源的竞争才可能产生死锁，对可剥夺资源竞争（如CPU和主存）不会引起死锁。

2）进程推进顺序非法

请求和释放资源的顺序不当就会导致死锁。eg：进程a和b分别保持了资源e和f，而a申请了资源f，b申请了资源e，两者都会因为所需资源被占用而阻塞，就导致死锁。

信号量使用不当也会导致死锁。进程间彼此相互等待对方发来的信息，也会导致进程无法继续向前推进。

死锁产生的必要条件：

1）互斥条件：即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。

2）不可剥夺条件：进程所获得的资源在未使用完前，不能被强行夺走，只能由进程自己来释放这个资源（只能是自动释放）。

3）请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源被别的进程占有，此时请求资源的进程就只能被阻塞，但对自己以获得的资源又保持不放。

4）循环等待条件：存在一种进程资源的循环等待链，链中每个进程以获得的资源同时被链中下一个进程所请求。

如：

每种资源只有一个，并出现了环路，可以确定出现了死锁。

但是又如当一个游离在循环等待队列之外的另一个进程手握资源出现时，就会打破这一死锁现象：

二、死锁的处理策略

1）死锁预防

四个死锁的必要条件中，无法破坏的是互斥使用资源（有些资源根本就不能被同时访问，如打印机就只能互斥使用，使用不能被破坏）

预防死锁的发生只需要破坏死锁产生的4个必要条件之一即可。

1.破坏互斥条件

如果互斥使用的资源改为运行共享使用，那么就不会进入死锁状态。但是有些资源根本不能同时访问，如打印机等临界资源只能互斥使用，所以破坏互斥条件而预防死锁的方法不太可行，为了系统安全很多时候都必须要保护这种互斥性。（但现在也有程序，能让进程假装认为进程可以连续不断的在打印机上工作，其实只是程序替进程保存了这些打印任务）

2.破坏不可剥夺条件

当一个已经保持了某些不可剥夺资源的进程，请求新的资源而得不到满足，他就必须释放已经保持的所有资源，待以后需要时在重新申请。这就意味着，进程已占有的资源会被暂时释放，或者是被剥夺了，从而破坏了不可剥夺条件。

但是该策略实现起来比较复杂。释放已获得的资源可能造成前一阶段的工作失效，因此这种方法常用于状态易于保存和恢复的资源，如CPU的寄存器及内存资源，一般不能用于打印机之类的资源。反复申请和释放资源即影响进程推进速度，又增加系统开销，进而降低系统吞吐量。

3.破坏请求并保持条件

1）采用预先静态分配法，即进程在运行前，一次申请完它所需要的全部资源，在他的资源未满足前，不让它投入运行。在进程运行期间，不会再提出资源请求，从而破坏请求条件。在等待期间，进程不占有任何资源，破坏了保持条件。

缺点：可能导致饥饿，个别资源长期被别的进程占用将导致等待该资源的进程迟迟不能开始。

2）允许进程只获得初期所需要的资源后，便可开始运行。进程在运行过程中再逐步释放已分配给自己且已使用完毕的全部资源后，才能请求新的资源。

4.破坏循环等待条件

为了破坏循环等待条件，可以采用顺序资源分配法。给系统中的各类资源进行编号，只有小编号资源才有资格申请大编号资源，这样就不会产生循环等待的现象。

缺点：编号必须相对稳定，因此不便于增加新的类型设备。按规定次序申请编号资源，还会给用户编程带来麻烦。

2）死锁避免

1.安全状态：系统能按某种进程推进，为每个进程pi分配其所需资源，直到满足每个进程对资源的最大需求，使每个资源都可以顺利完成。此时称为安全序列，否则就叫做不安全状态。

2.银行家算法（任何时刻都能保证至少有一个进程可以得到所需的全部资源）

1）Available：系统中有K个R类资源可用

2）Max：系统中R类资源最大数目为K

3）Allocation:表示进程已经分配R类资源的数目为K

4）Need：表示该进程还需要R类资源的数目为K

Need=Max-Allocation

做一题，就什么都明白了！~

三、死锁检测和解除

用圆圈表示一个进程，用框表示一类资源，框中的一个圆表示一类资源中的一个资源。

从进程到资源的有向边称为请求边，表示进程申请一个单位的该类资源；

从资源到进程的边称为分配边，表示已有一个资源分配给该进程。

如图就是p1可以被r2分配一个资源，从而消除p1的所有边，然后此时r1就会有空闲的两个资源可以被分配，其中p2已经请求一个资源让r1分配，那么当r1分配给p2时，p2也会结束所有关于它的边请求和分配任务。

此时加入p3，让r2分配了一个资源给p3，导致只有p3能被正常结束，p1和p2都会缺少r1与r2分配给他们的资源，其中，要消掉关于p1和p2进程，必须要有r1和r2中额外多出的资源来将p1和p2的请求给消除掉。

重点：

死锁公式：资源数大于进程个数乘以“每个进程需要的最大资源数减1”就不会发生死锁，

即m>n*(w-1);其中m是磁带机的数量，n是进程的数量，w是每个进程最多请求的磁带机数量

eg：某系统有n台互斥使用的同类设备，三个并发进程分别需要3，4，5台设备，可确保系统不发生死锁的设备数n最小为多少？

根据死锁公式，当资源数量大于个进程所需资源数-1的总和时，不发生死锁，三个进程分别需要3，4，5台设备，那么当资源数大于（3-1）+（4-1）+（5-1）=9时，不发生死锁，而当系统中只有9台设备时，当一个进程分配2台，第二个3台，第三个4台情况下，三个进程都无法继续执行下去，发生死锁，当系统再增加一台设备后，任意一个进程都可以顺利进行，因此不小于10台。