死锁问题

死锁产生的原因

• 进程管理是操作系统的核心，但如果设计不当，就会出现死锁问题。

• 死锁：由于多个进程共享资源而引起的进行不能向前推进的僵死状态（两个或两个进程因竞争资源而无休止的等待着其他进程释放已占有的资源）。

• 一个或多个进程产生死锁，就会造成系统死锁。

• A1$A_1$需要n1$n_1$个系统资源，A2$A_2$需要n2$n_2$个系统资源，A3$A_3$需要n3$n_3$个系统资源，……，Am$A_m$需要nm$n_m$个系统资源,则系统至少有（n1−1）+（n2−1）+...+(nm−1)+1$（n_1-1）+（n_2-1）+...+(n_m-1)+1$个资源，才能避免死锁。

例：系统有3个进行：A、B、C。这3个进程都需要5个系统资源。系统至少有13个资源，则不可能发生死锁。
分析：因3个进程都需要5个系统资源才能运行，则只要一个进程分配到5个资源得以运行，运行完毕后的资源均可分给其他两个进程，从而避免死锁。假设有12个系统资源，A、B、C三个进程均分配4个资源时，发生死锁。因此12个系统资源是一个瓶颈，系统再多一个资源时，A、B、C其中之一的进程就可运行。

• 死锁产生的条件：四个必要条件

  • 互斥条件：一个资源在一段时间内只能由一个进程占用。如果此时还有其他进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
  • 保持等待条件：各个进程保持自己的资源，当又提出了新的资源请求，而该资源已被其他进程占用，此时请求进程阻塞，但又对自己已获得的其他资源保持不放。
  • 不剥夺条件：进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
  • 环路等待条件：指在发生死锁时，进程集合{P0,P1,P2,...,Pn}$\{P_0,P_1,P_2,...,P_n\}$中P0$P_0$在等待一个P1$P_1$占用的资源，P1$P_1$在等待一个P2$P_2$占用的资源，……，Pn$P_n$在等待一个P0$P_0$占用的资源。

• 死锁的预防

  • 打破四个必要条件之一就能有效预防死锁的发生。
  • 打破互斥条件：各个进程可以同时使用资源。需要注意的是互斥条件是不能摒弃的，因为一旦摒弃互斥条件，有可能使访问临界资源的进程出现执行结果的错误。
  • 打破保持等待条件：当进程因请求不到资源处于请求阻塞状态时，主要将自己拥有的资源分配给其他资源。
  • 打破不可剥夺条件：当进行缺少资源时，可从其他进行剥夺相应资源使自己运行。
  • 打破环路等待条件：实现资源有序分配策略，A进程运行完再分配资源给B进程，B进程运行完再分配资源给C进行…

• 死锁的避免

  • 有序资源分配法:A进程运行完再分配资源给B进程，B进程运行完再分配资源给C进行…，可以有效避免死锁，但资源利用率低。
  • 银行家算法。
    
    

• 银行家算法

  • 利用银行家算法避免死锁的基本思想是：一个进程提出资源请求后，系统先进行资源的试分配，然后检查本次的试分配是否使系统处于安全状态，若安全则按试分配方案分配资源，否则不分配资源。
  • 银行家算法缺少实用价值：很少有进程能够在运行之前就知道其所需资源的最大值，而且进程数不是固定的，往往在不断变化，况且原本可用的资源也可能突然间变得不可用。
  • 安全状态转不安全状态