计算机操作系统 第三版 第三章处理机调度课件.ppt

第三章 处理机调度与死锁;处理机管理的工作是对CPU资源进行合理的分配使用，以提高处理机利用率，并使各用户公平地得到处理机资源。 要解决的问题 WHAT：按什么原则分配CPU —进程调度算法 WHEN：何时分配CPU —进程调度的时机 HOW： 如何分配CPU —CPU调度过程（进程的上下文切换）;作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成。 一个作业可由多个进程组成，且必须至少有一个进程，但反过来不成立。 作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。;处理机三级调度;低级调度：最基本。各类0S必须具有的功能。 中级调度：较完善的OS中，引入其来改善内存的利用率和提高作业的吞吐量。 高级调度：批处理OS必须配置，纯粹的分时或实时OS中，通常无须配置。;;作业状态;调度的层次;调度的层次;调度的层次;调度的层次;3.1.3 处理机调度模型;作业;1 作业调度的功能 记录系统中各作业的状况 从后备队列中选择一部分作业投入运行（涉及调度算法） 为被选中的作业做好执行前的准备（建立进程、为进程们分配系统资源） 作业执行结束时的后处理;2 作业调度目标 目标 公平性：对所有作业应该是公平的 利用率：应使设备有高的利用率 作业量：每天执行尽可能多的作业 响应时间：有快的响应时间;3 作业调度性能衡量 面向用户的调度性能准则 周转时间：作业从提交到完成（得到结果）所经历的时间。 周转时间Ti=作业完成时刻(Tei)-作业提交时刻(Tsi) =作业等待时间(Twi)+作业执行时间（Tri) 平均周转时间;3 作业调度性能衡量 面向用户的调度性能准则 带权周转时间 带权周转时间Wi=Ti / Tri 平均带权周转时间 响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间——分时系统;3 作业调度性能衡量 面向系统的调度性能准则 吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系——批处理系统 处理机利用率：——大中型主机 各种设备的均衡利用：如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配——大中型主机;1 先来先服务 按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。 FCFS算法 当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式） 最简单的算法 FCFS特点 比较有利于长作业，而不利于短作业 有利于CPU繁忙的作业，而不利于I/O繁忙的作业;2 短作业／进程优先(SJF/SPF)调度算法 (SJF, Shortest Job First) SJF算法 对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢先正在执行的作业 SJF优点 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间 提高系统的吞吐量;2 短作业优先 (SJF, Shortest Job First) SJF缺点 对长作业非常不利，可能长时间得不到执行 未能依据作业的紧迫程度来划分执行的优先级 难以准确估计作业（进程）的执行时间，从而影响调度性能 ;先来先服务调度算法和短作业优先调度算法;4 时间片轮转算法 (Round Robin) 说明 前两种算法主要用于宏观调度，说明怎样选择一个进程或作业开始运行，开始运行后的作法都相同，即运行到结束或阻塞，阻塞结束时等待当前进程放弃CPU 本算法主要用于微观调度，说明怎样并发运行，即切换的方式；设计目标是提高资源利用率 其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率;4 时间片轮转算法 (Round Robin) Round Robin算法 将系统中所有的就绪进程按照FCFS原则，排成一个队列 当执行的时间片用完时，调度程序便停止该进程的执行，并将它送就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片 保证就绪队列中的所有进程，在一给定的时间内，均能获得一个时间片的处理机执行时间 进程可以未使用完一个时间片，就出让CPU（如阻塞）;4 时间片轮转算法 (Round Robin) 时间片长度的确定 （时间片的长度从几个ms到几百ms） 时间片长度变化的影响 过长?退化为FCFS算法，进程在一个时间片内都执行完，响应时间长 过短?用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长;7多级反馈队列算法 (Round Robin with Multiple Feedback) 多级反馈队列算法（目前公认的较好的一种进