存储体系

郑振宁2024年4月12日大约 23 分钟

存储体系 *

华中科技大学-计算机系统结构

存储体系概念
1. 定义、分支、依据
2. 主要指标参数的计算
虚拟存储体系
1. 3 种虚拟管理方式的原理、地址映像规则、影响表机构、地址变换过程、各自优缺点
2. 段页式虚拟存储器中，由虚地址计算实地址；根据映像表内容计算主存实地址；判断段失效、页失效、保护失效
3. 页式虚拟存储器中，虚实地址字段的对应关系、地址映像规则；由虚地址查映像表计算实主存地址，或判断页失效
4. 用 FIFO、LRU、OPT 算法页面替换的过程模拟，计算命中率
5. 堆栈型替换算法定义、种类；给出程序运行时的虚页地址流用 LRU 替换算法进行堆栈模拟处理，求不同实页数的命中率
6. PFF 替换算法的原理；二道程序给出各自程序运行中得虚页地址流，合理分配给它们的实主存页数，使系统效率最高
7. 分析虚拟存储器得页面大小、分配给主存容量与主存命中率的变化趋势，给出综合评估和改进虚拟存储器性能得办法
Cache 存储器
三级存储体系的组织

真题

简答题·全

【虚拟存储器篇】

简述页式虚拟存储器页面失效和实页冲突发生的原因及所确定替换算法的依据 2104 0707

简述提出虚拟存储器的原因并根据存储映像算法的不同写出虚拟存储器主要的三种存储管理方式。2010

简述在采用页式虚拟存储器的系统中，页面失效频率(PFF)算法的思想。1304

简述提高模m值，影响主存实际频宽的因素及结果。1904 0604 x2

对模m交叉，若都是顺序取指，则效率可提高m倍；
转移指令的客观存在性会降低主存系统的效率；
模m越大，总线越长，传输速度越慢；
因此，提高模m能提高主存频宽，但二者不成线性关系。

【Cache 存储器篇】

简述Cache全相联映像的概念及其优缺点 1910

简述Cache存储器地址映像、地址变换的概念以及映像规则的选择要求 1610

简述更新主存内容的写回法和写直达法的基本原理 2204 1804 1710 x

应用题·全

提高C的等效访问速度（命中率H）**

已知 $t_c$ 是Cache的访问时间；$t_m$ 是主存周期；$t_a$是等效存储周期；$H_c$ 是访Cache的命中率，那么：

（1）增大主存容量，对 $H_c$ 基本不影响。虽然增大主存容量可能会使 $t_m$ 稍微有所加大，但如果 $H_c$ 已经很高，那么这种 $t_m$ 的增大对 $t_a$ 的增大不会有明显的影响。

（2）增大Cache中的块数，而块的大小不变，意味着Cache的容量增大了。由于 LRU替换算法属于堆栈型算法，因此将使 $H_c$ 上升，从而使 $t_a$ 缩短。$t_a$ 是否显著降低取决于$H_c$所处的水平，若 $H_c$ 较低，则 $t_a$ 会显著降低，反之则无明显变化。

（3）增大组相联组的大小，块的大小不变，意味着组内的块数增大了。这将使块的冲突概率下降，块的替换次数减少，$H_c$ 上升，从而使 $t_a$ 缩短。$t_a$ 是否显著降低取决于$H_c$所处的水平，若 $H_c$ 较低，则 $t_a$ 会显著降低，反之则无明显变化。

（4）增大块的大小，且组的大小和cache总容量不变。与（3）一致。

（5）提高 Cache 本身器件的访问速度，即减小 $t_c$ 的时间。仅当 $H_c$ 很高时，才会显著缩短 $t_a$ 。

单体交叉存储器转移概率

Cache 存储器替换

虚拟存储器替换

实页数=主存容量/页面大小；
虚页地址流=地址流/页面大小

存储体系的性能参数

存储系统

定义 ·

两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软硬结合的方式连接起来构成存储系统。计算机一般有两种存储系统：

Cache 存储系统
虚拟存储系统

【图】由多个存储器构成的存储系统
image-20230212123046510
再具化一点：
image-20230212123323599
image-20230212123617425
从上面可以得出一个结论：CPU 与主存储器的速度差距越来越大，且今后差距会更大。

基本要求 *

对存储系统的基本要求：大容量、高速度、低价格。

对于这些要求，有几个公式需要记：*****

