操作系统的物理内存： —— 常说的 “内存条”
数据从磁盘中加载到内存后，才能被CPU访问。【操作系统的代码和数据、应用程序的代码和数据】

最早期的计算机操作系统：
1）硬件：物理内存容量小
2）软件： 1）单个应用程序 + （简单）操作系统 2）直接面对物理内存编程 3）各自使用内存的另一半

早起的计算机操作系统

CPU 访问内存的最自然的方式就是使用物理地址 —— 物理寻址

多重编程时代
1）多用户多程序：计算机很昂贵，多人同时使用（远程连接）
2）分时复用CPU 资源：保存复用寄存器很快
3）分时复用物理内存资源：将全部内容写到磁盘里面开销太高
4）同时使用、各占一部分物理内存：没有安全性（隔离性）

QR：如何让OS与不同的应用程序都高效又安全地使用物理内存资源？

IBM 360 的内存隔离：protection key
protection key 机制：
1）内存被划分为一个个大小为2KB的内存块(block)
2）每个内存块有一个4-bit的key，保存在寄存器中
3）1MB内存需要512个不保存key的寄存器，占512-Byte 。内存变大怎么办？需要改CPU以增加key寄存器...
4）每个进程对应一个key： CPU 用另一个专门的寄存器，保存当前运行进程的key ，不同进程的key不同。
5）一个进程访问一块内存时： CPU检查进程的key与内存的key是否匹配。

protection key禁止的挑战
1）应用加载与隔离：不同应用被加载到不同的物理地址段，不同应用的key不同，以保证隔离
2）问题：（1）同一个二进制文件，程序-1加载到0000-1000地址段，程序-2加载到5000-6000地址段（2）JMP42 ，程序-1能执行，程序-2会出错
3）解决方法：（1）代码中所有地址在加载过程中都需要增加一个偏移量，eg：改为：“JMP 5042” （2）新的问题：《1》加载过程中变得更慢《2》如何在代码中定位所有的地址？ eg：MOV REG1 , 42 ，其中的42是地址还是数据？

上面都是使用物理地址的情况：
使用物理地址的缺点：
1）物理地址对应用是可知的，导致：
《1》一个应用会因其他应用的加载而收到影响
《2》一个应用可通过自身的内存地址，猜测出其他应用的加载位置。

2）是否可以让应用看不见物理地址？
《1》不用关系其他进程，不受其他进程的影响
《2》看不见其他进程的信息，更强的隔离能力。

——> 从而引申出来 虚拟内存

虚拟内存 —— 透明、效率、保护

虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互，它为每个进程提供了一个大的、一致的私有的地址空间。

提供了三个重要的能力：
1）看成了磁盘的高速缓存,只保存活动区域【主存和磁盘数据来回传输数据】《效率》
2）每个进程提供了一致的地址空间【独占整个内存】，从而简化了内存管理【不再看到物理地址，加载时不再为地址增加一个偏移量】—— 虚拟地址会被硬件"自动地"翻译成物理地址《透明》
3）它保护了每个进程的地址空间不被其他进程破坏。《保护》

以虚拟内存抽象为核心的内存管理： —— `也就是使用了虚拟内存之后，计算机有关的变化`

1）CPU：支持虚拟内存功能、增加了虚拟地址空间
2）操作系统：配置并使用虚拟内存机制
3）所有软件(包括OS) : 均使用虚拟地址，无法直接访问物理地址

QR：既然虚拟内存高度封装了里面：沉默地、自动地工作，不需要应用程序的任何干涉 程序员为什么还需要理解它呢？也就是理解虚拟内存的必要性：
1）虚拟内存是核心：虚拟内存遍布计算机系统的所有层面，在硬件异常、汇编器、连接器、加载器、共享对象、文件、进程的设计中扮演重要角色。
2）虚拟内存是强大的：提供了可以创建、销毁内存碎片，将内存片映射到磁盘文件的某个部分，以及与其他进程共享内存。
3）虚拟内存是危险的：每次应用程序引用一个变量、简介引用一个指针，或者调用一个诸如malloc 这样的动态分配程序时，它就会和虚拟内存发生交互。如果使用不当，应用将遇到复杂危险的与内存有关的错误。 eg：一个带有错误指针的应用程序可以立即崩溃于“段错误”，“保护错误”....

QR：两个角度： 1）虚拟内存是如何工作的（2）应用程序如何使用和管理虚拟内存

1、虚拟地址：

1> 虚拟地址概览

使用虚拟地址来寻址 —— 虚拟寻址
使用虚拟寻址， CPU通过生成一个虚拟地址(virtual Adddress， VA ) 来访问主存，这个虚拟地址在被送到内存之前转换成适当的物理地址。
将一个虚拟地址转换为物理地址的任务叫做 地址翻译【address translation】

和异常处理一样，地址翻译需要CPU硬件和操作系统之间的紧密合作。 CPU芯片上叫做内存管理单元[memory management Unit， MUU]的专用硬件，利用存放在主存中的查询表【页表？】来动态翻译虚拟地址，该表的内存由操作系统管理。

翻译规则：居于虚拟内存采用的组织机制，包括：分段机制和分页机制

2> 地址空间 & 地址生成

一个非负整数地址的有序集合 {0,1,2,...}

地址空间中的帧数是连续的 —— 线性地址空间(linear address space)

在一个带有虚拟内存的系统中， CPU从一个有N= 2^n 个地址的地址空间中生成虚拟地址，这个地址空间称为 虚拟地址空间（vritula address space）

