操作系统第03讲：调度算法.pptVIP

第3讲 调度算法 进程的行为 进程交替占用CPU执行指令和等待CPU执行； 计算密集型：较长时间占用CPU执行指令，较少时间和次数等待I/O操作结束； I/O密集型：占用CPU执行指令时间较短，频繁、长时间等待I/O操作结束； 计算机系统的三种基本类型 批处理系统(Batch OS)： 天气预报、科学计算、高精度仿真等需要高性能计算的大型应用； 计算中心，系统配置高，成本昂贵：国防科大的“天河一号”超级计算机，20000个以上CPU，造价数亿； 系统设计目标：最大程度提高硬件资源的使用效率； 非交互式计算：执行过程中不需要和用户进行交互； 作业：定义在批处理文件的一组命令，OS在无用户干预的情况下自动执行； 作业从提交到完成的周转时间长，通常以小时为单位； 计算机系统的三种基本类型 分时系统(Time-sharing OS)： 多个用户在各自的终端上同时连接到计算机系统，以提交命令/返回执行结果的方式与系统进行交互； CPU在用户之间进行时分复用，及时响应用户提交的命令，通常以秒为单位； 系统设计目标：在用户之间公平地分配系统资源； 应用最广的系统：Multics、UNIX、Linux等所有OS都支持； 计算机系统的三种基本类型 实时系统(Real-time OS)： CPU在多进程之间时分复用，进程的执行进度是难以预测的； 应用场合：过程控制系统、信息查询系统、事务处理系统等； 处理流程：数据采集、加工处理、操作控制、反馈处理 用户提交作业时明确定义对外部事件的响应时间或范围；实时系统要么拒绝，一旦接受，就必须按用户要求的时间完成； 硬实时系统：必须在规定的时间内完成处理，否则和没有响应具有同样严重的后果；核电站、武器系统等； 软实时系统：可以容忍偶尔超过规定的时间限制，后果没有完全不响应那么严重；多媒体系统； 调度的目标 公共目标 公平：相对公平（不是绝对公平）地给进程分配资源； 实现策略：设计时制定的调度策略在执行时得到了贯彻； 平衡：尽可能让系统各部分都工作；同时运行计算密集型和I/O密集型 批处理系统 吞吐量：单位时间（小时）内完成的作业数 周转时间：作业提交到完成的用户等待时间；和吞吐量目标可能矛盾 CPU利用率：保持CPU尽可能忙碌； 分时系统 响应时间：快速响应用户的请求； 合理性：满足用户对进程执行的合理期望； 实时系统 满足时间限制：实时系统最重要的目标； 可预测和稳定性：提前预测到可能出现的的性能瓶颈； 批处理调度算法1：先来先服务FCFS 用户同时提交三个作业，进入后备作业队列，所需执行时间分别是： 作业1：28ms；作业2：9ms；作业3：3ms； 高级调度：单道批处理，主存只容纳一个作业；低级调度不起作用； 如果后备作业队列是：作业1、作业2、作业3，则： 周转时间：28、28+9=37、28+9+3=40；平均周转时间：35； 带权周转系数：28/28=1；37/9=4.1；40/3=13.3；平均带权周转系数：6.1 如果后备作业队列是：作业3、作业2、作业1，则： 周转时间：3、3+9=12、3+9+28=40；平均周转时间：18.3； 带权周转系数：3/3=1；12/9=1.3；40/28=1.42；平均带权周转系数：1.24 批处理调度算法1：先来先服务FCFS 高级调度：多道批处理，为3个作业创建3个进程进入就绪队列 进程1：28ms=8ms CPU时间+8ms I/O时间+12ms CPU时间； 进程2：9ms=3ms CPU时间+3ms I/O时间+3ms CPU时间； 进程3：3ms=1ms CPU时间+1ms I/O时间+1ms CPU时间； 批处理调度算法1：先来先服务FCFS 进程1：计算密集型，进入无限循环：1s CPU时间+ 10ms I/O时间 进程2-11：I/O密集型，循环1000次： 1ms CPU时间+ 10ms I/O时间 FCFS以1.01s为周期，循环调度进程1－11依次执行； 进程2－11需要1.01s*1000=1010s才能执行结束； 无进程1，则FCFS以11ms为周期，循环调度进程2－11依次执行 进程2－11需要11ms*1000=11s就能执行结束 批处理调度算法2：最短作业优先 Shortest Job First(SJF)：非抢占式算法，选择所需运行时间最短的作业或进程 高级调度：作业驻留在内存中的时间长度； 低级调度：进程下一次占用CPU执行的时间长度； 批处理调度算法2：最短作业优先 SJF：对同时达到作业/进程的调度是最优的 批处理调度算法2：最短作业优先 Shortest Job First(SJF)：运行时间是调度算法的前提 高级调度：用户根据历史运行数据，估算本次运行所需要的时间 低级调度：可根据本次和历史上每次占用CPU时间