现代操作系统.ppt

《现代操作系统.ppt》由会员分享，可在线阅读，更多相关《现代操作系统.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、死死 锁锁主要内容主要内容一、死锁产生一、死锁产生二、死锁处理二、死锁处理三、分布式死锁处理技术三、分布式死锁处理技术一、死锁产生一、死锁产生死锁的基本概念死锁的基本概念如果一个进程集合中的每个进程都在等待只能由该如果一个进程集合中的每个进程都在等待只能由该组进程中的其他进程才能引发的事件，那么，该组组进程中的其他进程才能引发的事件，那么，该组进程是死锁的。进程是死锁的。死锁的起因死锁的起因竞争资源竞争资源进程推进顺序不当（非资源死锁）进程推进顺序不当（非资源死锁）P1P1和和P2P2并发执行并发执行,按下述顺序推进：按下述顺序推进：P1 Req(R1)P1 Req(R1)；Pl Req(R2

2、)Pl Req(R2)；P1 Rel(R1)P1 Rel(R1)；P1 Rel(R2)P1 Rel(R2)；P2 Req(R2)P2 Req(R2)；P2 Req(R1)P2 Req(R1)；P2 Rel(R1)P2 Rel(R1)；P2 Rel(R1)P2 Rel(R1)；两个进程可顺利完成。称这种不会两个进程可顺利完成。称这种不会引起进程死锁的推进顺序是引起进程死锁的推进顺序是合法合法的。的。R1R2P1P2进程推进顺序不当（非资源死锁）进程推进顺序不当（非资源死锁）P1P1和和P2P2并发执行并发执行,按下述顺序推进：按下述顺序推进：P1 Req(R1)P1 Req(R1)；P2 Req

3、(R2)P2 Req(R2)；P1 Rel(R2)P1 Rel(R2)；P2 Rel(R1)P2 Rel(R1)；两个进程不可顺利完成。称这种引两个进程不可顺利完成。称这种引起进程死锁的推进顺序是起进程死锁的推进顺序是非法非法的。的。死锁的基本概念死锁的基本概念如果一个进程集合中的每个进程都在等待只能由该如果一个进程集合中的每个进程都在等待只能由该组进程中的其他进程才能引发的事件，那么，该组组进程中的其他进程才能引发的事件，那么，该组进程是死锁的。进程是死锁的。一、死锁产生一、死锁产生死锁的条件死锁的条件1.1.互斥条件互斥条件每个资源要么已经分配给了一个进程，要么可用。每个资源要么已经分配给

4、了一个进程，要么可用。2.2.占有和等待条件占有和等待条件已经得到了某个资源的进程可以再请求新的资源。已经得到了某个资源的进程可以再请求新的资源。3.3.不可抢占条件不可抢占条件已经分配给一个进程的资源不能强制性地被抢占，它只能已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。被占有它的进程显式地释放。4.4.环路等待条件环路等待条件死锁发生时，系统中一定有由两个或两个以上的进程组成死锁发生时，系统中一定有由两个或两个以上的进程组成的一条环路，该环路中的每个进程都在等待着下一个进程的一条环路，该环路中的每个进程都在等待着下一个进程所占有的资源。所占有的资源。二、死锁处

5、理二、死锁处理有四种处理死锁的策略有四种处理死锁的策略1.1.忽略忽略2.2.鸵鸟算法鸵鸟算法2.2.让死锁发生，检测它们是否发生；一旦发生，采取让死锁发生，检测它们是否发生；一旦发生，采取行动解决行动解决死锁检测和恢复死锁检测和恢复3.3.仔细分配资源，动态地避免死锁仔细分配资源，动态地避免死锁死锁避免死锁避免4.4.破坏引起死锁的四个条件之一，防止死锁产生破坏引起死锁的四个条件之一，防止死锁产生死锁预防死锁预防1.1.鸵鸟算法鸵鸟算法如果死锁平均每如果死锁平均每5 5年发生一次，而每个月系统都会因年发生一次，而每个月系统都会因为硬件故障、编译器错误或者操作系统故障而崩溃一为硬件故障、编译器

