OS03实时调度死锁2014-2015-2

1、操作系统操作系统Operating Systems3.4 实时调度实时调度 实现实时调度的基本条件实现实时调度的基本条件1.1.必要信息必要信息就绪时间、开始截至时间、完成截至时间、处理时间；就绪时间、开始截至时间、完成截至时间、处理时间；资源要求；优先级；资源要求；优先级； 2.2.系统处理能力强系统处理能力强3.3.采用抢占式机制采用抢占式机制-硬实时任务；截止时间要求；硬实时任务；截止时间要求；4.4.有快速切换机制有快速切换机制-快速响应外部中断；快速任务分派；快速响应外部中断；快速任务分派；11miiiPCNPCmiii1处理时间处理时间: : C Ci i; ;周期时间周期时间:

2、: P Pi i系统处理能力系统处理能力例：例：A任务周期为任务周期为10ms，执行，执行5ms； B任务周期为任务周期为15ms, 执行执行10ms (5/10)+(10/15)=35/30，系统处理不了系统处理不了A1B1A2B2任务执行任务执行t任务到达任务到达A1B1A2B2A3051015202530A4B3(A3错过错过)讨论讨论一个实时系统有四个周期性事件，周期分别为一个实时系统有四个周期性事件，周期分别为50、100、300和和250ms。若假设其处理时间分别需要。若假设其处理时间分别需要35、20、10和和x ms，则该系统可调度允许的，则该系统可调度允许的x值最大为多少？值

3、最大为多少？答：答：在单处理机情况下：在单处理机情况下： （35/50+20/100+10/200+x/250） 1 x 16.75ms 11miiiPC实时调度算法的分类实时调度算法的分类非抢占式非抢占式轮转调度轮转调度( (同质任务同质任务) )；优先调度优先调度 为时间要求严格的任务分配较高优先级为时间要求严格的任务分配较高优先级抢占式抢占式时钟中断优先；时钟中断优先；立即抢占优先立即抢占优先非抢占式轮转调度算法非抢占式轮转调度算法轮转调度轮转调度( (同质任务同质任务) )；l常用于工业生产的群控系统中常用于工业生产的群控系统中非抢占式优先调度算法非抢占式优先调度算法优先调度优先调度为

4、时间要求严格的任务分配较高优先级为时间要求严格的任务分配较高优先级 基于时钟中断的抢占式优先权调度算法基于时钟中断的抢占式优先权调度算法 某实时任务到达后，若优先级高于当前正在执行任务的优某实时任务到达后，若优先级高于当前正在执行任务的优先级，并先级，并不立即抢占不立即抢占当前任务的处理机，而是当前任务的处理机，而是等到时钟中等到时钟中断到来断到来后调度程序才剥夺当前任务的执行后调度程序才剥夺当前任务的执行立即抢占的优先权调度算法立即抢占的优先权调度算法 一旦有外部中断，一旦有外部中断，只要当前任务不在临界区内只要当前任务不在临界区内，便，便立即剥立即剥夺夺当前任务的执行，交处理机分配给要求中

5、断的紧迫任务当前任务的执行，交处理机分配给要求中断的紧迫任务常用的几种实时调度算法常用的几种实时调度算法最早截止时间优先算法最早截止时间优先算法非抢占式和抢占式非抢占式和抢占式EDFEDF算法用于非抢占调度的调度方式算法用于非抢占调度的调度方式 非抢占式调度方式用于非周期实时任务非抢占式调度方式用于非周期实时任务342开始截止时间开始截止时间任务到达任务到达12 3442任务执行任务执行t131通常的优先级调度不能适用于实时系统通常的优先级调度不能适用于实时系统A1B1A2B1A3任务任务执行执行t任务任务到达到达A1B1A2B2A3最后期限最后期限任务任务A A的周期时间为的周期时间为20

