2019-03-04 21:36:17 weixin_42285271 阅读数 42
  • sql server 性能优化和日常管理维护

    课程总结sql server运行过程中对系统资源的使用和由此产生性能问题,介绍数据库规划设计、事务和锁的基本知识,如何处理阻塞和死锁,优化索引和读懂统计信息和执行计划等知识,同时详细介绍SQL 2014新功能特性内存优化表、列存储索引、alwayOn高可用。

    11719 人正在学习 去看看 宋立桓

大家好,今天给大家介绍进程死锁,这是操作系统原理中比较重要的一部分。
首先介绍进程死锁的定义
进程死锁:
一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到的资源,这种现象被称为进程死锁,这一组进程就称为死锁进程。如果死锁发生,会浪费大量系统资源,甚至导致系统崩溃
举一个最形象的例子,汽车过马路的例子
在这里插入图片描述
在这里插入图片描述
那么为什么会出现进程死锁的现象呢?
1、竞争资源,当系统中供多个进程共享资源如打印机、公共队列的情况下,该资源无法满足进程需求,引起进程竞争而产生死锁
2、进程间的推进顺序非法,进程在运行过程中,请求和释放资源的顺序不当,同样导致死锁
以下两个图分别为两种情况的例子
在这里插入图片描述
在这里插入图片描述
有死锁当然也有活锁
活锁的定义为
进程1和进程2都可以使用同一个资源,但是两者之间由于优先级相同,互相礼让导致一直进入CPU轮训却都不使用资源,不断循环。
在这里插入图片描述
如上图例子,进程A与进程B在系统中并发执行,当进程A给资源1加锁以后,这个时候CPU切换到进程B,进程B对资源2加锁。当再次进入进程A以后,算法不断去轮询资源2,然后进程A直到离开CPU,进程B也是同理,但是两个进程既无进展也不阻塞。

进程死锁有四个必要条件:
1、互斥使用(资源独占)
一个资源每次只能给一个进程使用
2、占有且等待(请求和保持资源)
进程在申请新的资源的同时,保留对原有资源的占有
3、不可抢占(不可剥夺)
资源申请者不能强行从资源占有者手中剥夺资源,资源只能由占有者自愿释放
4、循环等待
存在一个进程等待队列, {P1 , P2 , … , Pn}, 其中P1等待P2占有的资源,P2等待P3占有的资源,…, Pn等待P1占有的资源,形成一个进程等待环路

谈到死锁就要谈到死锁的预防
从两个角度来考虑,死锁的预防分为两种办法
1、不让死锁发生
死锁预防采用静态策略(设置合适的资源分配算法,不让死锁发生)和动态策略(以不让死锁发生为目标,跟踪并评估资源分配过程,根据评估结果决策是否分配 )
2、让死锁发生
死锁检测与解除

死锁的预防通常思路是在设计系统时,通过确定资源分配算法,排除发生死锁的可能性具体的做法是防止产生死锁的四个必要条件中任何一个条件发生,也就是破坏四个必要条件之一
1、破坏互斥现象
把独占资源变为共享资源
2、破坏占有等待现象
如一个进程在申请新的资源不能立即得到满足而变为等待状态之前,必须释放已占有的全部资源,若需要再重新申请或者要求每个进程在运行前必须一次性申请它所要求的所有资源,且仅当该进程所要资源均可满足时才给予一次性分配
3、破坏不可抢占现象
当一个进程申请的资源被其他进程占用时,可以通过操作系统抢占这一资源(两个进程优先级不同)
4、破坏循环等待条件
把系统中所有资源编号,进程在申请资源时必须严格按资源编号的递增次序进行,否则操作系统不予分配

2017-06-18 15:55:51 Windy0011 阅读数 266
  • sql server 性能优化和日常管理维护

    课程总结sql server运行过程中对系统资源的使用和由此产生性能问题,介绍数据库规划设计、事务和锁的基本知识,如何处理阻塞和死锁,优化索引和读懂统计信息和执行计划等知识,同时详细介绍SQL 2014新功能特性内存优化表、列存储索引、alwayOn高可用。

    11719 人正在学习 去看看 宋立桓

1.死锁的概念

死锁是进程死锁的简称,是由Dijkstra于1965年研究银行家算法时首先提出来的。它是计算机操作系统乃至并发程序设计中最难处理的问题之一。实际上,死锁问题不仅在计算机系统中存在,在我们日常生活中它也广泛存在。

2.什么是死锁

我们先看看这样一个生活中的例子:在一条河上有一座桥,桥面较窄,只能容纳一辆汽车通过,无法让两辆汽车并行。如果有两辆汽车A和B分别由桥的两端驶上该桥,则对于A车来说,它走过桥面左面的一段路(即占有了桥的一部分资源),要想过桥还须等待B车让出右边的桥面,此时A车不能前进;对于B车来说,它走过桥面右边的一段路(即占有了桥的一部分资源),要想过桥还须等待A车让出左边的桥面,此时B车也不能前进。两边的车都不倒车,结果造成互相等待对方让出桥面,但是谁也不让路,就会无休止地等下去。这种现象就是死锁。如果把汽车比做进程,桥面作为资源,那麽上述问题就描述为:进程A占有资源R1,等待进程B占有的资源Rr;进程B占有资源Rr,等待进程A占有的资源R1。而且资源R1和Rr只允许一个进程占用,即:不允许两个进程同时占用。结果,两个进程都不能继续执行,若不采取其它措施,这种循环等待状况会无限期持续下去,就发生了进程死锁。  

所谓死锁,是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然,如果没有外力的作用,那麽死锁涉及到的各个进程都将永远处于封锁状态。
3.产生死锁的必要条件

从以上分析可见,如果在计算机系统中同时具备下面四个必要条件时,那麽会发生死锁。换句话说,只要下面四个条件有一个不具备,系统就不会出现死锁。

〈1〉互斥条件。即某个资源在一段时间内只能由一个进程占有,不能同时被两个或两个以上的进程占有。这种独占资源如CD-ROM驱动器,打印机等等,必须在占有该资源的进程主动释放它之后,其它进程才能占有该资源。这是由资源本身的属性所决定的。如独木桥就是一种独占资源,两方的人不能同时过桥。

〈2〉不可抢占条件。进程所获得的资源在未使用完毕之前,资源申请者不能强行地从资源占有者手中夺取资源,而只能由该资源的占有者进程自行释放。如过独木桥的人不能强迫对方后退,也不能非法地将对方推下桥,必须是桥上的人自己过桥后空出桥面(即主动释放占有资源),对方的人才能过桥。

〈3〉占有且申请条件。进程至少已经占有一个资源,但又申请新的资源;由于该资源已被另外进程占有,此时该进程阻塞;但是,它在等待新资源之时,仍继续占用已占有的资源。还以过独木桥为例,甲乙两人在桥上相遇。甲走过一段桥面(即占有了一些资源),还需要走其余的桥面(申请新的资源),但那部分桥面被乙占有(乙走过一段桥面)。甲过不去,前进不能,又不后退;乙也处于同样的状况。

〈4〉循环等待条件。存在一个进程等待序列{P1,P2,...,Pn},其中P1等待P2所占有的某一资源,P2等待P3所占有的某一源,......,而Pn等待P1所占有的的某一资源,形成一个进程循环等待环。就像前面的过独木桥问题,甲等待乙占有的桥面,而乙又等待甲占有的桥面,从而彼此循环等待。

