ZY in NJU HomeArchivesTagsCategoriesAbout
COA Review (2)
|软件工程计算机组织与结构
字数总计: 12.9k|阅读时长: 41 分钟

8 内部存储器

**存储器（Memory）**由一定数量的单元构成，每个单元可以被唯一标识，每个单元都有存储一个数值的能力

  • 地址：单元的唯一标识符（采用二进制）
  • 地址空间：可唯一标识的单元总数
  • 寻址能力：存储在每个单元中的信息的位数
    • 大多数存储器是字节寻址的，而执行科学计算的计算机通常是64位寻址的

半导体存储器

用半导体存储器作主存储器是目前的流行做法

位元（memory cell）

  • 半导体存储器的基本元件，用于存储1位数据

  • 特性：

    • 呈现两种稳态（或半稳态）：分别表示二进制的0或1
    • 它们能够至少被写入（write）数据一次：用来设置状态
    • 它们能够被读取（read）来获得状态信息

  • 操作

半导体存储器类型

存储器类型 种类 可擦除性 写机制 易失性
随机存取存储器（RAM） 读-写存储器 电可擦除，字节级 电 易失
只读存储器（ROM） 只读存储器 不可能 掩膜 非易失
可编程ROM（PROM） 只读存储器 不可能 电 非易失
可擦除PROM（EPROM） 主要进行读操作的存储器 紫外线可擦除，芯片级 电 非易失
电可擦除PROM（EEPROM） 主要进行读操作的存储器 电可擦除，字节级 电 非易失
快闪存储器 主要进行读操作的存储器 电可擦除，块级 电 非易失

随机存取存储器（RAM）

Random-Access Memory（RAM）

特性：

  • 可以简单快速地进行读/写操作
  • 易失的（Volatile）

类型：

  • 动态RAM（DRAM）：Dynamic RAM
  • 静态RAM（SRAM）：Static RAM
DRAM
  1. 在电容器上用电容充电的方式存储数据
    • 电容器中有无电荷在分别代表二进制的1与0
  2. 需要周期地充电刷新以维护数据存储
    • 原因：电容器有漏电的自然趋势
    • 由一个阙值来确定电荷是被解释为1还是0

SRAM
  1. 使用传统触发器、逻辑门配置来存储二进制
    • 使用与处理器相同的逻辑元件
  2. 只要有电源，就可以一直维持数据

DRAM与SRAM的对比
  • 相同点：易失的：两者都要求电源持续供电才能保存位值
  • 不同点：
    1. DRAM比SRAM具有更简单、更小的位元，但要求能支持刷新的电路
    2. DRAM比相应的SRAM密度更高，价格更低
    3. SRAM通常比DRAM快
    4. DRAM更倾向于满足大容量存储器的需求，SRAM一般用于高速缓存（Cache），DRAM用于主存
高级的DRAM架构

问题：传统的DRAM芯片收到其内部架构和与处理器内存总线接口的限制

类型：

  • 同步DRAM（Synchronous DRAM, SDRAM）
  • 双速率SDRAM（Double-Data-Rate SDRAM, DDR SDRAM）
SDRAM

传统的DRAM是异步的：

  • 处理器向内存提供地址和控制信号，表示内存中特定单元的一组数据应该被读出或写入DRAM
  • DRAM执行各种内部功能，如激活行和列地址线的高电容，读取数据，以及通过输出缓冲将数据输出，处理器只能等待这段延迟，即存取时间
  • 延时后，DRAM才写入或读取数据

即处理器在读取数据是不能够马上获取数据，需要一段时间的延迟之后才能够读取DRAM（主存）中的数据

采用SDRAM：

  • SDRAM与处理器的数据交互同步与外部的时钟信号，并且以处理器/存储器总线的最高速度运行，而不需要插入等待状态
  • 由于SDRAM随系统时钟及时移动数据，CPU知道数据何时准备好，控制器可以完成其它工作

DDR SDRAM

  • 每个时钟周期发送两次数据，一次在时钟脉冲的上升沿，一次在下降沿（原本一个时钟周期只能提供一次数据的读写）

    不是CPU的时钟，而是外部的时钟信号

  • DDR →\rightarrow DDR2 →\rightarrow DDR3 →\rightarrow DDR4

    • 增加操作频率
    • 增加预取缓冲区

只读存储器（ROM）

Read-only Memory（ROM）

特性

  • 非易失的：不要求供电来维持数据
  • 可读，但不能写入新数据

应用

  • 微程序设计，库子程序，系统程序，寒暑表

问题

  • 无出错处理机会：如果有一位出错，整批的ROM芯片只能报废
  • 用户无法写入数据：唯一的数据写入机会在出厂时完成
可编程ROM（PROM）

Programmable ROM（PROM）

特性

  • 非易失的
  • 只能被写入一次
    • 写过程使用电信号执行
    • 需要特殊设备来完成写或编程过程
  • 与ROM的对比
    • PROM提融了灵活性和方便性
    • ROM在大批量生产领域仍然具有吸引力

主要进行读操作的存储器

Read-Mostly Memory

特性

  • 非易失的
  • 写操作与读操作相比，较为困难

应用

  • 读操作比写操作频繁得多的场景

类型

  • EPROM
  • EEPROM
  • Flash Memory
光可擦除/可编程只读存储器（EPROM）

Erasable Programmable read-only memory（EPROM）

特性：

  • 光擦除
    • 擦除：在写操作前将封装芯片暴露在紫外线下
      • 所有的存储单元都变回相同的初始状态
      • 每次擦除需要约20分钟
    • 电写入
  • 与PROM对比
    • EPROM更贵，但具有可多次改写的优点
电可擦除/可编程只读存储器（EEPROM）

Electrically erasable progammable read-only memory（EEPROM）

特性

  • 可以随时写入而不删除之前的内容
  • 只更新寻址到的一个或多个字节
  • 写操作每字节需要几百微秒

与EPROM对比

  • EEPROM更贵，且密度低，支持小容量芯片
快闪存储器

Flash Memory

