操作系统ppt课件第三章

Operating SystemOperating SystemPage 12024/7/18第三章 处理机调度与死锁操作系统Page 12023/8/1Operating SystemOperating System第第第第三三三三章章章章 处处处处理理理理机机机机调调调调度度度度与与与与死死死死锁锁锁锁q重点重点v掌握掌握进程调度进程调度算法，各适用于何种情况算法，各适用于何种情况 v理解常用的几种理解常用的几种实时调度实时调度算法算法 v理解产生理解产生死锁死锁的原因的原因 v掌握掌握银行家算法银行家算法避免避免死锁死锁q难点难点v多道程序设计中的各种调度算法多道程序设计中的各种调度算法 v响应比高者优先调度算法的计算过程响应比高者优先调度算法的计算过程 v银行家算法银行家算法 Page 22024/7/18第三章 处理机调度与死锁重点Page 22023/8/15Operating SystemOperating System第第第第三三三三章章章章 处处处处理理理理机机机机调调调调度度度度与与与与死死死死锁锁锁锁q知识点知识点v处理机调度及调度算法处理机调度及调度算法v多处理机环境下的进程（线程）调度方式多处理机环境下的进程（线程）调度方式v产生死锁的原因和必要条件产生死锁的原因和必要条件v预防死锁的方法，死锁的检测与解除预防死锁的方法，死锁的检测与解除 v银行家算法银行家算法Page 32024/7/18第三章 处理机调度与死锁知识点Page 32023/8/15Operating SystemOperating System第第第第三三三三章章章章 处处处处理理理理机机机机调调调调度度度度与与与与死死死死锁锁锁锁q处理机是计算机系统中的处理机是计算机系统中的重要资源重要资源q在多道程序环境下，进程数目通常在多道程序环境下，进程数目通常多于处多于处理机的数目理机的数目q系统必须按一定方法系统必须按一定方法动态地动态地把处理机把处理机分配分配给给就绪队列中的一个进程就绪队列中的一个进程q处理机处理机利用率和系统性能利用率和系统性能（吞吐量、响应（吞吐量、响应时间）在很大程度上时间）在很大程度上取决于取决于处理机处理机调度调度分配处理机的任务是由进程调度程序完成分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。的。它是操作系统设计的中心问题之一。WHAT：按什么原则分配：按什么原则分配CPU进程调度算法进程调度算法WHEN：何时分配：何时分配CPU 进程调度的时机进程调度的时机 HOW：如何分配：如何分配CPU CPU调度过程（进程调度过程（进程的上下文切换）的上下文切换）Page 42024/7/18第三章 处理机调度与死锁处理机是计算机系统中的重要资源分配处Operating SystemOperating System第第第第三三三三章章章章 处处处处理理理理机机机机调调调调度度度度与与与与死死死死锁锁锁锁q 处理机调度的基本概念处理机调度的基本概念 q 调度算法调度算法 q 实时调度实时调度 q 多处理机系统中的调度多处理机系统中的调度q 产生死锁的原因和必要条件产生死锁的原因和必要条件 q 预防死锁的方法预防死锁的方法 q 死锁的检测与解除死锁的检测与解除Page 52024/7/18第三章 处理机调度与死锁 处理机调度的基本概念 Page 5Operating SystemOperating System处处处处理理理理机机机机调调调调度度度度的的的的基基基基本本本本概概概概念念念念 q高级、中级和低级调度高级、中级和低级调度q进程调度的任务进程调度的任务q确定算法的原则确定算法的原则q进程调度方式进程调度方式q调度队列模型调度队列模型q选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则Page 62024/7/18处理机调度的基本概念 高级、中级和低级调度Page 6202Operating SystemOperating System处处处处理理理理机机机机调调调调度度度度的的的的基基基基本本本本概概概概念念念念q作业作业是用户在一次解题或一个事务处理过是用户在一次解题或一个事务处理过程中程中要求计算机系统所做工作的集合要求计算机系统所做工作的集合，包，包括用户程序、所需的数据及命令等括用户程序、所需的数据及命令等q作业的状态：作业的状态：一个作业进入系统到运行结一个作业进入系统到运行结束，一般需要经历收容、运行、完成三个束，一般需要经历收容、运行、完成三个阶段，与之相对应的是作业的三种状态阶段，与之相对应的是作业的三种状态v后备状态后备状态v运行状态运行状态v完成状态完成状态Page 72024/7/18处理机调度的基本概念作业是用户在一次解题或一个事务处理过程中Operating SystemOperating System运行状态运行状态处处处处理理理理机机机机调调调调度度度度的的的的基基基基本本本本概概概概念念念念后备状态后备状态完成状态完成状态就绪就绪阻塞阻塞执行执行I/O完成完成I/O请求请求时间片完时间片完作业作业注册注册作业作业调度调度进程进程调度调度终止终止作业作业q作业作业状态间转换状态间转换Page 82024/7/18运行状态处理机调度的基本概念后备状态完成状态就绪阻塞执行I/Operating SystemOperating System3.1 处理机调度的基本概念处理机调度的基本概念 3.1.1 高级、中级和低级调度高级、中级和低级调度 1.高级调度高级调度(High Scheduling)2.低级调度低级调度(Low Level Scheduling)3.中级调度中级调度(Intermediate-Level Scheduling)Page 92024/7/183.1 处理机调度的基本概念 3.1.1 高级、中级和低级Operating SystemOperating System高高高高级级级级、中中中中级级级级和和和和低低低低级级级级调调调调度度度度q高级调度高级调度(High Scheduling)(High Scheduling)作业调度作业调度或或长程调度（长程调度（Long-Term Long-Term SchedulingScheduling）v主要任务是按一定的原则对外存上处于后备主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业状态的作业进行选择，给选中的作业分配分配内内存、输入存、输入/输出设备等输出设备等必要的资源必要的资源，并，并建立建立相相应的应的进程进程，放入放入就绪就绪队列队列，以使该作业的进，以使该作业的进程获得竞争处理机的权利程获得竞争处理机的权利v也称为也称为接纳调度（接纳调度（Admission SchedulingAdmission Scheduling）v高级调度的时间尺度通常是分钟、小时或天高级调度的时间尺度通常是分钟、小时或天Page 102024/7/18高级、中级和低级调度高级调度(High SchedulingOperating SystemOperating System高高高高级级级级、中中中中级级级级和和和和低低低低级级级级调调调调度度度度在每次作业调度时，须决定：在每次作业调度时，须决定：v接纳多少个作业接纳多少个作业 即允许多少个作业同时在内存中运行，取决于即允许多少个作业同时在内存中运行，取决于多多 道程序度道程序度（Degree of Multiprogramming）作业太多作业太多 服务质量下降服务质量下降作业太少作业太少 资源利用率低资源利用率低v接纳哪些作业接纳哪些作业 取决于作业调度算法取决于作业调度算法先来先服务先来先服务短作业优先短作业优先作业优先权调度作业优先权调度响应比调度响应比调度周转时间太长系统吞吐量太低 适当的折衷多道程序度多道程序度多道程序度多道程序度：即允许多少个作业同时在内存中运行。：即允许多少个作业同时在内存中运行。周周周周转转转转时时时时间间间间：从从作作业业被被提提交交给给系系统统开开始始，到到作作业业完完成成为为止的这段时间间隔。止的这段时间间隔。吞吐量吞吐量吞吐量吞吐量：是指在单位时间内系统所完成的作业数。：是指在单位时间内系统所完成的作业数。Page 112024/7/18高级、中级和低级调度在每次作业调度时，须决定：周转时间太长Operating SystemOperating System高高高高级级级级、中中中中级级级级和和和和低低低低级级级级调调调调度度度度q低级调度低级调度 进程调度进程调度或或短程调度短程调度（Short-Term Scheduling）v主要任务是按照某种主要任务是按照某种策略和方法策略和方法选取选取一一个处于个处于就绪就绪状态的进程，将处理机状态的进程，将处理机分分配配给它给它v常见的低级调度有常见的低级调度有非抢占式非抢占式和和抢占式抢占式两两种种v低级调度的时间尺度通常是低级调度的时间尺度通常是毫秒级毫秒级的。的。由于低级调度算法的由于低级调度算法的频繁使用频繁使用，要求，要求在实现时做到在实现时做到高效高效Page 122024/7/18高级、中级和低级调度低级调度Page 122023/8/15Operating SystemOperating System高高高高级级级级、中中中中级级级级和和和和低低低低级级级级调调调调度度度度q中级调度中级调度(Intermediate-Level(Intermediate-Level Scheduling)Scheduling)中程调度中程调度(Medium-Term Scheduling)(Medium-Term Scheduling)v引入目的引入目的是为了提高是为了提高内存利用率内存利用率和和系统吞系统吞吐量。吐量。使那些暂时不能运行的进程不再占使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上用宝贵的内存资源，而将它们调至外存上去等待去等待v主要任务主要任务是按照给定的是按照给定的原则和策略原则和策略，将处，将处于外存于外存对换区对换区中的重又具备运行条件的就中的重又具备运行条件的就绪进程绪进程调入内存调入内存，或将处于内存就绪状态，或将处于内存就绪状态或内存阻塞状态的进程或内存阻塞状态的进程交换到外存交换到外存对换区对换区Page 132024/7/18高级、中级和低级调度中级调度(Intermediate-LeOperating SystemOperating System处处处处理理理理机机机机调调调调度度度度的的的的基基基基本本本本概概概概念念念念 q 高级、中级和低级调度高级、中级和低级调度q 进程调度的任务进程调度的任务q 确定算法的原则确定算法的原则q 进程调度方式进程调度方式q 调度队列模型调度队列模型q 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则Page 142024/7/18处理机调度的基本概念 高级、中级和低级调度Page 142Operating SystemOperating System进进进进程程程程调调调调度度度度的的的的任任任任务务务务q 进程调度的任务进程调度的任务 是是控制、协调进程控制、协调进程对对CPUCPU的竞争的竞争,即按一定的调度算法从就绪队列中选即按一定的调度算法从就绪队列中选中一个进程，把中一个进程，把CPUCPU的使用权交给被选的使用权交给被选中的进程中的进程Page 152024/7/18进程调度的任务 进程调度的任务Page 152023/8/1Operating SystemOperating System处处处处理理理理机机机机调调调调度度度度的的的的基基基基本本本本概概概概念念念念 q 高级、中级和低级调度高级、中级和低级调度q 进程调度的任务进程调度的任务q 确定算法的原则确定算法的原则q 进程调度方式进程调度方式q 调度队列模型调度队列模型q 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则Page 162024/7/18处理机调度的基本概念 高级、中级和低级调度Page 162Operating SystemOperating System确确确确定定定定算算算算法法法法的的的的原原原原则则则则q 具有具有公平性公平性q 资源资源利用率高利用率高（特别是（特别是CPUCPU利用率）利用率）q 在交互式系统情况下要追求在交互式系统情况下要追求响应时间响应时间（越短越好）（越短越好）q 在批处理系统情况下要追求系统在批处理系统情况下要追求系统吞吐量吞吐量Page 172024/7/18确定算法的原则 具有公平性Page 172023/8/15Operating SystemOperating System处处处处理理理理机机机机调调调调度度度度的的的的基基基基本本本本概概概概念念念念 q 高级、中级和低级调度高级、中级和低级调度q 进程调度的任务进程调度的任务q 确定算法的原则确定算法的原则q 进程调度方式进程调度方式q 调度队列模型调度队列模型q 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则Page 182024/7/18处理机调度的基本概念 高级、中级和低级调度Page 182Operating SystemOperating System进进进进程程程程调调调调度度度度方方方方式式式式q非抢占方式非抢占方式(Non-preemptive Mode)(Non-preemptive Mode)q抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)Page 192024/7/18进程调度方式非抢占方式(Non-preemptive ModOperating SystemOperating System进进进进程程程程调调调调度度度度方方方方式式式式q非抢占方式非抢占方式(Non-preemptive Mode)(Non-preemptive Mode)当某一进程正在处理机上执行时，即使有某个更当某一进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，该进程仍继为重要或紧迫的进程进入就绪队列，该进程仍继续执行，直到其完成或发生某种事件而进入完成续执行，直到其完成或发生某种事件而进入完成或阻塞状态时，才把处理机分配给更为重要或紧或阻塞状态时，才把处理机分配给更为重要或紧迫的进程迫的进程v引起进程调度的因素引起进程调度的因素正在执行的进程执行完毕，正在执行的进程执行完毕，或因发生某事或因发生某事件而不能再继续执行件而不能再继续执行执行中的进程因提出执行中的进程因提出I/OI/O请求而暂停执行；请求而暂停执行；在进程通信或同步过程中执行了某种原语在进程通信或同步过程中执行了某种原语操作，如操作，如waitwait、BlockBlock、WakeupWakeup原语原语优点优点：算法简单，：算法简单，系统开销小系统开销小缺点缺点：紧急任务不：紧急任务不能及时响应；短进能及时响应；短进程到达要等待长进程到达要等待长进程运行结束程运行结束Page 202024/7/18进程调度方式非抢占方式(Non-preemptive ModOperating SystemOperating System进进进进程程程程调调调调度度度度方方方方式式式式q抢占方式抢占方式(Preemptive Mode)(Preemptive Mode)当某一进程正在处理机上执行时，若有某个当某一进程正在处理机上执行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂更为重要或紧迫的进程进入就绪队列，则立即暂停正在执行的进程，将处理机分配给这个更为重停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程要或紧迫的进程抢占式调度主要有以下原则抢占式调度主要有以下原则优先权原则优先权原则 允许高优先权的新到进程抢允许高优先权的新到进程抢占当前进程的处理机占当前进程的处理机短作业短作业(进程进程)优先原则优先原则允许执行时间短允许执行时间短的新到进程抢占当前进程的处理机的新到进程抢占当前进程的处理机 时间片原则时间片原则 时间片用完后停止执行，时间片用完后停止执行，重新进行调度，适用于分时系统重新进行调度，适用于分时系统 优点优点：适于时间要：适于时间要求严格的实时系统求严格的实时系统缺点缺点：调度算法复：调度算法复杂，系统开销大杂，系统开销大Page 212024/7/18进程调度方式抢占方式(Preemptive Mode)优点：Operating SystemOperating System处处处处理理理理机机机机调调调调度度度度的的的的基基基基本本本本概概概概念念念念 q 高级、中级和低级调度高级、中级和低级调度q 进程调度的任务进程调度的任务q 确定算法的原则确定算法的原则q 进程调度方式进程调度方式q 调度队列模型调度队列模型q 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则Page 222024/7/18处理机调度的基本概念 高级、中级和低级调度Page 222Operating SystemOperating System调调调调度度度度队队队队列列列列模模模模型型型型q仅有进程调度的调度队列模型仅有进程调度的调度队列模型q具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型q同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型Page 232024/7/18调度队列模型仅有进程调度的调度队列模型Page 232023Operating SystemOperating System调调调调度度度度队队队队列列列列模模模模型型型型q仅有进程调度的调度队列模型仅有进程调度的调度队列模型v在分时系统中，通常仅设有进程调度在分时系统中，通常仅设有进程调度v系统把这些进程组织成一个系统把这些进程组织成一个就绪队列就绪队列v每个进程在执行时，可能有以下几种情况每个进程在执行时，可能有以下几种情况进程获得进程获得CPUCPU正在执行正在执行任务在给定时间片内任务在给定时间片内已完成已完成，释放处理，释放处理机后为完成状态机后为完成状态任务在时间片内任务在时间片内未完成未完成，进入就绪队列，进入就绪队列末尾末尾在执行期间因某事件而阻塞在执行期间因某事件而阻塞Page 242024/7/18调度队列模型仅有进程调度的调度队列模型Page 242023Operating SystemOperating System调调调调度度度度队队队队列列列列模模模模型型型型q仅有进程调度的调度队列模型仅有进程调度的调度队列模型就就 绪绪队队 列列阻阻 塞塞队队列列进程调度进程调度CPU进程完成进程完成等待事件等待事件交互用户交互用户事事件件出出现现时间片完时间片完Page 252024/7/18调度队列模型仅有进程调度的调度队列模型就绪队列阻塞队列进程调Operating SystemOperating System调调调调度度度度队队队队列列列列模模模模型型型型q具有高级和低级调度的调度队列模型具有高级和低级调度的调度队列模型v在批处理系统中，不仅需要在批处理系统中，不仅需要进程调度进程调度，而，而且还要有且还要有作业调度作业调度v就绪队列的形式就绪队列的形式在批处理系统中，常用高优先权队列。在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分入相应位置，调度程序总是把处理机分配给就绪队首进程配给就绪队首进程v设置多个阻塞队列设置多个阻塞队列根据事件的不同设置多个队列提高效率根据事件的不同设置多个队列提高效率Page 262024/7/18调度队列模型具有高级和低级调度的调度队列模型Page 262Operating SystemOperating System调调调调度度度度队队队队列列列列模模模模型型型型进程调度进程调度CPU进程完成进程完成时间片完时间片完就就 绪绪队队列列12等待事件等待事件等待事件等待事件等待事件等待事件n12n事件事件 出现出现事件事件 出现出现事件事件 出现出现后后备备 队队列列作业作业调度调度与上一模型的主要区别：就绪队列的形式；与上一模型的主要区别：就绪队列的形式；设置多个阻塞队列设置多个阻塞队列阻阻队队列列塞塞2 2阻阻队队列列塞塞n n阻阻队队列列塞塞1 1Page 272024/7/18调度队列模型进程调度CPU进程完成时间片完就绪队列12等待Operating SystemOperating System调调调调度度度度队队队队列列列列模模模模型型型型q同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型就绪队列就绪队列进程调度进程调度就绪，挂起队列就绪，挂起队列中级调度中级调度阻塞，挂起队列阻塞，挂起队列阻塞队列阻塞队列等待事件等待事件进程完成进程完成时间片完时间片完作业调度作业调度交互型作业交互型作业后备队列后备队列批量作业批量作业挂起挂起挂起挂起事事件件出出现现事件出现事件出现CPUPage 282024/7/18调度队列模型同时具有三级调度的调度队列模型就绪队列进程调度就Operating SystemOperating System处处处处理理理理机机机机调调调调度度度度的的的的基基基基本本本本概概概概念念念念 q 高级、中级和低级调度高级、中级和低级调度q 进程调度的任务进程调度的任务q 确定算法的原则确定算法的原则q 进程调度方式进程调度方式q 调度队列模型调度队列模型q选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则如果你是用户，你希望系统如何为你服务，如何考虑？如果你是用户，你希望系统如何为你服务，如何考虑？如果你是调度者，从系统整体角度出发，应如何考虑？如果你是调度者，从系统整体角度出发，应如何考虑？Page 292024/7/18处理机调度的基本概念 高级、中级和低级调度如果你是用户，你Operating SystemOperating System3.1.3 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 1.面向用户的准则面向用户的准则 2.面向系统的准则面向系统的准则 Page 302024/7/183.1.3 选择调度方式和调度算法的若干准则 1.面向用户Operating SystemOperating System3.1.3 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则 1.面向用户的准则面向用户的准则(1)周转时间短。周转时间短。(2)响应时间快。响应时间快。(3)截止时间的保证。截止时间的保证。(4)优先权准则。优先权准则。Page 312024/7/183.1.3 选择调度方式和调度算法的若干准则 1.面向用户Operating SystemOperating System选选选选择择择择调调调调度度度度方方方方式式式式和和和和调调调调度度度度算算算算法法法法的的的的若若若若干干干干准准准准则则则则q面向用户的准则面向用户的准则v周转时间短周转时间短平均周转时间平均周转时间带权周转时间：带权周转时间：进程（或作业）的进程（或作业）的周转时周转时间间T T与系统为它与系统为它提供服务的时间提供服务的时间T TS S之比，即之比，即W=T/TW=T/TS S。而。而平均带权周转时间平均带权周转时间则可表示为则可表示为:Page 322024/7/18选择调度方式和调度算法的若干准则面向用户的准则带权周转时间：Operating SystemOperating System选选选选择择择择调调调调度度度度方方方方式式式式和和和和调调调调度度度度算算算算法法法法的的的的若若若若干干干干准准准准则则则则q面向用户的准则面向用户的准则v响应时间快响应时间快响应时间响应时间是指从用户通过键盘提交一个请求是指从用户通过键盘提交一个请求开始，直至系统中开始，直至系统中首次首次产生产生响应响应为止的时间为止的时间交互式系统用周转时间衡量不是最佳交互式系统用周转时间衡量不是最佳v截止时间保证截止时间保证截止时间截止时间是指某任务必须开始执行的最迟时是指某任务必须开始执行的最迟时间或必须完成的最迟时间间或必须完成的最迟时间截止时间是截止时间是实时系统实时系统中的重要指标中的重要指标Page 332024/7/18选择调度方式和调度算法的若干准则面向用户的准则Page 33Operating SystemOperating System选选选选择择择择调调调调度度度度方方方方式式式式和和和和调调调调度度度度算算算算法法法法的的的的若若若若干干干干准准准准则则则则q面向用户的准则面向用户的准则v 周转时间短周转时间短v 响应时间快响应时间快v 截止时间保证截止时间保证批处理系统批处理系统分时系统分时系统实时系统实时系统等待时间短等待时间短优先权优先权Page 342024/7/18选择调度方式和调度算法的若干准则面向用户的准则批处理系统分时Operating SystemOperating System选选选选择择择择调调调调度度度度方方方方式式式式和和和和调调调调度度度度算算算算法法法法的的的的若若若若干干干干准准准准则则则则q面向用户的准则面向用户的准则v等待时间短等待时间短等待时间等待时间是在就绪队列中等待所花的时间是在就绪队列中等待所花的时间调度算法并不影响进程运行和执行调度算法并不影响进程运行和执行I/O的时的时间量；只影响进程在就绪队列中等待所花费间量；只影响进程在就绪队列中等待所花费的时间的时间v优先权准则优先权准则在在批处理批处理、实时实时和和分时系统分时系统中都可以选择优中都可以选择优先权准则，以便让紧急任务先处理先权准则，以便让紧急任务先处理有时还选择抢占式调度方式有时还选择抢占式调度方式Page 352024/7/18选择调度方式和调度算法的若干准则面向用户的准则Page 35Operating SystemOperating System选选选选择择择择调调调调度度度度方方方方式式式式和和和和调调调调度度度度算算算算法法法法的的的的若若若若干干干干准准准准则则则则q面向系统的准则面向系统的准则v系统吞吐量高系统吞吐量高吞吐量吞吐量指单位时间内系统所完成的作业数指单位时间内系统所完成的作业数作业调度的方式和算法对吞吐量的大小有较作业调度的方式和算法对吞吐量的大小有较大影响大影响v处理机利用率高处理机利用率高v各类资源的平衡利用各类资源的平衡利用使内存、外存和使内存、外存和I/OI/O设备的利用率高设备的利用率高基于这样的准则，你设计操作系统的调度策略应如何？基于这样的准则，你设计操作系统的调度策略应如何？Page 362024/7/18选择调度方式和调度算法的若干准则面向系统的准则基于这样的准则Operating SystemOperating System第第第第三三三三章章章章 处处处处理理理理机机机机调调调调度度度度与与与与死死死死锁锁锁锁q处理机调度的基本概念处理机调度的基本概念 q调度算法调度算法 q实时调度实时调度 q多处理机系统中的调度多处理机系统中的调度q产生死锁的原因和必要条件产生死锁的原因和必要条件 q预防死锁的方法预防死锁的方法 q死锁的检测与解除死锁的检测与解除Page 372024/7/18第三章 处理机调度与死锁处理机调度的基本概念 Page 37Operating SystemOperating System调调调调度度度度算算算算法法法法q在在OS中中调度的实质是一种资源分配调度的实质是一种资源分配，因而，因而调度算法是指：根据系统的资源分配策略调度算法是指：根据系统的资源分配策略所规定的资源分配算法所规定的资源分配算法q问题提出问题提出q如何制定分配策略：对不同的系统和系统如何制定分配策略：对不同的系统和系统目标，通常采用不同的算法，如短作业优目标，通常采用不同的算法，如短作业优先，时间片轮转等先，时间片轮转等q有些算法适用于作业调度，有些适用于进有些算法适用于作业调度，有些适用于进程调度，有些两者皆可程调度，有些两者皆可Page 382024/7/18调度算法在OS中调度的实质是一种资源分配，因而调度算法是指：Operating SystemOperating System调调调调度度度度算算算算法法法法q 先来先服务和短作业优先算法先来先服务和短作业优先算法q 高优先权优先调度算法高优先权优先调度算法q 基于时间片的轮转调度算法基于时间片的轮转调度算法Page 392024/7/18调度算法 先来先服务和短作业优先算法Page 392023/Operating SystemOperating System先先先先来来来来先先先先服服服服务务务务和和和和短短短短作作作作业业业业优优优优先先先先算算算算法法法法q先来先服务先来先服务(FCFS)/先进先出先进先出(FIFO)调度算法调度算法v按照作业按照作业/进程进入系统的进程进入系统的先后次序先后次序进行调度，进行调度，先进入系统者先调度；即启动等待时间最长的先进入系统者先调度；即启动等待时间最长的作业作业/进程进程v是一种最简单的调度算法，即可用于是一种最简单的调度算法，即可用于作业调度作业调度，也可用于也可用于进程调度进程调度q几个术语几个术语v到达时间、服务时间、开始时间到达时间、服务时间、开始时间v完成时间、等待时间完成时间、等待时间v周转时间：完成时间周转时间：完成时间-到达时间到达时间v带权周转时间：周转时间带权周转时间：周转时间/服务时间服务时间Page 402024/7/18先来先服务和短作业优先算法先来先服务(FCFS)/先进先出(Operating SystemOperating System先先先先来来来来先先先先服服服服务务务务和和和和短短短短作作作作业业业业优优优优先先先先算算算算法法法法04A13B25C32D44E044476先来先服务（先进先出）：先来先服务（先进先出）：712101214111418141225.53.592.8A A A A B B B C C C C C D D E E E E05101518tPage 412024/7/18先来先服务和短作业优先算法04A13B25C32D44E04Operating SystemOperating System先先先先来来来来先先先先服服服服务务务务和和和和短短短短作作作作业业业业优优优优先先先先算算算算法法法法q 先来先服务先来先服务（先进先出）（先进先出）优缺点优缺点v 比较有利于比较有利于长作业（进程）长作业（进程），而不利于，而不利于短作短作业（进程）业（进程）v 有利于有利于CPU繁忙型作业（进程）繁忙型作业（进程），而不利于，而不利于I/O繁忙型作业（进程）繁忙型作业（进程）v 用于批处理系统，不适于分时系统用于批处理系统，不适于分时系统Page 422024/7/18先来先服务和短作业优先算法 先来先服务（先进先出）优缺点 比Operating SystemOperating System先先先先来来来来先先先先服服服服务务务务和和和和短短短短作作作作业业业业优优优优先先先先算算算算法法法法q短作业短作业(进程进程)优先调度算法优先调度算法SJ(P)FSJ(P)Fv短作业短作业(进程进程)优先调度算法优先调度算法SJ(P)FSJ(P)F，以要求，以要求运运行时间长短行时间长短进行调度，即启动要求运行时间最进行调度，即启动要求运行时间最短的作业短的作业v可以分别用于可以分别用于作业调度作业调度和和进程调度进程调度v短作业优先短作业优先(SJF)(SJF)的调度算法，是从后备队列的调度算法，是从后备队列中选择一个或若干个中选择一个或若干个估计运行时间估计运行时间最短的作业，最短的作业，将它们调入内存运行；而短进程优先将它们调入内存运行；而短进程优先(SPF)(SPF)调调度算法，则是从就绪队列中选出一度算法，则是从就绪队列中选出一估计运行时估计运行时间间最短的进程，将处理机分配给它，使它立即最短的进程，将处理机分配给它，使它立即执行并一直执行到完成执行并一直执行到完成，或，或发生某事件发生某事件而被阻而被阻塞放弃处理机时，再重新调度塞放弃处理机时，再重新调度Page 432024/7/18先来先服务和短作业优先算法短作业(进程)优先调度算法SJ(POperating SystemOperating System先先先先来来来来先先先先服服服服务务务务和和和和短短短短作作作作业业业业优优优优先先先先算算算算法法法法04A13B25C32D44E0441短作业短作业/短进程优先（短进程优先（SJF/SPF）：）：4633/26988/391399/413181616/540/52.1A A A AB B BC C C C CD DE E E E05101518tPage 442024/7/18先来先服务和短作业优先算法04A13B25C32D44E04Operating SystemOperating SystemqFCFS/SJF调度算法的性能调度算法的性能先先先先来来来来先先先先服服服服务务务务和和和和短短短短作作作作业业业业优优优优先先先先算算算算法法法法SJFSJF能有效地降低作业的平均等待时间，提高系统吞吐量能有效地降低作业的平均等待时间，提高系统吞吐量SJFSJF平均周转平均周转时间和平均带时间和平均带权周转时间明权周转时间明显改善显改善Page 452024/7/18FCFS/SJF调度算法的性能先来先服务和短作业优先算法SJOperating SystemOperating System先先先先来来来来先先先先服服服服务务务务和和和和短短短短作作作作业业业业优优优优先先先先算算算算法法法法qSJ(P)F调度算法也存在不容忽视的缺点调度算法也存在不容忽视的缺点v对对长作业不利长作业不利。严重的是，若一长作业。严重的是，若一长作业(进程进程)进进入系统的后备队列入系统的后备队列(就绪队列就绪队列)，由于调度程序总，由于调度程序总是优先调度那些是优先调度那些(即使是后进来的即使是后进来的)短作业短作业(进程进程)，将导致长作业将导致长作业(进程进程)长期不被调度长期不被调度饥饿饥饿v完全未考虑作业完全未考虑作业(进程进程)的的紧迫程度紧迫程度，因而不能保，因而不能保证证紧迫性紧迫性作业作业(进程进程)会被会被及时处理及时处理v由于作业由于作业(进程进程)的长短只是根据的长短只是根据用户用户所提供的所提供的估估计执行时间计执行时间而定的，而用户又可能会而定的，而用户又可能会有意或无意有意或无意地地缩短缩短其作业的估计其作业的估计运行时间运行时间，致使该算法不一，致使该算法不一定能真正做到短作业优先调度。定能真正做到短作业优先调度。Page 462024/7/18先来先服务和短作业优先算法SJ(P)F调度算法也存在不容忽视Operating SystemOperating System调调调调度度度度算算算算法法法法q先来先服务和短作业优先算法先来先服务和短作业优先算法q高优先权优先调度算法高优先权优先调度算法q基于时间片的轮转调度算法基于时间片的轮转调度算法Page 472024/7/18调度算法先来先服务和短作业优先算法Page 472023/8Operating SystemOperating System高优先权优先高优先权优先高优先权优先高优先权优先（HPFHPF，Highest Priority FirstHighest Priority First）调度算法调度算法调度算法调度算法q优先权调度算法的类型优先权调度算法的类型v非抢占式非抢占式优先权调度算法优先权调度算法v抢占式抢占式优先权调度算法优先权调度算法Page 482024/7/18高优先权优先（HPF，Highest Priority FiOperating SystemOperating System高优先权优先高优先权优先高优先权优先高优先权优先（HPFHPF，Highest Priority FirstHighest Priority First）调度算法调度算法调度算法调度算法q优先权调度算法的类型优先权调度算法的类型v非抢占式非抢占式优先权调度算法优先权调度算法特点：系统一旦把处理机分配给就绪队特点：系统一旦把处理机分配给就绪队列中列中优先权最高优先权最高的进程后，该进程便的进程后，该进程便一一直执行直执行下去，直至完成，或因发生某事下去，直至完成，或因发生某事件使该进程放弃处理机时，系统才将处件使该进程放弃处理机时，系统才将处理机重新分配给另一优先权最高的进程理机重新分配给另一优先权最高的进程主要主要用于批处理系统用于批处理系统中，也可用于某些中，也可用于某些对实时性对实时性要求不严的实时系统要求不严的实时系统中中Page 492024/7/18高优先权优先（HPF，Highest Priority FiOperating SystemOperating System高优先权优先高优先权优先高优先权优先高优先权优先（HPFHighest Priority FirstHPFHighest Priority First）调度算法调度算法调度算法调度算法q优先权调度算法的类型优先权调度算法的类型v抢占式抢占式优先权调度算法优先权调度算法把处理机分配给优先权最高的进程，但在执行把处理机分配给优先权最高的进程，但在执行期间，只要出现另一个优先权更高的进程，则期间，只要出现另一个优先权更高的进程，则进程调度程序就进程调度程序就立即停止立即停止当前进程的执行，并当前进程的执行，并将处理机分配给新到的优先权最高的进程将处理机分配给新到的优先权最高的进程注意注意：只要只要系统中系统中出现出现一个新的就绪进程，一个新的就绪进程，就就进行进行优先权优先权比较比较该调度算法，能更好地该调度算法，能更好地满足紧迫作业满足紧迫作业的要求，的要求，故而常用于要求比较严格的实时系统中，以及故而常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中对性能要求较高的批处理和分时系统中Page 502024/7/18高优先权优先（HPFHighest Priority FiOperating SystemOperating System高高高高优优优优先先先先权权权权优优优优先先先先调调调调度度度度算算算算法法法法q优先权的类型优先权的类型v静态优先权静态优先权v动态优先权动态优先权Page 512024/7/18高优先权优先调度算法优先权的类型Page 512023/8/Operating SystemOperating System高高高高优优优优先先先先权权权权优优优优先先先先调调调调度度度度算算算算法法法法q优先权的类型优先权的类型v静态优先权静态优先权静态优先权在创建进程时确定，且在进程的整个静态优先权在创建进程时确定，且在进程的整个运行期间运行期间保持不变保持不变。一般地，优先权是利用某一。一般地，优先权是利用某一范围内的一个整数来表示的，例如，范围内的一个整数来表示的，例如，0 0 7 7或或0 0 255255，又把该整数称为又把该整数称为优先数优先数v确定进程静态优先权的依据确定进程静态优先权的依据进程类型进程类型:系统进程，用户进程系统进程，用户进程进程对资源的需求进程对资源的需求用户要求用户要求Page 522024/7/18高优先权优先调度算法优先权的类型Page 522023/8/Operating SystemOperating System确定进程优先权的依据有如下三个方面：(1)进程类型。进程类型。系统进程的优先权高于一般用户进程。(2)进程对资源的需求。进程对资源的需求。如进程的估计执行时间及内存需要量少的进程，应赋予较高的优先权。(3)用户要求。用户要求。由用户进程的紧迫程度和用户所付费用的多少来确定优先权。Page 532024/7/18确定进程优先权的依据有如下三个方面：Page 532023Operating SystemOperating System高高高高优优优优先先先先权权权权优优优优先先先先调调调调度度度度算算算算法法法法q优先权的类型优先权的类型v静态优先权静态优先权静态优先权在创建进程时确定，且在进程的整个静态优先权在创建进程时确定，且在进程的整个运行期间运行期间保持不变保持不变。一般地，优先权是利用某一。一般地，优先权是利用某一范围内的一个整数来表示的，例如，范围内的一个整数来表示的，例如，0 0 7 7或或0 0 255255，又把该整数称为又把该整数称为优先数优先数v确定进程静态优先权的依据确定进程静态优先权的依据进程类型进程类型:系统进程，用户进程系统进程，用户进程进程对资源的需求进程对资源的需求用户要求用户要求v静态优先权特点静态优先权特点系统开销小、不够精确、一般用在要求不高的系系统开销小、不够精确、一般用在要求不高的系统中统中问题：用户将优先权设的较高，对其他进程不利！问题：用户将优先权设的较高，对其他进程不利！短进程优先对长进程不利！短进程优先对长进程不利！Page 542024/7/18高优先权优先调度算法优先权的类型问题：用户将优先权设的较高，Operating SystemOperating System高高高高优优优优先先先先权权权权优优优优先先先先调调调调度度度度算算算算法法法法v动态优先权动态优先权随随进程的推进进程的推进或随其或随其等待时间等待时间的增加而改变，以获的增加而改变，以获得更好的调度性能得更好的调度性能可规定，在可规定，在就绪队列中的进程就绪队列中的进程，随其，随其等待时间的增等待时间的增长长，其优先权，其优先权以速率以速率a提高提高具有具有相同相同优先权优先权初值初值的进程，则的进程，则最先进入最先进入就绪就绪队列，其将因其动态优先权变得最高而队列，其将因其动态优先权变得最高而优先获得优先获得处理机，此即处理机，此即FCFS算法算法具有各不相同的优先权初值的就绪进程，则具有各不相同的优先权初值的就绪进程，则优优先权初值低先权初值低的进程，在的进程，在等待了足够的时间等待了足够的时间后，其后，其优先权便可能升为最高优先权便可能升为最高，从而可以获得处理机，从而可以获得处理机当采用抢占式优先权调度算法时，如果再当采用抢占式优先权调度算法时，如果再规定当前规定当前进程进程的优先权的优先权以速率以速率b下降下降，则可防止一个长作业，则可防止一个长作业长期地长期地垄断垄断处理机处理机Page 552024/7/18高优先权优先调度算法动态优先权Page 552023/8/1Operating SystemOperating System静态优先权，静态优先权，非抢占式非抢占式（1为高优先权）为高优先权）高高高高优优优优先先先先权权权权优优优优先先先先调调调调度度度度算算算算法法法法04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考虑一下考虑一下抢占式抢占式，情况如何？，情况如何？Page 562024/7/18静态优先权，非抢占式（1为高优先权）高优先权优先调度算法04Operating SystemOperating System高高高高优优优优先先先先权权权权优优优优先先先先调调调调度度度度算算算算法法法法q高响应比优先调度算法（高响应比优先调度算法（HRF）v是是FCFS和和SJF的结合，克服了两种算法的的结合，克服了两种算法的缺点缺点v调度策略调度策略：响应比：响应比最高的作业优先启动最高的作业优先启动v因因等待时间等待时间+服务时间服务时间=该作业的该作业的响应时间响应时间，故该优先权又相当于故该优先权又相当于响应比响应比RP。据此，又可。据此，又可表示为表示为Page 572024/7/18高优先权优先调度算法高响应比优先调度算法（HRF）PageOperating SystemOperating System高高高高优优优优先先先先权权权权优优优优先先先先调调调调度度度度算算算算法法法法q对对HRF的小结的小结v等待时间相同等待时间相同的作业，则的作业，则要求服务的时间愈要求服务的时间愈短短，其，其优先权愈高优先权愈高，v要求服务的时间相同要求服务的时间相同的作业，则的作业，则等待时间愈等待时间愈长长，其，其优先权愈高优先权愈高，v长作业，优先权长作业，优先权随等待时间的增加随等待时间的增加而提高，而提高，其等待时间足够长时，其优先权便可升到很其等待时间足够长时，其优先权便可升到很高，高，从而也可获得处理机从而也可获得处理机v是一种折衷，既照顾了短作业，又考虑了作是一种折衷，既照顾了短作业，又考虑了作业到达的先后次序，又不会使长作业长期得业到达的先后次序，又不会使长作业长期得不到服务。不到服务。缺点：要进行响应比计算，增加了系统开销缺点：要进行响应比计算，增加了系统开销对短作业有利对短作业有利是先来先服务是先来先服务对长作业有利对长作业有利Page 582024/7/18高优先权优先调度算法对HRF的小结缺点：要进行响应比计算，增Operating SystemOperating System调调调调度度度度算算算算法法法法q先来先服务和短作业优先算法先来先服务和短作业优先算法q高优先权优先调度算法高优先权优先调度算法q基于时间片的轮转调度算法基于时间片的轮转调度算法Page 592024/7/18调度算法先来先服务和短作业优先算法Page 592023/8Operating SystemOperating System基基基基于于于于时时时时间间间间片片片片的的的的轮轮轮轮转转转转调调调调度度度度算算算算法法法法q简单的时间片轮转法简单的时间片轮转法(RRRound Robin)v系统将所有的就绪进程按先来先服务的原则排系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把成一个队列，每次调度时，把CPU分配给队首分配给队首进程，并令其执行一个时间片进程，并令其执行一个时间片v当执行的时间片用完时，由一个计时器发出当执行的时间片用完时，由一个计时器发出时时钟中断钟中断请求，调度程序便停止该进程的执行，请求，调度程序便停止该进程的执行，并将其放就绪队列尾；然后，再把处理机分配并将其放就绪队列尾；然后，再把处理机分配给就绪队列中新的队首给就绪队列中新的队首v时间片的大小从几时间片的大小从几ms到几百到几百ms优点：公平。保证就绪队列中所有进程在一给定的优点：公平。保证就绪队列中所有进程在一给定的时间内，均能获得一时间片的处理机执行时间时间内，均能获得一时间片的处理机执行时间缺点：紧迫任务响应慢。缺点：紧迫任务响应慢。UNIX中采用：时间片中采用：时间片+优先权优先权Page 602024/7/18基于时间片的轮转调度算法简单的时间片轮转法(RRRoundOperating SystemOperating System基基基基于于于于时时时时间间间间片片片片的的的的轮轮轮轮转转转转调调调调度度度度算算算算法法法法A B C D E A B C D E A B C E A C E C05101518t04A03B05C02D04E012349121517181515/41212/31818/599/21717/414.24.02若到达时间若到达时间为为0 0、1 1、2 2、3 3、4 4，又如，又如何？何？Page 612024/7/18基于时间片的轮转调度算法ABCDEABCDEABCEACECOperating SystemOperating System基基基基于于于于时时时时间间间间片片片片的的的的轮轮轮轮转转转转调调调调度度度度算算算算法法法法v分时系统中常用时间片轮转法分时系统中常用时间片轮转法时间片选择时间片选择问题问题固定时间片固定时间片可变时间片可变时间片时间片大小时间片大小与与时间片大小时间片大小有关的因素有关的因素系统响应时间系统响应时间就绪进程个数就绪进程个数CPUCPU能力能力