上面我们提到的这四个条件在死锁时会同时发生。也就是说,只要有一个必要条件不满足,则死锁就可以排除。

4.死锁的预防

前面介绍了死锁发生时的四个必要条件,只要破坏这四个必要条件中的任意一个条件,死锁就不会发生。这就为我们解决死锁问题提供了可能。一般地,解决死锁的方法分为死锁的预防,避免,检测与恢复三种(注意:死锁的检测与恢复是一个方法)。我们将在下面分别加以介绍。

死锁的预防是保证系统不进入死锁状态的一种策略。它的基本思想是要求进程申请资源时遵循某种协议,从而打破产生死锁的四个必要条件中的一个或几个,保证系统不会进入死锁状态。

〈1〉打破互斥条件。即允许进程同时访问某些资源。但是,有的资源是不允许被同时访问的,像打印机等等,这是由资源本身的属性所决定的。所以,这种办法并无实用价值。

〈 2〉打破不可抢占条件。即允许进程强行从占有者那里夺取某些资源。就是说,当一个进程已占有了某些资源,它又申请新的资源,但不能立即被满足时,它必须释放所占有的全部资源,以后再重新申请。它所释放的资源可以分配给其它进程。这就相当于该进程占有的资源被隐蔽地强占了。这种预防死锁的方法实现起来困难,会降低系统性能。    

〈3〉打破占有且申请条件。可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足,则不分配任何资源,此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时,才一次性地将所申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源,所以不会发生占有资源又申请资源的现象,因此不会发生死锁。但是,这种策略也有如下缺点:

(1)在许多情况下,一个进程在执行之前不可能知道它所需要的全部资源。这是由于进程在执行时是动态的,不可预测的;

(2)资源利用率低。无论所分资源何时用到,一个进程只有在占有所需的全部资源后才能执行。即使有些资源最后才被该进程用到一次,但该进程在生存期间却一直占有它们,造成长期占着不用的状况。这显然是一种极大的资源浪费;

(3)降低了进程的并发性。因为资源有限,又加上存在浪费,能分配到所需全部资源的进程个数就必然少了。    


(4)打破循环等待条件,实行资源有序分配策略。采用这种策略,即把资源事先分类编号,按号分配,使进程在申请,占用资源时不会形成环路。所有进程对资源的请求必须严格按资源序号递增的顺序提出。进程占用了小号资源,才能申请大号资源,就不会产生环路,从而预防了死锁。这种策略与前面的策略相比,资源的利用率和系统吞吐量都有很大提高,但是也存在以下缺点:

(1)限制了进程对资源的请求,同时给系统中所有资源合理编号也是件困难事,并增加了系统开销;

(2)为了遵循按编号申请的次序,暂不使用的资源也需要提前申请,从而增加了进程对资源的占用时间。

死锁的检测与恢复

一般来说,由于操作系统有并发,共享以及随机性等特点,通过预防和避免的手段达到排除死锁的目的是很困难的。这需要较大的系统开销,而且不能充分利用资源。为此,一种简便的方法是系统为进程分配资源时,不采取任何限制性措施,但是提供了检测和解脱死锁的手段:能发现死锁并从死锁状态中恢复出来。因此,在实际的操作系统中往往采用死锁的检测与恢复方法来排除死锁。

死锁检测与恢复是指系统设有专门的机构,当死锁发生时,该机构能够检测到死锁发生的位置和原因,并能通过外力破坏死锁发生的必要条件,从而使得并发进程从死锁状态中恢复出来。
2019-05-06 18:06:28 qq_29677867 阅读数 223
  • sql server 性能优化和日常管理维护

    课程总结sql server运行过程中对系统资源的使用和由此产生性能问题,介绍数据库规划设计、事务和锁的基本知识,如何处理阻塞和死锁,优化索引和读懂统计信息和执行计划等知识,同时详细介绍SQL 2014新功能特性内存优化表、列存储索引、alwayOn高可用。

    11719 人正在学习 去看看 宋立桓

前言

我们都见过交通阻塞,一大堆汽车因为争夺行路权,互不相让而造成阻塞,又或者因为车辆发生故障抛锚或两辆车相撞而造成道路阻塞。在这种情况下,所有的车都停下来,谁也无法前行,这就是死锁。本篇就来了解一下什么是死锁,如何应对死锁。

一、死锁初窥

1、为何会发生死锁?

死锁的发生归根结底是因为对资源的竞争。因为大家都想要某种资源,但又不能随心所欲地得到所有资源,在争夺的僵局中,导致任何人无法继续推进。

在一个系统里存在多个线程,而这些线程共享该计算机系统里的资源。因为资源竞争而造成系统无法继续推进就难以避免了。这里的资源可以使硬件(CPU、内存、磁盘等),也可以是软件(例如锁、信号量等)。

2、死锁的定义与必要条件

  1. 死锁的定义

    如果有一组线程,每个线程都在等待一个事件的发生,而这个事件只能有该线程里面的另一线程发出,则称这组线程发生了死锁**。这里的事件主要是资源的释放,在死锁状态中,没有线程可以执行、释放资源或被叫醒。

    例如,有线程A和线程B如下:

    img

    如果线程A和线程B交替执行,那么线程A和线程B均会因为无法获得对应的资源而无法继续执行也不能释放锁,从而造成死锁

  2. 死锁的4个必要条件

    • 资源有限:即一个系统里面的资源数量是有限的,以致于无法同时满足所有线程的资源需求。
    • 持有等待:即一个线程在请求新的资源时,其已经获得的资源并不释放,而是继续持有。
    • 不可抢占:即如果可以抢占一个资源,则也不会发生死锁。(凡是可以抢占的资源,均不会称为死锁的原因)
    • 循环等待:即如果你等我、我等你,大家都这样等着对方,就产生了死锁。

    img

二、应对死锁

1、哲学家就餐问题

哲学家围坐在一个圆桌边,每个人的左右两边均放着一根筷子。如果要吃饭,需要获得左右两边的筷子(不能用一根筷子吃饭)。我们很自然地得到一个算法,对于每一个哲学家,执行以下的算法:

  • 等待左边的筷子可用,然后拿起左边的筷子。
  • 等待右边的筷子可用,然后拿起右边的筷子。
  • 吃饭。
  • 放下两根筷子。

显然,如果每个哲学家穿插着执行,将会出现每个哲学家都拿起左边筷子,而等待右边筷子的情况,即死锁将会发生。那么,有木有办法防止哲学家出现死锁呢?

2、死锁的应对方法

操作系统应对死锁的策略可以分为两大种、四小种。

  • 两大种是:允许死锁发生 和 不让死锁发生。
  • 四小种是:允许死锁发生有两个子对策,一是假装看不见不予理睬,二是死锁发生后想办法解决;不让死锁发生也有两个子对策,一是通过平时的仔细检点避免难题出现,二是通过将发生死锁的必要条件消除杜绝死锁的发生。

