OS_theory_6

磁盘的结构

可用(柱面号，盘面号，扇区号) 来定位任意一个“磁盘块”。

文件的物理结构中文件数据存放在外存中的块号就可以转换成(柱面号，盘面号，扇区号)的地址形式。

磁盘调度算法

减少磁盘延迟时间的方法

磁盘的管理

磁盘管理

磁盘介绍

基本概念

• 扇区(Sector):盘片被分为若干个扇区
• 磁道(Track):盘片上以盘片中心为圆心,不同半径的同心圆环
• 柱面(Cylinder):磁盘中,不同盘片相同半径的磁道组成的圆柱
• 磁头(Head):每个磁盘有两个面,每个面一个磁头

定位一个扇区需要三个信息:柱面号,磁头号,扇区号

磁盘结构

磁盘实际扇区数比硬盘标签上标定的大,其中一部分用于存储硬盘的固件(硬盘控制器使用)
一部分是用户存储数据的区域,即工作区,也就是硬盘标定容量的扇区.
剩下的是保留区,超过在固件里定义的硬盘容量的那些扇区就称为保留扇区.
对于坏扇区(不管是生产缺陷,还是使用过程中磁介质老化缺陷),都存在一张表用于映射坏扇区到空闲扇区.对于生产缺陷,这张表叫 P 表,对于老化缺陷,这张表叫 G 表.

磁盘参数

• 寻道时间:
  $Ts=m∗n+s$ (m是一个常数,可以认为是磁道的移动速度)
  把磁头从当前位置移动到指定磁道上所经历的时间,该时间是启动磁盘时间 s 与磁头移动 n 条磁道所花费的时间之和
• 旋转延迟时间
  $Tr=\frac{1}{2r}$ (r 是旋转速度)
• 传输时间
  $Tt=\frac{b}{rN}$ (b是每次读写操作的字节数,N是一个磁道上的字节数,r是旋转速度)
• 访问时间
  $Ta=Ts+Tr+Tt$

磁盘组织

主引导扇区(MBR)

硬盘的0柱面,0磁头,1扇区称为主引导扇区,该记录占用512个字节,用于在硬盘启动的时候将系统控制权转给用户控制权.
其结构为:

• 前446byte:包含启动代码和数据
• 后64byte:四个分区项组成的分区表,记录了启动时需要的分区参数
• 末2byte:魔数
  对于四个分区至少有一个主分区用于存储系统,其余盘为扩展磁盘分区用于存储数据,扩展磁盘分区可以分出多个逻辑分区.

磁盘调度

FCFS

算法思想:
按照请求到达的先后次序服务

• 优点
• • 简单,公平
• 缺点
• • 效率不高

SSTF

算法思想:
优先选择距当前磁头最近的访问请求进行服务

• 优点
• • 改善了磁盘的平均服务时间
• 缺点
• • 可能产生饥饿现象

SCAN

算法思想:
当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复.

• 优点
• • 克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向
• 缺点:
• • 但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。

CSCAN

算法思想:

• 按照所要访问的柱面位置的次序去选择访问者
• 移动臂到达最后一个柱面后,立即带动读写磁头快速返回到 0 号柱面
• 返回时不为任何的等待访问者服务.
• 返回后可再次进行扫描

优点:
改进了 SCAN 算法偏向于处理那些接近最里或最外的磁道的请求的问题.

LOOK和C-LOOK

和SCAN,CSCAN类似,但是区别是当移动方向上不再有请求时, 就调转方向.

空间的管理

位图

用一串二进制位反映磁盘空间中分配使用情况，每个物理块对应一位，分配的物理块为0，否则为1。

空闲表

将所有空闲块记录在一个表中，即空闲表.
表项记录两个内容:起始块号，块数.

空闲链表法

把所有空闲块链成一个表.

成组链接法

把空白物理块分成组，在通过指针把组与组之间链接起来，这种管理空白块的方法称为成组链接法。
成组链接法:

RAID

RAID(Redundant Arrays of Inexpensive Disks),也叫廉价冗余磁盘阵列,用低成本增加磁盘的容错能力

