磁盘

磁盘调度算法

显然对于一个磁盘数据的读/写序列（中途可能会更新）使用不同的调度算法会产生不同的效率，这里我们也探讨一下几种不同算法的性能，那么指标肯定就是时间了所以我们先介绍几个指标概念然后介绍调度算法。

一次磁盘读/写操作需要的时间

寻道时间Ts

寻道时间Ts：又称为寻找时间，在读/写操作之前，将磁头移动到指定磁道所花费的时间。

启动磁头臂是需要时间的。假设耗时为s。
移动磁头也是需要时间的，假设磁头均匀移动，每跨越一个磁道耗时为m，总共需要跨越n条磁道，则：
$T_s=s+m*n$
现在的硬盘移动一个磁道大约需要0.2ms,磁臂启动时间约为2ms。

延迟时间Tn

延迟时间Tn:通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r(单位:转/s，转/min)，那么平均所要的延迟时间为

T_n=(1/2)*(1/r)=1/2r

1/r就是转一圈所需要的时间，找到目标扇区平均需要转半圈，因此再乘1/2，硬盘的典型转速为5400转/min，或者7200转/min。

传输时间Tt

传输时间Tt:从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N，则：

T_t=(1/r)*(b/N)=b/rN

每个磁道可存N字节的数据，因此b字节的数据需要b/N个磁道才能存储，而读/写一个磁道所需要的时间刚好又是一圈所需要的时间1/r。

总的平均时间Ta

Ta=Ts+Tn+Tt=s+m*n+1/2r+b/rN

延迟时间Tn和传输时间Tt都与磁盘的转速有关，且为线性关系，而转速是硬件的固有属性，因此操作系统无法优化延迟时间和传输时间。

先来先服务算法（FCFS)

根据进程请求访问磁盘的先后顺序进行调度。例如：假设磁头的初始位置为100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道，那么按照FCFS的规则，按照请求的顺序，磁头需要一次移动到55、58、39、18、90、160、150、38、184号磁道。

磁头一共移动了45+3+19+21+72+70+10+112+146=498个磁道。响应一个请求平均需要移动489/9=55.3个磁道。（平均寻找长度）。

优点：公平，如果请求访问的磁道比较集中的话，算法还可以。

缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，那么FCFS在性能上很差，寻到时间长。

最短寻找时间优先（SSTF）

SSTF算法优先处理的是离当前磁头最近的磁道，可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。其实就是贪心思想，贪心解未必是最优解。

例如：假设磁头的初始位置为100号磁道，有多个进程先后陆续地请求访问55、58、39、18、90、160、150、38、184号磁道：

磁头总共移动了(100-18)+(184-18)=248个磁道，响应一个请求平均移动248/9=27.5个磁道（平均寻道长度）

优点：性能好，平均寻道时间短

缺点：可能产生饥饿现象

扫描算法（SCAN）

SSTF产生饥饿的原因是磁头有可能会在一个小区域内来回的移动，为了防止这个问题，可以规定，只有磁头移动到最外侧的磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法（SCAN）的思想。由于磁头移动方式很像电梯，因此也叫电梯算法。

假设某磁道为0~200号，磁头的初始位置是100号，此时磁头正在往磁道号增大的方向移动，那么此时有多个进程的请求访问：55、58、39、18、90、160、150、38、184号磁道。

一定要注意必须移动到磁道最边缘处才可以更改移动方向即使没有请求访问最边缘磁道也要经过。

磁头总共移动了（200-100）+（200-18）=282个磁道，响应一个请求平均需要282/9=31.3个磁道（平均寻道长度）。

优点：性能好，平均寻道时间短，不会产生饥饿现象

缺点：①只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。②SCAN算法对于各个位置磁道的响应频率不均匀（如：假设此时磁头正在向右移动，且刚处理过90号磁道，那么下次处理90号磁道的请求就需要等磁头移动很长一段距离，而相应了184号磁道的请求之后，很快又可以再次相应184号磁道的请求了）

LOOK调度算法