允许死锁发生有两个子对策:

  • 顺其自然不予理睬:此种策略就是操作系统不做任何措施,任由死锁发生。老子曾说,无为而治,说的就是这个策略。但是,如果牵涉到高可靠性系统、实时控制系统,那就另当别论了,那绝对不允许死锁。

  • 死锁的检测与恢复:在死锁检测上,一般会利用到两个矩阵:一个是资源分配矩阵,另一个是资源等待矩阵,如下图所示:

    资源分配矩阵

    img

    资源等待矩阵

    img

    此外,还维持两个矢量:一个是系统资源总量矢量(表示系统中所有资源的总数是多少),另一个是系统当前可用资源矢量(代表系统现在还有多少可用的资源),如下图所示:

    img

    有了上面的矩阵和矢量,我们就可以通过简单地矩阵运算来判断系统是否发生了死锁。例如,将上图中的资源可用数量矩阵与资源等待矩阵的每一行相减,都会出现负值,那么该系统将要发生死锁。

    在死锁恢复上,首先可以抢占(即将某个线程所占有的资源强行拿走,分配给别的线程),其次可以将整个线程Kill杀掉(因为抢占一个线程的资源有可能造成该线程无法再正确运行了),最后则是Rollback回滚(即将整个系统回滚到过去的某个状态,大家从那个状态重新来过)

不让死锁发生也有两个子对策

  • 死锁的动态避免:死锁的检测与恢复属于后发制人,这时死锁的消极后果已经产生,即使修复也已经浪费了时间,降低了效率,甚至造成了其他损失。因此,需要更加积极主动一点,不要等到死锁发生了再亡羊补牢,而是在运行中就小心翼翼,不让思索发生。

    动态避免的原则在于:在每次进行资源分配时,必须经过仔细计算,确保该资源请求批准后系统不会进入死锁或潜在的死锁状态。例如,有一种资源的数量为10个,当前有3个线程正在运行。每个线程需要资源的最大数和当前已经占用的资源数如下表所示:

    img点击并拖拽以移动

    可以通过以下分配过程得知,存在一个资源分配顺序使得所有线程都能获得其需要的资源,从而得知当前状态是安全状态,不会产生死锁。相反,如果不存在这样一个顺序,那么就有可能产生死锁。

    img

    动态避免的优点就是无需等待死锁的发生,而是在死锁有可能发生的时候采取先发制人的措施,断然拒绝有可能进入死锁的资源请求。但是,计算一个状态是否安全并不是一件容易的事情。

  • 死锁的静态防止

    该策略的中心思想是:清除死锁发生的土壤(即死锁的4个必要条件),只要清除4个必要条件中的一个,那么死锁将无法发生。

    • 清除资源独占条件:一是增加资源到所有线程满足的资源需要,但这并不实际,因为资源是有限的;二是将资源变为共享,但并不适合与所有的资源(例如键盘输入就无法共享)。
    • 清除保持和请求条件:一个线程必须一次请求其所需的所有资源,而不是一般情况下的请求一点资源做一点事情。由于一个线程一次就获得了其所需的所有资源,该线程就可以顺利执行,不会发生死锁。
    • 清除非抢占条件:允许抢占资源,也就是说可以从一个线程手上将资源抢夺过来。
    • 清除循环等待条件:出现循环等待是因为线程请求资源的顺序是随机的,所以只要约定线程对资源的使用顺序,那么死锁就不能发生。

3、银行家算法

顾名思义,银行家算法就是仿照银行发放贷款时采用的控制方式而设计的一种死锁避免算法,该算法的策略是实现动态避免死锁

银行家算法的基本思想是:分配资源之前,判断系统是否是安全的;若是,才分配。每分配一次资源就测试一次是否安全,不是资源全部就位后才测试。我们可以把操作系统看作是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。概括起来基本思想就是:

  1. 分配检测:

    Request < Need

    Request < Available

  2. 安全序列检测算法

    下面看一个在操作系统教科书中出现的例子:

某系统有R1,R2,R3共3中资源,在T0时刻P0,P1,P2,P3和P4这5个进程对资源的占用和需求情况如下表1,此时系统的可用资源向量为(3,3,2)。试问:

1、T0时刻系统是否存在安全序列?

2、P1请求资源:P1发出请求向量Request(1,0,2),系统是否接受该请求?请使用银行家算法检查

表1 T0时刻的资源分配表

MAX Allocation Need Available
P0 7 5 3 0 1 0 7 4 3 3 3 2
P1 3 2 2 2 0 0 1 2 2
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1

1、T0时刻系统是否存在安全序列?

Available > Need1 ----> 可用资源分配给P1,直到P1进程执行完成,然后Available = Available + Allocation1 = (5,3,2)

​ Available > Need3 ----> 可用资源分配给P3,直到P3进程执行完成,然后Available = Available + Allocation3 = (7,4,3)

Available > Need4 依次类推

​  得到安全序列为:P1,P3,P4,P2,P0

2、P1请求资源:P1发出请求向量Request(1,0,2),系统是否接受该请求?请使用银行家算法检查

第一步(假分配检查):把Request分配给P1,必须满足Request要小于Available,Request要小于Need。

​ Request(1,0,2)< Available(3,3,2)

​ Request(1,0,2)< Need(1,2,2)

​ 因为满足第一步检查,进入第二层检查(安全序列检查)。

第二步(安全序列检查):建立安全性检查表

Work Need Allocation Work+Allocation Finish
P1 2 3 0 0 2 0 3 0 2

如果 Work > Need,那么执行Work+Allocation,得到:

Work Need Allocation Work+Allocation Finish
P1 2 3 0 0 2 0 3 0 2 5 3 2 true
5 3 2

找到Need < Work的进程,如果没有找到这样的进程而进程集合没有执行,则算法返回,得到不存在安全序列结果,否则继续执行该算法。

这里我们找到了P3进程。修改安全序列检查表:

Work Need Allocation Work+Allocation Finish
P1 2 3 0 0 2 0 3 0 2 5 3 2 true
P3 5 3 2 0 1 1 2 1 1 7 4 3 true
7 4 3

这样一直执行到所有的进程到完成,以完成该安全序列检查表:

Work Need Allocation Work+Allocation Finish
P1 2 3 0 0 2 0 3 0 2 5 3 2 true
P3 5 3 2 0 1 1 2 1 1 7 4 3 true
P4 7 4 3 4 3 1 0 0 2 7 4 5 true
P0 7 4 5 7 4 3 0 1 0 7 5 5 true
P2 7 5 5 6 0 0 3 0 2 10 5 7 true

​ 这样就找到了整个安全序列为:P1,P3,P4,P0,P2

​ 总的来说,银行家算法是一个动态避免死锁算法,通过对资源的仔细分配以避免死锁。其特点是可以超额批准客户的信用额度,即所有客户的信用额度之和可以超过银行的全部资本,这就是杠杆(Leverage)

4、解决:哲学家就餐问题

这里使用C#语言,模拟信号量,以消除死锁的必要条件(消除保持并等待的必要条件)的方式来实现解决哲学家就餐问题。

(1)首先定义哲学家的三种状态:

/// <summary>
/// </summary>
    public enum StateEnum{
        THINKING = 0,// 思考状态
        HUNGRY = 1,// 饥饿状态
        EATING = 2// 吃饭状态
    }

(2)然后定义一个临界区互斥用的信号量,给每个哲学家单独定义一个信号量。如果一个哲学家需要阻塞,则阻塞发生在该信号量上。

    private const int NumOfPhilosopher = 5; // 哲学家人数
    private static StateEnum[] states = new StateEnum[NumOfPhilosopher]; // 记录每个哲学家当前状态的数组
    private static semaphore mutex = 1; // 模拟互斥信号量
    private static semaphore[] s = new semaphore[NumOfPhilosopher]; // 每个哲学家等待一个单独的信号量
  //这里的semaphore其实就是int类型:
  using semaphore = System.Int32;

要模拟互斥信号量,需要有两种基本原语操作Up 和 Down:

