CSAPP笔记之虚拟存储器

Catalogue
  1. 1. 物理和虚拟寻址
    1. 1.1. 1. 物理地址
    2. 1.2. 2. 虚拟地址
  2. 2. 虚拟内存的三个角色
    1. 2.1. 作为缓存工具
      1. 2.1.1. 页表
    2. 2.2. 作为内存管理工具
    3. 2.3. 作为内存保护工具
  3. 3. 地址翻译
    1. 3.1. 利用TLB加速地址翻译
    2. 3.2. 多级页表
  4. 4. 动态内存分配
    1. 4.1. 性能指标
      1. 4.1.1. 内部碎片
      2. 4.1.2. 外部碎片
    2. 4.2. 垃圾回收
      1. 4.2.1. 垃圾收集器的基本知识
    3. 4.3. C程序中常见的与存储器有关的错误
  5. 5. 参考资料

下面是对《深入理解计算机系统》以及虚拟内存与动态内存分配博客文章的学习笔记

物理和虚拟寻址

1. 物理地址

计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组,每字节都有唯一的物理地址,第一个字节的地址为0,接下来的字节地址为1,再下一个为2,依此类推。CPU访问存储器的最自然的方式就是使用物理地址,我们把这种方式称为物理寻址

物理寻址

当CPU执行这条加载指令时,它会生成一个有效的物理地址,通过存储器总线,把它传递给主存,主存取出从物理地址4处开始的4字节的字,将将它返回给CPU,CPU会将它存放到一个寄存器里。

物理地址一般应用在简单的嵌入式微控制器中(汽车、电梯、电子相框等),因为应用的范围有严格的限制,不需要在内存管理中引入过多的复杂度。

2. 虚拟地址

现代处理器使用一种称为虚拟寻址的寻址方式,如下图

虚拟寻址

使用虚拟地址时,CPU通过生成一个虚拟地址来访问主存,这个虚拟地址在被送到存储器之前先转换成适当的物理地址,将一个虚拟地址转换为物理地址的任务叫做地址翻译,这个任务就是靠MMU内存管理单元实现的。

虚拟内存的三个角色

虚拟存储器提供了三个重要的能力:

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

作为缓存工具

概念上讲,虚拟内存就是存储在磁盘上的N个连续字节的数组,这个数组的部分内容,会缓存在DRAM中,在DRAM中的每个缓存块称为页(page),类似地,物理存储器被分割成物理页(页帧),页和页帧大小一致。

虚拟内存与物理内存

在任意时刻,虚拟页面的集合都分为三个不相交的子集:

  • 未分配的: VM系统还未分配(或创建的)的页。未分配的块没有任何数据和他们相关联,因此也就不占用任何磁盘空间
  • 缓存的: 当前缓存在物理存储器中的已分配页
  • 未缓存的:没有缓存在物理存储器中的已分配页

页表

同任何缓存一样,虚拟存储器必须有某种方法来判定一个虚拟页是否存放在DRAM中的某个地方,如果是,系统还必须确定这个虚拟页存放在哪个物理页中,如果不命中,系统必须判断这个虚拟页存放在磁盘的哪个位置,在物理存储器中选择一个牺牲页,并将虚拟页从磁盘拷到DRAM中,替换这个牺牲页。

这个机制就是通过页表(page table),每个页表实际上是一个数组,数组中的每个元素都称为页表项(PTE,page table entry),每个页表项负责把虚拟页映射到物理页上,在DRAM中,每个进程都有自己的页表,具体如下:

页表

注意:页表是存放在物理存储器中的,每次地址翻译硬件一个虚拟地址转换为物理地址时都会读取页表

通常我们可以假设每个PTE是由一个有效位(valid bit)和一个n位地址字段组成的,有效位表明了该虚拟页当前是否被缓存在DRAM中

  • 如果设置了有效位,那么地址字段就表示DRAM中相应的物理页的起始位置,这个物理页中缓存了该虚拟页。

  • 如果没有设置有效位,那么一个空地址表示这个虚拟页还未被分配

