什么叫电脑虚拟内存(虚拟内存是干什么用的)-东辰安华生活网

　　什么叫电脑虚拟内存(虚拟内存是干什么用的)，新营销网红网本栏目通过数据整理汇集了什么叫电脑虚拟内存(虚拟内存是干什么用的)相关信息，下面一起看看。

　　系统中的进程与其他进程共享CPU和主存。首先，更多的进程需要更多的内存。其次，内存容易被破坏，比如进程A不小心写了进程b使用的内存，为了更有效的管理内存，少出错，系统提供了一个抽象的主存概念，叫做虚拟内存。虚拟内存是硬件异常、硬件地址转换、主存、磁盘文件和内核之间的完美交互，为每个进程提供了一个大的、一致的、私有的地址空间。虚拟内存提供了三种重要的功能：

　　使用主存效率更高：DRAM作为虚拟地址空间的缓存的一部分，简化内存管理：每个进程都有一个统一的线性地址空间来隔离地址空间：进程之间不会互相影响；用户不能访问内核信息和代码。

　　 1地址空间物理地址通常用于“简单”的嵌入式微控制器(汽车、电梯等。)，而且内存管理也比较简单。然而，现代计算机，包括笔记本电脑和智能手机等其他智能设备，需要更复杂的内存管理机制，因此虚拟地址至关重要。这是计算机科学中最伟大的想法之一。

　　 2虚拟内存作为缓存工具从概念上讲，虚拟内存是存储在磁盘上的N个连续字节的数组。磁盘上阵列的内容缓存在物理内存(DRAM缓存)中，每个缓存块称为一个页面，如下图所示：

　　在任何时候，虚拟页面都可以分为三个部分：

　　未分配：未被VM系统分配或创建的页面，不占用任何磁盘空间。已缓存：已缓存在主存中的已分配页面。未缓存：尚未缓存在物理内存中的已分配页面。

　　见上图：0和3不分配，1、4和6缓存在物理内存，2、5和7分配但不缓存在主存。

　　 2.1 DRAM高速缓存的组织类似于以前的高速缓存。快存取速度作为慢存取速度缓存，磁盘数据尽可能用比磁盘快10倍的DRAM缓存在DRAM中(同理DRAM比SRAM慢10倍，SRAM也可以作为缓存)，所以要尽可能从DRAM中获取数据。这需要：

　　更大的页面大小：通常为4KB，Linux的巨大页面是2M到1G的完全关联：每个虚拟页面可以放在任何物理页面中，映射函数非常复杂，与缓存不同，无法在硬件中实现。替换算法是昂贵的，并且通常使用回写机制来代替直写机制。

　　在直写：命中后，它更新缓存并同时写入内存。回写：直到需要替换这个缓存时才写入内存(需要脏位来表示缓存中的数据是否与内存中的数据相同，因为内存中对应地址的数据可能在某个点已经被更新，重复写入会导致原始数据丢失)

　　 2.2页表页表是一个数组，其元素PTE，页表项(PTE)，将虚拟页映射到物理页。PTE由1个有效位和n个地址字段组成。在DRAM中，每个进程都有自己的页表，如下所示：

　　 2.2.1页面命中。被访问的虚拟地址的页面在DRAM缓存中，这被称为页面命中。命中时可以直接访问，因为DRAM中有对应的数据。如果未命中，DRAM中没有相应的数据，需要从磁盘复制到DRAM中，具体为：

　　 MMU触发页面错误异常，将模式升级到内核模式。调用软件Page fault Handler Page fault Handler在DRAM中选择需要替换的页面，将数据从磁盘复制到DRAM中。复制的等待时间称为请求分页，以重新执行访问指令，这将是页面命中。

　　 2.2.2处理页面错误

　　在磁盘和内存之间传输页面的活动称为交换或页面调度。从磁盘到DRAM的页入(或页入)和从DRAM的页出(或页出)。这种等到最后时刻(即未命中发生的时刻)的策略被称为按需页面调度。所有现代操作系统都使用按需页面调度。