6、ms20 ms，每个周期的处理时间为，每个周期的处理时间为10 ms10 ms；任务任务B B的周期时间为的周期时间为50 ms50 ms，每个周期的处理时间为，每个周期的处理时间为25 ms25 ms固定优先级调度固定优先级调度 （A A有较高优先级）有较高优先级）A1A2A30102030405060100708090A4A5A6B3A4B2A5(B1错过错过)B1通常的优先级调度不能适用于实时系统通常的优先级调度不能适用于实时系统B1任务任务执行执行t任务任务到达到达A1B1A2B2A3最后期限最后期限任务任务A A的周期时间为的周期时间为20 ms20 ms，每个周期的处理时间为，每个

7、周期的处理时间为10 ms10 ms；任务任务B B的周期时间为的周期时间为50 ms50 ms，每个周期的处理时间为，每个周期的处理时间为25 ms25 ms固定优先级调度固定优先级调度 （B B有较高优先级）有较高优先级）A1A2A30102030405060100708090A4A5A6B3A4B2A5(A1错过错过)B1EDFEDF算法用于抢占调度方式算法用于抢占调度方式A1B1A2B1A3任务任务执行执行t任务任务到达到达A1B1A2B2A3最后期限最后期限任务任务A A的周期时间为的周期时间为20 ms20 ms，每个周期的处理时间为，每个周期的处理时间为10 ms10 ms；任务

8、任务B B的周期时间为的周期时间为50 ms50 ms，每个周期的处理时间为，每个周期的处理时间为25 ms25 msA1A2A30102030405060100708090A4A5A6B3A4B2A5B2A4B2A5B1最低松弛度优先（最低松弛度优先（ LLF LLF ）算法）算法松弛度松弛度= =必须完成时间必须完成时间- -本身运行时间本身运行时间- -当前时间当前时间 设有两个周期性实时任务设有两个周期性实时任务A A和和B B，分别每，分别每20ms,50ms20ms,50ms执行一执行一次，每次执行次，每次执行10ms,25ms10ms,25ms。则其须完成的时间为：。则其须完成的

9、时间为：A1,A2,A1,A2,和和B1,B2,B1,B2,，A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0利用利用LLFLLF算法进行调度的情况算法进行调度的情况t t1=01=0时，时，A1A1的松弛度的松弛度=20-10-0=10ms=20-10-0=10ms； B1B1的松弛度的松弛度=50-25-0=25ms;=50-25-0=25ms;A1A2A3A4A5A6A7A820406080100120140160B1B2B3t0松弛度松弛度= =必须完成时间必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间利用利用LLF算法

10、进行调度的情况算法进行调度的情况t8B2(10)松弛度松弛度= =必须完成时间必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间vt2=10t2=10，A1A1结束，结束，A2A2未到达未到达 vB1B1运行运行松弛度松弛度= =必须完成时间必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间vt3=30t3=30，A2A2的松弛度的松弛度=40ms-10ms-30ms=0ms=40ms-10ms-30ms=0ms B1 B1的松弛度的松弛度=50ms-5ms-30ms=15ms=50ms-5ms-30ms=15msvA2A2抢占运行抢占运行松弛度松弛

11、度= =必须完成时间必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间vt4=40t4=40，A3A3的松弛度的松弛度=60ms-10ms-40ms=10ms=60ms-10ms-40ms=10ms B1 B1的松弛度的松弛度=50ms-5ms-40ms=5ms=50ms-5ms-40ms=5msvB1B1运行运行松弛度松弛度= =必须完成时间必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间vt5=45t5=45，A3A3的松弛度的松弛度=60ms-10ms-45ms=5ms=60ms-10ms-45ms=5ms B2 B2未到达未到达vA3A3运

12、行运行松弛度松弛度= =必须完成时间必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间vt6=55t6=55，A3A3结束，结束，A4A4未到达未到达 vB2B2运行运行松弛度松弛度= =必须完成时间必须完成时间- -其本身的运行时间其本身的运行时间- -当前时间当前时间vt7=70t7=70，A4A4的松弛度的松弛度=80ms-10ms-70ms=0ms=80ms-10ms-70ms=0ms B2 B2的松弛度的松弛度=100ms-10ms-70ms=10ms=100ms-10ms-70ms=10msvA4A4运行运行松弛度松弛度= =必须完成时间必须完成时间- -其本