6、错误或者操作系统故障而崩溃一次，那么大多数工程师不会以性能损失和可用性的代次，那么大多数工程师不会以性能损失和可用性的代价去防止死锁。价去防止死锁。大多数操作系统（如大多数操作系统（如UNIXUNIX和和WindowsWindows）处理这一问题）处理这一问题的办法是忽略它，因为解决死锁的代价通常很大，给的办法是忽略它，因为解决死锁的代价通常很大，给进程带来诸多不便，而多数用户宁可在极偶然情况下进程带来诸多不便，而多数用户宁可在极偶然情况下产生死锁，也不愿受很多不便限制。产生死锁，也不愿受很多不便限制。大多数操作系统潜在地受到了死锁的威胁，但这些大多数操作系统潜在地受到了死锁的威胁，但这些死锁

7、从来没有被检测到过，理所当然地自动解除了。死锁从来没有被检测到过，理所当然地自动解除了。2.2.死锁检测和死锁恢复死锁检测和死锁恢复对资源的分配不加任何限制，也不采取死锁避免措对资源的分配不加任何限制，也不采取死锁避免措施，但系统定时地运行一个施，但系统定时地运行一个“死锁检测死锁检测”程序，判断程序，判断系统内是否已出现死锁，如果检测到系统已发生了死系统内是否已出现死锁，如果检测到系统已发生了死锁，再采取措施解除它锁，再采取措施解除它每种类型一个资源的死锁检测常借助资源分配图；每种类型一个资源的死锁检测常借助资源分配图；每种类型多个资源的死锁检测常基于矩阵每种类型多个资源的死锁检测常基于矩阵

8、RASWUTVCFDBGE资源资源进程进程较好算法见（较好算法见（Even,1979）2.2.死锁检测和死锁恢复死锁检测和死锁恢复一种具体的死锁检测方法，检测算法步骤如下：一种具体的死锁检测方法，检测算法步骤如下：1)currentavail=available；2)如果如果allocationk,*!=0，令，令finishk=false;否则否则finishk=true；3)寻找一个寻找一个k，它应满足条件：，它应满足条件：(finishk=false)&(requestk,*=currentavail*);若找若找不到这样的不到这样的k，则转向，则转向5)；4)修改修改currentav

9、ail*=Currentavail*+allocationk,*;finishk=true;然后转向然后转向3)；5)如果存在如果存在k(1kn),finishk=false,则系统处于死锁状态，则系统处于死锁状态，并且并且finishk=false的的Pk为处于死锁的进程。为处于死锁的进程。2.2.死锁检测和死锁恢复死锁检测和死锁恢复利用抢占恢复利用抢占恢复临时将某个资源从它的当前所有者那里转移到另一临时将某个资源从它的当前所有者那里转移到另一个进程（对运行在大型主机上的批处理操作系统来说，个进程（对运行在大型主机上的批处理操作系统来说，要人工干预）要人工干预）比较困难；可行与否取决于资源本

10、身特性；挂起进比较困难；可行与否取决于资源本身特性；挂起进程的选择取决于哪个进程拥有较易收回的资源程的选择取决于哪个进程拥有较易收回的资源利用回退恢复利用回退恢复根据系统保存的检查点，让所有进程回退，直到足根据系统保存的检查点，让所有进程回退，直到足以解除死锁。进程检查点中应包括存储映像，资源状以解除死锁。进程检查点中应包括存储映像，资源状态，及资源的分配情况等态，及资源的分配情况等这种措施要求系统建立保存检查点、回退及重启机这种措施要求系统建立保存检查点、回退及重启机制；当进程执行时，一系列检查点文件被累积制；当进程执行时，一系列检查点文件被累积2.2.死锁检测和死锁恢复死锁检测和死锁恢复通