　　 2.2.3页面故障完成。页面错误处理器执行返回中断指令(iret ),并返回：

　　类似ret指令，但是恢复特权级别会返回导致错误的指令。

　　 2.2.4分配页面

　　只有发生页面错误时，才会将数据复制到内存中，即按需页面调度。

　　 2.2.5局部性原则虚拟内存看起来效率很低，但是由于局部性原则，虚拟内存是非常高效的。在任何时候，程序都倾向于访问一组称为工作集的活动虚拟页面。本地性越好，程序的工作集就越小。

　　工作集大小内存大小，工作集大小性能好的进程的内存大小，多个进程同时运行，页面不断交换(复制)进或出，也叫抖动。

　　 3作为内存管理工具，每个进程都有自己的虚拟地址空间。这些地址空间可以看作是简单的线性空间(但它们实际上可能是有间隔的，分散在物理内存中)。映射函数通过物理内存分散地址，好的映射函数可以提高局部性。具体的映射过程如下图所示：

　　作为内存管理工具：

　　简化内存分配：每个虚拟页面都可以映射到任何物理页面。虚拟页面可以很容易地在不同时间存在的不同物理页面上共享：每个进程都有自己的私有代码、数据、堆和栈，这些都不与其他进程共享。它提供了操作系统在进程和系统之间共享代码和数据的机制，将不同进程的虚拟页面映射到同一个物理页面(也就是上面PP 6的情况，只读)来简化链接和加载：每个程序都有相同的抽象和相似的虚拟地址空间，代码、数据和堆段从Execve开始分配虚拟页面给。文本和。数据段并创建标记为无效的页表条目(pte );根据虚拟内存系统的需要。大调音阶的第7音

　　xt和.data段逐页复制

　　4 作为内存保护工具

　　任何现代计算机系统必须为操作系统提供手段控制对内存系统的访问，不应允许进程修改只读代码段，也不许读或修改任何内核中的代码和数据结构。不许读或改其他进程私有地址，不许改任何与其他进程共享的虚拟页面，除非所有共享者都显式允许这么做（通过调用明确的进程间通信系统调用）

　　使用权限位扩展PTEs，高位是表示权限的位，MMU 检查这些位进行权限控制（读、写、执行），如下图所示：

　　5 地址翻译5.1 地址翻译符号

　　地址空间可分为：

　　线性地址空间：连续非负整数地址的有序，{0, 1, 2, 3 }虚拟地址空间：N=2^n的虚拟地址，{0, 1, 2, 3, , N-1}物理地址空间：M=2^m的物理地址，{0, 1, 2, 3, , M-1}

　　地址翻译：MAP: V → P U {}

　　MAP(a) = a’：若虚拟地址a中的数据在P中的物理地址a 上MAP(a) = {}：若虚拟地址a中的数据不在物理内存中（无效或存储在磁盘）

　　开始之前先来了解以下参数：

　　N=2^n：虚拟地址空间中的地址数量M=2^m：物理地址空间中的地址数量P=2^p：页的大小（字节）

　　虚拟地址(VA, Virtual Address)中的元素：

　　TLBI：TLB索引TLBT：TLB标记(tag)VPO：虚拟页偏移量VPN：虚拟页号

　　物理地址(PA, physical address)中的元素：

　　PPO：物理页偏移（与 VPO 的值相同）PPN：物理页号CO：缓存偏移字节CI：缓存索引CT：缓存标签

　　5.2 用页表进行地址翻译

　　具体的访问过程为：

　　通过虚拟地址找到页表(page table)中对应的条目检查有效位(valid bit)，是否需要触发页错误(page fault)根据页表中的物理页编号(physical page number)找到内存中对应地址把实际地址和虚拟页偏移(virtual page offset)拼接即为最终的物理地址

　　这里又分两种情况：Page Hit 和 Page Fault