特性

  • 电可擦除：与EEPROM相同，优于EPROM
  • 擦除时间为几秒：优于EPROM，不如EEPROM
  • 可以在块级擦除，不能在字节级擦除：优于EPROM，不如EEPROM
  • 达到与EPROM相同的密度，优于EEPROM

与EPROM、EEPROM对比

  • 价格和功能介于EPROM和EEPROM之间

从位元到主存

寻址单元

Addressable Unit

  • 由若干相同地址的位元组成
  • 寻址模式：Byte（常用）、word

存储阵列

Memory Array

由大量寻址单元组成

如何寻址

地址译码器

  • 一个 nn 位译码器有 2n2^n 种输出
  • 当所有 nn 个寻址位都满足条件时，该输出为 11
  • 任何时候，只有一个输出是 11，其余都是 00

如何刷新

  1. 集中式刷新（Centralized refresh）
    • 停止读写操作，并刷新每一行
    • 刷新时无法操作内存
  2. 分散式刷新（Decentralized refresh）
    • 在每个存储周期中，当读写操作完成时进行刷新
    • 会增加每个存储周期的时间
  3. 异步刷新（Asynchronous refresh）
    • 每一行各自以64ms间隔刷新
    • 效率高（常用）

芯片

芯片引脚

模块组织

  1. 位扩展：地址线不变，数据线增加
    • 使用 88 块 4K×1 bit4K \times 1\ bit 的芯片组成 4K×8 bit4K \times 8\ bit 的存储器
  2. 字扩展：地址线增加，数据线不变
    • 使用 44 个 16K×8 bit16K \times 8\ bit 的芯片组成 64K×8 bit64K \times 8\ bit 的存储器
  3. 字、位同时扩展：地址线增加，数据线增加
    • 使用 88 个 16K×4 bit16K \times 4\ bit 的芯片组成 64K×8 bit64K \times 8\ bit 的存储器

主存

插槽：组合多个存储模块

9 高速缓冲存储器（Cache）

Cache的基本思路：解决内存墙带来的CPU和主存协作问题

  • 在使用主存（相对大而慢）之余，添加一块小而快的Cache
  • Cache位于CPU和主存之间，可以集成在CPU内部或作为主板上的一个模块
  • Cache中存放了主存中的部分信息的副本

Cache的工作流程

  • 检查（check）：当CPU试图访问主存中的某个字时，首先检查这个字是否在Cache中
  • 检查分两种情况处理：
    1. 命中（Hit）：如果在Cache中，则把这个字传送给CPU
    2. 未命中（Miss）：如果不在Cache中，则将主存中包含这个字固定大小的块（block）读入Cache中，然后再从Cache传送该字给CPU

问题

  1. 如何判断是命中还是未命中
  2. 如果未命中，为什么不直接把所需要的字从内存传送到CPU
  3. 如果未命中，为什么从内存中读入一个块而不只读入一个字
  4. 使用Cache后需要更多的操作，为什么还可以节省时间

如何判断是命中还是未命中

冯·诺依曼体系的设计

  • CPU通过位置对主存中的内容进行寻址，不关心存储在其中的内容

Cache通过标记（tags）来标识其内容在主存中的对应位置

如果未命中，为什么不直接把所需要的字从内存传送到CPU

程序的局部性原理

Definition

处理器频繁访问主存中相同位置或者相邻存储位置的现象

类型

  1. 时间局部性：在相对较短的时间周期内，重复访问特定的信息（也就是访问相同位置的信息）
  2. 空间局部性：在相对较短的时间周期内，访问相邻存储位置的数据
    • 顺序局部性：当数据被线性排列和访问时，出现的空间局部性的一种特殊情况
    • 例如：遍历一位数组中的元素

利用“时间局部性”：将未命中的数据在返回给CPU的同时存放在Cache中，以便再次访问时命中。即如果我们再访问到这个字，因为这个字已经在Cache中了，我们就可以不用访问主存，从而减少访问主存的次数

如果未命中，为什么从内存中读入一个块而不只读入一个字

利用“空间局部性”：将包含所访问的字的块存储到Cache中，以便在访问相邻数据时命中

使用Cache后需要更多的操作，为什么还可以节省时间

假设 pp 是命中率， TcT_c 是Cache的访问时间，TMT_M 是主存的访问时间

使用Cache时的平均访问时间为：

T_A = p \times T_c + (1-p) \times (T_c + T_M) \\ = T_c + (1-p) \times T_M \ \ \ \ \ \ \ \ \ \ \ \ \

  • 命中率 pp 越大， TcT_c 越小，效果越好

  • 如果想要 TA<TMT_A < T_M，必须满足

如何理解计算平均访问时间的公式？

  1. 有 pp 的概率只需要访问Cache，(1−p)(1-p) 的概率需要访问Cache和主存
  2. 每次必定会访问Cache（检查），如果不在Cache中则访问主存（(1−p)(1-p) 的概率）

Cache的设计要素

Cache容量

扩大Cache容量带来的结果：

  1. 增大了命中率 pp
  2. 增加了Cache的开销和访问时间 TcT_c

映射功能（Mapping Function）

实现主存块到Cache行的映射

块号，块内地址

映射方式的选择会影响Cache的组织结构

  • 直接映射（Direct mapping）
  • 关联映射（Associative mapping）
  • 组关联映射（Set associative mapping）
直接映射

将主存中的每个块映射到一个固定可用的Cache行中

假设 ii 是Cache行号， jj 是主存储器的块号， CC 是Cache的行数

i=j  mod  Ci = j\ \ mod\ \ C

标记

  • 地址中最高 nn 位，且满足 n=log⁡2M−log2Cn = \log_2M - log_2C （MM 是主存中块的数量）

例

假设Cache有4行，每行包含8个字，主存中包含128个字。访问主存的地址长度为7位，则：

  • 最低的3位：块内地址（包含8个字，需要3位来的地址来表示
  • 中间的2位：映射时所对应的Cache行号（Cache有4行，所以需要2位来表示行号
  • 最高的2位：区分映射到同一行的不同块，记录为Cache标记（每一行有4块能够映射到（2422\frac{2^4}{2^2}），所以需要2位来进行标记）