13、身的运行时间其本身的运行时间- -当前时间当前时间vt8=80t8=80，A5A5的松弛度的松弛度=100ms-10ms-80ms=10ms=100ms-10ms-80ms=10ms B2 B2的松弛度的松弛度=100ms-10ms-80ms=10ms=100ms-10ms-80ms=10msvB2B2运行（同样松弛度应先来先服务）运行（同样松弛度应先来先服务）A1B1A2B2A3A4A5任务到达任务到达最后期限最后期限A1A2A3A4B120304050607010803.5 产生死锁的原因和必要条件产生死锁的原因和必要条件死锁死锁l在多进程在运行过程中因争夺资源而造成的一种僵局，当进程处在

14、多进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们都将无法再向前推进。于这种僵局状态时，若无外力作用，它们都将无法再向前推进。产生死锁的原因产生死锁的原因 竞争资源竞争资源l当系统中供多个进程共享的资源，其当系统中供多个进程共享的资源，其数目不足数目不足以满足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。死锁。 进程间推进顺序非法。进程间推进顺序非法。l进程在运行过程中，请求和释放资源的顺序不当，也进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。同样会导致产生进程死锁。 产生

15、死锁的原因产生死锁的原因 3个进程共享个进程共享4个同种类型的资源，每个进程最大需要个同种类型的资源，每个进程最大需要2个个资源，请问该系统是否会因为竞争资源而死锁？资源，请问该系统是否会因为竞争资源而死锁？ R R系统有同类资源系统有同类资源m个，被个，被n个进程共享，当个进程共享，当mn 和和mn时，每时，每个进程最多可以请求多少个这类资源时，系统一定不会发生个进程最多可以请求多少个这类资源时，系统一定不会发生死锁？死锁？当当m n 时时:l每个进程最多申请每个进程最多申请1个这类资源时，系统一定不会发生死锁个这类资源时，系统一定不会发生死锁当当mn时时:假设每个进程最多申请假设每个进程最

16、多申请x个这类资源个这类资源l若每个进程申请若每个进程申请x-1个这类资源后，系统还剩下一个资源，个这类资源后，系统还剩下一个资源，就能保证某一个进程能分配到全部就能保证某一个进程能分配到全部x个资源，并能运行到底个资源，并能运行到底，最终释放这，最终释放这x个资源。即：个资源。即： n*（x -1） m x(m/n)+1竞争资源引起进程死锁竞争资源引起进程死锁 系统中的资源分成两类系统中的资源分成两类l可抢占性资源。可抢占性资源。如：如：CPU和主存和主存对于这类资源是不会引起死锁的对于这类资源是不会引起死锁的l不可抢占性资源。不可抢占性资源。 如：磁带机、打印机如：磁带机、打印机在系统中所

17、配置的不可抢占性资源，由于它们的数量不能在系统中所配置的不可抢占性资源，由于它们的数量不能满足诸进程运行的需要，会因争夺这些资源而陷入僵局。满足诸进程运行的需要，会因争夺这些资源而陷入僵局。竞争不可抢占性资源竞争不可抢占性资源R1R1R2R2m3m3竞争可消耗资源竞争可消耗资源可消耗资源（可消耗资源（临时性资源）临时性资源）l由一个进程产生，被另一进程使用一短暂时间后便无用的资由一个进程产生，被另一进程使用一短暂时间后便无用的资源，故也称之为消耗性资源源，故也称之为消耗性资源P1： send(p2,m1)； Receive(p3,m3)； P2： send(p3,m2)； Receive(p1

18、,m1)； P3： send(p1,m3)； Receive(p2,m2)； m2m2m1m1竞争可消耗资源竞争可消耗资源引起进程死锁引起进程死锁P1： Receive(p3,m3)；send(p2,m1)P2： Receive(p1,m1)；send(p3,m2)P3： Receive(p2,m2)；send(p1,m3)2. 进程推进顺序不当引起死锁进程推进顺序不当引起死锁 例例: 进程推进顺序不当产生死锁进程推进顺序不当产生死锁设系统有打印机、读卡机各一台，被进程设系统有打印机、读卡机各一台，被进程1和和P2共享。共享。两个进程并发执行，按下列次序请求和释放资源：两个进程并发执行，按下列

