计算机体系中数据存储设备主要分为易失性设备（如内存DRAM）和非易失性设备（如磁盘，固态硬盘等），计算机体系架构中的存储层次结构（memory hierarchy），操作系统中的文件系统（file system）等会涉及如何管理存储设备，以便获得更好的性能。本文作为基础篇介绍常用的存储设备，为后续讲解进行铺垫。

1.物理存储设备

第一部分介绍市面上常见的存储设备，主要包括易失性和非易失性存储设备。易失性存储设备因为断电后数据丢失主要用于作为缓存或内存使用，而非易失性存储设备断电后仍能保证数据不丢失，主要用于持久化存储数据。

1.1.易失性存储设备

• DRAM
  DRAM（Dynamic Random Access Memory）动态随机访问存储器主要用于作为主内存使用。存储器内部是一个按行和列寻址的长方形矩阵，为了在每个芯片中容纳更多的位，DRAM仅使用一个晶体管来存储一位数据，信息的读取过程会破坏该信息，所以需要进行恢复，为了防止在没有读写一个位时丢失信息，必须定期“刷新”该位，不过只需要对一行数据读取就能刷新该行，存储器系统中的DRAM必须在特定时间间隔（比如8ms）访问每一行，这也是称为动态RAM的原因。

  
  DRAM内部组成结构,来源【1】
  

  现代DRAM通常是以“组（Bank）”为单位来组织行的，DDR4通常有16组，每一组有一系列行构成，当发送Act（Activate）指令时，会打开一个组将一行数据读取到缓冲区，当发送Pre（precharge）指令时，会关闭组和行，为下次访问做准备。当行已经在缓冲区时，可以采用2种方式进行传送，一种是根据DRAM的宽度采取连续列地址传送（通常是4，8，16位）；另一种是指定块传送方式，并给出初始地址。每个命令和块传送过程都是通过时钟同步。

• SRAM
  SRAM（Static Random Access Memory）静态随机访问存储器, 和DRAM的差异是DRAM数据需要持续刷新,而SRAM不需要刷新, 只要保持通电, 存储的数据就能稳定不变。SRAM采用6个晶体管保持1bit数据, 导致单位面积容量有限, 由于无需刷新数据, SRAM性能比DRAM好, 但价格高, 一般作为CPU的L1, L2, L3缓存使用。
• 寄存器
  寄存器(Processor Register)是CPU内部一小块用于存储数据的单元, 类型包括指令寄存器, 数据寄存器, 地址寄存器, 程序计数器, 通用寄存器等, 大小包括8位, 32位及64位, 主要用于处理器进行计算或数据缓存。

1.2.非易失性存储设备

• 软盘
  软盘（floppy disk，又称FDD）是在早期计算机中广泛使用的存储媒介，一般是在聚氯乙烯制成的盘面上覆盖磁性材料来记录数据。典型的3.5英寸软盘容量是1.44M，它包含80个磁道，每个磁道有18个扇区，两面都可以存储数据，一个扇区512字节，故容量为80×18×2×512=1440KB。软盘主要由控制电路板、马达、磁头定位器和磁头组成。主要特点是小巧可插拔，方便携带；但容量小，存取速度慢。随着u盘，光盘，移动硬盘的普及，软盘逐渐淡出人们视野。