一个地址空间的大小是由表示最大地址所需要的位数来描述的。 eg：一个包含N=2^n 个地址空间叫做一个n为地址空间，现在常见的是： 32、64位虚拟地址空间(virtual address space)

一个系统还有一个物理地址空间[physical address space] ，对应于系统中物理内存的M个字节，M 不要求是2的幂。

地址空间：区分了数据对象(字节) 和它们的属性(地址)。
允许每个数据对象有多个独立的地址，其中每个地址都选自一个不同的地址空间。 —— 虚拟内存的基本思想

主存中的每个字节都有一个选自虚拟地址空间的虚拟地址和一个选自物理地址空间的物理地址。

3> 虚拟内存作为缓存的工具

1）虚拟内存每个字节都有一个唯一的虚拟地址，作为到数据索引。
2）磁盘（较低层）上的数据被分割成块 —— 传输单元
3）VM系统通过将虚拟内存分割为虚拟页[VP] 的大小固定的块来处理这个问题。每个虚拟页的大小为P=2^p字节。
4）类似，物理内存被分割为物理页[PP]，大小也是P字节(物理页也被称为页帧【page frame, PF】)。

虚拟页面的集合都分为3个不想交的子集：
1）未分配的： VM系统还未分配（或者创建）的页。未分配的快没有任何数据和它们相关联，因此也就不占用任何磁盘空间
2）缓存的：当前已缓存在物理内存中的额已分配页
3）未缓存的：未缓存的物理内存中的已分配页。

示例图

0、3 未分配， 1、4、6已被缓存在物理中， 2、5、7 已被分配。

3.1> DRAM 缓存组织结构

经常使用术语SRAM缓存来表示位于CPU和主存之间的L1,L2, L3 高速缓存，并且用术语DRAM 缓存来表示虚拟内存系统的缓存，它在主存中缓存虚拟页。

在存储层次结构中，DRAM缓存的位置对它的组织结构有很大的影响。
DRAM比SRAM要慢大约10倍，而磁盘要比DRAM慢大约100 000 倍。所以， DRAM缓存中的不命中比起SRAM缓存中要昂贵很多，这是因为DRAM缓存不命中要由磁盘来服务，而 SRAM缓存不命中通常是由基于DRAM的主存来服务的。从磁盘的一个扇区读取第一个字节的时间开销比起读这个扇区中连续的字节要慢大约100 000 倍。 DRAM 缓存的组织结构完全是由巨大的不命中开销驱动。
不命中，替换，这个触发的代价还是很高的，所以，这里需要更加复杂精密的替换算法。

3.2> 页表

分页机制：
1> 更细粒度的内存管理
1）物理内存被划分成连续的、等长的物理页
2）虚拟页和物理页的页长相等
3）任意虚拟页可以映射到任意物理页
4）大大缓解分段机制中常见的外部碎片

虚拟地址分为：虚拟页号 + 页内偏移

主流CPU均支持分页机制，可替换分段机制。

页表：分页机制的核心数据结构
页表包含多个页表项，存储虚拟页到物理页的映射

判断逻辑： 
if (虚拟页是否缓存在DRAM中的某个地方) {
  系统必须确定这个虚拟页存放在哪个物理页中
}
else{
   查找虚拟页存放在磁盘的哪个位置
  物理内存中选择一个牺牲页，并将虚拟页从磁盘复制到DRAM中，替换这个牺牲页
}

这些判断过程：是由软硬件联合提供的，包括操作系统软件、MMU（内存管理单元）中的地址翻译硬件和一个存放在物理内存中叫做页表(page table )的数据结构，页表将虚拟页映射到物理页。每次地址翻译硬件见搞一个虚拟地址转换为物理地址时，都会读取页表。操作系统负责维护页表的内容。以及在磁盘与DRAM之间来回传送页。

展示了一个页表的解百纳组织结构

1）页表就是一个页表条目的数组。【页表条目:page table entry , PTE 】
2）虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个PTE。
3）假设每个PTE是由一个有效位(valid bit) 和一个n位地址字段组成的。有效位表明了该虚拟页当前是否被缓存在DRAM中。

if (valid bit == 1) {
  表示在DRAM中相应物理页的起始位置，这个物理页中缓存了该虚拟页。
}
else { 
  if (address == NULL) {  //空地址
     空地址表示未被分配
  }
  else {
    这个地址指向虚拟页面在磁盘的起始位置。 
  }
}

4）8个虚拟页和4个物理的系统页表。四个虚拟页(VP1 , VP2 , VP4, VP7) 当前被缓存在DRAM中，两个页(VP0 和VP5 )还没有分配，剩下的VP3,VP6 已经被分配了，但是当前还未被缓存。

DRAM 缓存是全相联的，所以任意物理页都可以包含人任意虚拟页。

3.3> 页命中

当CPU想要读包含在VP2中的虚拟内存的一个字时会发生什么？
《页命中》因为有效位是1，所以，MMU将虚拟地址作为一个索引来定位PTE2，并从物理内存中读取到它。

3.4> 缺页 —— DRAM缓存不命中

VP3 不命中的情况下；

1）VP3并未缓存在DRAM中，地址翻译硬件从内存中读取PTE3，从有效位推断VP3未被缓存，并且触发一个缺页异常。缺页异常调用内核中的缺页异常处理程序，该程序会选择一个牺牲页，在这个例子中PP3中的VP4. 如果VP4已经被修改了，那么就会将它复制到磁盘。无论哪种情况，内核都会修改VP4的页表条目。
2）内核从磁盘复制VP3到内存中的pp3，更新PTE3，随后返回。当异常处理程序返回时，它会重新启动缺页的指令，该指令会把导致缺页的虚拟地址重新发送到地址翻译硬件。但是现在， VP3 已经缓存在主存中了，那么页命中也能够由地址翻译硬件正常处理了。

