【知识总结】 第三章-存储器层次结构

存储器概述

• 存储元：一个二进制物理器件
• 存储单元：多个存储元组成，一般是一次存取的单位
• 存储体：若干存储单元

存储器分类

• 按作用/层次分类
  • 主存储器
    • 即内存，存放计算机运行期间的数据和程序
    • CPU可以直接进行访问，也可以和Cache和辅存交换数据
    • 容量较小，速度较快，价格较高
  • 辅助存储器
    • 即外存，存放暂时不用的数据和程序，或需要长期保存的信息。
    • CPU不能直接访问
    • 容量大，速度慢，成本低
  • 高速缓冲存储器
    • 即Cache，位于主存和CPU之间，存放正在执行的程序段和数据，加速CPU访问数据
    • CPU可以直接进行访问，可以和内存交换数据
    • 容量小，价格高，存取速度和CPU速度匹配
• 按存取方式分类
  • 随机存储器RAM
    • 存取时间和位置无关，可随机存取，使用方便
    • 常用于主存和缓冲存储器
    • 可分为静态RAM（SRAM），动态RAM（DRAM）
  • 只读存储器ROM
    • 只能随机读出，不能写入
    • 通常存放不变的程序、字库、常数，和RAM共同作为主存的一部分
  • 串行访问存储器
    • 顺序存取存储器SAM：只能按某种顺序存取，存取时间和位置有关，速度慢，如磁带
    • 直接存取存储器DAM：不是全局随机存取，也不是完全顺序存取，折中方案。先确定数据所在小区域，在区域内顺序查找，如磁盘、光盘（详见第7章笔记）
• 按存储介质分类
  • 磁表面存储器
    • 磁盘
    • 磁带
  • 磁芯存储器
  • 半导体存储器
    • MOS型存储器
    • 双极型存储器
  • 光存储器
    • 光盘
    • 比如CD-ROM是只读型光盘，串行访问存储器，不是只读存储器ROM
    • 详见第7章笔记
• 按信息的可保存性分类
  • 易失性存储器
    • 断电后存储信息就会消失
    • 如RAM
  • 非易失性存储器
    • 断电后存储信息不会消失
    • 如ROM、磁表面存储器、光存储器

存储器性能指标

• 存储容量
  • 存储字数字长
  • 字数是地址空间大小，字长是一次存取的数据量
• 单位成本：总成本/总容量
• 存储速度
  • 存取时间：启动一次存储器操作到完成操作所需时间，具体区分为读出时间、写入时间
  • 存取周期
    • 两次独立访存之间所需最小时间间隔，即完整一次读写操作需要的时间
    • 存取周期分为存取时间和恢复时间（有的存取是有破坏性的，需要恢复），因此一般情况
  • 数据宽度：一个周期内可以从存储器进出的数据量
  • 数据传输率：
    • 又叫主存带宽，是单位时间内从主存进出的最大数据量
    • ，单位可以是字/秒、B/s、b/s

层次化存储器的基本结构

• 多级存储系统的目的：解决存储器大容量、高速度、低成本的矛盾，上层作为下层的高速缓存（数据是副本），使得CPU访问速度接近最上层，容量和成本接近最下层，性价比大幅度提高
• 层级结构从上到下：
  • 寄存器、Cache、主存、磁盘、磁带或光盘
  • 速度和成本递减，容量递增
• 主要层次
  • Cache-主存层次
    • 构成高速缓冲存储器，解决CPU和主存速度不匹配的问题
    • 速度接近Cache，容量和成本接近主存
    • 数据调动由硬件自动完成，对所有程序员透明（看不见）
  • 主存-辅存层次
    • 构成虚拟存储系统，解决存储系统的容量问题
    • 速度接近主存，容量和成本接近辅存
    • 数据调动由硬件和操作系统共同完成，对应用程序员透明（看不见）
• CPU、Cache、主存相互之间可以直接交换信息，辅存只能和主存交换信息

半导体随机存取存储器

• RAM（全称random-access memory）和ROM（全称read-only memory）都属于半导体存储器
• 前者支持随机存储，后者部分支持随机存储