扫描算法（SCAN）：只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了184号磁道的访问请求之后就不需要再往右移动磁头了。LOOK算法就是为了解决这个问题，如果在磁头移动方向上没有别的请求，就可以立即改变磁头移动方向。（边移动边观察，因此叫LOOK）

假设某磁道的磁盘为0~200号，磁头的初始位置为100号磁道，且此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的请求访问55、58、39、18、90、160、150、38、184号磁道。

那么响应一个请求平均寻道长度为250/9=27.5磁道

优点：比起SCAN算法来，不需要每次都移动到最外侧或最内侧时才改变磁头方向，使寻道时间进一步缩短。

缺点：只解决了SCAN算法的缺点1，响应频率还是不均匀。

循环扫描算法（C-SCAN）

SCAN算法对于各个位置磁道的响应频率不平均，而C-SCAN就是解决了这个问题。规定只有磁头向右移动或者向左移动时才可以处理磁道访问请求，而返回时直接快速移动到起始端中间返回过程不做任何请求任务。

假设某磁盘的磁道为0~200号，磁头的初始位置为100号磁道，且此时磁头正在向磁道号增大的方向移动，那么有多个进程陆续的请求访问55、58、39、18、90、160、150、38、184号磁道。

优点：比起SCAN算法，对于各个位置的响应频率很平均

缺点：只解决了SCAN算法的缺点2，但是还是只有到达最边缘的磁道才可以返回到起始端。

C-LOOK调度算法

C-SCAN算法的主要缺点是只有到达最边缘的磁道才可以返回到起始端，但是我们也可以模仿LOOK算法边移动边观察，当后面没有更大的请求磁道号时就不用再移动到最边缘了，直接返回到起始端节省开销。

优点：比起C-SCAN算法来，不需要每次移动到最外侧或者最内侧才改变刺头方向，同时响应频率也很均匀。

缺点：也不算是缺点，就是没必要，因为边移动边观察看似节省开销了实际上实现起来开销也不必C-SCAN小多少。

总结

减少延迟时间的方法

我们知道延迟时间就是磁头等待到目标扇区的时间，那么磁盘扇区的不同排列方式也会对延迟时间造成影响。

如果排列如下：

那么假设现在要连续读取橙色区域的2,3,4区域，那么磁头读取一块的内容（也就是一个扇区的内容后）需要一小段的处理时间，而此时盘片还在不停地旋转。因此如果2,3号扇区相邻着排列，则读完2号扇区后无法连续不断的读入3号扇区。必须等待盘片继续旋转，3号扇区再次滑过磁头，才可以完成扇区读入。所以我们可以得到如下结论：磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，那么读入几个连续的逻辑扇区，可能需要很长的延迟时间。

减少延迟的方法：交替编号

很明显，此时采用交替编号后，逻辑相邻的磁盘块物理结构上并不是相邻的，这样可以使读取连续的逻辑扇区所需要的延迟时间更小。

磁盘结构的设计

我们思考一个问题，为什么在设计磁盘的物理地址时使用的表示方法为（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）？这里的原因如下：

假设现在某个磁盘有8个柱面即8个磁道（且最内侧磁道编号为0），4个盘面，8个扇区。那么可以用3个二进制位表示柱面，2个二进制位表示盘面，3个二进制位表示扇区。

那么如果物理地址是（盘面号，柱面号，扇区号）来表示，那么如果现在需要连续读入物理地址（00,000,000）~（00,001,111）的扇区。那么（00,000，000）~（00,000,111）转两圈即可读完，之后在读取物理地址相邻的区域即（00,001,000）~（00,001,111）的时候需要启动磁头臂，将磁头移动到下一个磁道。

而如果是物理地址结构为（柱面号，盘面号，扇区号），且需要连续读入物理地址为（000,00,000）~（000,01,111）的扇区时，由于都在柱面为000的位置，所以不需要移动磁臂，只是在读入(000,01,000)~(000,01,111)时需要激活1号盘面的磁头即可。所以如果是（盘面，柱面，扇区）这种物理地址结构读入连续的物理地址时也需要不断的移动磁头，但是如果是（柱面，盘面，扇区）时就只需要激活不同盘面的磁头即可，无需移动磁臂，这样可以减少磁头移动消耗的时间。