在一个页表中查询,就会遇到两种情况,一种是命中(page Hit),另一种则是未命中 (page Fault)

  • 命中的时候,DRAM有对应的物理页,可以直接访问
  • 不命中的时候,DRAM中并没有对应的数据,所以需要执行一系列的操作(从磁盘复制到DRAM中),具体为:
    • 触发Page fault,也就是一个缺页异常
    • 缺页异常调用内核的缺页异常处理程序,选择DRAM中需要被置换出的page,并将数据从磁盘复制到DRAMz中
    • 重新启动导致缺页的指令,这时候就会命中

作为内存管理工具

每个进程都有自己的虚拟地址空间,这样一来,对于进程来说,它们看到的就是简单的线性空间(但实际上在物理内存中可能是间隔,支离破碎的),具体的映射过程如下:

内存管理

在内存分配中没有太多限制,每个虚拟页都可以被映射到任何的物理页上。这样也带来一个好处,如果两个进程间有共享的数据,那么直接指向同一个物理页即可

虚拟内存带来的另一个好处就是可以简化链接和载入的结构(因为有了统一的抽象,不需要纠结细节)

  • 独立的地址空间允许每个进程的存储器映像使用相同的基本格式

作为内存保护工具

页表中的每个条目的高位部分是表示权限的位,MMU 可以通过检查这些位来进行权限控制(读、写、执行),如下图所示:

内存保护工具

每个PTE中已经添加了三个许可证:

  • SUP位表示进程是否必须运行在内核模式才能访问该页;运行在内核模式中的进程可以访问任何页面,但是运行在用户模式中的进程只允许访问那些SUP为0的页面
  • READ位和WRITE位控制对页面的读和写访问

地址翻译

形式上说,地址翻译是一个N元素和虚拟地址空间(VAS)中的元素和一个M元素的物理地址空间(PAS)中元素之间的映射:

  • N=2^n: N表示虚拟地址空间中的地址数量
  • M=2^m: M表示物理地址空间中的地址数量

虚拟地址中的元素:

  • TLBI: TLB 的索引值
  • TLBT: TLB 的标签(tag)
  • VPO: 虚拟页偏移量
  • VPN: 虚拟页编号

物理地址中的元素:

  • PPO: 物理页偏移量
  • PPN: 物理页编号

下面看一个具体的例子来说明如何进行地址翻译:

地址翻译

具体的访问过程为:

  • 通过虚拟地址找到页表(page table)中对应的条目
  • 检查有效位(valid bit),是否需要触发页错误(page fault)
  • 然后根据页表中的物理页编号找到内存中的对应地址
  • 最后把虚拟页偏移和前面的实际地址拼起来,就是最终的物理地址

在上述第二步中需要检查有效位,有效位如果等于0,那么页面就不在存储器中(也就是缺页),所以这里有两种情况:Page Hit 和Page Fault,先来看看Page Hit的情况:

页面命中

  • 处理器生成一个虚拟地址,并把它传送给MMU
  • MMU生成PTE地址,并从高速缓存/主存请求得到它
  • 高速缓存/主存向MMU返回PTE
  • MMU构造物理地址,并把它传送给高速缓存/主存
  • 高速缓存/主存返回所请求的数据字给处理器

Page Fault就要复杂一点,第一次触发页错误会把页面载入内存/缓存,然后再以Page Hit的机制得到数据

缺页

这里有 7 步,前面和 Page Hit 是一致的,先把虚拟地址发给 MMU 进行检查,然后发现没有对应的页,于是触发异常,异常处理器会负责从磁盘中找到对应页面并与缓存/内存中的页进行置换,置换完成后再访问同一地址,就可以按照 Page Hit 的方式来访问了。

利用TLB加速地址翻译

每次CPU产生一个虚拟地址,MMU就必须查阅一个PTE,以便将虚拟地址翻译为物理地址,在最糟糕的情况下,这又会要求从存储器取一次数据,代价是几十到几百个周期。许多系统都试图消除这样的开销,它们在MMU中包括了一个关于PTE的小的缓存,称为翻译后备缓冲器(Translation Lookaside Buffer,TLB)

TLB是一个小的、虚拟寻址的缓存,其中每一行都保存着一个由单个PTE组成的块。

使用TLB的流程是:

  • CPU生成一个虚拟地址
  • 如果TLB中有对应的PTE,那么MMU从TLB中取出对应的PTE
  • MMU将虚拟地址翻译成物理地址,并且将它发送到主存
  • 主存将所请求到的数据字返回给CPU