/// <summary>
    /// 互斥信号量Down
    /// </summary>
    private static void Down(semaphore mutex){
        if (mutex == 1){
            mutex--;
        }
    }

    /// <summary>
    /// 互斥信号量Down
    /// </summary>
    private static void Down(ref semaphore mutex){
        // 阻塞操作
        while (mutex < 1) { }
    }

    /// <summary>
    /// 互斥信号量Up
    /// </summary>
    private static void Up(semaphore mutex){
        if (mutex == 0){
            mutex++;
        }
    }

    /// <summary>
    /// 互斥信号量Up
    /// </summary>
    private static void Up(ref semaphore mutex){
        if (mutex == 0){
            mutex++;
        }
    }

(3)哲学家的两种生活状态:Think 和 Eat

/// <summary>
    /// 思考
    /// </summary>
    /// <param name="philosoper">哲学家编号</param>
    private static void Think(int philosopher){
        Console.WriteLine("Philosopher:{0} IS THINKING.", philosopher + 1);
        System.Diagnostics.Debug.WriteLine("Philosopher:{0} IS THINKING.", philosopher + 1);
    }

    /// <summary>
    /// 吃饭
    /// </summary>
    /// <param name="philosoper">哲学家编号</param>
    private static void Eat(int philosopher){
        Console.WriteLine("Philosopher:{0} IS EATING.", philosopher + 1);
        System.Diagnostics.Debug.WriteLine("Philosopher:{0} IS EATING.", philosopher + 1);
    }

(4)哲学家的日常生活:思考,拿筷子,吃饭,放下筷子,继续思考…

/// <summary>
    /// 哲学家程序
    /// </summary>
    /// <param name="philosopher">哲学家编号</param>
    private static void PhilosopherRoutine(object number){
        int philosopher = (semaphore)number;
        while (true){
            Think(philosopher);
            TakeChopsticks(philosopher);    // 同时获得两根筷子,否则阻塞等待
            Eat(philosopher);
            PutChopsticks(philosopher);     // 同时放下两根筷子
        }
    }

    /// <summary>
    /// 获取筷子
    /// </summary>
    /// <param name="philosoper">哲学家编号</param>
    private static void TakeChopsticks(int philosopher){
        Down(mutex);

        states[philosopher] = StateEnum.HUNGRY;
        Test(philosopher);  // 试图拿起两根筷子
        Up(mutex);

        Down(ref s[philosopher]);    // 如果没有拿到筷子,则继续阻塞等待
    }

    /// <summary>
    /// 放下筷子
    /// </summary>
    /// <param name="philosoper">哲学家编号</param>
    private static void PutChopsticks(int philosopher){
        Down(mutex);

        states[philosopher] = StateEnum.THINKING;
        int left = (philosopher + NumOfPhilosopher - 1) % NumOfPhilosopher;
        int right = (philosopher + 1) % NumOfPhilosopher;
        // 测试左面的哲学家是否可以吃饭
        Test(left);
        // 测试右面的哲学家是否可以吃饭
        Test(right);

        Up(mutex);
    }

    /// <summary>
    /// 测试是否可以同时拿起两根筷子
    /// </summary>
    /// <param name="philosopher">哲学家编号</param>
    private static void Test(int philosopher){
        int left = (philosopher + NumOfPhilosopher - 1) % NumOfPhilosopher;
        int right = (philosopher + 1) % NumOfPhilosopher;

        if (states[philosopher] == StateEnum.HUNGRY && states[left] != StateEnum.EATING &&
            states[right] != StateEnum.EATING){
            // 可以拿起两根筷子,改变哲学家状态到吃饭状态
            states[philosopher] = StateEnum.EATING;
            // 发出叫醒信号
            Up(ref s[philosopher]);
        }
    }

Run之后的结果如下图所示:

img

这样看不清楚,截一段结果出来看看:

Philosopher:2 IS THINKING.
Philosopher:3 IS THINKING.
Philosopher:5 IS THINKING.
Philosopher:1 IS THINKING.
Philosopher:5 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:5 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:1 IS EATING.
Philosopher:4 IS EATING.
Philosopher:5 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:1 IS THINKING.
Philosopher:4 IS THINKING.
Philosopher:5 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:1 IS EATING.
Philosopher:2 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:5 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:5 IS THINKING.
Philosopher:4 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:1 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:4 IS EATING.
Philosopher:2 IS THINKING.
Philosopher:4 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:4 IS EATING.
Philosopher:5 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:5 IS THINKING.
Philosopher:4 IS THINKING.
Philosopher:2 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:5 IS EATING.
Philosopher:4 IS EATING.
Philosopher:2 IS EATING.
Philosopher:1 IS EATING.
Philosopher:5 IS THINKING.
Philosopher:3 IS THINKING.
Philosopher:5 IS EATING.
Philosopher:3 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:2 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:5 IS THINKING.
Philosopher:3 IS THINKING.
Philosopher:4 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:5 IS EATING.
Philosopher:4 IS EATING.
Philosopher:2 IS THINKING.
Philosopher:5 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:5 IS EATING.
Philosopher:1 IS THINKING.
Philosopher:4 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:5 IS THINKING.
Philosopher:4 IS EATING.
Philosopher:2 IS THINKING.
Philosopher:5 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:5 IS THINKING.
Philosopher:1 IS EATING.
Philosopher:5 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:2 IS EATING.
Philosopher:4 IS EATING.
Philosopher:5 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:4 IS THINKING.
Philosopher:2 IS THINKING.
Philosopher:5 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:5 IS THINKING.
Philosopher:3 IS EATING.
Philosopher:4 IS EATING.
Philosopher:2 IS EATING.
Philosopher:5 IS EATING.
Philosopher:3 IS THINKING.
Philosopher:5 IS THINKING.
Philosopher:1 IS THINKING.

可以看到,哲学家们交替着思考吃饭,井然有序,没有发生死锁。这里没有使用.NET中现有的Mutex、Semaphore等类型,而采用了一个int类型来模拟最简单的互斥信号量。

完整的代码如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using semaphore = System.Int32;

namespace PhilosopherDemo{
    public class Program{
        private const int NumOfPhilosopher = 5; // 哲学家人数
        private static StateEnum[] states = new StateEnum[NumOfPhilosopher]; // 记录每个哲学家当前状态的数组
        private static semaphore mutex = 1; // 模拟互斥信号量
        private static semaphore[] s = new semaphore[NumOfPhilosopher]; // 每个哲学家等待一个单独的信号量

        /// <summary>
        /// 初始化哲学家状态
        /// </summary>
        private static void InitializePhilosopher(){
            for (int i = 0; i < NumOfPhilosopher; i++){
                states[i] = StateEnum.THINKING;
                s[i] = 1;
            }
        }

        /// <summary>
        /// 哲学家程序
        /// </summary>
        /// <param name="philosopher">哲学家编号</param>
        private static void PhilosopherRoutine(object number){
            int philosopher = (semaphore)number;
            while (true){
                Think(philosopher);
                TakeChopsticks(philosopher); // 同时获得两根筷子,否则阻塞等待
                Eat(philosopher);
                PutChopsticks(philosopher);   // 同时放下两根筷子
            }
        }

        /// <summary>
        /// 获取筷子
        /// </summary>
        /// <param name="philosoper">哲学家编号</param>
        private static void TakeChopsticks(int philosopher){
            Down(mutex);

            states[philosopher] = StateEnum.HUNGRY;
            Test(philosopher);  // 试图拿起两根筷子
            Up(mutex);

            Down(ref s[philosopher]); // 如果没有拿到筷子,则继续阻塞等待
        }

