6

存储器概述
- 存储器分类
  - 层次存储结构
- 性能指标
主存与cpu的连接及读写
- 主存芯片技术
- 读取/写入操作过程
磁盘存储器
高速缓冲存储器cache
虚拟存储器
- 虚拟存储器的实现
- 存储保护
IA-32+linux中的地址

存储器概述¶

基本术语
记忆单元（存储基元/存储元/位元）（Cell）
- 具有两种稳态的能够表示二进制数码0和1的物理器件
存储单元/ 编址单位（Addressing Unit）
- 具有相同地址的位构成一个存储单元，也称为一个编址单位（可由多个记忆单元构成，通常8个cell即一字节一个存储的单元）
存储体/ 存储矩阵/ 存储阵列（Bank）
- 所有存储单元构成一个存储阵列
编址方式（Addressing Mode）
- 字节编址、按字编址
存储器地址寄存器（Memory Address Register - MAR）
- 用于存放主存单元地址的寄存器
存储器数据寄存器（Memory Data Register-MDR (或MBR) ）
- 用于存放主存单元中的数据的寄存器

存储器分类¶

按工作性质/存取方式分类
随机存取存储器(RAM)
- 每个单元读写时间一样，且与各单元所在位置无关。如：内存
顺序存取存储器(SAM)
- 数据按顺序从存储载体的始端读出或写入，因而存取时间的长短与信息所在位置有关。例如：磁带。（需要按照顺序移动）
直接存取存储器(DAM)
- 直接定位到读写数据块，在读写数据块时按顺序进行。如磁盘。
相联存储器Associate Memory（AM） Content Addressed Memory (CAM)
- 按内容检索（而不是根据位置）到存储位置进行读写。例如：快表。
按存储介质分类
半导体存储器：双极型，静态MOS型，动态MOS型
磁表面存储器：磁盘（Disk）、磁带（Tape）
光存储器：CD，CD-ROM，DVD
按信息的可更改性分类
读写存储器（Read / Write Memory)：可读可写
只读存储器（Read Only Memory)：只能读不能写
按断电后信息的可保存性分类
非易失（不挥发）性存储器(Nonvolatile Memory) 信息可一直保留，不需电源维持。
- 如：ROM、磁表面存储器、光存储器等
易失（挥发）性存储器(Volatile Memory) 电源关闭时信息自动丢失。
- 如：RAM、Cache等
按功能/容量/速度/所在位置分类
寄存器(Register)
- 封装在CPU内，用于存放当前正在执行的指令和使用的数据
- 用触发器实现，速度快，容量小（几~几十个KB）
高速缓存(Cache)
- 位于CPU内部或附近，用来存放当前要执行的局部程序段和数据-
- 用SRAM实现，速度可与CPU匹配，容量小（几MB）
内存储器MM（主存储器Main(Primary)Memory）
- 位于CPU之外，用来存放已被启动的程序及所用的数据
- 用DRAM实现，速度较快，容量较大（几GB）
外存储器AM(辅助存储器Auxiliary/Secondary Storage)
- 位于主机之外，用来存放暂不运行的程序、数据或存档文件
- 用磁盘、SSD等实现，容量大而速度慢
CPU首先把欲访问的主存单元的地址送到主存地址寄存器
后通过地址线将主存地址送到主存中的地址寄存器，以便地址译码器进行译码后选中相应单元
同时，CPU将读／写控制归通过控制线送到主存的读写控制电路
- 如果是写操作，CPU同时将要写的信息送主存数据器MDR
- 在读写控制电路的控制下，经数据线将信息写入选中的单元
- 如果是读操作，则主存读出选中单元的内容送数据线，然后送到MDR中
数据线的宽度与MDR的宽度相同，地址线的宽度与MAR的宽度相同。
- 图中采用64位数据线，因此，在字节编址方式下，每次最多可以存取8个字节的内容
- 地址线的位数决定了主存地址空间的最大可寻址范围，例如，36位地址的最大可寻址范围为0~2³⁶-1。
F|ash存储器也称为闪存，是高密度非易失性读写存储器，它兼有RAM和ROM的优点．而且功耗低、集成度高，不需后备电源。这种器件可在计算机内进行擦除和编程写入，因此又称为快擦型电可擦除重编程ROM。目前被广泛使用的U盘和存储卡等都屈千Flash存储器、也用千存放BIOS

