《操作系统第三章ppt课件.ppt》由会员分享，可在线阅读，更多相关《操作系统第三章ppt课件.ppt（81页珍藏版）》请在三一办公上搜索。
1、第三章 处理机调度与死锁,第一节处理机调度的层次和调度算法的目标第二节作业与作业调度第三节 进程调度第四节 实时调度第五节死锁概述第六节 预防死锁第七节 避免死锁第八节 死锁的检测与解除,第一节处理机调度的层次和调度算法的目标,在多道批处理系统中，存在着多个进程的数量已超过了处理机的数量。这就要求系统能够实现动态地将处理机分配给一个就绪进程。这个分配任务便是交由处理机调度程序完成的。这个调度程序的调度性能直接决定着系统的吞吐量高不高、资源利用率大不大，作业周转的时间以及系统响应的及时性等等，故处理机调度便成为OS中至关重要的部分。,第一节处理机调度的层次和调度算法的目标,处理机调度：根据处理机
2、分配策略所规定的处理机分配算法，对处理机资源进行分配。 由于在多道环境下，一个作业从提交到获得处理机执行，到作业运行完成，在这个过程中，可能需要经历多级处理机调度处理机的层次：高级调度：称长程调度或作业调度调度对象：为作业。调度功能：实现将外存后备队列中的哪几个作业调入到内存中，为它们创建进程，分配系统资源，并插入就绪队列中。（应用于多道批处理系统）低级调度：称进程调度或短程调度调度对象：进程。调度功能：决定在内存中的就绪队列中，哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。（应用于多道批处理系统、分时系统、实时系统）,第一节处理机调度的层次和调度算法的目标,中级调度：称内存调
3、度调度对象：为进程。调度功能：实现提高内存利用率和系统吞吐量，将暂时不能运行的进程调至外存等待，进程状态转为就绪驻外存状态或挂起状态。当它具备运行条件且内存具有空间则重新调入内存，变为就绪状态。（应用于存储器管理）三种调度的比较与分析运行频率：进程调度中级调度作业调度运行时间：作业调度（几分钟）中级调度进程调度 （10100ms）,调度队列模型,第一节处理机调度算法的目标,不同类型的的操作系统具有不同的调度方式和算法，这些算法具有一些共同的目标，当然根据各自OS系统的特征，也形成了有差异的目标：处理机调度算法的共同目标批处理系统的目标分时系统的目标实时系统的目标,第一节处理机调度算法的目标,处
4、理机调度算法的共同目标：（1）资源的利用率CPU的利用率=CPU有效工作时间/（ CPU有效工作时间+ CPU空闲等待时间）（2）公平性指应使诸进程都获得合理的CPU时间，不会发生进程饥饿现象，根据紧急性和重要程度来提供不同的服务。（3）平衡性由于系统中进程的类型多样，比如有计算进程，有I/O进程，为了使得处理机和各外部设备都处于忙碌状态，调度算法需要考虑保持资源使用的平衡性。（4）策略强制执行对所制定的策略只要需要，就必须准确执行，即使会造成某些工作的延迟也要执行。（例如：文件安全性检测）,第一节处理机调度算法的目标,批处理系统的目标：（1）平均周转时间短周转时间：指从作业被提交给系统开始到
5、作业完成为止，这段时间间隔。包括：作业在外存后备队列上等待调度的时间、进程在就绪队列上等待调度的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。为了使大多数用户都感到满意，系统应使作业的周转时间和平均周转时间尽量短，否则会引起特别是短作业用户的不满。那么作业平均周转时间表示为：,第一节处理机调度算法的目标,批处理系统的目标：（2）系统吞吐量高指在单位时间内系统所完成的作业数。单纯的满足吞吐量高只需要尽量多的选择短作业运行。（3）处理机利用率高使CPU一直忙碌，最好处理计算量大且复杂的长作业。分时系统的目标：（1）系统响应时间快指从用户通过键盘提交一个请求开始，到屏幕上显示处理结果
6、为止的这一段时间间隔。（2）均衡性系统响应时间的快慢应与用户所请求服务的复杂性相适应。实时系统的目标：1.截止时间的保证：某任务必须开始执行或完成的最迟时间。2.可预测性：如对于视频连续播放，实现第i帧的播放和i+1帧的读取处理，这便提供了请求的可预测性。,第二节作业与作业调度,作业调度：将存放在外存后备队列中的作业调入内存中。1.批处理系统中的作业和作业步作业：不仅包含程序和数据还包含一份作业说明书，系统根据作业说明书来控制、运行程序。作业步：每个作业在运行期间，都要经历若干个加工步骤，我们把每个加工步骤称为一个作业步。例如：编译作业步、链接装配（目标程序）作业步、运行作业步。2.作业控制块
7、（JCB）JCB：作为作业在系统中存在的标识，保存了系统对作业进行管理和调度的信息。包括：作业标识、用户名、资源使用情况等等。过程：一个作业进入系统，便为其建立JCB，然后根据其类型将它放入相应的后备队列中，若它被系统调度，则将其由外存放入内存。作业在运行过程中，系统会根据作业说明书对作业进行控制，完成运行后，系统将收回已分配给它的资源并撤销JCB。,第二节作业与作业调度,作业运行的三个阶段和三种状态（1）收容阶段作业进入系统后会存放在系统的外存（硬盘）中，创建JCB并插入到相应的后备队列来等待作业的调度，此时作业的状态称为后备状态。（2）运行阶段当作业被作业调度选中后，并为其创建进程，分配必
8、要资源，插入到就绪队列中。作业从第一次进入到就绪状态到运行结束前期间，都称之为运行状态。（3）完成阶段当作业运行完成或发生异常情况而终止时，作业便进入完成状态。,第二节作业与作业调度,作业调度的主要任务（1）接纳多少个作业每次执行作业调度时，决定将多少个作业由外存调入到内存中，取决于多道程序度 ，即允许多少个作业同时在内存中运行。 多道程序度的确定需要综合系统的规模、运行速度、作业大小、系统性能等情况。 （2）接纳哪些作业由调度算法决定将哪些作业从外存调入内存。1.先来先服务调度算法2.短作业优先调度算法3.基于作业优先级的调度算法作业调度仅应用于批处理系统中，实时、分时系统没有。,第二节 调
9、度算法,先来先服务FCFS (first come, first served)短作业优先SJF (short job first)高响应比优先HRRN (Highest Response Ratio Next),先来先服务（FCFS）,主要用于作业调度，也可用于进程调度。用于作业调度：每次从后备作业队列中选择最先进入的作业，将它们调入内存，为它们分配资源、创建进程，然后挂到就绪进程队列上。有利于长作业，而不利于短作业。用于进程调度：每次从就绪进程队列中选择最先进入的进程，为之分配处理机，使之投入运行。直到运行完成进程才会让出处理机-非抢占式。性能评价：周转时间 = 完成时间 到达时间带权周转
10、时间 = 周转时间 / 服务（运行）时间,单处理机系统，FCFS 有利于 CPU繁忙型的作业,短作业优先调度算法,短作业优先算法（SJF）是以作业所要求的运行时间长短来计算优先级的，作业越短，其优先级越高。SIF算法将从外存的后备队列中，选择若干个估计运行时间最短的作业，优先将它们调入内存运行。缺点：必须预知作业的运行时间，一般采用偏长估计。对长作业非常不利，其周转时间会明显增长，没 有限制作业等待时间，可能会出现饥饿现象。无法实现人机交互。未考虑作业的紧迫程度。,短作业 / 进程优先（SJ/PF）,优先级调度算法（PSA）,是基于作业的紧迫程度，由外部赋予作业相应的优先级，根据优先级进行调度
11、，该算法既能用于作业调度，也可用于进程调度。作业调度思想：从后备队列中选择若干个优先级最高的作业，装入内存或（进程）分配给处理机。对进程调度而言，有非抢占式和抢占式两种。非抢占式：主要用于批处理系统，也可用于某些对实时性要求不严的实时系统抢占式：每当出现新就绪进程，就将其优先权与正在执行的进程的优先权比较；用于严格的实时系统，对性能要求高的批处理和分时系统中。,高响应比优先调度算法HRRN,FCFS算法特点：只考虑作业从进入系统时，在后备队列中排队等待被系统调入内存中的等待时间，也就是先来先服务思想，而忽略了作业的运行时间。SJF算法特点：只考虑作业的运行时间，按照运行时间越短越优先的选择，而
12、忽略了作业的等待时间，与FCFS算法正好相反。HRRN算法特点：既考虑了作业的等待时间又考虑了作业的运行时间。因此照顾了短作业，又不致使长作业的等待时间过长。,高响应比中优先权,动态优先权：系统为每一个作业创建一个动态优先级，令它随等待时间的延长而增加，即作业的等待时间越久，那么作业的优先级会变得越来越高，到一定时间后，必然获得调度。优先级的变化规律用公式描述为： 等待时间 + 要求服务时间优先权 = - 要求服务时间,高响应比中响应比,等待时间 + 要求服务时间优先权 = - 要求服务时间Rp 响应比： 等待时间 + 要求服务时间 响应时间 Rp = - = - 要求服务时间 要求服务时间该
13、调度算法大大改进了FCFS和SJF算法的缺点。,如果作业的等待时间相同，则要求服务的时间越短，优先权越高，该算法有利于短作业当要求服务的时间相同时，等待时间越长，优先权越高，实现了FCFS对于长作业，当等待时间足够长，优先权可升到很高，也可以得到处理该算法照顾了短作业，考虑了作业到达的先后次序，不会使长作业长期得不到服务，它实现了一个较好的折中。,课堂练习,计算在单CPU环境下,采用FCFS调度算法、SJF优先调度算法和高响应比优先算法时的平均周转时间和平均带权周转时间,并指出它们的调度顺序,答案,FCFS：,答案,SJF：,顺序：1-4-3-2,答案_优先级计算,HRRN：高响应比优先,优先
14、级计算方法：第一轮：优先级比较（编号3优先）2.优先级=（1.5+1）/1=2.53.优先级=（1.33+0.5）/0.5=3.664.优先级=（0.5+0.3）/0.3=2.66,第二轮：优先级比较（编号4优先）2.优先级=（2+1）/1=34.优先级=（1+0.3）/0.3=4.33顺序：1-3-4-2,答案,HRRN：高响应比优先,顺序：1-3-4-2,进程调度,无论是在多道批处理系统、分时系统还是实时系统中，都配置了进程调度。进程调度任务（1）保存处理机的现场信息（2）按某种算法选取进程调度程序按某种算法从就绪队列中选取一个进程，将其状态改为运行状态，并准备分配处理机。（3）把处理器分
15、配给进程由分派程序将处理器分配给该进程，此时需要将选中进程的PCB内有关处理机现场的信息装入处理器相应的各个寄存器中，把处理器的控制权交给该进程，让它从上次的断点处恢复运行。,进程调度机制,（1）排队器用于将系统中的所有就绪进程按照一定策略，排成一个或多个队列。排队器负责将新的就绪进程插入到相应的就绪队列中。（2）分派器分派器根据进程调度程序所选定的进程，负责将其从就绪队列中取出，将其交与上下文切换器。（3）上下文切换器发生上下文切换时，分二步：第一步，处理机中断对当前进程的运行，并将此时处理机中寄存器内容保存到当前进程的PCB中。第二步，将新选中的就绪进程的PCB中记录的CPU现场信息装入到
16、处理机的各个相应寄存器中，以便该新进程运行。,进程调度方式,1.非抢占方式指系统一旦把处理机分配给某个进程，就一直让该进程运行下去，直至该进程完成或者因发生某事（I/O请求、执行block原语）而被阻塞。2.抢占方式这种调度方式允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。那么抢占所遵循的原则主要有：a.优先权原则：允许优先权高的新进程抢占当前进程的处理机。b.短进程优先原则：允许新到的短进程抢占当前长进程的处理机。c.时间片原则：即各进程按时间片轮转运行。,时间片轮转调度算法,时间片轮转调度算法称为RR算法，该算法特别公平，即让就绪队列上的每
17、个进程每次仅运行一个时间片。原则：FCFS策略时间片：几ms 几百ms 切换时机：1.若时间片尚未用完，正在运行的进程已完成，则立即启动对下一个就绪进程的执行。2.若时间片已用完，进程尚未运行完毕，则借助计时器，将其送入就绪队列队尾，并运行下个就绪进程。实现方法：由计时器发出时钟中断，引起一次轮转调度。,q=1时，时间片太小，系统会频繁地执行进程的调度，增加系统开销，平均周转时间长。选择合适的时间片，能缩短系统的响应时间。,服务时间4,3,4,2,4,优先级调度算法,由于进程的紧迫性并不相同，于是在进程调度算法中引入了优先级，从而形成了优先级调度算法。该算法将处理机分配给优先级最高的进程。优先
18、级调度算法的类型：（1）非抢占式优先级调度算法一旦把处理机分配给就绪队列中优先级最高的进程后，该进程便一直执行下去直至完成。（2）抢占式优先级调度算法 把处理机分配给优先级最高的进程，使之执行。但在执行期间，只要出现了另一个优先级更高的进程，调度程序则会立即停止对该进程的执行，从而将处理机资源分配给新到的进程。即系统中每出现一个新的就绪进程变会与正在执行的进程进行优先级比较。该算法常用于对实时性要求较高的系统。,优先级调度算法,优先级的类型：（1）静态优先级指在进程创建时确定的，在进程的整个运行期间保持不变，使用0255中的一个整数来表示。确立优先级大小的依据：1.进程的类型：通常系统进程的优
19、先级高于一般用户进程的优先级。2.进程对资源的需求：对资源要求少的进程优先级越高。3.用户要求：根据进程的紧迫程度确定优先级。（2）动态优先级指在创建进程之初，先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变，以获得更好的调度性能。例如：随着等待时间的增加，让其优先级变得更高；若就绪进程的优先级初值相同，则遵循FCFS原则；若优先级不同，则随着等待时间增加，提高其优先级；若采用抢占式调度方式，则设定随着进程的运行时间增加，其优先级慢慢降低，可防止一个长作业一直运行。,多队列调度算法,多队列：该算法将进程的就绪队列，按照不同的类型或性质拆分为不同的就绪队列，不同的就绪队列采用不同的
20、调度算法。同一就绪队列进程设置不同优先级。特点：能够实现根据不同用户进程的需求，很容易提供多种调度策略。对于一组相互合作的进程而言，可以将它们分配到一组处理机所对应的多个就绪队列中，使得它们能同时获得处理机并行执行。,多级反馈队列调度算法,特点：不必事先知道各进程所需的执行时间，还可以较好满足各种类型进程的需要，是一种较好的算法。多级反馈队列调度算法的思想设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片，第一个队列优先级最高而队列中进程的执行时间片最短，随后渐变；新创建的进程挂到第一优先级的队列的末尾，然后按 FCFS 原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便
21、撤离系统；如果不能完成，便被挂入第二队列末尾，当被降到第n个队列后，便采用RR；按队列优先级调度。仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推；新进程可抢占低优先级进程的处理机。,多级反馈队列调度算法的性能,设置第一个队列的时间片略大于人机交互时间，就能较好地满足各种类型用户的需要。服务于终端（交互）型作业用户：由于这些用户提交的作业较小，能够在第一队列所规定的时间片内完成，让用户感到满意。短批处理作业用户：经过两到三个队列的时间片的执行一般也能完成，周转时间短。长批处理作业用户：在n个队列中执行，用户不必担心作业长期得不到处理。,基于公平原则的调度算法,考虑到调度的公
22、平性，设计了以下两种相对公平的调度算法：1.保证调度算法它向用户作出明确的性能保证（做到处理机分配的公平性）。在实行该算法时，系统必须具有这样一些功能：（1）跟踪计算每个进程自创建以来已经执行的处理时间。（2）计算每个进程应获得的处理机时间。（3）计算进程获得处理机时间的比率，即进程实际执行的时间和应获得的处理机时间之比。（4）比较各进程获得处理机时间的比率。（5）调度程序应选择比率最小的进程将处理机分配给它，并让该进程一直运行，直到超过最接近它的进程的比率为止,基于公平原则的调度算法,2.公平分享调度算法该算法与体现进程的公平性不同，其体现的是用户的公平性。假设在系统中，有两个用户，用户1启
23、动了4个进程，用户2只启动了一个进程，按照RR算法，那么用户1得到了80%的处理机时间，用户2只得到了20%，这显然对用户2不公平。那么怎么办呢？只需要在系统中执行强制调度序列。如果用户1的4个进程为A、B、C、D，用户2的一个进程为E，那么要保证两个用户获得相同的处理机时间的强制调度序列为：A E B E C E D E A E如果希望用户1获得的处理机时间是用户2的两倍，则：A B E C D E A B E,死锁概述,什么是死锁1.假设系统中只有一台扫描仪R1和一台刻录机R2，现有两个进程P1和P2，都准备将扫描的文档刻录到CD光盘上。如果P1先向系统请求扫描仪成功，P2先向系统请求刻录
24、机成功，那么P1再请求刻录机资源就会被阻塞，同时P2再请求扫描仪资源是也会被阻塞。这种它们谁都因不能获得自己所需的资源去继续运行，从而无法释放自己占有的资源，并一直处于这样僵持的状态的现象，称之为死锁。2.哲学家进餐问题，同时拿起左筷子。,死锁概述,死锁产生的原因资源问题系统中有许多不同类型的资源，其中需要互斥访问的资源可以引起死锁现象，这种资源也称为临界资源。系统的资源主要分为：1.可重用性资源性质：a.资源的单元对应一个进程，不共享。b.进程使用该资源所需顺序：1.请求资源。2.使用资源（用打印机打印）3.释放资源。c.系统中可重用性资源的单元数目是固定的。2.消耗性资源也称为临界资源，由
25、进程创建和消耗，具有如下性质：a.在进程运行期间，该资源的单元数目是变化的，数值可以很大，也可以为0。b.进程可以不断创建该资源的单元。c.进程在运行过程中可以请求若干个该资源。该资源通常由生产者进程创建，消费者进程消耗。,死锁概述,3.可抢占性资源指某进程在获得这类资源后，该资源可再被其它进程或系统抢占。例：优先级高的进程抢占优先级低的进程的处理机资源。将阻塞进程由内存调入外存中，抢占其内存空间。4.不可抢占性资源指一旦系统把资源分配给该进程后，就不能将它强行收回，只能在进程用完后自行释放。例如：刻录机、打印机等都属于不可抢占性资源。,计算机系统中的死锁,引起死锁的原因，通常是由于多个进程对
26、不可抢占资源的争夺或是对可消耗资源的争夺导致的。1.竞争不可抢占性资源引起的死锁例如：在系统中有两个进程P1、P2，两进程都准备写两文件F1、F2，这两文件属于系统中的可重用、不可抢占性资源。进程P1先打开F1进行写，然后再打开F2进行写，进程P2与之相反。a.若P1,P2都按照先打开F1再打开F2或先打开F2再打开F1的方式都能正常运行。b.若P1打开F1的同时P2去打开F2，这样会导致这两个进程无限地等待下去，而形成死锁。,计算机系统中的死锁,计算机系统中的死锁,2.竞争可消耗资源引起的死锁,1.正常情况：每个进程同时都先发送消息，再接收消息。2.死锁：每个进程同时都先接收消息，再发送消息
27、，那么每个进程都在等待一条永远不会发出的消息。,进程推进顺序不当,进程推进顺序不当引起的死锁指进程在运行过程中，对资源进行申请和释放的顺序是否合法。如果系统中只有一台打印机R1和一台磁带机R2，进程P1、P2会有两种顺序向前推进：1.进程推进顺序合法按照书P115图3-14中曲线1的顺序推进：随着时间推移为：P1请求R1，P1请求R2，P1释放R1，P1释放R2，P2开始请求R2,请求R1,释放R2,释放R1。2.进程推进顺序非法详见曲线4，曲线进入不安全区D，可能会发生死锁。,死锁的定义、必要条件和处理方法,1.死锁的定义如果一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事
28、件，那么该组进程是死锁的（Deadlock）。2.产生死锁的必要条件同时具备以下几个必要条件将会产生死锁：（1）互斥条件。进程只能互斥访问某资源，该资源只能被一个进程占用。（2）请求和保持条件。进程已经保持了至少一个资源，并且又提出了新的资源请求，但该资源被其他进程占用，此时该进程仍对已获得资源保持不放。（3）不可抢占条件。进程已获得的资源在未使用完之前不能被抢占，只能在进程使用完时释放。（4）循环等待条件。在发生死锁时，必然存在一个进程-资源的循环链：P0正在等待P1占用的资源，P1正在等待P2占用的资源，。，Pn正在等待P0占用的资源。,死锁的定义、必要条件和处理方法,3.处理死锁的方法（
29、1）预防死锁该方法通过设置某些限制条件，去破坏产生死锁的必要条件中的一个或几个来预防产生死锁。（2）避免死锁在系统资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。（3）检测死锁通过检测机构及时地检测出系统死锁的发生，然后采取适当的措施，把进程从死锁中解脱出来。（4）解除死锁当检测到系统中已发生死锁时，就采取相应措施，将进程从死锁状态中解脱出来。常用方法：撤销一些进程，回收它们的资源，用以解脱处于阻塞状态的进程。,预防死锁,破坏产生死锁的条件来预防死锁:1.破坏请求和保持条件 系统必须保证做到：当一个进程在请求资源时，它不能持有不可抢占资源，可通过如下两个协议实现：
30、a.第一种协议 该协议规定，所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源。若资源足够，则破坏了请求条件；若资源不足，一种资源都不允分配，则破坏了保持条件。该协议简单、易行、安全但仍有以下缺点： （1）资源被严重浪费，严重恶化资源利用率。 （2）使进程经常会发生饥饿现象。b.第二种协议 它允许一个进程只获得运行初期所需的资源后，便开始运行。进程运行过程中再逐步释放已分配给自己的、且已用完的全部资源，然后再请求新的所需资源。,预防死锁,破坏不可抢占条件 规定当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需
31、要时再重新申请。相当于进程占有的资源被抢占了，从而破坏了不可抢占条件。缺点：方法实现较复杂。让不可抢占资源（打印机）被抢占，会使得被抢进程前后两次运行的信息不连续。让资源被抢的进程因为一直不能获得所需全部资源而无限的等待，从而延长了进程的周转时间，降低了系统吞吐量。,预防死锁,破坏循环等待条件对系统所有资源类型进行线性排序，并赋予不同的序号。规定每个进程必须按序号递增的顺序请求资源。如果某进程已请求到一些序号较高的资源，但又想请求一个序号低的资源时，它必须释放所有具有相同和更高序号的资源后，才能申请序号低的资源。采用这种策略所形成的资源分配图中，不可能再出现环路，因而破坏了循环等待条件。缺点：
32、规定的序号必须相对稳定，限制了新设备的添加。作业实际使用资源的顺序与系统规定的顺序不同，造成资源的浪费。限制了用户简单、自主地编程。,避免死锁,避免死锁属于事先预防的策略，是指在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁，是目前常用的方法。系统安全状态当系统处于安全状态时，就可以避免发生死锁，反之，系统就可能进入死锁状态。避免死锁思想：该方法允许进程动态地申请资源，但系统在分配资源前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，才可将资源分配给进程，否则令进程等待。安全状态：指系统能够按照某种进程推进顺序，为每个进程分配其所需资源，使每个进程都能顺利运行
33、完成。不安全状态：如果系统无法找到一个让每个进程都能顺利完成的安全序列，则系统处于不安全状态。,避免死锁,系统安全状态例子避免死锁方法如何让系统处于安全状态，举例：系统中有三个进程，共12台磁带机，T0时刻资源分配T0时刻系统是安全的，存在安全序列，是的每个进程都能顺利运行完成。若不按照安全序列为进程分配资源，系统可能会进入不安全状态，T0时刻后，系统给P3分配资源1,?,避免死锁思想：确保系统始终处于安全状态：当进程请求一个资源时，系统需要进行计算，若资源分配后系统仍处于安全状态，才把资源分配给该进程。,利用银行家算法避免死锁,创始人Dijkstra，该算法因能用于银行系统现金贷款的发放而得
34、名。银行家算法的实质就是要设法保证系统动态分配资源后仍然保持安全状态，从而避免死锁的发生。要求：进程预先告知自己的最大资源需求，并且假设系统拥有固定的资源总量。,银行家算法中的数据结构,可利用资源向量Available：它是一个含有m个元素的数组，其中每个元素代表一类可利用资源的数目，Availablej=k表示系统现有Rj类资源k个。动态改变，初始值？最大需求矩阵Max: n x m矩阵，表示n个进程的每一个对m类资源的最大需求，Maxi,j=k表示进程i需要Rj类资源的最大数目为k个。,分配矩阵Allocation ：n x m矩阵，表示每个进程已分配的资源数，Allocationi,j=
35、k表示进程i当前已分得Rj类资源的数目为k。需求矩阵Need ： n x m矩阵，表示每个进程还需要各类资源数，Needi,j=k表示进程i还需要Rj类资源k个。存在关系：Needi,j=Maxi,j- Allocationi,j,数据结构示例,设系统有五个进程和三类资源，每类资源分别有10、5、7。在T0时刻资源分配情况如图,银行家算法描述,设Requesti是进程Pi的请求向量， Requestij=k 表示进程Pi申请k个Rj类资源，进程Pi发出请求后，系统执行步骤：如果Requestij Needi,j，便转步骤2，否则认为出错；如果Requestij Availablej，便转步骤3
36、，否则表示尚无足够资源， Pi须等待；系统试探着把资源分配给Pi ，并修改数据结构： Availablej = Availablej - Requestij; Allocationi,j = Allocationi,j + Requestij; Needi,j = Needi,j - Requestij;系统执行安全性算法，如果安全则正式分配，否则试探分配作废并恢复原来的资源分配状态；,算法实现,安全性算法设置两个向量：工作向量Work: 表示系统可提供给进程继续运行所需要的各类资源数目，Workj=k表示Rj类资源可用数目为k个；布尔向量Finish:表示系统是否有足够的资源分配给进程，使之
37、运行完成, Finishi= true表示系统有足够资源分配给进程i使其运行完成；Work有m个元素，初始值为： Workj= AvailablejFinish有n个元素，初始值为： Finishi=false,安全性算法步骤(1) Work:=Available; Finish:=false;(2) 寻找满足下列条件的进程i： a). Finishi=false; b). Needi,jWorkj;如果找到，转步骤（3），否则转(4)；,(3) 假设进程Pi获得资源后，可顺利执行完成， 并释放资源，则： Workj:=Workj+Allocationi,j; Finishi:=true; 转
38、(2)(4) 若对所有i,Finishi=true,则系统处于安 全状态，否则处于不安全状态,例：假定系统有5个进程，三种资源，在T0时刻的资源分配表如图：（该时刻是否安全状态？）,FinishFalseFalseFalseFalseFalse,Work3 3 2,T0时刻的安全性检查,P1请求资源Request(1,0,2),经过前面的判断试探性分配资源,P1请求资源Request(1,0,2),对此进行安全性检查,继P1 后P4请求资源Request(3,3,0),P4发出请求Request(3,3,0), 执行银行家算法Available=2 3 0不能通过算法第2步 （ 要求Reque
39、stAvailable ），所以P4等待。,继P4 后P0请求资源Repuest(0,2,0),进行安全性检查: Available2,1,0已不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配，若改成（0，1，0）？,练习,有三类资源A(17)、B(5)、C(20)。有5个进程P1P5。T0时刻系统状态如下：问(1)、T0时刻是否为安全状态，给出安全系列。(2)、T0时刻，P2: Request(0,3,4)，能否分配，为什么？(3)、在(2)的基础上P4：Request(2,0,1)，能否分配，为什么？(4)、 在(3)的基础上P1：Request(0,2,0)，能否分配，为
40、什么？,(1) T0时刻的出安全系列,先求出Need和Work,A(17)、B(5)、C(20)Work=Available=( 2 3 3 ),Work=2 3 3,(2) P2: Request(0,3,4),因 Request(0,3,4) Available（2 3 3） 所以不能分配,(3) P4：Request(2,0,1),Available =2 3 3,(4) P1：Request(0,2,0),0 1 2 已不能满足任何进程的需要，不能分配,检测与解除死锁,死锁的检测允许死锁发生，通过系统的检测机构，及时地检测出死锁的发生，确定与死锁有关的进程和资源。一旦死锁发生则采取专门
41、的措施，解除死锁并以最小的代价恢复操作系统运行检测时机：死锁的频繁检测会增加系统开销为了检测系统须：,（1）当进程等待时检测死锁 （其缺点是系统的开销大） （2）定时检测 （3）系统资源利用率下降时检测死锁,（1）保存有关资源的请求和分配信息；（2）提供一种算法，以利用这些信息来检测 系统是否已进入死锁状态。,死锁的检测方法死锁定理,资源分配图：描述死锁现象 是由一组结点N和一组边E组成的一个对偶G=（N，E） N：结点集，分为P，R进程、资源两子集部分 P=p1,p2,pn R=r1,r2,rm N=P U R E：边的集合，其元素为有序二元组 (pi,rj)或(rj,pi) 进程Pi指向R
42、j,表示进程Pi请求一个单位的Rj资源 资源Rj指向Pi,表示已将一个单位的Rj资源分配给进程Pi,死锁的检测方法死锁定理,资源分配图表示法资源类（资源的不同类型）：用方框表示资源数量（存在于每类资源中）：用方框中的圆圈表示进程：用圆圈中加进程名表示分配边：资源实例进程的一条有向边申请边：进程资源类的一条有向边,死锁的检测方法死锁定理,资源分配图实例,死锁的检测方法死锁定理,资源分配图简化：1）找出一个既不阻塞又非独立的进程结点Pi，在顺利情况下Pi可获得所需资源运行完毕，再释放所有资源，这相当于消去Pi的分配边和请求边，将其变为孤立结点。2）重复上述操作，若所有进程成为孤立结点，称该图是可完全简化的，否则称该图是不可完全简化的。状态S为死锁状态的充分条件：当且仅当S状态的资源分配图是不可完全简化的。该充分条件称为死锁定理,资源分配图简化实例,资源分配图简化实例,资源分配图简化实例,资源分配图简化实例,死锁检测中的数据结构,见教材P125,检测与解除死锁,死锁的解除一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。最小代价撤销进程法：选择被撤进程代价最小的。挂起进程：使用挂起与激活机构，缓解资源紧张。,The END！,