SRAM存储器

• 又叫做静态随机存储器，常用于实现Cache
• 易失性存储器
• 存储元一般是双稳态触发器（六晶体管MOS），非破坏性读出
• 行列独立技术，组织成数组，地址信号一次传送
• 相比DRAM价格高，存取快，集成度低，容量较小，功耗大
• 不需要刷新（后面会解释刷新）

DRAM存储器

• 又叫做动态随机存储器，常用于实现主存储器
• 易失性存储器
• 存储元一般是栅极电容（单晶体管），比SRAM密度高很多，大都是破坏性读出
• 行列地址复用技术，组织成矩阵，地址信号分行列两次传送
• 相比SRAM价格低，存取慢，集成度高，容量大，功耗低
• DRAM为了维持电荷，需要在刷新周期内（通常2ms）刷新
  • 刷新方法
    • 集中刷新：停止读写，用一段固定时间（少于刷新周期）刷新，读写不受刷新影响但期间不能访问存储器（称为死区）
    • 分散刷新：每个存储周期内（通常微秒级别，且存取时间和刷新时间各占存储周期的一半）刷新一行，分多个周期刷新，没有死区但存取周期长
    • 异步刷新：前两个方法的结合，根据刷新周期/行数，得到两次刷新行操作需要的时间间隔t，利用逻辑电路t时间产生一次刷新请求进行刷新，比集中刷新的死区短，比分散刷新的刷新次数少
  • 刷新说明
    • 以行为单位进行刷新，所有存储芯片的同一行同时刷新
    • 刷新对CPU透明，芯片内部自行生成行地址
    • 刷新内部本质类似于读操作，一次刷新时间等于一次访存时间
    • 不是易失性存储器都需要刷新，比如SRAM不需要，DRAM需要

ROM存储器

• 和RAM一样都是支持随机存取的存储器，但只供读出
• 非易失性半导体存储器，可靠性高
• 结构简单，位密度比可读写存储器高
• 类型包括
  • 掩模式只读存储器MROM
    • 半导体制造厂按用户要求在生产时写入，此后无法改变
    • 可靠性高、集成度高、便宜，但不灵活
  • 一次可编程只读存储器PROM
    • 可以实现一次性编程的只读存储器
    • 写入后无法改变
  • 可擦除可编程只读存储器EPROM
    • 可以由编程器写入信息
    • 写入后可以先擦除全部内容再修改
    • 分为紫外线擦除UVEPROM和电擦除EEPROM
    • 虽然可读可写，但是编程次数有限，写入时间很长，无法代替RAM
  • 闪速存储器Flash Memory
    • 在EPROM和EEPROM基础上发展起来的
    • 具备EPROM价格便宜，集成度高的特点
    • 具备EEPROM的性能，且可以快速读取、快速擦除和重写
    • 断电后可长期保存信息
    • 反复写后会磨损
    • 比如U盘和MP3
    • 具体分为两种
      • NOR Flash：读取速度快，用户能直接运行NOR Flash中代码，适合小容量存储器
      • NAND Flash：一次读一个块，价格便宜，用户不能直接运行NAND Flash中代码，适合大容量存储器
  • 固态硬盘Solid State Drive（SSD）
    • 基于闪存技术，用固态电子存储芯片阵列制成（固体电容称作Solid）
    • 和U盘本质差不多，但容量更大，存取性能更好
    • 由控制单元（Flash翻译层）和存储单元（Flash芯片或DRAM芯片）组成
    • 和Flash存储器一样可长期保存信息、可快速擦除重写
    • 比传统磁盘读写快、质量轻、功耗低、体积小、抗震性好、安全性高、无噪音
    • 缺点是价格高、容量不算很大、寿命短、容易磨损、数据破坏后难恢复

主存储器

主存储器的组成

