CSAPP 虚拟存储器 笔记

一个系统中的进程是与其他进程共享 CPU 和主存资源的。然而，共享主存会形成一些特殊的挑战。

虚拟内存提供了三个重要的能力：

• 它将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在主存之间来回传送数据，通过这种方式，它高效地使用了主存。
• 它为每个进程提供了一致的地址空间，从而简化了内存管理。
• 它保护了每个进程的地址空间不被其他进程破坏。

内存管理要干些啥？

• 内存空间的分配与回收
• 内存空间的扩充
  • 覆盖技术
  • 交换技术
  • 虚拟存储
• 地址转换：逻辑 => 物理
• 存储保护：保证各进程只在自己的内存空间访问，不会越界
  • 上下界寄存器
  • 重定位寄存器 + 界地址寄存器

学习资源

LWN.net 上有一系列的 “What every programmer should know about memory” 文章你需要读一下。当然，你可以直接访问一个完整的 PDF 文档。下面是这个系列文章的网页版列表。读完这个列表的内容，你基本上就对内存有了一个比较好的知识体系了。

• Part 1: Introduction ，中译版为 “每个程序员都应该了解的内存知识【第一部分】”
• Part 2: CPU caches
• Part 3 (Virtual memory)
• Part 4 (NUMA systems)
• Part 5 (What programmers can do - cache optimization)
• Part 6 (What programmers can do - multi-threaded optimizations)
• Part 7 (Memory performance tools)
• Part 8 (Future technologies)
• Part 9 (Appendices and bibliography)

连续分配

分类：

• 单一连续：只支持单道程序，内存分为系统区和用户区
• 固定分区
• 动态分区：在程序被装入内存时，根据进程的大小动态调整分区
  • 首次适应
  • 最佳适应
  • 最坏适应
  • 邻近适应

缺点：

• 分配给一个程序的物理内存是连续的
• 内存利用率低
• 有内外碎片问题

非连续分配

优点：

• 一个程序的物理地址空间是非连续的
• 更好的内存利用和管理
• 允许共享代码与数据（共享库等）
• 支持动态加载和动态链接

缺点：

• 如何建立虚拟地址和物理地址之间的转换
  • 软件方案
  • 硬件方案

分段

段是信息的逻辑单位。

分段的目的是更好地满足用户需求。

一个段通常包含着一组属于一个逻辑模块的信息，更容易实现信息的共享和保护。

分段对用户是可见的，用户编程时需要显式给出段名。

段的大小不固定，取决于用户编写的程序（低级语言）。

• 程序text段
  • 库
  • 用户代码
• 程序数据段
• 运行栈
• 堆

段表：段号、段长、基址

分页

页是信息的物理单位。分页的目的是为了实现离散分配，提高内存利用率。

分页仅仅是系统管理上的需要，完全是系统行为，对用户不可见。

页表

作用：记录进程中各个页与所占用内存块的关系，形成映射。

快表

多级页表

单页表遇到的问题：

• 页表必须连续存放，若页表项小，总的页表太占空间；页表项过大，内碎片影响大。
• 没有必要让所有页表常驻内存，进程在一段时间内可能只需要访问几个特定的页面。

实现对页表本身的虚拟存储。

注意：

• 各级页表的大小不能超过一个页面。若两级不够，可分成多级
• 多级页表访存次数（无快表） = 页表级数 + 1

段页

进程分段 =》段分页 =》内存分块

维护一个段表和若干个页表

虚拟内存

程序不需全部装入即可运行，运行时根据需要动态调入数据，若内存不够，还需换出一些数据。

请求调页

访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存

页表结构：内存块号 中断位P 访问位A 修改位M 外存地址

缺页中断与一般的 I/O 中断区别：

• 缺页中断是指令执行时中断，而普通的是两条指令执行之间。
• 缺页中断是运行状态，而普通的是阻塞态。

页面置换

内存空间不够时，将内存中暂时用不到的信息换出到外存，换出时注意清掉快表中的缓存。

理想置换算法要求：被换出的页面在以后的运行中不需要。

• 先进先出（FIFS） 往下挤。实现简单，性能差，可能出现 Belady 现象，即增加内存块后，缺页中断却增加。
• 最近最久未使用（LRU） 依然是往下挤，区别在于，一旦命中，提到栈顶。
• 最近最不常用（LFU） 记录访问次数，淘汰访问次数最小的，但这样实现太麻烦，所以直接在对应的内存块上计数。
• 最近未使用（NRU） 搞一个定时器，定期清除访问位。
• 二次机会（Second Chance） 一般来说不用管改进算法，只要 A 请求调页时，不算访问，之后的命中才算，而且从时间最久开始，遇到0就直接淘汰，遇1置0。 置换掉的页作为最新页放顶上，注意是按时钟旋转，而不是直接往下挤。 改进后的算法加了一个判断位——修改位M，减少了I/O，也降低了抖动现象。
• 页缓冲

内存管理

• 简化链接
• 简化加载
• 简化共享
• 简化内存分配

物理和虚拟寻址

计算机系统的主存被组织成一个由 M 个连续的字节大小的单元组成的数组。每个字节都有一个唯一的物理地址。

在物理地址与虚拟地址间加个地址翻译就构成了虚拟寻址。

地址空间

地址空间是一个非负整数地址的有序集合。

地址空间的概念是很重要的，因为它清楚地区分了数据对象（字节）和他们的属性（地址）。

缓存

内存成了对硬盘的缓存，虚拟页面可划分为未分配的、未缓存的和已缓存的。

地址翻译

逻辑地址到物理地址

内存映射

回到本章前言，“虚拟内存是强大的”。

• 你知道可以通过读写内存位置读或者修改一个磁盘文件的内容吗？
• 可以加载一个文件的内容到内存中，而不需要进行任何显示地复制吗？

将一个文件或其他对象映射到进程的地址空间，实现文件磁盘地址和进程地址空间中一段虚拟地址的一一对应。

实现了这样的映射关系后，进程就可以采用指针的方式读写操作这一段内存，而系统会自动回写脏页面到对应的文件磁盘上，即完成了对文件的操作而不必再调用 read、write 等系统调用函数。

相反，内核空间对这段区域的修改也直接反应用户空间，从而可以实现不同进程的文件共享。

简单总结，有如下特点：

• 提高数据的读、写和传输的时间性能
  • 减少了数据拷贝次数
  • 用户空间和内核空间的高效交互（通过映射区域直接交互）
  • 用内存读写代替 I/O 读写
• 提高内存利用率：通过虚拟内存、共享对象

动态内存分配

为什么要动态分配内存？因为很多时候只有在运行时才知道某些数据结构的大小。

malloc 与 mmap、munmap 区别是什么？

分配器

这一部分可以借鉴操作系统为进程分配内存的操作。

垃圾收集

一个进程终止后，其占用的内存由操作系统来释放和重新分配。

进程存活时，释放掉不用的内存就得交给程序本身了，C / C++ 把这活交给了程序员，Java 这类的有自己的垃圾回收器。

回收器

C 中常见的内存错误

• 间接引用坏指针
• 读未初始化的内存
• 允许栈缓冲区溢出
• 假设指针和他们指向的对象是相同的大小
• 造成错位错误
• 引用指针，而不是它所指向的对象
• 误解指针运算
• 引用不存在的变量
• 引用空闲堆块中的数据
• 引起内存泄露