减少延迟的方法：错位命名

如果按照上面这样命名，即不同盘面的相对位置处编号相同，那么假设要连续读入物理地址为(000,00,000)~(000,01,111)时当读取完磁盘块（000,00,111）之后需要短暂的时间处理，而盘面又在不停地旋转，那么当（000,01,000）第一次滑过1号盘面的磁头下方时，并不能读取数据，只能再等扇区再次滑过磁头。所以我们可以错位命名如下：

即此时的两个盘面相对位置处的编号都有错位。那么就可以做到当读取完磁盘块（000,00,111）之后，还有一段时间处理，当（000,01,000）第一次滑过1号盘面的磁头下方时，就可以直接读取数据了，从而减少了延迟时间。

思考：交替编号和错位命名的区别？

首先交替编号和错位命名是两种策略，他们相互配合减少了磁盘读/写的时间开销。交替编号是针对某一个盘面的编号来说的，使得每一个盘面的编号的交替的。而错位命名是针对的不同盘面之间编号的，使得每一个盘面编号相同的扇区在不同的相对位置，使得切换盘面有一定的时间缓冲可以立刻读取下一个相邻的物理地址。

总结

磁盘的管理

磁盘初始化

分为如下几个步骤：

进行低级格式化（物理格式化），将磁盘的各个磁道划分为扇区。一个扇区通常可分为头、数据区域（如512B大小）、尾三个部分组成。管理扇区包括各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验码，CRC循环冗长验证码等，校验码用于校验扇区中的数据是否发生错误）
将磁盘分区，每个分区由若干柱面组成（即分为C,D,E盘等）

我们可以看出越靠近里面的盘数据密度也就越大。
进行逻辑格式化，创建文件系统。包括创建文件系统的根目录，初始化存储空间管理所用的数据结构（如位示图法、空闲分区表等）

引导块

计算机在开机时需要进行一系列初始化工作，这些初始化工作通过执行初始化程序（自举程序）完成的。

初始化程序可以放在ROM中（只读存储器）中，ROM中的数据在出厂时就写入了，并且以后就不可以修改了（ROM一般是出厂时就集成在主板上）。

思考：自举程序放在ROM中存在什么问题？

我们发现当需要更新自举程序时就会很不方便，因为ROM中的数据结构无法更改。所以我们需要解决此问题。

我们可以考虑不将自举程序放入ROM，而是在ROM中存放很小的“自举装入程序”，开机时计算机先运行“自举装入程序”，通过执行该程序就可以找到引导块，并将完整的“自举程序”读入内存，完成初始化。而完整的自举程序放在了磁盘的启动块（即引导块/启动分区）上，启动块位于磁盘的固定位置。拥有启动分区的磁盘称为启动磁盘或系统磁盘（一般我们的计算机中都是C盘）。

坏块的管理

对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明那些是坏扇区比如在FAT表上标明（在这种方式中，坏块对操作系统不透明）。对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部位）会维持一个坏块链表。在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。当然也可以保留一些备用扇区用于替换坏块。这种方案称为扇区备用，且这种处理方式中，坏块对操作系统透明。我们这里介绍几种策略：

RAID0

RAID0又称为Stripe或者Striping,他代表着所有RAID级别中最高性能的存储性能。RAID0的原理就是把连续的数据分散到多个磁盘上存取，这样当系统有数据请求时就可以多个磁盘并行的执行，每一个磁盘运行属于它自己的那部分数据请求。这种并行操作请求的方法显著提高了存储性能。并且磁盘的读/写操作也会提高，假设RAID0将某一个请求分成了三个部分，那么每个磁盘只运行自己的那部分任务，那么理论上运行速度会提升为原来的3倍，但是由于总线带宽等影响，会低于理论值，但是也明显提升了速度。