11、过杀死进程恢复通过杀死进程恢复杀掉环中的一个进程或选一个环外的进程作为牺牲杀掉环中的一个进程或选一个环外的进程作为牺牲品以释放该进程资源。品以释放该进程资源。杀掉环中进程的最坏情况是逐个撤销陷于死锁的进杀掉环中进程的最坏情况是逐个撤销陷于死锁的进程并回收其资源重新分派，直至死锁解除；杀掉环外程并回收其资源重新分派，直至死锁解除；杀掉环外进程时，该进程应正好持有环中某些进程所需的资源。进程时，该进程应正好持有环中某些进程所需的资源。杀死进程在第二次运行时可能是不安全的（如数据杀死进程在第二次运行时可能是不安全的（如数据库的更新进程），故最好杀死可以从头开始运行不会库的更新进程），故最好杀死可以从

12、头开始运行不会带来副作用的进程带来副作用的进程3.3.死锁避免死锁避免避免死锁的主要算法是基于安全状态的概念。避免死锁的主要算法是基于安全状态的概念。所谓安全状态即对于所有进程的资源请求，存在某所谓安全状态即对于所有进程的资源请求，存在某种调度次序能使得进程运行完毕。种调度次序能使得进程运行完毕。资源轨迹图与银行家算法资源轨迹图与银行家算法3.3.死锁避免死锁避免银行家算法银行家算法系统中的所有进程进入进程集合系统中的所有进程进入进程集合,在安全状态下系统收到进程的资源请求后在安全状态下系统收到进程的资源请求后,先把资源试探性先把资源试探性分配给它。分配给它。系统用剩下的可用资源和进程集合中其

13、他进程还要的资源系统用剩下的可用资源和进程集合中其他进程还要的资源数作比较，在进程集合中找到剩余资源能满足最大需求量数作比较，在进程集合中找到剩余资源能满足最大需求量的进程的进程,从而从而,保证这个进程运行完毕并归还全部资源。保证这个进程运行完毕并归还全部资源。把这个进程从集合中去掉把这个进程从集合中去掉,系统的剩余资源更多了系统的剩余资源更多了,反复执反复执行上述步骤。行上述步骤。最后最后,检查进程集合检查进程集合,若为空表明本次申请可行若为空表明本次申请可行,系统处于安系统处于安全状态全状态,可实施本次分配可实施本次分配;否则否则,有进程执行不完，系统处于有进程执行不完，系统处于不安全状态

14、不安全状态,本次资源分配暂不实施本次资源分配暂不实施,让申请进程等待。让申请进程等待。3.3.死锁避免死锁避免银行家算法银行家算法processAllocationClaimAvailableABCABCABCP0010753332P1200322P2302902P3211222P4002433可以断言目前系统处于安全状态可以断言目前系统处于安全状态,因为因为,序列序列P1,P3,P4,P2,P0能满足安全性条件。能满足安全性条件。3.3.死锁避免死锁避免死锁避免算法与死锁检测算法是类似的，死锁避免算法与死锁检测算法是类似的，不同在于后者考虑了检查每个进程还需要不同在于后者考虑了检查每个进程还

15、需要的所有资源能否满足要求；而前者则仅要的所有资源能否满足要求；而前者则仅要根据进程的当前申请资源量来判断系统是根据进程的当前申请资源量来判断系统是否进入了不安全状态。否进入了不安全状态。4.4.死锁预防死锁预防通过限制进程的资源请求来达到预防死锁的目的，都通过限制进程的资源请求来达到预防死锁的目的，都是通过打破四个死锁条件中的一个条件来实现的。是通过打破四个死锁条件中的一个条件来实现的。破坏占有和等待条件破坏占有和等待条件所有进程在开始执行前请求所需的全部资源所有进程在开始执行前请求所需的全部资源优点：易实现，安全，有效防死锁优点：易实现，安全，有效防死锁缺点：很多进程直到开始运行时才知道它

