第08章 高速缓冲存储器和虚拟存储器

需要计算字块的使用次数，开销大，但平均命中率比 FIFO要高。
最优淘汰算法（OPT）
系统预测作业今后要访问的页面，淘汰页是将来不被访 问的页面或者在最长时间后才被访问的页面。它保证有最少 的缺页率，但它实现困难，只能通过理论分析用来衡量其它 算法的优劣
改写主存储器的策略
若 CPU 改写了 Cache 一单元内容（写命中）后且尚未 改变主存相应单元内容，则出现数据不一致性。有两种 解决办法： 直接改写主存单元内容（Write Through写 直达）：
多路组相联映像方式特点： 折衷方案。组间为全相联，组内为直接映像。 集中了两个方式的优点。成本也不太高。 内存与CACHE关系，有限度的多对多。
最常用的CACHE映像方式
两路组相联映像方式
有 效 位 标志
比较
CACHE 比较
主存地址
主存字 块标记
译码
数 据
主 存 储 器
数据
译码
组内地址
cache的容量与命中率的关系
100% 80% 60% 40% 20% 0% 1 8 16 32 64 128 256 512
Hit Rate
Cache Size in KB
cache line size与缺失率的关系
多级的cache结构与命中率的关系
为增加计算机系统中的cache容量，通常可以在已有的 cache存储器系统之外，再增加一个容量更大的cache。 此时原有cache为第一级cache（例如奔腾机微处理机芯 片内的cache），新增加的cache则成为第二级的cache。 第二级cache的容量比第一级cache的容量要大得多，在 第一级cache中保存的信息也一定保存在第二级cache中， 但保存有比第一级cache中更多的信息。当CPU访问第一 级cache出现缺失情况时，就去访问第二级cache。 若第一级、第二级cache的命中率为90%，则它们合起 来后的命中率为１-（１-90％）×（１-90％）=99％， 而不会是81％。
译码 CPU
主存字块 标记
组内地址
块内 地址
多路组相联硬件实现举例
三种映像方式比较
全相联映射