19、次序请求和释放资源： 进程进程1 进程进程P2 请求读卡机请求读卡机 请求打印机请求打印机 请求打印机请求打印机 请求读卡机请求读卡机 释放读卡机释放读卡机 释放读卡机释放读卡机 释放打印机释放打印机 释放打印机释放打印机 进程推进顺序进程推进顺序进程进程1 进程进程P2 请求读卡机请求读卡机 请求读卡机请求读卡机 请求打印机请求打印机 请求打印机请求打印机 释放读卡机释放读卡机 释放读卡机释放读卡机 释放打印机释放打印机 释放打印机释放打印机 死锁的基本概念死锁的基本概念这两个进程在并发执行过程中，可能会发生死锁。这两个进程在并发执行过程中，可能会发生死锁。大家可以思考一下，如何修改，进程才

20、不会发生大家可以思考一下，如何修改，进程才不会发生死锁？死锁？死锁的基本概念死锁的基本概念关于死锁的一些结论关于死锁的一些结论l参与死锁的进程参与死锁的进程最少是两个最少是两个l参与死锁的进程参与死锁的进程至少有两个已经占有资源至少有两个已经占有资源l参与死锁的所有进程参与死锁的所有进程都在等待资源都在等待资源l参与死锁的进程是当前系统中所有参与死锁的进程是当前系统中所有进程的子集进程的子集注：注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。溃。3.5.33.5.3产生死锁的必要条件产生死锁的必要条件互斥条件：互斥条件：l进程互斥使用资源

21、进程互斥使用资源请求和保持条件请求和保持条件：部分分配条件：部分分配条件l申请新资源时不释放已占有资源申请新资源时不释放已占有资源不可抢占条件：不可抢占条件：l一个进程不能抢夺其他进程占有的资源一个进程不能抢夺其他进程占有的资源环路条件：环路条件：l存在一组进程循环等待资源存在一组进程循环等待资源S1S1S3S3S2S2处理死锁的方法处理死锁的方法预防死锁。预防死锁。l破坏产生死锁的四个必要条件中的一个或几个条件破坏产生死锁的四个必要条件中的一个或几个条件 避免死锁。避免死锁。l在资源的动态分配过程中，用某种方法去防止系统进入在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免

22、发生死锁。不安全状态，从而避免发生死锁。 检测死锁。检测死锁。l通过系统所设置的检测机构，及时地检测出死锁的发生通过系统所设置的检测机构，及时地检测出死锁的发生；采取适当措施，从系统中将已发生的死锁清除掉。；采取适当措施，从系统中将已发生的死锁清除掉。 解除死锁。这是与检测死锁相配套的一种措施解除死锁。这是与检测死锁相配套的一种措施3.6预防死锁预防死锁一种较简单和直观的事先预防的方法。一种较简单和直观的事先预防的方法。l设置某些限制条件，去破坏产生死锁的四个必要条件设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁：中的一个或几个条件，来预防发生死锁：互斥条件互

23、斥条件请求和保持条件请求和保持条件不可抢占条件不可抢占条件环路条件环路条件1. 1. 破坏破坏“请求和保持请求和保持”条件条件破坏破坏“请求和保持请求和保持”条件条件l一个进程必须在一个进程必须在执行前执行前就就申请申请它所要的它所要的全部资源全部资源，l直到它所要的资源都得到满足后才开始执行。直到它所要的资源都得到满足后才开始执行。优点优点l简单、易于实现且很安全。简单、易于实现且很安全。缺点缺点l资源被严重浪费，严重地恶化了系统资源的利用率；资源被严重浪费，严重地恶化了系统资源的利用率；l使进程延迟运行，仅当进程在获得了其所需的全部资使进程延迟运行，仅当进程在获得了其所需的全部资源后，才能