16、需要多少资源；缺点：很多进程直到开始运行时才知道它需要多少资源；资源利用率不高，进程推迟运行资源利用率不高，进程推迟运行大型机批处理系统要求用户在所提交作业的第一行列出所大型机批处理系统要求用户在所提交作业的第一行列出所需资源，系统分配所需全部资源，直到作业完成回收。需资源，系统分配所需全部资源，直到作业完成回收。当一个进程请求资源时，先暂时释放其当前占有的当一个进程请求资源时，先暂时释放其当前占有的所有资源，然后再尝试一次获得所需全部资源所有资源，然后再尝试一次获得所需全部资源4.4.死锁预防死锁预防破坏不可抢占条件破坏不可抢占条件一个已保持了某些资源的进程，若新的资源要求不一个已保持了某些

17、资源的进程，若新的资源要求不能立即得到满足，它必须释放已保持的所有资源。能立即得到满足，它必须释放已保持的所有资源。实现比较复杂，且代价很大；一个资源在使用一段时间后实现比较复杂，且代价很大；一个资源在使用一段时间后被释放可能会造成前阶段工作的失效。被释放可能会造成前阶段工作的失效。破坏循环等待条件破坏循环等待条件保证每个进程在任何时刻只占用一个资源。保证每个进程在任何时刻只占用一个资源。对所有资源统一编号对所有资源统一编号所有资源都被赋予一个唯一的数字编号。一个进程可以请所有资源都被赋予一个唯一的数字编号。一个进程可以请求一个有唯一编号求一个有唯一编号i i的资源，条件是该进程没有占用编号小

18、的资源，条件是该进程没有占用编号小于或等于于或等于i i的资源。的资源。可能产生饥饿问题可能产生饥饿问题4.4.死锁预防死锁预防破坏互斥条件破坏互斥条件资源不被一个进程独占，采用资源不被一个进程独占，采用spoolingspooling技术技术通过多道程序技术将一台物理通过多道程序技术将一台物理CPUCPU虚拟为多台逻辑虚拟为多台逻辑CPUCPU，从，从而允许多个用户共享一台主机，是对脱机输入输出的模拟。而允许多个用户共享一台主机，是对脱机输入输出的模拟。spoolingspooling系统必须建立在具有系统必须建立在具有多道程序功能多道程序功能的操作系统上，的操作系统上，还应有还应有高速随机

19、外存高速随机外存的支持，常采用的支持，常采用磁盘存储技术磁盘存储技术。不适用于所有资源（如进程表）；对磁盘空间本身的竞争不适用于所有资源（如进程表）；对磁盘空间本身的竞争也可能引起死锁也可能引起死锁避免分配不是绝对必需的资源，尽量做到尽可能少避免分配不是绝对必需的资源，尽量做到尽可能少的进程可以真正请求资源。的进程可以真正请求资源。Spooling技术技术当系统进入多道程序设计后，完全可以利用其中的一道程序，当系统进入多道程序设计后，完全可以利用其中的一道程序，来模拟脱机输入时的外围控制机功能，把低速来模拟脱机输入时的外围控制机功能，把低速I/O设备上的数设备上的数据传送到高速磁盘上，再利用另

20、一道程序来模拟脱机输出时外据传送到高速磁盘上，再利用另一道程序来模拟脱机输出时外围控制机功能，把数据从磁盘传送到低速输出设备上。这样，围控制机功能，把数据从磁盘传送到低速输出设备上。这样，便可在主机的直接控制下，实现便可在主机的直接控制下，实现脱机输入输出功能脱机输入输出功能。此时的外。此时的外围操作与围操作与CPU对数据的处理同时进行，我们把这种对数据的处理同时进行，我们把这种在联机情况在联机情况下实现的同时外围操作下实现的同时外围操作称为称为spooling（SimultaneousPeripheralOperationOn-Line）,或称为假脱机操作。或称为假脱机操作。Spooling

