磁盘结构、访问时间、调度算法

目录

一、什么是磁盘？

二、磁盘分类

1、从磁头分

2、通过盘面分

三、一次磁盘读/写的时间

四、磁盘调度算法

1、先来先到服务算法FCFS

2、最短寻找时间优先SSTF

3、扫描算法（SCAN）

4、LOOk算法

5、循环扫描算法（C-SCAN）

6、C-LOOK算法

五、减少读取延迟的方法

1、交替编号扇区

2、磁盘地址结构的设计

3、交错编号法

六、磁盘管理

1、初始化

2、引导块

3、坏块管理

---

一、什么是磁盘？

磁道、扇区、磁头臂、盘面、柱面
内扇区密度大
每一个盘面一个磁头
所有磁头连在一个磁臂上，只能共进退
同一个同同心圆的磁道构成一个柱面
一个扇区就是一个物理块，一般为512B
一个物理块地址用（柱面号，盘面号，扇区号）来识别
因此，读取一个块，需要做：
（1）移动磁臂，找到柱面
（2）激活盘面磁臂
（3）旋转找到扇区

二、磁盘分类

1、从磁头分

活动磁头：一个盘面只有一个磁头，通过移动找到磁道和柱面
固定磁头：每一个磁道有一个磁头

2、通过盘面分

盘片可以更换：可换盘磁盘
盘片不可更换：固定盘磁道

三、一次磁盘读/写的时间

寻道时间：
（1）启动磁头的时间s
（2）移动磁头的时间，跨越一个磁道m，需跨越n个磁道：m*n
总功寻道时间：s+m*ns

延迟时间：
定位到磁道的固定扇区的时间
平均时间为：1/2r
（平均要转半圈才能找到对应扇区）

传输时间：
（b/N）/r
b为读/写数据量，N为一个磁道的总数据量
b/N表示：数据需要几个磁道

四、磁盘调度算法

为什么有磁盘调度算法？
因为对于磁盘来说
延迟时间和数据传输时间是固定的，和磁盘转速有关
唯一可以优化的地方是寻道时间
不同的寻道顺序由不同的速度
下面的这一系列算法本质就是根据不同磁道访问顺序实现的

1、先来先到服务算法FCFS

谁先来就先服务谁

2、最短寻找时间优先SSTF

离谁近就服务谁
但是有可能产生饥饿现象
这是因为比较远的磁道可能很久都不会被服务

3、扫描算法（SCAN）

为了克服最短寻找的饥饿问题
SCAN算法规定：
只有磁头移动到最外侧磁道，才可以往内磁道移动
移动到最内磁道，才可以往外磁道移动
（就是往一个方向走到底才能返回）
缺点：
（1）只有到达最边缘才返回，有时候并没有这个必要
（2）对于各个位置的磁道响应不均匀（加入往右，最右边的磁道短期内被访问两次，而左边的很久才被再访问）

4、LOOk算法

为了解决SCAN算法的不撞南墙不回头的缺点
LOOK算法在移动方向上已经没有了其他请求就折回
（就像边走边观察，因此叫LOOl算法）

5、循环扫描算法（C-SCAN）

为了解决SCAN算法对磁道响应不公平的算法
该算法在达到边缘时，直接折返到另外一端（从最外->最内 / 从最内->最外）
（折返过程不响应任何请求）

6、C-LOOK算法

对于C-SCAN算法来说
该算法和SCAN算法一样，必须要到达最边缘才能折返
但是事实上，如果在移动方向上没有了别的请求就可以折返了
C-LOOK算法就是如此

五、减少读取延迟的方法

1、交替编号扇区

当读取多个连续的扇区时
磁头每读完一个扇区时，还需要一个短暂的准备时间
在这个准备时间内，是不可以进行扇区读取的
因此，读完扇区1之后，如果扇区2是紧挨着的，那么就来不及读取2
这能再转一圈，第二次转到扇区2时才能读取
这样就会导致很慢

