第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)算法