进程管理----死锁

系统管理员 2023-01-17 06:30 185阅读 0赞

# ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzIyMjE3_size_16_color_FFFFFF_t_70][] #

# 1.死锁、饥饿、死循环 #

<table> 
 <tbody> 
  <tr> 
   <td style="width:90px;">&nbsp;</td> 
   <td style="width:161px;">共同点</td> 
   <td> <p>区别</p> </td> 
  </tr> 
  <tr> 
   <td style="width:90px;">死锁</td> 
   <td colspan="1" style="width:161px;"> <p>都是进程无法顺利向前推进的现象</p> <p>（故意设计的死循环除外）</p> </td> 
   <td>一定是“循环等待对方手里的资源"导致的，因此如果有死锁现象，那<span style="color:#f33b45;">至少有两个或两个以上的进程同时发生死锁</span>。另外，发生死锁的进程一定处于阻塞态。</td> 
  </tr> 
  <tr> 
   <td style="width:90px;">饥饿</td> 
   <td><span style="color:#f33b45;">可能只有一个进程发生饥饿</span>。发生饥饿的进程既可能是阻塞态(如长期得不到推进的现象需要的I/O设备)，也可能是就绪态(长期得不到处理机)</td> 
  </tr> 
  <tr> 
   <td style="width:90px;">死循环</td> 
   <td>可能只有一个进程发生死循环。死循环的进程可以上处理机运行(可以是运行态)，只不过无法像期待的那样顺利推进。死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。<span style="color:#f33b45;">死锁和饥饿是管理者(操作系统)的问题，死循环是被管理者的问题。</span></td> 
  </tr> 
 </tbody> 
</table>

# 2.预防死锁的两种方式及优缺点 #

<table> 
 <tbody> 
  <tr> 
   <td style="width:181px;">&nbsp;</td> 
   <td style="width:359px;">方案</td> 
   <td>缺点</td> 
  </tr> 
  <tr> 
   <td style="width:181px;">破坏互斥条件</td> 
   <td style="width:359px;">将资源改造为共享使用资源（如SPOOLing技术）</td> 
   <td>可行性不高，很多时候无法破坏互斥条件</td> 
  </tr> 
  <tr> 
   <td colspan="1" style="width:181px;">破坏不剥夺条件</td> 
   <td style="width:359px;">申请的资源得不到满足时，立即释放所拥有的资源</td> 
   <td colspan="1">实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放资源导致系统开销大；可能导致饥饿</td> 
  </tr> 
  <tr> 
   <td style="width:359px;">申请的资源被其他进程占用时，由操作系统协助剥夺</td> 
  </tr> 
  <tr> 
   <td style="width:181px;">破坏请求和保持条件</td> 
   <td style="width:359px;">运行前分配好所有需要的资源，之后一直保持</td> 
   <td>资源利用率低，可能导致饥饿</td> 
  </tr> 
  <tr> 
   <td style="width:181px;">破坏循环等待条件</td> 
   <td style="width:359px;">给资源编号，必须按照编号从小到大的顺序申请资源</td> 
   <td>不方便增加新设备；会导致资源浪费；用户编程麻烦</td> 
  </tr> 
 </tbody> 
</table>

# 3.银行家算法 #

假设系统中有n个进程，m种资源  
每个进程在运行前先声明对各种资源的最大需求数，则可用一个n\*m的矩阵(可用二维数组实现)表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max，Max\[i, j\]=K表示进程Pi最多需要K个资源Rj。同理，系统可以用一个n\*m的分配矩阵Allocation表示对所有进程的资源分配情况。Max - Allocation=Need 矩阵，表示各进程最多还需要多少各类资源。另外，还要用一个长度为m的一维数组Available表示当前系统中还有多少可用资源。  
某进程Pi向系统申请资源，可用一个长度为m的一维数组Request表示本次申请的各种资源量。

例子：系统中有5个进程P0~P1，3种资源R0~R2，初始量为（10,5,7），在某一时刻的情况如下表：

已使用（7，2 ，5）

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>&nbsp;</td> 
   <td colspan="3"><span style="color:#3399ea;">Available = （3,3,2）&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Request(0) = （7,4,3）</span></td> 
  </tr> 
  <tr> 
   <td>&nbsp;</td> 
   <td><span style="color:#3399ea;">Max矩阵</span></td> 
   <td><span style="color:#3399ea;">Allocation矩阵</span></td> 
   <td><span style="color:#3399ea;">Need矩阵</span></td> 
  </tr> 
  <tr> 
   <td>进程</td> 
   <td>最大需求</td> 
   <td> <p>已分配</p> </td> 
   <td> <p>最多还需要</p> </td> 
  </tr> 
  <tr> 
   <td>P0</td> 
   <td>（7,5,3）</td> 
   <td>（0,1,0）</td> 
   <td>（7,4,3）</td> 
  </tr> 
  <tr> 
   <td>P1</td> 
   <td>（3,2,2）</td> 
   <td>（2,0,0）</td> 
   <td>（1,2,2）</td> 
  </tr> 
  <tr> 
   <td>P2</td> 
   <td>（9,0,2）</td> 
   <td>（3,0,2）</td> 
   <td>（6,0,0）</td> 
  </tr> 
  <tr> 
   <td>P3</td> 
   <td>（2,2,2）</td> 
   <td>（2,1,1）</td> 
   <td>（0,1,1）</td> 
  </tr> 
  <tr> 
   <td>P4</td> 
   <td>（4,3,3）</td> 
   <td>（0,0,2）</td> 
   <td>（4,3,1）</td> 
  </tr> 
 </tbody> 
</table>

可用银行家算法预判本次分配是否会导致系统进入不安全状态:

①如果Request(i)\[j\] <= Need\[i, j\] (0 <= j <= m)便转向②:否则认为出错。  
  
②如果Request(i)\[j\] <= Available\[j\] (0 <= j <= m),便转向③;否则表示尚无足够资源，Pi必须等待。  
  
③系统试探着把资源分配给进程Pi，并修改相应的数据(并非真的分配，修改数值只是为了做预判) :

Available        = Available - Request(i);

Allocation\[i, j\] = Allocation\[i, j\] + Request(i)\[j\];

Need\[i, j\]         = Need\[i, j\] - Request(i)\[j\]

④操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式分配:否则，恢复相应数据，让进程阻塞等待。

最终可选出一个安全序列P1、P3、P0、P2、P4

# 4.死锁检测算法 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzIyMjE3_size_16_color_FFFFFF_t_70 1][]

按照P1、P2的顺序资源分配 图可化简为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzIyMjE3_size_16_color_FFFFFF_t_70 2][]

称该图是可完全简化的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzIyMjE3_size_16_color_FFFFFF_t_70]: /images/20221021/3d5dcd381d914778b7a450965f195e1e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzIyMjE3_size_16_color_FFFFFF_t_70 1]: /images/20221021/3106f8bc817a4afebec71bac22779602.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzIyMjE3_size_16_color_FFFFFF_t_70 2]: /images/20221021/daf56cd865d94483aec63b1a5f74c8d1.png