当前课程知识点：操作系统 > 第二十三讲 I/O子系统 > 23.4 磁盘调度 > 567A3F1FCBFB3F4C9C33DC5901307461
下面我们来讨论磁盘调度
前面我们说了I/O的特点
I/O的结构和I/O的数据传输
下面我们举一类
具体的设备的优化问题
这就是我们这里的磁盘调度
在具体讨论磁盘调度之前
我们有必要讨论一下
磁盘的工作机理和它的性能参数
这是一个磁盘的基本结构
它由若干个盘片和一个磁头组组成
磁头组上呢
每一个磁头上有一个读写头
分别对应着盘片的正反面
我们可以在这里读写相应的数据
中间这些盘片
是围绕着磁盘轴进行旋转的
在这个旋转的过程当中
我们要读写的数据
是分布在各个盘片上的
这里磁道 柱面和扇区
这是我们要找的
每一块数据所在的位置
你在这里要读写磁盘上的数据
首先必须移动磁头
到达指定的位置然后读写
那我们看到在这里花时间最长的
是这个磁头的移动
这就是我们这里的寻道时间
定位到指定的磁道所需要花的时间
然后再有一个是旋转延时
也就是说中间这个盘片
它是一直在匀速旋转的
这个旋转不会因为
我想读的位置不同而有所改变
所以我们在这里要想找到指定的扇区
必须是等待它旋转
那这样一来我们基本上是说
在这里从当前位置
旋转到你想要的那个位置
这中间时间是我们这里的旋转延时
有了这个之后
那我们基本可以说
这个旋转延时基本上是转半圈的情况
也就是说我在任何一个位置开始
读到我想要的那个位置
那通常情况下中间平均的延时
是要转半圈的时间
这是磁盘的结构
和它相应的几个影响参数
下面我们来具体分析一下
磁盘I/O它的时间都花在什么地方
首先第一个是我要读写某个设备
我要等的这个设备是可以访问的
等待设备可用这是一段时间
然后第二个是等待
我这个设备要想跟它进行交流的话
DMA通道或者是I/O通道它必须可用
这是一个时间
这两个时间基本上
跟你实际的设备操作关系不大
然后是寻道时间
这相当于磁头移到指定的磁道
然后是旋转延时
最后我到了指定地方之后
我还有一个数据读出的时间
后面这三个时间
都会有机械动作
所以我们在这里
计算这个传输时间的时候
基本上是把这三个时间加在一起
这三个时间
加上前面这个通道的等待时间
这是我设备忙的状态
这是我们给出来的传输时间的公式
这是我最后算出来的访问时间
它由三个部分组成
实际上这是我们已经简化过的
一个是寻道时间就是中间这一段
然后是旋转延时
第一个寻道时间
跟你磁头移动的距离是相关的
那它花的时间是最大的
第二个旋转延时
基本上是说我们转的速度它的倒数
就是你转一圈的时间
那我们在这儿
基本上是平均时间是转一圈的一半
就是2r分之一
然后再有一个数据读取的时间
这是传输时间 这里头这个时间
它这几个参数是什么意思呢
就是要读多少个字节
你这一圈磁道上有多少个比特
然后你的转速是啥样的
这三个数rN分之B
就是你这里头传输的延时
从这个分析我们可以知道
我们主要需要优化的是TS
这个寻道时间
为了寻道时间的优化
这就是我们这里磁盘调度所要干的事
那它通过优化磁盘访问的顺序
来达到提高磁盘访问性能的目标
访问顺序如何来影响这个寻道时间呢
实际上我们有这样几条依据
第一个寻道是磁盘上最耗费的时间
所以我们有必要对它进行优化
如果这时间很短 那优化的空间不大
那我们就没有必要在这里
来做这个优化
然后再有一个我必须在同一个磁盘上
同时会有多个I/O请求
如果一个磁盘上只有一个
那你不管怎么优化
你都要到指定位置的
同时有多个我可以调整这个顺序
就好比说图书馆的管理员要去书库取书
它同时有多本书要取的时候
它可以看看这几本分布的位置
我优化出一条线路来
如果说你只有一本的话
那相当于我就直接去 直接回
没有什么好优化的
再有一个是随机进行磁盘的I/O请求
那这时候它的性能是很差的
基于这样几条
我们可以通过优化这个顺序
来优化磁盘的访问性能
具体说起来呢
我们在这里给出这样几种优化算法
第一种是FIFO先进先出
它就是按照请求的顺序
来顺序的进行处理
这个算法它是公平的
但是它在很多情况下
它的性能是不好的
接近于你的随机访问
那我们用一个例子来说
它是在怎么访问
在这个例子给了一个访问的序列
并且约定了我磁头当前的位置
来按照FIFO的做法
看看它总共磁头移动的距离是多少
我们要优化的目标
就是这个移动的距离
当前位置是53
我第一个是98
第一个要移动53到98
这时候移动了45个单位的距离
这样的话一个一个移动下去
到最后
到这个地方我到67
我总共加在一起
它总和是640个单位
那我们看到这来回左移右移
实际上走了很多的冤枉路
这种做法呢它的性能是很差的
我们首先想到的第一个优化是什么
我就近
离的这后面这一段里
哪一个最近我按哪一个
这就是我们下一种做法
最短服务时间优先
在这里头呢
它依据磁头当前的位置
来找移动最少的那个I/O请求
所在的位置
这时候总是找最短寻道时间的
当前寻道最短的那个
那我们还是以刚才这个例子来说
在这个序列里头
我们仍然是这个序列
仍然是这个当前位置
我们看按最短寻道时间优先
它的结果是啥样的
我们在这儿53
离它最近的是哪个 是65
然后67 最后两个
然后67之后再往哪
37是离它最近的
然后这样一直走下去到最后
最后到哪 到这个地方 183
是它最后一个
这时候236和我们刚才的640
差不多差了接近3倍
那这时候我们看到这种做法
比刚才那个又有了很大的优化
原因在于刚才那个根本就没有考虑到
它的位置分布情况
这个做法是不是还可以优化呢
那我们再有第三种做法 扫描算法
它的做法是在一个方向上进行移动
一直到所有的访问全部完成
然后直到到达磁头的最后一个磁道
这种做法呢
它主要是因为我们在磁盘上
磁头是两个方向来回移动
哪些地方会是优待呢
中间那一部分会是优待
所以我沿一个方向走到头
然后再到另一个方向
这样一来的话
我换方向之后 再从那头扫回来
这种做法有点类似于
我们电梯里的控制算法
电梯的话
它是从最顶上到最底下
然后再从最底下到最顶上
这是我们这里的扫描算法
我们用扫描算法再来试一下
刚才那个序列
同样的序列 同样的起点
但这时候起头有一个方向的假定
我们在这儿
假定是往编号低的方向走
这时候我沿路扫到头
一直有多少个我就扫到那儿
这样一来的话基本上我转一圈
是从第一个到最后一个
200个单位这样的距离
也就是说极端的情况
如果说你是从最头上开始
不管你中间有多少个请求
它移动的距离就应该是不超过200
从这个角度来说这个算法呢
它的性能也是不错的
在我们这儿看到
它算出来和我们刚才那个
最短寻道时间优先的算法
的结果是一样的
这种做法它的特点是
我沿着一个方向走 顺序扫过去
这个地方我的判断会比较简单
不像刚才那个
我需要去找到底哪一个是最近的
每一次找的时候呢
都要来挨个去算一遍
我在这儿沿着一个方向就可以了
与此同时这种做法有一个问题
就是在于中间这些磁道
我会有更好的访问性能
而两头我到的时间会比较少
所以在这儿又有一种变化
叫做循环扫描
它仅在一个方向进行扫描
另一个方向呢是直接走到头
这种做法呢
它主要的目的是为了提高它的公平性
那我们看
刚才说你把从一个方向走到头
最外头那个地方
即使没有你要访问的I/O请求
你也要走到头
这个实际上是不合算的
所以在这儿就有一个C-Look
它和我们刚才说的扫描算法
唯一的区别就在于
它只是走到最后一个请求的位置
它不走到头 然后就折返了
其它的跟循环扫描算法是一样的
这样的话它就可以提高它的公平性
然后在这基础上我们还会再有两种优化
这就是N步扫描和双队列扫描算法
N步扫描算法实际上
想对付的问题是什么呢
是说由于我在扫描算法里头
我是考虑后面这些请求
哪个离我最近
如果说你总是在当前磁头
所在位置的边上有请求
在这个位置的请求就会优先响应
但这种优先响应
就会使另外一些请求
得不到访问的机会
这就是我们这里的磁头粘着现象
这时候呢
我们怎么来解决这个问题呢
你比如说在这里刚才我们说的
进程反复请求某一磁道的I/O操作
它就会长时间的停到这儿
对其它的后续的请求
等待延时就会非常长
为了减少这种某些情况速度很快
在另外一些情况下性能很差这种情况
有了N步扫描
它的做法是什么呢
它的做法是把磁盘请求
分成N个子队列
每次按照先进先出的顺序
来处理所有的子队列
也就说子队列我是按照先来后到的顺序
但是在每一个队列内部我用扫描算法
这就是我们这里的N步扫描算法
那这种算法呢又有一个小变种
就叫双队列扫描算法
它和前面的做法的区别是在于
我只分两个队列
某种角度上讲
你认为是N步扫描算法的一个简化
这种简化完了之后呢
我分成两个队列
交替使用扫描算法处理每一个队列
在处理一个队列的时候呢
当前新到达的请求就放在另外一个
没有进行处理那个队列里头
用这种办法呢
我就让这些请求有一个最长的等待时间
也就是说当前处理的这些
处理完了之后我再会去处理新的请求
从这个角度来讲呢
我的平均等待时间就会减少
这是我们对磁盘调度的一个简要介绍
-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