21、技术特点：技术特点：1）提高了）提高了I/O速度；速度；2）将独占设备改为）将独占设备改为共享设备；共享设备；3）实现了虚拟设备功能。）实现了虚拟设备功能。共享打印机共享打印机打印机是经常要用到的输出设备，属于独占设备，利用打印机是经常要用到的输出设备，属于独占设备，利用spooling技术，可将之改造为一台可供多个用户共享的设备。当用户进程技术，可将之改造为一台可供多个用户共享的设备。当用户进程请求打印输出时，请求打印输出时，spooling系统同意为他打印输出，但并不真正系统同意为他打印输出，但并不真正立即把打印机分配给该用户进程，而只为他做两件事：立即把打印机分配给该用户进程，而只为他做

22、两件事：（1）由）由输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的输出进程在输出井中为之申请一个空闲磁盘块区，并将要打印的数据送入其中；（数据送入其中；（2）输出进程再为用户进程申请一张空白的用）输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入其中，再将该表挂到请户请求打印表，并将用户的打印要求填入其中，再将该表挂到请求队列上。如果还有进程要求打印输出，系统仍可接受该请求，求队列上。如果还有进程要求打印输出，系统仍可接受该请求，也同样为该进程作上述两件事。也同样为该进程作上述两件事。若打印机空闲，输出程序从请求打印队列的队首取出一张请求打若打印机空闲，输出程序

23、从请求打印队列的队首取出一张请求打印表，根据表中的要求将要打印的数据，从输出井传送到内存缓印表，根据表中的要求将要打印的数据，从输出井传送到内存缓冲区，再由打印机进行打印。打印完后，输出进程再查看请求打冲区，再由打印机进行打印。打印完后，输出进程再查看请求打印队列中是否还有等待打印的请求表。若有，又取出队列中的第印队列中是否还有等待打印的请求表。若有，又取出队列中的第一张表，并根据其中的要求进行打印，如此下去，直至请求打印一张表，并根据其中的要求进行打印，如此下去，直至请求打印队列为空，输出进程才将自己阻塞起来。仅当下次再有打印请求队列为空，输出进程才将自己阻塞起来。仅当下次再有打印请求时，输

24、出进程才被唤醒。时，输出进程才被唤醒。4.4.死锁预防死锁预防条件处理方式占有和等待在开始就请求全部资源不可抢占抢占资源循环等待对资源按数值编号互斥一切都使用假脱机技术采用层次分配策略（破坏条件采用层次分配策略（破坏条件2 2和和4 4）资源被分成多个层次资源被分成多个层次当当进进程程得得到到某某一一层层的的一一个个资资源源后后，它它只只能能再再申申请请较较高层次的资源高层次的资源当当进进程程要要释释放放某某层层的的一一个个资资源源时时，必必须须先先释释放放占占有有的较高层次的资源的较高层次的资源当当进进程程得得到到某某一一层层的的一一个个资资源源后后，它它想想申申请请该该层层的的另一个资源时

25、，必须先释放该层中的已占资源另一个资源时，必须先释放该层中的已占资源4.4.死锁预防（补充）死锁预防（补充）三、分布式死锁处理技术三、分布式死锁处理技术死锁检测死锁检测核心是维护核心是维护等待图等待图。局部等待图：描述的是结点内访问相同数据项的事务之间局部等待图：描述的是结点内访问相同数据项的事务之间的等待解锁的关系。的等待解锁的关系。全局等待图：对各场地局部等待图的综合。全局等待图：对各场地局部等待图的综合。图中的点表示正在访问该场地某数据项的事务，有向边图中的点表示正在访问该场地某数据项的事务，有向边PQPQ反映了事务反映了事务P P等待事务等待事务Q Q解锁的依赖关系。解锁的依赖关系。任