层次存储结构¶

单独用某一种存储器，都不能满足我们的需要

性能指标¶

存储容量：所包含的存储单元的总数（单位：MB或GB）
存取时间TA ：从CPU送出内存单元的地址码开始，到主存读出数据并送到CPU（或者是把CPU数据写入主存）所需要的时间（单位：ns，1ns=10^-9s），分读取时间和写入时间
读取时间：指从存储器接到读命令开始至信息被送到数据线上所需的时间
写入时间：指存储器接到写命令开始至信息被写入存储器所需的时间
存储周期TMC ：连读两次访问存储器所需的最小时间间隔，它应等于存取时间加上下一次存取开始前所要求的附加时间，因此， TMC 比TA 大（因为存储器由于读出放大器、驱动电路等都有一段稳定恢复时间，所以读出后不能立即进行下一次访问。）
存储器带宽B：表示存储器被连续访问时可以提供的数据传送速率，通常用每秒传送信息的位数（或字节数）来衡量。
带宽下用10底数，容量下用2底数
- 如速率\(40MB/s\)读取\(4KB\)
- \((4*2^{10})/(40*10^{6})=0.1024ms\)

主存与cpu的连接及读写¶

主存芯片技术¶

DRAM芯片¶

动态存储芯片大多采用双译码结构。地址译码器分为X和Y方向两个译码器。如图6.4所示的就是二维双译码结构，其中的存储阵列有4096个单元，需要12根地址线。（\(\lceil\log_2 64\rceil=6\) ）
典型的16M位DRAM（4Mx4）
16M位= 4Mbx4 = 2048x2048x4 = 2¹¹x2¹¹x4
地址线：11根线分时复用，由RAS和CAS提供控制时序
需4个位平面，对相同行、列交叉点的4位一起读/写
行地址和列地址分时复用, 每出现新一代DRAM芯片，至少要增加一根地址线。每加一根地址线，则行地址和列地址各增加一位，所以行数和列数各增加一倍。因而容量至少提高到4倍。
- A0-A10十一位地址引脚线（RAS DAS行列交换使用）
- D1-D4四个数据引脚，每次可以读出4位（即平面数目）数据
- WE读写控制
- OE输出使能驱动

SDRAM¶

传统DRAM与CPU之间采用异步方式交换数据，CPU发出地址和控制信号后，经过一段延迟时间，数据才读出或写入。在这段时间里，CPU不断采样DRAM的完成信号，在没有完成之前，CPU插入等待状态而不能做其他工作。而SDRAM芯片则不同，其读写受外部系统时钟（即前端总线时钟CLK)控制，因此与 CPU之间采用同步方式交换数据。它将CPU或其他主设备发出的地址和控制信息锁存起来，经过确定的几个时钟周期后给出响应。因此，主设备在这段时间内，可以安全地进行其他操作。
ddr内存采用这种技术

内存的物理构成¶

总线宽度指的就是数据线的宽度
行缓冲是对特定行的所有列的每一层进行缓冲
单个内存条由多个存储芯片共同构成，每个存储芯片还会叠很多层，不同层中同一个位置同时读取（超元）
位扩展指用若干片位数较少的存储器芯片构成给定字长的存储器。例如，用8片4Kx 1位的芯片构成 4K x8位的存储器，需在位方向上扩展8倍，而字方向上无须扩展。
不改变控制位的数目(只能同时读取)
字扩展是容量的扩充，位数不变。例如，用16Kx8位的存储芯片在字方向上扩展4倍，构成一个64Kx8位的存储器。
字扩展会增加控制位的数目（可以不同时读取）
位扩展和字扩展都会增大存储的容量！
当芯片在容址和位数上都不满足存储器要求的情况下，需要对字和位同时扩展。例如，用16Kx4位的存储器芯片在字方向上扩展4倍、位方向上扩展2倍，可构成一个64Kx8位的存储器。
同时读取8（层数）*8（芯片数目）= 64个字节同时读取
- 同时读取不同芯片处于同一坐标的不同层！交叉编址
方便缓存，快速存取
将8个内存芯片以字扩展组成一块内存，0~7、8~15等属于一块芯片的不同层，可以同时读取，这体现了内存对齐的意义

读取/写入操作过程¶