　　5.2.1 page hit

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

　　5.2.2 page fault

　　处理器生成一个虚拟地址，并把它传给MMUMMU生成PTE地址，并从高速缓存/主存请求得到它高速缓存/主存向MMU返回PTE有效位为零，所以MMU触发页故障异常，传递CPU控制到系统内核中缺页异常处理程序处理程序寻找被置换页(如果页脏，则将其换出到磁盘)处理程序从磁盘找到对应页并载入内存/缓存并更新内存中的PTE处理程序返回到原始进程，重启出错指令，CPU将引起缺页的虚拟地址重新发给MMU，由于已缓存在主存故会命中

　　5.3 结合虚拟内存和高速缓存

　　在既有虚拟内存又有SRAM高速缓存的系统中，是使用虚拟地址还是物理地址访问SRAM高速缓存的讨论有很多，但大多数系统用物理寻址，这样多个进程共享虚拟页和存储的值，无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。虽然缓存已经很快了，但还能更快，主要思路是地址翻译发生在高速缓存查找之前，直接在 MMU和内存之间加上L1缓存，于是就有了另外一种设计，如图：

　　页表条目(PTE)像任何其他内存中的数据一样缓存在L1中，PTE可能被其他数据驱逐；PTE命中仍然需要一个小的L1延迟，解决办法是使用Translation Lookaside Buffer(TLB)。TLB可以认为是页表在处理芯片上的缓存，是MMU中的小型集关联硬件缓存，将虚拟页号映射到物理页号，大多数页表条目位于L1高速缓存，但被称为TLB的页表条目的片上高速缓存，包含少量页的完整页表条目，通常回消除访问L1上的页表条目的开销。MMU使用虚拟地址的VPN部分位访问TLB：

　　如图是TLB命中和不命中的两种情况：

　　若TLB不命中时，MMU必须从L1缓存中取出相应的PTE，新取出的PTE存放在TLB中可能覆盖已存在的条目（这里未画出L1缓存，下面Interl Core i7部分画出cpu中的L1缓存和MMU的TLB）

　　这里顺便复习下前面的缓存结构：

　　这里 VPN + VPO 就是虚拟地址，同样分成三部分，分别用于匹配标签、确定，若TLB命中，直接返回对应页表项(PTE)，否则，就要从缓存/内存中获取，并更新 TLB 的对应。幸好不命中很少发生

　　5.4 多级页表

　　因为虚拟地址的位数比物理内存的位数要大得多，所以保存页表项(PTE) 所需要的空间也是一个问题。例如：

　　假设每个页的大小是 4KB（2的12次方），每个地址有 48 位，一条 PTE 记录有 8 个字节，那么要全部保存下来，需要的大小是：2^48×2^-12×2^3=2^39bytes = 512G所以采用多层页表，第一层的页表中的条目指向第二层的页表，一个一个索引下去，最终寻找具体的物理地址，如图是二级页表：

　　K级页表翻译过程如下：

　　5.5 地址翻译实例

　　来看一个简单的例子，我们的内存系统设定如下：

　　虚拟地址14 位物理地址12 位页大小 64 字节

　　简单内存系统的TLB的配置为：

　　存储 16 条记录4个

　　简单内存系统页表：

　　简单内存系统缓存：

　　16 行，每个块 4 个字节物理地址直接映射（即 16 个）

　　虚拟地址：0x03D4，在TLB中找到index为3的set，且其tag为3的PPN为0D，加上前面的虚拟地址的VPO即为最终的物理地址

　　得到物理地址，在缓存中找到idx为，tag为0D，且CO为0，则值为36

　　虚拟地址为0x0020，虽然TLB中去找到编号为0的set且tag为0的缓存，但为0，所以TLB Miss了，从页表中找到缓存PPN为2，则物理地址为0x0A20

　　接下来找到idx为8的缓存，但tag不匹配，故未命中缓存，只能重新读取