26、何场地的局部等待图若有环，则表示出现死锁，但即使任何场地的局部等待图若有环，则表示出现死锁，但即使所有局部等待图都无环，全局等待图仍可能有环，可有死所有局部等待图都无环，全局等待图仍可能有环，可有死锁发生。锁发生。三、分布式死锁处理技术三、分布式死锁处理技术死锁检测死锁检测集中式死锁检测集中式死锁检测整个系统只有一个协调者，它维持全局等待图，全局等待整个系统只有一个协调者，它维持全局等待图，全局等待图是由局部等待图组合而成的图是由局部等待图组合而成的全局资源分配图全局资源分配图(或等待图或等待图)的获得方法：的获得方法：1)1)当在局部图中有边被加入或删除时，向协调者发送一个报当在局部图中有边

27、被加入或删除时，向协调者发送一个报文，协调者根据报文信息对全局图进行更新。文，协调者根据报文信息对全局图进行更新。2)2)定期地更新，每个机器定期地向协调者发送自上次更新以定期地更新，每个机器定期地向协调者发送自上次更新以来所有添加的边和删除的边，协调者根据报文信息对全局来所有添加的边和删除的边，协调者根据报文信息对全局图进行更新。图进行更新。3)3)当协调者认为需要运行回路检测算法时，它要求所有的机当协调者认为需要运行回路检测算法时，它要求所有的机器向它发送局部图的更新信息，协调者对全局图进行更新。器向它发送局部图的更新信息，协调者对全局图进行更新。4)4)当开始死锁检测时，协调者便查找全局

28、等待图。如果发当开始死锁检测时，协调者便查找全局等待图。如果发现回路，一个进程就会被卷回，从而打破循环等待。现回路，一个进程就会被卷回，从而打破循环等待。5)5)缺点：容易产生假死锁的情况缺点：容易产生假死锁的情况 。三、分布式死锁处理技术三、分布式死锁处理技术死锁检测死锁检测分布式死锁检测分布式死锁检测每个节点维持一个全局等待图的拷贝，独立进行死锁检每个节点维持一个全局等待图的拷贝，独立进行死锁检测；每个节点全局等待图分解到若干个节点上进行维护，测；每个节点全局等待图分解到若干个节点上进行维护，需要时通过消息交换组合起来。需要时通过消息交换组合起来。Knapp将其分为四类将其分为四类路径推动

29、算法路径推动算法(path-pushingalgorithm)。在每个节点建立。在每个节点建立部分的全局等待图，当需要进行死锁检测时，节点将自己部分的全局等待图，当需要进行死锁检测时，节点将自己的全局等待图向邻接点进行扩散；接到消息的节点用自己的全局等待图向邻接点进行扩散；接到消息的节点用自己的等待图信息完善全局等待图并再进行邻接点扩散操作，的等待图信息完善全局等待图并再进行邻接点扩散操作，直至在某节点形成最终的全局等待图，得到是否存在死锁直至在某节点形成最终的全局等待图，得到是否存在死锁的结论并将检测结论通知各个节点。的结论并将检测结论通知各个节点。这种算法状态比较难这种算法状态比较难一致，

30、可能依据部分等待图来判断。一致，可能依据部分等待图来判断。三、分布式死锁处理技术三、分布式死锁处理技术边跟踪算法边跟踪算法(edge-chasingalgorithm)。分布式网络结构图中。分布式网络结构图中的回路可以通过沿图的边传播一种叫探测器的特殊信息来的回路可以通过沿图的边传播一种叫探测器的特殊信息来检测。当一个发起者得到一个与自己发送的探测器相匹配检测。当一个发起者得到一个与自己发送的探测器相匹配的探测器时，它就知道它在图中的一个回路里。的探测器时，它就知道它在图中的一个回路里。扩散计算扩散计算(diffusingputation)。当需要检测时，进程向它所。当需要检测时，进程向它所依

