不愿飞的蜂鸟首页

大容量存储器的结构

磁盘

  • 磁盘（ magnetic disk）为现代计算机系统提供了大容量的外存。从概念上来说，磁盘相对简单。每个磁盘片为扁平圆盘。
  • 磁头与磁臂( disk arm)相连，磁臂能将所有磁头作为一个整体而一起移动。磁盘片的表面被逻辑地划分成圆形磁道( track)，磁道再进一步划分为扇区( sector)。位于同一磁臂位置的磁道集合形成了柱面(cylinder)。每个磁盘驱动器有数千个同心柱面，每个磁道可能包括数百个扇区。常用磁盘驱动器的存储容量是按GB来计算的。
  • 大多数驱动器每秒可转60～200圈。磁盘速度有两部分。传输速率( transfer rate）是在驱动器和计算机之间的数据传输速率。定位时间( positioning time),有时称为随机访问时间(random access time),由寻道时间(seektime)(移动磁臂到所要的柱面所需时间）和旋转等待时间（rotational latency)(等待所要的扇区旋转到磁臂下所需时间）组成。典型磁盘能以每秒数兆字节的速率传输，寻道时间和旋转等待时间为数毫秒。
image-20220228162952715

磁盘结构

  • 对使用常量线性速度(constant linear velocity，CLV)的介质，每个磁道的位密度是均匀的。磁道离磁盘中心越远，其长度越长，因而也能容纳更多的扇区。从外到内时，每个磁道的扇区数也会减少。外部磁道的扇区数通常比内部磁道的扇区数多40%。随着磁头由外移到内，驱动器会增加速度以保持磁头续写的数据速率恒定。这种方法用于CD-ROM和 DVD-ROM驱动器。
  • 另外，磁盘转动速度可以保持不变，因此内磁道到外磁道的位密度要不断降低以保持数据率不变。这种方法被用在硬盘中，称为恒定圆角速度( constant angular velocity，CAV)。

磁盘调度

描述

  • 操作系统的任务之一就是有效地使用硬件。对磁盘驱动器来说，满足这一要求意味着要有较快的访问速度和较宽的磁盘带宽。访问时间包括两个主要部分:寻道时间和旋转延迟。寻道时间是磁臂将磁头移动到包含目标扇区的柱面的时间。旋转延迟是磁盘需要将目标扇区转动到磁头下的时间。磁盘带宽是所传递的总的字节数除以从服务请求开始到最后传递结束时的总时间。可以通过使用适当的访问顺序来调度磁盘IO请求，提高访问速度和带宽。
  • 每当一个进程需要对磁盘进行I/O操作，它就向操作系统发出一个系统调用。
  • 如果所需的磁盘驱动器和控制器空闲，那么该请求会马上处理。如果磁盘驱动器或控制器忙，那么任何新的服务请求都会加到该磁盘驱动器的待处理请求队列上。对于比个有多个进程的多道程序设计系统，磁盘队列可能有多个待处理请求。操作系统该如何选择？

调度算法

FCFS调度

  • 最简单的磁盘调度形式当然是先来先服务算法(FCFS)。这种算法本身比较公平，但是它通常不提供最快的服务。例如，有一个磁盘队列，其IO对各个柱面上块的请求顺序如下;
  • 98,183,37,122,14,124,65,67
  • 如果磁头开始位于53，总的磁头移动为640柱面。
image-20220228163043587

SSTF调度

  • 最短寻道时间优先算法（shortest-seek-time-first，SSTF）选择距当前磁头位置由最短寻道时间的请求来处理。由于寻道时间随着磁头所经过的柱面数而增加，SSTF选择与当前磁头位置最近的待处理请求。
  • 这种调度算法所产生的磁头移动为236柱面，约为FCFS调度算法所产生的磁头移动数量的三分之一强。这种算法大大提高了性能。
image-20220228163102932
  • SSTF调度基本上是一种最短作业优先(SJF）调度，与SJF调度一样，它可能会导致一些请求得不到服务。虽然SSTF 算法与FCFS算法相比有了很大改善，但是并不是最优的。

SCAN调度

  • 对于SCAN算法，磁臂从磁盘的一端向另一端移动，同时当磁头移过每个柱面时，处理位于该柱面上的服务请求。当到达另一端时，磁头改变移动方向，处理继续。磁头在磁盘上来回扫描。SCAN算法有时被称为电梯算法（elevator algorithm)，因为磁头的行为就像大楼里面的电梯，先处理所有向上请求，然后再处理相反方向请求。
  • 在应用SCAN算法来调度请求之前，不但需要知道磁头当前位置(53)，还需知道磁头移动方向。
image-20220228163136663

C-SCAN算法

  • C-SCAN (circular SCAN，C-SCAN）调度是SCAN调度的变种，主要提供一个更为均匀的等待时间。与SCAN一样，C-SCAN将磁头从磁盘一端移到磁盘的另一端，随着移动不断地处理请求。不过，当磁头移到另一端时，它会马上返回到磁盘开始，返回时并不处理请求。C-SCAN调度算法基本上将柱面当做一个环链，以将最后的柱面和第一个柱面相连。
image-20220228163158852

LOOK算法和C-LOOK算法

  • 正如以上所述，SCAN和C-SCAN使磁头在整个磁盘宽度内进行移动。事实上，这两个算法都不是这么实现的。通常，磁头只移动到一个方向上最远的请求为止。接着，它马上回头,而不是继续到磁盘的尽头。这种形式的SCAN和C-SCAN称为LOOK和C-LOOK调度，这是因为它们在朝一个方向移动会看(look〉是否有请求。
image-20220228163218626

磁盘调度算法的选择

  • SSTF较为普通且很有吸引力,因为它比FCFS 的性能要好。SCAN和 C-SCAN对于磁盘负荷较大的系统会执行得更好，这是因为它不可能产生饿死问题。
  • 对于任何调度算法,其性能主要依赖于请求的数量和类型。
  • 磁盘服务请求很大程度上受文件分配方法所影响。程序在读一个连续分配文件时会产生数个在磁盘上相近位置的请求，因而产生有限的磁头移动。另一方面，链接或索引文件可能会有许多块，分散在磁盘上，因而产生大量的磁头移动。
  • 目录和索引块的位置也很重要。在内存中缓存目录和索引块有助于降低磁头移动，尤其是对于读请求。
  • 由于这些复杂因素，磁盘调度算法应作为一个操作系统的独立模块，这样如果有必要，它可以替换成另一个不同的算法。SSTF或LOOK是比较合理的默认算法。

磁盘管理

磁盘格式化

  • 在磁盘能存储数据之前，它必须分成扇区以便磁盘控制器能读和写。这个过程称为低级格式化（或物理格式化)。低级格式化为磁盘的每个扇区采用特别的数据结构。每个扇区的数据结构通常由头、数据区域（通常为512B大小）和尾部组成。头部和尾部包含了一些磁盘控制器所使用的信息，如扇区号码和纠错代码(error-correcting code, ECC)。当控制器在正常IO时写入一个扇区的数据时，ECC 会用一个根据磁盘数据计算出来的值来更新。当读入一个扇区时，ECC值会重新计算，并与原来存储的值相比较。如果这两个值不一样，那么这可能表示扇区的数据区可能已损坏或磁盘扇区可能变坏。控制器在读写磁盘时会自动处理ECC。
  • 绝大多数硬盘在工厂时作为制造过程的一部分就已低级格式化了。
  • 为了使用磁盘存储文件，操作系统需要将自己的数据结构记录在磁盘上。这分为两步。一是将磁盘分为由一个或多个柱面组成的分区。操作系统可以将每个分区作为一个独立的磁盘。在分区之后，二是逻辑格式化(创建文件系统)。操作系统将初始的文件系统数据结构存储到磁盘上。

引导块

  • 对绝大多数计算机，自举程序（初始化程序）保存在只读存储器（ROM)中。由于ROM 不需要初始化且位于固定位置，这便于处理器在打开电源或重启时开始执行。而且，由于 ROM是只读的，所以不会受计算机病毒的影响。绝大多数系统只在启动ROM 中保留一个很小的自举加载程序，其作用是进一步从磁盘上调入更为完整的自举程序。这一完整的自举程序可以容易地进行修改:新版本可写到磁盘上。这个完整的自举程序保存在磁盘的启动块上，启动块位于磁盘的固定位置。拥有启动分区的磁盘称为启动磁盘( boot disk)或系统磁盘( systemdisk)。

坏块

  • 由于磁盘有移动部件并且容错能力小（磁头在磁盘表面上飞行)，所以容易出问题。常见的是，一个或多个扇区坏掉。绝大多数磁盘从工厂里出来时就有坏块。
  • 对于简单磁盘，可手工处理坏扇区。MS-DOS format命令执行逻辑格式化，它扫描磁盘以查找坏扇区。如果找到坏扇区，就在相应的FAT条目中写上特殊值以通知分配程序不要使用该块。
  • 更为复杂的磁盘，对坏块的处理就更加智能化了。其控制器维护一-个磁盘坏块链表。该链表在出厂前进行低级格式化时就已经初始化了，并在磁盘整个使用过程中不断更新。低级格式化将一些块放在一边作为备用，操作系统看不到这些块。控制器可以用备用块来逻辑地替代坏块。这种方案称为扇区备用( sector sparing）或转寄（ forwarding)。
  • 这种控制器所引起的重定向可能会使操作系统的磁盘调度算法无效。为此，绝大多数磁盘在格式化时为每个柱面都留了少量的备用块，还保留了一个备用柱面。当坏块需要重新映射时，控制器就尽可能使用同一柱面的备用扇区。
  • 作为扇区备用的另一方案，有的控制器采用扇区滑动( sector slipping）来替换坏扇区。这里有一个例子:假定逻辑块17变坏，而第一个可用的备用块在扇区202之后。那么，扇区滑动就将所有从17~202的扇区向下滑动一个扇区，即扇区202复制到备用扇区，201到202，200到201等，直到扇区18复制到扇区19。这样滑动扇区使得扇区18为空，这样可将扇区17映射到其中。

交换空间管理

  • 交换空间管理是操作系统的另一底层任务。虚拟内存使用磁盘空间作为内存的扩充。由于磁盘访问比内存访问要慢很多，所以使用交换空间会严重影响系统性能。交换空间设计和实现的主要目的是为虚拟内存提供最佳吞吐量。

交换空间的使用

  • 不同操作系统根据所实现的内存管理算法，可按不同方式来使用交换空间。例如，实现交换的系统可以将交换空间用于保存整个进程映像，包括代码段和数据段。换页系统也可能只用交换空间以存储换出内存的页。系统所需交换空间的量因此会受以下因素影响:物理内存的多少、所支持虚拟内存的多少、内存使用方式等。它可以是数MB到数GB的磁盘空间。
  • 注意，对交换空间数量的高估要比低估更为安全。这是因为如果系统使用完了交换空间，那么可能会中断进程或使整个系统死机。高估只是浪费了一些空间（本可用于存储文件)，但并没有造成什么损害。

交换空间位置

  • 交换空间可有两个位置:交换空间在普通文件系统上加以创建，或是在一个独立磁盘分区上进行。
  • 有的操作系统较为灵活，可以使用原始分区空间和文件系统空间进行交换。Linux 就是这样的操作系统:策略和实现是分开的，系统管理员可决定使用何种类型。权衡取决于文件系统分配和管理的方便和原始分区交换的性能。

RAID结构

  • 随着磁盘驱动器不断地变得更小更便宜。一个系统拥有了大量磁盘，它就有机会改善数据读写速度（因为磁盘操作可并行进行)。而且，这种设置也使系统有机会改善数据存储的可靠性，因为可在多个磁盘上存储冗余信息。因此，一个磁盘损坏并不会导致数据丢失。这里的多种磁盘组织技术，通常统称为磁盘冗余阵列(RAID)）技术，通常用于提高性能和可靠性。
  • 过去，RAID是由许多小的、便宜磁盘组成，可作为大的、昂贵磁盘的有效替代品。现在，RAID的使用主要是因为其高可靠性和高数据传输率。

