当前课程知识点：操作系统 > 第十五讲 处理机调度 > 15.2 调度准则 > 15.2 调度准则
下面我们来介绍调度准则
也就说在我们处理机调度里头
我们调度的策略
和调度算法好坏的一个比较指标
那首先呢是调度策略
调度策略呢是用来确定
我如何从就绪队列当中
选择下一个执行进程
那这种选择呢
到底选择哪一个
实际上跟我们选择的
调度目标是有关系的
好 那这里我们具体说起来
有些什么问题呢
具体说起来就是挑选哪一个
第二个 挑选的时候
我用什么样的一个准则
来进行挑选
好 调度策略确定下来之后呢
那调度策略的实现
就是我们这里的调度算法
然后我们在这里呢
需要约定一个目标
说我到底这两个调度算法
或者是调度策略哪个比哪个好
在前面我们讲过存储管理
里头有置换算法
那个置换算法的标准很清楚
说到底哪个置换算法好呢
最后 对一个序列来讲
它的缺页次数最少 这就是好的
如果说是在一类的
测试用例里头
它平均的缺页次数少 那就是好的
但是对于调度策略来说呢
这件事情就没有这么简单了
那为了具体说明 我们的调度算法
用什么来作为它的考核指标
我们在这儿呢 有必要介绍一下
处理机的使用模式
也就是说我们通常情况下
进程占用CPU来执行
它通常处于
这样两种模式之间来回切换
一个是用CPU算
这叫CPU计算
另一个呢 我在CPU指挥下
我要进行I/O操作
这时候要跟外设打交道
在外设打交道时候呢
CPU通常情况下处于等待状态
通常情况下呢
我们的应用程序
在这两种状态之间做交替执行
那这种过程呢
我们可以用这样一个图式来表现出来
CPU计算 I/O操作
CPU计算 I/O操作
这几个序列是交替进行的
那从这种交替里头
我们能发现些什么规律呢
这些规律对我们的调度算法有影响吗
那我们对这里的这个执行的过程
做这样一些统计
统计出这样一个结果
说我们关心它每一次CPU执行的时间
这是这儿的横轴
然后根据每一次时间长短呢
对所有的CPU执行时间呢做一个统计
纵向是某一个长度的执行时间
它总的执行次数
那这时候呢我们就得到这样一条曲线
从这儿呢我们可以看到每一次执行呢
通常情况下它的时间都很短
比如说在这里看到的
就是8毫秒以内
好 那更长的时间呢
如果说你给它分配更长的时间片
那这时候呢 我们这件事情就没必要了
所以这个呢可以用来说
我们每一次执行的时间到底分配多长
这是会有依据的
好 那这时候说
我们一个要决定下一个给谁
那肯定是要给到
下一个就绪的进程
但是就绪进程如果有多个的话
我们怎么来判断
那这是第一个问题
第二个是说
如果在这里有时间片机制
也就是我对时间有要求的话
那进程如果说你的时间片分短了
比如说在这里头
我分的时间很短
那大多数操作
都没有执行到一个阶段的时候
你把它暂停下来
好 这样你恢复回来的时候
有些事情没法做了
好 这时候呢我可能被迫放弃CPU
这时候对进程的执行是不利的
所以我们在这儿要选一个
合适的时间尺度
来作为我们这里时间片的基本单位
好 有了这个介绍之后
我们再来看
我们关心的调度算法的目标
我会用什么样的一些指标来度量
我这个调度算法好与坏
首先第一个是CPU的使用率
也就说你不同的调度算法在进程执行等待I/O的时候
我是不是能够及时的找到另一个进程来占用CPU来执行
如果能那这样的话
我总的CPU的繁忙的时间
的比例就会提高
那最理想这是到100%
好 这是系统关心的一个目标
还有一个呢是吞吐力
在单位时间内我完成的进程数目
这是从系统利用效率的角度
来讲我关心的两个指标
而从用户的角度来讲呢
我们可能关心的是另外一些指标
比如说周转时间
从我提交作业到最后算出结果
这中间有多长时间
这是周转时间用户关心的
换个角度来说呢
他可能会关心我的等待时间
这里的等待时间是指
我进程在就绪队列的时间
因为处于我们进程状态里的
那个等待状态的时间
那是必须等的
因为你等I/O操作没结束
想干别的干不了
那我们能缩短的
是在处于就绪状态的这个时间
如果说我一个进程
从等待状态到了就绪
马上就能占用CPU来执行的话
那我的这个周转时间肯定就会短
好 然后对于交互性应用来说
我还关心它的响应时间
从我提交请求到系统给出响应
这中间需要多长时间
比如说我敲键盘 玩游戏
那这时候它不能及时响应我的操作
这是影响用户体验的
好 那在这里头我们说
到底这些指标搁到一起
好像他们都是矛盾的
我们怎么来做 好
这里头呢就有一个
我到底关心哪项指标是我的重点
通常情况下用户只是说
我希望更快的服务
到底怎么算快
那在这儿呢
我们给出这样一些描述
那在不同的情况下
我们对快的描述是不一样的
比如说我在传文件的时候
带宽高 那这时候是快
对应到我们调度算法里头呢
我在单位时间里
能执行更多的进程 这叫快
而在另一些情况下
如果说我是在玩游戏的时候
那我希望它的响应速度好
那就延时低
对于调度算法呢
它就是有低的响应延迟
也就是说响应时间很短 很快
那在这里头呢
这两个因素实际上是相互独立的
延时低并不一定意味着高带宽
高带宽并不一定意味着低延时
它们俩是相互独立的
好 我们在这儿呢用一个类比
来说明它们之间的关系
低延时是指说我想喝水
那这时候呢
那杯水我能很快的有水
我就能喝上了
所以这时候呢是从
我提出这个请求
到有水这个时间段
而如果说我是想把一个游泳池灌满
那这时候呢
开始有水的时间我并不关心
我关心的是最后灌满水的时间
这时候实际上需要的是
你这个水管子流量必须大
好 这是吞吐量和响应延时这两个指标
它们之间的对快的这个描述
好 依据这些描述
我们就可以把
处理机调度策略的目标
分成这样几个方面
一个呢是响应时间目标
我们希望快的响应
也就说减少响应时间
及时处理用户的输入请求
尽快地把输出反馈给用户
那同时呢 我们希望这种响应的时间
它的抖动必须很小
原因在于 如果说
你在某一些情况下响应时间很短
在另外一些情况下响应时间很长
那实际上这时候用户体验
它是很不稳定的
所以在这儿 可预测的响应时间
比高差异的低响应时间更重要
好 这是从这个角度来讲呢
我们改善了它的响应时间
那这时候呢
用户的交互体验就会好
如果说你操作了
机器没有及时给出响应
那这时候呢用户很可能就会说
我就把机器
认为它有故障了就会把它重启
好 所以在这个地方呢
响应时间是操作系统的一个
重要的调度算法要达到目标
这就是它这里的计算延时
另一个目标呢是吞吐量目标
也就说我们希望增加系统的吞吐量
那增加系统吞吐量呢
可以从两个角度来提出解决的方案
一个呢是减少开销
比如说我们上下文切换的时候
它的速度是不是能更快
第二个是提高系统的利用效率
你比如说CPU的利用率
I/O设备的利用率
如果让这两者都达到100%
那你的效率是最高的
同时减少等待时间
这个减少等待时间
用户和系统的目标呢是一致的
减少等待时间可以提高它的响应性能
也可以提高它的吞吐量的性能
好 那也就说我们在这里呢
要在有用户交互的情况下
应该保证系统的吞吐力
否则的话 那我们这个系统呢
它就没办法正常使用了
好 这时候说
吞吐量呢是系统的计算带宽
也就相当于我在单位时间里头
能够尽可能执行更多的进程
这是我们想要达到的目标
还有一个目标呢是公平性
也就说我们的系统它是不是公平的
什么是公平呢
我保证每一个进程占用相同的CPU时间
这是一种描述
这样就公平了吗 那不一定
如果说一个用户执行了更多的进程
那这时候每个进程的时间相同
各个用户之间它是不同的
好 那这时候说
我们换一种提法
让每一个进程的等待时间相同
所以在不同的时间 不同场合
它对公平性的度量是不一样的
好 所以在这里头我们说公平性
实际上你为了增加它的公平性
我在很多时候
会增加它的平均响应时间
也就是我会有一定的开销
来保证它是公平的
好 这是我们关于调度算法的度量指标
和一个调度算法怎么算好
给出来的相应的描述
-0.1 Piazza讨论区
--html
-0.2 在线实验平台
--实验平台使用帮助
--平台使用帮助
-0.2在线实验平台
--Raw HTML
-1.1 课程概述
--视频
-第一讲 操作系统概述--练习
-1.2 教学安排
--视频
-1.3 什么是操作系统
--Video
-1.4 为什么学习操作系统，如何学习操作系统
--Video
-1.5 操作系统实例
--视频
-1.6 操作系统的演变
--视频
-1.7 操作系统结构
--视频
-2.1 前言和国内外现状
-2.2 OS实验目标
-2.3 8个OS实验概述
-2.4 实验环境搭建
-2.5 x86-32硬件介绍
-2.6 ucore部分编程技巧
-2.7 演示实验操作过程
--Q6
--Q7
--Q10
-3.1 BIOS
--3.1 BIOS
-3.2 系统启动流程
-3.3 中断、异常和系统调用比较
-第三讲 启动、中断、异常和系统调用--3.3 中断、异常和系统调用比较
-3.4 系统调用
--3.4 系统调用
-第三讲 启动、中断、异常和系统调用--3.4 系统调用
-3.5 系统调用示例
-3.6 ucore+系统调用代码
-4.1 启动顺序
--4.1 启动顺序
-4.2 C函数调用的实现
-4.3 GCC内联汇编
-4.4 x86中断处理过程
-4.5 练习一
--4.5 练习一
-4.6 练习二
--4.6 练习二
-4.7 练习三
--4.7 练习三
-4.8 练习四 练习五
-4.9 练习六
--4.9 练习六
-5.1 计算机体系结构和内存层次
-5.2 地址空间和地址生成
-5.3 连续内存分配
-5.4 碎片整理
--5.4 碎片整理
-5.5 伙伴系统
--5.5 伙伴系统
-第五讲 物理内存管理: 连续内存分配--5.6 练习
-6.1 非连续内存分配的需求背景
-6.2 段式存储管理
-- 6.2 段式存储管理
-6.3 页式存储管理
-6.4 页表概述
--6.4 页表概述
-6.5 快表和多级页表
-6.6 反置页表
--6.6 反置页表
-6.7 段页式存储管理
-第六讲 物理内存管理: 非连续内存分配--6.8 练习
-7.1 了解x86保护模式中的特权级
-第七讲 实验二 物理内存管理--7.1 了解x86保护模式中的特权级
-7.2 了解特权级切换过程
-第七讲 实验二 物理内存管理--7.2 了解特权级切换过程
-7.3 了解段/页表
-第七讲 实验二 物理内存管理--7.3 了解段/页表
-7.4 了解UCORE建立段/页表
-第七讲 实验二 物理内存管理--7.4 了解UCORE建立段/页表
-7.5 演示lab2实验环节
-8.1 虚拟存储的需求背景
-8.2 覆盖和交换
-8.3 局部性原理
-8.4 虚拟存储概念
-8.5 虚拟页式存储
-8.6 缺页异常
--8.6 缺页异常
-9.1 页面置换算法的概念
-9.2 最优算法、先进先出算法和最近最久未使用算法
-第九讲 页面置换算法--9.2 最优算法、先进先出算法和最近最久未使用算法
-9.3 时钟置换算法和最不常用算法
-第九讲 页面置换算法--9.3 时钟置换算法和最不常用算法
-9.4 Belady现象和局部置换算法比较
-第九讲 页面置换算法--9.4 Belady现象和局部置换算法比较
-9.5 工作集置换算法
-第九讲 页面置换算法--9.5 工作集置换算法
-9.6 缺页率置换算法
-第九讲 页面置换算法--9.6 缺页率置换算法
-9.7 抖动和负载控制
-10.1 实验目标：虚存管理
-第十讲 实验三 虚拟内存管理--10.1 实验目标：虚存管理
-10.2 回顾历史和了解当下
-第十讲 实验三 虚拟内存管理--10.2 回顾历史和了解当下
-10.3 处理流程、关键数据结构和功能
-第十讲 实验三 虚拟内存管理--10.3 处理流程、关键数据结构和功能
-10.4 页访问异常
-第十讲 实验三 虚拟内存管理--10.4 页访问异常
-10.5 页换入换出机制
-第十讲 实验三 虚拟内存管理--10.5 页换入换出机制
-11.1 进程的概念
-第十一讲 进程和线程--11.1 进程的概念
-11.2 进程控制块
-第十一讲 进程和线程--11.2 进程控制块
-11.3 进程状态
-第十一讲 进程和线程--11.3 进程状态
-11.4 三状态进程模型
-11.5 挂起进程模型
-第十一讲 进程和线程--11.5 挂起进程模型
-11.6 线程的概念
-第十一讲 进程和线程--11.6 线程的概念
-11.7 用户线程
-第十一讲 进程和线程--11.7 用户线程
-11.8 内核线程
-第十一讲 进程和线程--11.8 内核线程
-12.1 进程切换
-第十二讲 进程控制--12.1 进程切换
-12.2 进程创建
-第十二讲 进程控制--12.2 进程创建
-12.3 进程加载
-第十二讲 进程控制--12.3 进程加载
-12.4 进程等待与退出
-第十二讲 进程控制--12.4 进程等待与退出
-13.1 总体介绍
-13.2 关键数据结构
-13.3 执行流程
-13.4 实际操作
-14.1 总体介绍
-14.2 进程的内存布局
-14.3 执行ELF格式的二进制代码-do_execve的实现
--14.3 执行ELF格式的二进制代码-do_execve的实现
-14.4 执行ELF格式的二进制代码-load_icode的实现
--14.4 执行ELF格式的二进制代码-load_icode的实现
-14.5 进程复制
-14.6 内存管理的copy-on-write机制
-15.1 处理机调度概念
-第十五讲 处理机调度--15.1 处理机调度概念
-15.2 调度准则
-15.3 先来先服务、短进程优先和最高响应比优先调度算法
--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-第十五讲 处理机调度--15.3 先来先服务、短进程优先和最高响应比优先调度算法
-15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
--15.4 时间片轮转、多级反馈队列、公平共享调度算法和ucore调度框架
-第十五讲 处理机调度--15.4 时间片轮转、多级反馈队列、公平共享调度算法和uc
-15.5 实时调度和多处理器调度
-第十五讲 处理机调度--15.5 实时调度和多处理器调度
-15.6 优先级反置
-第十五讲 处理机调度--15.6 优先级反置
-16.1 总体介绍和调度过程
-16.2 调度算法支撑框架
-16.3 时间片轮转调度算法
-16.4 Stride调度算法
-17.1 背景
--17.1 背景
-17.2 现实生活中的同步问题
-第十七讲 同步互斥--17.2 现实生活中的同步问题
-17.3 临界区和禁用硬件中断同步方法
-第十七讲 同步互斥--17.3 临界区和禁用硬件中断同步方法
-17.4 基于软件的同步方法
-第十七讲 同步互斥--17.4 基于软件的同步方法
-17.5 高级抽象的同步方法
-第十七讲 同步互斥--17.5 高级抽象的同步方法
-18.1 信号量
--18.1 信号量
-第十八讲 信号量与管程--18.1 信号量
-18.2 信号量使用
-第十八讲 信号量与管程--18.2 信号量使用
-18.3 管程
--18.3 管程
-第十八讲 信号量与管程--18.3 管程
-18.4 哲学家就餐问题
-18.5 读者-写者问题
-19.1 总体介绍
-19.2 底层支撑
-第十九讲 实验七 同步互斥--19.2 底层支撑
-19.3 信号量设计实现
-第十九讲 实验七 同步互斥--19.3 信号量设计实现
-19.4 管程和条件变量设计实现
-第十九讲 实验七 同步互斥--19.4 管程和条件变量设计实现
-19.5 哲学家就餐问题
-20.1 死锁概念
-第二十讲 死锁和进程通信--20.1 死锁概念
-20.2 死锁处理方法
-第二十讲 死锁和进程通信--20.2 死锁处理方法
-20.3 银行家算法
-第二十讲 死锁和进程通信--20.3 银行家算法
-20.4 死锁检测
-第二十讲 死锁和进程通信--20.4 死锁检测
-20.5 进程通信概念
-第二十讲 死锁和进程通信--20.5 进程通信概念
-20.6 信号和管道
-第二十讲 死锁和进程通信--20.6 信号和管道
-20.7 消息队列和共享内存
-第二十讲 死锁和进程通信--20.7 消息队列和共享内存
-21.1 文件系统和文件
-第二十一讲 文件系统--21.1 文件系统和文件
-21.2 文件描述符
-第二十一讲 文件系统--21.2 文件描述符
-21.3 目录、文件别名和文件系统种类
-第二十一讲 文件系统--21.3 目录、文件别名和文件系统种类
-21.4 虚拟文件系统
-第二十一讲 文件系统--21.4 虚拟文件系统
-21.5 文件缓存和打开文件
-第二十一讲 文件系统--21.5 文件缓存和打开文件
-21.6 文件分配
-第二十一讲 文件系统--21.6 文件分配
-21.7 空闲空间管理和冗余磁盘阵列RAID
-第二十一讲 文件系统--21.7 空闲空间管理和冗余磁盘阵列RAID
-22.1 总体介绍
-第二十二讲 实验八 文件系统--22.1 总体介绍
-22.2 ucore 文件系统架构
-第二十二讲 实验八 文件系统--22.2 ucore 文件系统架构
-22.3 Simple File System分析
-第二十二讲 实验八 文件系统--22.3 Simple File System分析
-22.4 Virtual File System分析
-第二十二讲 实验八 文件系统--22.4 Virtual File System分
-22.5 I/O设备接口分析
-第二十二讲 实验八 文件系统--22.5 I/O设备接口分析
-22.6 执行流程分析
-23.1 I/O特点
--视频
-第二十三讲 I/O子系统--23.1 I/O特点
-23.2 I/O结构
--816C80A0F5E3B8809C33DC5901307461
-第二十三讲 I/O子系统--23.2 I/O结构
-23.3 I/O数据传输
--C58221E14388B9DB9C33DC5901307461
-第二十三讲 I/O子系统--23.3 I/O数据传输
-23.4 磁盘调度
--567A3F1FCBFB3F4C9C33DC5901307461
-第二十三讲 I/O子系统--23.4 磁盘调度
-23.5 磁盘缓存
--C327536B80D25CE79C33DC5901307461
-第二十三讲 I/O子系统--23.5 磁盘缓存
-html
--html