        /// <summary>
        /// 放下筷子
        /// </summary>
        /// <param name="philosoper">哲学家编号</param>
        private static void PutChopsticks(int philosopher){
            Down(mutex);

            states[philosopher] = StateEnum.THINKING;
            int left = (philosopher + NumOfPhilosopher - 1) % NumOfPhilosopher;
            int right = (philosopher + 1) % NumOfPhilosopher;
            // 测试左面的哲学家是否可以吃饭
            Test(left);
            // 测试右面的哲学家是否可以吃饭
            Test(right);

            Up(mutex);
        }

        /// <summary>
        /// 测试是否可以同时拿起两根筷子
        /// </summary>
        /// <param name="philosopher">哲学家编号</param>
        private static void Test(int philosopher){
            int left = (philosopher + NumOfPhilosopher - 1) % NumOfPhilosopher;
            int right = (philosopher + 1) % NumOfPhilosopher;

            if (states[philosopher] == StateEnum.HUNGRY && states[left] != StateEnum.EATING &&
                states[right] != StateEnum.EATING){
                // 可以拿起两根筷子,改变哲学家状态到吃饭状态
                states[philosopher] = StateEnum.EATING;
                // 发出叫醒信号
                Up(ref s[philosopher]);
            }
        }

        /// <summary>
        /// 思考
        /// </summary>
        /// <param name="philosoper">哲学家编号</param>
        private static void Think(int philosopher){
            Console.WriteLine("Philosopher:{0} IS THINKING.", philosopher + 1);
            System.Diagnostics.Debug.WriteLine("Philosopher:{0} IS THINKING.", philosopher + 1);
        }

        /// <summary>
        /// 吃饭
        /// </summary>
        /// <param name="philosoper">哲学家编号</param>
        private static void Eat(int philosopher){
            Console.WriteLine("Philosopher:{0} IS EATING.", philosopher + 1);
            System.Diagnostics.Debug.WriteLine("Philosopher:{0} IS EATING.", philosopher + 1);
        }

        /// <summary>
        /// 互斥信号量Down
        /// </summary>
        private static void Down(semaphore mutex){
            if (mutex == 1){
                mutex--;
            }
        }

        /// <summary>
        /// 互斥信号量Down
        /// </summary>
        private static void Down(ref semaphore mutex){
            // 阻塞操作
            while (mutex < 1) { }
        }

        /// <summary>
        /// 互斥信号量Up
        /// </summary>
        private static void Up(semaphore mutex){
            if (mutex == 0){
                mutex++;
            }
        }

        /// <summary>
        /// 互斥信号量Up
        /// </summary>
        private static void Up(ref semaphore mutex){
            if (mutex == 0){
                mutex++;
            }
        }

        public static void Main(string[] args){
            InitializePhilosopher();

            for (int i = 0; i < NumOfPhilosopher; i++){
                Thread thread = new Thread(PhilosopherRoutine);
                thread.Start(i);
            }
            Console.ReadKey();
        }
    }
}

​ (转至:http://edisonchou.cnblogs.com ,感谢博主的总结归纳)

2019-02-28 21:05:15 slh2016 阅读数 86
  • sql server 性能优化和日常管理维护

    课程总结sql server运行过程中对系统资源的使用和由此产生性能问题,介绍数据库规划设计、事务和锁的基本知识,如何处理阻塞和死锁,优化索引和读懂统计信息和执行计划等知识,同时详细介绍SQL 2014新功能特性内存优化表、列存储索引、alwayOn高可用。

    11719 人正在学习 去看看 宋立桓

2.17 死锁的概念以及产生死锁的原因

死锁的定义

在多道程序系统中,由于多个进程的并发执行,改善了系统资源的利用率并提高了系统 的处理能力。然而,多个进程的并发执行也带来了新的问题——死锁。所谓死锁是指多个进程因竞争资源而造成的一种僵局(互相等待),若无外力作用,这些进程都将无法向前推进

下面我们通过一些实例来说明死锁现象。

先看生活中的一个实例,在一条河上有一座桥,桥面很窄,只能容纳一辆汽车通行。如果有两辆汽车分别从桥的左右两端驶上该桥,则会出现下述的冲突情况。此时,左边的汽车占有了桥面左边的一段,要想过桥还需等待右边的汽车让出桥面右边的一段;右边的汽车占有了桥面右边的一段,要想过桥还需等待左边的汽车让出桥面左边的一段。此时,若左右两边的汽车都只能向前行驶,则两辆汽车都无法过桥。

在计算机系统中也存在类似的情况。例如,某计算机系统中只有一台打印机和一台输入设备,进程P1正占用输入设备,同时又提出使用打印机的请求,但此时打印机正被进程P2 所占用,而P2在未释放打印机之前,又提出请求使用正被P1占用着的输入设备。这样两个进程相互无休止地等待下去,均无法继续执行,此时两个进程陷入死锁状态。

死锁产生的原因

1) 系统资源的竞争

通常系统中拥有的不可剥夺资源,其数量不足以满足多个进程运行的需要,使得进程在运行过程中,会因争夺资源而陷入僵局,如磁带机、打印机等。只有对不可剥夺资源的竞争才可能产生死锁,对可剥夺资源的竞争是不会引起死锁的

2) 进程推进顺序非法

进程在运行过程中,请求和释放资源的顺序不当,也同样会导致死锁。例如,并发进程 P1、P2分别保持了资源R1、R2,而进程P1申请资源R2,进程P2申请资源R1时,两者都会因为所需资源被占用而阻塞。

信号量使用不当也会造成死锁。进程间彼此相互等待对方发来的消息,结果也会使得这些进程间无法继续向前推进。例如,进程A等待进程B发的消息,进程B又在等待进程A 发的消息,可以看出进程A和B不是因为竞争同一资源,而是在等待对方的资源导致死锁

3) 死锁产生的必要条件

产生死锁必须同时满足以下四个条件,只要其中任一条件不成立,死锁就不会发生。
  • 互斥条件:进程要求对所分配的资源(如打印机)进行排他性控制,即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源,则请求进程只能等待。
  • 不剥夺条件:进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能由获得该资源的进程自己来释放(只能是主动释放)。
  • 请求和保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已被其他进程占有,此时请求进程被阻塞,但对自己已获得的资源保持不放。
  • 循环等待条件:存在一种进程资源的循环等待链,链中每一个进程已获得的资源同时被链中下一个进程所请求。即存在一个处于等待状态的进程集合{Pl, P2, ..., pn},其中Pi等待的资源被P(i+1)占有(i=0, 1, ..., n-1),Pn等待的资源被P0占有,如图2-15所示。

2.18 死锁的处理策略

为使系统不发生死锁,必须设法破坏产生死锁的四个必要条件之一,或者允许死锁产生, 但当死锁发生时能检测出死锁,并有能力实现恢复。

预防死锁

设置某些限制条件,破坏产生死锁的四个必要条件中的一个或几个,以防止发生死锁。

避免死锁

在资源的动态分配过程中,用某种方法防止系统进入不安全状态,从而避免死锁。

死锁的检测及解除

无需釆取任何限制性措施,允许进程在运行过程中发生死锁。通过系统的检测机构及时地检测出死锁的发生,然后釆取某种措施解除死锁。

预防死锁和避免死锁都属于事先预防策略,但预防死锁的限制条件比较严格,实现起来较为简单,但往往导致系统的效率低,资源利用率低;避免死锁的限制条件相对宽松,资源分配后需要通过算法来判断是否进入不安全状态,实现起来较为复杂。

