Download presentation
Presentation is loading. Please wait.
1
中国科学技术大学计算机系 陈香兰 xlanchen@ustc.edu.cn Fall 2013
第四讲 CPU调度 中国科学技术大学计算机系 陈香兰 Fall 2013
2
内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法
3
内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法
4
调度的类型 按调度的层次： 按OS的类型： 长期（长程、作业、高级）调度； 中期（中级、中程）调度； 短期（短程、进程、低级）调度
批处理调度 分时调度 实时调度 多处理机调度 等等
5
作业调度 在批处理系统中，一般需要进行作业调度；分时系统和实时系统大多不需要作业调度
作业调度要考虑 1）接纳多少个作业多道程序度 2）接纳哪些作业调度算法
6
中期调度 与挂起状态相关 目的：提高内存利用率和系统吞吐量 对换
7
进程调度 在分时系统中，进程调度的运行频率很高
Linux中，常规经验值，时间片大小50ms左右 进程调度要考虑 1）什么时候 发生调度的时机 2）哪个进程 调度原则和调度算法 3）如何分派 进程上下文切换
8
调度的方式：抢占式／非抢占式 可剥夺式（可抢占式Preemptive）：
当有比正在运行的进程优先级更高的进程就绪时，系统可强行剥夺正在运行进程的CPU，提供给具有更高优先级的进程使用 不可剥夺式（不可抢占式 Non-preemptive ）： 某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去
9
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 根据时间片抢占、根据优先关系抢占
10
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
11
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
12
Histogram of CPU-burst Times
13
内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法
14
调度队列模型 按照系统中调度层次的数目，有3种模型 仅有进程调度的 具有高级和低级调度的 同时具有三种调度的
15
仅具有进程调度的调度队列模型 就 绪 队 列 阻 塞 CPU 时间片完 交互用户 进程调度 进程完成 等待事件 事件发生
16
具有高、低两级调度的调度队列模型 CPU 进程完成 进程调度 就 绪 队 列 阻 塞 时间片完 等待事件1 等待事件2 等待事件n
作 业 调 度 等待事件1 等待事件2 等待事件n 事件1发生 事件2发生 事件n发生 后 备 批作业 交互
17
具有三级调度的调度队列模型 CPU 进程完成 进程调度 就 绪 队 列 、 挂 起 时间片完 事件出现 阻 塞 挂起 等待事件 事件发生 后
作业 调度 事件出现 阻 塞 挂起 等待事件 中级 事件发生 后 备 批作业 交互
18
内容提要 调度的类型 调度的队列模型 调度的准则 调度的算法
19
选择调度方式和算法的若干准则 面向用户的准则 面向系统的准则 周转时间短 响应时间快 截止时间的保证 优先权准则 系统吞吐率高
处理机利用率好 各类资源的平衡利用
20
面向用户的准则：1、周转时间短 定义：作业周转时间(Turnaround time)是指从作业提交给系统开始，到作业完成为止的这段时间间隔。包括： 1）作业在外存后备队列上等待作业调度的时间 2）进程在就绪队列上等待进程调度的时间(waiting time) 3）进程在CPU上执行的时间 4）等待I/O操作完成的时间 其中，第2、3、4项在一个作业的处理过程中，可能发生多次 用户和系统管理员对周转时间有不同的需求
21
定义：平均周转时间 定义：带权周转时间：作业周转时间T与系统为它提供的实际服务时间Ts之比，即W=T/Ts 定义：平均带权周转时间： 通常将周转时间作为评价批处理系统的性能、选择作业调度方式和算法的准则
22
面向用户的准则：2、响应时间快 定义：响应时间(Response time)是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的的时间，或者说直到在屏幕上显示出结果为止的一段时间间隔。包括： 从键盘输入的请求信息传送到处理机的时间 处理机对请求信息进行处理的时间 将所形成的响应回送到终端显示器的时间 响应时间常用于评价分时操作系统的性能，是选择分时系统中进程调度算法的重要准则之一
23
面向用户的准则：3、截止时间的保证 定义：截止时间(Deadline)是指某任务必须开始执行的最迟时间，或者必须完成的最迟时间。
截止时间是用来评价实时系统性能的重要指标，因而是选择实时调度算法的重要准则 实时系统 软实时系统(soft real-time) vs 硬实时系统(hard real-time) 非实时系统
24
面向用户的准则：4、优先权准则 引入优先权 使用优先数表示优先权 优先权高者优先执行 必要时，引入抢占
25
面向系统的准则：1、系统吞吐率高 定义：吞吐率(Throughput)是指系统在单位时间内完成的作业数 吞吐率与作业的平均长度有关
是用于评价批处理系统性能的重要指标，也是用于选择批处理作业调度的重要准则 吞吐率与作业的平均长度有关 大型作业 中、小型作业 吞吐率与作业的调度算法也有关
26
面向系统的准则：2、处理机利用率好 CPU是稀缺资源 定义：处理器利用率（CPU Utilization） =
40%～90%
27
面向系统的准则：3、各类资源的平衡利用 除CPU之外的其他资源，例如内存、外存、I/O设备
Similar presentations
