2018/5/18 15:03:05当前位置推荐好文程序员浏览文章

死锁

什么是死锁

死锁是指多个进程因竞争共享资源而造成的一种僵局,若无外力作使用,这些进程都将永远不可以再向前推进。

也就是说,一组进程中,每个进程都无限等待被改组进程中另一进程锁占有的资源,因此永远无法得到资源,这种现象称为进程死锁,这一组进程就称为死锁进程。

关于死锁的少量特征

-参加死锁的进程最少是两个

-参加死锁的进程至少有两个已经占有的资源

-参加死锁的所有进程都在等待资源(参加死锁的进程,而非系统所有进程)

-参加死锁的进程是当前系统中所有进程的子集(不仅仅是进程间,进程内也会死锁)

资源又分为什么呢

永久性资源(可再使用资源)

可抢占资源:CPU

不可抢占资源:打印机

临时性资源(耗费性资源)

信号量,中断信号,同步信号等

死锁和死循环的区别和联络

1.死锁是偶然的(error),死循环是必然的(feature)

2.死锁处于阻塞状态,死循环一直在占使用CPU运行

3.死锁是因为操作系统并发执行,进程之间对互斥资源共享等引起的,与操作系统的管理可控制有关;死循环是程序员自己写的,有可可以是feature,也有可可以就是单纯的bug

死锁与饥饿的区别和联络

-饥饿的进程是长时间得不到CPU,而其余所需资源均已取得,一旦得到CPU即可以立即运行;而死锁除了CPU之外还有其余资源也为得到(正在被占使用),即便把CPU分配给它也不可以够执行。

-死锁进程至少有两个,而饥饿仅仅是由于每页调度它执行,所有可可以只有它一个

产生死锁的直接起因(充分条件)

1.系统资源的竞争(竞争不可剥夺资源)

2.进程推进顺序非法(例如信号量用不当,导致两个进程死锁)

产生死锁的必要条件

1.互斥条件

-进程对锁分配到的资源进行排它性的用

2.不剥夺条件

-进程已至少保持了一个资源,但又提出了新的资源请求,而该资源又被其余进程占有

3.请求和保持条件

-进程已取得的资源在未用完之前不可以被剥夺

4.循环等待条件

-在发生死锁时,必然存在一个进程——资源循环等待的环形链

为什么循环等待是必要条件而不是充要条件?

如果这个循环的S环节需要资源A,而系统有两个资源A,一个正在被S+1占使用,另一个正在被一个不属于该循环的进程K占使用,这个时候,假如K释放了它锁占使用的资源A,死锁即可以解开了。所以不是充分条件。

死锁的解决策咯

分三类:预防死锁,避免死锁,检测及解除死锁

预防死锁(破坏这四个必要条件就可)

1.破坏互斥条件

不可行,由于有很多东西的确是没办法同时访问的,例如打印机

2.破坏不剥夺条件

当某个进程S所需要的资源A正在被进程K所占有时,强行让K让出资源A

缺点:会导致K之前的工作失效(想象一下,你正在打印一幅画,打印到一半有一个新进程来了,他想打印点文件,于是正在打印一半的画忽然往下打印文字了..。)

3.破坏请求和保持条件

所有进程在开始运行之前必需一次性申请整个运行过程所需的一律资源

优点:简单、安全

缺点:资源白费严重,可可以导致饥饿

4.破坏循环等待条件

给资源和进程排好序,申请资源必需按照序号进行

确定:存在资源白费,也不利于新的设施的添加

死锁避免

系统安全状态:系统可以按某种(也就是存在)进程推动顺序,为每个进程分配所需资源,直到满足每个进程对资源的最大需求,使每个进程都能顺序地完成。则处于安全状态。

不安全状态:无法找到一个安全序列,则处于非安全状态(并不等价于死锁状态)。不安全状态只是说按照当前的情况,可可以会导致死锁,但是假如忽然某个进程释放了大量资源,就会解除不安全状态。

银行家算法的数据结构形容

1.可利使用资源Avaliable

含有m个元素的数组,每一个元素代表一类可使用资源的数目。Available[j]=K,代表Available[j]资源有K个可使用。(例如我Available[0]代表耳机,Available[1]代表鼠标,Available[2]代表键盘,Available[4]代表显示器,若Available[2]=3,代表我系统中有3个可使用的键盘资源)


2.最大需求矩阵Max

一个nXm的矩阵,定义了系统中n个进程中的每一个ijnc对m类资源的最大需求。Max[i,j]=K,代表进程i需要j资源的最大数目为K。

3.分配矩阵Allocation

和Max矩阵相似,只不过数量代表以及给的资源数

4.需求矩阵Need

Need[i,j]=Max[i,j]-Allocation[i,j]


4.系统执行安全性算法,检查此次资源分配后,系统能否处于安全状态。

若安全,才正式将资源分配给Pi,否则,本次试探分配作废,回还原理的状态,让Pi等待

安全性算法

1.设置两个向量

工作向量Work:表示系统可提供给进程继续运行所需的各类资源数目,它含有m个元素,在执行安全算法开始时,Work=Available

Finish:表示系统能否有足够的资源分配给进程,使之运行完成。开始时先做Finish[i]=False;当有足够资源分配给进程时,在令Finish[i]=true

2.从进程集合中找到一个可以满足下述条件的进程

1,Dinish[i]=false2.NeeD[i,j]<=Work[j]

若可以找到,执行步骤3,否则,执行步骤4

3.当进程Pi取得资源后,可顺利执行,直至完成,并释放出分配给它的资源

Work[j]=Work[i]+Allocation[i,j];

Finish[i]=true;

Go to step 2;

4,假如所有进程的Finish[i]=true都满足,则表示系统处于安全抓个年头,否则,系统处于不安全状态。

死锁的检测与解除

死锁的检测:允许死锁发生,操作系统不断监听系统进展情况,判断死锁能否发生

一旦死锁发生,则采取专门的措施,解除死锁并以最小的代价回复操作系统允许

检测的时机:当进程等待时检测死锁或者定时检测(但是无论如何系统开销都会因而增大)

资源分配图:使用有向图形容进程的死锁,系统中各类资源的分配和各个进程对资源请求的状态


方框表示资源

方框中圆点表示资源实例

使用圆圈加箭头名表示进程

资源实例指向进程的有向边表示分配边

进程指向资源类的有向边表示申请边

死锁定理:假如资源分配图中没有环路,则系统中没有死锁,如过存在环路,则可可以存在死锁。

假如每个资源类中只包含一个资源实例,则环路是死锁存在的充要条件。


我们在分析资源分配图的时候要进行适当的化简,假如能化简到只剩下资源和进程的样子,说明不存在死锁,反之,则说明存在死锁


死锁的解除

一般方法是:重新启动、撤销进程、剥夺资源、进程回退

网友评论