31、赖的进程发起询问，并将因此而引发的各个询问关联成依赖的进程发起询问，并将因此而引发的各个询问关联成等待图；或者通过接收应答将图消解，或者从中发现死锁。等待图；或者通过接收应答将图消解，或者从中发现死锁。全局状态检测全局状态检测(globalstatedetection)。使用。使用Chandy和和Lamport的快照方法来建立一致的全局状态图，以此来检的快照方法来建立一致的全局状态图，以此来检测是否有死锁发生。测是否有死锁发生。等级式死锁检测等级式死锁检测系统的节点按树型结构关联起来，由子树的根节点负责系统的节点按树型结构关联起来，由子树的根节点负责对本子树进行死锁检测。整个树的根节点作为中心

32、节点，对本子树进行死锁检测。整个树的根节点作为中心节点，可以为每个子树确定作为控制节点的根节点。可以为每个子树确定作为控制节点的根节点。子树之间应当是不相关的子树之间应当是不相关的v关于死锁检测和恢复的研究方向：关于死锁检测和恢复的研究方向：1)算法正确性。严格证明死锁检测算法的正确性是困难的，由于报文的传输延迟是不可预料的，所以得到一致的全局状态是很困难的。2)算法性能。需要在信息流量(监测和恢复算法的复杂性)和死锁持续时间(监测和恢复的速度)之间达成妥协。3)死锁解决。一个好而快的死锁检测算法可能并不能提供足够的信息用于解决死锁。4)假死锁。一个检测程序不仅要满足前进要求，即必须在有限的时

33、间内发现死锁，还要满足安全要求。如果一个死锁被发现，那么这个死锁应该是确实存在的。5)死锁概率。检测和恢复算法的设计依赖于给定系统中死锁发生的概率。三、分布式死锁处理技术三、分布式死锁处理技术三、分布式死锁处理技术三、分布式死锁处理技术死锁预防死锁预防由于消息传输延迟的不确定性，分布式系统中的物由于消息传输延迟的不确定性，分布式系统中的物理时钟无法完美同步；而全局时钟的缺乏，使得后理时钟无法完美同步；而全局时钟的缺乏，使得后后发生的事件有可能赋予较早的时间标记。后发生的事件有可能赋予较早的时间标记。因此，因此，Lamport(1978)指出：所有的进程需要在时指出：所有的进程需要在时间的发生间

34、的发生顺序上达成一致；不进行交互的两个进程顺序上达成一致；不进行交互的两个进程之间不需要时钟同步；所有节点应具有相同时间，之间不需要时钟同步；所有节点应具有相同时间，但该时间不一定与实际时间相同。但该时间不一定与实际时间相同。分布式死锁预防主要基于分布式死锁预防主要基于时间戳时间戳三、分布式死锁处理技术三、分布式死锁处理技术死锁预防死锁预防基于时间戳的预防死锁方法基于时间戳的预防死锁方法包括两种死锁预防方案，这两种方案相互补充。包括两种死锁预防方案，这两种方案相互补充。等待等待死亡方案死亡方案(wait-diescheme)。该方案是基于非剥夺。该方案是基于非剥夺方法。当进程方法。当进程Pi请

35、求的资源正被进程请求的资源正被进程Pj占有时，只有当占有时，只有当Pi的时间戳比进程的时间戳比进程Pj的时间戳小时，即的时间戳小时，即Pi比比Pj老时，老时，Pi才能才能等待。否则等待。否则Pi被卷回被卷回(roll-back)，即死亡。，即死亡。伤害伤害等待方案等待方案(wound-waitscheme)。它是一种基于剥。它是一种基于剥夺的方法。当进程夺的方法。当进程Pi请求的资源正被进程请求的资源正被进程Pj占有时，只有占有时，只有当进程当进程Pi的时间戳比进程的时间戳比进程Pj的时间戳大时，即的时间戳大时，即Pi比比Pj年轻年轻时，时，Pi才能等待。否则才能等待。否则Pj被卷回被卷回(roll-back)，即死亡。，即死亡。