欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

操作系统-4——并发:死锁和饥饿

程序员文章站 2022-04-20 11:53:35
...

一、死锁

1、死锁原理

  • 当一组进程中的每个进程都在等待某个事件(所请求的资源被释放),而只有在这组进程中的其他阻塞进程才能触发该事件,而只有这组进程中的其他阻塞进程才能触发该事件,称这组进程发生死锁。
  • 死锁涉及两个或多个进程之间的资源需求冲突。
  • 死锁原因:竞争资源,进程推进顺序不当。

2、资源

  • 资源分为两类:可重用资源和可消耗资源
2.1 可重用资源
  • 可重用资源:指可重复使用,互斥使用的资源。如CPU,虚拟内存,磁盘等。【打印机,磁带机,文件,数据库,信号量等】(属于不可剥夺资源:如果被剥夺,会引起进程失败。)
  • 竞争不可剥夺资源可能导致死锁。

?#为什么死锁不会涉及虚拟内存或磁盘?

2.2 可消耗资源

  • 可消耗资源:可被创建(生产)和销毁(消费)的资源。如消息、信号、缓冲数据等。
  • 竞争可消耗资源也可能导致死锁。

2.3  资源分配图

有向图,描述资源和进程状态。

  • 进程节点:P
  • 资源节点:R。 一个圆点表示一个资源实例。
  • 请求边:进程->资源。 Pi -> Rj
  • 分配边: 资源 ->进程。 Rj -> Pi

操作系统-4——并发:死锁和饥饿

  • 若死锁、则资源分配图中必有环。
  • 但有环路时并不一定死锁,要看是否进程都阻塞而无法运行。

操作系统-4——并发:死锁和饥饿

3、死锁的条件

  • 互斥:涉及的是需要互斥访问的临界资源。
  • 占有并等待:进程申请资源而阻塞(等待)时,不释放(继续占有)已分配资源。
  • 不可抢占:进程已占有的资源未使用完前不可强行剥夺(抢占),只能有进程资源释放。
  • 循环等待:进程间形成一个等待资源的循环链。

死锁时,以上四个必要条件同时成立。某一个或几个必要条件成立时并未进入死锁状态。

3.1 死锁的三个处理方法

  • 死锁预防:破坏四个必要条件之一。
  • 死锁避免:不破坏必要条件,允许进程动态申请资源,但检查资源分配状态,以避免可能导致的死锁。
  • 死锁检查和恢复:检查系统是否已死锁、那些进程和资源涉及死锁,并撤销死锁进程或剥夺资源以摆脱死锁。
其实还有一种被包括windows,unix等OS采用的方法就是忽略死锁:假设死锁不会发生

4、死锁预防

破坏四个必要条件的其中一个。

4.1 破坏互斥

    互斥条件不可破坏。因为一旦互斥条件破坏,就不存在多道程序设计了。

4.2 破坏占有且等待

    ①资源静态分配法:程序运行前,一次性分配所有需要的资源。若有某个资源不能满足,则全部不分配。进程等待直至所有资源可用。

  • 可能会引起进程饥饿;资源利用率低。
  • 进程可能事先不知道所需要的资源列表。

4.3 破坏不可抢占

  • 进程申请新资源被阻塞时,必须(主动)释放已占有的资源。本进程需要时再重新申请。
  • OS剥夺低优先级进程的资源给高优先级进程。

4.4 破坏循环等待

   ①资源有序分配法:系统内每个资源一个编号,各进程必须严格按照编号递增的顺序申请资源。

!#死锁≠死机

5、死锁避免

    系统运行进程动态申请资源。在分配资源之前,先计算资源分配的安全性。若此次分配可能导致死锁,则暂不分配,该进程等待

    两种死锁避免方法:

    ①进程启动拒绝:如果一个新进程的资源最大需求总量会导致死锁,则不启动此新进程。

    ②资源分配拒绝:如果一个进程提出的某次资源请求会导致死锁,则不允许此次分配。(更常用)

5.1 进程启动拒绝

定义以下向量和矩阵:n——进程数;m——资源类型数

  • 资源总量Resource = R = (R1,R2,...,Rm)
  • 可用资源Available = V = (V1,V2,...,Vm)
  • 最大需求矩阵Claim = C = :n*m 的矩阵 ——C[i,j] = k 表示进程 i 需要第 j 类资源最多为k个。
  • 已分配矩阵Allocation = A = n*m的矩阵 ——A[i,j] = k 表示进程 i 已分得第 j 类资源 k 个。
  • 操作系统-4——并发:死锁和饥饿