• 地址寄存器：和CPU的MAR通过地址线相连
• 地址译码器：对地址寄存器内容进行译码，选择相应存储单元
• 存储体：字数个存储单元组成，每个存储单元是字长个存储元件（0和1）
• 读写控制电路：接收CPU中读写控制信号，控制存储体和CPU的MDR交换信息
• MAR和MDR的位数对应存储器中的字数的位数和字的位数（即字长）

DRAM芯片和内存条

DRAM存储芯片

• 内部结构
  • 存储体：即存储矩阵，由行选择线、列选择线访问单元。
  • 地址译码器：根据地址驱动相应读写电路
  • 读写控制逻辑（IO控制电路）：控制被选中的存储单元的输入和输出
• 外部引脚
  • 地址线：位数和存储空间大小有关
  • 数据线：位数和存储单元大小有关
  • 读写控制线：2位线（读线、写线，若共用则只需要1位线）
  • 片选信号线：1位CS线，存储器一般用多个芯片进行拓展，访问时需要片选信号控制是否选该片
  • 电源线和地线
• DRAM芯片需要定时刷新、地址线采用复用技术（地址线为正常的一半，容易忽略）
• 常见的DRAM芯片有
  • EDORAM：extend data output RAM
  • DDR RAM：double data rate RAM，也叫DDR SDRAM。一个时钟读写两次，传输速度加倍
  • SDRAM：synchronous dynamic RAM
• DRAM芯片读写周期
  • 读写周期表示DRAM芯片两次连续读写操作所必须间隔的时间
  • 读出（写入）时间比如读写周期小，从地址有效开始，并要求CS地址片选信号有效
  • RAS有效后将行地址送入引脚
  • CAS有效后将列地址送入引脚
  • 读周期时为高电平，需要在CAS有效前建立
  • 写周期时为低电平，需要在CAS有效前建立；写数据在CAS有效前保持稳定

内存条

• 对容量较小的单个芯片进行拓展，将多个芯片集成到一个内存条上，再由多个内存条和主板的ROM芯片组成主存空间
• 拓展的方法有
  • 位拓展
    • 加大字长
    • 各芯片读写信号相连，接CPU读写控制线
    • 各芯片地址线相连，接系统地址总线
    • 各芯片的片选线相同，保证同时选中（各芯片的同位置单元）
    • 各芯片单独引出各自的数据线，连接数据总线的各对应位
  • 字拓展
    • 加大字数
    • 各芯片读写信号相连，接CPU读写控制线
    • 各芯片地址线相连，接系统地址总线的低位
    • 各芯片的片选线不同，由系统地址总线的高位译码得到（后面将提到片选信号的译码方法）
    • 各芯片的数据线，连接数据总线
  • 字位同时拓展
    • 加大字数和字长，各芯片分组，组内进行位拓展，组间进行字拓展
    • 各芯片读写信号相连，接CPU读写控制线
    • 各芯片地址相连，接系统地址总线低位
    • 各芯片片选线组间不同、组内相同。由系统地址总线的高位译码得到
• 片选信号的译码方法
  • 线选法
    • 高位的每位各自直接（或经过反相器）接到各芯片的片选端口，高位的各位中只能有一个1（或一个0）。
    • 优点是不需要地址译码器，线路简单
    • 缺点是地址不连续，空间利用不充分即地址资源存在浪费
  • 译码法
    • 需要地址译码器，个高位对应个输出线，接到对应的片的片选信号端口
    • 地址连续
    • 根据高位是否全部被使用进行译码，进一步分为全译码法和部分译码法

主存和CPU之间的连接

• 主存储器通过数据总线、地址总线、控制总线连接到CPU的MDR、MAR、读写控制信号
• 数据总线的位数就是数据宽度（前面存储器性能小节中提到过），当存储芯片位数不足数据宽度时需要用多个芯片进行位拓展
• 地址总线的位数决定了可寻址最大空间
  • 一般地址总线高位接到主存的地址译码器，一般是74LS138译码器。译码器的输入还需要接CPU的访存控制信号，低电平有效，比如访问io时为高电平，表示不需要访问存储
  • 一般地址总线低位接到每个芯片的地址线