• 光盘
  光盘（compact disc）是以光信息为存储载体的设备，利用激光原理来读写数据。主要分为2类：只读型光盘，如CD-ROM，DVD-ROM等；可擦写光盘，如CD-RW，DVD-R，DVD+R，DVD+RW等；根据光盘结构差异（即烧录读取激光波长和物镜孔径），主要分为CD，DVD，蓝光等。容量为CD（700M）、DVD(4.7G）、蓝光（25G）。
  结构包括基板、记录层、反射层、保护层、印刷层。其中记录层用来存储数据，对于只读型光盘，是在基板上涂抹有机染料；对于可擦写光盘，是涂抹碳性材料。通过激光烧录时改变碳性材料的极性或有机染料的反射率，从而形成对应计算机二进制码的0和1。
• 硬盘
  硬盘（hard disk，又称HDD）是计算机主要存储设备，一般是在铝制或玻璃制碟片上覆盖磁性材料来记录数据，通常是会永久性固定在磁盘驱动器中。磁盘主要包括主轴马达、柱面、磁道、扇区、内存芯片等组成，磁盘转速（RPM）越快则内部数据传输速率越快，平均访问时间越短。服务器为了追求磁盘读写性能转速通常为10000rpm，甚至高达15000rpm。几个硬盘相关的核心概念：
  平均访问时间（access）：磁头从起始位置到达目标磁道，并从目标磁道找到访问数据所在扇区所需时间，平均在8~12ms。
  平均寻道时间（seek）：磁头移到到目标磁道时间，平均等待时间：处于目标磁道，等待需要访问的扇区旋转到磁头下方的时间，为磁盘旋转一周时间的一半，即1×60/(2×rpm)。而硬盘内部传输速率主要由转速决定，速度非常快。而外部传输速率和接口类型有关，例如SATA3.0理论速率高大750MB/s。数据传输时间非常短，基本可以忽略。因此磁盘的平均访问时间=平均寻道时间+平均等待时间。
• U盘
  U盘全称是USB闪存盘（usb flash disk，UFD），是一种采用usb标准无需物理驱动器的微型高容量移动存储产品。U盘主要2部分：由PCB、USB控制芯片、Flash闪存等组成的机芯以及外壳。主要优点是小巧易携带、存储容量大、价格便宜、性能可靠，目前主流的U盘容量有128/256g，最高有1T。USB3.0理论传输速率是500MB/s。

• 固态硬盘
  固态硬盘（solid state disk，SSD）是基于闪存或DRAM作为存储媒介的硬盘设备。之所以成为固态,就是不存在可移动部件。

  
  SSD架构,来源【3】

其组成部分和U盘类似，包括PCB、主控芯片、缓存芯片、存储媒介Flash或DRAM。基于闪存的存储媒介在断电后仍然能够保存数据，而基于DRAM为存储媒介的固态硬盘要求有独立电源供应保持不断电，Flash SSD是市面上主流产品。相对于传统硬盘，优点是安静、防震、省点、性能好，由于无需机械寻道，获取任意位置数据的时间都相同，使得固态硬盘IO性能远高于传统硬盘。Flash晶片有NOR Flash和NAND Flash两种，由于NAND Flash容量大，写和擦除速度快，因此大部分固态硬盘都是NAND Flash。Flash的基本电路单元是浮空栅极晶体管，每个单元称为一个cell，cell类型主要包括：1.single level cell（SLC）；2.multi level cell（MLC）；3.Triple level cell（TLC）; 4.Quard level cell （QLC）(备注: 历史原因MLC专指2层单元), 单元层次越多，容量越大，价格越便宜。下面简单介绍SSD的工作原理，SSD主控芯片主要负责：错误纠正和检查ECC，磨损平衡（Wear Leveling），坏块映射（Bad block mapping），缓存控制，垃圾回收，加密等。传统硬盘的读写基本单元是扇区，通常是512字节；而固态硬盘的基本读写单元称为page，每个page由一堆cell组成，page分为2部分，一部分存储数据，一部分存储ECC及其他信息；不同型号SSD的page不一样，一般page由2048字节数据区和64字节空闲区组成，共2112字节。每128个page组成一个block。由于电路构造原因，block是数据擦除最小单元，不同于传统磁盘，block写入数据后不能直接覆盖，需要擦除后变为空白block才允许写入新数据。SSD控制器会维护一个mapping table，记录逻辑地址和物理地址的映射关系，当读取逻辑Page页时，需要通过mapping table找到物理Page页地址，然后在Flash读取相应数据。由于Flash无法覆盖写，因此容易产生很多垃圾数据，为了解决这个问题，SSD有垃圾回收机制，在写入新数据时，如果SSD控制器无法找到找到可以写入的空Page时，会选择若干block，将仍然有效的page复制到某个block，然后将原来的block进行擦除以便回收空间，由于有这个垃圾回收过程，因此SSD在写入大量数据后，也会变慢。为了保持gc时有空白block能够用于迁移数据，一般SSD都会有7%的预留空间（Over Provisioning），这部分空间无法对外使用，由SSD用来进行垃圾回收、备用坏块等。预留空间越大，垃圾回收越快，Flash损耗越小，Flash损耗用P/E数（Program/Erase Count）来衡量。考虑到SSD可能会对某些block进行频繁擦写，比如操作系统日志可能频繁更新，导致不同block的损耗不均衡，为了保证所有block的损耗是均衡了，采用了磨损平衡（Wear Leveling）机制。
因为Flash无法覆写即垃圾回收机制，因此引入了写放大（write amplification）机制，写放大倍数=闪存写入数据量/主控写入数据量，当flash是空盘时，写放大倍数为1；当出现垃圾回收时，由于写入数据时要迁移page，写放大倍数可能大于1.

1.3.总结

表1: 设备大小和性能对比, 由于不同设备性能存在差异, 表1描述了相关设备的典型参数.

	寄存器	缓存SDRAM	主内存DRAM	固态硬盘SSD	硬盘HDD
大小	1000~4000byte	64KB~64MB	4~256GB	256GB~1TB	16~64TB
性能	0.2~0.3ns	1~20ns	50~100ns	0.025~0.2ms	5~10ms
价格美元/GB, 2012年数据	*	500~1000	10~20	0.75~1	0.05~0.1

2.存储器层次结构设计

2.1 存储器层次结构

在开始本章节前, 首先给出计算机发展过程中的3个知名定律或原则:

• 摩尔定律：1965 Gordon Moore 预测芯片中晶体管数量每2年增加一倍。（已经变缓，2015年终结，目前每年3.5%）
• Dennard scaling：1974年Dennard提出，晶体管不断变小，但芯片的功率密度不变。要保持功率密度不变, 意味着电压和电流得减半。（2003年终结, 实际上为保持可靠性，电压和电流无法继续下降, 随着晶体管变小, 静态功率也无法再忽视了。）
• 阿姆达尔定律：1967年，不断提升的处理器数量会导致性能提升递减。并行计算的理论加速受到任务顺序部分的限制。

虽然近年摩尔定律和Denard scaling开始失效, CPU的增长已经放缓, 但CPU和存储器之间性能仍存在指数级差异。

处理器&内存性能差异

理想情况下, 我们希望拥有无限大的内存容量, 这样就可以访问任意一个特定的机器字(指令或数据), 但考虑到实际情况, 我们不得不设计一个分层结构的存储器, 每一层比前一层容量更大, 但访问速度也更慢。这种经济而又实用的解决方案就是存储器层次结构(memory hierarchy), 这一方案充分利用了局部性原理以及"在给定技术和功耗要求下, 硬件尺寸越小, 性能越快"的准则。

存储器层次结构

存储结构划分为几个级别, 约接近CPU, 硬件容量越小, 速度越快, 而单位字节成本也越高. 通过这种设计, 目标是提供一种存储体系, 每字节的成本和最便宜的存储器级别相同, 而速度与最快速的级别相同. 低层级存储器包含上一级存储器中的数据, 层次结构的最低一层必需满足这一包含性质. 计算机体系架构中存储器结构如下所示:

CPU&缓存&内存层次结构

	L1	L2	L3	内存
大小	64kB	256kB	16~64MB	32~256GB
速度	1ns	3~10ns	10~20ns	50~100ns

2.2.基本概念

• 缓存布局
  主内存和缓存中移动数据的基本单位是块(block, 或称为行line), 一般包括多个字, 主要是为了性能考虑, 利用了空间局部性原理。设计时需要考虑块如何放置在缓存中, 常见方案是组相连(set associative), 组由多个块组成, 查找一个块时, 首先需要映射到组, 然后在组内进行搜索. 组的映射: [块地址] MOD [缓存中组数], 如果组中有n个块, 则称为n路组相联(n-way set associative), 如果n为1, 则是直接映射(direct mapped), 如果只有一个组, 则称为全相联(fully associative)
  

  缓存布局

• 写缓存策略
  为了保证缓存和存储器中副本一致, 通常有3种策略
  直写(write through): 更新缓存, 并直接写入存储器进行更新
  回写(write back): 仅更新缓存, 此时块被标记为脏块, 只有在块替换时才将其更新回存储器
  后写(write behind): 仅更新缓存, 并记录脏记录列表, 定期将脏记录刷回存储器
  为了提高写性能, 两种策略都是用了写缓冲(write buffer), 将数据写入缓冲区后, 马上进行缓存操作, 而无需等待将数据写入存储器.
  采用只写能更好的解决缓存一致性问题, 但直写代价高, 通常在L1采用直写, 而L2/L3采用回写方式
  通过缺失率(miss rate)来衡量缓存组织的性能, 缺失率=缓存中未找到数据请求数/总请求数.
  缺失产生的类型(4C模式)主要分为:
  1.强制（Compulsory）：指首次访问时，数据不在缓存中
  2.容量（Capacity）：指缓存无法包含所有的数据块，因此有些块需要淘汰, 在访问时需重新放回缓存
  3.冲突（Conflict）：指多个数据块可能映射到一个组中，不同块的访问混在一起，可能导致需要先将一个块淘汰，之后重新加载
  4.一致性（coherency）：指在多处理器和多线程中，需要将缓存刷新以保持多个处理器缓存中的数据一致性。

存储器平均访问时间=命中时间+缺失率×缺失代价
提升缺失率的方法包括:
(1) 增大块
(2) 增大缓存
(3) 提高相联程度
(4) 采用多级缓存   在加快缓存命中速度以跟上高速时钟频率和加大缓存,缩小处理器访问和存储器访问之间的差距中间很难抉择, 但是可以通过多级缓存方案, L1缓存足够小, 以便跟上时钟频率; L2或L3缓存足够大, 以便能够更多容纳数据减小对存储器的访问
(5)读缺失优先级高于写入操作   读取缺失时先检查缓冲区的内容, 在没有冲突时, 则在写入操作之前读取数据从而降低写缺失
(6)缓存索引期间避免地址转换    由于需要将处理器的虚拟地址转换为存储器的物理地址, 转换旁视缓冲区(translation look aside buffer, TLB)

• 虚拟内存
  虚拟存储器(virtual memory, 又称虚拟内存)是操作系统对内存的管理方式, 能够在物理内存不足时将数据在辅助存储（磁盘或Flash）和主存中换入和换出，这种虚拟化的方式使得对用户来说存在一个比实际物理内存更大的一块内存，被称为虚拟内存空间。程序使用虚拟地址, 而处理器只能通过地址总线访问主内存，计算机通过软硬件结合的方式完成虚拟地址到物理地址的映射(地址转换), 硬件部分是CPU中的内存管理单元（Memory Management Unit, MMU）,软件部分则通过操作系统的内存管理模块（如页表）。对于程序来说主内存和用于虚拟内存的磁盘组成了一个完整的连续地址空间。通过虚拟内存技术, 实现了对主内存和辅助内存的2级存储器层次结构的自动化管理, 减轻了程序员的压力。使得既可以共享内存空间, 增加了安全保护（虚拟内存保护了进程的地址空间不被其他进程访问）, 并提高了可用内存空间。

  
  虚拟内存机制

虚拟存储器中基本单位是页(Page), 一般大小是4KB, 虚拟地址空间中的虚拟页(Virtual Page)和主内存中的物理页(Physical Page)大小一样, 虚拟地址空间大小由处理器的地址大小决定, 为了通过虚拟地址定位页内位置, 需要2^p位, 我们选择虚拟地址的低p位作为偏移量, 选择低位的原因是利用空间局部性原理, 相邻地址对应同一个page或相邻page, 同样选择物理地址的低p位作为偏移量. 虚拟地址由虚拟页号(virtual page number, VPN)和偏移量(offset, VPO)组成, 物理地址由物理页号(physical page number, PPN)和偏移量(offset, PPO)组成, 需要维护一个单独的页表(page table)来实现虚拟页号到物理页号的映射. 当物理页在主内存中不存在时, 则出现页缺失(page fault), 此时会触发页缺失异常, 由处理器中断, 切换到页中断处理函数(page fault handler), 从辅助存储中加载对应的页数据到主内存. 如果主内存中没有空间用于存储新的页数据时, 则需要采用页替换策略选择替换页, 一般采用最近最少使用(LRU)策略, 将LRU页内容换出到辅助内存, 将空出的物理页用于存储新访问的缺失虚拟页内容, 这种处理模式称为页面调度(paging), 这种调度也称为按需调度(demand paging), 由程序的需要将相应页从辅助内存加载到主内存.

地址构成及地址映射

程序工作集(working set)是指程序运行需要保持在主内存中活动页集合, 程序开始运行后, 通过不断的页缺失调度, 工作集会逐步稳定, 页缺失也会逐步变少, 从而使得程序只需访问主内存即可运行, 这也是局部性原理来保证的, 如果程序编写的不好, 可能会频繁发生页缺失, 造成频繁从辅助内存读取数据到主内存, 这种现象称为抖动(thrashing), 需要尽量避免.

页表中的每一项(page table item, PTE)除了维护虚拟页号到物理页号的映射, 还会记录额外信息
脏位(dirty bit): 1表示数据从辅助存储加载到内存后数据发生修改, 如果脏页发生替换, 需要首先将脏页内容刷会辅助存储
驻留位(resident bit): 1表示页驻留在主内存, 0表示未驻留(可能在磁盘或者未分配).

页映射

下图是页缺失的例子, 当cpu访问的虚拟地址对应的物理地址页缺失, 数据在内存时, 此时主内存已满, 会选择一个LRU页, 将该页内容放回磁盘, 缺失页数据加载到物理内存中

18D4D663F9641890F37CFAE61737F636.jpg

由于地址转换VtoP在每次CPU进行内存访问时都会发生, 为了提升查找page table的性能, 可以考虑专用硬件设备, 如SRAM来作为缓存, 避免CPU每次都查找主内存. 这种专用设备被称为转址旁路缓存(translation lookaside buffer , TLB), 位于CPU中. TLB非常小且速度快, 采用全相联缓存布局, 在TLB命中时只需一次物理内存访问, 通常命中率高达99%.

基于TLB地址转换

上下文(context)是指每个程序维护的一个虚拟地址到物理地址的映射, 每个程序有单独上下文, 在程序切换时由操作系统选择合适的上下文加载到映射表; 此外, 提供了保护机制用于区分内核态(kernel)和用户态(user), 比如中断处理只能由OS切换到内核态调用.

上下文示意图

为了避免每个上下文有独立的映射表, 造成上下文切换代价高昂(TLB需要清空重新加载), 高效的上下文切换方案调整为TLB中包含上下文信息(上下文id)

快速上下文切换方案

实际地址空间被分为多个区域进行管理, 调度方式有分页式、段式、段页式. 如下图所示, 被划分为独立区间, 如代码码, 保留的中断处理, 堆空间和栈空间等.

地址空间

页映射也可以采用层次结构, 使用多级缓存可以减小页映射表的大小. 如图所示, 采用2级映射时, 一级页和二级页只有1024PTE, 考虑到程序局部性原理, 可以只需要缓存部分项, 尤其是在多进程, 每个进程有自己的上下文时, 可以极大节省TLB占用.

多级页映射

• b

3.操作系统文件系统设计

9.扩展阅读

TODO

10.参考文献

【1】Computer Architecture: A Quantitative Approach (6th)
【2】NAND Flash电路单元SLC&MLC&TLC的区别
【3】Architecture of an SSD and Benchmarking
【4】Computer Organization And Design (5th)
【5】计算机结构: MIT课程
【6】Virtual memory - Wikipedia