3处理机调度与死锁-2

2009年4月21日星期二1操作系统（Linux）第三章处理机调度与死锁2第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除33.4实时调度™引述ƒ实时任务•任务的结束时间有严格约束(Deadline)，即任务执行必须在Deadline之前完成。•具有紧迫性。ƒ前述算法不能很好地满足实时系统对调度的特殊要求，所以引入实时调度。43.4实时调度™3.4.1实时调度的基本条件ƒ1、提供必要的信息•就绪时间、开始/完成截止时间、处理时间、资源要求、优先级。ƒ2、系统处理能力强•提高系统处理能力途径–单处理机，增强处理能力–多处理机ƒ3、采用抢占式调度机制•高优先权任务可以抢占低优先权，使用处理机。ƒ4、具有快速切换机制•对外部中断的快速响应能力•快速的任务分派能力53.4实时调度™3.4.2实时操作系统RTOSƒReal-TimeOperatingSystemƒ对外部输入的信息，实时操作系统能够在规定的时间内处理完毕并做出反应ƒ正确性：不仅依靠计算逻辑的正确，而且要求在规定的时间内得到该结果ƒ通常给定一个开始时间或者结束时间的最后期限ƒ多用于工业、军事等控制领域或实时信息处理方面63.4实时调度™3.4.2实时操作系统RTOSƒ嵌入式操作系统的实时性都比较强，可归为RTOS•VxWorks操作系统–美国WindRiver公司于1983年设计开发，实时性强，内核可极微（据说最小可8K），可靠性较高等，主要在通信设备等实时性要求较高的系统中。•uCOS–uC/OS是一种免费公开源代码、结构小巧、具有可剥夺实时内核的实时操作系统。•嵌入式Linux操作系统–Linux本身嵌入式操作系统，嵌入式领域使用的是专为嵌入式设计的已被裁减过的Linux系统，如uClinux•WindowsCE–主要用于PDA、手机、显示仪表等界面要求较高或者要求快速开发的场合•其他RTOS：Symbian、PalmOS等7第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除83.5产生死锁的原因和必要条件™3.5.1死锁的定义ƒ所谓死锁，是指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法向前推进。93.5产生死锁的原因和必要条件™3.5.2产生死锁的原因ƒ1、竞争资源ƒ2、进程间推进顺序非法103.5产生死锁的原因和必要条件™3.5.2产生死锁的原因ƒ1、竞争资源•资源分为可剥夺资源和非剥夺资源。•竞争非剥夺资源，且数量不能满足进程运行需要，就会陷入僵局。•如：200K的可用内存，P1，P2都进行到第二步时，死锁发生。P1......Request80Kbytes;Request60Kbytes;P2......Request70Kbytes;Request80Kbytes;113.5产生死锁的原因和必要条件™3.5.2产生死锁的原因ƒ2、进程间推进顺序非法进程P进程QGetAGetB…………GetBGetA…………ReleaseAReleaseB…………ReleaseBReleaseA123.5产生死锁的原因和必要条件™3.5.3产生死锁的必要条件ƒ（1）互斥条件•一段时间内，某资源只能由一个进程占用。ƒ（2）请求和保持条件•保持已经获得资源不放，继续提出新的资源需求。ƒ（3）不剥夺条件•进程已获得资源在未使用完前不能被剥夺。ƒ（4）环路等待条件•存在一个进程对资源需求的环形链。133.5产生死锁的原因和必要条件™3.5.4处理死锁的基本方法ƒ（1）预防死锁•提前采取一些限制措施，预防死锁条件的成立。ƒ（2）避免死锁•在每次分配资源前进行检测，如果检测到本次资源分配会导致死锁就取消分配，避免死锁的发生。ƒ（3）检测死锁和解除死锁•允许发生死锁，通过检测机制及时检测死锁有关的进程和资源，采取措施解除死锁。14第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除153.6预防死锁的方法™3.6.1预防死锁ƒ使四个必要条件中的2、3、4之一不能成立，1应保证。•（1）摒弃“请求和保持”条件–进程开始运行前一次性申请其在运行过程中所需的全部资源–资源浪费，进程延迟•（2）摒弃“不剥夺”条件–当进程已经占有某些资源，申请新资源不能立即满足时，必须释放所有已经保持的资源，以后需要再重新申请。–资源前端工作失效，进程延迟，增加系统开销，降低吞吐量•（3）摒弃“环路等待”条件–对资源按类型线性排队编号，进程对资源的请求必须按照资源序号递增提出。–限制新类型设备增加，作业需求顺序与资源编号顺序不同。限制用户简单自主编程。163.6预防死锁的方法™3.6.2系统安全状态ƒ所谓安全状态，系统能按某种进程顺序(P1,P2,…，Pn)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。ƒ称(P1,P2,…,Pn)序列为安全序列173.6预防死锁的方法™3.6.2系统安全状态ƒ系统有某个资源R共10个。ABC三个进程在运行过程中分别需要R的数量是6，5，4个。使用顺序如下：ƒ若已完成第一步分配，那么当前状态安全吗？ƒ如果能找到一个安全序列，系统就是安全的申请使用4个申请使用2个进程A结束申请使用3个申请使用2个进程B结束申请使用1个申请使用1个申请使用2个进程c结束183.6预防死锁的方法™3.6.2系统安全状态ƒ安全序列：各个并发进程的一个执行顺序，按照该顺序，所有的进程都能获得所需要的全部资源并能执行完。ƒ如上例，可以找到的安全序列：A-B-C或B-A-Cƒ不安全状态：如果系统无法找到这样一个安全序列，则称系统处于不安全状态。ƒPPT42中的状态就是不安全的193.6预防死锁的方法™3.6.3利用银行家算法避免死锁ƒ在系统运行过程中，对进程发出的每一个能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源。•若分配后系统可能发生死锁，则不予分配•若分配后系统处于安全状态，则予以分配ƒ避免死锁实质：•在进程资源分配时，如何使系统不进入不安全状态。203.6预防死锁的方法™3.6.3利用银行家算法避免死锁ƒ避免死锁策略•1.当前状态下，某进程申请资源；•2.系统假设将资源分给该进程，满足它的需求；•3.检查分配后的系统状态是否是安全的，如果是安全，就确认本次分配；如果系统是不安全的，就取消本次分配并阻塞该进程。（第三步又称安全算法）ƒ避免死锁策略也称作银行家算法。213.6预防死锁的方法™3.6.3利用银行家算法避免死锁ƒ银行家算法中的数据结构•系统中有n个进程和m种不同类型的资源•Resource=（R1，R2，…，Rm）资源总数•Available=（V1，V2，…，Vm）可用资源数•Claim：各进程对各类资源的需求•Allocation：各进程已经获得的各类资源数•Need：各进程还需要的各类资源数223.6预防死锁的方法™3.6.3利用银行家算法避免死锁ƒ银行家算法举例（资源总数10、5、7）：ƒ（1）当前时刻安全性。ƒ（2）如果P1请求（1,0,2），是否分配？资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2902302600P3222211011P4433002431233.6预防死锁的方法™3.6.3利用银行家算法避免死锁ƒ银行家算法举例（资源总数10、5、7）：ƒ（1）安全。可以找到安全序列P1,P3,P4,P2,P0资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2902302600P3222211011P4433002431243.6预防死锁的方法™3.6.3利用银行家算法避免死锁ƒ银行家算法举例（资源总数10、5、7）：ƒ（2）P1请求(1,0,2)，假设分配，则状态变成新状态（见下页）资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2902302600P3222211011P4433002431253.6预防死锁的方法™3.6.3利用银行家算法避免死锁ƒ银行家算法举例（资源总数10、5、7）：ƒ新状态安全吗？安全则同意刚才的假设，否则不同意。ƒ可以找到一个安全序列p1,p3,p4,p2,p0，所以安全，可以将P1申请的资源分配给它。资源情况进程MaxABCAllocationABCNeedABCAvailableABCP0753010743332P1322200122P2902302600P3222211011P443300243130202023026第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度准则3.3调度算法3.4实时调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测与解除273.7死锁的检测与解除™3.7.1死锁的检测ƒ1、系统必须提供检测和解除死锁的手段•保存有关资源的请求和分配信息——资源分配图•提供算法检测系统是否进入死锁状态——死锁定理283.7死锁的检测与解除™3.7.1死锁的检测ƒ2、资源分配图•（1）用圆圈表示进程•（2）方框表示一类资源，•方框中的点表示一类资•源中的一个资源。•（3）请求边从进程开始•（4）分配边从方框中一点开始P1P2r1r2293.7死锁的检测与解除™3.7.1死锁的检测ƒ3、死锁定理•（1）简化资源分配图–找出一个既不阻塞又非独立的进程结点Pi，消去所有请求边和分配边，使之成为独立的结点。–不断进行上步操作，若能消去图中所有的边，则称该图是可完全简化的，否则是不可完全简化的。303.7死锁的检测与解除™3.7.1死锁的检测ƒ3、死锁定理•（2）死锁定理–S状态死锁的充分条件：当且仅当S状态的资源分配图是不可完全简化的。313.7死锁的检测与解除™3.7.2死锁的解除ƒ1、剥夺资源ƒ2、撤消进程•撤消全部死锁进程•按照某种顺序逐个撤消，直至有足够可用资源•可采取某种策略使得–所需撤消进程数目最小–撤消进程所付出代价最小32小结™三级调度，选择调度方式的准则™调度算法ƒ先来先服务、短作业（进程）优先、高响应比优先、时间片轮转法™实时调度（了解）™产生死锁的原因、必要条件™处理死锁的基本方法ƒ预防、避免（银行家算法）、检测、解除