《操作系统处理机调度与死锁(1)》由会员分享，可在线阅读，更多相关《操作系统处理机调度与死锁(1)（73页珍藏版）》请在金锄头文库上搜索。
1、,Page 1,2018/9/19,第三章 处理机调度与死锁,操作系统,刘 刚 ,Page 2,2018/9/19,第三章 处理机调度与死锁,重点 掌握进程调度算法，各适用于何种情况 理解常用的几种实时调度算法 理解产生死锁的原因 掌握银行家算法避免死锁 难点 多道程序设计中的各种调度算法 响应比高者优先调度算法的计算过程 银行家算法,Page 3,2018/9/19,第三章 处理机调度与死锁,知识点 处理机调度及调度算法 多处理机环境下的进程（线程）调度方式 产生死锁的原因和必要条件 预防死锁的方法，死锁的检测与解除 银行家算法,Page 4,2018/9/19,第三章 处理机调度与死锁,处
2、理机是计算机系统中的重要资源 在多道程序环境下，进程数目通常多于处理机的数目 系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程 处理机利用率和系统性能（吞吐量、响应时间）在很大程度上取决于处理机调度,分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。,WHAT：按什么原则分配CPU进程调度算法 WHEN：何时分配CPU 进程调度的时机 HOW：如何分配CPU CPU调度过程（进程的上下文切换）,Page 5,2018/9/19,第三章 处理机调度与死锁,处理机调度的基本概念 调度算法 实时调度 多处理机系统中的调度 产生死锁的原因和必要条件 预防死锁的方法 死锁
3、的检测与解除,Page 6,2018/9/19,处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 7,2018/9/19,处理机调度的基本概念,作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合，包括用户程序、所需的数据及命令等 作业的状态：一个作业进入系统到运行结束，一般需要经历收容、运行、完成三个阶段，与之相对应的是作业的三种状态 后备状态 运行状态 完成状态,Page 8,2018/9/19,处理机调度的基本概念,后备状态,完成状态,就绪,阻塞,执行,I/O完成,I/O请求
4、,时间片完,作业状态间转换,Page 9,2018/9/19,3.1 处理机调度的基本概念,3.1.1 高级、中级和低级调度,1. 高级调度(High Scheduling),2. 低级调度(Low Level Scheduling),3. 中级调度(Intermediate-Level Scheduling),Page 10,2018/9/19,高级、中级和低级调度,高级调度(High Scheduling) 作业调度或长程调度（Long-Term Scheduling） 主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存、输入/输出设备等必要的资源，并建立相应的
5、进程，放入就绪队列，以使该作业的进程获得竞争处理机的权利 也称为接纳调度（Admission Scheduling） 高级调度的时间尺度通常是分钟、小时或天,Page 11,2018/9/19,高级、中级和低级调度,在每次作业调度时，须决定： 接纳多少个作业 即允许多少个作业同时在内存中运行，取决于多 道程序度（Degree of Multiprogramming） 作业太多 服务质量下降 作业太少 资源利用率低 接纳哪些作业 取决于作业调度算法 先来先服务 短作业优先 作业优先权调度 响应比调度,周转时间太长,系统吞吐量太低,适当的折衷,多道程序度：即允许多少个作业同时在内存中运行。 周转时
6、间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。 吞吐量：是指在单位时间内系统所完成的作业数。,Page 12,2018/9/19,高级、中级和低级调度,低级调度 进程调度或短程调度（Short-Term Scheduling） 主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它 常见的低级调度有非抢占式和抢占式两种 低级调度的时间尺度通常是毫秒级的。由于低级调度算法的频繁使用，要求在实现时做到高效,Page 13,2018/9/19,高级、中级和低级调度,中级调度(Intermediate-Level Scheduling) 中程调度(Medium-Term
7、Scheduling) 引入目的是为了提高内存利用率和系统吞吐量。使那些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待 主要任务是按照给定的原则和策略，将处于外存对换区中的重又具备运行条件的就绪进程调入内存，或将处于内存就绪状态或内存阻塞状态的进程交换到外存对换区,Page 14,2018/9/19,处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 15,2018/9/19,进程调度的任务,进程调度的任务 是控制、协调进程对CPU的竞争,即按一定的调度算法从就绪队列中选中一个进
8、程，把CPU的使用权交给被选中的进程,Page 16,2018/9/19,处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 17,2018/9/19,确定算法的原则,具有公平性 资源利用率高（特别是CPU利用率） 在交互式系统情况下要追求响应时间（越短越好） 在批处理系统情况下要追求系统吞吐量,Page 18,2018/9/19,处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 19,2018/9/1
9、9,进程调度方式,非抢占方式(Non-preemptive Mode) 抢占方式(Preemptive Mode),Page 20,2018/9/19,进程调度方式,非抢占方式(Non-preemptive Mode) 当某一进程正在处理机上执行时，即使有某个更为重要或紧迫的进程进入就绪队列，该进程仍继续执行，直到其完成或发生某种事件而进入完成或阻塞状态时，才把处理机分配给更为重要或紧迫的进程 引起进程调度的因素 正在执行的进程执行完毕， 或因发生某事件而不能再继续执行 执行中的进程因提出I/O请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作，如wait、Block、Wakeup原语
10、,优点：算法简单，系统开销小 缺点：紧急任务不能及时响应；短进程到达要等待长进程运行结束,Page 21,2018/9/19,进程调度方式,抢占方式(Preemptive Mode) 当某一进程正在处理机上执行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在执行的进程，将处理机分配给这个更为重要或紧迫的进程 抢占式调度主要有以下原则 优先权原则 允许高优先权的新到进程抢占当前进程的处理机 短作业(进程)优先原则允许执行时间短的新到进程抢占当前进程的处理机 时间片原则 时间片用完后停止执行，重新进行调度，适用于分时系统,优点：适于时间要求严格的实时系统 缺点：调度算法复杂，系统开销大
11、,Page 22,2018/9/19,处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,Page 23,2018/9/19,调度队列模型,仅有进程调度的调度队列模型 具有高级和低级调度的调度队列模型 同时具有三级调度的调度队列模型,Page 24,2018/9/19,调度队列模型,仅有进程调度的调度队列模型 在分时系统中，通常仅设有进程调度 系统把这些进程组织成一个就绪队列 每个进程在执行时，可能有以下几种情况 进程获得CPU正在执行 任务在给定时间片内已完成，释放处理机后为完成状态 任务在时间片内未完成，
12、进入就绪队列末尾 在执行期间因某事件而阻塞,Page 25,2018/9/19,调度队列模型,仅有进程调度的调度队列模型,进程调度,进程完成,等待事件,交互用户,时间片完,Page 26,2018/9/19,调度队列模型,具有高级和低级调度的调度队列模型 在批处理系统中，不仅需要进程调度，而且还要有作业调度 就绪队列的形式 在批处理系统中，常用高优先权队列。进程进入就绪队列时，按优先权高低插入相应位置，调度程序总是把处理机分配给就绪队首进程 设置多个阻塞队列 根据事件的不同设置多个队列提高效率,Page 27,2018/9/19,调度队列模型,进程调度,进程完成,时间片完,与上一模型的主要区别
13、：就绪队列的形式； 设置多个阻塞队列,Page 28,2018/9/19,调度队列模型,同时具有三级调度的调度队列模型,进程调度,中级调度,等待事件,进程完成,时间片完,作业调度,交互型作业,批量作业,挂起,挂起,事件出现,Page 29,2018/9/19,处理机调度的基本概念,高级、中级和低级调度 进程调度的任务 确定算法的原则 进程调度方式 调度队列模型 选择调度方式和调度算法的若干准则,如果你是用户，你希望系统如何为你服务，如何考虑？ 如果你是调度者，从系统整体角度出发，应如何考虑？,Page 30,2018/9/19,3.1.3 选择调度方式和调度算法的若干准则,1. 面向用户的准则
14、,2. 面向系统的准则,Page 31,2018/9/19,3.1.3 选择调度方式和调度算法的若干准则,1. 面向用户的准则,(1) 周转时间短。,(2) 响应时间快。 (3) 截止时间的保证。 (4) 优先权准则。,Page 32,2018/9/19,选择调度方式和调度算法的若干准则,面向用户的准则 周转时间短 平均周转时间,带权周转时间：进程（或作业）的周转时间T与系统为它提供服务的时间TS之比，即W=T/TS 。而平均带权周转时间则可表示为:,Page 33,2018/9/19,选择调度方式和调度算法的若干准则,面向用户的准则 响应时间快 响应时间是指从用户通过键盘提交一个请求开始，直
15、至系统中首次产生响应为止的时间 交互式系统用周转时间衡量不是最佳 截止时间保证 截止时间是指某任务必须开始执行的最迟时间或必须完成的最迟时间 截止时间是实时系统中的重要指标,Page 34,2018/9/19,选择调度方式和调度算法的若干准则,面向用户的准则 周转时间短 响应时间快 截止时间保证,批处理系统,分时系统,实时系统,等待时间短,优先权,Page 35,2018/9/19,选择调度方式和调度算法的若干准则,面向用户的准则 等待时间短 等待时间是在就绪队列中等待所花的时间 调度算法并不影响进程运行和执行I/O的时间量；只影响进程在就绪队列中等待所花费的时间 优先权准则 在批处理、实时和
16、分时系统中都可以选择优先权准则，以便让紧急任务先处理 有时还选择抢占式调度方式,Page 36,2018/9/19,选择调度方式和调度算法的若干准则,面向系统的准则 系统吞吐量高 吞吐量指单位时间内系统所完成的作业数 作业调度的方式和算法对吞吐量的大小有较大影响 处理机利用率高 各类资源的平衡利用 使内存、外存和I/O设备的利用率高,基于这样的准则，你设计操作系统的调度策略应如何？,Page 37,2018/9/19,第三章 处理机调度与死锁,处理机调度的基本概念 调度算法 实时调度 多处理机系统中的调度 产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除,Page 38,2018/9/19,调度算法,在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法 问题提出 如何制定分配策略：对不同的系统和系统目标，通常采用不同的算法，如短作业优先，时间片轮转等 有些算法适用于作业调度，有些适用于进程调度，有些两者皆可,
