第3章 处理机调度与死锁new.pptVIP

3.3.2 实时调度算法的分类 1.非抢占式调度算法 (1)非抢占式轮转调度算法。响应时间：几秒～几十秒。用于分时系统，实时信息处理系统。 (2)非抢占优先权调度算法。响应时间：几秒～几百毫秒。用于多道批处理系统，要求不太严格的实时控制系统中。 练习题 1、在面向用户的调度准则中，(A)是选择实时调度算法的重要准则，(B)是选择分时系统中进程调度算法的重要准则，(C)是批处理系统中选择作业调度算法的重要准则，而(D)准则是为了照顾紧急作业用户的要求而设置的。 A,B,C,D:(1)响应时间快(2)平均周转时间短(3)截止时间的保证(4)优先权高的作业能获得优先服务(5)服务费低 2、我们如果为每一个作业只建立一个进程，则为了照顾短作业用户，应采用(A);为照顾紧急作业的用户，应采用(B);为能实现人机交互作用应采用(C);为了兼顾短作业和长时间等待的作业，应采用(D);为了使短作业、长作业及交互作业用户都比较满意，应采用(E) 。 A,B,C,D,E,F(1)FCFS调度算法(2)短作业优先(3)时间片轮转法(4)多级反馈队列调度算法(5)基于优先权的剥夺调度算法(6)高响应比优先 3、下述解决死锁的方法中，属于死锁预防策略的是(A),属于死锁避免策略的是(B). A,B:(1)银行家算法(2)资源有序分配法(3)资源分配图化简法(4)撤消进程法 4、死锁的预防是通过破坏产生死锁的四个必要条件来实现的。下列方法中，(A)破坏了“请求与保持”条件，(B)破坏了“循环等待”条件。 A,B:(1)银行家算法(2)一次性分配策略(3)资源有序分配策略(4)SPOOLing技术 19.在银行家算法的例子中，如果P0发出的请求向量由Request0(0,2,0)改为Request0(0,1,0)，问系统可否将资源分配给它？ 可以。(1)Request0(0,1,0)=Need0(7,4,3) (2) Request0(0,1,0)=Available(2,3,0); (3)修改资源，进行安全性检查， 3.5.2 产生死锁的必要条件 互斥条件 :进程所访问的是临界资源。 (2)请求和保持条件 :进程在请求新资源的同时，保持对某些资源的占有。 (3)不剥夺条件 :进程已获得的资源，只能在使用完时自行释放。 (4)环路等待条件 :存在一个至少包含两个进程的循环等待链，{P0,P1,P2,…Pn},其中P0等待P1占用的资源，P1等待P2,…Pn等待P0。 如果进程间发生死锁，必然会出现以下四种情况： 3.5.3 处理死锁的基本方法 预防死锁:通过破坏产生死锁的某个必要条件来防止死锁的发生。 优点：实现简单，应用广泛。 缺点：限制条件严格，降低了资源利用率和系统吞吐量。 (2) 避免死锁:在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。 优点：限制条件不多，有较高的资源利用率和系统吞吐量。 缺点：实现有一定难度。 (3) 检测死锁:此法允许系统在运行过程中发生死锁，但可通过系统设置的检测机构，及时检测出死锁的发生。 (4) 解除死锁:将进程从死锁状态下解脱出来。 优点：较高的资源利用率和系统吞吐量。 缺点：不易实现。 3.6预防死锁的方法 3.6.1预防死锁 摒弃“请求和保持”条件:所有进程都必须一次性申请其在运行过程中所需 的全部资源。 2. 摒弃“不剥夺”条件:一个已经保持了某些资源的进程，在提出新的资源请求而不能立即得到满足时，必须释放它已获得的所有资源。 3. 摒弃“环路等待”条件 :将系统中的资源按类型赋予不同的序号，所有的进程必须严格按照资源序号递增的顺序申请资源。 使四个必要条件中的第2、3、4条件之一不能成立。 条件1是由设备的固有特性决定的，不能改变，要加以保证。 3.6.2 系统安全状态 1. 安全状态 只要能使系统始终处于安全状态，便可避免发生死锁。  所谓安全状态，是指系统能按某种进程顺序(P1, P2, …，Pn)(称〈P1, P2, …, Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。 2. 安全状态之例 假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1 P2和P3分别要求10台、4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，剩3台： 3 5 2 2 10 4 9 P1 P2 P3 可 用 已 分 配 最 大 需 求 进 程 在T0时刻存在安全状态(序列)：P2, P1, P3 3、由安全状态向不安全状态的转换：