优点

  • 简单
  • 快速映射
  • 快速检查

缺点

  • 抖动现象（Thrashing）：如果一个程序重复访问两个需要映射到同一行中且来自不同块的字，则这两个块不断地被交换到Cache中，Cache的命中率将会降低

适合大容量的Cache

关联映射

一个主存块可以装入Cache任意一行

标记

  • 地址中最高 nn 位，且满足：n=log⁡2Mn = \log_2M

例

假设Cache有4行，每行包含8个字，主存中包含128个字。访问主存的地址长度为7位，则：

  • 最低的3位：块内地址
  • 最高的4位：块号，记录为Cache的标记

优点

  • 避免抖动

缺点

  • 实现起来比较复杂
  • Cache搜索代价很大，即在检查时候需要取访问Cache的每一行

适合容量较小的Cache

组关联映射

Cache分为若干组，每一组包含相同数量的行，每个主存块被映射到固定组的任意一行

假设 ss 是Cache的组号， jj 是主存块号， SS 是组数

s=j  mod  Ss = j\ \ mod \ \ S

  • K-路组关联映射（ KK 代表了一组里面有多少行）

K=CSK = \frac{C}{S}

标记

  • 地址中最高 nn 位，且满足 n=log⁡2M−log⁡2Sn = \log_2M - \log_2S（ MM 是主存块的数量）

例

假设Cache有4行，每行包含8个字，分成2个组，主存中包含128个字。访问主存的地址长度为7位，则：

  • 最低的3位：块内地址
  • 中间的1位：映射时所对应的Cache中的组（2个组只需要1为地址表示）
  • 最高的3位：区分映射到同一组的不同块，记录为Cache标记（每个组有8个块可以映射到，需要3位地址来表示）

优点

  • 结合了直接映射和关联映射的优点

缺点

  • 结合了直接映射和关联映射的缺点

面向不同容量的Cache做了折中

三种替换方式比较
  1. 如果 K=1K = 1，组关联映射等同于直接映射
  2. 如果 K=CK = C，组关联映射等同于关联映射

Definition（关联度）

一个主存块映射到Cache中可能存放的位置个数被称为关联度

  • 直接映射：1
  • 关联映射：C
  • 组关联映射：K
  1. 关联度越低，命中率越低。
    • 直接映射的命中率最低，关联映射的命中率最高
  2. 关联度越低，判断是否命中的时间越短
    • 直接映射的命中时间最短，关联映射的命中时间最长
  3. 关联度越低，标记所占额外空间的开销越小
    • 直接映射的标记最短，关联映射的标记最长

替换算法

  • 一旦Cache行被占用，当新的数据块装入Cache中时，原先存放的数据块将会被替换掉。
  • 对于直接映射，每个数据块都只有唯一对应的行可以放置，没有选择的机会
  • 对于关联映射和组关联映射，每个数据块被允许在多个行中选择一个进行放置，就需要替换算法来决定替换哪一行中的数据块

替换算法通过硬件来实现

最近最少使用算法（LRU）

假设：最近使用过的数据块更有可能被再次使用

策略：替换掉在Cache中最长时间未被访问的数据块

实现：对于2路组关联来说：

  • 每行包含一个 USE 位
  • 当同一组中的某行被访问时，将其 USE 位设为1，同时将另一行的 USE 位设为0
  • 当将新的数据块读入该组时，替换掉 USE 位为0的行中的数据块

编程实现中，我们使用“时间戳”来记录，对于一个访问过的数据，我们将时间戳更新到当前时间，然后替换的时候替换掉TimeStamp最小的那一行（代表很久没有访问过，所以没有更新时间戳（什么是时间戳？wiki

先进先出算法（FIFO）

假设：最近由主存载入Cache的数据块更有可能被使用

策略：替换掉在Cache中停留时间最长的块

实现：时间片轮转法 或 环形缓冲技术

  • 每行包含一个标志位
  • 当同一组的某行被替换时，将其标识位设为1，同时将其下一行的标识位设为0
    • 如果被替换的是该组的最后一行，则将该组中的第一行的标识位设为0
  • 当将新的数据块读入该组时，替换掉标识位为0的行中的数据块

Tip：注意FIFO与LRU的区别，LRU替换的是最长时间未被访问的行，FIFO替换的是停留时间最长的行，两者的结果可能是不一样的

最不经常使用算法（LFU）

假设：访问越频繁的数据块越有可能被再次使用

策略：替换掉Cache中被访问次数最少的数据块

实现：为每一行设置计数器 visited

编程实现中，我们对Cache中的每一行加一个标志位visited来记录该行被访问的次数，在替换的时候，只需要遍历该组的所有行，找到该标志位最小的行，就是我们要替换的目标

随机替换算法（Random）

假设：每个数据块被再次使用的可能性是相同的

策略：随机替换Cache中的数据块

实现：随机替换

随机替换算法在性能上只稍逊于使用其他替换算法

写策略

为什么要有写策略？

主存和Cache要有一致性

  • 当Cache中的某个数据块被替换时，需要考虑该数据块是否被修改

两种情况

  • 如果没被修改，则该数据块可以直接被替换掉
  • 如果被修改，则在替换该数据块之前，必须将修改后的数据块写回到主存中对应位置
写直达（write through）

所有写操作都同时对Cache和主存进行

即对Cache进行写操作的时候，需要同步对主存进行写操作

优点：确保主存中的数据总是和Cache的数据一致的，总是最新的

缺点：产生大量的主存访问，减慢写操作

写回法（write back）
  • 先更新Cache中的数据，当Cache中某个数据块被替换时，如果它被修改了，才被写回主存
  • 利用一个脏位（dirty bit）或者使用位（use bit）来表示块是否被修改

优点：减少了主存的访问次数

缺点：部分主存数据可能不是最新的

I/O模块存取时可能无法获得最新的数据，为解决该问题会使得电路设计更加复杂而且有可能带来性能瓶颈