主存中的一块可以映射到Cache中任何一个位置，灵活、命中率高， 但是使用价格比较高 主存中的一块只能映射到Cache中唯一的一个位置，命中率低，使 用价格低 定位时，不需要判断，只需替换 主存中的一块可以选择映射到Cache中多个位置，适当的价格和命 中率。 从主存中取出新块 为了腾出Cache空间，需要替换出一个Cache块 不唯一，则需要判断应替出哪块
8. 1 高速缓冲存储器（Cache）
目的：就是在性能上使主存储器的平均读出时间尽 可能的接近与Cache的读出时间。要实现这个目的， 就是要将CPU将要读取的主存单元内容先预先读到 Cache中。 由于程序编制的局部性，即程序总是按顺序编写 和编址的，指令按地址顺序存放在存储器中;一条指 令执行后一般是执行紧接着的那条指令，只有遇到 转移指令时才会跳到另一个区域，但跳转之后又会 顺序执行;还有就是当执行一个循环程序时，会在一 块小的区域内重复循环执行若干指令;对于存储的数 据也是如此。按照一定的预读算法，可以实现很高 的Cache命中率。
如果CPU写内存的数据不在Cache中（写缺失）那么怎么 处理呢？
CACHE 接入系统的体系结构
侧接法：像入出设备似的连接到总线上，优点是结构 简单，成本低，缺点是不利于降低总线占用率。
MEMORY
Bus Master 1
CPU
总 线
CCACHE 接入系统的体系结构
使用成本太高
全相联映像方式
有 效 位 标志 数据
数 据 CACHE
比 较
主 存 储 器
主存字块标记
主存地址
译码
CPU
主存字块标记 块内地址
全相联硬件实现举例
主存地址
31 30 ……… 3 2 1 0
主存字块标记
30
块内地址
有效位 标记
0
数据
有效位 标记
1
数据
…… ……
有效位 标记
1023
数据
=
=
第8章
高速缓冲存储器和虚拟存储器
本章主要内容
高速缓冲存储器（Cache） 高速缓存的基本运行原理、高速缓存的3种映像 方式、高速缓存使用中的问题 虚拟存储器 虚拟存储器概述、段式存储管理、页式存储管理
程序的局部性原理
程序在一定时间段内通常只访问较小的地址空间
访问概率
地址空间
两种局部性：时间局部性和空间局部性
8. 1 高速缓冲存储器（Cache）
用途：设置在 CPU 和 主存储器之间，完成高速 与 CPU 交换信息，尽量避免 CPU不必要地多次 直接访问慢速的主存储器，从而提高计算机系统 的运行效率。 实现：这是一个存储容量很小，但读写速度更快 的，以 关联存储器方式 运行、用静态存储器芯 片实现的存储器系统。 要求：有足够高的命中率，既当 CPU需用主存中 的数据时，多数情况可以直接从CACHE中得到， 称二者之比为命中率。
利用率低，命中率低，效率较低
直接映像方式
CACHE
有 效 位
标志
数据
数 据
比 较
主存 字块 标记
译 码
cache 字块 地址
主 存 储 器
主存地址
译码 CPU
主存字块 标记
cache字块 地址
块内 地址
直接映像硬件实现举例
主存地址
主存字块标记
cache字块地址 块内地址
多路组相联映像方式
多路组相联映像方式：是对全相联映像和直接映想象的 一种折衷的处理方案。既不在主存和CACHE之间实现字 块的完全随意对应，也不在主存和CACHE之间实现字块 的多对一的硬性对应，而是实现一种有限度的随意对应。
8. 1 高速缓冲存储器（Cache）
当CPU要从主存中读取一个字，先把这个 字的地址传给Cache，检查这个字是否在 Cache中，如果在，就把这个字直接从 Cache送到CPU中，如果不在，则把这个地 址传给主存，从主存中读出这个字。同时，把 这个字附近地址单元的内容取到Cache中，以 满足下次访问的字能在Cache中。
8. 1 高速缓冲存储器（Cache）
CPU和主存之间的速度大约相差一个数 量级，为了弥补主存速度的不足，在CPU和 主存之间设置了一级容量不大，但速度很高 的高速缓冲存储器（Cache），简称高速缓 存或快存。CPU在某一小段时间内所要访问 的程序和数据被事先从主存中调入Cache中， 当CPU需要这些程序和数据时，就直接去 Cache中读取，这样将大大提高存取速度。 Cache和主存借助于辅助硬件构成一个整体。
虚拟存储器概述
主－辅存层次 --容量 辅助存储器是主存的补充，用来存放暂 时不用的程序和数据，当需要时，再调到主 存中去。主－辅存层次通过附加的硬件及存 储管理软件来控制，主－辅存形成一个整体， 称之为虚拟存储器。 虚存=主存+辅存
虚存 主存 辅存
虚拟存储器概述
虚拟存储器概述
虚拟空间可以比实际空间大得多: 80286，实存空间224=16MB，虚存空间1GB。 Pentium，实存空间232=4GB，虚存空间 64TB。 辅存只与主存交换信息，CPU不能直接访问 辅存。 从整体看，主－辅存层次的存取速度接近于 主存的存取速度，容量则接近于辅存的容量，而 每位平均价格也接近于廉价的辅存平均价格，从 而解决了大容量和低成本间的矛盾。
3. CACHE的3种映像方式
地址映像：把一主存单元的数据复制到CACHE中 时，还要把该主存单元的地址，经过某种函数关 系处理后写进CACHE的标志字段，这一过程被称 为CACHE的地址映像。 地址变换：在程序执行时，还要把主存地址变换 为访问CACHE的地址，这一过程被叫做CACHE 的地址变换。 CACHE存储器通常使用3种映像方式，它们是全 相联映像方式、直接映像方式、多路组相联映像 方式，3种映像方式有各自的优缺点。
直接映像


多路组相联映射

全相联映射和多路组相联映射的失效处理


CACHE使用中的几个问题
CACHE的重要技术指标：命中率 影响 CACHE 命中率的因素



CACHE 的容量，大一些好 CACHE 与主存储器每次交换信息的单位量(Cache Line Size)适中 CACHE 不同的组织方式，多路组相联更好 CACHE 的多级组织可提高命中率 CACHE 装满后的替换算法
Cache替换算法
随机替换（RAND）
随机找一个Cache块进行替换，比较盲目。
先进先出算法（FIFO）
将最早调入Cache的字块替换出去，采用循环电路容易 实现，开销小。
最不常使用淘汰算法(LFU)
即替换掉引用次数最少的块。需要计算字块的使用次数， 开销大，但平均命中率比FIFO要高。
最近最少使用算法（LRU）
1. Cache存储单元的组成部分

有效位
标志
数据
数据字段：保存从主存单元复制过来的数据 标志字段：保存相应主存单元的地址信息 有效位字段：标识数据字段和标志字段的是否有效
Cache单元的大小：cache line size（几个主存字，减少标志位位 数，较少Cache总容量） Cache与主存交换数据的单位： cache line size（充分利用空间 局部性） Cache单元与主存单元的对应关系，例如：
=
……
1024-1选择器
命中
数据
直接映像方式
直接映像方式：是指主存的一个字块只能映像到 CACHE的一个准确确定的字块中。 直接映像方式特点：


主存的字块只可以和固定的Cache字块对应，方式直接， 利用率低。内存与CACHE关系，多对一。 标志位较短，比较电路的成本低。如果主存空间有2m 块，Cache中字块有2c块，则标志位只要有m-c位。且 仅需要比较一次。