操作系统-课堂笔记-磁盘调度(南航)
文章目录
存储管理-磁盘调度
CHS寻址 磁道:盘面:扇区
工作原理
- CHS全称:Cylinder-Head-Sector即柱面(磁道)/盘面/扇区 寻址方式,是早期IBM PC架构上用来进行磁盘寻址的方法。
- 来张图
- 下面分别介绍C, H, S
- 首先是C:Cylinder译为柱面,也可以译为磁道,示意图见上图。
- H:Head译为磁头也可以理解成盘面(含义是相同的),上图所示,现在只需要知道一个盘面一般有上下两面,分别对应一个磁头,即一个盘面对应2个磁头,可以称为上盘面磁头和下盘面磁头。
- S:Sector译为扇区,上图所示,扇区是硬盘寻址的最小单位,一般一个扇区保存512字节,这个记忆下来就好。
现在明白了什么是CHS,那么我们到底是怎么控制磁头,从而能让这种寻址方式跑起来,帮助我们找到要找的数据呢?
- 还是看要看上面的图:上图可以看出,每个盘面是中空的,其实中间是一个控制转轴, 其目的是让各个盘面高速旋转起来,目前主流硬盘旋转速度有5400转/min和7200转/min,单位是每分钟哦~好的,现在盘面已经转起来了。
- 现在我们假设磁头不动,盘面在转,那么磁头就能遍历一整个磁道,即可以访问整磁道上的数据。
- 那么问题来了,怎么能让我的磁头访问到整个盘面的数据呢?聪明的你一定想到两种方案,一是让磁头动起来,在半径方向上移动,二是多装一些磁头,使磁头覆盖整个半径。很显然前者是一种比较划算的实现方式,后者我个人认为是完全可行的方案,而且还能大大提高访问速度。不过目前市场上的硬盘都是方式一,方式二实现起来可不能很不划算。
- 让磁头在半径方向上移动起来,并且配合盘面的高转速,现在我们就能够访问整个盘面上的数据了。
相关计算
现在我们已经明白什么是CHS,以及CHS的基本工作原理,那么下面就进行一些计算。
CHS的组成:
- 一共24个比特位(最传统的实现,还有28位的实现,这里我们只讨论24位的)
- Cylinder 10位 — 210=1024个磁道,即一个盘面可以被划分成1024个同心圆
- Head 8位—28=256个磁头,有256个磁头意味着可以寻址256个盘面
- Sector 6位—26=64个扇区,即一个柱面有64个扇区
- 最大寻址空间的计算:现在就很容易计算了,能寻址256个盘面,一个盘面可以分割成1024个磁道,一个同心圆又有64个扇区,那么我现在就有 1024x256x64=16K个扇区了
- 要想计算存储空间还得知道一个扇区能保存多少字节的内容,这里硬记下来就好,一般一个扇区保存512B,那么16Kx512=8G(224x29=233),现在就算明白了。
其实上面的计算不太对,原因如下:
- 越靠近圆心的磁道其周长越小,那么扇区数就会越小。
- 上面的计算忽略了上述圆的特性,只是一个示例计算,其结果是不对的。
问题来了,我们算出来最大寻址8G,现在很多硬盘都1T是怎么回事?
- 首先CHS经过一次扩展,从24位扩展到28位,那也只能寻址128G,所以后来出现了LBA
注意事项
BIOS int 0x13调用是和读磁盘相关的,需要注意的是CHS寻址的单位是磁道,而不是盘面。笔者在读Linux0.11内核源码时遇到与此相关的内容,思考了好久,发现之前理解错了。
为什么现代OS不使用CHS呢?
- 早期OS也使用CHS寻址方式
- 技术发展后,不同磁道的扇区数不同
- 地址位数确定后,容量不容易扩展
LBA寻址
LBA简介
LBA:Logical Blokc Address
- 寻址的基本单位是块(block)
- 地址线性增长:0,1,2,3,…
- 块的大小是扇区大小的整数倍:一般为4K!
- 在OS看来,一块磁盘可以当作block类型的一维数组
LBA的出现是用来取代CHS的,那么LBA是如何寻址的呢? - LBA是一个整数,通过转换,成为CHS格式完成磁盘寻址。
- LBA采用48个比特位寻址,最大寻址空间位128PB
- 即LBA将CHS这种三维寻址转变成一维的线性地址,所谓一维即扇区号
相关计算
其实LBA与CHS相关计算的思路很简单,举个例子,现在有一个三维数组a[4][3][2],那么请问这个数组里有多少元素呢?很简单432=24,这就是一个三维到一维的转换。
那么再来一个问题,我问a[2][2][1]是第几个元素:计算方法:232+2*2+1-1
同理LBA的计算公式(与上式对比容易理解):
LBA=磁头数(盘面数)x 每磁道扇区数 x 当前柱面号 + 没磁道扇区数 x 当前所在磁头号 + 当前所在扇区号 - 1
例如CHS=0/0/1,那么LBA=255630+63*0+1-1=0,即 0柱面,0磁头,1扇区,是逻辑 0扇区。
磁盘(磁臂)调度算法
为什么需要磁盘调度算法?回想下从磁盘上读写数据的过程:
- 移动磁头到指定磁道上—寻道时间
- 等待磁盘旋转,直到需要读写的扇区在磁头下面—旋转延迟时间
- 传输数据—把数据从磁盘读出或写入
- 其中前两者的耗时比较长
- 磁盘调度问题的目的是减少寻道时间
- 更确切的说是:磁臂调度问题
磁臂调度算法分类:
- 先来先服务
- 最短寻道时间优先
- 电梯调度算法
- 循环扫描算法
先把题目给出来,便于后面讨论:
假设给定一组磁盘读写请求访问的磁道号是:55,58,39,18,90,160,150,38,18
- 当前磁头处于100号磁道上
问应当如何满足这些访问磁盘的请求,使得:
- 磁道的移动距离尽量短
- 尽量公平(至少不发生饿死)
1.先来先服务
是一种简单、公平、低效的方法:
访问顺序是:55,58,39,18,90,160,150,38,18
磁臂移动距离:45+3+19+21+72+70+10+112+20
2.最短寻道时间优先
是一种高效、不公平(磁臂容易停留在中间区域)
访问顺序是: 90,58,55,39,38,18,150,160,184
每次都找距离本磁道最近的磁道访问
磁臂移动距离:10+32+3+16+1+20+132+10+24
3.电梯调度算法
沿着某个方向移动,直到该方向没有请求,逆转方向
访问顺序:150,160,184,90,58,55,39,38,18
磁臂移动距离:50+10+24+94+32+3+16+1+20
4.循环扫描算法
只沿一个方向移动(没有逆转操作),移动到最边缘,直接返回最开始的地方
- 是一种折中的方案,能降低最坏情况下的时延
访问顺序:150,160,184,18,38,39,55,58,90
磁臂移动距离:50+10+24+166+20+1+16+3+32
思考一个问题:磁臂调度算法在何处实现?
- 驱动程序?
- 中断处理程序?
- 硬件设备?
驱动程序!
如果觉得写的不错,对你有帮助,点个赞鼓励一下叭!