行大小

  • 假设从行的大小为一个字开始，随着行大小的逐步增大，则Cache的命中率会增加
    • 数据块包含了更多周围的数据，每次会有更多的数据作为一个块装入Cache中
    • 利用了空间局部性
  • 当行大小变得较大之后，继续增加行大小，则Cache命中率会下降
    • 当Cache容量一定的前提下，较大的行会导致Cache中的行数变少，导致装入Cache中的数据块数量减少，进而造成数据块被频繁替换
    • 每个数据块中包含的数据在主存中位置变远，被使用的可能性减小

行大小与命中率之间的关系较为复杂

Cache数目

一级 vs 多级

一级

  • 将Cache与处理器置于同一芯片（片内Cache）
  • 减少处理器在外部总线上的活动，从而减少了执行时间

多级

  • 当L1未命中时，减少处理器对总线上DRAM或ROM的访问
  • 使用单独的数据路径，替代系统总线在L2缓存和处理器之间传输数据，部分处理器将L2 Cache结合到处理器芯片上
统一 vs 分立

统一

  • 更高的命中率，在获取指令和数据的负载之间自动进行平衡
  • 只需要设计和实现一个Cache

分立

  • 消除Cache在指令的取值/译码单元和执行单元之间的竞争，在任何基于指令流水线的设计中都是重要的

10 外部存储器

外部存储器

并非冯诺依曼模型中的Memory，而是属于一个外部设备（I/O），但仍然属于存储器层次结构中的一员。

为什么要使用外部存储设备？

特性：

  • 用于存储不经常使用、数据量较大的信息
  • 非易失

类型：

  • 磁盘存储器（magnetic disk） – 机械硬盘
  • 光存储器（optical memory）
  • 磁带（magnetic tape）
  • U盘（USB flash disk），固态硬盘（solid state disk，SSD）

磁盘存储器

磁盘是由涂有可磁化材料的非磁性材料（基材）构成的圆形盘片

  • 基材：铝、铝合金、玻璃…
  • 玻璃基材的优势
    • 改善磁膜表面的均匀性，提高磁盘的可靠性
    • 显著减少整体表面瑕疵，以帮助减少读写错误
    • 能够支持（磁头）较低的飞行高度
    • 更高的硬度，使磁盘转动时更加稳定
    • 更强的抗冲击和抗损伤能力

软盘

容量小，硬度低，已经基本被淘汰。

硬盘

结构
  • 盘片（盘片沿轴旋转，盘片与轴是固定的）
  • 读写头（所有读写头都连接在一根吊杆上，并径向移动寻找磁道）

磁盘存储器每个盘片表面有一个读写磁头，所有磁头通过机械方式固定在一起，同时移动。

在任何时候，所有磁头都位于距磁盘中心等距离的磁道上。

对盘片进行读写操作的装置叫做磁头（head）

  1. 磁头必须产生或感应足够大的电磁场，以便正确地读写
  2. 磁头越窄，离盘片的距离就越近
  3. 更高的数据密度需要更窄的磁头和更窄的磁道，这将导致更高的出错风险
  4. 温彻斯特磁头（Winchester head）
    1. 磁头实际上是一个空气动力箔片，当磁盘静止时，它轻轻地停留在盘片的表面
    2. 旋转圆盘时产生的空气压力足以使箔片上升到盘片表面上方
读写机制
  • 在读或写操作期间，磁头静止，而盘片在其下方旋转
  • 磁头的数量
    • 单磁头：读写公用同一个磁头（软盘、早期硬盘）
    • 双磁头：使用一个单独的磁头进行读取（当代硬盘）

写入机制

  • 电流脉冲被发送到写入磁头
  • 变化的电流激发出磁场
  • 产生的磁性图案被记录在下面的盘片表面上
  • 反转电流方向，则记录介质上的磁化方向也会反转

读取机制

  • 读取磁头是由一个部分屏蔽的磁阻（MR）敏感器组成，其电阻取决于在其下移动的介质的磁化方向
  • 电流通过MR敏感器时，通过电压信号检测其电阻变化
  • MR敏感器允许更高频率的操作，实现更高的存储密度和更快的操作速度
数据组织

  • 盘片上的数据组织呈现为一组同心圆环，称为磁道（track）

  • 数据以扇区（sector）的形式传输到磁盘或传出磁盘，看起来大小不同但存储的数据量相同。

    默认值为512B

  • 相邻磁道之间有间隙（gap），相邻的扇区之间也留有间隙

  • 磁道编号方式：最外为0，最内为N

扇区划分

  1. 恒定角速度（Constant angular velocity, CAV）

    • 增大记录在盘片区域上的信息位的间隔，使得磁盘能够以恒定的速度扫描信息
    • 优点：能以磁道号和扇区号直接寻址各个数据块
    • 缺点：磁盘存储容量受到了最内层磁道所能实现的最大记录密度的限制

  2. 多带式记录 / 多重区域记录（Multiple zone recording）

    • 将盘面划分为多个同心圆区域，每个区域中各磁道的扇区数量是相同的，距离中心较远的分区包含的扇区数多于距离中心较近的分区

      即相邻两个磁道的扇区数量是有可能相同，且相同扇区数量的两个磁道可以以相同的转速来访问。

    • 优点：提升存储容量

    • 缺点：需要更复杂的电路（内层圆心角大，转速需要快一点，外层相反，以维持稳定的数据传输率）

    每个深色区域并不是一个磁道，而是多个磁道所组成的区域，将磁道分成多个这样的区域，保证同一个区域的磁道转速相同。

所有盘片上处于相同的相对位置的一组磁道被称为柱面（cylinder）

格式化

  • 磁道必须有一些起始点和辨别每个扇区起点及终点的方法

  • 格式化时，会附有一些仅被磁盘驱动器使用而不被用户存取的额外数据。

ID域

  1. 同步字节：特殊位模式，定义区域的起始点
  2. 道号（磁道号，标识一个磁道）
  3. 头号（磁头号，标识一个磁头）
  4. 扇号（扇区号，标识一个扇区）
  5. CRC（循环冗余校验码）

数据域

  1. 同步字节
  2. 数据（512B）
  3. CRC