死锁的几种处理策略的比较见表2-14。

表2-14 死锁处理策略的比较
-- 资源分配策略 各种可能模式 主要优点 主要缺点
死锁预防 保守,宁可资源闲置 一次请求所有资源,资 源剥夺,资源按序分配 适用于做突发式处理的进程,不必进行剥夺 效率低,进程初始化时间延长;剥夺次数过多;不便灵活申请新资源
死锁避免 是”预防“和”检测“ 的折中(在运行时判断是否可能死锁) 寻找可能的安全允许顺序 不必进行剥夺 必须知道将来的资源需求;进程不能被长时间阻塞
死锁检测 宽松,只要允许就分配资源 定期检查死锁是否已经发生 不延长进程初始化时间,允许对死锁进行现场处理 通过剥夺解除死锁,造成损失


2.19 死锁预防和死锁避免

死锁预防

防止死锁的发生只需破坏死锁产生的四个必要条件之一即可。

1) 破坏互斥条件

如果允许系统资源都能共享使用,则系统不会进入死锁状态。但有些资源根本不能同时访问,如打印机等临界资源只能互斥使用。所以,破坏互斥条件而预防死锁的方法不太可行,而且在有的场合应该保护这种互斥性。

2) 破坏不剥夺条件

当一个已保持了某些不可剥夺资源的进程,请求新的资源而得不到满足时,它必须释放已经保持的所有资源,待以后需要时再重新申请。这意味着,一个进程已占有的资源会被暂时释放,或者说是被剥夺了,或从而破坏了不可剥夺条件。

该策略实现起来比较复杂,释放已获得的资源可能造成前一阶段工作的失效,反复地申请和释放资源会增加系统开销,降低系统吞吐量。这种方法常用于状态易于保存和恢复的资源,如CPU的寄存器及内存资源,一般不能用于打印机之类的资源。

3) 破坏请求和保持条件

釆用预先静态分配方法,即进程在运行前一次申请完它所需要的全部资源,在它的资源未满足前,不把它投入运行。一旦投入运行后,这些资源就一直归它所有,也不再提出其他资源请求,这样就可以保证系统不会发生死锁。

这种方式实现简单,但缺点也显而易见,系统资源被严重浪费,其中有些资源可能仅在运行初期或运行快结束时才使用,甚至根本不使用。而且还会导致“饥饿”现象,当由于个别资源长期被其他进程占用时,将致使等待该资源的进程迟迟不能开始运行。

4) 破坏循环等待条件

为了破坏循环等待条件,可釆用顺序资源分配法。首先给系统中的资源编号,规定每个进程,必须按编号递增的顺序请求资源,同类资源一次申请完。也就是说,只要进程提出申请分配资源Ri,则该进程在以后的资源申请中,只能申请编号大于Ri的资源。

这种方法存在的问题是,编号必须相对稳定,这就限制了新类型设备的增加;尽管在为资源编号时已考虑到大多数作业实际使用这些资源的顺序,但也经常会发生作业使甩资源的顺序与系统规定顺序不同的情况,造成资源的浪费;此外,这种按规定次序申请资源的方法,也必然会给用户的编程带来麻烦。

死锁避免

避免死锁同样是属于事先预防的策略,但并不是事先釆取某种限制措施破坏死锁的必要条件,而是在资源动态分配过程中,防止系统进入不安全状态,以避免发生死锁。这种方法所施加的限制条件较弱,可以获得较好的系统性能。

1. 系统安全状态

避免死锁的方法中,允许进程动态地申请资源,但系统在进行资源分配之前,应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给进程; 否则,让进程等待。

所谓安全状态,是指系统能按某种进程推进顺序( P1, P2, ..., Pn),为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺序地完成。此时称 P1, P2, ..., Pn 为安全序列。如果系统无法找到一个安全序列,则称系统处于不安全状态。

假设系统中有三个进程P1、P2和P3,共有12 台磁带机。进程P1总共需要10台磁带机,P2和P3 分别需要4台和9台。假设在T0时刻,进程P1、P2 和P3已分别获得5合、2台和2台,尚有3台未分配,见表2-15。

表2-15 资源分配
进程 最大需求 已分配 可用
P1 10 5 3
P2 4 2
P3 9 2

则在T0时刻是安全的,因为存在一个安全序列P2、Pl、P3,即只要系统按此进程序列分配资源,则每个进程都能顺利完成。若在T0时刻后,系统分配1台磁带机给P3,则此时系统便进入不安全状态,因为此时已无法再找到一个安全序列。

并非所有的不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状态;反之,只要系统处于安全状态,系统便可以避免进入死锁状态。

2. 银行家算法

银行家算法是最著名的死锁避免算法。它提出的思想是:把操作系统看做是银行家,操作系统管理的资源相当于银行家管理的资金,进程向操作系统请求分配资源相当于用户向银行家贷款。操作系统按照银行家制定的规则为进程分配资源,当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源,若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若能满足则按当前的申请量分配资源,否则也要推迟分配。

1) 数据结构描述
可利用资源矢量Available:含有m个元素的歎组,其中的每一个元素代表一类可用的资源数目。Available[j]=K,则表示系统中现有Rj类资源K个。

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

分配矩阵Allocation:为n*m矩阵,定义了系统中每一类资源当前已分配给每一进程的资源数。All0Cati0n[i, j]= K,则表示进程i当前已分得Rj类资源的数目为K。

需求矩阵Need:为n*m矩阵,表示每个进程尚需的各类资源数。Need[i, j]=K,则表示进程i还需要Rj类资源的数目为K。

上述三个矩阵间存在下述关系:
Need[i, j] = Max[i, j] - Allocation[i, j]

2) 银行家算法描述
设Requesti是进程Pi的请求矢量,如果Requesti[j]K,表示进程Pi需要Rj类资源K个。当Pi发出资源请求后,系统按下述步骤进行检查:

①如果Requesti[j] <= Need[i, j],便转向步骤②;否则认为出错,因为它所需要的资源数已超过它所宣布的最大值。

②如果Requesti[j] <= Available[j],便转向步骤③;否则,表示尚无足够资源,Pi须等待。

③系统试探着把资源分配给进程Pi,并修改下面数据结构中的数值:
  1. Available[j] = Available[j] - Requesti[j];
  2. Allocation[i, j] = Allocation[i, j] + Requesti[ j];
  3. Need[i, j] = Need[i, j] - Requesti[j];
④系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将资源分配给进程Pi,以完成本次分配;否则,将本次的试探分配作废,恢复原来的资源分配状态,让进程Pi等待。

3) 安全性算法
①设置两个矢量。工作矢量Work;它表示系统可提供给进程继续运行所需的各类资源数目,它含有所个元素,在执行安全算法开始时,Work=Available; Finish:它表示系统是否有足够的资源分配给进程,使之运行完成。开始时 Finish[i]=false;当有足够资源分配给进程 Pi 时,再令 Finish[i]=true。

②从进程集合中找到一个能满足下述条件的进程:Finish[i]=false;    Need[i, j]<=Work[j]; 若找到,执行下一步骤,否则,执行步骤4。

③当进程Pi获得资源后,可顺利执行,直至完成,并释放出分配给它的资源,故应执行:
  1. Work[j]=Work[j]+Allocation[i, j];
  2. Finish[i]=true;
  3. go to step <2>;
