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

操作系统

OperatingSystemsWINDOWSUNIXLINUXOS2VxWorksMacOS3.4实时调度实现实时调度的基本条件1.必要信息就绪时间、开始截至时间、完成截至时间、处理时间；资源要求；优先级；2.系统处理能力强3.采用抢占式机制---硬实时任务；截止时间要求；4.有快速切换机制---快速响应外部中断；快速任务分派；处理时间:Ci;周期时间:Pi系统处理能力例：A任务周期为10ms，执行5ms；B任务周期为15ms,执行10ms

(5/10)+(10/15)=35/30，系统处理不了A1B1A2B2任务执行t任务到达A1B1A2B2A3051015202530A4B3(A3错过)讨论一个实时系统有四个周期性事件，周期分别为50、100、300和250ms。若假设其处理时间分别需要35、20、10和xms，则该系统可调度允许的x值最大为多少？答：在单处理机情况下：

（35/50+20/100+10/200+x/250）≤1

x≤16.75ms

实时调度算法的分类非抢占式轮转调度(同质任务)；优先调度为时间要求严格的任务分配较高优先级抢占式时钟中断优先；立即抢占优先非抢占式轮转调度算法轮转调度(同质任务)；常用于工业生产的群控系统中非抢占式优先调度算法优先调度为时间要求严格的任务分配较高优先级

基于时钟中断的抢占式优先权调度算法某实时任务到达后，若优先级高于当前正在执行任务的优先级，并不立即抢占当前任务的处理机，而是等到时钟中断到来后调度程序才剥夺当前任务的执行立即抢占的优先权调度算法一旦有外部中断，只要当前任务不在临界区内，便立即剥夺当前任务的执行，交处理机分配给要求中断的紧迫任务常用的几种实时调度算法最早截止时间优先算法非抢占式和抢占式EDF算法用于非抢占调度的调度方式非抢占式调度方式用于非周期实时任务342开始截止时间任务到达123442任务执行t131通常的优先级调度不能适用于实时系统A1B1A2B1A3任务执行t任务到达A1B1A2B2A3最后期限任务A的周期时间为20ms，每个周期的处理时间为10ms；任务B的周期时间为50ms，每个周期的处理时间为25ms固定优先级调度（A有较高优先级）A1A2A30102030405060100708090A4A5A6B3A4B2A5(B1错过)B1通常的优先级调度不能适用于实时系统B1任务执行t任务到达A1B1A2B2A3最后期限任务A的周期时间为20ms，每个周期的处理时间为10ms；任务B的周期时间为50ms，每个周期的处理时间为25ms固定优先级调度（B有较高优先级）A1A2A30102030405060100708090A4A5A6B3A4B2A5(A1错过)B1EDF算法用于抢占调度方式A1B1A2B1A3任务执行t任务到达A1B1A2B2A3最后期限任务A的周期时间为20ms，每个周期的处理时间为10ms；任务B的周期时间为50ms，每个周期的处理时间为25msA1A2A30102030405060100708090A4A5A6B3A4B2A5B2A4B2A5B1最低松弛度优先（LLF）算法松弛度=必须完成时间-本身运行时间-当前时间设有两个周期性实时任务A和B，分别每20ms,50ms执行一次，每次执行10ms,25ms。则其须完成的时间为：A1,A2,…和B1,B2,…，利用LLF算法进行调度的情况t1=0时，A1的松弛度=20-10-0=10ms；

B1的松弛度=50-25-0=25ms;松弛度=必须完成时间-其本身的运行时间-当前时间利用LLF算法进行调度的情况t8B2(10)松弛度=必须完成时间-其本身的运行时间-当前时间t2=10，A1结束，A2未到达

B1运行松弛度=必须完成时间-其本身的运行时间-当前时间t3=30，A2的松弛度=40ms-10ms-30ms=0msB1的松弛度=50ms-5ms-30ms=15msA2抢占运行松弛度=必须完成时间-其本身的运行时间-当前时间t4=40，A3的松弛度=60ms-10ms-40ms=10msB1的松弛度=50ms-5ms-40ms=5msB1运行松弛度=必须完成时间-其本身的运行时间-当前时间t5=45，A3的松弛度=60ms-10ms-45ms=5msB2未到达A3运行松弛度=必须完成时间-其本身的运行时间-当前时间t6=55，A3结束，A4未到达