• 控制总线指出了总线周期的类型（读或写）和本次操作完成的时刻。
  • 如果读写只用一根线，一般高电平为读，低电平为写
  • 如果读写各自用一根线，则读命令线和写命令线都是低电平有效

双端口RAM和多模块存储器

• 为了提高CPU访存速度，采用双端口RAM（空间并行）、多模块存储器（时间并行）
• 双端口RAM
  • 存储器左右两个独立端口，有独立的数据线、地址线、控制线
  • 两个控制器允许同时异步的访问存储单元
  • 如果对不同地址读写，或对同一地址读，无冲突
  • 如果对同一地址写则有写冲突；如果对同一地址读和写，则有读冲突
  • 解决冲突的方法
    • 把信号置0，相当于暂时关闭一个端口，延迟其访问
    • 对每个存储看单元的数据进行CPU的权限分配
• 多模块存储器
  • 单体多字存储器
    • 一个存储体，每个存储单元多个字，比如m个
    • 总线宽度也是m个字，一次并行读出
    • 一个存取周期能取出m个指令，每隔1/m周期CPU向主存取一条指令，带宽增加
    • 缺点是只能处理连续情况，遇到转移指令，效果不明显
  • 多体并行存储器（多体交叉存储器）
    • 多个存储体模块，每个模块有独立的控制电路、地址寄存器、数据寄存器，可并行
    • 高位交叉编址：高位表示体号，低位表示体内地址，本质还是顺序访问，吞吐量基本不能提高
    • 低位交叉编址：低位表示体号，高位表示体内地址，此时可以流水线并行存取，提高存储器带宽。设模块字长等于总线宽度，模块存取周期是T，总线传送周期是r（每隔至少r启动流水线下一模块，一般取r），模块数（交叉存取度）不小于T/r，使得每个模块的启动间隔大于T。因此，连续存取m个字需要时间T+(m-1)r，小于顺序存取时间mT，带宽明显提高。

外部存储器

磁盘存储器

• 利用磁记录技术在涂有磁记录介质的旋转圆盘上进行数据存储
• 一般用于辅助存储器
• 由磁盘、磁盘驱动器、磁盘控制器构成
• 磁盘一般装在磁盘驱动器上，其数据的定位类似于柱坐标（盘面层号对应高度、扇区号对应角度、磁道号对应半径）
• 磁盘驱动器即磁盘机，是驱动磁盘转动并在盘面上通过磁头进行读写的装置
• 磁盘控制器即磁盘驱动器适配器，属于磁盘面向计算机的接口设备，接受计算机命令，向磁盘驱动器发出控制信号
• 存储容量大、数据传输率高、可长期保存
• 计组笔记第7章输入输出系统、操作系统的输入输出管理的外存管理部分也有介绍

固态硬盘SSD

• 参考前面ROM存储器的固态硬盘内容

高速缓冲存储器Cache

程序访问局部性原理

• 时间局部性：最近要用的信息可能是现在正在用的信息
• 空间局部性：最近要用的信息在存储空间里和正在用的信息是相邻的
• 利用程序局部性原理，把程序正在使用的部分存放的高速、容量较小的Cache中，使得访存操作通过Cache进行，提高程序速度

Cache基本原理

• 通常由SRAM构成
• 主存和Cache划分为相等的块，Cache块又叫Cache行，每块有若干字节，块长度被称为块长或Cache行长
• Cache块数远小于主存块数，仅保存主存最活跃的部分块
• CPU发出读请求时
  • 如果命中Cache，则地址转换为Cache地址，直接对Cache读
  • 如果没命中Cache，则需要访问主存，并把该字所在块从主存调入Cache
    • 如果Cache未满，则直接调入
    • 如果Cache已满，根据替换算法，进行Cache中块的替换
  • CPU和Cache交换字，主存和Cache交换块
• CPU发出写请求时
  • 如果命中Cache，则要考虑Cache数据和内存数据的一致性问题，采取一定的写策略，如
    • 全写法
    • 写回法
  • 如果未命中Cache，则根据块是否调入Cache，可以分为
    • 写分配法
    • 非写分配法
