中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn Fall 2013 第四讲 CPU调度 中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn Fall 2013
内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法
内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法
调度的类型 按调度的层次： 按OS的类型： 长期（长程、作业、高级）调度； 中期（中级、中程）调度； 短期（短程、进程、低级）调度 批处理调度 分时调度 实时调度 多处理机调度 等等
作业调度 在批处理系统中，一般需要进行作业调度；分时系统和实时系统大多不需要作业调度 作业调度要考虑 1）接纳多少个作业多道程序度 2）接纳哪些作业调度算法
中期调度 与挂起状态相关 目的：提高内存利用率和系统吞吐量 对换
进程调度 在分时系统中，进程调度的运行频率很高 Linux中，常规经验值，时间片大小50ms左右 进程调度要考虑 1）什么时候 发生调度的时机 2）哪个进程 调度原则和调度算法 3）如何分派 进程上下文切换
调度的方式：抢占式／非抢占式 可剥夺式（可抢占式Preemptive）： 当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用 不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去
Scheduling time 调度的时机 When a process Scheduling Switches from running to waiting state Switches from running to ready state Switches from waiting to ready Terminates Scheduling Nonpreemptive: for 1 & 4 Till 1 or 4 Win 3.x, old versions of MacOS, … Preemptive: for 2 & 3 根据时间片抢占、根据优先关系抢占
Objective of multiprogramming 与进程调度相关的进程运行规律分析 Process execution = n (CPU execution + I/O wait) Objective of multiprogramming Maximum CPU utilization Scheduling is a fundamental OS function for almost all resources
Alternating Sequence of CPU And I/O Bursts A property of process：CPU-I/O burst cycle Process Starts as a CPU burst Ends as a CPU burst CPU burst distribution CPU-bound VS. I/O-bound
Histogram of CPU-burst Times
内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法
调度队列模型 按照系统中调度层次的数目，有3种模型 仅有进程调度的 具有高级和低级调度的 同时具有三种调度的
仅具有进程调度的调度队列模型 就 绪 队 列 阻 塞 CPU 时间片完 交互用户 进程调度 进程完成 等待事件 事件发生
具有高、低两级调度的调度队列模型 CPU 进程完成 进程调度 就 绪 队 列 阻 塞 时间片完 等待事件1 等待事件2 等待事件n 作 业 调 度 等待事件1 等待事件2 等待事件n 事件1发生 事件2发生 事件n发生 后 备 批作业 交互
具有三级调度的调度队列模型 CPU 进程完成 进程调度 就 绪 队 列 、 挂 起 时间片完 事件出现 阻 塞 挂起 等待事件 事件发生 后 作业 调度 事件出现 阻 塞 挂起 等待事件 中级 事件发生 后 备 批作业 交互
内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法
选择调度方式和算法的若干准则 面向用户的准则 面向系统的准则 周转时间短 响应时间快 截止时间的保证 优先权准则 系统吞吐率高 处理机利用率好 各类资源的平衡利用
面向用户的准则：1、周转时间短 定义：作业周转时间(Turnaround time)是指从作业提交给系统开始，到作业完成为止的这段时间间隔。包括： 1）作业在外存后备队列上等待作业调度的时间 2）进程在就绪队列上等待进程调度的时间(waiting time) 3）进程在CPU上执行的时间 4）等待I/O操作完成的时间 其中，第2、3、4项在一个作业的处理过程中，可能发生多次 用户和系统管理员对周转时间有不同的需求
定义：平均周转时间 定义：带权周转时间：作业周转时间T与系统为它提供的实际服务时间Ts之比，即W=T/Ts 定义：平均带权周转时间： 通常将周转时间作为评价批处理系统的性能、选择作业调度方式和算法的准则
面向用户的准则：2、响应时间快 定义：响应时间(Response time)是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的的时间，或者说直到在屏幕上显示出结果为止的一段时间间隔。包括： 从键盘输入的请求信息传送到处理机的时间 处理机对请求信息进行处理的时间 将所形成的响应回送到终端显示器的时间 响应时间常用于评价分时操作系统的性能，是选择分时系统中进程调度算法的重要准则之一
面向用户的准则：3、截止时间的保证 定义：截止时间(Deadline)是指某任务必须开始执行的最迟时间，或者必须完成的最迟时间。 截止时间是用来评价实时系统性能的重要指标，因而是选择实时调度算法的重要准则 实时系统 软实时系统(soft real-time) vs 硬实时系统(hard real-time) 非实时系统
面向用户的准则：4、优先权准则 引入优先权 使用优先数表示优先权 优先权高者优先执行 必要时，引入抢占
面向系统的准则：1、系统吞吐率高 定义：吞吐率(Throughput)是指系统在单位时间内完成的作业数 吞吐率与作业的平均长度有关 是用于评价批处理系统性能的重要指标，也是用于选择批处理作业调度的重要准则 吞吐率与作业的平均长度有关 大型作业 中、小型作业 吞吐率与作业的调度算法也有关
面向系统的准则：2、处理机利用率好 CPU是稀缺资源 定义：处理器利用率（CPU Utilization） = 40%～90%
面向系统的准则：3、各类资源的平衡利用 除CPU之外的其他资源，例如内存、外存、I/O设备