B2运行松弛度=必须完成时间-其本身的运行时间-当前时间t7=70，A4的松弛度=80ms-10ms-70ms=0msB2的松弛度=100ms-10ms-70ms=10msA4运行松弛度=必须完成时间-其本身的运行时间-当前时间t8=80，A5的松弛度=100ms-10ms-80ms=10msB2的松弛度=100ms-10ms-80ms=10msB2运行（同样松弛度应先来先服务）A1B1A2B2A3A4A5任务到达最后期限A1A2A3A4B120304050607010803.5产生死锁的原因和必要条件死锁在多进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵局状态时，若无外力作用，它们都将无法再向前推进。Honk!产生死锁的原因竞争资源当系统中供多个进程共享的资源，其数目不足以满足诸进程的需要时，会引起诸进程对资源的竞争而产生死锁。

进程间推进顺序非法。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。

产生死锁的原因3个进程共享4个同种类型的资源，每个进程最大需要2个资源，请问该系统是否会因为竞争资源而死锁？

R系统有同类资源m个，被n个进程共享，当m>n和m≤n时，每个进程最多可以请求多少个这类资源时，系统一定不会发生死锁？当m≤n时:每个进程最多申请1个这类资源时，系统一定不会发生死锁当m>n时:假设每个进程最多申请x个这类资源若每个进程申请x-1个这类资源后，系统还剩下一个资源，就能保证某一个进程能分配到全部x个资源，并能运行到底，最终释放这x个资源。即：

n*（x

-1）<

mx<(m/n)+1竞争资源引起进程死锁系统中的资源分成两类可抢占性资源。如：CPU和主存对于这类资源是不会引起死锁的不可抢占性资源。如：磁带机、打印机在系统中所配置的不可抢占性资源，由于它们的数量不能满足诸进程运行的需要，会因争夺这些资源而陷入僵局。竞争不可抢占性资源R1R2m3竞争可消耗资源可消耗资源（临时性资源）由一个进程产生，被另一进程使用一短暂时间后便无用的资源，故也称之为消耗性资源P1：…send(p2,m1)；Receive(p3,m3)；…P2：…send(p3,m2)；Receive(p1,m1)；…P3：…send(p1,m3)；Receive(p2,m2)；…m2m1竞争可消耗资源引起进程死锁P1：…

Receive(p3,m3)；send(p2,m1)…P2：…Receive(p1,m1)；send(p3,m2)…P3：…

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

进程推进顺序进程Ｐ1进程P2请求读卡机请求读卡机请求打印机请求打印机释放读卡机释放读卡机释放打印机释放打印机

死锁的基本概念这两个进程在并发执行过程中，可能会发生死锁。大家可以思考一下，如何修改，进程才不会发生死锁？死锁的基本概念关于死锁的一些结论参与死锁的进程最少是两个参与死锁的进程至少有两个已经占有资源参与死锁的所有进程都在等待资源参与死锁的进程是当前系统中所有进程的子集注：如果死锁发生，会浪费大量系统资源，甚至导致系统崩溃。3.5.3产生死锁的必要条件互斥条件：进程互斥使用资源请求和保持条件：部分分配条件申请新资源时不释放已占有资源不可抢占条件：一个进程不能抢夺其他进程占有的资源环路条件：存在一组进程循环等待资源S1S3S2处理死锁的方法预防死锁。破坏产生死锁的四个必要条件中的一个或几个条件