• Cache命中率指的是CPU欲访问信息在Cache中的比率，越接近1越好
• 假设是命中情况的Cache访问时间，是未命中情况的访问时间（有可能比访问内存时间长，因为要先检查是否命中Cache），是命中率，则是Cache-内存系统平均访问时间
• Cache的结构为
  • 存储主存信息的数据块
  • 有效位：表示内容是否有用
  • 标记位：标记该Cache行对应主存哪个块，位数和地址映射方式有关
  • 块修改标记：提供写策略使用
  • 替换标记：提供替换策略使用

Cache和主存间映射方式

• 映射指的是从主存地址映射到Cache地址
• Cache中的每个块都标记了其在内存中对应的块位置（块号），并有一个块有效位
• 主要方法有
  • 直接映射
    • 主存每个块映射到Cache唯一位置。如果冲突直接替换，不需要替换算法
    • 实现简单但不灵活。
    • 主存块号的低c位是Cache行号，即，高t位存入对应Cache行的标记中
    • 主存地址的结构是：主存区号（作为Cache标记）、主存区内块号（等于Cache行号）、块内地址，前两者合并就是主存块号
    • 访存先根据Cache行号对比Cache行的标记和主存地址的高t位是否一致，一致且有效位是1则命中，根据块内地址存取Cache行信息；否则不命中，先从主存读该地址对应的块到Cache中，并设置有效位为1，并标记高t位，然后将地址对应的数据送到CPU
  • 全相联映射
    • 主存块可以映射到Cache任何一位置，CPU访存需要和所有Cache行标记对比
    • 灵活、冲突率低、空间利用率高、命中率高，但是标记比较速度慢，一般要用高成本的相联存储器（通常按内容寻址，也可以按地址寻址）进行映射
    • 主存的地址结构是：主存块号（作为Cache标记）、块内地址
  • 组相联映射
    • 把Cache空间分组，组间直接映射，组内全相联，访存需要和对应组的所有Cache行标记对比
    • 主存的地址结构是：主存区号、组内块号、组号、块内地址。前两者作为标记存入Cache；前三者就是主存块号
    • 注意主存地址的组号是主存块号的低位，位数由组数来确定。这意味着主存中连续的块，在Cache中对应不同的分组
    • n路组相联，表示每个组有n个块；n为1（即组数为Cache块数）则变为直接映射；n为Cache块数（即组数为1）则变为全相联
    • 访存先根据组号找到Cache组，再对比组内每个Cache块的标记。然后相等且有效位为1则命中，否则不命中。

Cache中主存块替换算法

• 对应全相联和组相联，当需要把主存块调入已满的Cache时，需要进行替换
• 常见的有
  • 随机算法RAND
    • 随即确定替换块，实现简单
    • 未考虑程序局部性原理，命中率可能低
  • 先进先出算法FIFO
    • 选最早进入的块替换，实现简单
    • 未考虑程序局部性原理，命中率可能低
  • 近期最少用算法LRU
    • 选最久没使用的块替换，考虑局部性原理，命中率比FIFO高
    • 设置一个计数器，最近访问的Cache块（可能是新调入的，或命中原本Cache的）的计数器置0，Cache中已有的其他块计数器加1
    • 计数器的位数等于组内块数对应的位数，即计数器的值小于组内块数，当计数器的值自增达到上限后，不再自增
    • 如果Cache已满需要替换，则移出计数器值最大（等于组内块数减1）的块
    • 当集中访问的、映射到同一组的存储块数超过了组内块数，很可能出现命中率很低的情况，称为抖动现象
  • 最不经常使用LFU算法
    • 选近期访问次数最少的块替换
    • 每行设置一个计数器，新建的块从0开始计数
    • 每命中一次计数器加1，替换时把计数器最小的块移出
    • 和LRU类似思想但又有不同

Cache写策略

