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