当系统的资源总量能够满足“所有进程的最大需求量加上新进程Pn+1的最大需求量”时,才能启动新进程Pn+1。

(即所有进程申请的资源最大需求量之和不能大于系统的资源总量。)

操作系统-4——并发:死锁和饥饿

?#进程启动拒绝和资源静态分配有什么区别???

5.2 资源分配拒绝

  • 银行家算法:分配资源前,先计算此次分配是否会导致系统处于不安全状态。若安全则分配,否则不分配(事先评估)。
  • 安全状态:存在一个由所有进程(P1,P2,...,Pn)构成的安全序列,如果系统安装这个顺序为每个进程分配所需资源,直至该进程声明的最大资源需求量,则可以使每个进程都运行完。
  • 不安全状态:系统不存在任何一个安全序列,使得所有进程都能够运行完。

!#不安全状态≠死锁状态

进程提出资源分配请求后,OS先试探性分配,若仍处于“安全状态”才分配,否则暂不分配,进程等待

操作系统-4——并发:死锁和饥饿

  • 安全性测试算法(银行家算法)

boolean safe(state S){
	int currentavail[m];//系统可用资源数目(临时记录,非真实)
	process rest[进程总数];//剩余的,未运行完毕的进程集合
	currentavail = available;//开始时,currentavail = 实际的可用资源
	rest = {所有进场};//开始时,所有进程都尚未运行完毕
	possible = true;
	while(possible){
		<在rest中(循环)查找一个进程Pk,满足claim[k,*]-alloc[k,*]<= currentavail;>
		//其资源需求可被满足
		if(found){//如果有这样的进程Pk,则认为它能够运行完毕
			currentavail = currentavail+alloc[k,*];//并释放其已分配的资源
			rest=rest-{Pk};//从rest集合中去掉“已运行完的”进程Pk
		}
		else possible = false;//如果没有找到这样的进程Pk,则结束循环
	}
	return (rest == null);//若rest为空,则为安全状态,否则不安全
}

6、死锁检测

只要所请求资源可用,则分配给进程。OS定期运行死锁检测算法,判断是否存在死锁。

死锁检测算法类似于银行家算法。

6.1恢复

解除死锁:代价最小地撤销进程、剥夺资源。

  • 终止所有死锁进程。
  • 每个死锁进程回滚到某个安全状态的“检查点”(周期性将内存映像、资源状态等写入文件),并重启进程。
  • 每次终止一个死锁进程,知道死锁环解除。
  • 每次剥夺一个资源,直至死锁环解除。

选择终止进程顺序和剥夺自愿的顺序

  • 进程已运行时间最少,预计剩余运行时间最长。
  • 进程已产生的输出最少,已用资源总量最少。
  • 进程的优先级最低,进程是交互式的还是批处理的。
  • 防止饥饿:避免总是选择同一个牺牲者(考虑其回滚的次数)。

?#某系系统中仅有5个并发进程竞争某类资源,且都需要3个该类资源,那么至少有 11 个该类资源,才能保证系统不会发生死锁。

7、哲学家就餐问题

基于信号量解决方案:

  • 至多允许4个哲学家同时拿起叉子
semaphore fork[5] = 1;
semaphore room = 4;//至多允许四人同时拿起叉子
void phiosopher(int i){
	while(true){
		think();
		wait(room);
		wait(fork[i]);
		wait(fork[(i+1) mod 5]);
		eat();
		signal(fork[i]);
		signal(fork[fork(i+1) mod 5]);
		signal(room);
	}
}
  • 奇数号人先拿左叉,偶数号人先拿右叉。
semaphore fork[5] = 1;
void phiosopher(int i){
	while(true){
		think();
		if(i % 2 == 1){
			wait(fork[i]);
			wait(fork[(i+1) mod 5]);
		}
		else{
			wait(fork[(i+1) mod 5]);
			wait(fork[i]);
		}
		eat();
		signal(fork[fork(i+1) mod 5]);
		signal(fork[i]);
	}
}
#其实可以进一步简化,只需要其余4人先拿左叉再拿右叉,另一人先拿右叉再拿左叉就可以避免死锁了。