• 写策略主要处理Cache和主存数据的一致性问题
• 当Cache写命中时
  • 全写法（写直通法、写直达法、write through）
    • 数据同时写入Cache和主存
    • 好处是实现简单，替换块时不需要写回，随时保证主存数据准确
    • 坏处是增加访存次数，降低Cache效率
    • 可以在Cache和主存间加一个写缓冲，数据同时写入Cache和写缓冲器，一定程度解决速度不匹配问题，但也存在缓冲器溢出问题
  • 写回法（write back）
    • 只修改Cache
    • 当块被替换掉时再写回主存
    • Cache行设置脏位，标记该块是否改过
    • 减少访存次数，但有数据不一致的风险
• 当Cache未命中时
  • 写分配法（write-allocate）
    • 加载主存的块到Cache中，然后更新这个Cache块
    • 和写回法配合使用，缺点是每次不命中都需要读取主存的块
  • 非写分配法（not-write-allocate）
    • 只更新主存，不调块到Cache
    • 和全写法配合使用，缺点是未考虑程序空间局部性
  • 现代计算机往往采用多级Cache（通常3级）
    • 按离CPU从近到远分为L1 Cache、L2 Cache、L3 Cache等，速度递减，容量递增
    • 比如两级Cache系统中，L1 Cache和L2 Cache采用全写法，因为访问L2 Cache速度比访问主存快，没有缓冲器溢出问题；L2 Cache和主存采用写回法，减少访存的次数。

虚拟存储器

虚拟存储器的基本概念

• 虚拟存储器由主存和辅存共同构成，具有前者的速度和后者的空间
• 虚地址
  • 又叫逻辑地址、程序地址，是编程允许涉及的地址
  • 对应的存储空间为虚拟空间（程序空间）
  • 虚地址=虚存页号+页内字地址
• 实地址
  • 又叫物理地址，是实际的主存单元地址
  • 对应的存储空间为实地址空间（主存地址空间）
  • 实地址=主存页号+页内字地址
• 辅存地址
  • 辅存的单元地址
  • 对应的存储空间为辅存空间
  • 辅存地址=磁盘号+盘面号+磁道号+扇区号
• CPU使用虚地址时，先由辅助软硬件找到虚地址和实地址的关系，判断该地址对应存储单元是否装入主存
  • 若在主存，则通过地址变换，CPU直接访问主存对应单元
  • 若不在主存，则把该字的一个页或一个段调入主存后再由CPU访问；若主存已满则需要使用替换算法。

页式虚拟存储器

• 基本原理
  • 页式存储器以页为基本单位，虚拟空间和主存空间划分为同样大小的页，分别叫虚页和实页（也可以叫页框、页帧、块）。外存中也按同样大小划分，叫块
  • 虚拟地址分为虚页号和页内地址，由页表转换为物理地址
• 页表
  • 随着进程的建立，对应进程页表被建立
  • 长期保存在主存中
    • 进程切换运行时，页表被调入主存
    • 页表首地址和长度（用于越界检查）保存在进程控制块中，在进程执行时，存入页表基址寄存器PTR
  • 每个页表项包含
    • 有效位（装入位、状态位）：对应页是否在主存
    • 脏位（修改位）：页面是否被修改过，一般结合回写策略，在页面从主存中被替换时写回磁盘
    • 引用位（访问字段）：配合替换策略进行设置，比如帮助实现FIFO或LRU策略
    • 物理页号或磁盘地址
• 虚拟地址转换到物理地址步骤
  • 查页表前先进行越界检查
  • 然后通过虚页号（虚拟地址高位，作为页表的索引）和页表首地址找到页表项
  • 如果有效则取出物理页号，和虚拟地址低位页内地址拼接，成为物理地址
  • 如果无效则缺页，需要操作系统先进行缺页处理
• 优点是页长固定，页表简单，调入方便；缺点是程序不一定是页整数倍，最后一页可能有空间浪费，同时页没有逻辑含义，不方便处理、保护、共享
• 快表TLB
  • 专门存放主存中页表的部分表项的缓冲表（类似于Cache）
  • 通常是全相联或组相联
  • TLB表项包括：页表表项内容、TLB标记
  • TLB标记表示该TLB表项来自主存页表的哪一个表项
    • 全相联方式，TLB标记就是虚页号
    • 组相联方式，TLB标记是虚页号的高位，虚页号的低位是TLB的组号
  • 如果查表时标记相等且有效位为1则命中，直接用TLB进行地址转换
  • 如果不命中，则TLB缺失，需要访问主存查页表
    • 如果TLB未满，则把主存页表中相应表项调入TLB页表
    • 如果TLB已满，则需要替换策略