24、开始运行。源后，才能开始运行。2.2.破坏破坏“不可抢占不可抢占”条件条件破坏破坏“不可抢占不可抢占”条件条件l当进程有新的资源请求时，如果得不到满足，要先释当进程有新的资源请求时，如果得不到满足，要先释放原先占有的资源，待以后重新申请。放原先占有的资源，待以后重新申请。l等价于等价于“被抢占被抢占”。该方法实现起来比较复杂，要付出很大的代价。该方法实现起来比较复杂，要付出很大的代价。l反复地申请和释放资源反复地申请和释放资源l进程的执行被无限地推迟进程的执行被无限地推迟只适用于对主存资源和处理器资源的分配只适用于对主存资源和处理器资源的分配3.3.破坏破坏“环路等待环路等待”条件条件破坏破坏

25、“环路等待环路等待”条件条件l把系统资源按类型排序，进程要按照资源的序号递增把系统资源按类型排序，进程要按照资源的序号递增的次序提出资源申请。的次序提出资源申请。优点优点l资源利用率和系统吞吐量都有较明显的改善。资源利用率和系统吞吐量都有较明显的改善。存在下述严重问题：存在下述严重问题：l限制了新类型设备的增加。限制了新类型设备的增加。l造成对资源的浪费。造成对资源的浪费。l必然会限制用户简单、自主地编程。必然会限制用户简单、自主地编程。 讨论讨论在哲学家就餐问题中，奇数号先取左手边的筷子，偶数号先取在哲学家就餐问题中，奇数号先取左手边的筷子，偶数号先取右手边的筷子。请说明为何不会产生死锁。右

26、手边的筷子。请说明为何不会产生死锁。3.73.7避免死锁避免死锁1. 1. 安全状态安全状态l指系统能按某种指系统能按某种进程顺序进程顺序(P(P1 1，P P2 2，P Pn n) )，来为每个进，来为每个进程程P Pi i分配其所需资源，直至满足每个进程对资源的分配其所需资源，直至满足每个进程对资源的最大最大需求需求，使每个进程都可顺利地完成。，使每个进程都可顺利地完成。l如果系统无法找到这样一个安全序列，则称系统处于不如果系统无法找到这样一个安全序列，则称系统处于不安全状态。安全状态。当系统进入不安全状态后，便有当系统进入不安全状态后，便有可能可能进而进入死锁状态。进而进入死锁状态。避免

27、死锁避免死锁的实质在于：的实质在于：l系统在进行资源分配时，如何使系统不进入不安全状态系统在进行资源分配时，如何使系统不进入不安全状态2 2安全状态之例安全状态之例假定系统中有三个进程假定系统中有三个进程P1、P2和和P3，共有，共有12台磁带机。台磁带机。T0时刻是安全的？时刻是安全的？+2-2=12安全状态之例安全状态之例假定系统中有三个进程假定系统中有三个进程P1、P2和和P3，共有，共有12台磁带机。台磁带机。+5-5=02安全状态之例安全状态之例假定系统中有三个进程假定系统中有三个进程P1、P2和和P3，共有，共有12台磁带机。台磁带机。安全序列：安全序列：P2 、P1、P3T0时刻

28、是安全的。时刻是安全的。+7-7=33由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。进入不安全状态。+1-1=23由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。进入不安全状态。+2-2=03由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态进

29、入不安全状态。进入不安全状态。3由安全状态向不安全状态的转换由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。进入不安全状态。从给从给P3分配了第分配了第3台磁带机开始，系统便又进入了不安全台磁带机开始，系统便又进入了不安全状态。状态。3.7.23.7.2利用银行家算法避免死锁利用银行家算法避免死锁1 1银行家算法中的数据结构银行家算法中的数据结构(1) (1) 可利用资源向量可利用资源向量Available Available l每类资源未分配数量向量每类资源未分配数量向量l含有含有m个元素的数组个

30、元素的数组l如果如果Availablej=KAvailablej=K，则表示系统中现有，则表示系统中现有R Rj j类资源类资源K K个。个。银行家算法中的数据结构银行家算法中的数据结构(2) (2) 最大需求矩阵最大需求矩阵MaxMax。一个一个n nm m的矩阵，它定义了系统中的矩阵，它定义了系统中n n个进程中的每一个进程个进程中的每一个进程对对m m类资源的最大需求。如果类资源的最大需求。如果Maxi,j=KMaxi,j=K，则表示进程，则表示进程i i需要需要R Rj j类资源的最大数目为类资源的最大数目为K。Max=Max=M M1111M M1212M M1m1mM M2121M