存储器容量的公式 $S_M=W·m·l$ 简记：一碗麻辣粉
- $W$ - 存储体的字长
- $m$ - 存储体的个数
- $l$ - 存储体的字数
单/多体频宽的公式 $B_m=m·W/T_M$ 当$m=1$时名为单体公式。
- $m$ - 存储体的个数
- $W$ - 存储体的字长
- $T_M$ - 连续启动一个存储体所需的间隔时间

最大频宽与实际频宽的区别：最大频宽是存储器连续访问时的频宽，实际频宽：一般低于最大频宽。 ^

【例】1610#26、1504#26
image-20230212121410491
image-20230212121439209

人们总是期望“存储器的速度能与 CPU 相匹敌”，但是存储器的“容量、速度、价格”存在着相互制约的关系。因此，为了弥补 CPU 和存储器在速度上的差异，一条途径是在组成上引入并行和重叠技术，构成并行主存系统。通过这种方式可以实现“在每位价格基本保持不变的前提上，提高主存的频宽”。

谈存储时，一定要关注3样东西：容量、速度、价格。

容量、速度、价格有着这样一种关系：容量越大，速度越低，价格越高。

并行主存系统**

概念：能够并行读出多个 CPU 的单体多字、多体单字、多体多字的交叉访问主存系统，统称为并行主存系统。

并行主存系统的频宽分析结论：

提高模m,可以提高并行主存系统的速度（频宽），但实际频宽并不随着m的提高而线性提高。因为：

① 模m越大，总线越长，传输速度越慢。

② 转移指令的客观存在性会导致存储器的并行访问效率下降。

因此：提高m的值能提高主存系统的最大频宽，但主存的实际频宽并不随m值增大而线性提高，实际效率偏低。

【图】并行访问存储器结构框图
image-20230212123752183

每周期能访问的平均字数 *

【例】讨论模32和模16的多体单字存储器中，每个周期你呢个访问到的平均字数（记住公式，带上计算器）
IMG_9424

存储体系

存储体系是让构成存储系统的几种不同的存储器（$M_1 ~ M_n$）之间，配上辅助软、硬件或辅助硬件，使之从应用程序员角度来看，它在逻辑上是一个整体。不同于存储系统，存储系统是由多个存储器简单的组合在一起。

一般有两种基本的二级存储体系：

虚拟存储器。因主存容量不满足要求而提出来的。
Cache 存储器。因主存速度不满足要求而提出来的。

虚拟存储器	Cache 存储器

目的：扩容	目的：提速

构成依据（局部性）**

简述计算机程序时间上的局部性和空间上的局部性 2210

《计算机系统结构（2012版）》ch4p127

基于程序的局部性预知未来被访问信息的地址，包括时间的局部性和空间的局部性。其中：

时间上的局部性系指在最近的未来要用到的信息很可能是现在正在使用的信息。这是因为程序存在循环。

空间上的局部性系指在最近的未来要用的信息很可能与现在正在的使用的信息在程序空间上是邻近的。这是因为指令和数据一般都是相对簇聚成页或块的。

预知的准确性是设计存储体系好坏的主要标志，一般取决于算法和地址映像变换方式。

性能参数

评价存储器性能需引入3个指标：

每位价格 $c$
命中率 $H$
等效访问时间 $T_A$

以此图例给出公式：

【图】由两个存储器构成的存储系统
image-20230212130708243
其中， S - 容量；C - 每位价格；T - 访问时间

计算价格

计算命中率

计算平均访问时间 **

计算访问效率 **

访问效率与命中率和两级存储器的速度之比有关：

image-20230212131106510
由图可知，人们总是期望等效访问效率 $e→1$ ，那么：
在 $r$ 越大时，若要求 $e→1$ ，则 $H→1$。即等效访问速度与命中率密切相关。

虚拟存储器

虚拟存储器通过增设地址映像表机构来实现程序在主存中的定位。将程序分割成若干段或页，再用映像表指明程序的某段或某页是否已装入主存。若已装入，指明其在主存中的起始位置；若未装入，就去辅存中调段或调页，装入主存后在映像表中建立好程序空间和实存空间的地址映像关系。如此，【1910】程序执行时通过查映像表将程序（虚）地址变换成实（主）存地址再访问主存。

📚《计算机系统结构》page#134：虚实地址对应关系及空间压缩
华中科大-谢长生：虚拟存储器

提出虚拟存储器的原因：主存容量满足不了要求。

虚拟存储器研究4个问题：

映像规则：全相联
查找算法：页表、段表、TLB*
替换算法：LRU
写策略：写回法

存储管理方式

根据存储映像算法的不同，可有多种不同的存储管理方式的虚拟存储器，其中主要有 3 种存储管理方式：段式、页式、段页式。

