复旦大学961-计算机系统基础-第三章-存储器结构及虚拟存储器

水深无声 2022-12-24 13:51 153阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  局部性
 *  存储器层级结构
 *  计算机高速缓存原理
 *  计算高速缓存对性能的影响
 *  地址空间
 *  虚拟存储器
 *  虚拟内存的管理、翻译和映射
 *  TLB（快表）
 *  动态存储器分配和垃圾收集
 *   *  垃圾收集器（GC）的基本概念

# 局部性 #

《CSAPP》P418

一个编写良好的计算机程序常常具有良好的**局部性（locality）**。也就是，它们倾向于引用邻近与其他最近引用过的数据项的数据项。或者最近引用过的数据项本身。这种倾向被称为**局部性原理（principle of locality）**。

局部性通常有两种不同的形式（《王道2021操作系统》P194）：

1.  **时间局部性（temporal locality）**：程序中的某条指令一旦执行，不久后该指令可能再次执行，某数据被访问过，不久后该数据可能再次被访问。产生时间局部性的典型原因是程序中存在着大量的循环操作。
2.  **空间局部性（spatial locality）**：一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围内，因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

# 存储器层级结构 #

《CSAPP》P421

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70]  
《王道2021组原》P96  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70 1]

# 计算机高速缓存原理 #

《王道2021组原》P125  
Cache指高速缓存，位于存储器层次结构的顶层，通常由SRAM组成。其基本结构如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70 2]  
为了便于Cache和主存之间交换信息，Cache和主存都被划分为相等的块（也称为行）。Cache中的块远远少于主存中的块，所以它仅保存主存中最活跃的若干块副本。因此，Cache按照某种策略，预测CPU未来一段时间内欲访存的数据，将其装入Cache。

当CPU发出**读请求**时，会出现以下几种情况：

1.  若访存地址在**Cache命中**，就将地址转换为Cache地址，直接对Cache进行读操作，与主存无关
2.  若**Cache未命中**，则仍需访问主存，并把此字所在的块一次性地从主存调入Cache。若此时Cache已满，则需要根据某种替换算法，用这个块替换Cache中原来的某块信息。

当CPU发出**写请求**时，若Cache命中，为了防止写造成的内存和Cache数据不一致问题，通常的处理方法有两种：

1.  **全写法（write-through）**：把数据同时写入Cache和主存
2.  **写回法（write-back）**：只修改Cahce的内容，而不立即写入主存，只有当此块被换出时才写回主存。

**Cache和主存的映射方式**：Cache行中的信息是主存中某个块的副本，**地址映射**是指把主存的地址空间映射到Cache地址空间，即把存放在主存中的信息按照某种规则装入Cache。地址映射的方法有以下三种：

1.  **直接映射**：主存中的每一块只能装入Cache中的唯一位置。若这个位置有已有内容，则产生块冲突，原来的块将无条件地被替换出去（无需使用替换算法）。直接映射实现简单，但不够灵活，即使Cache的其他许多地址空间空着也不能占用。
2.  **全相联映射**：主存中的每一块可以装入Cache中的任何位置，每行的增加标记，用于指出该行取自主存中的哪一块，所以CPU访存时需要与所有Cache行的标记进行比较。全相联映射方式的优点是比较灵活，Cache块的冲突概率低，空间利用率高，命中率也高；缺点是标记的比较速度较慢，实现成本较高，通常采用昂贵的按内容寻址的相联存储器进行地址映射。
3.  **组相联映射**：将Cache空间分成大小相同的组，主存的一个数据块可以装入一组内的任何一个位置，即组间采用直接映射，而组内采用全相联映射。

# 计算高速缓存对性能的影响 #

《CSAPP》P444

通过分析**存储器山** 可以得出以下结论：

1.  利用时间局部性，使得频繁使用的字从L1（一级缓存）中取出
2.  利用空间局部性，使得尽可能多的字从一个L1高速缓存中可以访问到。

**通过重新排列循环以提高空间局部性**：降低高速缓冲的不命中率。

**通过使用分块来提高时间局部性**

**在程序中利用局部性**：

1.  将你的注意力集中在内循环上，大部分计算和内存访问都发生在这里
2.  按照对象存储在内存中的顺序，连续的访问你的数据，从而使得你程序中的空间局部性最好
3.  一旦从存储器中读入一个数据对象，就尽可能多地使用它，从而使程序的时间局部性最好。

# 地址空间 #

《CSAPP》P560

**地址空间（address space）** 是一个非负整数地址的有序集合：如果地址空间中的整数是连续的，那么我们说它是一个**线性地址空间（linear address space）**。CPU从一个有2n个地址的地址空间中生成虚拟地址，这个地址空间称为**虚拟地址空间（virtual address space）** 。该地址空间被称为n位地址空间。现代系统通常支持32位和64位。

一个系统还有一个**物理空间地址（physical address space）**，对应于系统中物理内存的M个字节。

操作系统按照虚拟空间地址进行寻址，由**内存管理单元（Memory Management Unit, MMU）** 进行**地址翻译**，然后翻译成主存中的物理空间地址，进而访存。

# 虚拟存储器 #

《王道2021操作系统》P194 虚拟存储器的定义和特征

在程序装入时，将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将暂时不使用的内容换出到外存上，从而腾出空间来存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为**虚拟存储器**。

虚拟存储器有三个主要特征：