31、 M2121M M2121M Mn1n1M Mn1n1M Mnmnm银行家算法中的数据结构银行家算法中的数据结构(3) 分配矩阵分配矩阵Allocation。也是一个也是一个nm的矩阵，它定义了系统中每一类资源当前已的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。分配给每一进程的资源数。如果如果Allocationi,j=KAllocationi,j=K，则表示进程，则表示进程i i当前已分得当前已分得R j类资源类资源的数目为的数目为K。Allocation=Allocation=A A1111A A1212A A1m1mA A2121A A2121A A2121A An1n1

32、A An1n1A Anmnm银行家算法中的数据结构银行家算法中的数据结构(4) 需求矩阵需求矩阵Need。一个一个nm的矩阵，用以表示每一个进程尚需的各类资源的矩阵，用以表示每一个进程尚需的各类资源数。数。如果如果Needi,j=KNeedi,j=K，则表示进程，则表示进程i还需要还需要Rj类资源类资源K个，方个，方能完成其任务。能完成其任务。上述三个矩阵间存在下述关系：上述三个矩阵间存在下述关系：Needi, j=Maxi, j- Allocationi, j Needi, j=Maxi, j- Allocationi, j 2 2银行家算法银行家算法(1)(1)设设RequestReque

33、sti ij=Kj=K，表示，表示P Pi i需要需要K K个个R Rj j类资源。类资源。P Pi i发出资源请求发出资源请求RequestRequesti i后，系统按下述步骤进行检查：后，系统按下述步骤进行检查：(1)(1)如果如果RequestRequesti ijNeedi,jjNeedi,j，转向步骤，转向步骤(2)(2)； 否则认为出错，因为它所需要的资源数已超过它所宣布的否则认为出错，因为它所需要的资源数已超过它所宣布的 最大值。最大值。(2)(2)如果如果RequestRequesti ijAvailablejjAvailablej，转向步骤，转向步骤(3)(3)； 否则，表

34、示尚无足够资源，否则，表示尚无足够资源，P Pi i须等待。须等待。 2 2银行家算法银行家算法(2)(2)(3)(3)系统系统试探试探把把资源分配资源分配给进程给进程P Pi i，并，并修改数据结构中的值修改数据结构中的值：Availablej:= Availablej - RequestAvailablej:= Availablej - Requesti ijj；Allocationi,j:= Allocationi,j + RequestAllocationi,j:= Allocationi,j + Requesti ijj；Needi,j:= Needi,j - RequestNeed

35、i,j:= Needi,j - Requesti ijj；(4)(4)执行安全性算法执行安全性算法，检查此次资源分配后系统是否处于，检查此次资源分配后系统是否处于安全安全状态状态。l若安全，将资源若安全，将资源正式分配正式分配给进程给进程P Pi i；l否则，将本次的否则，将本次的试探分配作废，恢复原来的资源分配状试探分配作废，恢复原来的资源分配状态，让进程态，让进程P Pi i等待等待。3.3.安全性算法安全性算法(1)(1)(1)(1)设置两向量：设置两向量：可供进程继续运行可供进程继续运行所需各类资源数所需各类资源数的的WorkWork 初始时初始时 Work:=AvailableWor

36、k:=Available。表示资源是否足够的表示资源是否足够的FinishFinish， 初始时令初始时令Finishi:=falseFinishi:=false； 资源足够时再令资源足够时再令Finishi:=trueFinishi:=true。Workj=KWorkj=K3.3.安全性算法安全性算法(2)(2)(2)(2)寻找一个能满足下述条件的进程：寻找一个能满足下述条件的进程： Finishi=falseFinishi=false； Needi,jWorkj;Needi,jWorkj;找到执行步骤找到执行步骤(3)(3)，否则执行步骤，否则执行步骤(4)(4)。(3)(3)进程进程P