段式虚拟存储器

程序都是有模块性，一个复杂的大程序总是可以分解成多个逻辑上相对独立的模块。这些模块可以是主程序、子程序或过程，也可以是数据块。 ^

段式管理：将主存按段分配的管理方式，即为段式管理。

地址映像

【图】段式虚拟存储器的地址映像方式
从这张图里，要看懂 2 个地方：
每个程序段的从 0 开始编址
每个程序的段长，可长可短

地址变换

【图】段式虚拟存储器的地址变换方法
image-20230212133514178

优缺点

优点方面：模块化性能高，便于程序和数据的共享；程序的动态链接和调度比较容易；便于实现信息保护。

缺点方面：地址变换时间长；主存储器利用率低；辅存管理困难。

页式虚拟存储器 * *

段式存储的诸多缺点，比如辅助开销大、查表速度慢、段间零头多等问题，促使人们提出了页式存储。

页式存储是把主存空间和程序空间都机械地等分成固定大小的页，按页顺序编号。

地址映像

将主存块按某种规则装入Cache 中；即建立多用户虚地址与主存地址的对应关系（一种函数关系）。

映像规则的选择要求（3看）：

看硬件是否速度快、价格低和实现方便
看块冲突概率是否低
看Cache 空间利用率是否高。

地址变换

地址变换：将主存地址变换成 Cache 地址；

优缺点

优点方面：

主存储器的利用率比较高
页表相对比较简单
地址变换的速度比较快
对磁盘的管理比较容易

缺点方面：

程序模块化性能不好
页表很长，需占用很大的存储空间

页面替换算法 * ^

页面失效

CPU 要使用的数据（或指令）不在主存时，会产生页面失效，需从辅存调取新页（页面中包含要使用的数据（或指令））

实页冲突

在主存已满的情况下发生了页面失效，那么从辅存调取新页到主存时，就会发生实页冲突。

为解决实页冲突问题，就必须通过页面替换算法来决定“选择主存中的哪个页面作为被替换的页”

替换算法 * ^

替换算法的确定依据 ：

主存是否有高的命中率；
算法是否便于实现；
辅助软、硬件成本是否低。

目前，主要的替换算法有：

随机算法（已过时）
最优替换算法（OTP），理想型算法，仅作为评价其它算法好坏的标准
先进先出算法（FIFO）
近期最少使用算法（LRU）

替换算法一般通过页地址流模拟其替换过程，再根据命中率的高低评价其好坏。影响命中率的因素除替换算法外，还有地址流、页面大小和主存容量等。^

【图】三种页面替换算法对同一页面地址流的调度过程
image-20230212203934288

堆栈型替换算法 * *

定义对任意一个程序的页地址流作两次主存页面数分配，分别分配 $m$ 个主存页和 $n$ 个主存页面，且满足 $m≤n$ 。若在任意时刻 $t$ ，主存页面集合 $B_t$ 都满足 $B_t(m) ⊆ B_t(n)$ 。则此类算法称为堆栈型替换算法。

特点随着分配给程序的主存页面数增加，主存的命中率也提高。

LRU 是堆栈型替换算法、OPT也是 *

不同的堆栈型替换算法，替换页号的过程也不同。对于 LRU 算法，是把主存中刚访问过的页号置于栈顶，把最久未访问的置于栈底。

【例】使用 LRU 替换算法对页面地址流进行堆栈处理
可以从中看出最近访问和最久未被访问的页号如何处置
IMG_9425

页面失效频率（PFF）算法

利用堆栈型替换算法的特点，人们对其加以改进并创造出了页面失效频率（PFF）算法：该算法可以根据程序运行中的主存页面失效率，来动态调整实页数。当主存页面失效率超过某个阈值时，就自动加配主存实页数，反之减少。以此使主存的命中率和使用率都得到提高。

提高主存命中率

影响主存命中率的因素 *

程序在执行过程中的页地址流分布情况。
页面大小
主存容量
页面替换算法
页面调度算法

如：页式虚拟存储器中，影响命中率的因素除替换算法外，还有地址流、页面大小、主存容量等。 ^

提高主存命中率的办法

利用页面大小提高命中率：

【图】页面大小与命中率的关系图。
image-20230215182001546

利用主存容量提供命中率

【图】主存容量与命中率的关系
image-20230215182138990

利用页面调度方式提高命中率

请求式：使用时，再调入主存。
预取式：程序重启前，先将上一次停止运行前一段时间内用到页面调入到主存，然后再启动程序。优点：避免程序重启后，发生页面失效；缺点：调入的页很可能用不上，导致时间浪费了，空间被占了。

