我的回答

一、什么是死锁?

死锁是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程。是操作系统层面的一个错误,是进程死锁的简称,最早在 1965 年由 Dijkstra 在研究银行家算法时提出的,它是计算机操作系统乃至整个并发程序设计领域最难处理的问题之一。

事实上,计算机世界有很多事情需要多线程方式去解决,因为这样才能最大程度上利用资源,才能体现出计算的高效。但是,实际上来说,计算机系统中有很多一次只能由一个进程使用的资源的情况,例如打印机,同时只能有一个进程控制它。在多通道程序设计环境中,若干进程往往要共享这类资源,而且一个进程所需要的资源还很有可能不止一个。因此,就会出现若干进程竞争有限资源,又推进顺序不当,从而构成无限期循环等待的局面。我们称这种状态为死锁。简单一点描述,死锁是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然,如果没有外力的作用,那么死锁涉及到的各个进程都将永远处于封锁状态。

系统发生死锁现象不仅浪费大量的系统资源,甚至导致整个系统崩溃,带来灾难性后果。所以,对于死锁问题在理论上和技术上都必须予以高度重视。

二、死锁发生的原因?

A:java 死锁产生的四个必要条件

1、互斥使用,即当资源被一个线程使用(占有)时,别的线程不能使用
2、不可抢占,资源请求者不能强制从资源占有者手中夺取资源,资源只能由资源占有者主动释放。
3、请求和保持,即当资源请求者在请求其他的资源的同时保持对原有资源的占有。
4、循环等待,即存在一个等待队列:P1占有P2的资源,P2占有P3的资源,P3占有P1的资源。这样就形成了一个等待环路。

B:产生原因:

1. 竞争资源引起进程死锁

当系统中供多个进程共享的资源如打印机、公用队列的等,其数目不足以满足诸进程的需要时,会引起诸进程对资源的竞争而产生死锁。

可剥夺资源和不可剥夺资源

系统中的资源可以分为两类,一类是可剥夺资源,是指某进程在获得这类资源后,该资源可以再被其他进程或系统剥夺。例如,优先权高的进程可以剥夺优先权低的进程的处理机。又如,内存区可由存储器管理程序,把一个进程从一个存储区移到另一个存储区,此即剥夺了该进程原来占有的存储区,甚至可将一进程从内存调到外存上,可见,CPU和主存均属于可剥夺性资源。另一类资源是不可剥夺资源,当系统把这类资源分配给某进程后,再不能强行收回,只能在进程用完后自行释放,如磁带机、打印机等。

竞争不可剥夺资源

在系统中所配置的不可剥夺资源,由于它们的数量不能满足诸进程运行的需要,会使进程在运行过程中,因争夺这些资源而陷于僵局。例如,系统中只有一台打印机R1和一台磁带机R2,可供进程P1和P2共享。假定PI已占用了打印机R1,P2已占用了磁带机R2,若P2继续要求打印机R1,P2将阻塞;P1若又要求磁带机,P1也将阻塞。于是,在P1和P2之间就形成了僵局,两个进程都在等待对方释放自己所需要的资源,但是它们又都因不能继续获得自己所需要的资源而不能继续推进,从而也不能释放自己所占有的资源,以致进入死锁状态。

竞争临时资源

上面所说的打印机资源属于可顺序重复使用型资源,称为永久资源。还有一种所谓的临时资源,这是指由一个进程产生,被另一个进程使用,短时间后便无用的资源,故也称为消耗性资源,如硬件中断、信号、消息、缓冲区内的消息等,它也可能引起死锁。例如,SI,S2,S3是临时性资源,进程P1产生消息S1,又要求从P3接收消息S3;进程P3产生消息S3,又要求从进程P2处接收消息S2;进程P2产生消息S2,又要求从P1处接收产生的消息S1。如果消息通信按如下顺序进行:
P1: ···Relese(S1);Request(S3); ···
P2: ···Relese(S2);Request(S1); ···
P3: ···Relese(S3);Request(S2); ···
并不可能发生死锁。但若改成下述的运行顺序:
P1: ···Request(S3);Relese(S1);···
P2: ···Request(S1);Relese(S2); ···
P3: ···Request(S2);Relese(S3); ···
则可能发生死锁。