交换/页面调度：在磁盘和内存之间传送页的活动。页从磁盘换入（或者页面调入）DRAM和从DRAM换出(或者页面调出)磁盘。一直等待，知道最后时刻，也就是当有不命中发生时，才换入页面的这种策略称为 按需页面调度[demand paging] 。其他方法,eg：尝试着预测不命中，在页面实际被引入之前换入页面，然而，所以现代系统都使用的是按需页面调度的方式。

3.5> 分配页面

当操作系统分配一个新的虚拟内存页时对我们示例也白哦的影响： eg：调用malloc的结果。在这个示例中，VP5的分配过程是在磁盘上创建空间并更新PTE5，使它指向磁盘上这个新创建的页面。

3.6> 局部性

换页处罚性太大，虚拟内存工作得相当好，—— 局部性（locallity）

1> 因为程序趋向于一个较小的活动页面集合上工作。【这个集合叫做工作集（working set）】；在初始开销，也就是将工作集页面调到内存之后，接下来对这个工作集的引用将导致命中，而不会产生额外的磁盘流量。
2> 如果工作集的大小超出了物理内存的大小，那么程序将产生一种不幸的状态，叫做抖动(thrashing)，这时页面将不断地换进换出。虽然，通常虚拟内存是有效的，但是如果一个程序性能慢得像是爬一样，那么久应该考虑是不是发生抖动了。 —— 如何去判断是不是抖动了？

4> 虚拟内存作为内存管理的工具

*) 假设有一个单独的页表，将一个虚拟地址空间映射到物理地址空间。实际上，操作系统为每个进程提供了一个独立的页表。因为也就是一个独立的虚拟地址空间。看上图的逻辑映射。
*)按需调度和独立的虚拟地址空间结合。 VM 简化了链接和加载、代码和数据共享以及应用程序的内存分配。

简化链接：独立的地址空间允许每个进程的聂村映射使用相同的基本格式，而不管代码和数据实际存放在物理内存何处。允许连接器生成完全链接的可执行文件，这些可执行文件是独立于物理内存中代码和数据的最终位置。
简化加载：虚拟内存还使得容易想内存中加载可执行文件和共享对象文件。
eg:要把目标文件中.text 和.data 节加载一个新创建的的进程中, linux 加载器为代码和数据端分配虚拟页，把它们标志为无效的, 将页表条目执行目标文件中适当的位置。【有趣的是：加载器从不从磁盘到内存实际复制任何数据。在每个叶初次被引用时，要么是CP取指令时引用的，要么是一条正在执行的指令引用一个内存位置时应用的，虚拟内存系统会按照需要自动调入数据页】

将一组连续的虚拟也映射到任意一个文件中的任意位置的表示方法称作：内存映射（memory mapping） . linux提供一个mmap的系统调用，允许应用程序自己做内存映射。

简化共享：独立地址空间为操作系统提供了一个管理用户进程和操作系统自身的共享的一致机制。在共享情况下，操作系统创建也白哦，将相应的虚拟页映射到不连续的物理页面。
【在一些情况下，还是需要进程共享代码和数据。eg：每个进程必须调用相同的操作系统内核代码，而每个C程序都会调用C标准库中的程序，eg：printf。操作系统通过 将不同进程中适当的虚拟页面映射到到相同的物理页面，从而安排多个进程共享这部分代码的一个副本，而不是在每个进程中都包含单独的内核和C标准库的副本】
简化内存分配：虚拟内存向用户进程提供了一个简单的分配内存的机制。当一个运行在用户进程中的程序要求额外的堆空间时(eg: 调用malloc的结果)，操作系统分配一个适当数字(例如：k)个连续的虚拟内存页面，并且将它们映射到物理内存中任意位置的k个任意的物理页面。由于页表工作方式，操作系统没有必要分配k个连续的物理内存页面。 页面可以随机分散在物理内存中。

5> 虚拟内存作为内存保护的工具

操作系统必须提供收端控制对内存系统的访问。

提供独立的地址空间使得区分不同进程的私有内存变得容易。但是，地址翻译机制可以以一种自然的方式扩展提供更好的访问控制。 因为每次CPU生成一个地址时，地址翻译硬件就会读一个PTE，所以通过PTE上天啊及一些额外的许可位来控制对一个虚拟页面内容的访问事发呢简单

SUP 表示进程是否运必须运行在内核(超级用户)模式下才能够访问该页。运行在内核模式中的进程可以访问任何页面，但是运行在用户模式中的进程只允许访问这些SUP为0的页面。 超级用户权限
READ ：是否可读
WRITE : 是否可写

违反这些保护故障： linux报错： “段错误， segmentation fault”

6> 地址翻译【省略的时序】

了解硬件在支持虚拟内存中的角色。

地址翻译是一个N元素的虚拟地址空间(VAS) 中的元素和一个M元素的物理地址空间(PAS)中元素之间的映射：
MAP:VAS ---> PAS ∪ Ø
(1)MAP(A) 中的， A' 如果虚拟地址A出的数据在APS的物理地址A'处
(2)Ø 如果虚拟地址A处的数据不在物理内存中