TLB命中

下面是TLB未命中的情况:

TLB未命中

多级页表

如果我们有一个32位的地址空间,4KB的页面和一个4字节的PTE,那么即使应用所引用的只是虚拟地址空间中很小的一部分,也总是需要一个4MB的页表驻留在存储器中。对于地址空间为64位的,情况更复杂。

所以我们需要一种多级页表的方法,第一层的页表中的条目指向第二层的页表,一个一个索引下去,最终寻找到具体的物理地址,整个翻译过程如下:

多级页表

动态内存分配

程序员通过动态内存分配(例如malloc)来让程序在运行时得到虚拟内存,动态内存分配器维护着一个进程的虚拟存储器区域,称之为堆(heap)。

分配器将堆视为一组不同大小的块(block)的集合来维护,每个块就是一个连续的虚拟存储器片,要么是已分配的,要么是空闲的。已分配的块显式地保留为供应用程序使用,空闲块是可用来分配的,空闲块保持空闲,直到它显式地被应用所分配。

分配器有两种类型的分配器:

  • 显式分配器:应用分配并且回收空间(C语言中的malloc和free)
  • 隐式分配器(又叫做垃圾收集器):应用只负责分配,但是不负责回收,由垃圾收集器去回收内存空间(比如Java语言中的垃圾收集)

一个简单的使用 malloc 和 free 的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <stdio.h>
#include <stdlib.h>
void foo(int n) {
int i, *p;

/* Allocate a block of n ints */
p = (int *) malloc(n * sizeof(int));
if (p == NULL) {
perror("malloc");
exit(0);
}

/* Initialize allocated block */
for (i=0; i<n; i++)
p[i] = i;
/* Return allocated block to the heap */
free(p);
}

分配器有如下的限制:

  • 不能控制已分配块的数量和大小
  • 必须立即响应malloc请求 (不能缓存或者给请求重新排序)
  • 必须在未分配的内存中分配
  • 不同的块需要对齐(32位中的8byte,64位中16位byte)
  • 只能操作和修改未分配的内存
  • 不能移动已分配的块

性能指标

在以上分配器的限制之下,分配器的编写者试图实现吞吐率最大化和存储器使用率最大化,而这两个性能指标往往是相互冲突的。

吞吐率定义为每个单位时间里完成的请求数,例如,如果一个分配器在1秒钟内完成500个分配请求和500个释放请求,那么它的吞吐率就是每秒1000次操作。

另一个目标就是最大的内存利用率,影响内存利用率的主要因素就是【内存碎片】,内存碎片又分为内部碎片和外部碎片两种。

内部碎片

内部碎片指的是对于给定的块,如果需要存储的数据(payload)小于块大小,就会因为对齐和维护所需的数据结构的缘故而出现无法利用的空间,例如:

内部碎片

外部碎片

外部碎片指的是内存中没有足够的连续空间,如下图所示,内存中有足够的空间,但是空间不连续,所以成为了碎片:

碎片

垃圾回收

垃圾回收器是一种动态存储分配器,它自动释放程序不再需要的已分配块。这些块就称为垃圾。自动回收堆存储的过程叫做垃圾回收

垃圾收集器的基本知识

垃圾收集器将存储器视为一张有向可达图,其形式如下图

可达图

该图的节点被分成一组根节点和一组堆节点。每个堆节点对应于堆中的一个已分配块。当对于堆中的任何一个节点,如果从任何一个根节点出发都能到达,那么我们可以说该节点是可达的,那么该节点占据的内存块还是有用的,能够被再次利用。 在任何时候,不可达节点就是垃圾,不能被应用程序再次利用,垃圾回收器会回收掉该节点,清除没有用的对象。垃圾回收器的作用就是一直维护这张可达图,直到应用程序不再运行。(类似Java虚拟机中的可达性分析算法)

C程序中常见的与存储器有关的错误

C程序中常见的与存储器有关的错误:

  • 间接引用坏指针
  • 读未初始化的存储器
  • 允许栈缓冲区溢出
  • 错位错误
  • 引用指针,而不是它所指向的对象
  • 引用不存在的变量
  • 引用空闲堆中的数据
  • 引起存储器泄漏

参考资料

Bagikan Komentar