1.存储器层次结构

• 计算机对存储器的基本要求：速度快，容量大，价格低，三者相互矛盾，速度越快，位价格越高，存储器容量越大，速度就不可能很快
• 多层次存储系统的目的：为了解决容量，速度和价格三者之间的矛盾，通常把各种不同存储容量，不同存取速度和位价格的存储器，按一定的结构组织起来，形成一个多层次的存储系统
• 信息在层次化的存储系统中进行存储时需满足两个基本原则
  • 包含性原则：指在上层存储器中所存放的内容一定是其下层存储器内容的一部分，即上层存储器存储的信息是其下层存储器部分内容的副本
  • 一致性原则：最上层存储器中的内容被修改后，也必须修改该信息保存在其他下层存储器的所有副本，以保持信息的一致性，即存放在不同存储器中的同一数据，在不同存储器中要保持相同的值
• 命中率H_i：H_i表示在存储器中找到被访问信息的概率
• 程序运行的局部性原理
  • 时间局部性：在一小段时间内，最近被CPU访问过的程序和数据很可能再次被访问
  • 空间局部性：一段时间内被CPU访问的指令和数据往往集中在一小片存储区域内
• 存储器层次结构中最重要的两个层次：
  • 高速缓存存储器 Cache：目的是为了提高存储器的访问速度，使得CPU访存速度接近cache，容量接近主存，由硬件实现，对所有程序员透明
  • 虚拟存储器：目的是提高存储器的容量，使得用户在使用内存时，可面对接近辅存的容量，访问速度接近主存，软硬件结合实现
    
    现代存储系统的层次结构
• 存储器层次结构带来的问题：
  • 地址映射：解决上层副本所在单元地址与下层地址对应关系的问题
  • 数据一致性问题：存放在不同存储器中的同一数据，在不同存储器中要保持相同的值，如何保证不同层次存储器中存放数据的一致性
  • 地址变换：CPU访存提供的主存地址如何转换为不同层次存储器中的地址
  • 替换策略: 当某层存储器已经存满数据，又有新数据要装入时，应将哪些数据替换出去

2.相联存储器

相联存储器就是选择存储单元中的某一个存储项的内容作为地址来对存储器进行寻址。这个用来定位存储单元的字段称为关键字，简称键(key)。故相联存储器中每个存储单元中存储的信息都由关键字和数据两部分组成

• 相联存储器按存储单元中存放的全部或部分内容进行访问的存储器，也称按内容访问存储器(AM Associative Memory)
• 主要用于需快速检索的场合
• 读操作按内容访问过程：CPU给出的关键字(存储单元的全部或部分内容)和存储器中所有单元中相应信息(counterpart)进行比较，定位到与关键字匹配的存储单元后，将此单元所有信息读出
• AM主要组成

相联存储器

• 存储体
• 检索寄存器：存放用于查询的检索字
• 屏蔽寄存器：存放屏蔽码，来屏蔽检索字中非关键字字段位，即屏蔽码中与关键字对应位置1，其余位置0，检索字和屏蔽码与操作后得到关键字值
• 匹配寄存器：关键字通过比较电路与所有存储单元对应位进行比较，若相符，则该存储单元在匹配寄存器相应位置1，匹配寄存器位数 = 相联存储器字数(存储单元个数)，所有存储单元内容都比较完后，匹配寄存器中所有值为1的位对应的存储单元，就是与检索字匹配成功的存储单元
• 数据寄存器
• 比较电路和译码电路

3.高速缓冲存储器 Cache

特点：

• 速度快，容量小，位价格高
• 可加快程序执行速度，解决CPU和主存速度不匹配
• 命中率越高，CPU访存速度越接近于Cache的存取速度
• 与主存以块为单位进行数据交换，块由若干字组成，通常是定长的
• cache接收到地址后，首先进行地址变换操作，即将主存地址转换成cache地址
  
  CPU访存处理流程

• cache读过程

cache读

• 地址变换机制可以判断出本次要访问的存储单元内容是否已经装入cache中，即是否命中
• cache命中率越高，CPU平均访存时间越短，但当cache容量大到一定程度时，命中率不会再随着容量的增加而明显地增大
• Cache性能指标
  • 命中率：H = N₁ / N，CPU访存N次，cache命中N₁次
  • 平均访存时间T_a：指CPU单次访存所需要的平均时间，T_c为cache存取时间，T_m为主存存取时间
    T_a = HT_c + (1-H)×T_m