段页式虚拟存储器

段页式存储即把主存机械地等分成固定大小的页，程序按模块分段，每个段又分成与主存页面大小相同的页。

地址映像

【图】段页式虚拟存储器的地址映像
image-20230212135618065

地址变换

【图】段页式虚拟存储器的地址变换过程
image-20230212135956576

高速缓冲（Cache）存储器

高速缓冲存储器：弥补主存速度不足，在 CPU 和主存之间设置一个高速、小容量的 Cache ，构成【 Cache -主存】存储层次，使之从 CPU 角度看，速度接近于 Cache ，容量却是主存。

【图】Cache - 主存存储层次图
image-20230215183943952

当我们谈Cache存储系统时，我们从4个方面谈：

（数据）如何放？3种映像方式（全、直、组相联映像）
（数据）如何找？根据地址找（块号、块内地址等）
（数据）如何写？写直达法、写回法
（数据）如何换？LRU等替换算法

地址映像与变换

全、直、组相联地址映像与变换的过程-华中科技大学

【Cache-主存】的地址映像是指把主存中的程序按照某种规则装入到cache中，并建立主存地址与cache地址之间的对应关系。

【Cache-主存】的地址映像方式有 3种，简记：全直组 。 ^

【Cache-主存】的地址变换是指当程序装入到cache后，在程序运行过程中，把主存地址变换成cache地址。 ^

选取地址映像方法的需要考虑哪些因素？

硬件是否速度高、价格低、易实现
块冲突概率是否低
Cache空间利用率是否高

3种地址映像和变换分别是什么？ 简记：全直组

全相联映像和变换
直接相联映像和变换
组相联映像和变换

全相联地址映像与变换

地址的映像规则

主存的任意一块可以映像到 Cache 中的任意一块。 简记：多对多映射

【图】cache-主存的全相联地址映像，映像关系有 $C_b × M_b$ 种
image-20230215184802915

地址的变换过程

【图】cache-主存的地址变换过程
image-20230215185049012

优缺点

优点：块冲突概率低，空间利用率高。

缺点：相联存储成本高，查表速度慢。

直接相联地址映像与变换

地址的映像规则

主存储器中一块只能映像到 Cache 的一个特定的块中。 简记：一对一映射

【图】直接映像方式的地址映像规则
image-20230215185440351

地址的变换过程

【图】直接相联地址变换过程
image-20230215185854589

优缺点

优点：硬件实现简单，不需要相联访问存储器；访问速度快，不需要地址变换。

缺点：块冲突概率高。

组相联地址映像与变换

地址映像规则

主存和Cache按同样大小划分成块和组。
主存和Cache按照**“组间直，组内全”**的原则进行映像。

【图】组相联地址映像方式
IMG_F31E18E348B8-1

地址变换过程

【图】组相联映像的地址变换过程
image-20230215191236572

每块一个计数器
每组一个计数器

每块一个计数器

计数规则：新装入或替换的块，其计数器清零，同组其他块的计数器都加 1

【图】每块一个计数器
image-20230216183049198
如：
装入块00使，块00的计数器清零，其余加1
装入块01时，块01的计数器清零，其余加1

每组一个计数器

替换与计数规则：本组有替换时，计数器加1。计数器的值为待被替换的块号

NOVA3 机的 Cache 采用组相联映像方式，Cache 每组的块数为 8，每组设置了一个 3 位计数器。在需要替换时，计数器的值加1，用计数器的值直接作为被替换块的块号。
如 000 + 1 = 001，则被替换的块的块号位001

优缺点

优点：实现简单，能够利用历史上的块地址流情况。

缺点：没有利用到程序的局部性特点。（比较致命）

LRU 算法及其实现 *

为每一块设置一个计数器，计数器长度=块号字段长度

规则：新装入或替换的块，计数器清零，同组中其他块的计数器加1。命中的块计数器清零，需替换时，替换掉同组中取计数器值最大的块。

IBM 370/165 的 Cache 采用组相联映象方式。
每组有4块，为实现 LRU 替换算法，在块表中为每一块设置一个 2 位的计数器。在访问 Cache 的过程中，块的装入、替换及命中时，计数器的工作情况：
IMG_80C3F397D371-1

【图】 Cache 加速比公式：
image-20230216190306201
$T_m$ ：主存访问周期
$T_c$ ：cache 访问周期
$T$ : cache 等效访问周期
$H$：命中率
加速比 $S_p$ 与 $H$ 的关系：
image-20230216190509570
结论：提高加速比的最好途径是提高命中率。