操作系统4、处理机.ppt

四、处理机,处理机调度和反死锁策略,处理机调度的层次和调度算法的目标作业与作业调度进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除,处理机调度的层次,长程调度对作业进行调度，适用于多道批处理系统。短程调度对进程进行调度，适用于多道批处理、分时和实时系统。内存调度用于提高内存利用率和系统性能。将需要等待的进程占用的内存资源交换至外存，将可以继续运行的进程需要的内存资源从外存中读入。,处理机调度算法的共同目标,资源高利用率：CPU和其他所有资源都尽可能地保持忙碌状态。公平性：合理地对各进程分配CPU时间，避免出现某些进程长时间无法得到响应。平衡性：合理地调度计算型作业与I/O型作业，以保证各种资源使用的平衡性。,批处理系统的目标,平均周转时间短：周转时间包括等待时间和运行时间，周转时间与运行时间之比是带权周转时间。短作业优先。系统吞吐量高：吞吐量是指在单位时间内系统所完成的作业数。短作业优先。处理机利用率好：尽量少地切换作业、调度资源及等待。长作业、计算型作业优先。,分时系统的目标,响应时间快：响应时间=输入时间+运行时间+输出时间均衡性：响应时间的快慢与用户请求服务的复杂性相关，复杂任务的响应时间允许较长。,实时系统的目标,截止时间的保证：对于硬实时任务，调度方式和算法必须严格确保截止时间的要求；对于软实时任务，调度方式和算法也应基本上能保证截止时间的要求。可预测性：根据系统特点，可预测未来一段时间内的处理目标，以提高实时性（如媒体播放中同时读取第i帧和第i+1帧）。,处理机调度和反死锁策略,处理机调度的层次和调度算法的目标作业与作业调度进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除,批处理系统中的作业及调度,作业（Job）：批处理系统中进行调度的基本单位，包含程序、数据和作业说明书。系统根据说明书控制程序运行。作业步（JobStep）：作业中包含的多个相关的加工步骤。作业步之间存在相互联系，如输入输出关系。作业控制块（JobControlBlock）：存放作业在系统中管理和调度所需的信息，由作业注册程序创建。,批处理系统中的作业及调度,作业运行的三个阶段和三种状态收容阶段（后备状态）：由作业注册程序建立作业控制块（JCB），作业进入硬盘中的后备队列。运行阶段（运行状态）：作业被作业调度选中进入就绪队列，获得资源并建立进程，直至运行结束。完成阶段（完成状态）：作业正常完成或异常终止。“终止作业”程序负责撤销作业控制块、回收资源和输出运行结果。,批处理系统中的作业及调度,作业调度的主要任务根据JCB中的信息，检查系统资源能否满足作业需求，并按照一定的调度算法决定哪些作业由后备队列进入就绪队列。常见的调度算法有：先来先服务算法（First-ComeFirst-Served）短作业优先算法（ShortJobFirst）优先级调度算法（Priority-scheduling）高响应比优先算法,先来先服务调度算法（FCFS）,用于作业调度和进程调度，优先考虑最早进入等待队列的作业以及最先进入就绪队列的进程。非抢占：进程占有CPU直到程序结束或I/O中断。优点：实现简单，有利于长作业。缺点：不利于短作业，平均等待时间长。,短作业优先调度算法（SJF）,优先考虑运行时间最短的作业。优点：平均等待时间短，有利于短作业。缺点：作业的运行时间无法准确估计，长作业可能长期得不到响应。估计作业时间的方法：由用户指定进程运行时间极限，如果超时则报错。,优先级调度算法,根据作业的紧迫程度定义优先级，优先级高的作业优先运行。优先级定义依据内部方式：完成时限、内存占用、文件占用、CPU与I/O时间比外部方式：重要性、出价金额缺点：低优先级进程长期无法得到响应解决方案：定期提升等待进程的优先级,高响应比优先调度算法,先来先服务调度算法和短作业优先调度算法的折中方案。短作业以及等待时间长的作业都具有高优先级。,处理机调度和反死锁策略,处理机调度的层次和调度算法的目标作业与作业调度进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除,进程调度的目的,当多数进程的I/O区间较长、CPU区间较短时，加快进程的整体完成速度。确保所有任务都能完成。确保所有任务能尽快完成。确保所有任务能在限定时间内完成。,进程调度的任务,保存即将切换出处理机的进程信息：如多个通用寄存器中的内容等。选取一个切换入处理机的进程读取该进程的信息：将选中进程的进程控制块中有关处理机现场的信息，装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。,进程调度机制,排队器：将系统中所有就绪进程排成一个或多个队列分派器：从就绪队列中取出一个进程，与当前运行的进程进行上下文切换，并分配处理机。其间消耗的时间称为分派延迟。上下文切换器：保存当前进程的处理机寄存器内容，装入分派程序的处理机寄存器内容。通过使用多组寄存器和指针的方法加速切换过程。,进程调度机制,进程调度方式,非抢占方式（Windows3.x之前）已分配进程一直拥有处理机资源，直到正常结束或异常终止I/O操作在进程通信或同步过程中，主动使用阻塞原语Block优点：实现简单、系统开销小，适用于大多数的批处理系统。缺点：不能用于分时系统和大多数实时系统。,进程调度方式,抢占方式（Windows95开始）允许调度程序根据以下某种原则主动切换进程：优先权原则：允许优先级高的新到进程抢占当前进程的处理机；短进程优先原则：允许新到的短进程抢占当前长进程的处理机；时间片原则：各进程按时间片轮转运行，当正在执行的进程的一个时间片用完后，便停止该进程的执行而重新进行调度。优点：适用于分时系统和大多数实时系统。缺点：实现复杂、系统开销大。,下一个最短CPU区间算法,进程由CPU区间和I/O区间组成。CPU优先分配给具有下一个最短CPU区间的进程（类似SJF）。下一个CPU区间长度无法精确计算，但可根据历史数据估算。,CPU区间长度估算,n+1=tn+(1-)n=tn+(1-)tn-1+(1-)jtn-j+(1-)n+10其中t表示实际时长，表示估计时长，0,1例：=0.5，0=10,下一个最短CPU区间算法,在抢占模式下，当新进程到达时，与当前运行进程比较剩余时间，优先执行最短剩余时间进程。（平均等待时间比非抢占短）,轮转调度算法,轮转法的基本原理基于时间片的轮转（RR，RoundRobin）调度算法。所有进程轮流获得CPU资源，当时间片（如30ms）结束时，进程调度程序把CPU分配给队列中的下一个进程。Robin知更鸟,轮转调度算法,进程切换时机时间片用完，计时器中断处理程序激活。如果进程尚未运行完毕，调度程序把它送往就绪队列的末尾。时间片尚未用完，但正在运行的进程已经完成，就立即激活调度程序，将它从就绪队列中删除，再调度就绪队列中队首进程运行，启动一个新的时间片。,轮转调度算法,时间片大小的确定小的时间片有利于短作业，但频繁切换进程将增加系统开销。大的时间片能减少进程切换频率，有利于长作业，但若时间片选择得太长，使每个进程都能在一个时间片内完成，RR算法便退化为FCFS算法，无法满足短作业和交互式用户的需求。现代操作系统的时间片为10100ms，上下文切换时间一般小于10s,q=1时，进程执行顺序ABCDEABCDEABCEACE,优先级调度算法,优先把处理机分配给就绪队列中优先级最高的进程。优先级调度算法的类型非抢占式优先级调度算法：适用于批处理系统抢占式优先级调度算法：适用于实时性要求较高的系统,优先级调度算法,优先级的类型静态优先级：在创建进程时确定并保持不变。系统进程、要求资源较少的进程、紧迫程度高的进程的优先级高。动态优先级：在创建进程时赋予初始值，随着进程等待而增加，随着进程运行而减少。,多级队列调度算法（静态优先级）,将就绪队列分为多个具有不同优先级的队列。前台进程、系统进程具有高优先级，使用轮转调度算法。后台进程、批处理进程具有低优先级，使用FCFS调度算法。CPU采用抢占模式，根据优先级调度程序，或者根据优先级划分CPU时间。,多级反馈队列调度算法（动态优先级）,算法优点不需要预知各进程的执行时间，满足终端型用户、短批处理作业用户和长批处理作业用户的要求。调度机制N个就绪队列，赋予不同优先级，优先级越高时间片越短优先调度优先级最高的队列中的进程，各个队列分别采用FCFS算法所有新进程读入内存后进入第1级队列末尾（优先级最高），当执行后若未完成则进入下一级队列高优先级进程可以抢占CPU，被抢占进程回到所在等级的队列末尾,基于公平原则的调度算法,保证调度算法确保每个进程获得相对平均的处理机时间。将处理机分配给处理机时间比率最小的进程，直到该进程的时间比率不是最小的。公平分享调度算法确保每个用户获得相对平均的处理机时间。需要考虑每个用户拥有的进程数量。,多处理器调度,关注的问题：均衡负载、协同配合工作模式：非对称结构(asymmetricmultiprocessing)：主CPU负责进程调度、I/O，其它CPU负责执行代码对称结构(symmetricmultiprocessing,SMP)：所有CPU都具有私有调度进程队列，须注意临界数据一致性问题，WindowsXP以上支持。,亲和性与负载平衡,亲和性：进程保持在一个固定的CPU上运行，避免由于推迁移和拉迁移造成缓冲区数据在CPU间搬迁。负载平衡：所有CPU获得近似相等的进程负载。当出现负载不平衡时，通过推迁移和拉迁移改变进程归属的CPU。亲和性和负载平衡是矛盾的。,超线程技术(Hyper-Threading),处理机调度和反死锁策略,处理机调度的层次和调度算法的目标作业与作业调度进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除,实现实时调度的基本条件,提供必要的信息系统应向调度程序提供有关任务的信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级。系统处理能力强假设m个周期性硬实时任务，处理时间是Ci，周期时间是Pi，处理机数量为N，则必须满足：,实现实时调度的基本条件,采用抢占式调度机制具有快速切换机制对中断的快速响应能力：具有快速硬件中断机构，禁止中断的时间间隔尽量短；快速的任务分派能力：使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。,实时调度算法的分类,根据实时任务性质，可将实时调度的算法分为硬实时调度算法和软实时调度算法；按调度方式，则可分为非抢占调度算法和抢占调度算法。,非抢占式调度算法,轮转调度算法：调度程序每次选择实时任务队列的第一个任务投入运行，完成后挂在轮转队列的末尾。适用于要求不太高的实时系统。优先级调度算法：优先级高的实时任务排在就绪队列的队首，等待当前任务自我终止或运行完成。,抢占式调度算法,基于时钟中断的优先级调度算法：若就绪的实时任务的优先级高于当前任务，不立即抢占处理机，而是等到时钟中断发生时。适用于大多数实时系统。立即抢占的优先级调度算法：只要当前任务未处于临界区，能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。响应时间最短。,实时调度算法的分类,最早截止时间优先算法,根据任务的截止时间确定任务的优先级，具有最早截止时间的任务排在队列的前面。非抢占式调度方式用于非周期实时任务,最早截止时间优先算法,抢占式调度方式用于周期实时任务,最低松弛度优先算法,最低松弛度优先算法（LLF,LeastLaxityFirst）中，任务优先级根据任务的紧急（或松弛）程度。任务紧急程度愈高，赋予该任务的优先级就愈高，以使之优先执行。,A和B任务每次必须完成的时间,最低松弛度优先算法,进程的松弛度=必须完成时间其本身的运行时间当前时间,利用LLF算法进行调度的情况,优先级倒置,“优先级倒置”的现象：高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞。实时系统应避免“优先级倒置”现象。,优先级倒置：例子,三个独立的进程P1、P2和P3，优先级：P1P2P3。P1和P3共享临界资源。P1：P(mutex);CS-1;V(mutex);P2：program2;P3：P(mutex);CS-3;V(mutex);,优先级倒置的解决方法,方法一：进程P3进入临界区后，P3占用的处理机不允许被抢占。方法二：高优先级进程P1需要的临界资源若正被低优先级进程P3使用，则P1被阻塞，由P3继承P1的优先级，并保持到P3退出临界区。,处理机调度和反死锁策略,处理机调度的层次和调度算法的目标作业与作业调度进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除,可重用资源和消耗性资源,可重用资源：可供用户重复使用多次的资源。性质：一个资源单元只能分配给一个进程进程使用资源须按照请求资源、使用资源、释放资源的顺序。进程运行期间，每一类资源的单元数目固定不变。计算机系统中大多数资源都属于可重用资源。,可重用资源和消耗性资源,消耗性资源：进程运行期间，由进程动态创建和消耗。性质：进程运行期间，每一类资源的单元数目不断变化。部分进程创造消耗性资源单元，放入资源缓冲区中。部分进程消费消耗性资源单元，不再将它们返回给该资源类中。可消耗资源通常由生产者进程创建，由消费者进程消耗。最典型的可消耗资源是用于进程间通信的消息。,可抢占资源和不可抢占资源,可抢占资源：资源分配给进程后，可以再被其他进程或系统抢占（不会引起死锁）。CPU和主存属于可抢占资源。不可抢占资源：资源分配给进程后，不能强行收回，只能在进程用完后释放。磁带机、刻录机、打印机属于不可抢占资源。,死锁,如果一组进程中的每个进程都在等待仅由该组进程中的其它进程才能引发的事件，那么该组进程是死锁的。竞争不可抢占资源引起死锁P1P2Open(F1,w);Open(F2,w);Open(F2,w);Open(F1,w);,共享文件时的死锁情况,死锁,竞争可消耗资源引起死锁顺序1：P1：send(p2,m1);receive(p3,m3);P2：send(p3,m2);receive(p1,m1);P3：send(p1,m3);receive(p2,m2);,顺序2：P1：receive(p3,m3);send(p2,m1);P2：receive(p1,m1);send(p3,m2);P3：receive(p2,m2);send(p1,m3);,死锁,进程之间通信时的死锁,产生死锁的必要条件,互斥条件：进程对分配到的资源进行排它性使用。请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。不可抢占条件：进程已获得的资源，在未使用完之前不能被抢占，只能在进程使用完时由自己释放。循环等待条件：发生死锁时，必然存在一个进程资源的循环链，即进程集合P0，P1，P2，Pn中的P0，正在等待一个P1占用的资源，P1正在等待P2占用的资源，Pn正在等待已被P0占用的资源。,处理死锁的方法,预防死锁：属于事先预防策略。通过设置某些限制条件，破坏产生死锁四个必要条件中的一个或几个来预防产生死锁。预防死锁是一种较易实现的方法，已被广泛使用。避免死锁：属于事先预防策略，在资源的动态分配过程中，用某种方法防止系统进入不安全状态，避免发生死锁。,处理死锁的方法,检测和解除死锁：不事先采取任何限制性措施，允许进程在运行过程中发生死锁。通过检测机构及时检测死锁，撤消一些进程，回收资源，并分配给其他阻塞状态的进程，使其能继续运行。,处理机调度和反死锁策略,处理机调度的层次和调度算法的目标作业与作业调度进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除,破坏“请求和保持”条件,第一种协议：进程在开始运行前，必须一次性地申请其在整个运行过程中所需的全部资源。优点：简单、易行且安全。缺点：资源利用率低进程经常发生饥饿现象。,破坏“请求和保持”条件,第二种协议：进程在开始运行前，一次性地申请运行初期所需资源。运行过程中释放已分配并使用完毕的资源，请求新的所需资源。优点：使进程更快地完成任务，提高设备的利用率。,破坏“不可抢占”条件,当一个已经保持了某些不可被抢占资源的进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。缺点：实现复杂，需付出很大的代价。因为反复地申请和释放资源，致使进程的执行被无限地推迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。,破坏“循环等待”条件,设R=(R1,R2,R3,Rm)为资源类型的集合，为每个资源类型编号（根据大多数进程需要资源的先后顺序确定）。例如系统中有磁带驱动器、硬盘驱动器、打印机，则F(tapedrive)=1，F(diskdrive)=5，F(printer)=12。预防协议：每个进程必须按序号递增的顺序请求资源。如果需要多个同类资源单元，必须一起请求。优点：资源利用率和系统吞吐量明显改善。缺点：编号相对稳定的要求限制了新类型设备的增加；作业使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费。违背用户简单、自主的编程原则。,处理机调度和反死锁策略,处理机调度的层次和调度算法的目标作业与作业调度进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除,系统安全状态,系统能按某种进程推进顺序（P1，P2，Pn），为每个进程Pi分配所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称（P1，P2，Pn）为安全序列。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。,系统安全状态,假定系统中有三个进程P1、P2和P3，共有12台磁带机。P3请求1台磁带机，若系统把剩余3台中的1台分配给P3，则系统进入不安全状态。所有进程都在等待对方释放资源，导致死锁。,利用银行家算法避免死锁,银行家算法中的数据结构可利用资源向量Available：含有m个元素的数组，每个元素的初始值是一类可利用资源的数目，随该类资源的分配和回收而动态改变。Availablej=K表示系统中现有Rj类资源K个。最大需求矩阵Max：nm矩阵，定义n个进程对m类资源的最大需求。Maxi,j=K表示进程i需要Rj类资源的最大数目为K。分配矩阵Allocation：nm矩阵，定义当前已分配给各进程的资源数目。Allocationi,j=K表示进程i当前已分得Rj类资源的数目为K。需求矩阵Need：nm矩阵，表示各进程尚需的各类资源数目。Needi,j=K表示进程i还需要Rj类资源K个。Needi,j=Maxi,j-Allocationi,j,银行家算法,设Requesti是进程Pi的请求向量，Requestij=K表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：若RequestijNeedi,j，则转步骤2；否则出错，因为需要的资源数超过它所宣布的最大值。若RequestijAvailablej，则转步骤(3)；否则表示尚无足够资源，Pi须等待。系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值：Availablej=Availablej-Requestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestij;系统执行安全检查算法，确认资源分配后系统是否处于安全状态。若安全正式将资源分配给进程Pi；否则撤销分配，让进程Pi等待。,安全检查算法,设置两个向量：工作向量Work：表示系统可提供给进程继续运行所需的各类资源数目，含有m个元素。在执行安全算法开始时，Work=Available。Finish：表示系统是否有足够的资源分配给进程，使之运行完成。开始时Finishi=false;当有足够资源分配给进程时，Finishi=true。从进程集合中找到一个能满足下述条件的进程：Finishi=false;Needi,jWorkj；若找到执行步骤(3)，否则执行步骤(4)。当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：Workj=Worki+Allocationi,j;Finishi=true;返回步骤(2);如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。,银行家算法案例,系统中有五个进程P0,P1,P2,P3,P4和三类资源A,B,C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。,1、T0时刻的资源分配情况,1、T0时刻的安全性,2、P1请求Request1(1,0,2),Request1(1,0,2)Need1(1,2,2)Request1(1,0,2)Available(3,3,2)系统先假定可为P1分配资源，并修改Available,Allocation1和Need1向量利用安全性算法检查此时系统是否安全,2、P1请求Request1(1,0,2),3、P4请求Request4(3,3,0),Request4(3,3,0)Need4(4,3,1)Request4(3,3,0)Available(2,3,0)，让P4等待,4、P0请求Request0(0,2,0),Request0(0,2,0)Need0(7,4,3)Request0(0,2,0)Available(2,3,0)系统先假定可为P0分配资源，并修改Available,Allocation1和Need1向量利用安全性算法检查此时系统是否安全,4、P0请求Request0(0,2,0),处理机调度和反死锁策略,处理机调度的层次和调度算法的目标作业与作业调度进程调度实时调度死锁概述预防死锁避免死锁死锁的检测与解除,死锁检测,允许死锁发生，操作系统不断监视系统，判断死锁是否发生。一旦死锁发生，则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行,资源分配图,资源分配图是结点集N和有向边集E组成的对偶G=(N,E)，具有下述形式的定义和限制：把N分为两个互斥的子集，即进程结点集P=p1,p2,pn和资源结点集R=r1,r2,rn，N=PR。任意eE连接P和R中各一个结点。e=pi，rj是资源请求边，由进程pi指向资源rj，表示进程pi请求一个单位的rj资源。e=rj，pi是资源分配边，由资源rj指向进程pi，表示把一个单位的资源rj分配给进程pi。用圆圈代表一个进程，用方框代表一类资源。,资源分配图,P=p1,p2,R=r1,r2,N=r1,r2p1,p2。E=(p1,r2),(r2,p2),(p2,r1),(r1,p1)。,死锁定理,利用简化资源分配图方法检测当前系统是否处于死锁状态。,资源分配图简化方法,在资源分配图G=(N,E)中找出不阻塞且非独立的进程结点Pi，可获得所需资源至运行完毕，再释放全部资源，这相当于消去pi的请求边和分配边，使之成为孤立的结点，形成新的资源分配图G(N,E)。称G可化简为G。,资源分配图简化方法,在图a中，将p1的两个分配边和一个请求边消去，形成图b。p1释放资源后，可使p2获得资源而继续运行，直至p2完成后释放全部资源，形成图c。,资源分配图简化方法,资源分配图可化简关系具有传递性。即若G1可化简为G2，G2可化简为G3，则G1可化简为G3。对于资源分配图Gn(N,En)，若不存在Gn+1，使Gn可化简为Gn+1，则称Gn是不可简化图。当En为空集时，Gn必为不可简化图。若G(N,E)可化简为Gn(N,En)，且En为空集，则称资源分配图G是可完全简化的，否则称图G是不可完全简化的。,资源分配图简化方法,对于较复杂的资源分配图，可能有多个既未阻塞，又非孤立的进程结点，不同的简化顺序，是否会得到不同的简化图？有关文献已经证明，所有的简化顺序，都将得到相同的不可简化图。死锁定理：S为死锁状态，当且仅当S状态的资源分配图是不可完全简化的。,死锁检测中的数据结构,工作向量Work：含有m个元素的数组，初始值等于当前Available数组，表示m类资源的可用数目。分配矩阵Allocation：nm矩阵，定义当前已分配给各进程的资源数目。需求矩阵Need：nm矩阵，表示各进程尚需的各类资源数目。表L：用于记录不占用资源的进程（即Allocation=0）,死锁检测的方法,从进程集合中找到一个NeediWork的进程，做如下处理：释放进程资源，增加工作向量Work:=Work+Allocationi将进程记入L表中若不能把所有进程都记入L表中，表明系统状态的资源分配图是不可完全简化的。因此，该系统状态将发生死锁。,死锁检测的方法,Work:=Available;L:=Pi|Allocationi=0Needi=0;forallPiLdobeginforallNeediWorkdobeginWork:=Work+Allocationi;L:=PiL;endenddeadlock:=(LP1,P2,Pn);,死锁解除,发现进程死锁后，应立即把它从死锁状态中解脱出来，常采用的方法有：剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；撤消进程：直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态消除为止。,终止进程的方法,终止所有死锁进程：代价大，部分进程可能已接近结束。逐个终止进程：选择终止的依据是“代价最小”，包括进程优先级、已运行时间和剩余时间、已使用资源和需求资源、进程是交互式还是批处理式。,付出代价最小的死锁解除算法,作业,证明对于给定的一组进程，使用非抢占的短作业优先调度算法时，进程的平均完成时间最短。实时系统中有2个周期任务。第一个任务每隔m1秒需要进行n1次运算；第二个任务每隔m2秒需要进行n2次运算。现有2种CPU可供选择，第一种CPU每秒能运算r1次运算，价格为c1；第二种CPU每秒能运算r2次，价格为c2。问如何配置最省钱。课件第81页银行家算法案例中，如果把P0请求从Request0(0,2,0)改为Request0(0,1,0)，系统是否安全？证明同一个资源分配图按不同的简化顺序都将得到相同的不可简化图。证明死锁定理是正确的。写死锁解除算法，使用撤消进程的方法，通过撤销权值（表示撤销代价）总和最小的n个进程，使系统脱离死锁状态。,设n个进程的处理顺序是P1、P2、Pn，执行时间是t1、t2、tn，进程的平均完成时间为若进程不全按短作业优先原则，即存在Pj和Pk进程，满足jtk，则将Pj和Pk进程的交换，形成新的处理顺序P1、Pj-1、Pk、Pj+1、Pk-1、Pj、Pk+1、Pn，进程的平均完成时间为,两个周期任务平均每秒运算次数L=n1/m1+n2/m2，设Fori=0tok/i表示第一种CPU数量/j表示第二种CPU数量c=c1*i+c2*j/c表示总成本将最小的c对应的i和j作为第一种和第二种CPU的配置数量,P1、P3、P4、P2、P0,对于进程P1、P2、Pn，若资源分配图的两种简化方法涉及的进程（Pj1、Pj2、Pjm）相同，仅简化的顺序不同。由于资源简化的方法是将与进程节点有关的边都删除形成孤立节点，与执行顺序无关。资源分配图的初始值相同，故简化后也相同。若方法一与方法二涉及不同的进程，不妨设方法一中有Pjk进程，而方法二中没有，则将Pjk进程补到方法二最后一个进程后。方法一在处理Pjk进程时仅回收了Pj1、Pj2、Pjk-1的资源，而方法二已回收了除Pjk外Pj1、Pj2、Pjm的资源，故有足够资源供Pjk完成，因此方法二不是不可简化图，与已知矛盾。不同的简化方法涉及的进程相同，顺序可能不同，故得到相同的不可简化图。,若资源分配图可完全简化，则必然存在一个简化顺序P1、P2、Pn，该顺序即为进程能够顺序执行完毕的一种方法。故存在死锁时，资源分配图是不可完全简化的。同理，当进程能够顺序执行完毕时，必然存在一个执行顺序P1、P2、Pn，该顺序即为资源分配图的完全简化顺序。故若资源分配图是不可完全简化的，则存在死锁。,将空集以及对应的代价0作为第一个元素放入队列中循环执行取队列首个元素A若终止A中进程可解除死锁状态，则退出循环，A包含的进程为需终止进程，对应最小代价分别在A中添加一个不在A中的其他进程，计算代价，并根据代价大小，与队列中已有的元素按从小到大的顺序排序，重新放入队列中,