CSAPP又双叒叕来一遍之虚拟内存

Bkfish

2019-01-13

CSAPP

虚拟内存

本章还是比较肝的，说起虚拟内存想起了另外一个书《C++ primer plus》，大一寒假玩了一个月，唯独花了点时间看了这本书，印象最深的还是这本书讲了内存模型和名称空间，后悔啊大一上没看csapp，所以看的一脸懵逼，还没看懂，csapp这一章确实很精髓，曹神也和我聊过（Orz,曹神牛逼），看了csapp感觉其他所有的书都是在这个基础上的拓展，这样吸收其他书的知识就没有很高的门槛，对于内存这一块，印象比较深刻的还是《程序员的自我修养》，专门讲链接装载与库的一本书，没看csapp之前看那本书真的是一脸懵逼，看完csapp再看那本书还是收获非常大的。

虚拟存储器又叫做虚拟内存，我们现在的操作系统普遍都支持了虚拟内存，这样做是因为我们同时运行着太多的程序了，如果不使用虚拟内存4G的内存空间很快就会被耗尽，而一旦没有了内存空间，其他程序就无法加载了。虚拟内存的出现就是为了解决这个问题，当一个程序开始运行的时候，其实是为每个程序单独创建了一个页表（这个以后讲），只将一部分放入内存中，以后根据实际的需要随时从硬盘中调入内容。当然虚拟内存不仅仅只有这个功能，我们的操作系统也是在内存中运行着的，虚拟内存同时还提供了一种保护，这样做其他进程就不会损坏掉系统的内存空间。

1、物理寻址和虚拟寻址

1.1、物理地址(Physical Address,PA):计算机系统的主存被组织为M个连续的字节大小的单元组成的数组。每个字节的地址叫物理地址.CPU访问存储器的最自然的方式使用物理地址，这种方式称为物理寻址。早期的PC，数字信号处理器，嵌入式微控制器以及Cray超级计算机使用物理寻址

主存的每个地址都是唯一的，第一个字节地址为0，接下来为2，以此类推。CPU使用这种访问方式就是物理寻址。上图所示就是CPU通过地址总线传递读取主存中4号地址开始处的内容并通过数据总线传送到CPU的寄存器中。

1.2、现代处理器使用的是虚拟寻址(virtual addressing)的寻址形式。

CPU芯片上有叫做存储器管理单元(Memory Management Unit,MMU)的专用硬件
使用虚拟寻址的时候，cpu先是生成一个虚拟地址：4100再经过地址翻译器，将4100翻译成物理地址。

我们知道对内存的访问要比硬盘的访问快10000倍，如果我们在内存中没有找到相应的内容（不命中），而需要到硬盘上找的话，我们必须要提供相对来说高效率的访问方式。这时候就创建了一个虚拟存储器，管理着磁盘，以每页的方式进行整合，每个页面的大小4kb-2mb不等，加上偏移量就成为了一个虚拟地址。比如4100，说明的就是页4编号，偏移100处的位置。这就比挨个挨个单独寻址要快的多。

2、地址空间

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

如果地址空间中整数是连续的，我们说它是线性地址空间(linear address space)。
- 为了简化讨论，我们总是假设使用线性地址空间。
在一个带虚拟存储器的系统中，CPU从一个有N=2^n个地址的地址空间中生成虚拟地址，这个地址空间称为虚拟地址空间(virtual address space)。
一个地址空间大小是由表示最大地址所需要的位数来描述的。
- 如N=2^n个地址的虚拟地址空间叫做n位地址空间。
- 现在操作系统支持32位或64位。
一个系统还有物理地址空间,它与系统中物理存储器的M=2^m(假设为2的幂)个字节相对应。

地址空间的概念很重要，因为它区分了**数据对象(字节)和它们的属性(地址)**。

每个字节(数据对象)一般有多个独立的地址(属性)。每个地址都选自不同的地址空间。
- 比如一般来说。
  - 字节 有一个在虚拟地址空间的虚拟地址。
  - 还有一个在物理地址空间的 物理地址。
  - 两个地址都能访问到这个字节。
- 类似现实世界的门牌号, 和经纬度。

3、虚拟存储器作为缓存的工具

