计算机系统的主存被组织成一个由M个连续的字节大小的单元组成的数组,每字节都有一个唯一的 物理地址(PA) 。
物理地址空间对应于系统中物理内存的M个字节。
一个包含N=2 n 个地址的虚拟地址空间叫做一个N位地址空间,现代系统通常支持32或64位虚拟地址空间。
允许每个数据对象有多个独立的地址,每个地址选自一个不同的地址空间。
主存中的每字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。
一个系统中的进程与其他进程共享CPU和主存,为了更加有效的管理内存并减少出错,现代系统提出了一种对主存的抽象概念,叫做 虚拟内存(VM) 。它为每个进程提供了一个大的、一致的和私有的地址空间。虚拟内存提供三个重要功能:
虚拟内存系统通过把虚拟内存分割为虚拟页大小的块,每个虚拟页大小为P=2 p 字节。
物理内存也被分割为物理页,大小也为P字节,物理页也称为页帧。
任意时刻,虚拟页面的集合分为三个相交的子集:
SRAM缓存表示位于主存和CPU之间的L1、L2、L3高速缓存。
DRAM缓存表示虚拟内存系统的缓存,它在主存中缓存虚拟页,利用DRAM可以缓存来自通常更大的虚拟地址空间的页面。
虚拟页往往很大,DRAM缓存是全相联的,即任何虚拟页可以放在任何的物理页中。DRAM缓存总是使用写回,而不是直写。操作系统对DRAM缓存使用了复杂精密的替换算法。
页表(page table) 将虚拟页映射到物理页,是页表条目(Page Table Entry)的数组。
虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。
PTE通常有一个有效位和n位地址字段,如果设置了有效位那么地址字段表示DRAM中相应物理页的起始地址;如果没有设置有效位,空地址则表示该虚拟页还没被分配,否则这个地址字段表示该虚拟页在磁盘上的起始位置。
DRAM缓存不命中称为 缺页 ,缺页异常调用内核中的缺页异常处理程序。
该程序选择一个牺牲页,如果牺牲页被修改了就会被复制回磁盘,然后修改页表条目并把缺的页从磁盘复制到内存中。
异常处理程序返回时,会重新启动导致缺页的指令,该指令会把导致缺页的虚拟地址重发给地址翻译硬件,此时页命中。
操作系统分配一个虚拟页面时,在磁盘上创建空间并更新相应的页表条目,使它指向磁盘上这个新创建的空间。
虚拟内存工作良好主要归功于 局部性 :局部性原则保证了在任意时刻,程序趋向于在一个较小的活动页面集合上工作,这个集合叫做工作集。初始开销将工作集页面调度到内存中,接下来对工作集的引用将导致页命中。
工作集大小超过物理内存大小时,程序可能会发生抖动,这时页面不断换进换出。
操作系统为每个进程提供了一个独立的页表 ,因而也就是一个独立的虚拟地址空间。
提供独立的地址空间使得区分不同进程的私有内存变得容易。
通过在PTE上添加一些额外的许可位来控制对一个虚拟页面内容的访问,如果一条指令违反了许可条件,CPU会触发一个一般保护故障,将控制传递给内核中的一个异常处理程序:
注:地址翻译部分省略了大量的细节,尤其是时序相关的细节
地址翻译是一个N元素的虚拟地址空间中的元素和一个M元素的物理地址空间中元素之间的映射。
CPU中有一个页表基址寄存器(Page Table Base Register,PTBR)指向当前进程的页表。
n位的虚拟地址包括一个p位的虚拟页面偏移量和一个(n-p)位的虚拟页号,物理页号由虚拟页号得到,物理页偏移等于虚拟页偏移。
页面命中完全由硬件处理,处理缺页请求要求硬件和操作系统内核协作完成。
大多数系统是 使用物理地址访问SRAM高速缓存 的,地址翻译是发生在高速缓存查找之前的。
为了减少从内存读取页表的开销,内存处理单元包括了一个关于页表条目的小缓存,称为 翻译后备缓冲器(TLB) 。
TLB是一个小的、虚拟寻址的缓存,其中每一行保存着一个由单个页表条目组成的块,TLB常有高度的相联度。
那么内存管理单元只有在TLB不命中时,才会从L1缓存中取出相应的页表条目。
64位系统中页表往往很大,用来压缩页表的常用方法是使用 层次结构的页表 。
比如,一级页表中的每个PTE映射虚拟地址空间中的一个4MB的片,二级页表中的每个PTE映射一个4KB的页。
Core i7处理器中的CR3控制寄存器指向第一级页表的起始位置,CR3的值是每个进程上下文的一部分。
如果片i中的每个页面都未分配,那么一级PTE i就为空。如果片i中至少有一个片是分配的,那么一级PTE i指向一个二级页表的基址。
Linux将虚拟内存组织成一些区域的集合,一个区域就是已经存在的已分配虚拟内存的连续片。代码段、数据段、堆、共享库段以及用户栈都是不同的区域。允许虚拟地址空间有间隙。
内核为系统中的每个进程维护一个单独的任务结构task_struct
,任务结构中的元素包含或指向内核运行该进程所需要的所有信息(如PID、指向用户栈的指针,可执行目标文件的名字以及程序计数器)。
任务结构中的一个条目指向mm_struct
,它描述了虚拟内存的当前状态。
mm_struct
中的pgd
字段指向第一级页表的基址,mmap
指向一个vm_area_struct
(区域结构)的链表。
每个vm_area_struct
描述了当前虚拟地址空间的一个区域,一个具体区域的结构包含以下字段:
vm_start
:指向这个区域的起始处 vm_end
:指向这个区域的结束处 vm_prot
:描述区域内包含的所有页的读写许可权限 vm_flags
:描述这个区域内的页面是与其他进程共享的还是私有的(还有一些其他描述信息) vm_next
:指向链表中下一个区域结构 内存映射 :将一个虚拟内存区域与一个磁盘上的对象关联起来,以初始化这个虚拟内存区域的内容。
虚拟内存区域可以映射到两种类型的对象中的一种:
一个虚拟页面被初始化后,在由内核维护的交换文件之间换来换去,交换文件也叫交换空间。任何时刻,交换空间都限制着当前运行进程能够分配的虚拟页面的总数。
一个对象可以被映射到虚拟内存的一个区域,要么作为共享对象,要么作为私有对象。映射到共享对象的虚拟内存区域叫做共享区域,映射到私有对象的虚拟内存区域叫做私有区域。
被当前进程调用时,内核为新进程创建各种数据结构,并分配给它一个唯一的PID,新进程创建的虚拟内存是当前进程的原样副本,并将两个进程中的每个页面都标记为只读,并将两个进程中的每个区域结构标记为私有的写时复制。当两个进程中的任一个后来进行写操作时,写时复制机制就会创建新页面,为每个进程保持了私有地址空间。
execve("a.out", NULL, NULL)
Linux进程可以使用mmap
函数创建新的虚拟内存区域,并将对象映射到这些区域内。
#include <unistd.h> #include <sys/mman.h> // start:开始地址,通常定义为NULL // fd:文件描述符 // length:文件描述符指定对象的连续对象片大小,单位字节 // offset:文件描述符指定对象的开始处偏移量,单位字节 // prot:描述新映射的虚拟内存区域的访问权限位 // flags:描述被映射对象类型的位组成,表示私有写时复制对象/匿名对象/共享对象 // 成功时返回指向映射区域的指针,出错返回MAP_FAILED(-1) void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset); // 创建一个新的包含size字节的只读、私有、请求二进制零的虚拟内存区域,调用成功时bufp包含新区域的地址 bufp = Mmap(NULL, size, PROT_READ, MAP_PRIVATE|MAP_ANON, 0, 0); // 删除从虚拟地址start开始的length字节组成的区域,引用已删除区域会导致段错误 // 成功返回0,出错返回-1 int munmap(void *start, size_t length);
mmap
和munmap
可以创建和删除虚拟内存区域,但是C程序员使用 动态内存分配器 更方便且可移植。
动态内存分配器维护着一个进程的虚拟内存区域,称为 堆(heap) 。对于每个进程,内核维护着一个变量brk,指向堆的顶部。分配器将堆视为一组大小不同的块的集合,每个块是一个连续的虚拟内存片(chunk),要么是已分配的,要么是空闲的。空闲块保持空闲,直到显式地被应用所分配。已分配块保持已分配状态,直到它被释放。
malloc
/free
,C++程序的new
/delete
C程序通过调用malloc
函数从堆中分配块。
malloc
函数返回一个指针,指向大小至少size字节的内存块,这个块为可能包含在块内的任何数据对象类型做对齐。
32位模式中,malloc
返回的块地址总是8的倍数;64位模式中,malloc
返回的地址总是16的倍数。
malloc
不初始化 它返回的内存,calloc
函数基于malloc
,它将分配的内存初始化为0。
想要改变一个以前分配块的大小,可以使用realloc
函数。
#include <stdlib.h> // 成功时返回已分配块的指针,出错返回NULL void *malloc(size_t size);
sbrk
函数将内核的brk指针增加incr来扩展和收缩堆。成功时返回brk的旧值,否则返回-1并将errno设为ENOMEM。
incr为0时返回brk的当前值,incr的值也可以是负的。
#include <unistd.h> void *sbrk(intptr_t incr);
C程序通过free
函数释放已分配的块。
#include <stdlib.h> // ptr参数必须指向一个从malloc、calloc或realloc获得的已分配块起始位置 // 如果ptr参数不满足上述条件,行为就是未定义的,而且不会告诉应用出现错误 void free(void *ptr);
虚拟内存是一个有限的空间 ,系统中所有进程分配的虚拟内存的全部数量受磁盘上交换空间的数量限制。
显式分配器的编写者试图实现吞吐率(每个单位时间完成的请求数)最大化和内存利用率最大化。
造成堆利用率低的主要原因是 碎片现象 ,产生碎片时系统有未使用的内存但不能满足分配请求,分配器通常试图维持少量的大空闲块,而不是维持大量的小空闲块:
GNU malloc包采用的是 分离适配 :
每个空闲链表和一个大小类相关联,并被组织成某种类型的显式或隐式链表。
每个链表包含潜在大小不同的块,这些块的大小是大小类的成员。
分配一个块时,对适当的空闲链表做首次适配,如果找到则分割它并将剩余部分插入到适当的空闲链表中。
如果找不到合适的块,就搜索下一个更大的大小类的空闲链表。
释放块时,执行合并操作,并将结果放置到相应的空闲链表中。
分配器找到匹配空闲块后,可以选择使用整个空闲块,也可能将这个块分割为分配块和空闲块两部分。
如果分配器找不到合适的空闲块,可以选择合并相邻空闲块来创建更大的空闲块,如果仍然不能满足请求,分配器会调用sbrk
函数向内核请求额外的堆内存。
快速的分配器通常使用某种形式的推迟合并
垃圾收集器是一种动态内存分配器,它自动释放程序不再需要的已分配块。支持垃圾收集的系统中,应用显式分配堆,但从不显式地释放它们。
垃圾收集器将内存视为一张有向可达图,该图地节点被分成一组根节点和一组堆节点,每个堆节点对应于堆中的一个已分配块。有向边p → q意味块p中的某个位置指向块q中的某个位置。根节点不在堆中,它们包含指向堆中的指针,根结点可以是寄存器、栈里的变量或是虚拟内存中读写数据区域内的全局变量。当存在一条从任意根结点出发并到达p的有向路径时,则p是可达的。任何时刻, 不可达节点对应于垃圾 ,通过释放不可达节点且将它们返回给空闲链表来定期回收它们。
Java的垃圾收集器能够维护可达图的一种精确表示,因此可以回收所有垃圾;
C/C++的收集器通常不能维持可达图的精确表示,每个可达块可以被正确标记,但一些不可达节点却可能被错误标记为可达。C程序的垃圾收集器必须是保守的,根本原因是 C程序不会用任何类型信息标记内存位置 ,如int或者float这样的标量可能会伪装成指针。
scanf
错误,误把scanf("%d",&val)
写为scanf("%d",val)
calloc
gets(buf)
,应该使用fgets
sizeof(int *)
不一定等于sizeof(int)
A[n]
*size--
是指针size减一,(*size)--
是减少size指针指向的整数值 free
函数释放了的堆块中的数据,这种错误可能会在未来表现出来 a
--
123456789
更改id为3
--
test
更改id为2
--
commentor
伪造名称???
--
hhh
伪造名称???
--
yayay