　　5.6 Intel Core i7内存系统

　　5.6.1 Intel Core i7 内存翻译

　　5.6.2 Core i7 1-3层页表项

　　5.6.3 Core i7 4级页表项

　　5.6.4 加速技巧

　　将1）MMU将地址翻译成物理地址2）将物理地址传送到L1高速缓存。这两步骤部分重叠，故也加速对L1高速缓存的访问。

　　在虚拟地址和物理地址中确定CI的位当地址翻译时，可以将索引存入缓存通常用TLB，PPN位（CT位）可很快得到虚拟索引，物理标记仔细调整缓存大小

　　6 Linux进程中的虚拟地址

　　Linux为每个进程维护单独的虚拟地址空间，包括内核虚拟内存和进程虚拟内存。前者某些区域被映射到所有进程共享的物理页面，如每个进程共享内核的代码和全局数据结构。有趣的是，Linux也将一组连续的虚拟页面（大小等于系统中DRAM的总量）映射到相应的一组连续的物理页面，为内核提供便利的访问物理内存中特定位置。

　　6.1 Linux将虚拟内存组织为“区域”

　　Linux将虚拟内存组织称一些区域（也叫段）的，区域就是已经存在着的（已分配的）虚拟内存的连续片，这些页以某种方式相关联。如代码段、数据段、堆、共享库段以及用户栈都市不同区域，每个存在的虚拟页都抱存在某个区域中，而不属于某个区域的虚拟页是不存在的，且不能被进程引用。区域的概念很重要，因为它允许虚拟地址空间有间隙，内核不用记录那些不存在的虚拟页，而这样的页也不占用内存、磁盘或内核本身中的任何资源。

　　6.2 Linux页异常处理

　　缺页异常步骤：

　　虚拟地址A是否和法：缺页处理程序搜索区域结构的链表，把A和每个区域结构中的vm_start和vm_end做比较，若该指令不合法，则缺页处理程序就出发一个段错误，从而终止该进程，对应下图中的1内存访问是否合法：进程是否有读、写或执行这个区域内页面的权限，如是不是因为运行在用户模式的进程试图从内核虚拟内存中读取字造成，若访问不合法则触发缺页异常，从而终止该进程，对应图中的2合法虚拟地址进行合法操作：按调度算法选择一个页，若该页被修改过，将其交换出去换入新页并更新页表。缺页处理程序返回时，CPU重新启动引起缺页的指令，该指令再次发A到MMU，这次就能正常翻译A

　　6.3 内存映射

　　将虚拟内存的areas与磁盘对象关联并初始化的机制叫内存映射。area可通过磁盘的普通文件（如可执行文件），初始化来自文件的一部分为页，或者匿名文件，首次错误将分配一个写满0的物理页，一旦页被写（脏）就跟其他页一样。无论哪种情况，一旦虚拟页面被初始化了，它就在由内核维护的专门的交换文件间换来换取，任何时刻，交换空间都限制着当前运行着的进程能分配的虚拟页面的总数。

　　6.3.1 共享对象

　　若虚拟内存系统可集成到传统的文件系统中，就能提供一种简单而高效的把程序和数据加载到内存中的。

　　很多进程都有同样的只读代码区域，且许多程序需访问只读运行时库代码的相同副本，如每个C程序都需标准C库的printf函数，若每个进程都在主存中保持这些代码的副本，就极端浪费。

　　一个对象可被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象（非共享）。

　　多个进程可共享相同的对象，虚拟地址可以有差异，但差异必须是页大小的倍数

　　6.3.2 私有的写时复制对象

　　对于每个映射私有对象的进程，相应私有区域的页表条目都被标记为只读，且该区域被标记为私有的写时复制。一旦写入则触发保护错误，处理程序在主存中创建试图写私有的写时复制区域中的一个页面该页面的信服本，更新页表条目指向该新副本，再恢复该页面可写权限。指令在处理程序返回时重新执行，拷贝尽可能被推迟。