如何解决？
交替编号
如图：

扇区的编号不来连续，而是相隔一个扇区
这样，在读取一个扇区之后，经过另一个中间扇区的时间内，磁头就完成了准备时间
此时，到达下一个逻辑连续扇区就可以读取了
而不用等到下一圈，效率更快

2、磁盘地址结构的设计

问题：
为什么磁盘物理地址是（柱面号，盘面号，扇区号）
而不是（盘面号，柱面号，扇区号）？

我们分别来看情况：
（1）盘面号，柱面号，扇区号
假设有两个相邻磁道的数据需要读取
第一次读取A盘面的A柱面的A磁道
下一次读取相邻的磁道
此时，读取的是A盘面的B柱面的B磁道
也就是说，需要读取同一个盘面的两个不同的磁道
读取不同的磁道，就需要启动磁头并移动

（1）柱面号，盘面号，扇区号
同样，访问两个相邻磁道的数据
第一次访问A柱面，A盘面的A磁道
第二次访问A柱面，B盘面的A磁道
此时都属于一个柱面，
因此，不需要移动磁头
这就是这种设计方案的好处

即读取地址连续的磁盘块时，可以减少磁头移动的时间

3、交错编号法

交替命名的前提是：
所有的磁头一起转动
同时，基于物理块的地址是：（柱面号，盘面号，扇区号）
假设有8柱面，4盘面，8扇区
则编号为000 00 000 ~ 111 11 111

现在考虑这样一种情况：
要访问两个连续的磁道
对于第一个磁道，为000 00 000 ~ 000 00 111
下一磁道的位置，为000 01 000 ~ 000 01 111
请跟着想象：
当时访问玩第一个磁道后
要访问哪里？
是下一个盘面的同一个柱面的磁道
如图：

此时，当第一个磁道转两圈读取完毕后
最好的状态是立即读取下一个磁道，位置在同一柱面的下一个盘面
可是，因为磁头读取完一个扇区后需要准备一段时间
因此，如果两个盘面是同步编号的（上下编号对齐）
那么就只能再转一圈，等下一圈才能访问

因此，如果使用交错编号
那么就不用等待了
如图：

六、磁盘管理

1、初始化

（1）低级格式化

将磁盘的各个磁道划分为扇区
扇区分为头、尾、数据区
各种管理数据放在扇区的头和尾
数据区放数据

（2）磁盘分区
分为若若干柱面，例如C、D盘等

（3）逻辑格式化
创建文件系统

2、引导块

每当要开机的时候
需要进行一系列的初始化操作，例如安装操作系统
这就需要执行一些初始化程序，也叫做自举程序（因为是自动完成的）
一般自举程序会放在ROM（只读寄存器）内
在厂家生产时就已经设置好的，不可以更改

可以你不能保证自举程序一直不变
显然放在ROM里是无法解决改变的问题的
怎么办？
只放一个叫做“自举装入程序”的程序在ROM里
完整的自举程序放在磁盘的某个位置，这个位置叫做启动块，启动块是固定的
（拥有启动分区的磁盘称为启动磁盘 / 系统磁盘，例如我们的C盘）
当开机时，CPU先在运行ROM中的自举装入程序
通过该进程找到引导块，将引导块中完整的自举程序读入内存执行，完成初始化
于是，如果要是修改自举程序的话，就可以在内存中进行

3、坏块管理

一般的有两种方式
第一种方式：针对简单的磁盘
在磁盘格式化时，对整个磁盘进行扫描
并对坏块在FAT表中标明
这种方式对操作系统不透明，即可以看得见坏块的存在

第二种方式：对复杂的磁盘而言
设置一个单独的磁盘控制器会维护一个坏块链表（磁盘内部自带的硬件）
磁盘出厂时，对坏块链表初始化，并在后期不断维护
同时会保留一些备用块，用于替换坏块，这样方案叫做扇区备用
在这种方式中，坏块对操作系统透明
即操作系统看不到坏块的存在