• 多级页表
  • 考虑页表需要在内存中分配连续空间，页表较大时应当采用多级索引的方式
  • 比如IA-32（因特尔32位架构）中采取二级索引，虚页号进一步分成页目录索引、页表索引两个部分。先用页目录物理首地址（存放在用户不可见的控制寄存器CR3中）和页目录索引确定页表物理首地址，再结合页表索引确定物理页号
• 具有TLB和Cache的多级存储系统
  • 首先进行虚拟地址到物理地址的转换，（涉及快表TLB、多级页表、缺页处理）
  • 然后根据物理地址，在Cache-主存系统中存取相应的数据
  • 可能发生的缺失
    • TLB缺失：硬件或软件（操作系统）处理，需要访问主存
    • 缺页：软件（操作系统)处理，需要访问辅存（磁盘）
    • Cache缺失：硬件处理，需要访问内存

段式虚拟存储器

• 主存按程序的逻辑分段，以段为主存和辅存的调度单位，各段长不一定
• 虚拟地址分为段号和段内地址（由用户显式提供，实际设计一般是编译器实现），物理地址分为物理段号和段内地址
• 页式虚拟地址是一维的（可以分解为页号和页内地址），段式虚拟地址是二维的（段号和段内地址必须分别给出），是因为页大小固定，段大小不固定
• 段表
  • 指出各段在主存中的首地址
  • 包括段号、段长、段起始地址（高位相当于物理段号）、有效位（装入位）、段访问方式和标记等
  • 段表的首地址和长度（用于越界检查）存放在段表寄存器
• 虚拟地址转换到物理地址步骤
  • 查段表前先进行越界检查
  • 再通过段表基地址和段号找到对应段表项
  • 如果有效且段内偏移量不越界，则把段表项的段起始地址 + 段内地址（偏移量），得到物理地址
• 优点是段的分界和程序分界对应，易于编译、管理、修改、保护、共享；缺点是段长度可变，分配空间不便，主存中容易产生段内碎片的浪费

段页式虚拟存储器

设计思想

• 程序按逻辑分段，段内划分为固定大小的页，主存空间也划分为大小相等的页
• 主存和辅存以页为调度单位
• 每个程序对应一个段表，每段对应一个页表。
• 段的长度是页长整数倍，段的起点是页的起点
• 虚地址分为段号、段内页号、页内地址（二维的，段号和段内地址分别给出）
• 地址转换
  • 根据段表寄存器的段表长检查是否越界
  • 根据段号和段表寄存器中的段起始地址找到段表项，取出该段的页表首地址和页表长度
  • 根据页表长度和段内页号判断是否越界
  • 根据页表首地址和段内页号找到对应页表项
  • 从页表项中取出实页号和页内地址拼接为物理地址
• 优点是兼备段式和页式存储器的优点，可以按段共享和保护、按页进行存储调度
• 缺点是需要2次查表，开销较大

IA-32设计实例

上一节是教科书中的经典段页式虚拟存储器的设计思路，下面给出英特尔32位架构（IA-32）/linux中的虚拟存储设计实例