虚拟存储器(VM)被组织为一个存放在磁盘上的N个连续字节大小的单元组成的数组。（这是书上的原文，看了很久，其实没怎么看得懂，意会一波算了）

每个字节都有一个唯一的虚拟地址，这个虚拟地址作为到数组的索引。
磁盘上数组的内容被缓存到主存中。
- 同存储器层次结构其他缓存一样，磁盘上的数据被分割称块。
  - 这些块作为磁盘和主存之间的传输单元。
  - 虚拟页(Virtual Page,VP)就是这个块
    - 每个虚拟页大小为P=2^p字节。
- 物理存储器被分割为物理页,大小也为P字节
  - 也被称为页帧(page frame)
任何时候，虚拟页的集合都被分为3个不相交的子集。
- 未分配的:VM系统还未分配(或者创建)的页。未分配的块没有任何数据与之相关联。
  - 不占用磁盘空间
  - 通过malloc来分配
- 缓存的：当前缓存在物理存储器的已分配页。
- 未缓存的:没有缓存在物理页面存储器中的已分配页。

3.1、DRAM缓存的组织结构

DRAM就是我们传统的8g,16g啥的内存。
DRAM表示虚拟存储器系统的缓存，在主存中缓存虚拟页,有两个特点。

DRAM缓存不命中处罚十分严重。
- 因为磁盘比DRAM慢100000多倍。
访问一字节开销
- :从一个磁盘的一个扇区读取第一个字节的时间开销要比从该扇区中读连续的字节慢大约100000倍

DRAM缓存的组织结构由这种巨大的不命中开销驱动。因此有以下特点。
(有些地方不是特别懂，之后看完第六章应该会好点)

虚拟页往往很大。
- 4KB~2MB
- 访问一字节开销的原因才要这么大。
DRAM缓存是全相联
- 也就是：任何虚拟页都能放在任何物理页中。
- 原因在于大的不命中惩罚
更精密的替换算法
- 替换错了虚拟页的惩罚很高。
DRAM缓存总是写回
- 因为对磁盘的访问时间很长
- 而不用直写

3.2、页表

页表是一个存放在内存中的数据结构，MMU就是通过页表来完成虚拟地址到物理地址的转换。这个数据结构每一个条目称为PTE（Page Table Entry），由两部分组成：有效位和n位地址段。有效位如果是1，那么n位地址就指向已经在内存中缓存好了的地址；如果为0，地址为null的话表示为分配，地址指向磁盘上的虚拟内存（pagefile.sys）的话就是未缓存。我们来看一个典型的页表图：

虚拟页vp1,2,7,4当前被缓存在内存中，页表上有效位设置成1，分别用PTE1，2，4，7表示。VP0和VP5（PTE0、5）未被分配，VP3和VP6被分配并指向虚拟内存，但未被缓存。

3.3、页命中

当我们使用2100虚拟地址来访问虚拟页2的内容的时候，就是一个页命中。地址翻译将指向PTE2上，由于有效位1，地址翻译器MMU就知道VP2已经缓存在内存中了。就使用页表中保存的物理地址进行访问。

3.4、缺页咋整

我们再来看看不命中，也就是缺页的情况，当CPU需要VP3的一个字时，初始化是这样的：

PTE3有效位是0，同时地址位指向了虚拟内存（pagefile.sys），就会触发缺页异常。异常处理程序会选择牺牲一个内存（DRAM）中的页，本例中选择的是内存中的PP3页的VP4，接下来内核就从虚拟内存中拷贝VP3到内存中的PP3，并使得PTE3指向内存中的PP3，形成如下：

vp4就成了牺牲页（不知道为什么想到了小三上位了 hhhhh
页面交换:虚拟存储器出现早于高速缓存，按照习惯的说法块被叫做页。从虚拟内存到物理内存传送页的活动就叫做页面交换。

3.5、分配页面&&又是局部性拯救了我们

比如某个页面所指向地址为NULL，将这个地址指向磁盘某处，那么这就叫分配页面。此时虚拟页从未分配状态变为未缓存。

虚拟存储器工作的相当好，主要归功于老朋友局部性(locality)