*  **多次性**：多次性是指无须在作业运行时一次性地装入内存，而允许被分成多次调入内存运行。
 *  **对换性**：对换性是指无须在作业运行时一直常驻内存，而允许在作业的运行过程中，进行换进和换出
 *  **虚拟性**：虚拟性是指从逻辑上扩充内存的容量，使用户所看到的内存容量远大于实际的内存容量

《王道2021组原》P143

主机和联机工作的辅存（磁盘）共同构成了虚拟存储器，二者在硬件和系统软件的共同管理下工作。对应用程序员来说，虚拟存储器是透明的。虚拟存储器具有主存的速度和辅存的容量，提高了存储系统的性价比。

虚拟存储器将主存或辅存的地址空间**统一编址**，形成一个庞大的地址空间，在这个空间内，用户可以自由编程，不必在乎实际的主存容量和程序在主存中实际的存放位置。

用户编程允许涉及的地址称为**虚地址**或**逻辑地址**，虚地址对应的存储空间称为**虚拟空间**或**程序空间**。实际的主存单元地址称为**实地址**或**物理地址**。

**虚拟地址使用原理**：CPU使用虚地址时，由辅助硬件找出虚地址和实地址之间的对应关系，并判断这个虚地址对应的存储单元内容是否已装入主存。①若已在主存中，则通过地址变换，CPU可直接访问主存指示的实际单元；②若不在主存中，则把包含这个字的一页或一段调入主存后再由CPU访问。③若主存已满，则采用替换算法置换主存中的一页或一段。

# 虚拟内存的管理、翻译和映射 #

《王道2021操作系统》P194

虚拟内存的管理方式有以下三种方式：

*  **请求分页存储管理**：将内存按照相同单位划分成相同的块，进程中的块称为**页（Page）**，内存中的块称为**页框（Page Frame）**。 外存也做相同划分。系统为每个进程建立一张**页表**，记录了进程页在内存中对应的物理页框号。在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存中时，再通过调页功能将其调入，同时还可以通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间。
 *  **请求分段存储管理** （应该不考）
 *  **请求段页式存储管理** （应该不考）

**缺页中断的概念**：在请求分页系统中，每当所要访问的页面不在内存中时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞（调页完成唤醒），若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中的相应页表项，若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）。

**地址转换过程**如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70 3]

《CSAPP》P582  
**内存映射的概念**：Linux通过将一个虚拟内存区域与一个磁盘上的对象（object）关联起来，以初始化这个虚拟内存区域的内容，这个过程称为**内存映射（memory mapping）**。 虚拟内存区域可以映射到以下类型的对象：

*  **Linux文件系统中的普通文件**
 *  **匿名文件**

一旦一个虚拟页面被初始化了，它就在一个由内核维护的专门的**交换文件（swap file）** 之间换来换去。交换文件也叫做**交换空间（swap space）** 或者**交换区域（swap area）** 。

简单解释（个人理解）：就是把一个文件映射到程序的内存中（就好像程序把整个文件读入到内存中一样），程序就可以直接像操作内存一样操作该文件。而实际上，操作系统并没有真的把这些文件放入到内存，而是利用虚拟内存技术，对这些文件进行管理。

# TLB（快表） #

《王道2021组原》P145

**快表（TLB）** 是用来加快地址转换的。由于页表存在于主存中，访问起来相对较慢，所以根据局部性原理，将近期经常访问的页面存放在高速缓冲器组成的快表中，可以加快页表查询速度。

所以，当查询页表时，首先查询快表（TLB），若TLB命中，则直接通过TLB进行地址转换。若没有命中，再去主存中查询页表。

有些系统还支持快表和慢表（存储在主存中的页表）同时查询。

# 动态存储器分配和垃圾收集 #

《CSAPP》P587

**动态内存分配器（dynamic memory allocator）** 使用来为程序动态分配内存的。动态内存分配器维护着一个进程的虚拟内存区域，称为**堆（heap）**。

动态内存分配器有两种风格：

1.  **显式分配器（explicit allocator）**：要求程序显式的分配内存和释放内存。如C中，使用malloc分配内存，使用free释放内存
2.  **隐式分配器（implicit allocator）**：要求分配器可以自己检测哪些内存是不需要的，然后自己释放。隐式适配器也叫作**垃圾收集器（garbage collector，GC）**。Java里的GC就是隐式分配器。

## 垃圾收集器（GC）的基本概念 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70 4]  
垃圾收集器维护着这样的类似这样一张**可达图（reachability graph）** 的数据结构。 其中圆点为某个指针（其指向了一块内存区域），灰色部分为堆。若堆中的数据可以由根节点到达它，则它是可达的，这说明它不是垃圾。而蓝色的小球，堆外的根节点没有路径可以到达它那，所以它是不可达的，所以它是垃圾。

对于GC的最主要问题怎么找出那些不可达的节点。**Mark&Sweep垃圾收集器**可以干这个，基本原理为（分为两个阶段）：

1.  mark阶段：从根节点往下开始标记，把所有的可达节点都给标记一下。
2.  sweep阶段：最后没有被标记的节点就是垃圾，该阶段就会把没有被标记的内存节点给释放掉。

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70]: /images/20221120/d2e8892503474cab91e84335b6f2557a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70 1]: /images/20221120/4720fa4e23334e2bac0237e0f5dadcaa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201128163900891.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201130214203350.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020113023143337.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA==,size_16,color_FFFFFF,t_70