• 相关概念
  • 控制寄存器CR0中
    • PE=1，进入保护模式
    • PG=1，启动分页
  • 段寄存器SR
    • 段包括：数据段DS，代码段CS，栈堆段SS、附加段ES、FS、GS
    • 实模式是在32位机器推出后，对16位机器模式的一种说法，16位段寄存器保存的是段起始地址的高位，需要左移4位后加上段内偏移量，算出20位的物理地址。这种模式目前很少使用，只在开机的时候短暂的处于实模式。
    • 保护模式把寻址空间从20位拓展到32位，段寄存器拓展为96位，但只有16位指令可见。这16位就是下面介绍的段选择符。
    • 段寄存器的作用是直接（实模式）或间接（保护模式）的确定一个段的基地址（起始线性地址）
  • 段描述符：共64位8字节，存放一个段的有关信息，比如起始线性地址（如果不分页，则该线性地址就是物理地址）
  • 段选择符：共16位，包括13位段描述符表索引INDEX、1位判断是否为局部描述符表的标记TI、2位的特权级别RPL
  • 全局描述符表GDT
    • 一个处理器一个表，各个表项是各个段的段描述符，存放到内存里。
    • 通常会有GDT描述符Cache来加速访问。
  • 局部描述符表LDT
    • 一个任务一个表，存在内存里。
    • LDT本身是一个段，其段描述符就是GDT的一个项。
  • 全局描述符表寄存器GDTR：存放全局描述符表的起始线性地址
  • 局部描述符表寄存器LDTR：存放局部描述符表的段选择符，在进程切换时由OS进行更新
• 逻辑地址的计算
  • CPU通过指令计算出操作数的有效地址EA（EA的计算参考下一章笔记的寻址方式部分）
  • 有效地址作为32位段内偏移量，对应的段寄存器存放的是16位段选择符，共48位称为逻辑地址
• 线性地址的计算（分段机制）
  • 当操作数的段寄存器（16位段选择符）的TI=0，使用全局描述符表
    • GDTR（存的是GDT的线性首地址）和 INDEX（16位段选择符的高13位）定位一个段描述符的线性地址（若开启了分页需要进一步转成物理地址）
    • 从段描述符中取出该段在线性存储空间中的首地址
    • 该首地址加上32位段内偏移量得到线性地址
  • 当操作数的段寄存器（16位段选择符）的TI=1，使用局部描述符表
    • GDTR（存的是GDT的线性首地址）和 LDTR（16位段选择符）的高13位定位LDT的段描述符的线性位置（如果开启了分页，需要转换到物理地址）
    • 从LDT段描述符中取出LDT的线性起始地址，和操作数的段寄存器（16位段选择符）的高13位定位操作数的段描述符的线性地址（如果开启了分页，需要转换到物理地址）
    • 从段描述符中取出操作数的线性起始地址，和操作数的段内偏移量（即有效地址EA）相加，得到操作数的线性地址
• 物理地址的计算（分页机制）
  • 线性地址分成10位页目录索引、10位页表索引、12位页内地址
  • 页目录基址寄存器CR3（存放页目录内存首地址），结合页目录索引，定位页目录项（每项32位4字节，共1024项，刚好4KB，即页目录恰好占一页存储空间）
  • 在页目录项中找到页表的物理首地址，结合页表索引，定位页表项（每项32位4字节，共1024项，刚好4KB，即页表恰好占一页存储空间）
  • 在页表项中取出对应页的物理页号，结合页内地址，得到物理地址
• 32位linux采用“扁平模式”
  • 线性地址的段首地址都设置为0，等于逻辑地址就是线性地址，所有数据都看作在一个段中。
  • 这样做是因为不想使用16位系统中遗留下来的分段机制，但又保持了兼容性

虚拟存储器和Cache比较

• 相同之处
  • 都为了提高系统性能、具有容量、速度、价格的梯度
  • 数据都划分为小的信息块，作为传递单位，虚存系统的信息块更大
  • 都涉及地址的映射、替换算法、更新策略
  • 都依据程序局部性原理来应用快速缓存的思想，把活跃的数据保存在高速的部件中
• 不同之处
  • Cache主要解决CPU和主存存取速度不匹配问题，虚拟存储器是解决主存容量问题
  • Cache由硬件实现，对所有程序员透明；虚拟存储器由OS和硬件实现，对系统程序员不透明，对应用程序员透明
  • 因为CPU的速度约是Cache 10倍，主存速度约是硬盘100倍，所以虚拟存储器不命中时对性能影响更大
  • CPU和Cache都和主存有直接访问的通路，辅存和CPU没有直接通路