• 加速比S_p：主存存取时间与平均访存时间比值
  S_p = T_m / T_a
• 访问效率e：cache存取时间与平均访存时间的比值
  e = T_c / T_a
• 地址映射与地址变换
  • 地址映射机制：就是解决如何将主存的地址空间映射到cache的地址空间，即把主存中的内容按照某种规则装入到cache中，并建立主存地址与cache地址的映射关系
  • 地址变换：执行程序时，应首先将主存地址变换成cache地址，即执行地址变换
  • 二者密切联系，采用什么样的地址映射方法，就必然采用与之相对应的地址变换方法
  • 主存地址和cache地址可分为两部分：块地址，块内地址
  • 主存和cache之间以块为单位进行数据的调入，调出
  • cache中每一块都增加了标记字段(Tag)，用于说明该块是主存中哪一块的副本
  • CPU访存时需将所访问的主存块号与cache中的标记进行比较，才能判断出该地址对应的存储单元是否在cache中命中
    
    
    
  • 全相联映射及其地址变换
    • 全相联地址映射：指主存中的每一块都可以映射到cache中的任意块
    • 特点：最灵活，cache利用率高，成本高，缺点：标记比较的速度比较慢
    • 主存地址高m位表示主存块地址，低b位表示块内地址
    • cache地址同样划分为两部分：高c位表示cache块地址，低b位表示块内地址
    • 目录表记录主存块与cache块之间映射关系，目录表存放于相联存储器中
    • 目录表每个存储字包括三部分：主存块号，cache块号，有效位
      • 有效位：表示目录表中主存块号和cache块号建立的映射关系是否有效
    • 目录表共有2^c个存储字，即cache中每个块对应目录表中一个存储字
    • 当一个主存块调入cache中时，会同时将主存块号和cache块号存入目录表中，并将有效位置1
    • 当CPU发来一个访存地址，地址变换就是根据主存地址中的块号查询目录表的过程。若在目录表找到，且有效位为1，则表示命中，否则未命中

全相联映射

• 可以认为每一个目录表项记录了某个cache块是从主存中哪一块调入的，这样便可以根据主存访存地址的块号来相联比较目录表中的主存块号，若找到一条表项，且有效位为1，说明该主存块已经被调入了cache，此时目录表中的cache块号对应的cache块内容实质上就是主存地址的主存块号存放的内容，于是便可以直接按照目录表中的cache块号和主存地址的块内地址访问cache
  全相联映射的地址变换
  
  全相联映射的地址变换
• 直接映射及其地址变换
  • 直接映射：指主存中的块只能映射到cache中某个固定的块中，
  • 主存块和cache块对应关系公式：
    j = i mod 2^c
    • j 为数据在cache中的块号，i 为数据在主存中的块号，即主存块号模运算cache总的块个数
  • 按照cache字块个数将主存划分为若干区，即主存每个区所包含的子块数等于cache所包含的字块数，且每个区内每个字块和cache的字块按模关系一一对应
  • 使用区表保存主存块与cache块映射关系
  • 区表组成：主存区号，有效位，区表有2^c个存储字，常存放在高速缓冲存储器中，按地址访问
  • 优点：实现简单，地址变换速度快，缺点：不够灵活，cache存储空间得不到充分利用
    

直接映射

• 区表的表项个数和Cache中块的个数相同，于是可以建立二者之间的一一对应关系，即第 i 个区表表项，就是第 i 个cache块和主存每个区内对应第 i 个字块的映射关系，这样便可以按cache块号作为地址访问区表，因为每个主存区的字块个数和cache块个数相同，即每个主存区内都有一个字块可以映射到某个cache块，于是可以看是否有哪个区对应的这一字块被调入了cache，若在区表中找到对应表项，此时只能说明有某个区的对应字块已经调入了cache，但是仍然不能确定是否是CPU访存需要的数据，还需进行区号比较，若区号也相同，则可以确定CPU要访问的数据已经在Cache中了
  直接映射地址变换过程
  
  直接映射地址变换过程
