操作系统原理第十一章：大容量存储

忘是亡心i 2023-07-17 12:48 198阅读 0赞

### 目录 ###

*  1 磁盘结构
 *  2 磁盘调度
 *   *  2.1 先来先服务（FCFS）
     *  2.2 最短寻道时间优先（SSTF）
     *  2.3 扫描算法（SCAN）

# 1 磁盘结构 #

文件是放在磁盘上的，因此磁盘的性能是对操作文件有很大的影响。下图是一个磁盘的结构示意图，很多个磁盘`platter`围绕着一个轴`spindle`旋转，磁盘旁边有磁柱`arm assembly`，磁柱上有磁臂`arm`，磁臂的末端有磁头`read-write head`，每个磁头就可以访问盘面上的相关信息：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70]  
对磁盘划分时，我们把磁盘划分为很多个同心的圆环叫做磁道`track`，每个磁道上又划分了很多等大小的块叫扇区`sector`，在各个同心圆环上同一个磁道上的磁盘叫做柱面`cylinder`。

> 磁盘储存数据的原理和盒式磁带类似，只不过盒式磁带上存储是模拟格式的音乐，而硬盘上存储的是数字格式的数据。写入时，磁头线圈上加电，在周围产生磁场，磁化其下的磁性材料；电流的方向不同，所以磁场的方向也不同，可以表示 0 和 1 的区别。读取时，磁头线圈切割磁场线产生感应电流，磁性材料的磁场方向不同，所以产生的感应电流方向也不同。

--------------------

磁盘由若干磁盘组成，绕枢轴高速旋转，目前主流磁盘转速7200转/分；我们在定位磁盘上的某个记录时，往往需要如下三个参数：

*  **柱面号**：各盘面所有的读写头同时移动，并定位在同样的垂直位置的磁道上，这些磁道形成了一个柱面。由外向内是：0，1，2，……，L；
 *  **磁头号**：磁盘的全部有效盘面从上到下依次编号：0，1，2，……，H。磁头号与盘面号是相对应的；
 *  **扇区号**：将各盘面分割成若干大小相等的扇区，编号：0，1，2，3，……，n。

磁盘设备是以一种逻辑块的一维大数组的形式编址的，这里的逻辑块是传输的最小单位。逻辑块的一维数组映射到磁盘上一些相连的扇区。0扇区是最外边柱面的第一个磁道的第一个扇区。数据首先都映射到一个磁道，其余的数据映射到同一柱面的其他磁道，然后按照从外向里的顺序映射到其余的柱面。

磁盘I/O速度的高低，将直接影响文件系统的性能。提高磁盘I/O速度的主要途径有：

*  选择性能好的磁盘；
 *  设置磁盘高速缓冲区；
 *  采用好的磁盘调度算法。

前两种方法都是在硬件上下功夫，最后一种方法是可以由操作系统来控制的，因此我们主要讨论磁盘调度算法。

好的磁盘调度算法可以缩短磁盘的访问时间，磁盘的访问时间分为如下三种：

*  **寻道时间Ts**：把**磁头**从当前位置移动到指定**磁道**上所经历的时间，它与磁盘转速、移动的磁道数有关；
 *  **旋转延迟时间Tr**：指定**扇区**移动到**磁头**下面所经历的时间；
 *  **传输时间Tt**：指把数据从磁盘读出，或向磁盘写入数据所经历的时间。

# 2 磁盘调度 #

在上面提到的磁盘访问三个时间中，操作系统能够改变的时间只有**寻道时间**，在设计磁盘调度算法时，目的就是为了减少寻道时间（寻道距离）。

## 2.1 先来先服务（FCFS） ##

先来先服务调度算法的思想如字面意思一样，这里不再解释，假设磁盘的请求序列为 `98, 183, 37, 122, 14, 124, 65, 67` ，且磁头当前的位置在`53`，磁头移动轨迹示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 1]  
根据磁头移动的轨迹图，可以计算出磁头总共移动了`640`个柱面的距离。

## 2.2 最短寻道时间优先（SSTF） ##

最短寻道时间优先的思想就是选择从当前磁头位置所需寻道时间最短的请求，假设磁盘的请求序列为 `98, 183, 37, 122, 14, 124, 65, 67` ，且磁头当前的位置在`53`，磁头移动轨迹示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 2]  
根据磁头移动的轨迹图，可以计算出磁头总共移动了`208`个柱面的距离。最短寻道时间优先算法思想类似于短作业优先算法，有可能引起某些请求的饥饿。

## 2.3 扫描算法（SCAN） ##

为了解决最短寻道时间优先算法造成的饥饿问题，这里引入了扫描算法，它不仅考虑到欲访问的磁道与磁头当前位置间的距离，更优先考虑的是磁头当前的移动方向。算法所选择的访问对象应当是与磁头当前的移动方向一致且距离最近的。具体来说就是磁头从磁盘的一端开始向另一端移动，沿途响应访问请求，直到到达了磁盘的另一端，此时磁头反向移动并继续响应服务请求。由于扫描算法类似于现实中的电梯工作过程，有时也称为**电梯算法** 。

假设磁盘的请求序列为 `98, 183, 37, 122, 14, 124, 65, 67` ，且磁头当前的位置在`53` 且**朝磁道号减小的方向移动**，磁头移动轨迹示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 3]  
根据磁头移动的轨迹图，可以计算出磁头总共移动了`236`个柱面的距离。扫描算法存在着等待问题，也就是若磁头朝一个方向移动时，又来了大量另一方向的请求，那么这些请求就要等待较长时间磁头才能过来。

--------------------

为了解决这个问题，引入了 **C-SCAN** 算法，C的意思就是循环的意思，它提供比扫描算法更均衡的等待时间。它的办法是磁头从磁盘的一段向另一端移动，沿途响应请求。**当它到了另一端，就立即回到磁盘的开始处，在返回的途中不响应任何请求。**

假设磁盘的请求序列为 `98, 183, 37, 122, 14, 124, 65, 67` ，且磁头当前的位置在`53` 且**朝磁道号增加的方向移动**，磁头移动轨迹示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 4]

--------------------

不管是 **SCAN** 算法还是 **C-SCAN**算法，都需要磁头从一端移到另外一端，如上图，其实没有必要返回到 `0` 处，再到 `14`，为了解决这个问题，引入了 **LOOK**算法，它的办法是磁臂在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的一端。

假设磁盘的请求序列为 `98, 183, 37, 122, 14, 124, 65, 67` ，且磁头当前的位置在`53` 且**朝磁道号减小的方向移动**，磁头移动轨迹示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 5]  
根据磁头移动的轨迹图，可以计算出磁头总共移动了`198`个柱面的距离。

--------------------

此外还有 **C-LOOK** 算法是对 **C-SCAN** 算法的改进，**C-LOOK** 的办法是让磁臂在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的一端。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70]: /images/20230528/0e9ec3afcb7a488c80ba6648d6d23adc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 1]: /images/20230528/d733bea571af481c8e73d389d72368db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 2]: /images/20230528/00bcdcafaea547a1b704cf97546285c0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 3]: /images/20230528/bd8affd7c0dc4f4b8d6306325b5a2cc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 4]: /images/20230528/7a898a9ab89146a09caa51e7492056a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 5]: /images/20230528/40865341d3ba4805a289c52114686c05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3N5emRldg_size_16_color_FFFFFF_t_70 6]: /images/20230528/a02e36aa2f61488cb098f402fc541ef4.png