RAID1

镜像存储,在成对的独立磁盘上产生互为备份的数据.两个磁盘都可读取,提高了读取的性能,安全性很高,出现问题直接切换磁盘即可,但是成本也很高.

RAID2

海明码(汉明码)校验条带存储.将数据条块化地分布于不同的硬盘,条块单位为位或字节,使用海明码来提供错误检查及恢复.这种编码技术需要多个磁盘存放检查及恢复信息.

• 并行存取,各个驱动器同步工作
• 使用海明编码进行错误检测和纠正,数据传输率高
• 是一种在多磁盘易出错环境中的有效选择,并未被广泛应用,目前还没有商业化产品

海明校验

海明校验的基本原理是异或运算.由异或运算的性质可以知道a⊕a=0,因此如果$a_0=a_1⊕a_2⊕…⊕a_n$则$a_i=a_{j_0}⊕…⊕a_{j_n} (i,j_0,…,j_n=0,1,…,n)$

对于海明校验的数据,令 P 为海明校验码的维数,D 为数据的维数,则
$2^P=P+D+1$

RAID3

使用奇偶校验条带存储,共享校验盘,数据条带存储单位为字节.同 RAID2 类似,但是RAID 3使用的是简单的奇偶校验,并用单块磁盘存放奇偶校验信息.
特点

• 将磁盘分组，读写要访问组中所有盘，每组中有一个盘作为校验盘。
• 校验盘一般采用奇偶校验.
• 简单理解：先将分布在各个数据盘上的一组数据加起来，将和存放在冗余盘上。一旦某一个盘出错，只要将冗余盘上的和减去所有正确盘上的数据，得到的差就是出错的盘上的数据。
• 缺点:恢复时间长

RAID4

RAID4 和 RAID3 类似,只是 RAID4 以数据块为单位分布于不同磁盘,单位更大,方便了读操作.但是每次写都需要访问奇偶盘,限制了速度,因此在商业中用的也很少
特点:

• 冗余代价与 RAID3 相同
• 访问数据的方法与 RAID3 不同,RAID3 每次读都需要访问阵列中所有磁盘

RAID5

和RAID4类似,奇偶校验,存储单位为块,只是不单独设计奇偶校验盘符,而是在磁盘上交叉地存取数据及奇偶校验信息.在 RAID5 上,读/写指针可同时对阵列设备进行操作,提供了更高的数据流量.
特点

• 适合小数据块和随机读写的数据
• 因为块更大,所以操作涉及的磁盘少,可并行
• 写损失,每一次写产生四次读/写错做,其中两次读旧数据和奇偶信息,两次写新的数据和奇偶信息
• 如果两块盘坏掉,RAID失效

RAID6

和RAID5类似,只是增加了第二个奇偶校验信息块,两者使用不同的算法,数据可靠性高,即使两块磁盘失效,也不影响数据.
特点:

• 空间开销比 RAID5 大
• 每次写非常差,要对两个校验盘操作
• 可容忍双盘出错
• 实际应用少:性能和成本问题

提高I/O速度

主要途径:

• 提高磁盘性能
• 提高并行度
• 采用适当的调度算法
• 设置高速缓冲

缓存

• 磁盘高速缓存形式
• 独立缓存(固定大小)
• 虚拟内存(可变大小)
• 数据交付
• 直接交付(copy开销大)
• 指针交付(内存管理麻烦)
• 置换算法
• 周期性写回

优化数据布局

• 优化物理块分布
• 连续摆放
• 优化索引节点分布
• 减少与数据块的距离
• 与数据块结合

其他方法

• 提前读:
• 顺序访问的时候,把下一块提前读入缓冲区
• 延迟写
• 先写入缓冲区,直到缓冲区写满再写回磁盘
• 虚拟盘
• 利用内存空间仿真磁盘
• Virtual disk 和 disk cache 区别:
• Vitual disk的存放的内容由用户完全控制
• Disk cache中的内容完全是由操作系统控制

---

完结撒花！！！