• 组相联映射及其地址变换
  • 主存和cache的块都先进行分组，主存和cache每组包含的块数相同
  • 组间采用直接相联映射，组内采用全相联映射
  • 如图cache被分成2^u组，每组2^v块，主存共有2^s个区，每个区有2^u组
    
    组相联映射方式
    
    组相联映射的地址变换
  • 使用块表记录从主存地址到cache地址的映射关系
  • 块表容量大小：2^u+v个存储字，即cache的总字块容量大小
  • 每个块表存储字主要包含：区号，组号，组内块号，有效位等字段
  • 块表采用混合工作方式，块内按照相联方式访问，块间进行按地址访问
  • n路组相联指每组n块
  • 组相联地址变换过程
    • 由于组间是直接映射方式，所以cache中的每个组，主存中每个区内都对应有唯一一个组可以映射到对应位置，这里可以认为块表有 2^u 行，即cache中每一组对应块表中的一行，于是可以先直接按照主存地址的组号U字段作为地址访问块表，看是否主存的某个区对应组调入了cache，若按组号U字段作为地址访问块表找到了某一块表项，此时只能说明有某个区的对应组调入了cache，不能确定是否是CPU访存对应的区和对应的组内块号(因为组内是全相联，组任意块都可以映射到对应Cache组的任意Cache块)，于是需要对区号和组内块号进行相联比较，若相符，则可以确定CPU要访问的存储单元已经调入了cache
      
      组相联地址变换过程

组相联映射

• 替换算法
  • 随机算法(RAND)：不考虑cache中各块使用情况，随机选择一个块作为替换对象。特点：实现简单，速度快，缺点：没有利用程序局部性特点，随意替换出去的数据很有可能马上又要使用，降低了命中率和cache工作效率
  • FIFO先进先出算法：最先调入cache的主存块被替换出去，不需记录各块使用情况，故硬件实现容易，系统开销小
  • LRU (Least Recently Used) 近期最少使用算法：以cache中每块的历史使用情况为依据，在需要替换时将近期最少使用的块替换出去，较好反映了程序的局部性原则，对循环程序有较高命中率，需记录cache中各字块的使用情况，故实现复杂，开销大，需为每个字块设置计数器
  • LFR (Least Frequently Used) 最不经常使用算法：将访问次数最少的块替换出去，需为每个字块设置计数器，记录每个cache块的访问次数，当需要替换时，将计数值最小的块替换出去，同时将所有块的计数值清零，缺点：不能反映最近的访问情况，只能反映两次替换时间间隔内的使用情况
• cache写操作及一致性
  • 造成cache与主存内容不一致的原因主要有如下两种：
    • CPU对cache执行写操作，但没有立即写主存
    • I/O设备写主存，但没有同时写cache
  • 常见的写策略如下：
    • 写直达法 (Write Through)：CPU执行写操作时，将数据同时写入主存和cache，优点：实现简单，cache和主存内容始终保持一致，缺点：频繁访存降低平均访存速度
    • 写回法 (Write Back)：CPU执行写操作时，数据只写入cache，不同时写入主存，只有当cache中某个字块需要替换出去时，才把修改过的cache块写回主存，，优点：减少访存次数，有利于提高平均访存速度，缺点：增加了cache复杂性，存在主存与cache内容不一致问题，影响系统可靠性，写回法可分为如下两种
      • 简单写回法：无论字块是否被更新，都进行写回操作，
      • 采用标志位写回法：只在块被更新时，才进行写回操作
  • CPU执行写操作时，若在cache中未命中，存在写时是否取问题，解决方法如下两种：
    • 不按写分配法：cache写不命中时，只执行对主存的写入操作
    • 按写分配法：cache写命中时，首先执行写主存操作，然后将该主存块从主存调入cache
      写回法一般采用按写分配法，写直达法采用不按写分配法
• 多级cache
  • 数据cache和指令cache，分开的好处

4.硬磁盘存储器

• 由一组盘片组成，称为磁盘的盘片组，盘片组固定在一个主轴上，盘面中心是空心的，不能记录信息
• 每个盘面的有效记录区被划分为数目相等，由内向外排列的同心圆，这些同心圆间距相等，称为磁道
• 启停区(着陆区)：磁头靠近主轴表面，即线速度最小的地方，这个区域不存放任何数据，称为启停区(着陆区)
• 数据区：启停区之外就是数据区，通常从最外侧磁道开始编号，起始磁道号为0
• 不同盘面上具有相同磁道号的磁道形成一个柱面
• 柱面数 = 磁道数
• 每个盘面对应一个磁头，磁头从上到下从0开始编号
• 对文件进行写入操作通常按柱面进行，即磁头读/写数据时首先在同一柱面内从0磁头开始进行操作，依次向下在同一柱面的不同盘面即磁头上进行操作，只有同一柱面所有磁头全部读/写完毕后磁头才移动到下一柱面，这样设计的目的：为了提高读写效率，因为选取不同磁头是通过电子切换完成，而选取不同的柱面必须进行机械动作来完成磁头的移动
• 一个磁道通常被分成若干圆弧线，称为扇区，一个磁道上，所有扇区是等长度的
• 硬盘以扇区为单位进行存取，因此硬盘的可寻址最小单位为扇区
• 定长记录格式：每个扇区中存放的数据块大小固定，特点：简单，空间利用率不高
• 不定长记录格式：扇区中存放的数据块大小可变，外圈磁道可以比内圈磁道存储更多的字节，特点：灵活性好，空间利用率高

