第4章调度与死锁 在多道程序环境下,进程数目往往多于处理机数目,致使它们争用处理机。这就要求系统 能按某种算法动态地把处理机分配给就绪队列中的一个进程,使之执行进程。分配处理机的任 务是由进程调度程序完成的。本章讨论进程调度与死锁问题及相关题解 4.1内容辅导 4.1.1处理机调度的基本概念 1.调度的类型 一个作业从提交开始直到完成,往往要经历下述三级调度 (1)作业调度又称宏观调度或高级调度。其主要任务是按一定的原则对外存上处于后 备状态的作业进行选择,给选中的作业分配内存、输入输出设备等必要的资源,并建立相应的 进程,以使该作业的进程获得竞争处理机的权利。一般在批处理系统中大多配有作业调度,而 在其他系统中通常不需配置作业调度。作业调度的执行频率较低,通常为几分钟一次 2)进程调度又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个 处于就绪状态的进程,将处理机分配给它。进程调度的运行频率很高,一般几十毫秒要运行 次。 (3)交换调度又称中级调度。其主要任务是按照给定的原则和策略,将处于外存对换区 中的重又具备运行条件的就绪进程调入内存,或将处于内存就绪状态或内存阻塞状态的进程 交换到外存对换区。交换调度主要涉及内存管理与扩充,因此在存储管理部分介绍 2.进程调度方式 所谓进程调度方式是指当某一进程正在处理机上执行时,若有某个更为重要或紧迫的进 程需要进行处理,即有优先权更高的进程进入就绪队列,此时应如何分配处理机。通常有两种 进程调度方式 (1)剥夺方式所谓剥夺调度方式是指当一个进程正在处理机上执行时,若有某个更为重要 或紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给这个更重要或紧 迫的进程。抢占的原则有 (1)优先权原则。就绪的高优先权进程有权抢占低优先权进程的CPU。 (2)短作业优先原则。就绪的短作业(进程)有权抢占长作业(进程)的CPU (3)时间片原则。一个时间片用完后,系统重新进行进程调度 (2)非剥夺方式这种方式是当某一进程正在处理机上执行时,即使有某个更为重要或紧 迫的进程进入就绪队列,仍然让正在执行的进程继续执行,直到该进程完成或发生某种事件而 进入完成或阻塞状态时,才把处理机分配给更为重要或紧迫的进程。 对不同的调度方式,相应的调度算法也不同,进程调度的核心问题就是采用什么算法将处 理机分配给进程 4.1.2处理机调度算法 1.先来先服务调度算法 这是一种最简单的调度算法,即按照进程进入就绪队列的先后次序来分配处理机。先来先 服务算法属于非剥夺的调度方式,一旦一个进程占有处理机,就一直运行下去,直到该进程完 成其工作或因等待某一事件而不能继续执行时才释放处理机。采用这种进程调度方式,若一个 运行时间长的作业先占有了处理机,则会使很多晚到的运行时间短的作业等待时间过长,引起 许多短作业用户的不满。因此这种方式很少被用作主要调度策略,但它常作为一种辅助调度算 法使用 (2)短作业(进程)优先(SJF/SPF算法
第 4 章 调度与死锁 在多道程序环境下,进程数目往往多于处理机数目,致使它们争用处理机。这就要求系统 能按某种算法动态地把处理机分配给就绪队列中的一个进程,使之执行进程。分配处理机的任 务是由进程调度程序完成的。本章讨论进程调度与死锁问题及相关题解。 4.1 内容辅导 4.1.1 处理机调度的基本概念 1.调度的类型 一个作业从提交开始直到完成,往往要经历下述三级调度: （1）作业调度 又称宏观调度或高级调度。其主要任务是按一定的原则对外存上处于后 备状态的作业进行选择,给选中的作业分配内存、输入输出设备等必要的资源,并建立相应的 进程,以使该作业的进程获得竞争处理机的权利。一般在批处理系统中大多配有作业调度,而 在其他系统中通常不需配置作业调度。作业调度的执行频率较低,通常为几分钟一次。 （2）进程调度 又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个 处于就绪状态的进程,将处理机分配给它。进程调度的运行频率很高,一般几十毫秒要运行一 次。 （3）交换调度 又称中级调度。其主要任务是按照给定的原则和策略,将处于外存对换区 中的重又具备运行条件的就绪进程调入内存,或将处于内存就绪状态或内存阻塞状态的进程 交换到外存对换区。交换调度主要涉及内存管理与扩充,因此在存储管理部分介绍。 2. 进程调度方式 所谓进程调度方式是指当某一进程正在处理机上执行时,若有某个更为重要或紧迫的进 程需要进行处理,即有优先权更高的进程进入就绪队列,此时应如何分配处理机。通常有两种 进程调度方式: （1）剥夺方式 所谓剥夺调度方式是指当一个进程正在处理机上执行时,若有某个更为重要 或紧迫的进程需要使用处理机,则立即暂停正在执行的进程,将处理机分配给这个更重要或紧 迫的进程。抢占的原则有: (1)优先权原则。就绪的高优先权进程有权抢占低优先权进程的 CPU。 (2)短作业优先原则。就绪的短作业(进程)有权抢占长作业(进程)的 CPU。 (3)时间片原则。一个时间片用完后,系统重新进行进程调度。 （2）非剥夺方式 这种方式是当某一进程正在处理机上执行时,即使有某个更为重要或紧 迫的进程进入就绪队列,仍然让正在执行的进程继续执行,直到该进程完成或发生某种事件而 进入完成或阻塞状态时,才把处理机分配给更为重要或紧迫的进程。 对不同的调度方式,相应的调度算法也不同,进程调度的核心问题就是采用什么算法将处 理机分配给进程。 4.1.2 处理机调度算法 1.先来先服务调度算法 这是一种最简单的调度算法,即按照进程进入就绪队列的先后次序来分配处理机。先来先 服务算法属于非剥夺的调度方式,一旦一个进程占有处理机,就一直运行下去,直到该进程完 成其工作或因等待某一事件而不能继续执行时才释放处理机。采用这种进程调度方式,若一个 运行时间长的作业先占有了处理机,则会使很多晚到的运行时间短的作业等待时间过长，引起 许多短作业用户的不满。因此这种方式很少被用作主要调度策略,但它常作为一种辅助调度算 法使用。 (2)短作业(进程)优先(SJF/SPF)算法
该算法是指短作业或短进程优先调度的算法。短进程优先调度算法是选择就绪队列中 估计运行时间最短的进程技入执行,它既可采用抢占方式,也可采用非抢占方式。抢占的 Sw算法通常也叫做最短剩余时间优先算法。SFF算法能有效地缩短作业的平均周转时间, 提高系统的吞吐量,但不利于长作业和紧迫作业的运行。由于估计的运行时间不一定准确, 因而它不一定能真正做到短作业优先。 (3)高响应比优先调度(HRRN算法 (4))最高优先权优先调度算法 这是一种最常用的进程调度算法,即把处理机分配给优先权最高的进程。进程的优先权用 于表示进程的重要性及运行的优先性,通常分为两种:静态优先权和动态优先权 静态优先权是在创建进程时确定的;确定之后在整个进程运行期间不再改变。确定静态优 先权的依据有进程的类型、进程所使用的资源、进程的估计运行时间等因素。进程所索取的 资源越多,估计的运行时间越长,进程的优先权越低。进程类型不同,优先权也不同,如联机用 户进程的优先权高于脱机用户进程的优先权 动态优先权是指在创建进程时,根据系统资源的使用情况和进程的当前特点确定一个优 先权,在进程运行过程中再根据情况的变化调整优先权。动态优先权一般根据进程占有CPU 时间的长短、进程等待CPU时间的长短等因素确定。占有处理机的时间愈长,则优先权越低: 等待时间越长,优先权越高 基于优先权的调度算法还可按调度方式不同分为非剥夺优先权调度算法和可剥夺优先权 调度算法。 (5)时间片轮转调度算法 在这种调度算法中,系统将所有就绪进程按到达时间的先后次序排成一个队列,进程调度 程序总是选择队列中的第一个进程执行,且仅能执行一个时间片。在使用完一个时间片后,即 使进程并未完成其运行,也必须将处理机交给下一个进程。 时间片的长短对计算机系统的影响很大。如果时间片大到让一个进程足以完成其全部工 作,这种算法就退化为先来先服务算法。若时间片很小,那么处理机在进程之间的转换工作过 于频繁,处理机真正用于运行用户程序的时间将减少。时间片长短的值应能使分时用户得到好 的响应时间。 (6)多级反馈队列调度算法 在采用多级反馈队列调度算法的系统中,调度算法的实施过程如下: 首先应设置多个就绪队列,并为各个队列赋予不同的优先权。第一个队列的优先权最高, 第二队列次之,其余队列的优先权逐个降低 其次,赋予各个队列中进程执行时间片的大小也各不相同,在优先权愈高的队列中,每个 进程的执行时间片就规定得愈小。例如,第i+1队列的时间片是第i队列时间片的两倍。 第三,当一个新进程进入内存后,首先将它放入第一队列的末尾,按先来先服务的原则排 队等待调度。当轮到该进程执行时,如能在该时间片内完成,便可准备撤离系统:如果它在 个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按先来先服务 原则等待调度执行:如果它在第二队列中运行一个时间片后仍未完成,再以同样方法将它转入 第三队列。如此下去,当一个长作业从第一队列降到最后一个队列后,在最后一个队列中使用 时间片轮转方式运行 第四,仅当第一队列空闲时,调度程序才调度第二队列中的进程运行:仅当第1至(i一1 队列均为空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时, 又有新进程进入优先权较高的队列,则此时新进程将抢占正在运行进程的处理机,即由调度程 序把正在执行进程放回第i队列末尾,重新将处理机分配给新进程 4.实时调度
该算法是指短作业或短进程优先调度的算法。短进程优先调度算法是选择就绪队列中 估计运行时间最短的进程技入执行,它既可采用抢占方式,也可采用非抢占方式。抢占的 SW 算法通常也叫做最短剩余时间优先算法。SPF 算法能有效地缩短作业的平均周转时间, 提高系统的吞吐量,但不利于长作业和紧迫作业的运行。由于估计的运行时间不一定准确, 因而它不一定能真正做到短作业优先。 （3）高晌应比优先调度(HRRN)算法 （4））最高优先权优先调度算法 这是一种最常用的进程调度算法,即把处理机分配给优先权最高的进程。进程的优先权用 于表示进程的重要性及运行的优先性,通常分为两种:静态优先权和动态优先权。 静态优先权是在创建进程时确定的;确定之后在整个进程运行期间不再改变。确定静态优 先权的依据有进程的类型、进程所使用的资源、进程的估计运行时间等因素。进程所索取的 资源越多,估计的运行时间越长,进程的优先权越低。进程类型不同,优先权也不同,如联机用 户进程的优先权高于脱机用户进程的优先权。 动态优先权是指在创建进程时,根据系统资源的使用情况和进程的当前特点确定一个优 先权,在进程运行过程中再根据情况的变化调整优先权。动态优先权一般根据进程占有 CPU 时间的长短、进程等待 CPU 时间的长短等因素确定。占有处理机的时间愈长,则优先权越低； 等待时间越长,优先权越高。 基于优先权的调度算法还可按调度方式不同分为非剥夺优先权调度算法和可剥夺优先权 调度算法。 （5）时间片轮转调度算法 在这种调度算法中,系统将所有就绪进程按到达时间的先后次序排成一个队列,进程调度 程序总是选择队列中的第一个进程执行,且仅能执行一个时间片。在使用完一个时间片后,即 使进程并未完成其运行,也必须将处理机交给下一个进程。 时间片的长短对计算机系统的影响很大。如果时间片大到让一个进程足以完成其全部工 作,这种算法就退化为先来先服务算法。若时间片很小,那么处理机在进程之间的转换工作过 于频繁,处理机真正用于运行用户程序的时间将减少。时间片长短的值应能使分时用户得到好 的响应时间。 （6）多级反馈队列调度算法 在采用多级反馈队列调度算法的系统中,调度算法的实施过程如下： 首先应设置多个就绪队列,并为各个队列赋予不同的优先权。第一个队列的优先权最高, 第二队列次之,其余队列的优先权逐个降低。 其次,赋予各个队列中进程执行时间片的大小也各不相同,在优先权愈高的队列中,每个 进程的执行时间片就规定得愈小。例如,第 i+1 队列的时间片是第 i 队列时间片的两倍。 第三,当一个新进程进入内存后,首先将它放入第一队列的末尾,按先来先服务的原则排 队等待调度。当轮到该进程执行时,如能在该时间片内完成,便可准备撤离系统；如果它在一 个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按先来先服务 原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成,再以同样方法将它转入 第三队列。如此下去,当一个长作业从第一队列降到最后一个队列后,在最后一个队列中使用 时间片轮转方式运行。 第四,仅当第一队列空闲时,调度程序才调度第二队列中的进程运行:仅当第 1 至(i 一 1〉 队列均为空时,才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时, 又有新进程进入优先权较高的队列,则此时新进程将抢占正在运行进程的处理机,即由调度程 序把正在执行进程放回第 i 队列末尾,重新将处理机分配给新进程。 4.实时调度
实时系统中的任务通常都联系着一个截止时间,实时调度的关键是保证满足实时任务 对截止时间的要求 为了保证满足实时任务对截止时间的要求,实时系统必须具备足够强的处理能力和快速 的切换机制。通常,在提交实时任务时,系统将该任务的截止时间、所需的处理时间、资源要 求和优先级等信息一起提交给调度程序。若系统能及时处理该任务,调度程序便将它接收下来, 否则,将拒绝接收该任务。 对不同的实时系统,其调度方式和算法的选择也各不相同。在一些小型实时系统或要求不 太严格的实时控制系统中,常采用简单易行的非抢占式轮转调度方式,它可获得数秒至数十秒 的响应时间:而在有一定要求的实时控制系统中,可采用非抢占式优先权调度算法,它可获得 仅为数秒至数百毫秒级的响应时间。在要求比较严格(响应时间为数十毫秒以下)的实时系统 中,应采用比较复杂的抢占调度方式,其中,基于时钟中断的抢占式优先权调度算法,可获得几 十毫秒至几毫秒的响应时间,适用于大多数的实时系统:丽立即抢占的优先权调度算法,可将 响应时间降到几毫秒至1∞微秒,甚至更低,适用于要求更严格的实时系统。下面将介绍两种 常用的高优先权优先的实时调度算法 (1)最早截止时间优先CEDE币算法:该算法根据任务的开始截止时间来确定任务的优先级, 即任务的开始截止时间愈早,其优先级愈高。在实现该算法时,要求系统中保持一个实时任务就 绪队列,该队列按各任务的截止时间的早晚排序。EDF算法即可采用非抢占调度方式,也可采 用抢占调度方式。在采用抢占调度方式时,如果新到达的任务的开始截止时间比正在执行的任 务早,则它将立即抢占CP (2)最低松弛度优先(LF)算法。LIF算法根据实时任务的松弛度(松弛度=任务必须完成的 时间一任务本身的运行时间一当前时间)来确定任务的优先权,即任务的松弛度愈低,其优先 权愈高。在实现该算法时,要求系统中有一个按松弛度排序的实时任务就绪队列。 该算法主要用于可抢占调度方式中,当一任务的最低松弛度减为0时,它便必须立即抢占 CPU,以保证按截止时间的要求完成任务。 5.多处理机系统中的调度 1.进程分配方式 在对称多处理器系统(SMPS)中,各处理器单元在功能和结构上都是相同的,因而可把所有 的处理器作为一个处理器池?并将进程分配到其中的任干处理器上运行。在进行进程分配时, 可采用静态和动态两种分配方式。采用静态分配方式时,一个进程从开始执行直至其完成,都 被固定分配到一个处理器上去执行,此时,需要为每个处理器维护一个专用的就绪队列。静态 分配方式的优点是调度的开销小,缺点是会使处理器的忙闲不均。采用动态分配方式时,系统 中设置有二个公用的就绪队列,所有的就绪进程都被放在该队列中,然后被随机地调度到任 空闲的处理器上去执行,因此,在一个进程生命周期的不同时刻,它可以在不同的处理器上执 行,对松散祸合的多处理器系统,此时需要进行进程现场信息的转移,会明显增加调度开销,但 动态分配方式能较好地消除处理器忙闲不均的现象。 在配置有多种类型处理器单元的非对称多处理器系统中,常采用主一从式结构,即操作系 统的核心驻留在某个特定的处理器(即主处理器)上,而其他的处理器(即从处理器)只用于执 行用户程序。进程调度由主处理器执行,从处理器空闲时,便向主处理器发一索求进程的信号 并由主处理器从自己的就绪队列中摘下一个进程分配给请求的从处理器。这种方式的优点是 系统处理简单,缺点是主处理器的故障会导致整个系统瘫痪,而且主处理器容易成为系统瓶 2.进程(线程)调度方式 在多处理机系统中,常用的进程(线程)调度方式主要有 (1)自调度方式。一它是指在系统中设置一个公用的进程(或线程)队列,所有的处理器在空
实时系统中的任务通常都联系着一个截止时间,实时调度的关键是保证满足实时任务: 对截止时间的要求。 为了保证满足实时任务对截止时间的要求,实时系统必须具备足够强的处理能力和快速 的切换机制。通常,在提交实时任务时,系统将该任务的截止时间、所需的处理时间、资源要 求和优先级等信息一起提交给调度程序。若系统能及时处理该任务,调度程序便将它接收下来, 否则,将拒绝接收该任务。 对不同的实时系统,其调度方式和算法的选择也各不相同。在一些小型实时系统或要求不 太严格的实时控制系统中,常采用简单易行的非抢占式轮转调度方式,它可获得数秒至数十秒 的响应时间:而在有一定要求的实时控制系统中,可采用非抢占式优先权调度算法,它可获得 仅为数秒至数百毫秒级的响应时间。在要求比较严格(响应时间为数十毫秒以下)的实时系统 中,应采用比较复杂的抢占调度方式,其中,基于时钟中断的抢占式优先权调度算法,可获得几 十毫秒至几毫秒的响应时间,适用于大多数的实时系统:丽立即抢占的优先权调度算法,可将 响应时间降到几毫秒至 1∞微秒,甚至更低,适用于要求更严格的实时系统。下面将介绍两种 常用的高优先权优先的实时调度算法。 (1)最早截止时间优先 CEDE 币算法：该算法根据任务的开始截止时间来确定任务的优先级, 即任务的开始截止时间愈早,其优先级愈高。在实现该算法时,要求系统中保持-个实时任务就 绪队列,该队列按各任务的截止时间的早晚排序。EDF 算法即可采用非抢占调度方式,也可采 用抢占调度方式。在采用抢占调度方式时,如果新到达的任务的开始截止时间比正在执行的任 务早,则它将立即抢占 CPU。: (2)最低松弛度优先(LLF)算法。LIF 算法根据实时任务的松弛度(松弛度=任务必须完成的 时间一任务本身的运行时间一当前时间)来确定任务的优先权,即任务的松弛度愈低,其优先 权愈高。在实现该算法时,要求系统中有一个按松弛度排序的实时任务就绪队列。 该算法主要用于可抢占调度方式中,当一任务的最低松弛度减为 0 时,它便必须立即抢占 CPU,以保证按截止时间的要求完成任务。 5.多处理机系统中的调度 1.进程分配方式 在对称多处理器系统(SMPS)中,各处理器单元在功能和结构上都是相同的,因而可把所有 的处理器作为一个处理器池?并将进程分配到其中的任干处理器上运行。在进行进程分配时, 可采用静态和动态两种分配方式。采用静态分配方式时,一个进程从开始执行直至其完成,都 被固定分配到一个处理器上去执行,此时,需要为每个处理器维护一个专用的就绪队列。静态 分配方式的优点是调度的开销小,缺点是会使处理器的忙闲不均。采用动态分配方式时,系统 中设置有二个公用的就绪队列,所有的就绪进程都被放在该队列中,然后被随机地调度到任一 空闲的处理器上去执行,因此,在一个进程生命周期的不同时刻,它可以在不同的处理器上执 行,对松散祸合的多处理器系统,此时需要进行进程现场信息的转移,会明显增加调度开销,但 动态分配方式能较好地消除处理器忙闲不均的现象。 在配置有多种类型处理器单元的非对称多处理器系统中,常采用主一从式结构,即操作系 统的核心驻留在某个特定的处理器(即主处理器)上,而其他的处理器(即从处理器)只用于执 行用户程序。进程调度由主处理器执行,从处理器空闲时,便向主处理器发一索求进程的信号, 并由主处理器从自己的就绪队列中摘下一个进程分配给请求的从处理器。这种方式的优点是 系统处理简单,缺点是主处理器的故障会导致整个系统瘫痪,而且主处理器容易成为系统瓶 颈。 2.进程(线程)调度方式 在多处理机系统中,常用的进程(线程)调度方式主要有: (1)自调度方式。-它是指在系统中设置一个公用的进程(或线程)队列,所有的处理器在空
闲时,都可自己到该队列中取一进程(或线程)来执行 (2)成组调度方式。它是指将一组相互合作的进程或隶属于国一个进程的一组线程分配到 组处理器上去同时执行 3)专用处理器分配方式。它是指在一个应用程序的执行期间,专门为该应用程序分配一组 处理器,每一个线程一个处理器。这组处理器仅供该应用程序专用,直至该应用程序完成 4.1.3死锁 1.死锁的概念 所谓死锁是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程都将无法 向前推进。死锁是计算机系统和进程所处的一种状态 2.产生死锁的原因和必要条件 (1)死锁产生的原因 死锁产生的原因有以下两点 ①系统资源不足例如在上面的例子中,若系统中有两台打印机或者两台输入设备可 供进程P1和P2使用,当其中任一个进程提出设备请求后,立即可得到满足,显然不会出现死锁 状态。这就是说,如果系统中有足够的资源可供每个进程使用,死锁就不会发生。所以说,产生 死锁的根本原因是可供多个进程共亭的系统资源不足。当然,只有当进程提出资源请求时,才 会发生死锁。 ②进程推讲顺序不当例如在上面的例子中,若进程P2在P1提出使用输入设备的要求之 前,已经完成了对输入设备和打印机的使用,并且释放了它们:或者是在进程P2提出使用打印 机的请求之前,进程Pl已经完成了对输入设备和打印机的使用,并且释放了它们,则均不会发 生死锁。 (2)死锁产生的必要条件 发生死锁的必要条件有以下四条: ①互斥条件:造程要求对所分配的资源进行排它性控制,即在一段时间内某资源仅为一个 进程所占有。 ②不剥夺条件:进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能 由获得该资源的进程自己来释放 ③部分分配条件:进程每次申请它所需要的一部分资源。在等待新资源的同时,进程继续 占有己分配到的资源。 ④环路条件:存在一种进程资源的循环等待链,链中的每一个进程已获得资源的同时被链 中下一个进程所请求 3.死锁的预防 根据以上讨论,要想防止死锁的发生,只需破坏死锁产生的四个必要条件之一即可 (1)破坏互斥条件 破坏互斥条件就是要允许多个进程同时访问资源。但是这受到资源本身固有特性的限制, 有些资源根本不能同时访问,只能互斥访问。比如打印机,就不允许多个进程在其运行期间交 替打印数据,打印机只能互斥使用。因此,企图通过破坏互斥条件防止死锁的发生是不大可能 (2)破坏不剥夺条件 为了破坏不剥夺条件,可以制定这样的策略:一个已获得某些资源的进程,若新的资源请 求不能立即得到满足,则它必须释放所有己获得的资源,以后需要再重新申请。这意味着,一个 进程已获得的资源在运行过程中可被剥夺,从而破坏了不剥夺条件。该策略实现起来比较复杂, 释放已获得资源可能造成前一段工作的失效,重复申请和释放资源会增加系统开销,降低系统 吞吐量
闲时,都可自己到该队列中取一进程(或线程)来执行。 (2)成组调度方式。它是指将一组相互合作的进程或隶属于国一个进程的一组线程分配到 一组处理器上去同时执行。 (3)专用处理器分配方式。它是指在一个应用程序的执行期间,专门为该应用程序分配一组 处理器,每一个线程一个处理器。这组处理器仅供该应用程序专用,直至该应用程序完成。 4.1.3 死 锁 1.死锁的概念 所谓死锁是指多个进程因竞争资源而造成的一种僵局,若无外力作用,这些进程都将无法 向前推进。死锁是计算机系统和进程所处的一种状态。 2. 产生死锁的原因和必要条件 （1）死锁产生的原因 死锁产生的原因有以下两点: ①系统资源不足 例如在上面的例子中,若系统中有两台打印机或者两台输入设备可 供进程P1和P2使用,当其中任一个进程提出设备请求后,立即可得到满足,显然不会出现死锁 状态。这就是说,如果系统中有足够的资源可供每个进程使用,死锁就不会发生。所以说,产生 死锁的根本原因是可供多个进程共亭的系统资源不足。当然,只有当进程提出资源请求时,才 会发生死锁。 ②进程推讲顺序不当 例如在上面的例子中,若进程P2在P1提出使用输入设备的要求之 前,已经完成了对输入设备和打印机的使用,并且释放了它们；或者是在进程 P2 提出使用打印 机的请求之前,进程 Pl 已经完成了对输入设备和打印机的使用,并且释放了它们,则均不会发 生死锁。 （2）死锁产生的必要条件 发生死锁的必要条件有以下四条： ①互斥条件：造程要求对所分配的资源进行排它性控制,即在一段时间内某资源仅为一个 进程所占有。 ②不剥夺条件：进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能 由获得该资源的进程自己来释放。 ③部分分配条件：进程每次申请它所需要的一部分资源。在等待新资源的同时,进程继续 占有己分配到的资源。 ④环路条件：存在一种进程资源的循环等待链,链中的每一个进程已获得资源的同时被链 中下一个进程所请求。 3.死锁的预防 根据以上讨论,要想防止死锁的发生,只需破坏死锁产生的四个必要条件之一即可。 （1）破坏互斥条件 破坏互斥条件就是要允许多个进程同时访问资源。但是这受到资源本身固有特性的限制, 有些资源根本不能同时访问,只能互斥访问。比如打印机,就不允许多个进程在其运行期间交 替打印数据,打印机只能互斥使用。因此,企图通过破坏互斥条件防止死锁的发生是不大可能 的。 （2）破坏不剥夺条件 为了破坏不剥夺条件,可以制定这样的策略:一个已获得某些资源的进程,若新的资源请 求不能立即得到满足,则它必须释放所有己获得的资源,以后需要再重新申请。这意味着,一个 进程已获得的资源在运行过程中可被剥夺,从而破坏了不剥夺条件。该策略实现起来比较复杂, 释放已获得资源可能造成前一段工作的失效,重复申请和释放资源会增加系统开销,降低系统 吞吐量
(3)破坏部分分配条件 为了破坏部分分配条件,就要求所有进程一次性申请它所需要的全部资源。若系统有足够 的资源分配给进程,便一次把所有的资源分配给该进程。但在分配时只要有一种资源要求不能 满足,则资源全不分配,进程等待。显然这种资源分配方法造成了严重的资源浪费,以打印机为 例,一个作业可能只在最后完成时才需要打印计算结果,但在它运行前就把打印机分配给了它, 那么在作业的整个执行过程中打印机完全处于闲置状态。 (4)破坏环路条件 为了破坏环路条件,可以采用有序资源分配法。即将系统中的所有资源都按类型赋予一个 编号,如打印机为1,磁带机为2,等等。并且要求每一个进程均严格地按照编号递增的次序请 求资源。也就是说,只要进程提出请求资源Ri,则在以后的请求中,只能请求排在Ri后面的那 些资源。为资源编号〉,不能再要求编号低于Ri的那些资源。对资源请求作了这样的限制后, 系统中就不会再出现几个进程对资源的请求成为环路的情况。这种方法存在的主要问题是各 种资源编号后不宜修改,从而限制了新设备的增加:尽管在为资源编号时己考虑到大多数作业 实际使用这些资源的顺序,但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况, 从而造成资源的浪费。 4死锁的避免 在预防死锁的方法中所采取的几种策略,总的说来都施加了较强的限制条件,虽然实现起 来较为简单,但却严重地损害了系统性能。在避免死锁的方法中,所施加的限制条件较弱,有可 能获得较好的系统性能。在该方法中,把系统的状态分为安全状态和不安全状态,只要能使系 统始终处于安全状态,便可避免死锁的发生。 (1)安全与不安全状态 在避免死锁的方法中,允许进程动态地申请资源,系统在进行资源分配之前,先计算资源 分配的安全性。若此次分配不会导致系统进入不安全状态,便将资源分配给进程,否则进程等 若在某一时刻,系统能按某种顺序如(P1、P2、 n)来为每个进程分配其所需的资 源,直至最大需求,使每个进程都可顺利地完成,则称此时的系统状态为安全状态,称序列(P1、 P2、…、pn>为安全序列。若某一时刻系统中不存在这样一个安全序列,则称此时的系统状态 为不安全状态。 虽然并非所有不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状 态:反之,只要系统处于安全状态,系统便可避免进入死锁状态。 (2)利用银行家算法避免死锁 Dijkstra给出的银行家算法是具有代表性的避免死锁算法。为实现银行家算法,系统中必 须设置若干数据结构。 银行家算法的数据结构如下 (1)可利用资源向量 Available,它是一个含有m个元素的数组,其中的每一个元素代表一 类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源 的分配和回收而动态地改变。如果 Available(j)=K,表示系统中现有Rj类资源k个。 (2)最大需求矩阵Max,这是一个n×m的矩阵,它定义了系统中n个进程中的每一个进程 对m类资源的最大需求。如果Max(i,j)=k,表示进程i需要Rj类资源的最大数目为k (3)分配矩阵 Allocation,这是一个n×m的矩阵,它定义了系统中每一类资源当前己分配 给每一个进程的资源数。如果 Allocation(i,j)=k,表示进程i当前已分到Rj类资源的数目 为k。 Allocations表示进程i的分配向量,由矩阵 Allocation的第i行构成。 (4)需求矩阵Need,它是一个n×m的矩阵,用以表示每一个进程还需要的各类资源数 如果 Need G,j)哇,表示进程i还需要R类资源k个,才能完成其任务。 Needi表示进程
（3）破坏部分分配条件 为了破坏部分分配条件,就要求所有进程一次性申请它所需要的全部资源。若系统有足够 的资源分配给进程,便一次把所有的资源分配给该进程。但在分配时只要有一种资源要求不能 满足,则资源全不分配,进程等待。显然这种资源分配方法造成了严重的资源浪费,以打印机为 例,一个作业可能只在最后完成时才需要打印计算结果,但在它运行前就把打印机分配给了它, 那么在作业的整个执行过程中打印机完全处于闲置状态。 （4）破坏环路条件 为了破坏环路条件,可以采用有序资源分配法。即将系统中的所有资源都按类型赋予一个 编号,如打印机为 1,磁带机为 2,等等。并且要求每一个进程均严格地按照编号递增的次序请 求资源。也就是说,只要进程提出请求资源 Ri,则在以后的请求中,只能请求排在 Ri 后面的那 些资源。为资源编号〉,不能再要求编号低于 Ri 的那些资源。对资源请求作了这样的限制后, 系统中就不会再出现几个进程对资源的请求成为环路的情况。这种方法存在的主要问题是各 种资源编号后不宜修改,从而限制了新设备的增加:尽管在为资源编号时己考虑到大多数作业 实际使用这些资源的顺序,但也经常会发生作业使用资源的顺序与系统规定顺序不同的情况, 从而造成资源的浪费。 4 死锁的避免 在预防死锁的方法中所采取的几种策略,总的说来都施加了较强的限制条件,虽然实现起 来较为简单,但却严重地损害了系统性能。在避免死锁的方法中,所施加的限制条件较弱,有可 能获得较好的系统性能。在该方法中,把系统的状态分为安全状态和不安全状态,只要能使系 统始终处于安全状态,便可避免死锁的发生。 （1）安全与不安全状态 在避免死锁的方法中,允许进程动态地申请资源,系统在进行资源分配之前,先计算资源 分配的安全性。若此次分配不会导致系统进入不安全状态,便将资源分配给进程,否则进程等 待。 若在某一时刻,系统能按某种顺序如〈P1、P2、…、Pn〉来为每个进程分配其所需的资 源,直至最大需求,使每个进程都可顺利地完成,则称此时的系统状态为安全状态,称序列〈P1、 P2、…、pn>为安全序列。若某一时刻系统中不存在这样一个安全序列,则称此时的系统状态 为不安全状态。 虽然并非所有不安全状态都是死锁状态,但当系统进入不安全状态后,便可能进入死锁状 态:反之,只要系统处于安全状态,系统便可避免进入死锁状态。 （2）利用银行家算法避免死锁 Dijkstra 给出的银行家算法是具有代表性的避免死锁算法。为实现银行家算法,系统中必 须设置若干数据结构。 银行家算法的数据结构如下: (1)可利用资源向量Available,它是一个含有m个元素的数组,其中的每一个元素代表一 类可利用的资源数目,其初始值是系统中所配置的该类全部可用资源数目。其数值随该类资源 的分配和回收而动态地改变。如果 Available (j)=K,表示系统中现有 Rj 类资源 k 个。 (2)最大需求矩阵 Max,这是一个 n ×m 的矩阵,它定义了系统中 n 个进程中的每一个进程 对 m 类资源的最大需求。如果 Max(i,j〉=k,表示进程 i 需要 Rj 类资源的最大数目为 k。 (3)分配矩阵Allocation,这是一个n×m的矩阵,它定义了系统中每一类资源当前己分配 给每一个进程的资源数。如果 Allocation (i,j)=k,表示进程 i 当前已分到 Rj 类资源的数目 为 k。Allocationi 表示进程 i 的分配向量,由矩阵 Allocation 的第 i 行构成。 （4）需求矩阵 Need,它是一个 n×m 的矩阵,用以表示每一个进程还需要的各类资源数。 如果 Need G,j〉哇,表示进程 i 还需要 RJ 类资源 k 个,才能完成其任务。Needi 表示进程 i