第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
的需求向量,由矩阵Need的第i行构成。 上述三个矩阵间存在关系 Need (i, j)=Max(i, j)-Allocation (i, j) 银行家算法如下 Request是进程Pi的请求向量。 Request(j)表示进程Pi请求分配R类资源k个。 当Pi发出资源请求后,系统按下述步骤进行检查z 1)如果 Request<=Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过 它所宣布的最大值。 (2)如果 Request<= Available,则转向步骤(3);否则,表示系统中尚无足够的资源满足Pi 的申请,Pi必须等待。 (3)系统试探把资源分配给进程Pi,并修改下面数据结构中的数值: Available =Available-Requesti Allocation=Allocationi+Request Needi=Needi-Requesti: (4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将 资源分配给进程Pi,以完成本次分配:否则,将试探分配作废,恢复原来的资源分配状态,让进 程Pi等待 系统所执行的安全性算法描述如下 (1)设置两个向量 Work它表示系统可提供给进程继续运行的各类资源数目,它含有m个元素,开始执行安 全性算法时,Work= Availabh Finish它表示系统是否有足够的资源分配给进程,使之运行完成,开始时, Finish(i)= false:当有足够资源分配给进程Pi时,令 Finish(i)=true. (2)从进程集合中找到一个能满足下述条件的进程 Finish (i)=false Needi<=Work 如找到则执行步骤(3):否则,执行步骤(4) (3)当进程Pi获得资源后,可顺利执行直到完成,并释放出分配给它的资源,故应执行 Work =work+Allocation Finish (i)=true (4)若所有进程的 Finish(i)都为true,则表示系统处于安全状态:否则,系统处于不安全 状态 5.死锁的检测和解除 (1)死锁的检测 前面介绍的死锁预防和避免算法都是在系统为进程分配资源时施加限制条件或进行检测 若系统为进程分配资源时不采取任何措施,则应该提供检测和解除死锁的手段 发现死锁的原理是考察某一时刻系统状态是否合理,即是否存在一组可以实现的系统状 态,能使所有进程都得到它们所申请的资源而运行结束。检测死锁算法的基本思想是: 获得某时刻t系统中各类可利用资源的数目向量w(t〉,对于系统中的一组进程P1 P2、…、pn},找出那些对各类资源请求数目均小于系统现在所拥有的各类资源数目的进程 我们可以认为这样的进程可以获得它们所需要的全部资源并运行结束,当它们运行结束后释 放所占有的全部资源,从而使可用资源数目增加,这样的进程加入到可运行结束的进程序列L 中,然后对剩下的进程再作上述考察。如果一组进程{P1、P2、…、Pn}中有几个进程不在序列
的需求向量,由矩阵 Need 的第 i 行构成。 上述三个矩阵间存在关系: Need (i,j)=Max(i,j)-Allocation (i,j) 银行家算法如下: Requesti 是进程 Pi 的请求向量。Requesti(j)=k 表示进程 Pi 请求分配 Rj 类资源 k 个。 当 Pi 发出资源请求后,系统按下述步骤进行检查 z （1）如果 Requesti<=Need,则转向步骤(2);否则,认为出错,因为它所需要的资源数已超过 它所宣布的最大值。 (2)如果 Requesti<=Available,则转向步骤(3〉;否则,表示系统中尚无足够的资源满足 Pi 的申请,Pi 必须等待。 (3)系统试探把资源分配给进程 Pi,并修改下面数据结构中的数值: Available =Available-Requesti; Allocationi=Allocationi+Requesti; Needi=Needi-Requesti; (4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。若安全,才正式将 资源分配给进程 Pi,以完成本次分配:否则,将试探分配作废,恢复原来的资源分配状态,让进 程 Pi 等待。 系统所执行的安全性算法描述如下: (1)设置两个向量。 Work它表示系统可提供给进程继续运行的各类资源数目,它含有m个元素,开始执行安 全性算法时,Work =Availabh。 Finish 它表示系统是否有足够的资源分配给进程,使之运行完成,开始时, Finish (i)=false:当有足够资源分配给进程 Pi 时,令 Finish (i)=true. (2)从进程集合中找到一个能满足下述条件的进程。 Finish (i〉==false: Needi<=Work: 如找到则执行步骤(3〉:否则,执行步骤(4)。 (3)当进程 Pi 获得资源后,可顺利执行直到完成,并释放出分配给它的资源,故应执行 Work =work+Allocationi: Finish (i〉=true: Goto step2: (4)若所有进程的 Finish(i)都为 true,则表示系统处于安全状态:否则,系统处于不安全 状态。 5．死锁的检测和解除 （1）死锁的检测 前面介绍的死锁预防和避免算法都是在系统为进程分配资源时施加限制条件或进行检测， 若系统为进程分配资源时不采取任何措施，则应该提供检测和解除死锁的手段。 发现死锁的原理是考察某一时刻系统状态是否合理,即是否存在一组可以实现的系统状 态,能使所有进程都得到它们所申请的资源而运行结束。检测死锁算法的基本思想是: 获得某时刻 t 系统中各类可利用资源的数目向量 w(t〉,对于系统中的一组进程{Pl、 P2、…、pn},找出那些对各类资源请求数目均小于系统现在所拥有的各类资源数目的进程。 我们可以认为这样的进程可以获得它们所需要的全部资源并运行结束,当它们运行结束后释 放所占有的全部资源,从而使可用资源数目增加,这样的进程加入到可运行结束的进程序列 L 中,然后对剩下的进程再作上述考察。如果一组进程{P1、P2、…、Pn}中有几个进程不在序列
L中,那么它们会发生死锁。 检测死锁可以在每次分配后进行。但是,用于检测死锁的算法比较复杂,所花的检测时间 长,系统开销大,因此,也可以选取比较长的时间间隔来执行。 (2)死锁的解除 旦系统成为死锁状态,就应将系统从死锁状态解脱出来,即解除死锁,使系统恢复到正常 状态。解除死锁的常用方法有两种 ①资源剥夺法:当发现死锁后,从其他进程剥夺足够数量的资源给死锁进程,以解除死锁 状态 ②撤消进程法:此方法是采用强制手段从系统中撤消一个或一部分死锁进程,并剥夺这 些进程的资源供其他死锁进程使用 最简单的撤消进程方法是撤消全部死锁进程,使系统恢复到正常状态。但这种做法付出的 代价太大。另一方法是按照某种顺序逐个撤消死锁进程,直到有足够的资源供其他未被撤消的 进程使用,消除死锁状态为止 4.2重点难点学习提示 本章的学习目的主要是使学生理解和掌握处理机调度和死锁的基本概念,为此应对以下 几个重点、难点问题作认真而深入的学习 1.高优先权优先调度和基于时间片的轮转调度算法 高优先权优先调度和基于时间片的轮转调度算法是目前被广泛使用的两种进程调度算法, 读者应对它们有较深入的理解和掌握 (1)什么是高优先权优先调度算法:这是指将处理机分配给就绪队列中优先权最高的进程 的调度算法。在学习时应了解系统是根据哪些因素来确定一个进程的优先权的,在采用动态优 先权的系统中又将根据哪些因素来调整运行进程的优先权 (2)什么是高响应比优先调度算法:这是指以响应比作为进程的优先权的进程调度算法 在学习时应了解高响应比优先调度算法是为了解决什么问题而引入的,它有何优缺点 (3)什么是时间片轮转算法:这是指让就绪进程以FCFS的方式按时间片轮流使用CPU的 调度方式。在学习时应了解时间片的概念是为了解决什么问题而引入的,它是如何解决上述问 题的。 (4)什么是多级反馈队列调度算法:该算法设置了多个就绪队列,并给每个队列赋予不同 的优先权和时间片。在学习时应了解该算法是如何对各个就绪队列中的进程进行进程调度的, 为什么它能较好地满足各种类型用户的需要。 2.常用的几种实时调度算法 根据确定实时任务优先权方法的不同,可形成以下两种常用的实时调度算法 (1)最早截止时间优先(EDF)算法:在学习时应了解EDF算法是根据什么来确定任务的优 先权的,或者说它是如何保证满足各任务对截止时间的要求的 (2)最低松弛度优先(LLF)算法:在学习时应了解LLF算法是根据什么来确定任务的优先 级的,在什么情况下,一个进程应抢占被另一进程占用的CPU 3.多处理机环境下的进程(线程)调度方式 多处理机系统己广为流行多年,目前,己出现了多种多处理机环境下的进程(线程)调度方 式,故读者应对下述几种比较有代表性的调度方式有较好的了解 (1)自调度方式:自调度方式是多处理机环境下最简单的一种调度方式,在学习时应了解 它是如何为就绪进程(线程)分配处理机的,该方式主要有什么优点,以及它存在哪些缺点 (2)成组调度方式:它将一组相互合作的进程或隶属于同一个进程的一组线程分配到一组 处理器上去同时执行,读者应了解为什么成组调度方式的性能会优于自调度方式
L 中,那么它们会发生死锁。 检测死锁可以在每次分配后进行。但是,用于检测死锁的算法比较复杂,所花的检测时间 长,系统开销大,因此,也可以选取比较长的时间间隔来执行。 （2）死锁的解除 一旦系统成为死锁状态,就应将系统从死锁状态解脱出来,即解除死锁,使系统恢复到正常 状态。解除死锁的常用方法有两种: ①资源剥夺法：当发现死锁后,从其他进程剥夺足够数量的资源给死锁进程,以解除死锁 状态。 ② 撤消进程法：此方法是采用强制手段从系统中撤消一个或一部分死锁进程，并剥夺这 些进程的资源供其他死锁进程使用。 最简单的撤消进程方法是撤消全部死锁进程,使系统恢复到正常状态。但这种做法付出的 代价太大。另一方法是按照某种顺序逐个撤消死锁进程,直到有足够的资源供其他未被撤消的 进程使用,消除死锁状态为止。 4.2 重点难点学习提示 本章的学习目的主要是使学生理解和掌握处理机调度和死锁的基本概念,为此应对以下 几个重点、难点问题作认真而深入的学习。 1.高优先权优先调度和基于时间片的轮转调度算法 高优先权优先调度和基于时间片的轮转调度算法是目前被广泛使用的两种进程调度算法, 读者应对它们有较深入的理解和掌握。 (1)什么是高优先权优先调度算法：这是指将处理机分配给就绪队列中优先权最高的进程 的调度算法。在学习时应了解系统是根据哪些因素来确定一个进程的优先权的,在采用动态优 先权的系统中又将根据哪些因素来调整运行进程的优先权。 (2)什么是高响应比优先调度算法：这是指以响应比作为进程的优先权的进程调度算法。 在学习时应了解高响应比优先调度算法是为了解决什么问题而引入的,它有何优缺点。 (3)什么是时间片轮转算法：这是指让就绪进程以 FCFS 的方式按时间片轮流使用 CPU 的 调度方式。在学习时应了解时间片的概念是为了解决什么问题而引入的,它是如何解决上述问 题的。 (4)什么是多级反馈队列调度算法：该算法设置了多个就绪队列,并给每个队列赋予不同 的优先权和时间片。在学习时应了解该算法是如何对各个就绪队列中的进程进行进程调度的, 为什么它能较好地满足各种类型用户的需要。 2.常用的几种实时调度算法 根据确定实时任务优先权方法的不同,可形成以下两种常用的实时调度算法: (1)最早截止时间优先(EDF)算法：在学习时应了解 EDF 算法是根据什么来确定任务的优 先权的,或者说它是如何保证满足各任务对截止时间的要求的。 (2)最低松弛度优先(LLF)算法：在学习时应了解 LLF 算法是根据什么来确定任务的优先 级的,在什么情况下,一个进程应抢占被另一进程占用的 CPU。 3.多处理机环境下的进程(线程)调度方式 多处理机系统己广为流行多年,目前,己出现了多种多处理机环境下的进程(线程)调度方 式,故读者应对下述几种比较有代表性的调度方式有较好的了解： (1)自调度方式：自调度方式是多处理机环境下最简单的一种调度方式,在学习时应了解 它是如何为就绪进程(线程)分配处理机的,该方式主要有什么优点,以及它存在哪些缺点 (2)成组调度方式：它将一组相互合作的进程或隶属于同一个进程的一组线程分配到一组 处理器上去同时执行,读者应了解为什么成组调度方式的性能会优于自调度方式
(3)专用处理器分配方式:这种方式有可能造成部分处理机的严重浪费,读者必须了解在 并行程度相当高的多处理器环境下,为什么这种浪费是值得的,它换来了什么好处 4.死锁的基本概念 死锁是指多个进程竞争资源而形成的一种僵局,若无外力的作用,这些进程将无法再向前 推进。可见,死锁状态不同于一般的阻塞状态。在学习时,读者应对下述两个问题有较深刻的 理解和掌握 (1)产生死锁的原因是什么:产生死锁的根本原因是竞争资源和进程推进顺序非法,在学 习时应了解这两个根本原因与0S的两个基本特征并发和其事之间存在着什么样的联系。 (2)产生死锁的必要条件有哪些。产生死锁的必要条件奋互斥条件、请求与保持条件、不 剥夺条件和环路等待条件,在学习时请思考如果其中的一个条件不满足,为什么不会产生死 5.预防死锁的方法 预防死锁是通过摒弃死锁产生的必要条件来达到防止死锁产生的目的的在学习时应了 解下述几个方面的内容 (1)摒弃″互斥″条件:应了解"互斥"条件为什么很难被摒弃,对某些(极少数的)互斥共享 的设备(如打印机)又可通过什么技术来摒弃互斥条件 2)摒弃″请求和保持″条件:读者应了解可通过哪些方法来摒弃″请求和保持”条件它们 对进程的运行和系统资源的利用率造成了什么样的影响。 (3)摒弃″不剥夺″条件:读者应了解可通过哪些方法来摒弃”不剥夺”条件,这些法有什么 缺点 (4)摒弃″环路等待″条件:读者应了解可通过哪些方法来摒弃″环路等待”条件,它对系统 和用户带来了哪些不便,对资源的利用率又有什么影响 (5)各种方法的比较:读者应从实现的简单性和资源的利用率等方面比较上述几种预防 死锁的方法,以了解哪种方法实现最简便,哪种方法可使资源利用率受损最少 6.利用银行家算法避免死锁 银行家算法是一种最有代表性的避免死锁的算法。在学习时应对下述几个方面的内容国 有较好的理解: (1)避免死锁的实质在于如何防止系统进入不安全状态二在学习时,读者必须清晰地认识 到,为什么系统处于安全状态便可避免进入死锁状态,而处于不安全状态则极有可能导致死锁 状态的产生。 (2)在银行家算法中用到了可利用资源向量 Available、最大需求矩阵Max、分配矩阵 Allocation、需求矩阵Ned等数据结构,而在安全性检査算法中则还要用到工作向量Work 和完成向量 Finish等数据结构,读者应对它们的物理意义和相互关系有较好的理解。 (3)安全性检査算法的目的是寻找一个安全序列。在学习时应了解满足什么条件的进程 Pi,其对资源的最大需求可以得到满足,故可顺利完成:当Pi完成后,应如何修改工作向量 Work和完成向量 Finish (4)在利用银行家算法避免死锁时应了解,系统什么时候可以为提出资源请求的进程试行 分配资源,什么时候才可以正式将资源分配给进程。 4.3典型问题分析和解答 1.为什么说多级反馈队列调度算法能较好地满足各方面用户的需要? 答:对终端型作业用户而言,他们提交的作业大多属于交互型作业,作业通常较小,系统只 要能使这些作业在一个队列所规定的时间片内完成,便可使他们都感到满意。对短批处理作业 用户而言,开始时他们的作业像终端型作业一样,如果仅在第一个队列中执行一个时间片即可
(3)专用处理器分配方式：这种方式有可能造成部分处理机的严重浪费,读者必须了解在 并行程度相当高的多处理器环境下,为什么这种浪费是值得的,它换来了什么好处。 4.死锁的基本概念 死锁是指多个进程竞争资源而形成的一种僵局,若无外力的作用,这些进程将无法再向前 推进。可见,死锁状态不同于一般的阻塞状态。在学习时,读者应对下述两个问题有较深刻的 理解和掌握: (1)产生死锁的原因是什么：产生死锁的根本原因是竞争资源和进程推进顺序非法,在学 习时应了解这两个根本原因与 OS 的两个基本特征并发和其事之间存在着什么样的联系。 (2)产生死锁的必要条件有哪些。产生死锁的必要条件奋互斥条件、请求与保持条件、不 剥夺条件和环路等待条件,在学习时请思考如果其中的一个条件不满足,为什么不会产生死 锁。 5.预防死锁的方法 预防死锁是通过摒弃死锁产生的必要条件来达到防止死锁产生的目的的在学习时应了 解下述几个方面的内容: (1)摒弃"互斥"条件：应了解"互斥"条件为什么很难被摒弃,对某些(极少数的)互斥共享 的设备(如打印机)又可通过什么技术来摒弃互斥条件。 （2）摒弃"请求和保持"条件：读者应了解可通过哪些方法来摒弃"请求和保持"条件它们 对进程的运行和系统资源的利用率造成了什么样的影响。 (3)摒弃"不剥夺"条件：读者应了解可通过哪些方法来摒弃"不剥夺"条件,这些法有什么 缺点。 (4)摒弃"环路等待"条件：读者应了解可通过哪些方法来摒弃"环路等待"条件,它对系统 和用户带来了哪些不便,对资源的利用率又有什么影响。 （5）各种方法的比较：读者应从实现的简单性和资源的利用率等方面比较上述几种预防 死锁的方法,以了解哪种方法实现最简便,哪种方法可使资源利用率受损最少。 6.利用银行家算法避免死锁 银行家算法是一种最有代表性的避免死锁的算法。在学习时应对下述几个方面的内容国 有较好的理解： (1)避免死锁的实质在于如何防止系统进入不安全状态二在学习时,读者必须清晰地认识 到,为什么系统处于安全状态便可避免进入死锁状态,而处于不安全状态则极有可能导致死锁 状态的产生。 (2)在银行家算法中用到了可利用资源向量 Available、最大需求矩阵 Max、分配矩阵 Allocation、需求矩阵 Need 等数据结构，而在安全性检查算法中则还要用到工作向量 Work 和完成向量 Finish 等数据结构,读者应对它们的物理意义和相互关系有较好的理解。 (3)安全性检查算法的目的是寻找一个安全序列。在学习时应了解满足什么条件的进程 Pi,其对资源的最大需求可以得到满足,故可顺利完成:当 Pi 完成后,应如何修改工作向量 Work 和完成向量 Finish。 (4)在利用银行家算法避免死锁时应了解,系统什么时候可以为提出资源请求的进程试行 分配资源,什么时候才可以正式将资源分配给进程。 4.3 典型问题分析和解答 1.为什么说多级反馈队列调度算法能较好地满足各方面用户的需要? 答:对终端型作业用户而言,他们提交的作业大多属于交互型作业,作业通常较小,系统只 要能使这些作业在一个队列所规定的时间片内完成,便可使他们都感到满意。对短批处理作业 用户而言,开始时他们的作业像终端型作业一样,如果仅在第一个队列中执行一个时间片即可
完成,便可获得与终端型作业一样的响应时间:对于稍长的作业,通常也只需在第二队列和第 三队列各执行一个时间片即可完成,其周转时间仍然很短。对长批处理作业用户而言,他们的 作业将依次在第1,2,…,n个队列中运行,然后再按轮转方式邑行,用户不必担心其作业长期 得不到处理;而且每往下降一个队列,其得到的时间片将随着增加,故可进一步缩短长作业 的等待时间。 2.假设一个系统中有5个进程,它们的到达 表4.1进程到达和需服务时间 时间和服务时间如表4.1所示,忽略I/0以及 其他开销时间,若分别按先来先服务(FCFS)、非抢 匚进程『到达时间服务时间 占及抢占的短进程优先(SPF)、高响应比优先 HRN)、时间片轮转(RR,时间片=1)、多级反馈 队列(FB,第i级队列的时间片=2^i-1)以及立即 枪占的多级反馈队列(FB,第i级队列的时间片=2^i-1) BCDE 2468 3645 调度算法进行CPU调度,请给出各进程的完成时间、 周转时间、带权周转时间、平均周转时间和平均带 权周转时间。 分析:进程调度的关键是理解和掌握调度所采用的算法。FCFS算法选择最早进入就绪队 列的进程投入执行;SPF算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新 就绪的进程运行时间比正在执行的进程的剩余运行时间短,则运行时间+等待时间新进程将抢 占CPU;HRRN算法选择响应比(响应比=最高的运行时间+等待时间/运行时间)最高的进程投入 执行;R算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间 片;FB算法将就绪进程排成多个不同优先权及时间片的队列,新就绪进程总是按FIFO方式先 进入优先权最高的队列,CPU也总是分配给较高优先权队列上的队首进程,若执行一个时间片 仍未完成,则转入下一级队列的末尾,最后一级队列则采用时间片轮转方式进行调度 答:各进程的完成时间、周转时间和带权周转时间(如表4.2所示) 表4.2进程的完成时间和周转时间 进程 完成时间 131820 周转时间 B97 FCFS 带权周转时间1.001.172.256.006.002.56 完成时间 15|11|11 SPF(非抢占)周转时间 7.6 带权周转时间.001.172.7511.51.511.84 完成时间31581010 SPF(抢占)周转时间3134227.2 带权周转时间1.002.161.001.001.001.59 完成时间 131515 HRRN 周转时间 带权周转时间1.001.172.253.53.52.14 完成时间 17 17 15 RR(g=1) 周转时间 4 1313|14|710.8 带权周转时间1.333.253.252.83.52.71 完成时间 10.4 FB(q=2-1)周转时间 2.56 带权周转时间12.503.502.83.00
完成,便可获得与终端型作业一样的响应时间:对于稍长的作业,通常也只需在第二队列和第 三队列各执行一个时间片即可完成,其周转时间仍然很短。对长批处理作业用户而言,他们的 作业将依次在第 1,2,…,n 个队列中运行,然后再按轮转方式邑行,用户不必担心其作业长期 得不到处理； 而且每往下降一个队列，其得到的时间片将随着增加,故可进一步缩短长作业 的等待时间。 2.假设一个系统中有 5 个进程,它们的到达 表 4.1 进程到达和需服务时间 时间和服务时间如表 4.1 所示,忽略 I/0 以及 其他开销时间,若分别按先来先服务(FCFS)、非抢 占及抢占的短进程优先（SPF）、高响应比优先 (HRRN)、时间片轮转(RR,时间片=1)、多级反馈 队列(FB,第 i 级队列的时间片=2^i-1)以及立即 枪占的多级反馈队列(FB,第 i 级队列的时间片=2^i-1) 调度算法进行 CPU 调度,请给出各进程的完成时间、 周转时间、带权周转时间、平均周转时间和平均带 权周转时间。 分析：进程调度的关键是理解和掌握调度所采用的算法。FCFS 算法选择最早进入就绪队 列的进程投入执行;SPF 算法选择估计运行时间最短的进程投入执行,采用抢占方式时,若新 就绪的进程运行时间比正在执行的进程的剩余运行时间短,则运行时间+等待时间新进程将抢 占 CPU;HRRN 算法选择响应比(响应比=最高的运行时间+等待时间/运行时间)最高的进程投入 执行;RR算法中,就绪进程按FIFO方式排队,CPU总是分配给队首的进程,并只能执行一个时间 片;FB 算法将就绪进程排成多个不同优先权及时间片的队列,新就绪进程总是按 FIFO 方式先 进入优先权最高的队列,CPU 也总是分配给较高优先权队列上的队首进程,若执行一个时间片 仍未完成,则转入下一级队列的末尾,最后一级队列则采用时间片轮转方式进行调度。 答：各进程的完成时间、周转时间和带权周转时间(如表 4.2 所示) 表 4.2 进程的完成时间和周转时间 进程 A B C D E 平 均 FCFS 完成时间 周转时间 带权周转时间 3 3 1.00 9 7 1.17 13 9 2.25 18 12 6.00 20 12 6.00 8.6 2.56 SPF(非抢占) 完成时间 周转时间 带权周转时间 3 3 1.00 9 7 1.17 15 11 2.75 11 3 1.5 11 3 1.5 7.6 1.84 SPF(抢占) 完成时间 周转时间 带权周转时间 3 3 1.00 15 13 2.16 8 4 1.00 10 2 1.00 10 2 1.00 7.2 1.59 HRRN 完成时间 周转时间 带权周转时间 3 3 1.00 9 7 1.17 13 9 2.25 15 7 3.5 15 7 3.5 8 2.14 RR(q=1) 完成时间 周转时间 带权周转时间 4 4 1.33 17 13 3．25 17 13 3.25 20 14 2.8 15 7 3.5 10.8 2.71 FB(q=2^i-1) 完成时间 周转时间 带权周转时间 3 3 1 17 15 2.50 18 14 3.50 20 14 2.8 14 6 3.00 10.4 2.56 进程 到达时间 服务时间 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2
F(q=i-1)完成时间 16 (立即抢占周转时间 14810.6 带权周转时 2.84.002.87 3.何谓自调度方式?其主要优缺点是什么? 答:自调度方式是多处理器系统中的一种处理机调度方式,它在系统中设置一个公用的进 程(或线程)队列,所有的处理器在空闲时,都可自己到该队列中取一进程(或线程)来执行。在 自调度方式中,可采用单处理机环境下的进程调度算法(如先来先服务、最高优先权优先、抢 占式最高优先权优先调度算法等)来进行进程调度 自调度算法的主要优点是:①系统中公用就绪队列的组织方式以及具体的进程(或线程) 调度算法都可沿用单处理机中的方式,因而容易实现:②不会发生处理器忙闲不均的现象,因 而有利于提高处理器的利用率 而它的缺点主要是:①公用就绪队列很容易成为整个系统的瓶颈:②一个线程在整个生命 期中,可能要多次更换处理器,从而使处理器上的高速缓存使用率降低,并进一步降低整个系 统的性能:③相互合作型的线程很难冋时获得处理器而同时运行,这将会增加合作线程之间的 阻塞频率,从而提髙线程切换的频率,增加系统的开销并降低进程的运行速度 4.何谓成组调度方式?其主要优点是什么? 答:成组调度方式是多处理器系统中的一种处理机调度方式,它将一组相互合作的进程或 个进程的一组线程分配到一组处理器上去同时执行 成组调度的主要优点是:如果一组相互合作的进程或线程能并行执行,则可有效地减少同步阻 塞的现象,从而可以减少进程和线程的切换次数,使系统性能得到改善:另外,由于每次调度都 可以解决一组进程或线程的处理器分配问题,因而可显著地减少调度频率,降低调度开销。 5.产生死锁的四个必要条件是什么?试以过河问题中产生的死锁为例加以说明 答:产生死锁的必要条件如下: (1)互斥:系统中至少有一个(类)资源必须用非共享方式使用。过河问题中,每一块垫脚石 任一时刻仅能为一个人占用 (2)占用并等待∷一个进程至少占有一个资源并正等待得到其他资源,而这些资源已被其他 进程所占用.过河问题中,相遇的两个人各自踏在一块垫脚石上,并同时等待踏上对方占用的 那一块 (3)非抢占:资源不可能被抢占.在过河问题中,由于垫脚石不能强行移动,"非抢占"条件满 足。 (4)循环等待:存在循环等待情况。从东岸来的人等着从西岸来的人,而从西岸来的人则等 着从东岸来的人 于是,大家都不能过河,每人都等待对方从其占用的垫脚石上移开脚,具备以上四个条件 死锁发生 6.在哲学家就餐问题中,如果将先拿起左边的筷子的哲学家称为左撇子,而将先拿起右边 的筷子的哲学家称为右撇子,请说明在同时存在左撇子和右撤子的情况下,任何就座安排都不 会产空死锁。 分析:这类题目的关键是必须证明产生死锁的4个必要条件的其中一个不可能望成立。在 本题中,互斥条件、请求与保持条件、不剥夺条件是肯定成立的,因此必须证明"循环等待"条 件不成立 答:对本题,死锁产生的必要条件-一"循环等待"不可能成立。如果存在所有左边的哲学家 等待右边的哲学家放下筷子的循环等待链,则每个哲学家肯定已获得左边的筷子,但还没得到 右边的筷子,这与存在右撇子的情况不符:同样,也不可能存在相反的循环等待链。而且,系统
FB(q=^i-1) (立即抢占 完成时间 周转时间 带权周转时间 4 4 1.33 18 16 2.67 15 11 2.75 20 14 2.8 16 8 4.00 10.6 2.87 3.何谓自调度方式?其主要优缺点是什么? 答:自调度方式是多处理器系统中的一种处理机调度方式,它在系统中设置一个公用的进 程(或线程)队列,所有的处理器在空闲时,都可自己到该队列中取一进程(或线程)来执行。在 自调度方式中,可采用单处理机环境下的进程调度算法(如先来先服务、最高优先权优先、抢 占式最高优先权优先调度算法等)来进行进程调度。 自调度算法的主要优点是:①系统中公用就绪队列的组织方式以及具体的进程(或线程) 调度算法都可沿用单处理机中的方式,因而容易实现:②不会发生处理器忙闲不均的现象,因 而有利于提高处理器的利用率。 而它的缺点主要是:①公用就绪队列很容易成为整个系统的瓶颈:②一个线程在整个生命 期中,可能要多次更换处理器,从而使处理器上的高速缓存使用率降低,并进一步降低整个系 统的性能:③相互合作型的线程很难同时获得处理器而同时运行,这将会增加合作线程之间的 阻塞频率,从而提高线程切换的频率,增加系统的开销并降低进程的运行速度。 4.何谓成组调度方式?其主要优点是什么? 答:成组调度方式是多处理器系统中的一种处理机调度方式,它将一组相互合作的进程或 一个进程的一组线程分配到一组处理器上去同时执行。 成组调度的主要优点是:如果一组相互合作的进程或线程能并行执行,则可有效地减少同步阻 塞的现象,从而可以减少进程和线程的切换次数,使系统性能得到改善；另外,由于每次调度都 可以解决一组进程或线程的处理器分配问题,因而可显著地减少调度频率,降低调度开销。 5. 产生死锁的四个必要条件是什么?试以过河问题中产生的死锁为例加以说明。 答：产生死锁的必要条件如下： (1)互斥:系统中至少有一个(类)资源必须用非共享方式使用。过河问题中,每一块垫脚石 任一时刻仅能为一个人占用。 (2)占用并等待:一个进程至少占有一个资源并正等待得到其他资源,而这些资源已被其他 进程所占用.过河问题中,相遇的两个人各自踏在一块垫脚石上,并同时等待踏上对方占用的 那一块。 (3)非抢占:资源不可能被抢占.在过河问题中,由于垫脚石不能强行移动,"非抢占"条件满 足。 (4)循环等待:存在循环等待情况。从东岸来的人等着从西岸来的人，而从西岸来的人则等 着从东岸来的人。 于是,大家都不能过河,每人都等待对方从其占用的垫脚石上移开脚,具备以上四个条件, 死锁发生. 6.在哲学家就餐问题中,如果将先拿起左边的筷子的哲学家称为左撇子,而将先拿起右边 的筷子的哲学家称为右撇子,请说明在同时存在左撇子和右撇子的情况下,任何就座安排都不 会产空死锁。 分析：这类题目的关键是必须证明产生死锁的 4 个必要条件的其中一个不可能望成立。在 本题中,互斥条件、请求与保持条件、不剥夺条件是肯定成立的,因此必须证明"循环等待"条 件不成立。 答:对本题,死锁产生的必要条件-一"循环等待"不可能成立。如果存在所有左边的哲学家 等待右边的哲学家放下筷子的循环等待链,则每个哲学家肯定已获得左边的筷子,但还没得到 右边的筷子,这与存在右撇子的情况不符:同样,也不可能存在相反的循环等待链。而且,系统