• 硬盘存储信息定位常用地址格式：

  
  
  • 柱面号即磁道号，盘面号也可以用磁头号
• 磁盘进行读写时，大致分为两个步骤
  • 定位柱面(磁道)：磁盘驱动器进行寻道操作，即确定需操作的柱面，定位驱动系统带动磁头做径向运动
  • 定位扇区：主轴系统带动磁盘组进行旋转，将需读写的扇区移动到磁头上/下方
• 硬盘技术参数
  • 容量
    • 道密度：盘面径向上单位长度内磁道数量
      一个盘片的磁道总数 = 道密度 * 盘片有效半径
    • 位密度：盘面磁道上单位长度所能记录的二进制位数
      一个磁道的容量 = 位密度 * 磁道周长
    • 非格式化容量：
      硬盘容量 = 硬盘个数 * 磁盘记录面数 * 磁道数 * 磁道容量
      =硬盘个数 * 磁盘记录面数 * 道密度 * 盘片有效半径 * 位密度 * 磁道周长
    • 格式化磁道容量：
      硬盘容量 = 硬盘个数 * 磁盘记录面数 * 磁道数 * 每道扇区数 * 扇区容量
  • 平均寻址时间：磁头从起始位置到达目标磁道位置，且定位到目标磁道上目标扇区所需的平均时间
    • 平均寻址时间 = 平均寻道时间 + 平均等待时间
    • 平均寻道时间：磁头到达目标数据所在磁道平均时间
    • 平均等待时间：到达所访问扇区的平均时间，一般取盘片旋转一周时间的一半
      • 平均等待时间 = (1 / 转速) / 2
      • 转速：单位时间硬盘盘片旋转圈数
  • 数据传输率：读写数据时，单位时间内的数据传输量，单位字节/秒(B/s)

5.虚拟存储器

虚拟存储器：就是将一部分硬磁盘空间作为主存来使用，使得计算机的存储系统容量上接近辅存，速度上接近主存，成本上接近辅存每位价格

• 程序员可使用比主存大得多的存储空间，按虚存空间编址
• 交换信息的基本单位：段，页，段页
• 虚拟存储器和Cache的区别对比

• 虚拟地址：程序员编程时使用的地址，即逻辑地址，对应存储空间称为虚拟地址空间
• 物理地址：即主存地址(实地址)，主存空间被称为物理地址空间
• 辅存地址：辅助存储器的地址
• 程序重定位：对程序进行虚拟地址到物理地址变换的过程
  • 静态重定位：程序装入主存时一次性完成地址变换，且程序执行过程中不再改变，因灵活性差很少使用
  • 动态重定位：即在目标程序执行过程中，CPU访存前，由硬件地址映射机构完成将要访问的指令或数据的虚拟地址向主存物理地址的变换，即地址变换时在程序执行期间随着每条指令读取和数据访问自动进行的，特点：需硬件支持，支持程序浮动，便于利用零散的内存空间，有利于实现信息共享和虚拟存储
• 虚拟存储器基本思想：程序执行时，按照程序执行顺序将程序的一部分调入主存，其他部分保留在辅存。当需要执行存放在辅存中的程序段时，CPU按照某种调度算法以页，段等为单位将其调入主存。硬件和软件(操作系统)共同自动实现对存储信息的调度和管理，基本步骤如下：
  • 对CPU发出的访存地址(虚拟地址)进行内部地址变换，判断该地址对应的存储单元是否在主存中
  • 若在主存，则使用物理地址访问主存
  • 否则执行外部地址变换，确定该地址对应存储单元在辅存的地址
  • 若主存有空闲块，则将该存储块内容从辅存调入主存，否则使用替换算法将该存储块替换到主存，然后CPU访问主存单元