避免死锁。在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。检测死锁。通过系统所设置的检测机构，及时地检测出死锁的发生；采取适当措施，从系统中将已发生的死锁清除掉。解除死锁。这是与检测死锁相配套的一种措施3.6预防死锁一种较简单和直观的事先预防的方法。设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁：互斥条件请求和保持条件不可抢占条件环路条件1.破坏“请求和保持”条件破坏“请求和保持”条件一个进程必须在执行前就申请它所要的全部资源，直到它所要的资源都得到满足后才开始执行。优点简单、易于实现且很安全。缺点资源被严重浪费，严重地恶化了系统资源的利用率；使进程延迟运行，仅当进程在获得了其所需的全部资源后，才能开始运行。2.破坏“不可抢占”条件破坏“不可抢占”条件当进程有新的资源请求时，如果得不到满足，要先释放原先占有的资源，待以后重新申请。等价于“被抢占”。该方法实现起来比较复杂，要付出很大的代价。反复地申请和释放资源进程的执行被无限地推迟只适用于对主存资源和处理器资源的分配3.破坏“环路等待”条件破坏“环路等待”条件把系统资源按类型排序，进程要按照资源的序号递增的次序提出资源申请。优点资源利用率和系统吞吐量都有较明显的改善。存在下述严重问题：限制了新类型设备的增加。造成对资源的浪费。必然会限制用户简单、自主地编程。

讨论在哲学家就餐问题中，奇数号先取左手边的筷子，偶数号先取右手边的筷子。请说明为何不会产生死锁。3.7避免死锁1.安全状态指系统能按某种进程顺序(P1，P2，…，Pn)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。当系统进入不安全状态后，便有可能进而进入死锁状态。避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态2．安全状态之例假定系统中有三个进程P1、P2和P3，共有12台磁带机。T0时刻是安全的？+2-2=12．安全状态之例假定系统中有三个进程P1、P2和P3，共有12台磁带机。+5-5=02．安全状态之例假定系统中有三个进程P1、P2和P3，共有12台磁带机。安全序列：P2、P1、P3T0时刻是安全的。+7-7=33．由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。+1-1=23．由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。+2-2=03．由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。3．由安全状态向不安全状态的转换如果不按照安全序列分配资源，则系统可能会由安全状态进入不安全状态。从给P3分配了第3台磁带机开始，系统便又进入了不安全状态。3.7.2利用银行家算法避免死锁1．银行家算法中的数据结构(1)可利用资源向量Available每类资源未分配数量向量含有m个元素的数组如果Available[j]=K，则表示系统中现有Rj类资源K个。银行家算法中的数据结构(2)最大需求矩阵Max。一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。Max=M11M12M1mM21M21M21Mn1Mn1Mnm………银行家算法中的数据结构(3)分配矩阵Allocation。也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。Allocation=A11A12A1mA21A21A21An1An1Anm………银行家算法中的数据结构(4)需求矩阵Need。一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。上述三个矩阵间存在下述关系：Need[i,j]=Max[i,j]-Allocation[i,j]2．银行家算法(1)设Requesti[j]=K，表示Pi需要K个Rj类资源。Pi发出资源请求Requesti后，系统按下述步骤进行检查：(1)如果Requesti[j]≤Need[i,j]，转向步骤(2)；

否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。(2)如果Requesti[j]≤Available[j]，转向步骤(3)；

否则，表示尚无足够资源，Pi须等待。2．银行家算法(2)(3)系统试探把资源分配给进程Pi，并修改数据结构中的值：Available[j]:=Available[j]-Requesti[j]；Allocation[i,j]:=Allocation[i,j]+Requesti[j]；Need[i,j]:=Need[i,j]-Requesti[j]；(4)执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，将资源正式分配给进程Pi；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。3.安全性算法(1)(1)设置两向量：①可供进程继续运行所需各类资源数的Work

初始时Work:=Available。②表示资源是否足够的Finish，

初始时令Finish[i]:=false；

资源足够时再令Finish[i]:=true。Work[j]=K3.安全性算法(2)(2)寻找一个能满足下述条件的进程：①Finish[i]=false；②Need[i,j]≤Work[j];找到执行步骤(3)，否则执行步骤(4)。(3)进程Pi获得资源，执行完成后释放它的资源，故应执行：Work[j]:=Work[j]+Allocation[i,j]；Finish[i]:=true；gotostep2；(4)如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。实例说明系统所处的安全或不安全状态假定系统中有五个进程{P0，P1，P2，P3，P4}三类资源{A，B，C}。