虽然优点显著：读写，存储性能极高，但是缺点是不提供数据冗余，一旦用户数据损坏，损坏的数据将不能再恢复。所以RAID0中只要有一个硬盘损坏，整个RAID0设备都不能使用，所以可维护性极差。

磁盘空间使用率：100%，故成本最低。
读性能：N*单块磁盘的读性能
写性能：N*单块磁盘的写性能
冗余：无，任何一块磁盘损坏都将导致数据不可用

RAID1

其实就是镜像备份了，这样就实现了数据冗余，在成对的独立磁盘上产生互相备份的数据。当原始数据繁忙时，可以镜像拷贝读取数据，所以读取性能提高了。并且由于每一个盘都有镜像备份，所以磁盘阵列中单位成本很高。但是也提供了数据的安全性和可用性，当一个磁盘损坏失效，系统可以快速切换到备份的镜像磁盘上读写，不会立刻停止工作。当然两个都损坏了也是无法工作的，但概率太小。所以RAID1中总是有一个保持完整数据的备份盘，可靠性更好。

细节：读写数据的区别？

一定要注意RAID1中读只能在一个磁盘上进行，即要不在DRIVE1BlockX读，要不在DRIVE2BlockX读,只是在DRIVE1BlockX忙碌时暂时无法提供读数据的时候，DRIVE2BlockX可以替DRIVE1BlockX提供读，但是总体上看只能一个盘提供，所以读的时候是不能并行执行的。而写磁盘的时候可以并行的对两个磁盘进行写，毕竟他们的数据应该是一样的（备份盘和原盘数据必须一致），但是虽然是并行写操作，但是因为要比较硬盘中的数据，所以写数据性能还是比单块磁盘慢。

磁盘空间使用率：50%，故成本最高。
读性能：只能在一个磁盘上读取，取决于磁盘中较快的那块盘
写性能：两块磁盘都要写入，虽然是并行写入，但因为要比对，故性能单块磁盘慢
冗余：只要系统中任何一对镜像盘中有一块磁盘可以使用，甚至可以在一半数量的硬盘出现问题时系统都可以正常运行

RAID10

其实可以看出特点，就是RAID1和RAID0的组合，对于整体来看组合是RAID0而局部看来每一个不分都是RAID1这样的好处是，整体上的读写性能很好，并且也不容易损坏因为每一个部分都有备份盘即使损坏了也可以立刻用备份盘替换。

磁盘空间利用率：50%
读性能：N/2*单块硬盘的读性能
写性能：N/2*单块硬盘的写性能
冗余：只要一对镜像盘中有一块磁盘可以使用就没问题

思考：为什么不是RAID01组合？

即整体看来是RAID1，而局部看来每个部分都是RAID0我们发现整体看性能写很慢，读还可以，但是只要有2个局部损坏任意一个分盘都是整体都不能在使用了，性能一般且成本昂贵不易于维护😅。所以这个组合不适用。

RAID5

RAID 5是RAID 0和RAID 1的折中方案。RAID 5具有和RAID0相近似的数据读取速度，只是多了一个奇偶校验信息，写入数据的速度比对单个磁盘进行写入操作稍慢。同时由于多个数据对应一个奇偶校验信息，RAID5的磁盘空间利用率要比RAID 1高，存储成本相对较低，是目前运用较多的一种解决方案。当然我们发现每一组类型的盘都有一个备份盘随时准备顶替损坏的磁盘工作，并且备份盘每一个都分布在不同的disk上，而相应的有备份盘的disk就么有哪一种类的工作原盘。这样既便于维护整体性能也还不错，当有一个盘损坏时也可以继续工作，当然仅限于坏掉一个，当再坏掉一个或者备份盘先坏掉此时又有盘坏掉时也是会停止工作的。

磁盘空间利用率：(N-1)/N，即只浪费一块磁盘用于奇偶校验
读性能：(n-1)*单块磁盘的读性能，接近RAID0的读性能。
写性能：比单块磁盘的写性能要差
冗余：只允许一块磁盘损坏

以上内容来自大佬博客