　　再看fork函数，当被当前进程调用时，创建当前进程的mm_struct、区域结构和页表的原样副本。将两个进程中的每个页面都标记为只读，并将两进程中每个区域结构都标记为私有的写时复制。fork返回时，新进程虚拟内存和调用fork时存在的虚拟内存相同，当两进程中任一个后来进行写操作，写时复制机制就创建新页面，因此也就为每个进程保持私有地址空间的抽象概念。

　　再看execve假设执行execve( a.out ,NULL,NULL)该函数在当前进程中加载并运行包含在可执行目标文件a.out中的程序，用a.out替代当前程序，需以下步骤：

　　删除已存在的用户区域：删除当前进程虚拟地址的用户部分中的已存在的区域结构映射私有区域：为新程序代码、数据、bss和栈区域常见新的区域结构，所有这些新区域都是私有的、写时复制的映射共享区域：若a.out程序与共享对象链接，先动态链接，再映射到用户虚拟地址空间中的共享区域内设置程序计数器：设置当前进程上下文中的程序计数器，使之指向代码区域入口点

　　6.3.3 找到可共享的页

　　内核相同页归并：

　　系统扫描所有物理内存，寻找重复页，找到则归并为单个页，标记为写时拷贝在2009年的Linux内核实现，仅限于标记为可能的页，特别是处理器运行许多虚拟机时特别有用

　　6.3.4 用户模式的内存映射

　　函数void *mmap(void *start, int len,int prot, int flags, int fd, int offset)，从文件描述副fd指定的文件偏移量offset，从start地址（可能为0）开始映射len字节，prot表示权限（PROT_READ、PROT_WRITE、 PROT_EXEC），flags表示映射权限（MAP_ANON、 MAP_PRIVATE、MAP_SHARED等），返回映射区域开始的指针（可能不是start）

　　6.3.5 mmap的使用

　　使用分页机制将大文件读入内存，共享数据结构，当调用带MAP_SHARED的标签时，多进程可访问相同内存区域，很危险。基于文件的数据结构例如数据库，将prot设置为PROT_READ和PROT_WRITE，当解除映射时，文件通过写入被更新，通过文件加载/更新/写回文件实现。

　　6.3.6 用mmap实现attack lab

　　当机器堆栈不能执行时，如何通过代码注入进行攻击，解决是使用mmap分配内存并标记为可执行，转移堆栈到该区域，执行攻击代码，恢复原来堆栈，移除映射区域。

　　7 动态内存分配

　　程序员通过动态内存分配器（如 malloc）让程序在运行时得到虚拟内存，因为程序经常直到实际运行时才知道某些数据结构大小。动态内存分配器管理一个虚拟内存区域，称为堆(heap)。

　　分配器以块为单位来维护堆，可分配或释放。有两种类型的分配器：

　　显式分配器：应用分配并且回收空间（C 语言中的 malloc 和 free）隐式分配器：应用只负责分配，但是不负责回收（Java 中的new和垃圾收集）

　　7.1 相关函数

　　malloc：失败返回空指针并设置errno=ENOMEM，成功返回指向至少请求字节大小的内存块的指针free：将参数p指向的块返回到可用内存池，p必须来自先前调用的malloc、calloc、realloccalloc：将已分配的块初始化为0的malloc版本realloc：改变先前分配的快的大小 rk：分配器内部使用，用于增加或缩小堆

　　先来看看一个简单的使用 malloc 和 free 的例子

　　#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 i++)p[i] = i;/* Return allocated block to the heap */free(p);}

　　为了讲述方便，我们做如下假设：

　　内存地址按照字来编码每个字的大小和整型一致

　　例如：

　　可以用任意的顺序发送 malloc 和 free 请求，但free 请求必须作用与已被分配的 block。

　　显式分配器的限制：