间隙

间隙的目的是为了让CRC有足够长的时间去检测与修复前面的错误，以判定后面的数据是不是所需要的数据

低级格式化和高级格式化

  1. 低级格式化：清楚所有区域信息，但不能够分区域进行，只能够清楚整个硬盘的信息，且对硬盘是有损伤的。
  2. 高级格式化：
I/O 访问时间
  1. 寻道时间（seek time）：磁头定位到所需移动到的磁道所花费的时间
    • 初始启动时间 + 跨越若干磁道所用的时间
  2. 旋转延迟（rotational delay）：等待响应扇区的起始处到达磁头所需的时间
    • 通常是磁道旋转半周所需的时间（rpm：转/分钟）
  3. 传送时间（transfer time）：数据传输所需的时间

T=brNT = \frac{b}{rN}

TT = 传送时间

bb = 传送的字节数

NN = 每磁道的字节数

rr = 旋转速率，单位是转/秒

b<Nb < N 时成立，相反时需要考虑寻道时间和旋转延迟

  1. 平均访问时间

    当连续访问多个相邻的磁道时，跨越磁道：

    • 对于每个磁道都需要考虑旋转延迟
    • 通常只需要考虑第一个磁道的寻道时间，但在明确知道跨越每个磁道需要的时间时需要考虑。
I/O访问时间示例

假设某个硬盘的平均寻道时间为4ms，转速为15000rpm，每磁道500扇区，每扇区512B，现读取一个由2500个扇区组成的文件

  • 情况1：顺序组织，该文件占据相邻5个磁道的全部扇区（ 55 磁道 ×500\times 500 扇区/道 = 25002500 扇区）

    • Ta=Ts+12r+brNT_a = T_s + \frac{1}{2r} + \frac{b}{rN}
    • 平均寻道时间：4ms
    • 转速15000rpm = 250转/秒，所以r = 250转/秒
    • 平均旋转延迟 = 12r=0.002s=2ms\frac{1}{2r} = 0.002s = 2ms
    • 读取数据时间 T=brN=512×500512×500×250=0.004s=4msT = \frac{b}{rN} = \frac{512 \times 500}{512 \times 500 \times 250} = 0.004s = 4ms
    • 访问后续磁道不计入寻道时间（相邻），因此第一个磁道的访问需要 4+2+4=10ms4 + 2 + 4 = 10ms，后续磁道的访问需要 4+2=6ms4 + 2 = 6ms
    • 总时间 t=10+4×6=34ms=0.034st = 10 + 4 \times 6 = 34ms= 0.034s

  • 情况2：随机存取，改文件随机分布在磁盘上的各个扇区

    • Ta=Ts+12r+brNT_a = T_s + \frac{1}{2r} + \frac{b}{rN}
    • 平均寻道时间：4ms
    • 转速15000rpm = 250转/秒，所以r = 250转/秒
    • 平均旋转延迟 = 12r=0.002s=2ms\frac{1}{2r} = 0.002s = 2ms
    • 读取一个扇区的时间 T=brN=512512×500×250=0.000008s=0.008msT = \frac{b}{rN} = \frac{512}{512 \times 500 \times 250} = 0.000008s = 0.008ms
    • 随机存取每一次都需要寻道，因此每个扇区的访问时间都是 4+2+0.008=6.008ms4 + 2 + 0.008 = 6.008ms
    • 总时间 t=2500×6.008=15020ms=15.02st = 2500 \times 6.008 = 15020ms = 15.02s
磁盘调度算法

硬磁盘存储器：I/O存储时间

硬磁盘存储器：磁头寻找道/磁盘调度
目标：当有多个访问磁盘任务时，使得平均寻道时间最小

常见的磁头寻道/磁盘调度算法：

  1. 先来先服务（First Come First Service, FCFS）
  2. 最短寻道时间优先（Shortest Seek Time First, SSTF）
  3. 扫描/电梯（SCAN）
  4. 循环扫描（C-SCAN）
  5. LOOK
  6. C-LOOK
先来先服务

按照请求访问磁盘的先后次序进行处理
**优点：**公平简单
**缺点：**如果有大量访问磁盘的任务，且请求访问的磁道很分散，则性能上很差，寻道时间长。

示例:

假设磁头的初始位置是100号磁道，有多个任务先后陆续的请求访问55， 58， 39， 18， 90， 160， 150， 38， 184

按先后处理：

  • 磁头总共移动的磁道个数：45+3+19+21+72+70+10+112+146=49845 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = 498
  • 平均寻道长度：4989=55.3\frac{498}{9} = 55.3 个磁道

最短寻道时间优先

优先处理起始位置与当前磁头位置最接近的读写任务
**优点：**每次的寻道时间最短（局部最优），平均寻道时间缩短
**缺点：**可能产生饥饿现象，尤其是位于两端的磁道请求。

饥饿现象：即较远的磁道长时间无法被磁头寻道。因为磁头长时间在较近的几个磁道之间徘徊。

示例:

假设磁头的初始位置是100号磁道，有多个任务先后陆续的请求访问55， 58， 39， 18， 90， 160， 150， 38， 184

  • 磁头总共移动的磁道个数：(100−18)+(184−18)=248(100 - 18) + (184 - 18) = 248 个磁道
  • 平均寻道长度：2489=27.5\frac{248}{9} = 27.5 个磁道

扫描/电梯（SCAN）

总是按照一个方向进行磁盘调度，直到该方向上的边缘，然后改变方向。
优点：性能较好，平均寻道时间短，不会产生饥饿现象。
缺点：只有到最边上的磁道才能改变磁头的移动方向，对于各个位置磁道响应频率不平均。

示例:

假设磁头的初始位置是100号磁道，有多个任务先后陆续的请求访问55， 58， 39， 18， 90， 160， 150， 38， 184

  • 磁头总共移动的磁道个数：(200−100)+(200−18)=282(200 - 100) + (200 - 18) = 282 个磁道
  • 平均寻道长度：2829=31.3\frac{282}{9} = 31.3 个磁道

循环扫描（C-SCAN）