引脚数=log(max(行数，列数))
输入行后把一行缓冲到SDRAM，输入列后，从缓存处理指定的列

磁盘存储器¶

磁盘存储器的结构¶

间隙用全1表示
柱面是指由同一磁头在同一磁盘上扫描时能够覆盖到的所有磁道的集合。简单来说，柱面就是位于不同磁道但在同一半径位置上的所有磁道的集合。
所有磁头同步移动位置相同（不同磁盘处于相同位置的扇区属于同一个柱面，但同时只有一个磁头在使用）

工作原理¶

磁头号、扇区号存储在磁盘地址寄存器中

性能指标¶

记录密度¶

道密度：沿磁道分布方向上单位长度内的磁道数目
位密度:在沿磁道方向上，单位长度内存放的二进制信息数目
低密度存储：所有磁道上的扇区数相同，所以每个磁道上的位数相同，因而内道上的位密度比外道位密度高
高密度存储：每个磁道上的位密度相同，所以外道上的扇区数比内道上扇区数多，因而整个磁盘的容量比低密度盘高得多

存储容量¶

指整个存储器所能存放的二进制信息批，它与磁表面大小和记录密度密切相关
硬盘的未格式化容量是指按道密度和位密度计算出来的容量，它包括了头空、ID域、CRC 码等信息，是可利用的所有磁化单元的总数，格式化后的容量仅包括数据区的大小（512字节每扇区）
格式化容量（实际数据容量）：磁盘实际数据容量＝2x盘片数x磁道数／面x扇区数／磁道x512B／扇区
记录面数通常为盘数二倍（双面使用）
低密度：
磁盘总容量＝记录面数x理论柱面数x内圆周长x最内道位密度
高密度：
柱面数＝（有效记录区外径－有效记录区内径)/2x道密度

数据传输速率¶

是指磁表面存储器完成磁头定位和旋转等待以后，单位时间内从存储介质上读出或写入的二进制信息量。
也成为内部传输速率（持续传输速率）
外部传输速率是指主机从外设控制接口外存储器的缓存读出（写入）数据的速度（突发数据传输速率，接口传输速率）
由于磁盘在同一时刻只有一个磁头进行读写
内部数据传输速率＝每分钟转速/60 x内圆周长x最内道位密度

平均存取时间¶