　　不能控制已分配块的数量和大小必须立即响应 malloc 请求（不能缓存或者给请求重新排序）必须在未分配的内存中分配不同的块需要对齐（32 位中 8 byte，64 位中 16 byte）只能操作和修改未分配的内存不能移动已分配的块，不允许压缩，为什么？

　　7.2 性能指标

　　假设给定 malloc 和 free 的请求的序列：R0,R1, ,Rk, ,Rn-1R0,R1, ,Rk, ,Rn-1目标是尽可能提高吞吐量以及内存利用率（注意，这两个目标常常是冲突的）

　　吞吐量是在单位时间内完成的请求数量。假设在 10 秒中之内进行了 5000 次 malloc 和 5000 次 free 调用，那么吞吐量是 1000 operations/second

　　另外一个目标是 Peak Memory Utilization，就是最大的内存利用率。其次最小化开销，定义总负载Pk表示请求Rk完成时的当前已分配的载荷之和，当前堆大小Hk（假定Hk是单调非递减），则K+1次请求的开销Ok = Hk / (maxi≤k P i ) – 1.0

　　7.3 内存碎片

　　影响内存利用率的主要因素就是『内存碎片』，分为内部碎片和外部碎片两种。

　　内部碎片

　　内部碎片指的是存储的数据(payload)小于块大小，就会因对齐和维护堆所需的数据结构或明确的决策（如返回大块满足小的请求）的缘故而出现无法利用的空间，例如：

　　内部碎片只依赖于之前的请求的具体模式

　　外部碎片

　　内存中有足够的空间，但是空间不连续，所以成为了碎片，取决于未来请求的模式

　　实现细节

　　如何实现高效的内存分配算法？在具体实现之前，需要考虑以下问题：

　　给定一个指针，如何知道需要释放多少内存？如何记录未分配的块？当分配的结构小于所在的空闲块时，如何处理多余的空间?有多个区域满足条件，如何选择？如何重用已经释放的块？

　　如何实现回收

　　标准：在块开头记录块的长度（包括块头），每个分配的块需额外的字节

　　具体这部分书中提到了四种：

　　隐式列表 Implicit List：在首部记录长度，链接所有块显式列表 Explicit List：用指针的空闲块的显式列表分离的空闲列表 Segregated Free List：不同大小的不同链表按大小对块排序 Blocks Sorted by Size：使用平衡树（如红黑树），每个空闲块都有指针，长度作为键

　　8 跟踪自由块8.1 隐式空闲列表

　　每个块都记录大小和分配状态，只需一个字节，当块对齐时，一些低阶地址位总是0，与其存储始终为0的位，不如将其作为已分配/空闲标志。当读取Size字节时，必须屏蔽该位

　　8.1.1 数据结构

　　8.1.2 头访问

　　8.1.3 遍历链表

　　8.1.4 找到一个空闲块

　　如何确定哪部分空间合适，有三种：

　　First Fit: 每次都从头进行搜索，找到第一个合适的块，线性查找Next Fit: 每次从上次搜索结束的位置继续搜索，避免重复搜索没有帮助的块，速度较快，但可能会有更多碎片，一些研究表明碎片化教糟糕Best Fit: 每次遍历列表，找到剩余字节最少最合适的块，碎片较少，通常可提高内存利用率，但是速度最慢，仍是贪婪算法，没最优保证

　　8.1.5 分配空闲块

　　由于已分配空间可能小于空闲空间，可以分割块

　　8.1.6 释放块

　　最简单的实现方式是清除“已分配”的标记，但可能导致错误的碎片化

　　8.1.7 合并

　　若下一个/前一个块是空闲的，则连接合并

　　8.1.8 双向合并

　　在前面的基础上，在空闲块的“底部”记录块的大小，允许反向遍历列表，但需额外空间，边界标签（Knuth73）

　　8.1.9 通过footers实现

　　8.1.10 常数时间合并

　　总共四种情况，这里以第一种为例：