只有磁头朝某个方向移动时才会响应请求，移动到边缘后立即让磁头返回起点，返回途中不做任何处理。
**优点：**与SCAN算法相比，对于个位置磁道的响应频率平均。（因为到两端的磁道之后是直接回到起点，而不是再一次通过扫描回到起点）
**缺点：**与SCAN算法想法，平均寻道时间更长。（对于已经处理完的一端，可能会有新的任务，但由于磁头直接回到起点，无法扫描到新来的任务）

注意：直接回到起点的时间其实是比扫描的时间要短的，因为这个过程不需要进行扫描（空载的）。起点就是 00 号磁道

示例:

假设磁头的初始位置是100号磁道，有多个任务先后陆续的请求访问55， 58， 39， 18， 90， 160， 150， 38， 184

  • 磁头总共移动的磁道个数：(200−100)+(200−0)+(90−0)=390(200 - 100) + (200 - 0) + (90 - 0) = 390 个磁道

    200 - 0 是回到起点所需要移动的磁道数，但其实这部分的时间比扫描的时间要短

  • 平均寻道长度：3909=43.3\frac{390}{9} = 43.3 个磁道

LOOK

SCAN算法的升级，只要磁头移动方向上不再有请求就立即改变磁头的方向（即不会到最远端的磁道）
代价：无法处理新任务，即到了最远端的某个任务之后，如果返回之后更远端又来了个新任务，LOOK算法无法及时处理到。
示例：从100 - 184，LOOK算法回头之后，又来了一个磁道190的任务，此时就无法及时处理到。

示例:

假设磁头的初始位置是100号磁道，有多个任务先后陆续的请求访问55， 58， 39， 18， 90， 160， 150， 38， 184

  • 磁头总共移动的磁道个数：(184−100)+(184−18)=250(184 - 100) + (184 - 18) = 250 个磁道
  • 平均寻道长度：2509=27.8\frac{250}{9} = 27.8 个磁道
C-LOOK

C-SCAN算法的改进，只要在磁头移动方向上不再有请求，就立即让磁头返回起点。（这里的起点是有任务的最低磁道）

示例:

假设磁头的初始位置是100号磁道，有多个任务先后陆续的请求访问55， 58， 39， 18， 90， 160， 150， 38， 184

  • 磁头总共移动的磁道个数：(184−100)+(184−18)+(90−18)=322(184 - 100) + (184 - 18) + (90 - 18) = 322 个磁道

    184 - 18 是回到起点所需要移动的磁道数，但其实这部分的时间比扫描的时间要短

  • 平均寻道长度：3229=35.8\frac{322}{9} = 35.8 个磁道

光存储器

光盘（CD）/光盘只读存储器/高清晰视频光盘（蓝光Blu-Ray DVD）…

CD and CD-ROM

CD和CD—ROM采用类似的技术，但后者更加耐用且有纠错功能

制造方法

  • 用精密聚焦的高强度激光束制造母盘
  • 以母盘为模板压印出聚碳酸酯（透明的）的复制品（类似信封上滴蜡然后压印章，印章 约等于 母盘
  • 在凹坑表面上镀上一层高反射材料
  • 使用丙烯酸树脂保护高反射材料（金属容易被磨损
  • 在聚丙烯酸树脂层上用丝网印刷术印制标签

读取过程
通过安装在光盘播放器或驱动装置内的低强度激光束从CD或CD-ROM处读取信息

  • 如果激光束照在凹坑（pit）上，由于凹坑表面有些不平，因此光被散射，反射回低强度的激光
  • 如果激光束照在台（land）上，台的表面光滑平坦，反射回来的是高强度的激光

盘片上包含一条单螺旋的轨道，轨道上的所有扇区长度相同

  • 盘片以变速旋转
  • 凹坑被激光以恒定线速度读出(内侧的角速度较大)

优点

  1. 存储有信息的光盘可以廉价地进行大规模的复制
  2. 光盘是可更换的

缺点

  1. 它是只读的，不能更改
  2. 其存取时间比磁盘存储器长的多

CD—R and CD-RW

CD-R

  • 包含一个染色层，用于改变反射率，并且由高强度激光激活
  • 生成的盘即能在CD-R驱动器上也能在CD-ROM驱动器上读出

CD-RW

  • 使用了一种在两种不同相位状态下有两种显著不同反射率的材料，激光束能改变这种材料的相位
  • 材料老化最终会永久失去相位可变的特性，当前的材料可用于50万次到100万次的擦除

数字多功能光盘（DVD）

  • DVD上的位组装更紧密：光道间隙，凹坑间距（容量达到4.7GB）

    DVD的光驱要求激光束需要更加密集，所以DVD的光驱可以读取CD，但是反过来是不行的

  • DVD采用双层结构：设有半反射层，可以通过调整焦距读取每一层（容量达到8.5GB）

  • DVD-ROM可以用两面记录数据（容量达到17GB）

分类：DVD-R和DVD-ROM

高清晰光盘（蓝光

通过使用更短波长的激光（在蓝-紫光范围），可以实现更高的位密度（数据凹坑相对更小）。

磁带

使用与磁盘类似的记录和读取技术
记录：介质时柔韧的聚酯薄膜带，外涂磁性材料
读取：

  • 磁带：顺序读取（sequential-access）
    • 磁盘：直接读取（direct-access）
  • 并行记录 vs 串行记录（蛇形记录，S型）

U盘和固态硬盘

U盘

  • 采用了快闪存储器，属于非易失性半导体存储器
  • 相比于软盘和光盘：体积小，容量大，携带方便，寿命长达数年

固态硬盘

  • 与U盘没有本质区别：容量更大，存储性能更好

  • 与硬磁盘存储器相比：抗振性好，无噪声，能耗低，发热量低

    无磁头结构，没有轴转动和磁头转动