PTBR 页表基址寄存器(page table base register) 指向当前页表。
n位的虚拟地址包含两个部分： (1)一个是p位的虚拟页面偏移量(VPO) （2）一个n-p 位的虚拟页号(VPN). 将页表条目中物理页号(PPN) 和虚拟地址中的VPO串联气力啊，就得到相应的物理地址。【NOTE: 因为物理和虚拟页面都是P字节的，所以物理页面偏移(PPO) 和VPO是相同的】

处理器生成一个虚拟地址，并把它传送给MMU。

MMU生成PTEA地址，并从高速缓存/ 主存请求得到它。

高速缓存/主存向MMU返回PTE。

MMU 构造物理地址，并把它传送给高速缓存/主存

高速缓存/主存返回所有请求的数据字给处理器。

缺页：不同的地方就是处理缺页要求硬件和操作系统内核协作完成

1~3步骤和原来一样
第4步， PTE中的有效位为0，所以MMU触发了一次异常，传递给CPU中的控制到操作系统内核中的缺页异常处理程序
第5步：缺页处理程序确定出物理内存中的牺牲页，如果这个页面已经被修改了，则把它换出到磁盘
第6步：缺页处理程序页面调入新的页面，并更新内存中的PTE。
第7步: 缺页处理程序返回到原来的进程，再次执行导致缺页的指令。 CPU见感应器缺页的虚拟地址重新发送给MMU。因为虚拟页面现在缓存在物理内存中，所以，就会命中。走命中的逻辑。

6.1> 结合高速缓存和虚拟内存

在即使用虚拟内存也使用SRAM高速缓存的系统中，SRAM选择了使用物理寻址的方式。使用物理寻址，多个进程同时在告诉缓存中有存储块和共享来自相同虚拟页面的块成为很简单的事情。而且，告诉缓存无需处理保护问题，因为访问权限的检查是地址翻译过程的一部分。

展示了一个物理寻址的告诉缓存如何和虚拟内存结合起来的： *主要的思路是：地址翻译发生在告诉缓存查找之前。 * NOTE: 页表条目可以缓存，就像其他的数据字一样

6.2> 利用TLB加速地址翻译

TLB ： Translation Lookaside Buffer，TLB 翻译后背缓冲器

现在的问题： 每次CPU产生一个虚拟地址，MMU就必须查一个PTE，以便于将虚拟地址翻译为物理地址。最糟糕的情况下：这会要求内存夺取一次数据，代价是几十到几百个周期。
可能的解决方案： 如果PTE碰巧缓存在L1中，那么开销就下降到1个或2个周期。
现有的实践： 在MMU中包含一个关于PTE的小的缓存：TLB。

TLB 是一个小的、虚拟寻址的缓存，其中每一行都保存着一个由单个PTE组成的块。 TLB通常有高度的相联度。【上图】用于组选择和行匹配的索引和标记字段是从虚拟地址中的虚拟页号中提取出来的。如果TLB 有T=2^t 个组，那么TLB索引(TLBI)是由VPN的t个最低位组成的，而TLB标记(TLBT)是由VPN中剩余的位组成的。

TLB 命中时的步骤：
第1步：CPU产生一个虚拟地址
第2、3步：MMU从TLB中取出相应的PTE
第4步：MMU将这个虚拟地址翻译成为一个物理地址，并将它发送到告诉缓存、主存
第5步：告诉缓存、主存将所请求的数据字返回给CPU。

当TLB不命中时，MMU必须从L1缓存中取出相应的PTE。新取出的PTE存放在TLB中，可能会覆盖一个已存在的条目。

虚拟地址 —— PTE条目（TLB中缓存的是内存地址） —— 内存地址（缓存数据）
虚拟地址转变为 PTE条目这个过程的计算是怎么样的？具体计算过程，标记好

有时间看看是怎么计算的

6.3> 多级页表 —— 允许页表中出现“空洞”

！！！访问物理内存是在内核中进行处理的；

QR: 如果只有一个单独的页表， 32bit地址空间，4KB的页面和一个4byte的PTE，需要页表驻留在内存中4MB。如果是64bit的话，问题将会更加复杂。
————> 多级页表

假设32bit，分为4KB页，每个页表条目是4字节，情况：内存的钱2K个页面分配给了代码和数据，接下来的6K个页面还未分配，在接下来的1023个页面也未分配，接下来的额1个页面分配给了用户栈，两级页表

一级页表PTE负责映射虚拟地址空间中的恶一个4MB的片(chunk[1024个连续的页面组成的]), 。
一级页表指向二级页表 , 二级页表指向4KB虚拟内存页面。
每个一级、二级页表都是4KB字节。刚好和一个你也买呢的大小是一样的。
这种方法减少了内存，因为没有的时候，为空

K级页表

6.4> 综合：端到端的地址翻译

深入理解计算机系统的 9.6.4 的内容
【这个例子要看熟悉】

7、实例研究：Intel Core i7/Linux 内存系统

7.2 linux虚拟内存系统

目标：了解一个实际操作系统是如何组织虚拟内存，以及如何处理缺页。

linux为每个进程维护一个单独的虚拟地址空间【如图】；
包括代码、数据、堆、共享库以及栈段。

内核虚拟内存包含内核中的代码和数据结构；
内核虚拟内存的某些区域被映射到所有进程的物理页面。
eg: 每个进程共享内核的代码和全局数据结构。
LInux也将一组连续的虚拟页面(大小等于系统中的DRAM的总量)映射到相应的一组连续的物理页面。这就为内核提供了一种便利的方法来访问物理内存中的任何特定的位置。
例如：当它需要访问页表，或在一写设备上执行内存映射的I/O操作，而这些设备被映射到特定的物理内存位置时。
内核虚拟内存的其他区域包含每个进程都不相同的数据。比如说：页表、内核在进程的上下文执行代码时使用的栈，以及记录虚拟地址空间当前组织的各种数据结构。