　　注意：对于头和尾需要加上 dummy footer ，标记为已分配，防止在释放第一块和最后一块时意外合并

　　8.1.11 高层malloc/free代码

　　malloc/free不常用，因为线性时间分配，多用于特殊目的应用

　　const size_t dsize = 2*sizeof(word_t);void *mm_malloc(size_t size){size_t asize = round_up(size + dsize, dsize);block_t *block = find_fit(asize);if (block == NULL)return NULL;size_t block_size = get_size(block);write_header(block, block_size, true);write_footer(block, block_size, true);split_block(block, asize);return header_to_payload(block);}void mm_free(void *bp){block_t *block = payload_to_header(bp);size_t size = get_size(block);write_header(block, size, false);write_footer(block, size, false);coalesce_block(block);}8.1.12 边界标签缺点

　　导致内部碎片，footer标签能被优化，未使用一位代表已分配/未分配，除次之外使用多一位表示前一块是否分配

　　也有四种情况，这里以第一种情况为例：

　　8.2 显式空闲列表

　　维护空闲列表块，而不是所有块，下一个/上一个空闲块可能在任何地方，所以需存储前向/后向指针，而不仅是块大小，合并仍需边界标签，根据记忆顺序找到相邻的块

　　8.2.1 释放块

　　在空闲列表的什么地方放新释放的块？

　　无序：LIFO（Last in First out）、FIFO（First in First out），简单但花费时间，研究表明碎片化比按地址序更糟地址序：插入空闲块，以便空闲块总按地址顺序排列，需搜索

　　同样对于释放内存块也有4种情况，这里以第四种情况做简要说明：

　　8.2.2 一些实现的技巧建议

　　使用循环双向链表，但数据结构支持多种，要么保持自由指针固定要么作为搜索列表移动

　　8.2.3 显式空闲列表总结

　　分配是空闲块数量的线性时间，而不是所有块。由于需在列表中插入和取出块，因此分配和自由更复杂。但需要额外的链接空间

　　8.3 分割列表分配器

　　每个大小块类都有自己的空闲列表

　　8.3.1 分割分配器

　　给定一个自由列表数组，每个都是一定大小的类，分配一个大小为n的块，搜索大小为m n的块，若找到合适的块，分割块并放碎片在适当的列表，若没有块被发现，尝试下个更大的种类。重复直到块被找到。用 rk从系统请求额外的堆内存，从该新内存分配n个字节的块，将剩余的块作为一个单独的空闲块放在适当大小的类中。

　　8.3.2 分割分配器优点

　　更高的吞吐量：种类大小的2次幂的对数时间vs线性时间更好的内存利用率：对隔离的自由列表的First-fit搜索近似对整个堆的最佳搜索；极端情况是给每个块一个自己的大小的类相当于best-fit

　　8.4 内存陷阱

　　关于内存的使用需要注意避免以下问题：

　　解引用错误指针读取未初始化的内存覆盖内存引用不存在的变量多次释放同一块引用已释放的块释放块失败

　　8.4.1 解引用错误指针

　　没有引用对应的地址，少了

　　int val;...scanf("%d", val);8.4.2 读取未初始化的内存

　　不能假设堆中的数据会自动初始化为 0，如：

　　/* return y = Ax */int *matvec(int **A, int *x) {int *y = malloc(N * sizeof(int));int i, j;for (i = 0; i i++)for (j = 0; j j++)y[i] += A[i][j] * x[j];return y;}8.4.3 覆盖内存

　　第一种是分配错误的大小，下面的例子中，一开始不能用 sizeof(int)，因为指针的长度不一定和 int 一样。

　　int **p;p = malloc(N * sizeof(int));for (i = 0; i i++)p[i] = malloc(M * sizeof(int));

　　第二个问题是超出分配的空间，下面代码的 for 循环中，因为使用了 =，会写入到其他位置

　　int **p;p = malloc(N * sizeof (int *));for (i = 0; i i++)p[i] = malloc(M * sizeof(int));