尽管从头到尾的活动页面数量大于物理存储器大小。

但是在局部内，程序往往在一个较小的活动页面集合工作

这个集合叫做工作集(working set)或者叫常驻集(resident set)
- 初始载入开销比较大。
程序有良好的时间局部性，虚拟存储器都工作的相当好。
如果程序实在很烂，或者物理空间很小，工作集大于物理存储器大小。这种状态叫颠簸(thrashing).
- 这时，页面不断换进换出。性能十分低。

4、虚拟存储器作为内存管理的工具

实际上，操作系统为每个进程提供一个独立的页表。

因此，VM简化了链接和加载,代码和数据共享,以及应用程序的存储器分配。

简化链接
- 独立的空间地址意味着每个进程的存储器映像使用相同的格式。
  - 文本节总是从0x08048000(32位)处或0x400000(64位)处开始。
  - 然后是数据，bss节,栈。
- 一致性极大简化了链接器的设计和实现。
简化加载
- 加载器可以从不实际拷贝任何数据从磁盘到存储器。
- 基本都是虚拟存储系统完成。
将一组连续的虚拟页映射到任意一个文件中的任意位置的表示法称作存储器映射。Unix提供一个称为mmap的系统调用，允许程序自己做存储器映射。在9.8详细讲解。
简化共享
- 独立地址空间为操作系统提供了一个管理用户进程和操作系统自身之间的一致共享机制.
- 例子
  - 操作相同的操作系统内核代码
  - C标准库的printf.
- 因此操作系统需要将不同进程的适当的虚拟页映射到相同的物理页面。
  - 多个进程共享这部分代码的一个拷贝。
  - 而不是每个进程都要加载单独的内核和C标准库的拷贝。
简化存储器分配.
- 即虚拟页连续(虚拟页还是单独的)，物理页可以不连续。使得分配更加容易。
简化保护.
- 我们可以通过为PTE添加额外的标识位提供对存储器的保护。

通过新添加的三个标识位：SUP：内核or用户；READ:

5、地址翻译，加入高速缓存，多级页表，案例研究：Intel CoreI7，这些东西太肝了，总结不出来，Orz,希望感兴趣的能自己认真看下去，因为这里如果要详讲只能把书扫描放这了，东西太多，所以直接科普一下Linux虚拟存储系统

一个单独的Linux系统进程虚拟存储主要分为：内核虚拟存储器和进程虚拟存储器。我们主要来讲一下内核虚拟存储器：由下往上是内核的代码和数据结构，是每个进程共享的数据结构和代码；再往上是一组连续的虚拟页面映射到相应的物理页面的物理存储器，大小同主存一样大，提供很方便访问物理页面的任何位置。最后是每个进程不同的是页表、task（mm）、内核栈等。

5.1、虚拟存储器区域

区域就是我们通常说的段，text、data、bss都是不同的区域，这些区域是被分为连续的片。每个虚拟页面都在不同的段中，不属于某个段的虚拟页面是不存在的，且不能被使用。我们来看看内核中的一个task数据结构（mm）：task_struct是位于内核虚拟存储器中对于每个进程的都不同的内核数据结构，包含运行该进程所需要的基本信息（PID、可执行文件名称、程序计数器等）。这个结构中有一个mm字段，指向的是mm_struct中的pgd和mmap，其中pgd是一级页表的基地址，mmap指向的是一个vm_area_structs的链表，每个该链表中的一个元素描述的是当前虚拟地址空间的一个段（text、data、bss等），当内核运行该进程的时候CR3寄存器就被放入了pgd。

5.2、Linux缺页异常处理

我们将了解一些存储器区域划分的基础知识，并且介绍说mmap指向的是一个链表，这个链表中的每个元素都指向该进程的相应的段，其中vm_strat是段开始的地方，vm_end是段结束的地方。1> 访问地址是否合法：缺页处理程序只需要将这个地址A与vm_area_struct链表中的每个元素的start和end数据比较，如果都没有的话，表示该地址不在相应的段中。就是一个段错误。2> 保护异常：vm_area_struct中的vm_prot结构是包含了所有页面的读写权限，所以当对只有读权限的文本内容写入数据的时候，就会引发保护异常。

