死锁详解

女爷i 2022-09-24 12:27 170阅读 0赞

1.定义：所谓死锁： 是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。

**官方定义：**死锁的规范定义：集合中的每一个进程都在等待只能由本集合中的其他进程才能引发的事件，那么该组进程是死锁的。

2.产生死锁的原因主要是：

（1） 因为系统资源不足。  
（2） 进程运行推进的顺序不合适。  
（3） 资源分配不当等。  
如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则  
就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。  
3.产生死锁的四个必要条件：  
（1） 互斥条件：一个资源每次只能被一个进程使用。  
（2） 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。  
（3） 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。  
（4） 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。  
这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之  
一不满足，就不会发生死锁。  
**4.死锁的解除与预防：**  
理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和  
解除死锁。所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确  
定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态  
的情况下占用资源。因此，对资源的分配要给予合理的规划。

具体方法：

只要打破四个必要条件之一就能有效预防死锁的发生：打破互斥条件：改造独占性资源为虚拟资源，大部分资源已无法改造。打破不可抢占条件：当一进程占有一独占性资源后又申请一独占性资源而无法满足，则退出原占有的资源。打破占有且申请条件：采用资源预先分配策略，即进程运行前申请全部资源，满足则运行，不然就等待，这样就不会占有且申请。**打破循环等待条件：**实现资源有序分配策略，对所有设备实现分类编号，所有进程只能采用按序号递增的形式申请资源

### 有序资源分配法 ###

这种算法资源按某种规则系统中的所有资源统一编号（例如打印机为1、[磁带机][Link 1]为2、磁盘为3、等等），申请时必须以上升的次序。系统要求申请进程：

1、对它所必须使用的而且属于同一类的所有资源，必须一次申请完；

2、在申请不同类资源时，必须按各类设备的编号依次申请。例如：进程PA，使用资源的顺序是R1，R2； 进程PB，使用资源的顺序是R2，R1；若采用动态分配有可能形成环路条件，造成死锁。

采用有序资源分配法：R1的编号为1，R2的编号为2；

PA：申请次序应是：R1，R2

PB：申请次序应是：R1，R2

这样就破坏了环路条件，避免了死锁的发生

### 银行家算法 ###

避免死锁算法中最有代表性的算法是Dijkstra E.W 于1968年提出的[银行家算法][Link 2]：

银行家算法是避免死锁的一种重要方法，防止死锁的机构只能确保上述四个条件之一不出现，则系统就不会发生死锁。通过这个算法可以用来解决生活中的实际问题，如银行贷款等。

程序实现思路银行家算法顾名思义是来源于银行的借贷业务，一定数量的本金要应多个客户的借贷周转，为了防止银行家资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题**，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其他进程使用资源**。如果资源分配不得到就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。

把一个**进程需要和已占有资源的情况记录在进程控制中**，假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时，表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然，每个进程的资源需求总量不能超过系统拥有的资源总数， 银行算法进行资源分配可以避免死锁。

5.检测和解除死锁。

**先检测：**这种方法并不须事先采取任何限制性措施，也不必检查系统是否已经进入不安全区，此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源。检测方法包括定时检测、效率低时检测、进程等待时检测等。

**然后解除死锁：**采取适当措施，从系统中将已发生的死锁清除掉。

这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于[阻塞状态][Link 3]的进程，使之转为[就绪状态][Link 4]，以继续运行。死锁的检测和解除措施，有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

**排除方法：**

1、撤消陷于死锁的全部进程；

2、逐个撤消陷于死锁的进程，直到死锁不存在；

3、从陷于死锁的进程中逐个强迫放弃所占用的资源，直至死锁消失。

4、从另外一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态

死锁实例：

public class deadLock implements Runnable {
    	private int flag;
    	static Object o1 = new Object(), o2 = new Object(); // 静态的对象
    	public void run() {
    		System.out.println(flag);
    		if (flag == 0) {
    			synchronized (o1) {
    				try {所以在thread0线程启动的时候执行的是run()方法前半部分的代码，
    					Thread.sleep(500);
    					System.out.println(Thread.currentThread().getName()+"在执行");
    				} catch (Exception e) {
    					e.printStackTrace();
    				}
    				synchronized (o2) {//此时，出现了下列现象：thread1线程占有了o1对象并等待o2对象，
    				}
    			}
    		}
    		if (flag == 1) {//所以在thread0线程执行的时候执行的是执行此run()方法，flag等于1，
    			synchronized (o2) {//而thread1线程占有了o2对象并等待o1对象，而o1和o2又被这俩个线程所共享，所以就出现了死锁的问题了。
    				try {
    					Thread.sleep(500);
    					System.out.println(Thread.currentThread().getName()+"在执行");
    				} catch (Exception e) {
    					e.printStackTrace();
    				}
    				synchronized (o1) {
    				}
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		deadLock test1 = new deadLock();//在main方法中，实例化了两个实现了Runnable接口的deadLock对象test1和test2，test1的flag等于1，
    		deadLock test2 = new deadLock();
    		test1.flag = 1;
    		test2.flag = 0;
    		Thread thread1 = new Thread(test1);
    		Thread thread2 = new Thread(test2);
    		thread1.start();
    		thread2.start();
    	}
    }

0  
1  
Thread-1在执行  
Thread-0在执行

[Link 1]: http://baike.baidu.com/view/220750.htm
[Link 2]: http://baike.baidu.com/view/93075.htm
[Link 3]: http://baike.baidu.com/view/1624711.htm
[Link 4]: http://baike.baidu.com/view/636815.htm