> For the complete documentation index, see [llms.txt](https://lewiszlw.gitbook.io/notebooks/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lewiszlw.gitbook.io/notebooks/blogs/history/cun-chu-xi-tong.md).

# 存储系统的层次结构

## 存储系统的层次结构概述

存储系统的性能直接影响到整个计算机系统的性能。如何以合理的价格，设计容量和速度都满足计算机系统要求的存储器系统，始终是计算机系统结构设计中的关键问题之一。

人们对这三个指标的要求：容量大、速度快、价格低。

三个要求是相互矛盾的

* 速度越快，每位价格就越高；
* 容量越大，每位价格就越低；
* 容量越大，速度越慢。

解决方法：采用多种存储器技术，构成多级存储层次结构。

* 程序访问的局部性原理：对于绝大多数程序来说，程序所访问的指令和数据在地址上不是均匀分布的，而是相对簇聚的。
* 程序访问的局部性包含两个方面
  * 时间局部性：程序马上将要用到的信息很可能就是现在正在使用的信息。
  * 空间局部性：程序马上将要用到的信息很可能与现在正在使用的信息在存储空间上是相邻的。

## 存储系统的性能参数

下面仅考虑由M1和M2构成的两级存储层次：

* M1的参数：S1，T1，C1
* M2的参数：S2，T2，C2

存储容量S 一般来说，整个存储系统的容量即是第二级存储器M2的容量，即S=S2。

每位价格C $$C=\frac{C\_1S\_1+C\_2S\_2}{S\_1+S\_2}$$ 当$S\_1<\<S\_2$时，$C\approx C\_2$。

命中率H

* 命中率：CPU访问存储系统时，在M1中找到所需信息的概率。 $$H=\frac{N\_1}{N\_1+N\_2}$$
  * N1 ── 访问M1的次数
  * N2 ── 访问M2的次数
* 不命中率 ：F＝1－H

平均访问时间TA 分两种情况来考虑CPU的一次访存：

* 当命中时，访问时间即为T1（命中时间）
* 当不命中时，情况比较复杂。 不命中时的访问时间为：$T\_2+T\_B+T\_1=T\_1+T\_M$ 其中$T\_M=T\_2+T\_B$
  * 不命中开销TM：从向M2发出访问请求到把整个数据块调入M1中所需的时间。
  * 传送一个信息块所需的时间为TB。

考虑到命中和不命中的概率分别为H和1-H，故该存储系统的平均访存时间为 $$T\_A=HT\_1+(1-H)(T\_1+T\_M)=T\_1+(1-H)T\_M$$ 或 $$T\_A=T\_1+FT\_M$$

## 三级存储系统

三级存储系统

* Cache（高速缓冲存储器）
* 主存储器
* 磁盘存储器（辅存）

可以看成是由“Cache—主存”层次和“主存—辅存”层次构成的系统。 从主存的角度来看

* “Cache－主存”层次：弥补主存速度的不足
* “主存－辅存”层次： 弥补主存容量的不足

“Cache-主存”和“主存-辅存”层次的区别

| 比较项目             | “Cache-主存”层次 | “主存-辅存”层次   |
| ---------------- | ------------ | ----------- |
| 目的               | 为了弥补主存速度的不足  | 为了弥补主存容量的不足 |
| 存储管理的实现          | 全部由专用硬件实现    | 主要由软件实现     |
| 访问速度的比值（第一级比第二级） | 几比一          | 几万比一        |
| 典型的块（页）大小        | 几十个到几百个字节    | 几千个以上字节     |
| CPU对第二级的访问方式     | 可直接访问        | 均通过第一级      |
| 不命中时CPU是否切换      | 不切换          | 切换到其他进程     |
| # Cache的基本知识     |              |             |
| ## 基本结构和原理       |              |             |
| Cache和主存分块       |              |             |

* Cache是按块进行管理的。Cache和主存均被分割成大小相同的块。信息以块为单位调入Cache。相应地，CPU的访存地址被分割成两部分：块地址和块内位移。
  * 主存块地址（块号）用于查找该块在Cache中的位置。
  * 块内位移用于确定所访问的数据在该块中的位置。

Cache的基本工作原理示意图 ![存储系统1](http://ofolh8dcq.bkt.clouddn.com/%E5%AD%98%E5%82%A8%E7%B3%BB%E7%BB%9F1.PNG)

## 映像规则

映像规则有以下三种：

1. 全相联映象

* 全相联：主存中的任一块可以被放置到Cache中的任意一个位置。　　　　　　　　
* 对比：阅览室位置 ── 随便坐
* 特点：空间利用率最高，冲突概率最低，实现最复杂。 ![存储系统2](http://ofolh8dcq.bkt.clouddn.com/%E5%AD%98%E5%82%A8%E7%B3%BB%E7%BB%9F2.PNG)

1. 直接映象

* 直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。（循环分配）
* 对比：阅览室位置 ── 只有一个位置可以坐
* 特点：空间利用率最低，冲突概率最高，实现最简单。
* 对于主存的第i 块，若它映象到Cache的第j 块，则:j＝i mod (M ) （M为Cache的块数）
* 设M=2m，则当表示为二进制数时，j实际上就是i的低m位 ![存储系统3](http://ofolh8dcq.bkt.clouddn.com/%E5%AD%98%E5%82%A8%E7%B3%BB%E7%BB%9F3.PNG)

1. 组相联映象

* 组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。
* 组相联是直接映象和全相联的一种折衷 ![存储系统4](http://ofolh8dcq.bkt.clouddn.com/%E5%AD%98%E5%82%A8%E7%B3%BB%E7%BB%9F4.PNG)
* 组的选择常采用位选择算法
  * 若主存第i 块映象到第k 组，则: k＝i mod（G） （G为Cache的组数）
  * 设$G=2^g$，则当表示为二进制数时，k 实际上就是i 的低 g 位
  * 低g位以及直接映象中的低m位通常称为索引。
* n路组相联：每组中有n个块(n＝M/G )。 　　n 称为相联度。 　 相联度越高，Cache空间的利用率就越高，块冲突概率就越低，不命中率也就越低。

## 查找方法

1. 通过查找目录表来实现

* 目录表的结构
  * 主存块的块地址的高位部分，称为标识 。
  * 每个主存块能唯一地由其标识来确定
* 只需查找候选位置所对应的目录表项

1. 并行查找与顺序查找 提高性能的重要思想：主候选位置(MRU块)（前瞻执行）

Cache的容量与索引、相联度、块大小之间的关系为 $$Cache的容量=2^{index}\times 相联度 \times 块大小$$

## 替换算法

直接映像Cache中的替换很简单，因为只有一个块，别无选择。而在组相联和全相联Cache中，则有多个块供选择。 主要的替换算法有以下三种：

* 随机法 优点：实现简单
* 先进先出法
* 最近最少使用法
  * 选择近期最少被访问的块作为被替换的块。（实现比较困难）
  * 实际上：选择最久没有被访问过的块作为被替换的块。
  * 优点：命中率较高

## 写策略

“写”操作必须在确认是命中后才可进行 “写”访问有可能导致Cache和主存内容的不一致

两种写策略 写策略是区分不同Cache设计方案的一个重要标志。

* 写直达法（也称为存直达法） 执行“写”操作时，不仅写入Cache，而且也写入下一级存储器。
* 写回法（也称为拷回法） 执行“写”操作时，只写入Cache。仅当Cache中相应的块被替换时，才写回主存。 (设置“修改位”)

两种写策略的比较

* 写回法的优点：速度快，所使用的存储器带宽较低。
* 写直达法的优点：易于实现，一致性好。

“写”操作时的调块

* 按写分配(写时取) 写不命中时，先把所写单元所在的块调入Cache，再行写入。
* 不按写分配(绕写法) 写不命中时，直接写入下一级存储器而不调块。

写策略与调块

* 写回法 ── 按写分配
* 写直达法 ── 不按写分配

> 《计算机系统结构教程（第2版）》张晨曦 王志英 等 著