3> 最后，正常缺页。也就是相应的页面不在物理内存的时候，缺页程序就会锁定一个牺牲页面，将它的内容与实际需要的内容交换过来，当缺页程序返回的时候就可以正常的访问了。

6、存储器映射

存储器映射是通过将磁盘上的一个文件与虚拟存储器中的一个区域关联起来的过程。

6.1、共享对象

一个对象被映射到虚拟存储器的一个区域，这个区域要么是共享对象，要么是私有对象。如果一个进程A将一个共享对象映射X到了它的虚拟存储器中，那么对于也把这个共享对象X映射了的其他进程而言，进程A对共享对象X的任何读写操作都是可见的。下图是进程1和进程2映射了共享区域的图例：

私有区域：即使是私有区域在物理存储器上也是同一个区域，如下图进程1和进程2所映射的私有对象在物理存储器上只是一份拷贝。

每个对象都有唯一的一个文件名，在进程1的虚拟存储器中已经完成了私有对象到存储器的映射，进程2如果要映射这个区域只需要将页表条目指向已经映射好的物理存储器位置就行了。如上图所示，进程1和2将一个私有对象映射到了物理存储器的一个区域并共享这个私有对象。这个对象会被标记为只读，当其中一个进程2确实需要写这个区域的时候，就会引发一个保护故障，内核会在物理存储器中创建这个私有对象的一个拷贝，称为写时拷贝，更新页面条目使得进程1指向这个新的条目。然后把老对象修改为可写权限。这样当保护故障程序返回的时候，CPU重新执行写的操作就不会出错了。

6.2、再看fork函数

当当前进程调用fork函数的时候，内核为新进程创建各种数据结构，并分配PID。为了给新进程创建一个虚拟存储器，它创建的当前进程的mm_struct、区域结构和页表的一个拷贝，内核为两个进程的每个页表标记为只读，并将诶个区域标记为私有的写时拷贝。这样当fork函数返回的时候，新进程的虚拟存储器和当前进程的虚拟存储器刚好相同。任何一个进程进行写操作的时候，才会创建新的页面。

7、动态内存分配（what is malloc?

动态存储器分配指的是在程序运行的时候分配额外的存储空间，分配器维护着虚拟存储器中的堆实现这种分配。

堆是紧跟着.bss段，并向上增长，内核维护着一个brk指针，指向堆的顶部。任何一个堆中的块要么是已分配的要么是空闲的。分配的方式分为两种：显式和隐式，我们接下来主要讲一下显示分配和实现一个分配器的基础知识，隐式分配指的其实是分配器回收空间，这个在分配器基础知识中有所讲解，就不再另外提出了：

7.1、显式分配：程序调用malloc和free函数

经常直到我们的程序运行的时候，我们才知道某些数据结构的大小。这时候就必须显式的分配相应的存储空间。如下图所示：

使用malloc函数以具体的输入内容分配相应大小的存储空间，函数原型如下：

如果想要初始化存储器为0，可以使用calloc函数。想要改变已分配的大小可以使用realloc函数
释放是通过调用free函数来实现的：

ptr是指向一个已分配空间的起始位置

7.2、demo

（a）请求一个4字大小的块，malloc将分配好的空间的首地址返回给p1；
（b）请求一个5字大小的块，由于使用的双字对其，所以填充了一个空闲块；
（c）请求一个6字大小的块，返回给p3；
（d）释放p2，调用后p2仍然指向原来的位置；
（e）请求一个2字大小的块，在已经释放的p2处优先分配，然后返回指针p4

7.3、配器基础知识

分配器的目标主要是找到吞吐量和利用率的契合点，那么为什么需要隐式的分配，因为碎片的产生会降低存储空间的利用率
碎片：内部和外部
1>内部碎片：我们上面讲到的（b）的情况，分配了一个额外的空闲块，实现双字对其；

2>外部碎片：(e)中如果请求7字大小的块，即使存储空间有这么大，还是不行

当然，还有许多问题要思考，诸如：空闲块如何组织、如何分配新的块、怎么分割和合并块，这些技术都要求我们提供一种新的数据结构

(更分配器更高级的骚操作以及垃圾回收，请自行看书吧)