7.1> Linux虚拟内存区域

上图中，强调了记录一个进程中虚拟内存区域的内核数据结构。内核为系统中的每个进程维护一个单独的任务结构(源代码中的task_struct)。任务结构中的元素包含或者指向内核运行该进程所需要的所有信息(例如：PID、指向用户栈的指针、可执行目标文件的名字，以及程序计数器)

任务结构的一个条目指向mm_struct ，它描述了虚拟内存的当前状态。我们感兴趣的两个字段：pgd 和mmap ，其中pgd指向第一级页表(页全局目录)的基址，而mmap指向一个vm_area_structs（区域结构）的链表，其中每个vm_area_structs 都描述了当前虚拟地址空间的一个区域。当内核运行这个进程时，就将pgd存放在CR3控制寄存器中。

几个具体区域的区域结构包括下面的字段：
*）vm_start ：指向这个区域的其实处
*）vm_end：指向这个区域的结束处
*） vm_prot ：描述这个渔区内包含的所有页的读写许可权限
*）vm_flags：描述这个区域内的页面是与其他进程共享的，还有这个进程私有的(还描述了其他一些信息)
*)vm_next ：指向链表中的下一个区域结构。

7.2> Linux 缺页异常处理

假设MMU在试图翻译某个虚拟地址A时，出发一个缺页。这个异常导致控制转移到内核的缺页处理程序，处理程序随后就执行下面的步骤：
1）虚拟地址A是合法的饿吗？换句话说， A在某个区域结构定义的区域内吗？为了回答这个问题，缺页处理程序搜索区域结构的链表，把A和每个区域结构中的vm_start 和vm_end 做比较。如果这个指令是不合法的，那么缺页处理程序就出发一个段错误，从而终止这个进程。这个情况在图9-28 中表示为"1"
因为一个进程可以创建任意数量的新虚拟内存区域(使用在下一节中描述的mmap函数)，所以，顺序搜索区域结构的链表花销可能会很大。因此在实际中，linux使用某些我们没有显示出来的字段， Linux在链表中构建一颗树，并在这颗树上进行查找。

试图进行的内存访问是否合法？换句话说，进程是否在读、写或者执行这个区域内页面的权限？例如，这个缺页是不是由一条试图对这个代码段里的制度页面进行写操作的存储指令造成的？这个缺页是不是因为一个运行在用户模式中的进程试图从内核虚拟内存中读取字造成的？如果试图进程的访问是不合法的，那么缺页处理程序会出发一个保护异常，从而终止这个进程。 “2”
3）刺客，内核知道了这个缺页是由于对合法的虚拟地址进行合法的操作造成的。它是这样来处理这个缺页；选择一个牺牲页面，如果这个牺牲页面被修改过，那么久将它交换出去，还如新的页面并更新页表。当缺页处理程序返回时， CPU重新启动引起缺页的指令，这条指令将再次发送A到MMU。这次，MMU就能正常地翻译A，而不会再产生缺页中断了。

8> 内存映射

Linux 通过将一个虚拟内存区域与一个磁盘上的对象（object）关联起来，以初始化这个虚拟内存区域的内容。 —— 内存映射(memory mapping) 。

可以映射两种类型对象： 1）Linux系统中的普通文件 2）匿名文件
1）Linux文件系统中的普通文件：一个区域可以映射到一个普通磁盘文件的的连续部分。 eg：一个可执行目标文件。文件区（section）被分成页大小的片，每一片包含一个虚拟页面的初始化内容。因为按需进行页面调度，所以这些虚拟页面没有实际交换进入物理内存，知道CPU第一次应用到页面(即发射一个虚拟地址，落在地址空间这个页面的范围之内)。如果区域比文件区要大，那么就用零来填充这个区域的余下部分。
3）匿名文件：一个区域也可以映射到一个匿名文件，匿名文件是由啮合创建的，包含的全是二进制零。 CPU第一次应用这样的一个区域内的虚拟页面时，内核就在物理内存中找到一个合适的牺牲页面，如果该页面被修改过，就将这个页面换出来，用二进制零覆盖牺牲页面并更新页表，见跟这个页面标记为是驻留在内存中的。 NOTE：在磁盘和内存之间并没有实际的数据传送。因为这个原因，映射到匿名文件的区域中的要买呢有时也叫做 请求二进制零的页[demand-zero page]。

无论那种情况下：一旦一个虚拟页被初始化了，它就在一个由内核维护的专门的交换文件(swap file) 之间换来换去。交换文件也叫做交换空间(swap space) 或者交换区域(swap area)。 NOTE：在任何时刻，交换空间都限制这当前运行着的进程能够分配的虚拟页面的总总数。

8.1> 在看共享对象

内存映射的来源想法：如果虚拟内存系统可以集成到传统的文件系统中，那么就能提供一种简单而高效的把程序和数据加载到内存中的方法。

每个进程都是有保护机制的，同时又可以只读的副本。 —— 共享对象。这样就不用每个进程中保存常用的代码副本了。
内存映射提供了一种清晰的机制，用来控制多个进程如何共享对象。

