《操作系统-处理机调度和死锁os3(1)》由会员分享，可在线阅读，更多相关《操作系统-处理机调度和死锁os3(1)（53页珍藏版）》请在金锄头文库上搜索。
1、第三章 处理机调度和死锁,Review,实时调度算法 EDF LLF 截止时间（完成截止时间和开始截止时间） 松弛度的定义：松弛度=必须完成时间-运行时间-当前时刻,竞争资源,进程推进顺序不当,产生死锁的原因,竞争非剥夺性资源,竞争临时资源,本章主要内容,3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除,互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只供一个进程占用。如果此时其他进程请求该资源，请求者只能等待（资源独占） 请求和保持：指进程已经保
2、持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占用，此时请求进程阻塞，但又对自己已获得的其它资源保持不放（部分分配，占有申请）,产生死锁的必要条件,死锁的发生具备下列四个必要条件：,必要条件:如果能从命题B推出命题A,条件A是条件B的必要条件。 如果无A必无B，有A可能有B也可能没有B，则A是B的必要条件。,产生死锁的必要条件,不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放； 环路等待条件：指在发生死锁时，必然存在一个进程资源的环形链，即进程集合P0，P1，P2，,Pn中的P0正等待一个P1占用的资源，P1正等待一个P2占用的资源，Pn正
3、等待已被P0占用的资源。, , ,处理死锁的基本方法,不考虑此问题：（鸵鸟政策） 预防死锁 该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。由于所施加的限制条件往往太严格，可能会导致系统资源利用率和系统吞吐量的降低。 避免死锁发生 也是属于事先预防的策略，但它并不须事先采取各种限制措施去破坏产生死锁的四个必要条件。而是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁。常用的算法是银行家算法。 检测死锁 不须事先采取限制性措施，也不必检查系统是否进入不安全区，而是允许系统在运行过程中发生死锁。但可通过系统所设置的检测机构，及时
4、地检测出死锁的发生，并精确地确定与死锁有关的进程和资源；然后采用适当的措施从系统中将已发生的死锁清除掉。 解除死锁 与检测死锁相配套的一种措施。检测到系统中已发生死锁时，将进程从死锁状态中解脱出来。常用的实施方法是撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。,本章主要内容,3.1 处理机调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除,1、预防死锁,定义： 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏
5、产生死锁的必要条件之一（互斥条件是不能破坏的）,1）摒弃“请求和保持”条件-资源的静态分配 要求每个进程在运行前必须一次性申请它所要求的所有资源，当且仅当该进程所要资源均可满足时才给予一次性分配,缺点：资源严重浪费。进程申请到资源后，整个运行期间一直占用； 进程延迟运行，只有当进程获得了其所需的所有资源后，才能开始运行，可能因某些资源长期被其他进程占用而致使等待进程迟迟不能运行。,优点：简单、易于实现且很安全。,2）摒弃“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。,代价： 以前的工作失
6、效 反复申请释放使进程无限期推迟 系统开销大,缺点：为系统中各类资源所分配（确定）的序号必须相对稳定，这就限制了新设备的添加； 尽管在为资源的类型分配序号时，已经考虑到大多数作业在实际使用这些资源时的顺序，但也经常发生这种情况：即作业（进程）使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。如：某进程先用磁带机，再用打印机。但按系统规定，该进程应先申请打印机而后申请磁带机，致使先获得的打印机被长时间闲置。 为方便用户，系统对用户在编程时所施加的限制条件应尽量少。然而这种按规定次序申请的方法，必然会限制用户简单、自主地编程。,3）摒弃“环路等待”条件 采用资源有序分配法： 把系统中所有资
7、源顺序编号：r1，r2，rn 各进程按资源编号递增次序申请资源,系统安全状态,在预防死锁的方法中，都施加了较强的限制条件；在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。该方法中把系统的状态分为安全状态和不安全状态，只要使系统始终都处于安全状态，便可避免发生死锁。,P1,安全吗？,P1,安全吗？,安全,不安全,系统安全状态,在避免死锁的方法中，允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程，否则，令进程等待。 所谓安全状态，是指系统能按某种进程顺序（P1,P2,Pn），来为每个进程
8、Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。,避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。,安全状态之例,Eg: 系统中有进程P1、P2、P3和12台磁带驱动器，各进程对此资源的需求和分配情况如下表所示，此时按照安全序列分配资源可以保证各进程都顺利完成,安全状态向不安全状态的转换,分配资源时若不按照安全序列的顺序，可能会导致OS由安全状态进入不安全状态 eg：在上例中，为进程P3分配一台磁带机，系统进入不安全状态，此时再也找不到一个安全序列,银行家算法,假定某银行家有一笔资金
9、可供一批顾客借用，并假定： 每个顾客预知他的最大借款总额，且不超过银行家拥有的可用资金总和。 每当顾客提出借款请求，银行家可立即给予，或让顾客等一段时间。 只有当顾客达到他的预定最大借款额时，他才在有限时间依次归还。,死锁的产生：当各顾客借款总额之和大于银行可借用资金总和，而每顾客都未达到他的预定最大借款额。 安全状态：如果在某时刻，银行有可能使它当时的所有的顾客在以后有限时间内完成全部成交，则此刻的状态是安全。 不安全状态：永远不具有成交的可能，则为不安全。,银行家算法概念（P109P111） 把这种算法比作银行家，银行家占有有限的资金（资源），把进程比作借款人，如果借出去的款能收回则出借（
10、分配资源），否则拒绝贷款。 算法原理：每次分配检查系统是否存在一个进程安全序列，存在一个安全序列则分配，反之，拒绝分配，让申请的进程阻塞。,如果系统无法找到这样的一个安全序列，则称系统处于不安全状态。,例：有三个进程共享某类资源，最大需求为 （10，4，9），资源总数为：12, P1，P2，P3 P1，P3，P2 P2，P1，P3 P2，P3，P1 P3，P1，P2 P3，P2，P1 ,对安全序列的物理含义的说明:,(0,0,0),(0,0,7),(5,0,7),(5,2,7),(10,4,9),尚需,P3,P1,P2,安全,完成,3(12),(0,0,9),(0,0,7),t4,0(10),
11、(10,0,2),(5,0,0),t3,1(5),(5,4,2),(0,2,0),t2,3,(5,2,2),(5,2,2),t1,12,（0,0,0),（0,0,0),t0,可用数,P1,P2,P3分配,P1,P2,P3申请,各时刻系统状态都是安全的，因为每个时刻都存在一个进程安全序列，保证各进程顺利完成。,P1,P2,P3最大需求为（10，4，9）, P1，P2，P3 P1，P3，P2 P2，P1，P3 P2，P3，P1 P3，P1，P2 P3，P2，P1 ,如果进程P3再请求并分配一个资源:,不存在安全序列,(5,0,6),(5,0,6),(5,0,6),(5,2,6),(5,2,7),尚
12、需,P3阻塞,P1阻塞,P2,不安全,安全,完成,4,(5,0,3),(0,0,6),t5,4,(5,0,3),(5,0,0),t4,0(4),(5,4,3),(0,2,0),t3,2,(5,2,3),(0,0,1),t2,3,(5,2,2),(5,2,2),t1,可用数,P1,P2,P3分配,P1,P2,P3申请,不安全状态，最终推进到死锁。银行家算法就是要排除这种不安全状态的存在,不安全状态，最终推进到死锁。最大需求仍然为（10，4，9）,P3阻塞,P1阻塞,P2完成,P1完成,P3完成,(5),(10）,(12),最大需求仍然为（10，4，9）,银行家算法,n：系统中进程的总数 ； m：
13、资源种类 可用资源向量 Available : ARRAY1m of integer; 最大需求矩阵 Max: ARRAY1n,1m of integer;,已分配矩阵 Allocation: ARRAY1n,1m of integer; 需求矩阵（各进程的需求下限） Need: ARRAY1n,1m of integer; 请求向量 Request: ARRAY1n,1m of integer;,银行家算法符号简记：,Available 、Maxi Allocationi Needi 、Requesti,当进程Pi提出资源申请时，系统执行下列步骤： （1）若RequestiNeedi,转（2
14、）； 否则错误返回 （2）若RequestiAvailable, 转（3）；否则进程等待,(3）假设系统分配了资源，则有： Available:=Available-Requesti; Allocationi:= Allocationi+Requesti; Needi:=Needi-Requesti 若系统新状态是安全的，则分配完成 若系统新状态是不安全的，则恢复原状态，进程等待,银行家算法安全性检查,定义数据结构： 工作向量 Work: ARRAY1m of integer; 结束向量 Finish: ARRAY1n of Boolean;,安全性检查的步骤： (1) Work:=Avail
15、able; Finish:=false; (2) 寻找满足条件的i： Finishi=false; NeediWork; 如果不存在，则转(4) (3) Work:=Work+Allocationi; Finishi:=true; 转(2) (4) 若对所有i, Finishi=true,则系统处于安全状态，否则处于不安全状态,银行家算法之例（P110）,进程P0,1,2,3,4 共享A、B、C三类资源 A，B，C=10，5，7 T0时刻，资源的分配情况如下图所示。 （1）该状态是否安全？若安全，请找出安全序列。 （2）在此基础上，P1 申请（1，0，2）能否分配？为什么？ （3）P4 申请（3，3，0）能否分配？为什么？ （4）P0 申请（0，2，0）能否分配？为什么？,True,10 5 7,3 0 2,6 0 0,7 5 5,P2,True,7 5 5,0 1 0,7 4 3,7 4 5,P0,True,7 4 5,0 0 2,4 3 1,7 4 3,P4,True,7 4 3,2 1 1,0 1 1,5 3 2,P3,False,3 0 2,6 0 0,5 3 2,P2,True,5 3 2,2 0 0,1 2 2,3 3 2,P1,False,0 1 0,7 4 3,3 3 2,P0,finishi,Work+ allo