硬盘操作流程：
所有磁头同步寻道（由柱面号控制）内外移动
选择磁头（由磁头号控制）
被选中磁头等待扇区到达磁头下方（由扇区号控制）
读写该扇区中数据
磁盘信息以扇区为单位进行读写，平均存取时间为：
还包括磁盘控制器的开销时间（如果有的话）
T = 平均寻道时间+ 平均旋转等待时间+ 数据传输时间（忽略不计）
平均寻道时间——磁头寻找到指定磁道所需平均时间(约5ms)
平均旋转等待时间——指定扇区旋转到磁头下方所需平均时间 (约4～6ms) ( 转速： 4200 / 5400 / 7200 / 10000rpm 以分钟为单位)
数据传输时间——( 大约0.01ms / 扇区）
通常将复杂的磁盘物理扇区抽象成固定大小的逻辑块，物理扇区和逻辑块之间的映射由磁盘控制器来维护。磁盘控制器是一个内置固件的硬件设备，它能将主机送来的请求逻辑块号转换为磁盘的物理地址（柱面号、磁头号、扇区号），并控制磁盘驱动器进行相应的动作。
磁盘的最小读写单位是扇区，因此磁盘按成批数据交换方式进行读写，采用直接存储器存取（DMA，Direct Memory Access）方式进行数据输入输出，需用专门的DMA接口来控制外设与主存间直接数据交换，数据不通过 CPU。通常把专门用来控制总线进行DMA传送的接口硬件称为DMA控制器（在读取期间cpu可以继续去处理其他事情）
读取步骤
磁盘控制器初始化
磁盘读取数据，发送到主存
DMA告知CPU读取完成，请求处理

固态硬盘¶

它并不是一种磁表面存储器，而是一种使用NAND闪存组成的外部存储系统，与U盘并没有本质差别，只是容量更大，存取性能更好。
在SSD中有一个闪存翻译层，它将来自CPU的逻辑磁盘块读写请求翻译成对底层SSD物理设备的读写控制信号。因此，这个闪存翻译层相当于磁盘控制器

高速缓冲存储器cache¶

在较短时间间隔内，程序产生的地址往往集中在一个很小范围内这种现象称为程序访问的局部性：空间局部性、时间局部性
空间局部性：刚被访问过的单元的邻近单元很可能不久被访问
- 如：数组
时间局部性：刚被访问过的单元很可能不久又被访问
- 如：循环
而在缓存层次结构中，存储的是以字节为单位的数据，不涉及多字节数据的大小端问题。
在CPU和主存之间设置一个快速小容量的存储器（cache），其中总是存放最活跃（被频繁访问）的程序和数据，由于程序访问的局部性特征，大多数情况下，CPU能直接从这个高速缓存中取得指令和数据，而不必访问主存

原理¶

Cache是一种小容量高速缓冲存储器，它由SRAM组成，以块（如64字节）为单位进行存取。
主存被分成若干大小相同的块，称为主存块 (Block)，Cache也被分成相同大小的块，称为Cache行（line）或槽（Slot）。
cache的存在对程序员是透明的，无论使用什么语言都不能感知到cache的存在

cache映射¶

把访问的局部主存区域取到Cache中时，该放到Cache的何处？ Cache行比主存块少，多个主存块映射到一个Cache行中
方式
直接(Direct)：每个主存块映射到Cache的固定行
全相联(Full Associate)：每个主存块映射到Cache的任一行
组相联(Set Associate)：每个主存块映射到Cache固定组中任一行

直接映射¶

依据模映射的规则
加入Cache有16行，那么第100块主存应该映射到4=100 mod 16
特点
容易实现，命中时间短
无需考虑淘汰（替换）问题
缺点：换进换出频繁，命中率低，Cache利用率低
- 比如即使其他块都空着，在需要用0和16时也需要频繁更替
标记位数计算公式：
若cache有\(2^c\)行，主存有\(2^m\)块，块大小大小为\(2^b\)字节。即编码中cache行号有\(c\)位，主存块号有\(m\)位，块内地址b位。标记字段长度\(t=m-c\)（块群的数目）
将主存储器按照Cache缓存的大小划分为块群，每个块群中第i个块映射到cache中第i个槽
主存标记+Cache索引=主存块号
完整还原主存地址=主存标记+Cache 索引+块内地址
- 主存地址0000001 0010 000001100->块号00000010010（群号0000001行号0010）块内地址000001100
注意tag中只存储主存标记（块群号）
在最前面还需要一位标记，表示是否为空
从cache中取数据
首先依据标志位和地址判断是否hit
主存地址00000010010 000001100=块号00000010010+块内地址000001100
然后如果要取的是32位数据，则只需要看前两位偏移，否则还需有后两位
块大小指的是存储有效数据的大小不包含v和tag
32(data大小)+（32-14-2）（主存地址总大小-表示块数目-块内地址）+1（标志位）
- 地址总长度不一定是32，这是与主存（地址空间的大小相关的）

全相连映射¶

每一块可以放到cache中的任意位置
标记中存储对应的主存块号
地址=
每次从cache中寻找一个块都需要对所有行进行比较，才能知道是否能命中，以及在什么位置（按内容访问）
速度块，利用率高，但是成本高（比较器多、tag长）

组相联映射¶

组相联映射结合直接映射和全相联映射的特点
将Cache所有行分组，把主存块映射到Cache固定组的任一行中。也即：组间模映射、组内全映射。
结合直接映射和全相联映射的优点。当Cache组数为1时，变为相联映射；当每组只有一个槽时，变为直接映射。
每组2或4行（称为2-路或4-路组相联）较常用。通常每组4 行以上很少用。在较大容量的L2 Cahce和L3 Cahce中使用 4-路以上
标记位数计算公式：
若cache有\(2^c\)行，分成\(2^q\)组，即每组\(2^{c-q}\)行，主存有\(2^m\)块，块大小大小为\(2^b\)字节。即编码中cache行号有\(c\)位，主存块号有\(m\)位，块内地址b位。标记字段长度\(t=m-q\)
在tag中存储块来自哪一个组群
寻找一个块时到对应的组中并行比较tag
易于实现，速度快，利用率高

性能评估¶

命中率¶

\(t=at_c+(1-a)(t_c+t_m)=t_c+(1-a)t_m\)
平均消耗时间等于命中率乘以命中时间加上缺失率乘以命中时间加上缺失损失
例：
- 如果\(t_C=4ns\) \(t_m=40ns\)那么如果目标\(t=5ns\)命中率要达到多少？

缺失率和关联度¶

Cache替换¶

替换算法¶

FIFO¶

LRU最近最少用¶

LRU是一种栈算法，它的命中率随组的增大而提高。
当分块局部化范围(即：某段时间集中访问的存储区)超过了 Cache存储容量时，命中率变得很低。极端情况下，假设地址流是1,2,3,4,1 2,3,4,1,……，而Cache每组只有3行，那么，不管是FIFO，还是LRU算法，其命中率都为0。这种现象称为颠簸 (Thrashing / PingPong)
LRU具体实现时，并不是通过移动块来实现的，而是通过给每个 cache行设定一个计数器，根据计数值来记录这些主存块的使用情况。这个计数值称为LRU位。
数值越小表示最近使用
命中时被访问的计数器置为0，比前变化前的值低的计数器全部加1
未命中且未满时置为0，所有其他的加1
未命中且已满时计数值为3的被淘汰，其余加1
- 提高倍率：用cache前的时间/用cache后的时间
- 一个块中有多个字节按顺序读取算多次（所以术后只有第一字不命中）

写策略（一致性问题）¶

因为Cache中的内容是主存块副本，当对Cache中的内容进行更新时，就存在Cache和主存如何保持一致的问题。
尤其当多个io设备可以读写内存时，如果Cache中的内容被修改，则I/O设备读出的对应主存单元的内容无效；若I/O设备修改了主存单元的内容，则Cache中对应的内容无效。
写操作有两种情况
写命中（Write Hit）：要写的单元已经在Cache中
- Write Through (通过式写、写直达、直写)：
- 同时写Cache和主存单元
- 但是效率低，10%的存储指令使CPI增加到：1.0+100x10%=11
- 可以使用写缓冲（改进）
- Write Back (一次性写、写回、回写)：
- 锁死主存
- 当主存块被替换时执行回写
- 只写cache不写主存，缺失时一次写回，每行有个修改位（“dirty bit-脏位”标记是否修改过，即是否需要进行会写），大大降低主存带宽需求，控制可能很复杂
写不命中（Write Miss）：要写的单元不在Cache中
- Write Allocate (写分配)：
- 先在主存中直接更新数据
- 将主存块装入Cache
- 试图利用空间局部性，但每次都要从主存读一个块
- Not Write Allocate (非写分配)：
- 直接写主存单元，但不把主存块装入到Cache
写cache后同时写主存

Cache与程序性能¶

多级缓存¶

L1数据和指令分开存储；L2、L3混合存储
如果有两级存储，那么L1更关心速度（因为即使没有命中，L2也很快）；L2更关心命中率（因为主存太慢了）
L1、L2为核私有；L3为所有核共享

例题¶

虚拟存储器¶

基本思想：把地址空间和主存容量的概念区分开来。程序员在地址空间里编写程序，而程序则在真正的内存中运行。由一个专门的机制实现地址空间和实际主存之间的映射。
地址转化过程是由CPU中的存储器管理部件MMU来完成的
引入虚拟寄存器是为了解决应用程序大小与主存容量限制之间的矛盾
实质
程序员在比实际主存空间大得多的逻辑地址空间中编写程序
程序执行时，把当前需要的程序段和相应的数据块调入主存，其他暂不用的部分存放在磁盘上
指令执行时，通过硬件将逻辑地址（也称虚拟地址或虚地址）转化为物理地址（也称主存地址或实地址）
在发生程序或数据访问失效(缺页)时，由操作系统进行主存和磁盘之间的信息交换
系统会为不同的进程分配不同的页表
虚拟存储器机制由硬件与操作系统共同协作实现，涉及到操作系统中的许多概念，如进程、进程的上下文切换、存储器分配、虚拟地址空间、缺页处理等。
先建立映射关系等到真正使用时再从硬盘加载到主存

虚拟存储器的实现¶

分页式¶

内存被分成固定长且比较小的存储块（页框、实页、物理页）：主存中
每个进程也被划分成固定长的程序块（页、虚页、逻辑页）：磁盘中
程序块可装到存储器中可用的存储块中
操作系统为每个进程生成一个页表，通过页表(page table)实现逻辑地址向物理地址转换；因此无需用连续页框来存放一个进程。
逻辑地址：程序中指令所用地址(进程所在地址空间)，也称为虚拟地址
物理地址：存放指令或数据的实际内存地址，也称为实地址、主存地址。

页表（慢表）¶

采用全相联映射
将虚拟地址的虚拟页映射到主存中的实际存在的物理页
装入位表示是否为空，修改位（脏位，是否修改了数据需要回写），替换控制位（如 LRU 标记位），其他（如访问权限、禁止缓存等）
页的状态
装入位是1表示hit
0表示miss：分为两种情况（未分配、未缓存）都需要从磁盘读取
实现访问转化
- 与cache类似，前面是页码（tag）后面是页内地址（最后是要读取页中的一个块）
- 虚拟地址->物理地址(虚拟的页->主存上实际存在的)
- 页内偏移量不变，实际上转化的是页号

快表TLB¶

采用组相联映射
为了减少访问主存的次数，把经常要查的页表项放到Cache中（不是把页拿出来，是页表的内容）
tag使用虚页号表示
先在快表中查找，找不到则到慢表中查找
快表需要tag是因为不是按顺序排列并且存在缺号，而慢表中不需要使用tag因为是按顺序连续存储的，可以直接通过index进行访问
如果在TLB中找不到，则要从主存读取后放入TLB，如果TLB满了，使用随机替换策略
总结：
- 不在主存中则也不在cache中
- 不在TLB中则也不在页表中
- 不在页表中则也不在主存中，更不在cache中

例子¶

\(VA=VPN+VPO=(TLBT+TLBI)+VPO\)
\(PA=PPN+PPO=(CT+CI)+CO\)
PPO的位数由页的大小决定
四相联，因此有两位表示组号，故(8-2)位为tag
从第三组寻找tag为3的项，得到PPN=OD，与VPO拼起来得到物理地址（变化的只是页号，页内偏移量是相同的）
得到物理地址后再尝试从cache获取快

分段式¶

不等长分配，按照需求进行分配
问题：
占用空间多，存在间隙，浪费碎片空间

段页式¶

程序的虚拟地址空间按模块分段、段内再分页，进入主存仍以页为基本单位
逻辑地址由段地址、页地址和页内偏移量三个字段构成
用段表和页表（每段一个）进行两级定位管理
根据段地址到段表中查阅与该段相应的页表首地址，转向页表，然后根据页地址从页表中查到该页在主存中的页框地址，由此再访问到页内某数据
问题：访问流程相对复杂

存储保护¶

IA-32+linux中的地址¶

段页式存储
逻辑地址<--->线性地址（分段）<--->物理地址（分页）
逻辑地址由48位组成，包含16位段选择符（存放在段寄存器）和32位段内偏移量（即有效地址）
线性地址32位（其位数由虚拟地址空间大小决定）
物理地址32位（其位数由存储器总线中的地址线条数决定）
分段过程实现将逻辑地址转换为线性地址
分页过程实现将线性地址转换为物理地址

寻址方式¶

后面基址、比例因子等计算得到的是32位的段内地址，还需要在前面加上16位的段选择符
段选择符通常是一个隐藏的参数
使用段寄存器获取到段选择符，再获取（段描述符）段表项中关于端的信息（开始地址、长度等）得到段基址，加上计算的地址（段内偏移量）得到线性地址

段寄存器¶

ES、GS和FS可指向任意数据段

段选择符¶

段寄存器存储的是段选择符，用于指示段描述符的位置

段描述符¶

段描述符指的是段表中的一项
cache会在更换进程（程序段）时自动进行相关数据（段描述符）的缓存，减少访问主存中段表的次数
- 段寄存器都有隐藏空间（用于存储段选择符对应的段描述符的关键信息）
S位为0时
- 系统描述符（System Descriptor）：包括任务门（Task Gate）、调用门（Call Gate）、中断门（Interrupt Gate）和陷阱门（Trap Gate）。
S位为1时
- 代码段（Code Segment）：用于存储执行代码的段。
- 数据段（Data Segment）：用于存储数据的段，可以包括栈段（Stack Segment）、堆段（Heap Segment）等。