（1）如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内，那么这个进程对这个区域的任何写操作，对于哪些吧这个共享对象映射到它们虚拟内存的其他进程而言，也是可见的。而且，这些变化也会放映在磁盘上的原始对象中。
(2) 一个映射到私有对象的区域做了改变，对其他进程是不可见的，任何写操作都不会反映在磁盘的对象中。

一个映射到共享对象的虚拟内存区域叫做共享区域，类似：也有私有区域

共享对象

进程1和进城将一个共同的共享对象映射到各自的虚拟内存中

因为每个兑现格斗有一个唯一的文件名，内核可以迅速地判定进程1已经映射了这个对象，而且可以使进程2中的页表条目指向相应的物理页面。

私有对象
私有对象使用了一种叫做写时复制[copy-on-write]的技术被映射到虚拟内存中，一个私有对象开始生命周期的方式基本上与共享对象的一样，在物理内存中只保存有私有对象的一份副本。

两个进程使用的私有对象进行了写时复制

写时复制：就是讲内容在最后一刻再进行复制

两个进程将一个私有对象映射到它们虚拟内存中的不同区域，但是共享这个对象同一个物理副本。对于每个映射私有对象的进程，相应的私有区域的页表条目都被标志为只读，并且其余结构被标记为私有的写时复制。

只要有一个进程进行写操作，就出触发一个保护故障。

当故障处理程序注意到保护异常是由于进程视图写私有的写时复制区域中的一个页面而引起的，它就会在物理内存中创建这个页面的一个新副本，更新页表条目指向这个新的副本，然后恢复这个页面的可写权限。当故障程序返回时候， CPU重新执行这个写操作。

8.2 > fork 函数

1)当fork 函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。为了给这个新进程创建虚拟内存，它创建了当前进程的mm_struct、区域结构和页表的原样副本。它将连个进程中额每个页面都标记Wie只读，并将连个进程中的每个区域结构都标志为私有的写时复制。

当fork在新进程中返回时，新进程现在跌的虚拟内存刚好和调用fork时存在的虚拟内存相同。当着两个进程中的任意一个后来进行写操作时候，写时复制机制就会创建新页面。

8.3 > execve 函数

虚拟内存和内存映射在将陈旭加载到内存的过程中扮演着重要的角色。

QR ：理解execve 函数直接上是如何加载和执行程序的？

eg: execve("a.out", NULL, NULL);函数在当前进程中加载并运行包含在可执行目标文件a.out 中的程序。用a.out 程序有效的替代了当前程序。

加载并运行a.out的步骤：
1）删除已存在的用户区域。删除当前进程虚拟地址的用户部分中的已存在的区域结构。
2）映射私有区域。为新程序的代码、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时复制的。代码和数据区域被映射为a.out文件中的.text 和.data 区。 bss区域是请求二进制0的，映射到匿名文件，，IQ大学爱哦包含在a.out 中。栈和堆区域也是请求二进制零的，，初始长度为0。
3）映射共享区域。如果a.out 程序与共享对象链接， eg：标准的C库libc.so ，那么这些对象都是动态链接到这个程序的，然后在映射到用户虚拟地址空间中的共享区域内。
4）设置程序计数器(PC)：execve 做的最后意见事情就是设置当前进程上下文中的程序计数器，使之指向代码区域的入口点。

8.4 使用mmap函数的用户级内存映射

Linux 使用mmap函数俩创建的虚拟内存区域，，并将对象映射到这些区域中

mmap 函数要求内核创建一个新的虚拟内存区域，最好是从地址start开始的一个区域，并将文件描述符fd指定的对象的一个连续的片（chunk）映射到这个新的区域。连续的对象片大小为length字节，从距文件开始处偏移量为offset字节的地方开始。 start地址仅仅是一个暗示，通常被定义为NULL

参数prot 包含描述新映射的虚拟内存区域的访问权限位(即在相应区域结构中的vm_prot位)

prot_exec ：这个区域内的页面由可以被CPU执行的指令组成

prot_read: 这个区域内的页面刻度

prot_write: 这个区域内的页面可写

prot_none ：这个区域内的页面不能欧股被访问。

参数flags 由描述被映射对象类型的位组成。如果设置了 MAP_ANON标记位，那么被映射的对象就是一个匿名对象，而相应的虚拟页面是请求二进制零的。 MAP_PRIVATE 表示被映射的对象是一个私有的、写时复制的对象，而MAP_SHARED 表示是一个共享对象。

让内核创建一个新的包含size字节的只读、私有、请求二进制零的虚拟内存区域。如果调用成功，那么bufp 包含新区域的地址。

munmap函数删除虚拟内存的区域

删除从虚拟地址start开始的，由接下来length字节组成的区域。

9> 动态内存分配：

虽然使用低级的mmap和munmap函数创建和删除虚拟内存的区域，但是C程序员还是会觉得当运行时需要额外的虚拟内存时，使用动态内存分配器(dyanmic memory allcator) 更加方便、更好的可移植性。

动态分配器维护者一个进程的虚拟聂村区域 —— 堆（heap）。
假设对是一个请求二进制零的区域，它进阶在未初始化的数据区域后开始，并向上生长(向更高的地址)。每个继承，内核维护者一个变量brk（break）, 它指向堆的顶部。

分配器将堆视为一组不同大小的块(block)的集合来维护。每个块就是一个连续的虚拟内存片（chunk），要么已分配的，要么是空闲的。
已经分配的块显式地保留为共应用程序使用。空闲块可用来分配。空闲块保持空闲，知道它显式地被应用所分配。一个已经分配的快保持已分配的状态，知道它释放，释放是应用程序显示执行的，或者内存分配器隐式执行的。