11 冗余磁盘阵列（RAID）

  • 冗余磁盘阵列/独立磁盘冗余阵列：Redundant Arrays of Independent Disks(RAID)
  • 基本思想
    • 将多个独立操作的磁盘按某种方式组织成磁盘阵列，以增加容量
    • 将数据存储在多个盘体上，通过这些盘并行工作来提高数据传输率
    • 采用数据冗余来进行错误恢复以提高系统可靠性
  • 特性
    • 由一组物理磁盘驱动器组成，被视为单个的逻辑驱动器
    • 数据是分布在多个物理磁盘上
    • 冗余磁盘容量用于存储校验信息，保证磁盘万一损坏时能恢复数据

RAID分类

RAID 0

  • 数据以条带的形式在可用的磁盘上分布
  • 不采用冗余来改善性能（并非真正的RAID
  • 用途
    • 高数据传输率
    • 高速响应I/O请求

与单个大容量磁盘相比：

  • 高数据传输率：读取的时候可以多个物理磁盘并行读取，写的时候也可以对多个物理的磁盘进行同时读写。但对于单个磁盘，我们必须要进行顺序的存取。
  • 高速响应I/O请求：两个I/O请求所需要的数据块可能在不同的硬盘上。因此相比单个磁盘会有更高速的响应。
  • 代价：磁盘损坏概率升高

RAID 1

  • 采用了数据条带
  • 采用简单地备份所有数据的方法来实现冗余（即将磁盘分成了两半，一半为冗余盘，对原本数据进行拷贝）
  • 好处：
    • 硬盘损坏（只有一个）对整体没有影响，（若损坏多个硬盘呢？
    • 如果有两个位于同一个磁盘的I/O请求，RAID1也可以同时响应。
    • 数据传输率也会提高，因为可以对同一个磁盘上不同条带的数据进行同时存取（冗余盘和正常使用盘同时读取）
  • 坏处：对磁盘进行写操作的时候，需要写两个磁盘（冗余盘和正常使用盘），效率较低。但其实可以并行完成，取决于拷贝盘和数据盘中较慢的一个写来决定（即包含较大的寻道时间和旋转延迟的那一个写）。

优点：

  • 高速响应I/O请求：即便是同一个磁盘上的数据块，也可以由两组硬盘分别响应
  • 读请求可以由包含请求数据的两个对应磁盘中的某一个提供服务，可以选择寻道时间较小的那个
  • 写请求需要更新两个对应的条带：可以并行完成，但受限于写入较慢的磁盘
  • 单个磁盘损坏时不会影响数据访问，恢复受损磁盘简单

缺点

  • 价格昂贵

用途

  • 只限于用在存储系统软件/数据和其他关键文件的驱动器中

与RAID0相比

  • 如果有大批的读请求，则RAID1能实现高速的I/O速率，性能可以达到RAID0的两倍
  • 如果I/O请求有相当大的部分是写请求，则它不比RAID0的性能好多少。

RAID 01 vs RAID 10

  • RAID 01 = RAID 0 + 1:先做RAID 0，再做RAID 1
  • RAID 10 = RAID 1 + 0:先做RAID 1，再做RAID 0
  • 两者在数据传输率和磁盘利用率上没有明显区别，主要区别是对磁盘损坏的容错能力。（RAID 01较弱，因为不能跨越RAID 0进行合作。）
  • RAID 01 是先分好组的（即先组成RAID0，再组成RAID1），如果组里面有一个不能用了，那么该组的所有磁盘都会失效。这样就会导致容错率大大下降。

RAID 2

  • 采用并行存取技术
  • 目标
    • 所有磁盘都参与每个I/O请求的执行
  • 特点
    • 各个驱动器的轴是同步旋转的，因此每个磁盘上的每个磁头在任何时刻都位于同一位置
    • 采用数据条带：条带非常小，经常只有一个字节或一个字
  • 纠错
    • 对位于同一条带的各个数据盘上的数据位计算校验码（通常采用海明码），校验码存储在该条带中多个校验盘的对应位置
  • 访问
    • 读取：获取请求的数据和对应的校验码
    • 写入：所有数据盘和校验盘都被访问
  • 缺点
    • 冗余盘依然比较多，价格较贵
    • 适用于多磁盘易出错环境，对于单个磁盘和磁盘驱动器已经具备高可靠性的情况没有意义。

RAID 3

  • 采用并行存取技术

    • 各个驱动器的轴同步旋转
    • 采用非常小的数据条带

  • 对所有数据盘上同一位置的数据计算奇偶校验码

    • 当某一次盘损坏（已经明确知道哪一位是有问题的）时，可以用于重构数据

    • 优点：能够获得非常高的数据传输率

      • 对于大量传送，性能改善特别明显

    • 缺点：一次只能执行一个I/O请求

      • 在面向多个IO请求时，性能将受损

RAID 4

  • 采用独立存取技术

    • 每个磁盘成员的操作是独立的，各个I/O请求能够并行处理

  • 采用相对较大的数据条带

  • 根据各个数据盘上的数据来逐位计算奇偶校验条带，奇偶校验位存储在奇偶校验盘的对应条带上。

  • 性能

    • 当执行较小规模的I/O请求时，RAID4会遭遇写损失

      • 对于每一次写操作，阵列管理软件不仅要修改用户数据，而且要修改相应的校验位。

    • 每一次写操作必须涉及到唯一的校验盘，校验盘会成为瓶颈。

RAID 5

  • 与RAID4组织方式相似

  • 在所有磁盘上都分布了奇偶校验条带

    • 避免潜在的I/O瓶颈问题

  • 访问时的“两读两写”

RAID 50

RAID 5 与RAID 0 的组合，先作RAID 5，再作RAID 0，也就是对多组RAID 5 彼此构成条带访问

RAID 50在底层的任一祖或多组 RAID 5中出现一颗硬盘损坏时，仍能维持运作；如果任一祖RAID 5中出现2颗或2颗以上硬盘损毁，整组RAID 50就会失效

RAID 50由于在上层把多组RAID 5进行条带化，性能比起单纯的RIAD 5高，但容量利用率比RAID 5要低

RAID 6

  • 采用两种不同的校验码，并将校验码以分开的块存于不同的磁盘中
  • 优点
    • 提升数据可用性：只有在平均修复时间间隔内3个磁盘都出了故障，才会造成数据丢失
  • 缺点
    • 写损失：每次写都要影响两个校验块

