处理机调度与死锁(师范学校教授的课件)

null计算机操作系统 计算机操作系统 第3章 处理机调度与死锁第3章 处理机调度与死锁 在多道程序环境下，一个作业从提交到执行，通常都要经历多级调度，如高级调度、低级调度、中级调度等。而系统的运行性能在很大程度上取决于调度，因此调度便成为多道程序的关键。 在多道程序环境下，由于多个进程的并发执行，改善了系统资源的利用率并提高了系统的处理能力，然而，多个进程的并发执行也带来了新的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ----死锁。第3章 处理机调度与死锁第3章 处理机调度与死锁3.1-3.2处理机调度的基本概念 3.3调度算法 3.4实时调度 3.5产生死锁的原因和必要条件 3.6预防死锁的方法 3.7死锁的检测与解除3.1 处理机调度的基本概念3.1 处理机调度的基本概念 一、调度的层次 二、调度队列模型 三、选择调度方式和算法的若干准则返回目录一、调度的层次提交输入管理系统作业调度SPOOLING 输出后备退出完成就绪阻塞交换调度进程调度（线程调度）一、调度的层次一、调度的层次一、调度的层次1、高级调度（长程/作业/宏观调度） （1）从外存后备队列中选择作业进入就绪队列或挂起就绪. （2）在批处理系统中,大多配有作业调度,但在分时系统及实时系统中,一般不配置. （3）作业调度执行频率很低,通常为几分钟一次,甚至更久。作业的相关概念作业的相关概念作业是用户交给计算机的具有独立功能的任务。 在联机系统中，从用户登录系统到用户退出系统的整个过程，可以多次形成作业，用户每输入一条命令或运行一段程序都代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 着一个作业步。 作业在系统中也是动态的，从作业产生到作业消失的整个过程中，作业的状态跟随系统的运作而发生变化。作业的状态(1)作业的状态(1)作业被分为四种状态 (1)提交状态：当用户正在通过输入设备向计算机提交作业时，作业处于提交状态。 处于提交状态的作业，因为它的信息尚未全部进入系统，故不能被调度程序选中。 (2)后备状态：当用户完成作业的提交，作业已存在于辅助存储器中，则在它还未被调度去执行前，称该作业处于后备状态。 处于后备状态的作业具有完整的作业描述信息 处于后备状态的作业有资格进入主存储器，但何时进入主存储器，还需要看有否这样的时机.作业的状态(2)作业的状态(2)(3)执行状态：作业被调度进入主存储器，并以进程的形式存在，其状态就是执行状态。 处于执行状态的作业并不意味着一定在CPU上运行，是否运行依赖于进程控制。 处于执行状态的作业可以有多个。 (4)停止状态：当作业已经完成其指定的功能，等待着与之相关的进程、资源，及其他描述信息的撤消，作业便进入停止状态。 一、调度的层次一、调度的层次高级调度需解决的问题 （1）接纳作业数（内存驻留数） 即多道程序的“道或度” 太多，则可能会影响系统的服务质量（如周转时间太长） 太少，又将导致系统资源利用率和吞吐量的下降 应根据系统的规模和运行速度来确定，同时要求I/O型进程与CPU型进程中和调度 （2）接纳策略(应将哪些作业从外存调入内存) 取决于采用何种调度算法(先来先服务、短作业优先等)一、调度的层次进程调度任务 ①保存处理机的现场信息：在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等。 ②按某种算法选取进程：调度程序按某种算法，从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分配给它。 ③把处理器分配给进程：由分派程序把处理器分配给该进程。此时需要将选中进程的进程控制块内有关处理机现场的信息，装入处理器相应的各个寄存器中，把处理器的控制权交予该进程，让它从上次的断点处恢复运行。一、调度的层次2、低级调度（短程/CPU/进程/微观调度）2、低级调度（短程/CPU/进程/微观调度）进程调度机制 ⑴排队器：事先将系统中的所有就绪进程，按照一定的策略，排成一个或多个队列。以便调度程序能最快地找到它。以后每当有一个进程转变为就绪状态时，排队器便将它插入到相应的就绪队列。2、低级调度（短程/CPU/进程/微观调度）一、调度的层次 ⑵分派器：依据进程调度程序所选定的进程，将其从就绪队列中取出，然后进行进程间的上下文切换，将处理机分配给新选出的进程。一、调度的层次 ⑶上下文切换器：在对处理机进行切换时，会发生： ①第一对上下文切换时，OS将保存当前进程的上下文，装入分派程序的上下文，以便分派程序运行； ②第二对上下文切换是移出分派程序的上下文，装入新选进程上下文。一、调度的层次2、低级调度（短程/CPU/进程/微观调度）进程调度机制null进程调度机制一、调度的层次一、调度的层次2、低级调度（短程/CPU/进程/微观调度）进程调度方式 非抢占方式：一旦把处理机分配给某进程后，便让该进程一直执行，直到该进程完成或因某事件而被阻塞，才再把处理机分配给其它进程，决不允许某进程抢占已分配出去的处理机。 实现简单，系统开销小，常用于批处理系统。 实时性差，不利于处理紧急任务，故实时、分时系统不宜采用。一、调度的层次一、调度的层次2、低级调度（短程/CPU/进程/微观调度）抢占方式: 允许调度程序根据某种原则（时间片、优先权、短进程优先），停止正在执行的进程，而将处理机重新分配给另一进程。 有利于处理紧急任务，故实时与分时系统中常采用。★ “抢占” 必须遵循的原则 ①优先权原则 ②短进程优先原则 ③时间片原则一、调度的层次返回本节一、调度的层次3、中级调度（中程/交换调度） 在内存和外存对换区之间按照给定的原则和策略选择进程对换，以解决内存紧张问题，从而提高内存的利用率和系统吞吐量，常用于分时系统或具有虚拟存储器的系统中。二、调度队列模型二、调度队列模型 在OS中的任何一种调度中，都将涉及到进程队列，由此形成了三种类型的调度队列模型。 1.仅有进程调度的调度队列模型 2.具有高级和低级调度的调度队列模型 3.同时具有三级调度的调度队列模型返回本节1、仅有进程调度的调度队列模型1、仅有进程调度的调度队列模型进程调度时间片完返回2、具有高级和低级调度的调度队列模型2、具有高级和低级调度的调度队列模型时间片完……返回3、同时具有三级调度的调度队列模型3、同时具有三级调度的调度队列模型时间片完进程调度CPU进程完成等待事件作业调度中程调度返回三、选择调度方式和算法的若干准则三、选择调度方式和算法的若干准则面向用户的准则 周转时间短 响应时间快 截止时间的保证 优先权准则 面向系统的准则 系统吞吐量 处理机利用率好 各类资源平衡利用最优准则 最大的CPU利用率 最大的吞吐量 最短的周转时间 最短的等待时间 最短的响应时间 返回本节三、选择调度方式和算法的若干准则三、选择调度方式和算法的若干准则周转时间（常用于批处理系统） 定义：作业从提交――> 完成的时间 时间组成： （1）驻外等待调度时间 （2）驻内等待调度时间 （3）执行时间 （4）阻塞时间周转时间不具有区分实际运行时间长短的性质。 三、选择调度方式和算法的若干准则三、选择调度方式和算法的若干准则返回平均周转时间 带权周转时间 平均带权周转时间平均周转时间可以衡量不同调度算法对相同任务流的调度性能。带权周转时间衡量长短任务的差别，故带权周转时间W越小越好三、选择调度方式和算法的若干准则三、选择调度方式和算法的若干准则返回响应时间快（对交互性作业） 概念：键盘提交请求到首次响应时间 时间组成 （1）输入传送时间 （2）处理时间 （3）响应传送时间 截止时间的保证（特别用于实时系统） 优先权准则（即需要抢占调度）3.3 调度算法3.3 调度算法根据系统的资源分配策略所规定的资源分配算法一、先来先服务调度算法 二、短作业/进程优先调度算法 三、时间片轮转调度算法 四、优先权调度算法 五、高响应比优先调度算法 六、多级反馈队列调度算法一、先来先服务（FCFS）调度算法一、先来先服务（FCFS）调度算法基本思想: 对于作业调度：从后备作业队列中（按进入的时间顺序排队）选择队首一个或几个作业，调入内存，创建进程，放入就绪队列。 对于进程调度：从就绪队列中选择一个最先进入队列的进程，将CPU分配于它。一、先来先服务（FCFS）调度算法一、先来先服务（FCFS）调度算法例1： 作业名 到达时间 服务时间 A 0 1 B 1 100 C 2 1 D 3 100null完成时间-到达时间开始时间+服务时间上一个进程的完成时间1 101 100 1101 102 100 100 102 202 199 1.99一、先来先服务（FCFS）调度算法一、先来先服务（FCFS）调度算法例2：下面三个作业几乎同时到达系统并立即进行FCFS调度： 作业名 所需CPU时间 作业1 28 作业2 9 作业3 3 假设提交顺序为1、2、3，则平均作业周转时间T = 若提交顺序改为作业2、1、3，则T= 若提交顺序改为作业3、2、1，则T= FCFS调度算法的平均作业周转时间与作业提交的顺序有关。(28+37+40)/3 = 352918一、先来先服务（FCFS）调度算法一、先来先服务（FCFS）调度算法FCFS调度算法评价简单，但效率不高。 有利于长作业（进程）不利于短作业（进程）。 有时为了等待长作业的执行，而使短作业的周转时间变得很大，从而平均周转时间也变大。 现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中。但它常被结合在其它调度策略中使用。二、短作业/进程优先调度算法二、短作业/进程优先调度算法短作业优先调度算法（SJF） 从后备队列中选择一个或若干个估计运行时间 最短的作业，将它们调入内存运行。短进程优先调度算法（SPF） 从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它。 可采用抢占或者非抢占调度方式。SJF/SPF__非抢占式举例执行顺序：SJF/SPF__非抢占式举例A033103ABCDE24686452B3971.1791131.51115112.751520142.8ECD7.61.84nullFCFS：A→B→C→D→E SJF: A→D→B→E→CFCFS和的SJF比较二、短作业/进程优先调度算法二、短作业/进程优先调度算法 优点： 1）能有效降低作业/进程的平均等待时间； 2）提高吞吐量； 3）能有效缩短作业/进程的周转时间； 缺点： 1）对长作业/进程不利； 2）不考虑作业/进程的紧迫程度； 3）作业执行时间仅为估计*；课堂练习课堂练习练习：有如下四个进程，它们的到达时间和服务时间如下所示，请分别计算在采用FCFS、SPF非抢占调度算法时的平均周转时间和平均等待时间。 进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4课堂练习 进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4 FCFS 平均周转时间= ((7-0)+(11-2)+(12-4)+(16-5))/4=8.75 平均等待时间 = (0+(7-2)+(11-4)+(12-5))/4 =4.75课堂练习课堂练习课堂练习 进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4 SPF 平均周转时间= ((7-0)+(12-2)+(8-4)+(16-5))/4=8 平均等待时间= ((0-0)+(8-2)+(7-4)+(12-5))/4 = 4SPF与FCFS的比较SPF与FCFS的比较三、时间片轮转调度算法Round Robin三、时间片轮转调度算法Round Robin 轮转法是一种基于时钟的抢占策略，以一个周期性间隔产生的时钟中断依次进行各个进程的调度。 当时钟中断发生时，当前正在运行的进程被置于就绪队列中，然后再基于FCFS策略选择下一个就绪进程运行。 它主要用于分时系统中。轮转法 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 的问题是时间片的长度。举例举例例：一个分时OS，10个终端，时间片100ms，每个用户的请求进程要300ms的时间处理，问终端用户提出二次请求的时间间隔最少是多少？ 解：响应时间＝100ms×10＝1s，每个用户的请求要获得3个时间片才能处理完，要轮转3次，才能都处理完，所以终端用户的二次请求时间间隔最少应为3s。三、时间片轮转调度算法RR—注：三、时间片轮转调度算法RR—注：保证了就绪队列中的所有进程在给定的时间内，均能获得一时间片来执行。 若进程的执行时间少于时间片，则自愿释放CPU。 时间片将影响： 调度算法（太长---FCFS）； 上下文切换（太短---上下文切换频繁）； 平均周转时间。短时间片增加上下文切换频率短时间片增加上下文切换频率周转时间随时间片变化周转时间随时间片变化从图中可以看出，这组进程的平均周转时间并未随时间片的增加而得到改进。一般来说，如果在单个时间片内多数进程能够完成它们的运行工作，则平均周转时间会得到改善。三、时间片轮转调度算法—例(1)三、时间片轮转调度算法—例(1)EG： 进程 到达时间 服务时间 P1 0 7 P2 2 4 P3 4 1 P4 5 4 RR（时间片为4） P1P20 4 5 6 7 8 9 10 11 12 13 14 15 16P1P3P4平均周转时间 =((16-0)+(8-2)+(9-4)+(13-5))/4 =8.75 平均等待时间=(9+2+4+4)/4 = 4.75四、优先权调度算法（HPF）四、优先权调度算法（HPF）HPF(Highest-Priority-First) 需为每个进程设置一个由数字表示的优先数。 进程优先数的大小应与进程所对应事件的紧迫程度相对应。 当需要进行处理机分配时，系统在可运行的进程中选择优先数最高者使其投入运行。 进程的优先数反映了进程运行的优先级别，故又将其称作优先级算法。思考：优先数如何存放？PCB优先权的类型优先权的类型（1）静态优先级 优先权在创建进程时确定，且在进程的整个运行期间保持不变。一般用整数表示，小表示优先级高。 确定原则： 进程类型（系统进程／用户进程） 进程对资源的需求（是否是珍贵资源） 用户要求（紧急程度和付费情况） 优点：简单、开销较少 缺点：公平性差（对低优先数进程）优先权的类型优先权的类型（2）动态优先权 动态优先级在进程的存在过程中不断发生变化。 动态优先级的变化取决于： 进程的等待时间 进程的运行时间 进程使用资源的类型等 此优先数确定方法资源利用率高，公平性好，但开销较大，实现较为复杂。 最高响应比优先算法采用动态优先级。四、优先权调度算法(续)四、优先权调度算法(续)非抢占式优先权算法：系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直到完成或因发生某事件而放弃处理机时，系统方可重新分配处理机。非抢占式优先权算法—例1非抢占式优先权算法—例1EG1： 进程 到达时间 服务时间 优先数 P1 0 7 3 P2 2 4 2 P3 4 1 4 P4 5 4 1 Gantt图 平均周转时间 =((7-0)+(15-2)+(16-4)+(11-5))/4=9.5 平均等待时间=(0+9+11+2)/4 = 5.5优先数越小优先级越高四、优先权调度算法(续)四、优先权调度算法(续)抢占式优先权算法：系统把处理机分配给就绪队列中优先权最高的进程，使之执行。但在其执行期间，只要出现了另一个优先权更高的进程，进程调度程序就立即停止当前进程的执行，重新将处理机分配给新到的优先权最高的进程。抢占式优先权算法—例2抢占式优先权算法—例2EG2： 进程 到达时间 服务时间 优先数 P1 0 7 3 P2 2 4 2 P3 4 1 4 P4 5 4 1 Gantt图 平均周转时间 =((15-0)+(10-2)+(16-4)+(9-5))/4=9.75 平均等待时间=(8+4+11+0)/4 = 5.75各种算法结果值的比较各种算法结果值的比较返回五、高响应比优先权调度算法HRP五、高响应比优先权调度算法HRP优先权的变化为 如等待时间相同,则要求服务时间愈短,其优先权愈高--SPF. 如要求服务时间相同,优先权决定于等待时间----FCFS。 对长作业,若等待时间足够长，优先权也高，也能获得CPU。算法HRP示例算法HRP示例 HRP 的调度性能 =2.14039151339132015TA=3TB=7TC=9TD=14TE=7=8.008364522046ABCDE→→→→WE=3.50WA=1WB=1.17WC=2.25WD=2.80ECDAB周转时间T=结束时间Tc-到达时间Tin=3-0=3周转时间 T带权周转时间W=周转时间T/服务时间Tr=3/3=1带权周转时 间W平均=[(9-4)+4]/4=2.25=[(9-6)+5]/5=1.6=[(9-8)+2]/2=1.5RCRDRERD=[(13-6)+5]/5=2.4RE=[(13-8)+2]/2=3.5五、高响应比优先权调度算法HRP五、高响应比优先权调度算法HRP不同调度算法对同一个 作业/进程的性能分析:返回六、多级反馈队列调度算法MFQ六、多级反馈队列调度算法MFQ就绪队列1（8ms）就绪队列2（16ms）就绪队列3（32ms）就绪队列n（FCFS）多级反馈队列调度处理机终止┇七、多级反馈队列调度算法MFQ七、多级反馈队列调度算法MFQ设置多个就绪队列，并为每个队列赋予不同的优先级。队列1的优先级最高，其余队列逐个降低。 每个队列中进程执行时间片的大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。七、多级反馈队列调度算法MFQ七、多级反馈队列调度算法MFQ 当一个新进程进入系统时，首先将它放入队列1的末尾，按FCFS等待调度。如能完成，便可准备撤离系统，反之由调度程序将其转入队列2的末尾，按FCFS再次等待调度，如此下去，进入队列n按RR算法调度执行。 仅当队列1为空时，才调度队列2中的进程运行。若队列I中的进程正执行，此时有新进程进入优先级较高的队列中，则新进程将抢占运行。原进程转移至下一队列。七、多级反馈队列调度算法MFQ七、多级反馈队列调度算法MFQ多级反馈队列算法有如下特点：短优先。 输入/输出进程优先。 运算型进程有较长的时间片。 采用了动态优先级。 采用了可变时间片。返回null各种常用调度算法的比较返回3.3 实时系统中的调度3.3 实时系统中的调度在一个实时系统中，时间起着非常重要的作用，即每一个实时进程或任务都有一个时间约束要求。在一个实时应用系统，可能有多个实时进程或任务，每个实时任务都有其时间约束，所以需一种新的调度算法来合理地安排这些实时任务的执行次序，使它们能满足各个实时任务的的时间约束条件-----实时调度。满足实时任务各自时间约束条件的调度称为 实时调度一、实现实时调度的基本条件 提供必要的信息 就绪时间；成为就绪状态起始时间（PCB中）。在周期任务情况下，它就是预知的一串时间序列。 开始截止时间和完成截止时间。 处理时间；指任务从开始执行到完成所需时间 资源要求；任务开始执行时所需的一组资源 优先级；如果任务开始截止时间已经错过，就会引起故障，因而应为该任务赋予绝对优先级，供调度程序参考。 一、实现实时调度的基本条件一、实现实时调度的基本条件一、实现实时调度的基本条件 系统处理能力 实时系统通常都有多个实时任务，假定系统中有 m 个周期性的硬实时任务；单处理机下，满足上面限制条件才是可调度的。 5个硬实时任务，周期都是40ms，处理时间为 10ms，则有： 系统不可调度！一、实现实时调度的基本条件一、实现实时调度的基本条件提高系统处理能力途径有两个： 对单处理机系统须增强其处理能力，以减少每个任务处理时间（如增强速度，使10ms减少为8ms）。 采用多处理机系统。假定系统中处理机数为N，则应将上述的限制条件改为： 系统处理能力 一、实现实时调度的基本条件 采用抢占式调度机制 硬实时任务广泛采用抢占机制。问题是这样的调度机制是比较复杂和开销大的。 具有快速切换机制 对外部中断的快速响应能力；要求系统具有快速硬件中断机构（一般没有问题，可以作到）。 快速任务分派能力；在完成任务调度后，就应进行任务切换，应使任务切换时间开销尽可能小。 一、实现实时调度的基本条件二、实时调度算法的分类按调度方式 非抢占式调度算法 非抢占式轮转调度算法：用于工业生产的群控系统中。 非抢占式优先调度算法：用于有一定时间要求的实时控制系统之中。 抢占式调度算法 （按抢占发生的时间） 基于时钟中断抢占的优先权调度算法 立即抢占的优先权调度算法二、实时调度算法的分类null按调度方式分类三、常用的几种实时调度算法三、常用的几种实时调度算法 根据确定优先级方式不同而有形成以下几种实时调度算法。 最早截止时间优先（EDF） 根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。算法要求在系统中保持一个实时任务就绪队列，该队列按任务截止时间的早晚排序。null 任务1任务执行→ 任务到达→任务1t任务3任务4任务2任务2任务3任务4开始截止时间：最早截止时间优先（EDF） 该算法是根据任务的截止时间确定任务的优先级，具有最早截止时间的任务排在队列的前面。 抢占式调度方式用于非周期实时任务 null最早截止时间优先（EDF） 抢占式调度方式用于周期实时任务三、常用的几种实时调度算法 最低松弛度优先（LLF） 三、常用的几种实时调度算法 根据任务紧急（或松弛）程度来确定任务的优先级。任务紧迫程度愈高，所赋予优先级愈高。 例如，一个任务在200ms时必须完成，而它本身运行时间需要100ms，因此，调度程序必须在100 ms之前调度执行（松弛程度为100ms）。 松弛度=必须完成的时间点 - 本身所需运行时间 - 当前时间:null假如一个实时系统中有两个周期性实时任务，A和B，任务A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间25ms。 图给出了A和 B截止的时间点。 最低松弛度优先（LLF） null松弛度=必须完成的时间点 - 本身所需运行时间 - 当前时间:A1(10)B1(20) 0 10 20 30 40 50 60 70 80 90 100 t1 t2 t3 t4 t5 t6 t7 t8 t 利用LLF算法对两个周期性实时任务进行调度A2(10)A3(10)A4(10)B1(5)B2(15)B2(10)初始：t=0时刻，计算A，B松弛度：A1= 20 – 10 – 0 = 10B1= 50 – 25 – 0 = 25t=10时刻，计算A，B松弛度：A2= 40 – 10 – 10 = 20B1= 50 – 25 – 10 = 15t=30时刻，计算A，B松弛度：A2= 40 – 10 – 30 = 0B1= 50 – 5 – 30 = 15t=40时刻，计算A，B松弛度：A3= 60 – 10 – 40 = 10B1= 50 – 5 – 40 = 5t=45时刻，计算A，B松弛度：A3= 60 – 10 – 45 = 5B2= 100 –25 – 45 = 30t=55时刻，计算A，B松弛度：A4= 80 – 10 – 55 = 35B2= 100 –25 – 55 = 20t=70时刻，计算A，B松弛度：A4= 80 – 10 – 70 = 0B2= 100 –10 – 70 = 20t=80时刻，计算A，B松弛度：A5= 100 – 10 – 80 = 10B2= 100 – 10 – 80 = 10●●最低松弛度优先（LLF） 返回目录3.5 死锁的基本概念3.5 死锁的基本概念 例：设有一台输入机和一台输出机，进程P1和P2需要使用这两个资源。设两个进程的活动分别为： P1的活动： ……… 申请输入机 ……… 申请输出机 ……… 释放输出机 ………… 释放输入机P2的活动： ……… 申请输出机 ……… 申请输入机 ……… 释放输入机 ………… 释放输出机P1与P2均因得不到资源而无法继续向前推进，这种由于进程竞争资源而引起的僵持称为死锁。3.5 死锁的基本概念3.5 死锁的基本概念一、死锁 二、产生死锁的原因 三、产生死锁的必要条件 四、处理死锁的基本方法返回目录一、死锁一、死锁 指多个进程在运行过程中因争夺资源而造成的一种僵局（deadly-Embrace)，若无外力作用，这些进程都将无法向前推进。 如图 注意： （1）参与死锁的进程数至少为2 （2）参与死锁的所有进程均等待资源 （3）参与死锁的进程至少有两个占有资源 （4）参与死锁的进程是系统中当前正在运行进程的一部分。返回二、产生死锁的原因二、产生死锁的原因根据使用方式：共享资源和独享资源。 根据使用期限；永久资源和临时性资源。根据资源性质：二、产生死锁的原因二、产生死锁的原因 竞争资源 竞争非剥夺性资源 竞争临时性资源顺序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）； …二、产生死锁的原因进程P1、P2并发执行。 资源R1、R2曲线4将进入不安全区域（进程推进顺序非法）二、产生死锁的原因 进程间推进顺序非法返回三、产生死锁的必要条件三、产生死锁的必要条件 产生死 锁 必须具备以下四个条件，这四个条件是Coffman首先提出的，所以称为Coffman 条件： 互斥条件（资源独占条件） 请求和保持条件（部分分配条件） 不剥夺条件 循环等待条件（环路条件）返回四、处理死锁的基本方法四、处理死锁的基本方法不让死锁发生 预防死锁（静态策略） 避免死锁（动态策略） 让死锁发生 检测死锁 解除死锁四、处理死锁的基本方法四、处理死锁的基本方法鸵鸟算法：指像鸵鸟一样对死锁视而不见，即不理睬死锁。 预防死锁：指通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。 避免死锁：指在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。 检测死锁：允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当 措施 《全国民用建筑工程设计技术措施》规划•建筑•景观全国民用建筑工程设计技术措施》规划•建筑•景观软件质量保证措施下载工地伤害及预防措施下载关于贯彻落实的具体措施 加以清除。 解除死锁：当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。返回3.6 死锁的预防和避免方法通过破坏死锁的四个必要条件中的一个或多个以确保系统绝不会产生死锁。 1．互斥条件 ：无法破环，资源本身固有特性限制 2．破坏请求和保持条件 ：采用预先分配的策略 3．破坏循环等待条件：采用有序分配的策略 4．破坏非剥夺条件 ：可以收回已分给进程且尚未使用完毕的资源。采用策略 一、死锁的预防3.6 死锁的预防和避免方法null预先分配策略 系统要求任一进程必须预先申请它所需的全部资源，而且仅当该进程的全部资源要求能得到满足时，系统才能给予一次性分配，然后启动该进程运行，但是在分配时只要由一种资源不满足，系统就不会给进程分配资源。进程运行期间，不会再请求新的资源。 缺点：资源严重浪费 进程延迟进行null有序分配策略 把系统中所有资源编号，进程在申请资源时必须按资源编号的递增次序进行，否则操作系统不予分配 null优点：资源利用率和系统吞吐量与另两种方法相比有较明显的改善。 缺点： 1 为系统中各种类型的资源所分配的序号必须相对稳定，这就限制了新设备类型的增加； 2 作业实际使用资源的顺序与系统规定的顺序不同而造成资源的浪费； 3 限制了用户简单、自主地编程。 有序分配策略null破坏非剥夺条件采用的策略：一个已经保持了某些资源的进程，当它再提出新的资源要求而不能立即得到满足时，必须释放它已经保持的所有资源，待以后需要时再重新申请。 实现比较复杂，且要付出很大代价；此外，还因为反复地申请和释放资源，而使进程的执行无限地推迟，延长了周转时间，增加了系统的开销，降低了系统吞吐量。（例如打印机打印的结果不连续） 3.6 死锁的预防和避免方法3.6 死锁的预防和避免方法死锁的避免定义:系统运行过程中， 允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次资源分配的安全性。若此次分配不会导致系统进入不安全状态，则将资源分配给进程； 否则，令进程等待。 最具有代表性的避免死锁算法是银行家算法 : Banker’s Algorithm 。null 安全状态：如果系统能按某种顺序（如P4，P1，…,Pn, 称为安全序列）为每个进程分配其所需的资源，直至每个进程都能顺利地完成，称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。 安全状态一定是没有死锁发生的。二、系统的安全状态null 在死锁避免的方法中，允许进程动态申请资源，系统在进行资源分配之前，先计算资源分配的安全性，若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程等待。二、系统的安全状态安全、不安全、死锁状态空间安全、不安全、死锁状态空间基本事实 如果一个系统在安全状态，就没有死锁 如果一个系统处于不安全状态，就有可能死锁 避免死锁的实质：确保系统不进入不安全状态）安全状态实例安全状态实例假定系统中有三个进程P1，P2和P3，共有12台磁带机，三个进程对磁带机的需求和占有如下：T0时刻，存在一个安全序列（P2，P1，P3）或（ P2，P3，P1 ），所以系统是安全的。二、系统的安全状态null二、系统的安全状态 由安全状态向不安全状态的转换：如在T0以后，P3要求1台磁带机，若系统分给它一台，则系统进入不安全状态。 因为其余2台分给P2，P2完成后，只能释放4台，这既不能满足P1（5台），也不能满足P3（6台），将导致死锁。三、避免死锁的算法-银行家算法三、避免死锁的算法-银行家算法为实现银行家算法，系统中必须设置若干数据结构。假定系统中有n个进程（P1，P2，…，Pn），m类资源（R1，R2，…，Rm），银行家算法中使用的数据结构: 可利用资源向量:available[j]=k, 资源Rj类有k个可用 最大需求矩阵:Max[i,j]=k,进程Pi最大请求k个Rj类资源 分配矩阵：Allocation[i,j]=k,进程Pi分配到k个Rj类资源 需求矩阵：Need[i,j]=k,进程Pi还需要k个Rj类资源 三个矩阵的关系： Need [i,j] = Max[i,j] – Allocation [i,j].null ★银行家算法 设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1)如果Requesti［j］≤Need［i,j］，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2)如果Requesti［j］≤Available［j］，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。null ★银行家算法 (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等待。 null ★安全性算法 (1)设置两个向量：① 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work∶=Available; ② Finish: 它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish［i］∶=false; 当有足够资源分配给进程时， 再令Finish［i］∶=true。 (2)从进程集合中找到一个能满足下述条件的进程： ① Finish［i］=false; ② Need［i,j］≤Work［j］；若找到， 执行步骤(3)， 否则，执行步骤(4)。null ★安全性算法 (3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Work［j］∶=Work［i］+Allocation［i,j］; Finish［i］∶=true; go to step 2; (4)如果所有进程的Finish［i］=true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。 银行家算法的例子银行家算法的例子假定系统中有5个进程3类资源及数量分别为10、5、7，T0时刻的资源分配情况。银行家算法的例子（1） T0时刻的安全性T0时刻存在着一个安全序列 {P1 P3 P4 P2 P0}，故系统是安全的。银行家算法的例子(2) P1请求资源 Request1(1,0,2)执行银行家算法(2) P1请求资源 Request1(1,0,2)执行银行家算法银行家算法的例子P1请求资源时的资源分配表银行家算法的例子P1请求资源时的安全性检查表存在着一个安全序列{P1 P3 P4 P2 P0}，故系统是安全的，可以立即将P1所申请的资源分配给它。银行家算法的例子银行家算法的例子（3）P4请求资源Request4(3,3,0) P4发出请求向量Request4(3,3,0)，系统按银行家算法进行检查: 1) Request4(3,3,0)≤Need4 (4,3,1) 2) Request4 (3,3,0) > Available (2,3,0),表示资源不够,则让P4等待银行家算法的例子(4) P0请求资源 Request0(0,2,0)(4) P0请求资源 Request0(0,2,0)银行家算法的例子P0请求资源时的资源分配表Available＝(2,1,0) 不能满足任何进程需要，所以系统进入不安全状态，P0的请求不能分配返回目录3.7 死锁的检测和解除3.7 死锁的检测和解除 一、资源分配图 检测死锁的基本思想: 是在操作系统中保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。为此，将进程和资源间的申请和分配关系描述成一个有向图---资源分配图。3.7 死锁的检测和解除3.7 死锁的检测和解除 允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生 一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行一、资源分配图一、资源分配图 资源分配图又称进程-资源图，它描述了进程和资源间的申请和分配关系，该图是一个有向图进程有三个资源Pi 请求一个RjPi 持有一个Rj一、资源分配图一、资源分配图进程结点子集 P = {P1,P2,P3} 资源结点子集 R = {R1,R2,R3,R4} N=P ⋃ R ={P1,P2,P3}⋃{R1,R2,R3,R4} ={P1,P2,P3,R1,R2,R3,R4} E={(R2,P1),(R2,P2),(P1,R1),(R1,P2),(P2,R3),(R3,P3)}进程有三个资源Pi 请求一个RjPi 持有一个Rjnull二、死锁判定法则 (1)如果资源分配图中没有环路，则系统内 没有死锁。 (2)如果SRAG中有环路，且每类资源只有一个，则有环是系统存在死锁的必要充分条件。 (3)如果SRAG中有环路，但每类资源的个数不全为1，则可以利用对SRAG化简的方法，来检测系统是否存在死锁 null二、死锁判定法则 有环无死锁null二、死锁判定法则 有环有死锁资源分配图的化简资源分配图的化简（1）寻找一个即不阻塞又非孤立的进程结点Pi，若无则算法结束； （2）去除Pi的所有分配边和请求边，使Pi成为一个孤立节点； （3） 转步骤（1）。 若所有进程成为孤立结点，称该图是可完全简化的，否则称该图是不可完全简化的。二、死锁判定法则 nullnull该图是不可完全简化的二、死锁判定法则 S为死锁状态的充分必要条件是，当且仅当S状态的资源分配图是不可完全简化的。（死锁定理）二、死锁检测算法二、死锁检测算法基本思想 获得某时刻t系统中各类可利用资源的数目向量w(t),对于系统中的一组进程{ p1,p2, …,pn}，找出那些对各类资源请求数目均小于系统现有的各类可利用资源数目的进程。这样的进程可以获得它们所需要的全部资源并运行结束，当它们运行结束后释放所占有的全部资源，从而可用资源数目增加，将这样的进程加入到可运行结束的进程序列L中，然后对剩下的进程再作上述考查。如果一组进程{ p1,p2, …,pn}中有几个进程不属于序列L中，那么它们会发生死锁。二、死锁检测算法二、死锁检测算法类似于银行家算法中的数据结构： 可利用资源向量:available[j]=k, 资源Rj有k个可用 最大需求矩阵:Max[i,j]=k,进程Pi最大请求k个Rj资源 分配矩阵：Allocation[i,j]=k,进程Pj分配到k个Rj资源 需求矩阵：Need[i,j]=k,进程Pj还需要k个Rj资源 三个矩阵的关系： Need [i,j] = Max[i,j] – Allocation [i,j].检测算法**检测算法**1.让Work和Finish作为长度为m和n的向量 (a) Work := Available (b)For i = 1,2, …, n, if Allocationi  0, then Finish[i] := false;otherwise, Finish[i] := true. 2.找到下标i (a) Finish[i] = false (b) Requesti  Work 如果没有这样的i存在，转4 3.Work := Work + Allocationi Finish[i] := true go to step 2. 4.If Finish[i] = false, for some i, 1  i  n, then the system is in deadlock state. Moreover, if Finish[i] = false, then Pi is deadlocked.算法需要m x n2 的操作二、死锁检测算法三、死 锁 的 解 除三、死 锁 的 解 除常用解除死锁方法有两种: 资源剥夺法:当发现死锁后,从其它进程剥夺足够数量的资源给死锁进程,以解除死锁状态. 撤消进程法:采用强制手段从系统中撤消一个/一部分死锁进程,并剥夺这些进程的资源供其它死锁进程使用.返回目录