分配器有两种基本风格。都要求应用显式地分配块。不同在于由哪个实体来负责释放已分配的块。

显示分配器(explicit allocator) ，要求应用显示地释放任何已分配的块。 eg：C中的malloc ， C++中的new
要求分配器检测一个已分配的块什么时候不再被程序使用，那么久释放这个块。（垃圾收集器） Java 、。。。

9.1> malloc 和free 函数

void *malloc(size_t size); 
返回一个指针， size：字节块的大小。
这个块可能包含在这个块内的任何数据对象类型做对齐。
eg: 32位模式中， 是8的倍数， 64位中是16的倍数。

如果malloc调用错误[eg：程序要求的内存块比可用的虚拟内存还要大] ，那么它就返回NULL，并设置errno。

malloc 不初始化它返回内存，

想要已初始化的动态内存的应用程序可以使用calloc， calloc是一个基于malloc的瘦身包装函数，它将分配的内存初始化为0.

想要改变一个已经分配块的大小，可以使用realloc

动态内存分配器： eg： malloc 可以使用mmap、munmap函数显示分配和释放对内存；或者使用sbrk函数：

void *sbrk(intptr_t incr) ; 
返回：  若成功则为旧的brk指针，若出错则为-1

sbrk 通过将内核的brk指针增加incr来扩展/收缩堆。如果成功，它就返回brk的旧值，否则，就返回-1，并将errno设置为ENOMEM。如果 incr为0 ，那么sbrk就返回brk的当前值。 incr 为负值，因为返回值(brk的旧值)指向距离堆顶向上的abs(incr)字节处。

void free(void *ptr)

malloc 和free 实现如何管理一个C程序的16字的小的堆

9.2> 为什么要动内存分配

在实际中，经常会知道程序实际运行时，才知道某些数据结构的大小。

#define MAX  15213
 int array[MAX ]  // 静态定义这个数据，， 它的最大数组大小是硬编码

问题：MAXN与机器上的额U型你内存实际数量没有关系，有可能不够，有可能太多浪费 —— 动态内存分配

9.3> 分配器的要求和目标

处理任意请求序列。一个应用可以有任意的分配请求和释放请求序列，只要满足约束条件: 每个释放请求必须对应一个当前已分配块，这个块是由一个以前的分配请求获得的。
立即响应请求。分配器必须立即响应分配请求。因此，不允许分配器为了提高性能重新排列或缓冲请求。
只使用堆。为了使分配器是可扩展的，分配器使用的任何非标量数据结构都必须保存在堆里。
对齐块(对齐要求)。分配器必须对齐块，使得它们可以保存任何类型的数据对象。
不修改已份分配的块。分配器只能操作或改变空闲块。

分配器尽可能实现吞吐率最大化和内存使用率最大化，但是这两个性能相互冲突。 —— 应该要适当的平衡。

9.4> 碎片 —— 造成堆利用率很低的主要原因

虽然有未使用的内存，但是不能够用来满足分配请求时，就会发生碎片现象。分为内部碎片、外部碎片

1）内部碎片：一个已分配块比有效载荷大时发生的。（eg：内存对齐）量化：分配块大小 - 有效载荷
2）外部碎片：当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以处理这个请求时发生的。
量化：取决于请求的模式、分配器的实现方式以及将来请求的模式。难以量化，分配器通常采用启发式策略视图维持少量的大空闲块。

9.5> 实现问题

malloc/free 分配器的吞吐率极好，但是，分配器从不使用任何块，内存利用率极差。
吞吐率和利用率之间的平衡：
1）空闲块的组织：我们如何记录空闲块
2）放置：我们如何选择一个合适的空闲块来放置一个新分配的块
3）分割：在将一个新分配的块放置到某个空闲块之后，我们如何处理这个空闲块中的剩余部分？
4）合并：我们如何处理一个刚刚被释放的块？

9.6> 隐式空闲链表

堆块数据结构：用来区分块边界，以及区分已分配块和空闲块，大多数将这些信息嵌入块本身

块组成：一个字的头部、有效载荷、以及一些额外的填充。
头部：块的大小（包括头部和所有的填充），是否一斤分配。

隐式空闲链表

空闲块是通过头部中的大小字段隐含地连接着的，分配器可以通过遍历堆中所有的块，从而间接地遍历整个空闲块的整合。【NOTE: 我们需要某种特殊标记的结束块】

优点：简单
缺点：任何操作的开销，例如防止分配块的，要对空闲链表进行搜索，该搜索锁需时间与堆中已分配块和空闲块的总是呈线性关系。

很重要的一点: 系统对齐要求和分配器对块格式的选择会对分配器上的最小块大小有强制的要求。 没有分配块或者空闲块可以比这个最小值还小。

9.7> 放置已分配的块

当一个应用请求一个k字节的块时，分配器搜索空闲链表，查找一个足够大可以放置所请求块的空闲块。分配器执行这种跟着你搜索的方式是放置策略【placement polichy】 确定的。

一个常见的策略是首次适配(first fit) ，下一次适配(next fit) 和最佳适配(best fit)

首次适配：从头开始搜索空闲链表，选择第一个适配的空闲表。
优点：趋向于将大的空闲块保留在链表的后面。
缺点：趋向于在靠近链表起始处留下小空闲的“碎片”, 增加了对较大块的搜索时间。