④如果所有进程的Finish[i]=tme都满足,则表示系统处于安全状态;否则,系统处于不安全状态。

3. 银行家算法举例

假定系统中有5个进程{P0, P1, P2, P3, P4}和三类资源{A, B, C},各种资源的数量分别为10、5、7,在T0时刻的资源分配情况见表2-16。

1) T0时刻的安全性。
利用安全性算法对T0时刻的资源分配进行分析,由表2-17可知,在T0时刻存在着一个安全序列{P1, P3, P4, P2, P0},故系统是安全的。

表2-16 T0时刻的资源分配
进程 / 资源情况 Max
A  B  C
Allocation
A  B  C
Need
A  B  C
Available
A  B  C
P0 7  5  3 0  1  0 7  4  3 3  3  2
(2  3  0)
P1 3  2  2 2  0  0
(3  0  2)
1  2  2
(0  2  0)

P2 9  0  2 3  0  2 6  0  0
P3 2  2  2 2  1  1 0  1  1
P4 4  3  3 0  0  2 4  3  1

表2-17 T0时刻的安全序列
进程 / 资源情况 Work
A  B  C
Need
A  B  C
Allocation
A  B  C
Work+Allocation
A  B  C
Finish
P1 3  3  2 1  2  2 2  0  0 5  3  2 true
P3 5  3  2 0  1  1 2  1  1 7  4  3 true
P4 7  4  3 4  3  1 0  0  2 7  4  5 true
P2 7  4  5 6  0  0 3  0  2 10  4  7 true
P0 10  4  7 7  4  3 0  1  0 10  5  7 true

2) P1请求资源
P1发出请求矢量Request1(l,, 0, 2),系统按银行家算法进行检查:
  • Request1(1, 0, 2) <= Need1(l, 2, 2)。
  • Request1(1, 0, 2) <= Available1(3, 3, 2)。
  • 系统先假定可为P1分配资源,并修改Available、Allocation1和Need1矢量,由此形成的资源变化情况见表2-18。
  • 再利用安全性算法检查此时系统是否安全。

表2-18 P1申请资源时的安全性检测
进程 / 资源情况 Work
A  B  C
Need
A  B  C
Allocation
A  B  C
Work+ Allocation
A  B  C
Finish
P1 2  3  0 0  2  0 3  0  2 5  3  2 true
P3 5  3  2 0  1  1 2  1  1 7  4  3 true
P4 7  4  3 4  3  1 0  0  2 7  4  5 true
P0 7  4  5 7  4  3 0  1  0 7  5  5 true
P2 7  5  5 6  0  0 3  0  2 10  5  7 true

3) P4请求资源
P4发出请求矢量Request4(3, 3, 0),系统按银行家算法进行检查:
  • Request4(3, 3, 0) <= Need4(4, 3, 1)。
  • Request4(3, 3, 0) > Available(2, 3, 0),让 P4 等待。

4) P0请求资源
P0发出请求矢量Request0(0, 2, 0),系统按银行家算法进行检查:
  • Request0(0, 2, 0) <= Need0(7, 4, 3)。
  • Request0(0, 2, 0) <= Available(2, 3, 0)。
  • 系统暂时先假定可为P0分配资源,并修改有关数据,见表2-19。

表2-19 为P0分配资源后的有关资源数据
进程 / 资源情况 Allocation
A  B  C
Need
A  B  C
Available
A  B  C
P0 0  3  0 7  2  3 2  1  0
P1 3  0  2 0  2  0
P2 3  0  2 6  0  0
P3 2  1  1 0  1  1
P4 0  0  2 4  3  1

5) 进行安全性检测。
可用资源Available(2, 1, 0)已不能满足任何进程的需要,故系统进入不安全状态,此时系统不分配资源。

2.20 死锁的检测和解除

前面绍的死锁预防和避免算法,都是在为进程分配资源时施加限制条件或进行检测,若系统为进程分配资源时不釆取任何措施,则应该提供死锁检测和解除的手段。

资源分配图

系统死锁,可利用资源分配图来描述。如图2-17所示,用圆圈代表一个进程,用框代表一类资源。由于一种类型的资源可能有多个,用框中的一个点代表一类资源中的一个资源。从进程到资源的有向边叫请求边,表示该进程申请一个单位的该类资源;从资源到进程的边叫分配边,表示该类资源已经有一个资源被分配给了该进程。


图2-17  资源分配示例图

在图2-17所示的资源分配图中,进程P1已经分得了两个R1资源,并又请求一个R2 资源;进程P2分得了一个R1和一个R2资源,并又请求一个R1资源。

死锁定理

可以通过将资源分配图简化的方法来检测系统状态S是否为死锁状态。简化方法如下:

1) 在资源分配图中,找出既不阻塞又不是孤点的进程Pi(即找出一条有向边与它相连,且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。若所有的连接该进程的边均满足上述条件,则这个进程能继续运行直至完成,然后释放它所占有的所有资源)。消去它所有的请求边和分配边,使之成为孤立的结点。在图2-18(a)中,P1是满足这一条件的进程结点,将P1的所有边消去,便得到图248(b)所示的情况。

2) 进程Pi所释放的资源,可以唤醒某些因等待这些资源而阻塞的进程,原来的阻塞进程可能变为非阻塞进程。在图2-17中,进程P2就满足这样的条件。根据第1) 条中的方法进行一系列简化后,若能消去图中所有的边,则称该图是可完全简化的,如图2-18(c)所示。

S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的,该条件为死锁定理。

死锁的解除

一旦检测出死锁,就应立即釆取相应的措施,以解除死锁。死锁解除的主要方法有:

1) 资源剥夺法。挂起某些死锁进程,并抢占它的资源,将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源,而处于资源匮乏的状态。

2) 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。



图2-18  资源分配图的化简

3) 进程回退法。让一(多)个进程回退到足以回避死锁的地步,进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息,设置还原点。

2.21 关于进程和线程的知识点汇总

进程与程序的区别与联系

1) 进程是程序及其数据在计算机上的一次运行活动,是一个动态的概念。进程的运行实体是程序,离开程序的进程没有存在的意义。从静态角度看,进程是由程序、数据和进程控制块(PCB)三部分组成的。而程序是一组有序的指令集合,是一种静态的概念。

2) 进程是程序的一次执行过程,它是动态地创建和消亡的,具有一定的生命周期,是暂时存在的;而程序则是一组代码的集合,它是永久存在的,可长期保存。

3) 一个进程可以执行一个或几个程序,一个程序也可以构成多个进程。进程可创建进程,而程序不可能形成新的程序

4) 进程与程序的组成不同。进程的组成包括程序、数据和PCB。

死锁与饥饿

具有等待队列的信号量的实现可能导致这样的情况:两个或多个进程无限地等待一个事件,而该事件只能由这些等待进程之一来产生。这里的事件是V操作的执行(即释放资源)。当出现这样的状态时,这些进程称为死锁(Dead locked)。

为了加以说明,考虑到一个系统由两个进程P0和P1组成,每个进程都访问两个信号量S和Q,这两个信号量的初值均为1。
  1. P0 () {
  2. While (1){
  3. P(S) ;
  4. P(Q);
  5. // …
  6. V(S) ;
  7. V(Q) ;
  8. }
  9. }
  1. p1() {
  2. While(1){
  3. P(Q);
  4. P(S);
  5. // …
  6. V(Q);
  7. V(S);
  8. }
  9. }

