操作系统复习：死锁

1 死锁的概念

1.1 死锁的基本概念

• 个数至少为2个；
• 至少有两个进程已经占有资源；

操作系统设计中必须高度重视死锁问题

1.2 死锁的产生原因

1. 竞争资源，系统提供的资源有限
2. 多道程序运行时，进程推进顺序不合理

• 资源：永久性资源（CPU，IO设备，内存，文件，信号量）/临时性资源（信号，中断，消息）；都可能导致死锁发生

1.3 引发死锁的必要条件

1. 互斥条件
2. 不可剥夺条件
3. 请求和保持条件
4. 循环等待条件

(4)中蕴含了前三项的成立。列出必要条件的目的是，在操作系统的设计中可以破坏掉这些条件来达到预防死锁的效果。

2 解决死锁问题的方法

2.1 死锁预防

从引发死锁的必要条件入手。

（1）互斥使用/资源独占条件

一般来说是资源使用的固有特性，由资源本身决定而不由软件决定。

但是某些条件下，可以应用资源转换技术，将独占资源变为共享资源。

eg.SPOOLing技术（假脱机技术）的引入；解决不允许任何进程直接占有打印机的问题

（2）不可剥夺条件：

• ​ 实现：调度时帮后来者抢夺先来者的资源

• ​ 使用资源：CPU、内存等容易保存和恢复的资源

  这个策略一般是对虚拟化资源应用，即与其说是“抢夺”，不如说是“借用”，不影响对方稍后将工作进行完毕

• ​ 缺点：策略复杂，代价大；有可能造成先来者的饥饿问题

（3）请求和保持条件：

• 静态分配资源策略：
  • 运行前就给定所有资源
  • 系统工作效率低
• 动态分配资源策略
  • 运行中申请新资源前必须归还旧资源
  • 申请的新资源正被占用的话仍会需要较长的等待新资源的时间

（4）循环等待条件

• 资源有序分配法：为资源按照紧缺程度编号，编号大代表稀缺。进程申请资源必须按照从小到大的顺序，只有当进程拥有编号较小的资源时才能申请编号较大的资源；释放资源按照编号递减的顺序进行。

• 合理编号比较困难；进程为了得到高级资源，暂不需要的资源也*要申请，造成资源的浪费。

2.2 死锁避免

2.2.1 安全，不安全与死锁状态

在多道程序工作中，我们让每一时刻都对应一个状态，这个状态，用每个进程对资源的占用情况来表示。

如果存在一个进程序列，使得系统剩余资源按顺序地服务序列中的进程，能保证服务完成，这就是安全状态。

不安全状态对应着无论怎样的进程序列，系统总会在服务到某一个进程时发现自己已经不能提供足够的资源了，此时就到达了死锁状态。

我们要避免死锁，就是避免资源调度中系统从安全状态进入不安全状态。

（具体策略比如在临界情况下拒绝分配资源，等待别的资源的回收，不过银行家算法就详细地介绍了实现）

2.2.2 银行家算法

#银行家算法
def Banker(i,request[i]):
    if request[i]>need[i]:
        return Request_Amount_Error
    while request[i]>available:
        Wait
        if wait_time > SETTIME:
            return Time_Exceeding_Error
    # try to allocate 
    while(True):
        available -= request[i]
    	allocation[i] += request[i]
    	need[i] -= request[i]
        work:=available
    	if not SafetyTest(work,n):
    		available += request[i]
    		allocation[i] -= request[i]
    		need[i] += request[i]
        	Wait
            if wait_time > SETTIME:
            	return Time_Exceeding_Error
   return Allocate_Completion

#安全性算法
def SafetyTest(n):
    if n==0:
        return True
    for i in process:
        if finish[i]==False and need[i]<=work:
            work+=allocation[i] # 当前进程运行结束后归还资源
            finish[i]=True
        	SafetyTest(n-1)
            work-=allocation[i]
            finish[i]=False

2.3 死锁检测

资源分配表（资源–正在占用它的进程）+进程等待表（进程–等待的资源），两表交错取边构成环时，形成死锁。

死锁解除：1 剥夺资源 2 撤销进程

3 资源分配图

在资源点和进程点之间连接有向边，资源->进程的是分配边，进程->资源的是申请边。

3.1 环路

在资源点仅有单一资源的分配图中，环路是死锁的充分必要条件；而资源点上有多个相同资源的分配图中，环路仅仅是死锁的必要条件。

3.2 可化简与不可化简

# 化简算法
def Simplify(map):
    if map in None:
        return True
    p<-None
    for every process in process_set:
        if process.status is not WAIT:
            p<-process
            break
    if p is None:
        return False
    map.delete(p)        # Allocate_Resource(process)
    return Simplify(map) # map_size -= 1