2.进程推进顺序不当引起死锁

由于进程在运行中具有异步性特征,这可能使P1和P2两个进程按下述两种顺序向前推进。

1) 进程推进顺序合法

当进程P1和P2并发执行时,如果按照下述顺序推进:P1:Request(R1); P1:Request(R2); P1: Relese(R1);P1: Relese(R2); P2:Request(R2); P2:Request(R1); P2: Relese(R2);P2: Relese(R1);这两个进程便可顺利完成,这种不会引起进程死锁的推进顺序是合法的。

2) 进程推进顺序非法

若P1保持了资源R1,P2保持了资源R2,系统处于不安全状态,因为这两个进程再向前推进,便可能发生死锁。例如,当P1运行到P1:Request(R2)时,将因R2已被P2占用而阻塞;当P2运行到P2:Request(R1)时,也将因R1已被P1占用而阻塞,于是发生进程死锁。

三、如何避免(预防)和解决死锁?

A:死锁预防

理解了死锁的原因,尤其是产生死锁的四个必要条件,就可以最大可能地避免、预防和解除死锁。只要打破四个必要条件之一就能有效预防死锁的发生:打破互斥条件:改造独占性资源为虚拟资源,大部分资源已无法改造。打破不可抢占条件:当一进程占有一独占性资源后又申请一独占性资源而无法满足,则退出原占有的资源。打破占有且申请条件:采用资源预先分配策略,即进程运行前申请全部资源,满足则运行,不然就等待,这样就不会占有且申请。打破循环等待条件:实现资源有序分配策略,对所有设备实现分类编号,所有进程只能采用按序号递增的形式申请资源。 [3]
所以,在系统设计、进程调度等方面注意如何不让这四个必要条件成立,如何确定资源的合理分配算法,避免进程永久占据系统资源。此外,也要防止进程在处于等待状态的情况下占用资源,在系统运行过程中,对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源,若分配后系统可能发生死锁,则不予分配,否则予以分配。因此,对资源的分配要给予合理的规划。
下面几种方法可用以避免重装死锁的发生:
①允许目的节点将不完整的报文递交给目的端系统;
②一个不能完整重装的报文能被检测出来,并要求发送该报文的源端系统重新传送;
③为每个节点配备一个后备缓冲空间,用以暂存不完整的报文。
①、②两种方法不能很满意地解决重装死锁,因为它们使端系统中的协议复杂化了。一般的设计中,网络层应该对端系统透明,也即端系统不该考虑诸如报文拆、装之类的事。③方法虽然不涉及端系统,但使每个节点增加了开销。
有序资源分配法
这种算法资源按某种规则系统中的所有资源统一编号(例如打印机为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年提出的银行家算法:
银行家算法是避免死锁的一种重要方法,防止死锁的机构只能确保上述四个条件之一不出现,则系统就不会发生死锁。通过这个算法可以用来解决生活中的实际问题,如银行贷款等。
程序实现思路银行家算法顾名思义是来源于银行的借贷业务,一定数量的本金要应多个客户的借贷周转,为了防止银行家资金无法周转而倒闭,对每一笔贷款,必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题,系统中有限的资源要供多个进程使用,必须保证得到的资源的进程能在有限的时间内归还资源,以供其他进程使用资源。如果资源分配不得到就会发生进程循环等待资源,则进程都无法继续执行下去的死锁现象。
把一个进程需要和已占有资源的情况记录在进程控制中,假定进程控制块PCB其中“状态”有就绪态、等待态和完成态。当进程在处于等待态时,表示系统不能满足该进程当前的资源申请。“资源需求总量”表示进程在整个执行过程中总共要申请的资源量。显然,每个进程的资源需求总量不能超过系统拥有的资源总数, 银行算法进行资源分配可以避免死锁。

B:解决方法

在系统中已经出现死锁后,应该及时检测到死锁的发生,并采取适当的措施来解除死锁。
死锁预防
这是一种较简单和直观的事先预防的方法。方法是通过设置某些限制条件,去破坏产生死锁的四个必要条件中的一个或者几个,来预防发生死锁。预防死锁是一种较易实现的方法,已被广泛使用。但是由于所施加的限制条件往往太严格,可能会导致系统资源利用率和系统吞吐量降低。
死锁避免
系统对进程发出的每一个系统能够满足的资源申请进行动态检查,并根据检查结果决定是否分配资源;如果分配后系统可能发生死锁,则不予分配,否则予以分配。这是一种保证系统不进入死锁状态的动态策略。
死锁检测和解除
先检测:这种方法并不须事先采取任何限制性措施,也不必检查系统是否已经进入不安全区,此方法允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构,及时地检测出死锁的发生,并精确地确定与死锁有关的进程和资源。检测方法包括定时检测、效率低时检测、进程等待时检测等。
然后解除死锁:采取适当措施,从系统中将已发生的死锁清除掉。
这是与检测死锁相配套的一种措施。当检测到系统中已发生死锁时,须将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程,以便回收一些资源,再将这些资源分配给已处于阻塞状态的进程,使之转为就绪状态,以继续运行。死锁的检测和解除措施,有可能使系统获得较好的资源利用率和吞吐量,但在实现上难度也最大。

如果我们在死锁检查时发现了死锁情况,那么就要努力消除死锁,使系统从死锁状态中恢复过来。消除死锁的几种方式:

最简单、最常用的方法就是进行系统的重新启动,不过这种方法代价很大,它意味着在这之前所有的进程已经完成的计算工作都将付之东流,包括参与死锁的那些进程,以及未参与死锁的进程;

撤消进程,剥夺资源。终止参与死锁的进程,收回它们占有的资源,从而解除死锁。这时又分两种情况:一次性撤消参与死锁的全部进程,剥夺全部资源;或者逐步撤消参与死锁的进程,逐步收回死锁进程占有的资源。一般来说,选择逐步撤消的进程时要按照一定的原则进行,目的是撤消那些代价最小的进程,比如按进程的优先级确定进程的代价;考虑进程运行时的代价和与此进程相关的外部作业的代价等因素;

进程回退策略,即让参与死锁的进程回退到没有发生死锁前某一点处,并由此点处继续执行,以求再次执行时不再发生死锁。虽然这是个较理想的办法,但是操作起来系统开销极大,要有堆栈这样的机构记录进程的每一步变化,以便今后的回退,有时这是无法做到的。

其实即便是商业产品,依然会有很多死锁情况的发生,例如 MySQL 数据库,它也经常容易出现死锁案例。

参考回答

死锁

如果一组进程中每一个进程都在等待仅由该组进程中的其他进程才能引发的事件,那么该组进程是死锁的。换言之:死锁就是两个线程同时占用两个资源,但又在彼此等待对方释放锁。
举例来说:有两个进程 A 和 B,A 持有资源 a 等待 b 资源,B 持有资源 b 等待 a 资源,两个进程都在等待另一个资源的同时不释放资源,就形成死锁。

1.死锁产生的四个必要条件

  • 互斥条件:一个资源每次只能被一个进程使用。
  • 请求和保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放
  • 不剥夺条件:进程已获得的资源,在未使用完之前,不能强行剥夺
  • 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系

    2.死锁处理

    预防死锁:破坏四个必要条件中的一个或多个来预防死锁
    避免死锁:在资源动态分配的过程中,用某种方式防止系统进入不安全的状态
    检测死锁:运行时产生死锁,及时发现死锁,将程序解脱出来。
    解除死锁:发生死锁时,撤销进程,回收资源,分配给正在阻塞状态的进程。

预防死锁

1.预防死锁的方法:

破坏请求和保持条件:一次性的申请所有资源,之后不在申请资源,如果不满足资源条件则得不到资源分配。只获得初期资源运行,之后将运行完的资源释放,请求新的资源

破坏不可抢占条件:当一个进程获得某种不可抢占资源,提出新的资源申请,若不能满足,则释放所有资源,以后需要的时候则再次重新申请。

破坏循环等待条件:对资源进行排号,按照序号递增的顺序请求资源。若进程获得序号高的资源想要获取序号低的资源,则需要先释放序号高的资源。

2.死锁的解除方法:

抢占资源。从一个或多个进程中抢占足够数量的资源,分配给死锁进程,以解除死锁状态

终止(撤销)进程:将一个或多个死锁进程终止(撤销),直至打破循环环路,使系统从死锁状态解脱