假设进程P0执行P(S),接着进程P1执行P(Q)。当进程P0执行P(Q)时,它必须等待直到进程P1执行V(Q)。类似地,当进程P1执行P(S),它必须等待直到进程P0执行V(S)。由于这两个V操作都不能执行,那么进程P0和进程P1就死锁了。

说一组进程处于死锁状态是指:组内的每个进程都等待一个事件,而该事件只可能由组内的另一个进程产生。这里所关心的主要是事件是资源的获取和释放。

与死锁相关的另一个问题是无限期阻塞(Indefinite Blocking)或“饥饿” (Starvation),即进程在信号量内无穷等待的情况。

产生饥饿的主要原因是:在一个动态系统中,对于每类系统资源,操作系统需要确定一个分配策略,当多个进程同时申请某类资源时,由分配策略确定资源分配给进程的次序。有时资源分配策略可能是不公平的,即不能保证等待时间上界的存在。在这种情况下,即使系统没有发生死锁,某些进程也可能会长时间等待。当等待时间给进程推进和响应带来明显影响时,称发生了进程“饥饿”,当“饥饿”到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被“饿死”。

例如,当有多个进程需要打印文件时,如果系统分配打印机的策略是最短文件优先,那么长文件的打印任务将由于短文件的源源不断到来而被无限期推迟,导致最终的“饥饿”甚至“饿死”。

“饥饿”并不表示系统一定死锁,但至少有一个进程的执行被无限期推迟。“饥饿”与死锁的主要差别有:
  • 进入“饥饿”状态的进程可以只有一个,而由于循环等待条件而进入死锁状态的进程却必须大于或等于两个。
  • 处于“饥饿”状态的进程可以是一个就绪进程,如静态优先权调度算法时的低优先权进程,而处于死锁状态的进程则必定是阻塞进程。

银行家算法的工作原理

银行家算法的主要思想是避免系统进入不安全状态。在每次进行资源分配时,它首先检查系统是否有足够的资源满足要求,如果有,则先进行分配,并对分配后的新状态进行安全性检查。如果新状态安全,则正式分配上述资源,否则就拒绝分配上述资源。这样,它保证系统始终处于安全状态,从而避免死锁现象的发生。

进程同步、互斥的区别和联系

并发进程的执行会产生相互制约的关系:一种是进程之间竞争使用临界资源,只能让它们逐个使用,这种现象称为互斥,是一种竞争关系;另一种是进程之间协同完成任务,在关键点上等待另一个进程发来的消息,以便协同一致,是一种协作关系。

作业和进程的关系

进程是系统资源的使用者,系统的资源大部分都是以进程为单位分配的。而用户使用计算机是为了实现一串相关的任务,通常把用户要求计算机完成的这一串任务称为作业。

1) 批处理系统中作业与进程的关系(进程组织)

批处理系统中的可以通过磁记录设备或卡片机向系统提交批作业,由系统的SPOOLing 输入进程将作业放入磁盘的输入井中,作为后备作业。作业调度程序(一般也作为独立的进程运行)每当选择一道后备作业运行时,首先为该作业创建一个进程(称为该作业的根进程)。该进程将执行作业控制语言解释程序解释该作业的作业说明书。父进程在运行过程中可以动态地创建一个或多个子进程,执行说明书中的语句。
例如,对一条编译的语句,该进程可以创建一个子进程执行编译程序对用户源程序进行编译。类似地,子进程也可以继续创建子进程去完成指定的功能。因此,一个作业就动态地转换成了一组运行实体——进程族。当父进程遇到作业说明书中的“撤出作业”的语句时,将该作业从运行状态改变为完成状态,将作业及相关结果送入磁盘上的输出井。作业终止进程负责将输出井中的作业利用打印机输出,回收作业所占用的资源,删除作业有关数据结构,删除作业在磁盘输出井中的信息,等等。作业终止进程撤除一道作业后,可向作业调度进程请求进行新的作业调度。至此,一道进入系统运行的作业全部结束。

2) 分时系统中作业与进程的关系

在分时系统中,作业的提交方法、组织形式均与批处理作业有很大差异。分时系统的用户通过命令语言逐条地与系统应答式地输入命令,提交作业步。每输入一条(或一组)命令,便直接在系统内部对应一个(或若干个)进程。在系统启动时,系统为每个终端设备建立一个进程(称为终端进程),该进程执行命令解释程序,命令解释程序从终端设备读入命令解释执行用户输入的每一条命令。对于每一条终端命令,可以创建一个子进程去具体执行。若当前的终端命令是一条后台命令,则可以和下一条终端命令并行处理。各子进程在运行过程中完全可以根据需要创建子孙进程。终端命令所对应的进程结束后,命令的功能也相应处理完毕。用户本次上机完毕,用户通过一条登出命令即结束上机过程。

分时系统的作业就是用户的一次上机交互过程,可以认为终端进程的创建是一个交互作业的开始,登出命令运行结束代表用户交互作业的终止。

命令解释程序流程扮演着批处理系统中作业控制语言解释程序的角色,只不过命令解释程序是从用户终端接收命令。

3) 交互地提交批作业

在同时支持交互和批处理的操作系统中,人们可以用交互的方式准备好批作业的有关程序、数据及作业控制说明书。
比如,可用交互式系统提供的全屏幕编辑命令编辑好自编的一个天气预报程序,用编译及装配命令将程序变成可执行文件,用调试命令进行程序调试。在调试成功后,用户每天都要做如下工作:准备原始天气数据,运行天气预报执行文件处理原始数据,把结果打印出来等。这时,用交互系统提供的全屏幕编辑命令编辑好将要提交的作业控制说明书文件,如Windows系统的BAT文件和Linux系统的sh文件。然后用一条作业提交命令将作业提交给系统作业队列中。系统有专门的作业调度进程负责从作业队列中选择作业,为被选取的作业创建一个父进程运行命令解释程序,解释执行作业控制说明书文件中的命令。


2015-09-09 12:44:00 as02446418 阅读数 5953
  • sql server 性能优化和日常管理维护

    课程总结sql server运行过程中对系统资源的使用和由此产生性能问题,介绍数据库规划设计、事务和锁的基本知识,如何处理阻塞和死锁,优化索引和读懂统计信息和执行计划等知识,同时详细介绍SQL 2014新功能特性内存优化表、列存储索引、alwayOn高可用。

    11719 人正在学习 去看看 宋立桓

产生死锁的原因主要是:
(1) 因为系统资源不足。
(2) 进程运行推进的顺序不合适。
(3) 资源分配不当等。
产生死锁的四个必要条件:
(1)互斥条件:一个资源每次只能被一个进程使用。
(2)请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。
(3)不剥夺条件:进程已获得的资源,在末使用完之前,不能强行剥夺。
(4)循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
避免死锁:
死锁的预防是通过破坏产生条件来阻止死锁的产生,但这种方法破坏了系统的并行性和并发性。
死锁产生的前三个条件是死锁产生的必要条件,也就是说要产生死锁必须具备的条件,而不是存在这3个条件就一定产生死锁,那么只要在逻辑上回避了第四个条件就可以避免死锁。
避免死锁采用的是允许前三个条件存在,但通过合理的资源分配算法来确保永远不会形成环形等待的封闭进程链,从而避免死锁。该方法支持多个进程的并行执行,为了避免死锁,系统动态的确定是否分配一个资源给请求的进程。
预防死锁 :具体的做法是破坏产生死锁的四个必要条件之一

进程死锁概念

阅读数 329

数据库死锁

阅读数 284

没有更多推荐了,返回首页