　　第三种是因为没有检查字符串的长度，超出部分就写到其他地方去了（经典的缓冲区溢出攻击也是利用相同的机制）

　　char s[8];int i;gets(s); /* reads "123456789" from stdin */

　　第四种是没有正确理解指针的大小以及对应的操作，应该使用 sizeof(int *)

　　int *search(int *p, int val) {while (*p *p != null)p += sizeof(int);return p;}

　　第五种是引用了指针，而不是其指向的对象，下面的例子中，*size 一句因为的优先级比较高，所以实际上是对指针进行了操作，正确的应该是 (*size)

　　int *BinheapDelete(int **binheap, int *size) {int *packet;packet = binheap[0];binheap[0] = binheap[*size - 1];*size--;Heapify(binheap, *size, 0);return (packet);}8.4.4 引用不存在的变量

　　下面的情况中，没有注意到局部变量会在函数返回的时候失效（所以对应的指针也会无效），这是传引用和返回引用需要注意的，传值的话则不用担心

　　int *foo() {int val;return val;}8.4.5 多次释放同一块内存

　　这个不用多说，不能重复搞两次

　　x = malloc(N * sizeof(int));// manipulate x free(x);y = malloc(M * sizeof(int));// manipulate y free(x);8.4.6 引用已释放的块

　　同样是很明显的错误，不要犯

　　x = malloc(N * sizeof(int));// manipulate x free(x);// ....y = malloc(M * sizeof(int));for (i = 0; i i++)y[i] = x[i]++;8.4.7 内存泄漏

　　用完没有释放，就是内存泄露啦

　　foo() {int *x = malloc(N * sizeof(int));// ...return ;}

　　或者只释放了数据结构的一部分：

　　struct list {int val;};foo() {struct list *head = malloc(sizeof(struct list));head- val = 0;head- next = NULL;//...free(head);return;}9 垃圾回收

　　垃圾回收自动回收堆分配的存储，程序不必显式地释放内存，这种机制在许多动态语言中都有实现：Python, Ruby, Java, Perl, ML, Lisp, Mathematica。C 和 C++ 中也有变种，但是注意，不可能回收所有垃圾。

　　如何知道什么东西才是垃圾？只要没有任何指针指向的地方，不管有没有用，因为都不可能被使用，当然可以直接清理掉。不过这其实是需要一些前提条件的：

　　可以知道哪里是指针，哪里不是指针每个指针都指向 block 的开头指针不能被隐藏(by coercing them to an int, and then back again)

　　相关算法如下：

　　Mark-and-sweep collection (McCarthy, 1960)Reference counting (Collins, 1960)Copying collection (Minsky, 1963)Generational Collectors(Lieberman and Hewitt, 1983)

　　9.1 Mark Sweep垃圾收集器

　　可在malloc/free包之上构建，用malloc分配直到空间耗尽。当空间不足时，在每个块的头用额外的标记位标记，标记阶段标记出根节点所有可达的和已分配的后继，在每个可达的块上设置标记位，后面的清除释放每个未被标记的已分配块

　　9.2 简单实现

　　应用：

　　new(n)：返回指向清除所有位置的新块的指针read(b,i)：读块b在i处的值到寄存器wreite(b,i,v)：写v到块b的i处

　　每个块都有一个头：块b的头的地址是b[-1]，在不同的收集器中用于不同目的垃圾收集器使用的指令：is_ptr(p)检测p是否是指针，length(b)返回块b的长，不包括头，get_roots()返回所有的roots

　　10 总结

　　首先介绍虚拟内存等方面的知识，具体来说：

　　从程序员角度看虚拟内存：

　　每个进程有自己的私有线性地址空间不能被其他进程破坏

　　从系统角度看虚拟内存：

　　通过缓存虚拟内存页更有效地使用内存（局部性原理）简化内存管理和编程，提供方便的位检查权限，简化内存保护