A类资源共有10个B类资源共有5个C类资源共有7个。（1）在时刻T0,系统目前资源分配情况如下：每个进程目前还需资源为Need进程Max

AllocationAvailableABCABCABCP0753010

332P1322200P2902302P3222211P4433002NeedABC743122600011431

进程WorkNeed

AllocationWork=Work+allocationABCABCABCABC532332122200532011211743743P1P3P4P2P0431002745745600302104710474300101057Need

ABCP0743P1122ABCP2600P3011ABCP4431可以断言T0时刻，系统处于安全状态因为序列{P1,P3,P4,P2,P0}能满足安全性条件。（2）进程P1申请资源request1=(1,0,2)，系统能将资源分配给它吗？NeedABC743600011431进程Max

AllocationAvailableABCABCABCP0753010P1322

P2902302P3222211P4433002检查:request1(1,0,2)≤Need1(1,2,2)andrequest1(1,0,2)≤Available(3,3,2)

结果满足条件，试分配。302020230得到新状态：200332122判定新状态是否安全?找到一个进程序列

可保证进程P1运行完毕并归还资源进程WorkNeed

Allocationwork+allocationABCABCABCABC532230020302532011211743743P1P3P4P0P24310027457457430107557556003021057ABCP0743P1020P2600P3011P4431Need（3）进程P4申请资源request4=(3,3,0)检查:request4(3,3,0)≤Need4(4,3,1)andrequest4(3,3,0)≥Available(2,3,0)让P4等待NeedABC743020600011431进程Max

AllocationAvailableABCABCABCP0753010230P1322302P2902302P3222211P4433002（4）P0请求资源request0=(0,2,0);检查:request0(0,2,0)≤Need0(7,4,3)andrequest0(0,2,0)≤Available(2,3,0)

结果满足条件，试分配。030723210得到新状态：NeedABC743020600011431进程Max

AllocationAvailableABCABCABCP0753010230

P1322302P2902302P3222211P4433002系统已处于不安全状态了。死锁避免在使用中有许多限制必须事先声明每个进程请求的最大资源进程数不能变化所讨论的进程必须是无关的它们的执行顺序必须没有任何同步要求的限制分配的资源数目必须是固定的3.8死锁的检测与解除

3.8.1死锁的检测当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段系统必须做到：保存有关资源的请求和分配信息；提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。

1．资源分配图约定Pi→Rj为请求边，表示进程Pi申请资源类Rj中的一个资源得不到满足而处于等待Rj类资源的状态，该有向边从进程开始指到方框的边缘，表示进程Pi申请Rj类中的一个资源。Rj→Pi为分配边，表示Rj类中的一个资源已被进程Pi占用，由于已把一个具体的资源分给了进程Pi，故该有向边从方框内的某个黑圆点出发指向进程。RjPi2．死锁定理可以利用把资源分配图加以简化的方法，来检测当系统处于S状态时是否为死锁状态。如果能在进程-资源分配图中消去此进程的所有请求边和分配边，成为孤立结点。如果经一系列简化，使所有进程成为孤立结点，则该图是可完全简化的；否则则称该图是不可完全简化的。S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。资源分配图的简化R1R2资源分配图的一个例子R1R2P1P2P3R33.8.2死锁的解除抢占资源。从其它进程抢占足够数量的资源给死锁进程，以解除死锁状态。(2)撤消进程。最简单的方法是：使全部死锁进程都夭折掉；稍微温和一点的方法是：按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。一、选择题(1)产生死锁的基本原因是_______和_______，产生死锁的四个必要条件是互斥条件，_______，不可抢占条件和_______。①A.资源分配不当 B.竞争资源

C.作业调度不当 D.资源的独占性②A.进程推进顺序不当 B.进程调度不当

C.系统中进程太多 D.CPU运行不快③A.请求和阻塞条件 B.请求和释放条件

C.请求和保持条件