下一次适配：和首次适配很相似，只不过不是从链表的起始处开始每次搜索，而是从上一次查询结束的地方开始。
优点：比首次适配要快，尤其是前面不慢了许多小的碎片的时候。
缺点：利用率比首次适配低得多。

最佳适配：检查每个空闲块，选择合适锁需要请求大小的最小空闲块。
优点：比上面两种的利用率要高。
缺点：要求对堆进行彻底的搜索。

9.8> 分割空闲块

分配器找到一个匹配的空闲块 ——> 分配这个空闲块中多少空间。

1）使用整块，利用率低
2）如果匹配不好，分配器通常选择将这个空闲块分割为两个部分。第一块变成分配块，剩下成为一个新的空闲块。

9.9> 获取额外的堆内存

QR : 如果分配器不能为请求块找到合适的空闲块将发生什么呢？

通过合并哪些在内存中物理上相邻的空闲块创建一些更大的空闲块
合并之后还不足够大【或空闲块已经最大程度地合并了】，通过sbrk函数，向内核请求额外的堆内存。分配器将额外的内存转化成一个大的空闲块，将这个块插入到空闲链表中，然后将被请求的块放置在这个新的空闲块中。

9.9.10> 合并空闲块

当分配器释放一个已分配块时，可能有其他空闲块与这个新释放的空闲块相邻。 —— 假碎片

因为请求分配的空间，比它们的和小，但是比它们各自都大

解决方法：合并相邻的空闲块。（1）立即合并（2）推迟合并【eg: 分配器可以推迟合并，知道某个分配请求失败，然后扫描这个堆，合并所有的空闲块】

问题： 立即合并简单，可以在常数时间内执行完成，但是对于某些请求模式，这种方式会产生一种形式的抖动，块会反复的合并，然后马上分割。

9.9.11> 带边界标记的合并

分配器是如何实现合并的？
【合并下一块】想要释放当前的块。合并(内存中的下一个空闲块是很简单而高效)；当前块的头部指向相邻一个块的头部，那么检查这个指针以判断下一个块是否空闲的。如果是，就将它的大小简单地加到当前块头部的大小上，这两个块在常数时间内被合并。
【合并上一块】合并前面的块
给定一个带头部隐式空闲链表，唯一的选择将是搜索整个链表，记住前面块的位置，直到我们到达当前块。使用隐式空闲链表，这意味着每次调用free需要的时间都与堆的大小成线性关系。即使使用更复杂精细的空闲链表组织，搜索时间也不会是常数。
边界标记(boundary tag)：允许在常数时间内进行对前面块的合并。上图中，是每个块的结尾处添加的一个脚部(footer ，边界标记)，其中脚部就是头部的一个副本。如果每个块包括这样一个脚部，那么分配器就可以通过检查它的脚部，判断前面一个块的起始位置和状态，这个脚部总是在距当前块开始位置一个字的距离。【感觉就是一个前指针、后指针】

可能存在的4中情况

缺陷： 它要求每个块都保持一个头部和一个脚部，在应用程序许多小块时，会产生显著的内存开销。

优化：只有在前面的块是空闲时，才会需要用到它的脚部。如果我们把前面的块的已分配/空闲位存放在当前块中多出来的地位中，那么已分配的块就不需要脚部了，这样我们就可以将这个多出来的空间用作有效载荷了。

9.9.12 综合：实现一个简单的分配器

延伸

延伸到mmkv的内容

1、 window上的虚拟内存和 linux上的swap 区域，和我们现在所说的虚拟内存

window上的虚拟内存和 linux上的swap 区域基本上是同一个概念，我们讨论的系统的虚拟内存是不是一个概念，是两个不同的概念；

window的虚拟内存：若是计算机胡哦哦这操作所需要的额物理内存不够的时候， windows会用虚拟内存进行补偿，即拿出一部分硬盘空间来充当内存使用，这部分空间成为虚拟内存。它将计算机的RAM 和硬盘上的临时空间组合。

swap 分区： swap分区(即：交换区) 在系统的物理内存不够用的时候，把硬盘空间中的一部分空间释放出来，以供当前运行的程序使用。哪些被释放的空间可能来自一些很长时间没有什么操作的程序，这些被释放的空间被临时保存到Swap分区中，等到那个程序要运行时，再从Swap 分区中恢复保存的数据到内存中。

关系：
swap类似于windows上的虚拟内存，不同之处在于，windows 可以设置windows在任何盘符下面，默认是C盘，可以和系统文件放在一个分区里。而linux则是独立占用一个分区，方便由于内存需求不够的情况下，把一部分内容放在swap分区里，待内存有空余的情况下再继续执行，也称之为交换分区，交换空间是其中的部分。 windows 的虚拟内存是电脑自动设置的。

window 上面设置虚拟内存，只是一个申请，具体可以用到多少，还是操作系统来决定的；
swap是通过空间换时间的，是一种策略；
我们常说的设置电脑虚拟内存，其实那个是swap的分区，这个是用来扩展内存空间的；

系统上的虚拟内存：是一种抽象的概念

分段机制：【感觉是x86历史遗留下来的】

虚拟地址空间分成若干不同大小的段

1）虚拟地址空间分成若干个不同大小的段
《1》段表存储着分段信息，可供MMU查询
《2》虚拟地址分为：段号 + 段内地址（偏移）

2）物理内存也是以段为党委进行分配
《1》虚拟地址空间中相邻的段，对应的物理内存可以不相邻

3）存在问题
《1》分配的粒度太粗，外部碎片
《2》段与段之间留下碎片空间，降低主存利用率

段的翻译

内存