37、Pi i获得资源，执行完成后释放它的资源，故应执行：获得资源，执行完成后释放它的资源，故应执行：Workj:= Workj+Allocationi,jWorkj:= Workj+Allocationi,j；Finishi:=trueFinishi:=true；go to step 2go to step 2； (4)(4)如果所有进程的如果所有进程的Finishi=trueFinishi=true都满足都满足，则表示系统处于，则表示系统处于安全状态安全状态；否则，系统处于；否则，系统处于不安全状态不安全状态。 实例说明系统所处的安全或不安全状态实例说明系统所处的安全或不安全状态假定系统中有五个

38、进程假定系统中有五个进程P0，P1，P2，P3，P4三类资源三类资源A，B，C 。 lA类资源共有类资源共有10个个lB类资源共有类资源共有5个个lC类资源共有类资源共有7个。个。（1）在时刻）在时刻T0,系统目前资源分配情况如下：系统目前资源分配情况如下：每个进程目前还需资源为每个进程目前还需资源为Need 进程进程 Max Allocation Available A B C A B C A B C P0 7 5 3 0 1 0 3 3 2 P1 3 2 2 2 0 0 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2NeedA B C 7 4 31

39、 2 26 0 00 1 1 4 3 1 进程进程 Work Need Allocation Work=Work+allocation A B C A B C A B C A B C5 3 23 3 21 2 2 2 0 05 3 20 1 1 2 1 17 4 37 4 3P1P3P4P2P04 3 1 0 0 27 4 57 4 56 0 0 3 0 210 4 710 4 74 3 0 0 1 0 10 5 7Need A B C P0 7 4 3 P1 1 2 2 A B C P2 6 0 0P3 0 1 1 A B C P4 4 3 1可以断言可以断言T0时刻，系统处于安全状态时刻，

40、系统处于安全状态l因为序列因为序列P1,P3,P4,P2,P0能满足安全性条件。能满足安全性条件。（2）进程）进程P1申请资源申请资源request1=(1,0,2) ，系统能将资源分，系统能将资源分配给它吗？配给它吗？NeedA B C7 4 36 0 00 1 14 3 1 进程进程 Max Allocation Available A B C A B C A B C P0 7 5 3 0 1 0 P1 3 2 2 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2检查检查: request1(1,0,2) Need1(1,2,2) and reque

41、st1(1,0,2) Available(3,3,2) 结果满足条件，试分配。结果满足条件，试分配。3 0 2 0 2 02 3 0得到新状态：得到新状态： 2 0 03 3 21 2 2判定新状态是否安全判定新状态是否安全?找到一个进程序列找到一个进程序列 可保证进程可保证进程P1运行完毕并归还资源运行完毕并归还资源进程进程 Work Need Allocation work+allocation A B C A B C A B C A B C5 3 22 3 00 2 0 3 0 25 3 20 1 1 2 1 17 4 37 4 3P1P3P4P0P24 3 1 0 0 27 4 57

42、4 57 4 3 0 1 07 5 57 5 56 0 0 3 0 2 10 5 7 A B CP0 7 4 3P1 0 2 0P2 6 0 0P3 0 1 1P4 4 3 1 Need（3）进程）进程P4申请资源申请资源request4=(3,3,0) 检查检查: request4(3,3,0) Need4(4,3,1) and request4 (3,3,0) Available(2,3,0) 让让P4等待等待NeedA B C7 4 30 2 06 0 00 1 14 3 1 进程进程 Max Allocation Available A B C A B C A B C P0 7 5 3

43、 0 1 0 2 3 0 P1 3 2 2 3 0 2 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2（4） P0请求资源请求资源 request0=(0,2,0);检查检查: request0 (0,2,0) Need0(7,4,3) and request0 (0,2,0) Available(2,3,0) 结果满足条件，试分配。结果满足条件，试分配。0 3 0 7 2 32 1 0得到新状态：得到新状态：NeedA B C7 4 30 2 06 0 00 1 14 3 1 进程进程 Max Allocation Available A B C A