通过冗余提高可靠性

  • 可靠性问题的解决方法是引入冗余。存储额外信息，这是平常不需要的，但在磁盘出错时可以用来重新修补损坏信息。因此，即使磁盘损坏，数据也不会损坏。
  • 最为简单（但最为昂贵）的引入冗余的方法是复制每个磁盘。这种技术称为镜像( mirroring)。因此每个逻辑磁盘由两个物理磁盘组成，每次写都要在两个磁盘上进行。如果一个磁盘损坏，可从另一磁盘中恢复。只有在第一个损坏磁盘没有替换且第二个磁盘又出错，那么数据才会丢失。
  • 镜像磁盘出错（这里指数据丢失）的平均时间取决于两个因素:单个磁盘出错的平均时间，以及修补平均时间(用于替换损坏磁盘并恢复其中数据)。

通过并行处理改善性能

  • 对于磁盘镜像，读请求处理的速度可以加倍，因为读请求可以发送给任一磁盘（只要两个磁盘都能工作)。每个读的传输率与单个磁盘系统一样，但是单位时间内读数量加倍了。

  • 对于多个磁盘，通过在多个磁盘上分散数据，可以改善传输率。最简单形式是，数据分散是在多个磁盘上分散每个字节的各个位，这种分散称为位级分散。对于这种结构，每个磁盘都参与每次访问(读或写)，这样每秒所能处理的访问数与单个磁盘的一样，但每次访问可在同样时间内读相当于单个磁盘系统n倍的数据。

  • 另外，分散不必在字节的位级上进行:例如，对于块级分散，一个文件的块可分散在多个磁盘上;其他分散级别，如扇区字节和块的扇区也是可能的。

  • 总之，磁盘系统并行访问有两个主要目的:

    • 通过负荷平衡，增加了多个小访问（即页访问）的吞吐量。
    • 降低大访问的响应时间。

稳定存储实现

  • 根据定义，存储在稳定存储上的数据是永远不会丢失的。为了实现这种存储，需要在多个具有独立出错模式的存储设备（通常为磁盘）上复制所需信息。需要协调用于更新的写操作，以确保更新时所发生的差错不会使所有副本处于损坏状态，而且当恢复数据时，能强制使得所有数据处于一致和正确状态（即使在恢复时出现差错)。
Last Updated:
Contributors: liushun