一、磁盘结构
一个磁盘的盘面被分为一圈圈的磁道,一个磁道又被分为一个个扇区,每一个扇区就是一个磁盘块。每个扇区存放的数据量相同。
一个盘面的磁道大概有几千到几万条。
最中间的白色同心圆放着一个马达用来转动盘面,另外还有可移动的磁头。磁头只能在同一扇区内的不同磁道上移动,只有马达转动盘面才可以让磁头到达另一个扇区的磁道。
让目标扇区从磁头下面划过,才能完成对扇区的读/写操作。
一个磁盘包含多个盘面,通过一个盘臂组装在一起。盘臂长着多个磁头,每个盘面对应一个磁头。所有的磁头都 是连在同一个 磁臂上的,因此所有磁头只能“共进退”。但磁盘只读取/写入某一个激活了的磁头所划过的地方。
所有盘面的相同磁道(如下图黄色的磁道)组成柱面。
一个物理块号实际上由是一个(柱面号,盘面号,扇区号)的三元组信息定义的。块号可以转换成(柱面号,盘面号,扇区号) 的地址形式。
还有一种固定头磁盘,它的每个盘面的每个磁道都有一个磁头,磁头无法移动:
二、磁盘调度算法
一次磁盘读写操作所需的时间 = 寻道时间 + 延迟时间 + 传输时间
寻道时间是磁头在同一列扇区的不同磁道间的移动,移动到目标磁道的时间,延迟时间是马达转动盘面使磁头指到数据开始的块的时间,一个块的传输时间是马达转动盘片使磁头从块开头划到块结尾的时间。
寻找时间(寻道时间)TS:在读/写数据前,将磁头移动到指 定磁道所花的时间。它又包括:
①启动磁头臂是需要时间的。假设耗时为 s;
②移动磁头也是需要时间的。假设磁头匀速移动,每跨越一 个磁道耗时为 m,总共需要跨越 n 条磁道。
则:
寻道时间 TS = s + m*n
延迟时间TR:通过旋转磁盘,使磁头定位到目标扇区所需要的时间。设磁盘转速为 r (单位:转/秒,或 转/分),则平均所需的延迟时间是转二分之一圈的时间 TR = (1/2)*(1/r) = 1/2r
传输时间Tt:磁头从磁盘读出/写入数据的开始位置划到结束位置所经历的时间,假 设磁盘转速为 r,此次读/写的字节数为 b,每个磁道上的字节 数为 N。则:传输时间Tt = (1/r) * (b/N) = b/(rN)
延迟时间和传输时间都与磁盘转速有关,且为线性相关。而转速是硬件的固有属性,因此操作系统也无法优化延迟时间和传输时间,只能优化寻道时间,也就是说它只能优化磁头跨越磁道的条数。
下面介绍具体的磁盘调度算法,假设磁头的初始位置是100号磁道,有多个进程先后陆续地请求访问 55、58、39、18、90、160、 150、38、184 号磁道。
1、先来先服务(FCFS)
根据进程请求访问磁盘的先后顺序进行调度。
按照 FCFS 的规则,按照请求到达的顺序,磁头需要依次移动到 55、58、39、18、90、160、150、 38、184 号磁道。
磁头总共移动了 45+3+19+21+72+70+10+112+146 = 498 个磁道
响应一个请求平均需要移动 498/9 = 55.3 个磁道(平均寻找长度)
优点:公平;如果请求访问的磁道比较集中的话,算法性能还算过的去
缺点:如果有大量进程竞争使用磁盘,请求访问的磁道很分散,则FCFS在性能上很差,寻道时间长。
2、最短寻找时间优先(SSTF)
SSTF 算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短,但是并不能 保证总的寻道时间最短。(其实就是贪心算法的思想,只是选择眼前最优,但是总体未必最优)
假设磁头的初始位置是100号磁道,有多个进程先后陆续地请求访问 55、58、39、18、90、160、 150、38、184 号磁道
磁头总共移动了 (100-18) + (184-18) = 248 个磁道
响应一个请求平均需要移动 248/9 = 27.5 个磁道(平均寻找长度)
优点:性能较好,平均寻道时间短
缺点:可能产生“饥饿”现象
Eg:本例中,如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求,处理38号磁道 的访问请求时又来了一个18号磁道的访问请求。如果有源源不断的 18号、38号磁道的访问请求 到来的话,150、160、184 号磁道的访问请求就永远得不到满足,从而产生“饥饿”现象。
产生饥饿的表现在 于:磁头在一个小区域内来回来去地 移动。
3、扫描算法(SCAN)
SSTF 算法会产生饥饿的原因在于:磁头有可能在一个小区域内来回来去地移动。
为了防止这个问题, 规定只有磁头移动到最外侧磁道的时候才能往内移动,移动到最内侧磁道的时候才能往外移动。这就是扫描算(SCAN)的思想,也叫电梯算法。
磁头总共移动了 (200-100) + (200-18) = 282 个磁道
响应一个请求平均需要移动 282/9 = 31.3 个磁道(平均寻找长度)
优点:性能较好,平均寻道时间较短,不会产生饥饿现象
缺点:①只有到达最边上的磁道时才能改变磁头移动方向,因此会造成多余的磁道跨越。
②SCAN算法对于各个位置磁道的响应频率不平均,两边的磁道响应快,中间磁道慢(如:假设此时磁头正在往右移动,且刚处理过 90号磁道,那么下次处理90号磁道的请求就需要等磁头移动很长一段距离;而响应了184号磁道 的请求之后,很快又可以再次响应 184 号磁道的请求了)。
为了解决这两个缺点,提出了C-LOOK调度算法。
4、C-LOOK 调度算法
该算法是 边移动边观察算法(LOOK算法)和 循环扫描算法(C-SCAN算法)的结合。
如果在磁头移动方向上已经没有别的请求,就可以立即改变磁头移动方向,这就是LOOK算法的思想。
只有磁头从盘片的圆心磁道到边缘磁道方向移动时才处理磁道访问请求,而从边缘磁道返回到圆心磁道的过程直接快速移动至起始端而不处理任何请求。这就是C-SCAN算法的思想。
C-LOOK算法思想则是如果磁头移动的方向上已经没有 磁道访问请求了,就可以立即让磁头返回,返回的过程不处理请求,并且磁头只需要返回到有磁道访问请求的位置即可。
三、减少延迟时间的方法
假设要连续读取橙色区域的 2、3、4扇区:
磁头读取一块的内容(也就是一个扇区的内容)后,需要一小段时间处理,而盘片又在不停地旋转,也就是说相邻扇区的内容无法立刻读入。
因此,如果2、3号扇区相邻着排列,则读完2号扇区后无法连续不断地读入3号扇区。 必须等盘片继续旋转一圈, 3号扇区再次划过磁头,才能完成扇区读入。
如此一来需要转2圈才能成功读取2、3、4扇区的块。
结论是:磁头读入一个扇区数据后需要一小段时间处理, 如果逻辑上相邻的扇区在物理上也相邻,则读入几个连 续的逻辑扇区,可能需要很长的“延迟时间”。
为了解决这个问题,可以对扇区进行交替编号,让逻辑上相邻的扇区在物理上有一定 的间隔,可以使读取连续的逻辑扇区所需要的延迟时间更小。
此外不同盘面的扇区编号需要交错,也就是0号盘面的1号扇区的正下方不能对着1号盘面的1号扇区。这也是为了逻辑上相邻的扇区在物理上不能相邻。如下方所示用二进制表示柱面、盘面和扇区,如果需要读取 从(000, 00, 111)到(000, 01, 000)这2个盘块,这两个盘块位于两个盘面上,假如刚读完0号盘面的7号扇区(二进制111),接着磁头就刚好指到了1号盘面的0号扇区,但由于处理数据需要时延,所以无法马上读取这第二个盘块。最终还是需要转两圈才能读完这两个块。
采用不同盘面的扇区交错编号可以避免这个问题。
四、随机IO和顺序IO
首先我们知道磁头定位(磁头寻道)是磁盘操作成本最高的部分。
顺序IO是指读写的多个块在物理上是连续的,具体的物理表现为要读写的多个块在磁盘的同一磁道上(或者相邻磁道的扇区),磁头无需多次寻道(磁头不用移动或只用移动一丢丢)即可读写这些块。
随机IO就是多个块在物理上是离散存储的,具体的物理表现为要读写的多个块在磁盘的多个不同的磁道上,磁头需要多次寻道才能读取他们。
因此如果操作系统某个时刻瞬间发出的n次磁盘IO操作是顺序IO(具体是有序的读取多个连续的块,一次IO一个块),它会很快的完成,甚至能合并为1次IO操作。如果随机IO,由于需要寻道,因此会比顺序IO慢。
所以同样是n次IO,顺序的多次IO比随机的多次IO要快很多。
五、磁盘初始化、引导块和坏块
磁盘初始化
Step 1:进行低级格式化(物理格式化),将磁盘的各个磁道 划分为扇区。
Step 2:将磁盘分区(安装操作系统前做的事),每个分区由若干柱面组成(即分为我们 熟悉的 C盘、D盘、E盘)。
Step 3:进行逻辑格式化,创建文件系统。包括创建文件系统 的根目录、初始化存储空间管理所用的数据结构(如位示图、 空闲分区表)。
引导块
计算机开机时需要进行一系列 初始化的工作,这些初始化工 作是通过执行初始化程序(自 举程序)完成的。而自举程序就写在磁盘的某些固定的引导块中。
拥有启动分区(引导分区)的磁 盘称为启动磁盘或 系统磁盘(C:盘)。
坏块
坏了无法正常使用的扇区就是 “坏块”。这属于硬件故障,操作 系统是无法修复的。应该将坏块标 记出来,以免错误地使用到它。有时候操作系统提供的修复磁盘的功能其实不是真的修复磁盘的坏块,而是记录磁盘的坏块,使得系统存储文件时避开这些坏块。