《第4章处理器调度.ppt》由会员分享，可在线阅读，更多相关《第4章处理器调度.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第四章第四章 处理器调度处理器调度1.1.调度及其类型调度及其类型*关于调度关于调度 调度是操作系统的基本功能，几乎所有的系统资源在使用前都要经过调度。处理器是计算机系统中最重要的资源，其调度策略常表征操作系统的某种特征。*调度类型调度类型1.1 1.1 作业调度（高级调度、宏观调度、长期调度）作业调度（高级调度、宏观调度、长期调度）主要工作和任务主要工作和任务 根据某种策略或算法，从后备作业中选择若干作业，分配必要的资源，建立相应进程，加载相应的程序和数据并等待进程调度为其指派处理器。作业完成后的善后工作。时间尺度时间尺度分钟、小时、天。1.2 1.2 中级调度（进程对换、中期调度、交换调度
2、）中级调度（进程对换、中期调度、交换调度）设置原因设置原因内存资源缺乏、进程阻塞、进程数目过多。主要工作和作用主要工作和作用 内存与外存间进程交换。系统短期调整。常用于具有虚拟存贮技术的系统或分时系统中。1.3 1.3 进程调度（微观调度、低级调度、短期调度）进程调度（微观调度、低级调度、短期调度）主要工作和要求主要工作和要求 选择就绪进程占用处理器并实现转接。常驻内存。对系统性能影响重大。时间尺度时间尺度毫秒级。1.4 1.4 三级调度之间的关系三级调度之间的关系 作业身份的转换。竞争CPU过程中内存资源紧张或不足的处理。处理器的真正指派。*调度实例调度实例 1 1 MULTICSMULTI
3、CS系统系统其调度方案为 限定后备状态作业数60。限定内存作业道数8，定时交换（2秒）。说明说明 小范围内多道。大范围内分时。2 2 UNIXUNIX系统系统其调度方案为 核心程序中的sched程序段负责进程映象的换入换出，相当于中级调度。核心程序中的swtch程序段负责分配CPU，相当于进度调度。2.2.调度性能评价调度性能评价2.1 2.1 调度的实质与操作系统的设计目标调度的实质与操作系统的设计目标 调度的实质调度的实质是为了达到主观上某些设计目标。设计目标设计目标 尽可能多的作业。处理器忙。I/O设备充分利用。公平合理。2.2 2.2 设计调度算法的因素设计调度算法的因素 选择算法应与
4、系统的整个设计目标一致。注意系统资源的均衡使用。防止某些作业长期得不到调度。尽量公平合理。算法不应过于复杂。2.3 2.3 有关指标说明有关指标说明 与用户相关的指标与用户相关的指标 周转时间周转时间 指作业从提交到完成（得到结果）所经历的时间。响应时间响应时间 指用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间。公平性公平性 指调度算法不会因作业或进程本身的特性而使上两个指标过分恶化。与系统相关的指标与系统相关的指标 吞吐量吞吐量 指单位时间内所完成的作业数。作业平均周转时间作业平均周转时间 T=(Ti)/n 其中 n为被测定作业流中的作业数，Ti=Tci-Tsi(即作业执行
5、时间+等待调度时间),Tci=作业i的完成时刻，Tsi作业i的提交时刻。作业平均带权周转时间作业平均带权周转时间 W=(Wi)/n,其中 Wi=Ti/tRi,tRi=作业i的实际执行时间。系统利用率系统利用率 指处理器的利用率及各种设备的均衡利用率。ni=1ni=13.3.作业调度作业调度3.1 3.1 单道批处理系统的调度算法单道批处理系统的调度算法 先来先服务算法先来先服务算法FCFSFCFS按作业到达的先后次序进行调度，优先考虑在系统中等待时间最长的作业，而不论其要求的执行时间的长短。示例示例假定四个作业的到达顺序如下：1#：要求运行时间2秒。2#：要求运行时间60秒。3#：要求运行时间
6、2秒。4#：要求运行时间2秒。忽略四个作业在机外的等待时间，计算T与W。T=48.5W=16.76 短作业优先算法短作业优先算法SJFSJF优先调度要求运行时间最短的作业。上例T=19.5W=1.8 响应比高者优先算法响应比高者优先算法HRNHRN 响应比响应比 Rp=作业响应时间tR/要求执行时间 其中tR=到此次调度时已等待时间+要求执行时间 故 Rp=1+作业已等待时间/要求执行时间 1）防止无限制调度延迟。2）照顾先来后到。3）照顾短作业。3.2 3.2 多道批处理系统的调度算法多道批处理系统的调度算法 需要考虑的因素需要考虑的因素 CPU对I/O等待时间问题 T与W的定量计算问题 算
7、法讨论算法讨论 基于先来先服务算法基于先来先服务算法 基于优先级调度算法基于优先级调度算法 示例示例B5500计算机操作系统实行由用户根据作业的紧急程度在其作业申请表中指定一个优先数，系统依据这个优先数将作业的JCB插入相应的优先级队列中。示例示例 IBM360/370系统中按作业的类别划分优先级。如图 A类：I/O繁忙的作业 B类：I/O和CPU均衡的作业 C类：CPU繁忙的作业 D类：其它一般的作业 2 21 1A AA A类类优先级优先级0A A、B B、C C类类B B、C C类类X X类类优先级优先级1优先级优先级2优先级优先级3优先级高优先级高优先级低优先级低2 21 1B B2
8、21 1C C2 21 1D D 调度规则调度规则 1）用户说明其作业类别及该类中的优先数。2）作业注册程序对作业先按类排列，同类中按优先数排序。3）主存用户区分区，规定各分区接纳的作业类型。4）作业调度从相应类的作业中挑选优先级高的作业投入运行。分时和优先级相结合调度算法分时和优先级相结合调度算法用于分时系统及某些引入分时机制的多道批处理系统中。示例示例 MULTICS系统采用分时和优先级结合的调度算法。1）后备作业按优先级分成多个队列。2）作业指定一个优先级范围（L1,L2），任何时刻作业的优先级Li都满足1L1LiL2n。3）会话型作业（分时作业）优先级从1到P1，非会话型（批处理）作业优先级从P2到n，允许P2a0 2）若ba1；3-2；4-1。执行就绪阻塞123412、设某系统进程调度算法为：IO多的进程高优先级，使用CPU时间多的进程低优先级；进程按优先级高者优先调度原则，在同一优先级上按先进先出FIFO原则调度。试从下列方面实现上述调度算法：1）设计就绪队列；2）各进程何时进入就绪队列？在队列中的排序顺序如何？3）进程调度流程。