44、 B C A B C P0 7 5 3 0 1 0 2 3 0 P1 3 2 2 3 0 2 P2 9 0 2 3 0 2 P3 2 2 2 2 1 1 P4 4 3 3 0 0 2系统已处于不安系统已处于不安全状态了。全状态了。死锁避免死锁避免在使用中有许多限制在使用中有许多限制l必须事先声明每个进程请求的最大资源必须事先声明每个进程请求的最大资源l进程数不能变化进程数不能变化l所讨论的进程必须是无关的所讨论的进程必须是无关的它们的执行顺序必须没有任何同步要求的限制它们的执行顺序必须没有任何同步要求的限制l分配的资源数目必须是固定的分配的资源数目必须是固定的3.8死锁的检测与解除死锁的检测与

45、解除 3.8.13.8.1死锁的检测死锁的检测当系统为进程分配资源时，若未采取任何限制性措施，则当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段系统必须提供检测和解除死锁的手段系统必须做到：系统必须做到： 保存有关资源的请求和分配信息；保存有关资源的请求和分配信息； 提供一种算法，以利用这些信息来检测系统是否已进入死提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。锁状态。 1 1资源分配图资源分配图约定约定PiRj为请求边，表示进程为请求边，表示进程Pi申请资源类申请资源类Rj中的一个资源中的一个资源得不到满足而处于等待得不到满足而处于等待Rj类资源

46、的状态，该有向边从进程开始类资源的状态，该有向边从进程开始指到方框的边缘，表示进程指到方框的边缘，表示进程Pi申请申请Rj类中的一个资源。类中的一个资源。RjPi为分配边，表示为分配边，表示Rj类中的一个资源已被进程类中的一个资源已被进程Pi占用，由占用，由于已把一个具体的资源分给了进程于已把一个具体的资源分给了进程Pi，故该有向边从方框内的，故该有向边从方框内的某个黑圆点出发指向进程。某个黑圆点出发指向进程。 R Rj jP Pi i2 2死锁定理死锁定理可以利用把可以利用把资源分配图资源分配图加以简化的方法，来检测当系统处于加以简化的方法，来检测当系统处于S S状态时是否为死锁状态。状态时

47、是否为死锁状态。l如果能在进程如果能在进程-资源分配图中消去此进程的所有请求边和资源分配图中消去此进程的所有请求边和分配边，成为孤立结点。分配边，成为孤立结点。l如果经一系列简化，使所有进程成为孤立结点，则该图是如果经一系列简化，使所有进程成为孤立结点，则该图是可完全简化的可完全简化的；否则则称该图是不可完全简化的。；否则则称该图是不可完全简化的。S为死锁状态的为死锁状态的充分条件充分条件是：是：l当且仅当当且仅当S状态的资源分配图是不可完全简化的。状态的资源分配图是不可完全简化的。该充分条件被称为该充分条件被称为死锁定理死锁定理。资源分配图的资源分配图的简化简化R1R1R2R2资源分配图的一

48、个例子资源分配图的一个例子 R1 R1 R2 R2P1P1P2P2P3P3R3R33.8.23.8.2死锁的解除死锁的解除 抢占资源。抢占资源。l从其它进程抢占足够数量的资源给死锁进程，以解除从其它进程抢占足够数量的资源给死锁进程，以解除死锁状态。死锁状态。(2) (2) 撤消进程。撤消进程。l最简单的方法是：使全部死锁进程都夭折掉；最简单的方法是：使全部死锁进程都夭折掉；l稍微温和一点的方法是：稍微温和一点的方法是：按照某种顺序逐个地撤消进程，直至有足够的资源按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。可用，使死锁状态消除为止。一、选择题一、选择题(1)产生死锁的基本原因是产生死锁的基本原因是_和和_，产生死锁的，产生死锁的四个必要条件是互斥条件，四个必要条件是互斥条件，_，不可抢占条件和，不可抢占条件和_。A.资源分配不当资源分配不当B.竞争资源竞争资源 C.作业调度不当作业调度不当D.资源的独占性资源的独占性A.进程推进顺序不当进程推进顺序不当B.进程调度不当进程调度不当 C.系统中进程太多系统中进程太多D.CPU运行不快运行不快A.请求和阻塞条件请求和阻塞条件B.请求和释放条件请求和释放条件 C.请求和保持条件请求和保持条件D.释放和阻塞条件释放和阻塞条件A.线性增长条件线性增长条件B.环路等待条件环路等待条件