12 虚拟存储器

操作系统

操作系统：一种控制应用程序运行和在计算机用户与计算机硬件之间提供接口的程序

目标：

  • 使计算机使用起来更方便
  • 允许计算机系统的资源以有效的方式使用

存储器管理

早期计算机的主存中仅包含系统软件和一个用户程序。 – 单道程序设计

现在计算机的主存中包含操作系统和若干个用户程序

  • 当所有任务都需要等待I/O时，为了避免处理器处于空闲状态，需要尽可能让更多的任务进入主存
  • 多道程序设计：让处理器一次处理多个任务，提高处理器的利用率

存储器管理

  • 在多道程序系统中，主存需要进一步划分给多个任务，划分的任务由操作系统动态执行
  • 这里不考虑“进程”这一概念。

如何将更多任务装入主存

  1. 增大主存容量
  2. 使用交换（exchange）技术
    • 当主存中没有处于就绪的任务时，操作系统调入其他任务来执行
    • 分区（partitioning）与分页（paging）
  3. 虚拟存储器
    • 请求分页：每次访问仅将当前需要的页面调入主存，而其他不活跃的页面放在外存磁盘上
    • 虚拟地址

分区方式

  • 分区方式：将主存分为两大地址
    • 系统区：固定的地址范围内，存放操作系统
    • 用户区：存放所有用户程序
简单固定分区
  • 用户区划分成长度不等的固定长分区
  • 当一个任务调入主存时，分配一个可用的，能容纳它的、最小的分区（一个区只能放一个任务，不能够将两个小任务放在同一个分区中）
  • 优点：简单
  • 缺点：浪费主存空间
可变长分区

  • 用户区按每个任务所需要的内存大小进行分配

  • 优点：提高了主存的利用率

  • 缺点：时间越长，存储器中的碎片就会越多

    做完大任务后的内存区域存入了一个小任务，就会留下一个较小的碎片的内存空间。（分散的，没有办法被联合起来使用的）

分页方式

基本思想：

  • 把主存分成固定长并且比较小的存储块，称为页框（page frame），每个任务也被划分成固定长的程序块，称为页（page）

  • 将页装入页框中，且无需采用连续的页框来存放一个任务中所有的页

逻辑地址：指令中的地址

物理地址：实际主存地址

页表：能够通过页表知道任务在主存中的物理地址

流程：指令中的逻辑地址通过页表查询到对应的物理地址，然后到主存中找到对应地址中的数据

虚拟存储器

问题：内存的大小是有限的，但对内存的需求不断增加

基本思想

  • 请求分页：仅将当前需要的页面调入主存
    • 通过硬件将逻辑地址转换为物理地址
    • 未命中时在主存和硬盘之间交换信息

优点：

  • 在不扩大物理内存的前提下，可以载入更多的任务
  • 编写程序时不需要考虑可用物理内存的状态
    • 程序员认为可以独享一个连续的、很大的内存
  • 可以在大于物理内存的逻辑地址空间中编程

设计的一些问题：

  1. 页大小
  2. 映射算法：全相连映射
  3. 写策略：写回
  4. 类型
    1. 分页式虚拟存储器
    2. 分段式虚拟存储器
    3. 段页式虚拟存储器

Cache和主存的速度差距比主存和硬盘的速度差距小很多，所以我们应该尽可能减少对硬盘的访问，提高对主存的利用率。

Cache比主存快10倍，主存比硬盘快100000多倍

分页式虚拟存储器

主存储器和虚拟地址空间都被划分为大小相等的页面

  • 虚拟页（virtual page, VP）/逻辑页（logical page）：虚拟地址空间中的页面
  • 物理页（physical page, PP）/页框（page frame）：主存空间中的页面
页表
  • 页表中包含了所有所有虚拟页的信息，包括虚拟页的存放位置、装入位（valid）、修改位（dirty）、存取权限位等
  • 保存在主存中
  • 编写程序时认为有一块很大、连续的存储空间，写的是虚拟地址
  • 虚拟地址：虚拟页号 + 页内偏移量

页表的存放位置

  1. null：还未存放任何东西，没有指针指向实际的主存物理地址
  2. PPx（x为数字）：指向主存中的一块
  3. 空：指向磁盘的一块

存放地址中存储的是一样长的数据，以指向内存中的页的物理地址的长度为准，不需要存放虚拟页号（因为页表中存储的是所有的虚拟页，不会再有多的虚拟页了）

虚拟页号 + 页内偏移量 -> 物理页号 + 页内偏移量

页内偏移量相同，因为虚拟页和物理页的大小是一样的

快表

Translation Lookaside Buffer, TLB

页表的使用增加了主存的访问次数

为了减少访问主存的次数，把页表中最活跃的几个页表项复制到Cache中

后备转换缓冲器（简称“快表”）：将页表项放入Cache中

  • 映射：关联映射，组关联映射
  • 替换：随机替换

主存中的页表相应地称之为“慢表”

CPU访存过程

注意如果页表项不在TLB中，我们需要在读取数据的同时更新TLB

TLB、页表、Cache的缺失组合

分段式虚拟存储器

将程序和数据分成不同长度的段，将所需的段加载到主存中。

虚拟地址：段号 + 段内偏移量

与分页式虚拟存储器相比：

  • 分页式虚拟存储器：
    • 优点：实现简单、开销少
    • 缺点：一个数据或一条指令可能会横跨两个页面
  • 分段式虚拟存储器
    • 段的分界与程序的自然分界相对应，易于编译
    • 会产生碎片，长度不固定

段页式虚拟存储器

将程序和数据分段，段内再进行分页

  • 每个分段都有一个页表

虚拟地址：段号 + 页号 + 页内偏移量

优点：程序按段实现共享与保护

缺点：需要多次查表

文章作者: ZY
文章链接: https://zyinnju.com/2022/02/15/COA-Review-2/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ZY in NJU！
计算机组织与结构Software EngineeringComputer ScienceComputer Organization and Architecture