• 虚拟存储器的地址映射及变换
  • 虚拟存储器的地址映射：把虚拟地址空间映射到主存地址空间
  • 虚拟存储器的地址变换：程序被装入主存后，实际运行时，把用户的虚拟地址变成主存的物理地址(内部地址变换)或磁盘存储器地址(外部地址变换)
  • 页式虚拟存储器
    • 用固定大小的页描述逻辑地址空间，同样大小的页描述物理内存空间，程序运行时以页为单位进行调入调出
    • 主存中的页称为物理页，实页，虚存中的页称为逻辑页，虚页
    • 物理地址和逻辑地址计算方法：
      物理(逻辑)地址 = 页大小 * 页面号 + 页内地址
    • 页表完成页管理和地址变换，页表位于主存，虚存中每个页面对应一个页表表项
    • 页表表项内容：虚存页面所在主存页面号(物理页号)，有效位(指示该逻辑页是否已调入主存)
    • 页表起始地址由页表基址寄存器给出，用逻辑页号作为页表偏移地址检索页表，且首先判断该页是否已经调入主存(有效位为1)，若已经调入主存，则进行内部地址变换获得物理地址并访问主存
    • 优点 ：主存利用率高，页表格式简单，地址映射及变换简单，地址变换块，调入操作简单，缺点：页的长度固定，不利于编程独立性，程序及数据的保护及调入调出困难
  • 页式虚拟存储器的地址变换
    • 因为页表的表项个数和虚存的页面个数相等，故可以认为页表中，从页表基地址开始顺序编址，每一个页表项对应一个虚存页面，故可以按照虚拟地址的逻辑页号作为地址访问页表，得到的页表项，肯定能找到一个页表项，此时重要的是需要看有效位是否为1，只有有效位为1才说明该虚页已经被调入了主存，且此时页表中该表项中存储的主存页面号，与CPU访存提供的页内地址拼接便形成实际的物理地址

页式虚拟存储器地址变换

• 快表：为了减少访存次数，通常将页表中最常用的部分保存在cache中，这部分页表称为快表，可极大提高地址变换的效率
• TLB变换后援缓冲器：缓存快表的高速存储部件，大多采用相联存储技术，按内容查找，利用了程序访问的局部性
• 慢表：保存在主存中的完整页表
• 使用TLB后的地址变换过程

使用快慢表的虚拟存储的地址变换

• 段式虚拟存储器
  • 基本思想：按照程序的逻辑结构划分段，主存以段为单位进行分配
  • 每个段的长度可以不同
  • 通过段表对每道程序管理，段表一般也是位于主存中
  • 每个程序段对应段表一个表项，段表表项主要内容：有效位，段起址(指明该段在实存的首地址)，段长度 ，这里区分段起始地址和段表起始地址。
  • 段表的起始地址由段表基址寄存器给出
  • 段式虚拟存储器的地址变换
    • 段表中的表项，按顺序存储程序按逻辑被划分的若干段，即每个程序段在段表有唯一一个表项存储映射关系，第一个表项存储第一段程序段，段表表项的段起址字段存放这个程序段在主存中的起始地址，当段表对应表项的有效位为1时，此时CPU访存地址的段内地址作为偏移量与段表中对应表项的段起址字段相加形成实际访存的物理地址

段式虚拟存储器的地址变换

• 段页式虚拟存储器
  • 主存物理空间等分为页
  • 程序先按逻辑结构分段，每段再分成与物理空间页同样小的页面
  • 程序以页为单位进行调入调出操作，但以段为单位进行编程，保护和共享
  • 通过一个段表和一组页表进行管理，即每个程序段都有若干页，这些页被存储在一个页表中，若干段就有一组页表。
  • 段表每个表项对应一个段，内容包括：该段的页表起始地址，页表长度
  • 优点：同时具备段式和页式虚存的优点，缺点：映射过程需多次查表，耗时大
  • 页表每个表项给出：该段各页在主存中的实页号，是否装入，已修改等状态信息
  • 段页式虚拟存储器的地址变换
    • 由于每个程序段按顺序与段表表项一一对应，故首先根据CPU访存提供的虚拟地址的段号字段按地址访问段表，找到对应段的段表表项信息，表项信息中的页表地址字段给出该程序段对应的页表的起始地址，而页表中每个虚页页面按顺序与页表表项一一对应，故页表起始地址再与CPU访存提供的虚拟地址的页号字段相加作为地址访问该程序段对应的页表的页表项，确定了该虚页对应的物理页号，这个物理页号再于CPU访存地址的页内地址相加便形成最终的访存物理地址

  段页式虚拟存储器的地址变换