内存管理
写在最前
内存管理的要点简述：
- 程序看到的是逻辑地址，并不是真正的物理地址
- 内存需要进行分片，逻辑空间片叫page，物理空间的片叫page frame
- 逻辑-物理的page映射是放在page table（页表），其存在主存中
- 为了加速页表查询有了TLB（Translation Lookaside Buffer）快表
- 为了减小页表大小有了多级页表
- 为了程序本身便于管理内存有了分段
- 为了更好的使用cache有了VIPT
1 虚拟内存（逻辑内存）
win32程序从程序上能操作的逻辑地址空间有4G这么大（虽然实际可能用不了那么多），4G的逻辑地址需要全部映射到物理内存上。映射的最小单位如果是字节的话，映射表将会非常大，且效率低下。提出page概念，即最小的映射单位是一个page，一页一般是4K，2M等这样的大小。
显然逻辑空间可能比实际要大，但是只要程序没有用那么多内存，就不需要去映射那么多page，且就算用了那么多内存，也可以映射到磁盘上。
逻辑页是抽象的，需要映射到物理的页上，才能完成对内存的操作。我们把逻辑页叫页（page）物理页叫帧（page frame）。页号-帧号的映射表叫页表（page table）。
因为每个程序看到的逻辑地址空间都很大，所以程序变多了之后，程序使用的内存大于了物理内存，此时一般通过将部分不着急使用的页映射到磁盘的方式来解决。所以页表中映射项可能是磁盘。
同时每个进程都有自己的专属页表，如下：
一种实际情况，4G逻辑地址有32bit地址空间，假设pageSize=4K偏移量占12bit，因而页表的逻辑页号有20bit。再假设实际内存条只有256G 28bit地址空间 12bit偏移量 16bit页号。
逻辑地址0x 00001 1a3，去映射的时候00001就是逻辑页号，去查页表发现映射到真实页号00f3，然后偏移量不变还是1a3，最终就找到这个物理内存内容了。
这个过程中，可能会出现映射的帧号是disk，即映射到了磁盘上。此时会触发缺页异常，进入内核态，内核从磁盘中读取缺的这页内容，将其加载到物理内存中。但是物理内存的帧有可能所有帧都满了，此时就需要逐出不太"重要"的帧。
逐出的过程需要判断当前物理页(帧)是否是脏的（脏：与磁盘中内容不一致，即从磁盘加载到物理内存后被改过就是脏的），如果是脏的还需要更新磁盘中的内容保证一致。
逐出后就腾出了位置给从磁盘中读到的这页的数据，然后需要更新页表的这一项的映射关系，将磁盘改为帧号，然后重新进行查页表这一步。
逻辑层的作用：极大的降低了内存随便；借助磁盘可以实现"无限的内存"；各个进程间内存的安全性等。
2 页表PT、快表TLB、多级页表
上面提到了逻辑-物理页的映射，这就是页表，但是上面的页表其实除了简单的页号映射，还存储了其他一些属性：是否有效，读写权限，修改位，访问位（淘汰算法和TLB中用），是否是脏（被修改过就是脏的，因为他和硬盘上的数据不一致），是否允许被高速缓存等等。
页表存于主存中，每个进程都有自己的页表。
上面可以看到基于页表的寻址，需要两次访问主存（页表是存在主存的），效率低下。为了提高速度，引入了快表，快表是页表项的缓存，将最近一次的映射项存入快表，因为空间有限所以需要逐出最老的那一项。快表的设计是基于经验：程序经常访问的page一般就那几个，不会经常频繁的更换特别多的页。
快表可能存于硬件MMU中（也可能是软件TLB），一般只有8-256条，每个进程都有自己的快表。
另一个值得讨论的话题是页表占用空间太大，上面例子中（32位程序256M机器pageSize4K）页号有20bit即2百万个，所以需要有1百万条，每条大小如果只算逻辑页号(20bit)和物理页号(16bit)的话：
36bit * 2^20 = 4.5MB
如果有64个这样的程序在运行...后果可想而知。
一种很好的解决方法是多级页表，第一级页表用于寻找第二级页表的编号。<20bit-16bit>的单级映射可以改成<10bit-10bit>和<10bit-6bit>两级映射。此时占用内存为
20bit * 2^10 + 16bit * 2^20 = 2M
3 分段
严格意义的分段是，每一段的虚拟地址都是从0开始。然后页表是段号+页号来映射帧号的。但是这种形式已经被废弃了，只有x86 32位的intel的cpu还保留了这种段页结合的方式，即严格意义的分段已经用的很少。
那为什么还经常听到段的概念？现在所说的段一般是程序在逻辑层面保留的概念，对逻辑地址有个粗略的划分，便于程序编写，但是并不影响os的内存管理（还是分页管理）。
以32位程序为例，在逻辑空间中最高的0xc0000000 - 0xffffffff这1G的内存是给内核留出的。剩余3G内存从低到高分别是Text、Data、Heap、Lib、Stack。
Heap是从低往高增长，Stack是从高往低增长，且有个最大限制。Data存储静态变量Text存储程序二进制码，Lib存储库函数需要占用的内存，多个程序如果都使用了相同的库，内存是共用的（共享内存）。各个部分的留有随机的一段偏移量，可以保护程序，这也使得每次执行程序的时候变量所在的内存地址总是不同的。
分段是逻辑空间上的，不影响分页的内存管理方式，后面进行分页，映射到物理内存上各部分跨多个页其实并不连续。
4 cache
cpu的三级缓存扮演着缓存主存数据的作用，而cache在内存管理中的位置是怎样的呢？
PIPT，物理级cache，cpu分析完映射关系，先到cache找有没有该物理地址的cache。这样会非常的慢，但是所有进程可以共享cache。
VIVT，逻辑级cache，cpu直接通过逻辑地址找cache，miss后再查TLB页表这些。这样很快，但是逻辑地址只能对当期进程使用，其他进程完全不能复用，尤其是库函数这种共享的不能利用好cache。
VIPT，将两者结合，用逻辑地址查找cache，cache中数据部分前面添加一个对应物理地址的tag。这样拿到这个tag后到tlb、页表中查看下这个对应关系是否正确，如果正确就直接读cache。这样速度和共享性都是折中的。
以上三种方式各有优劣，在不同的cpu中可能使用的不一样。
5 磁盘映射mmap与缺页异常
在1中最后讲述了，如果页表映射到了磁盘的时候就会触发缺页异常。这个过程其实是非常非常慢的。
建立磁盘与内存页映射关系有专门的的系统调用即mmap。mmap其实经常用在一些数据库的底层实现上，其实现原理大概就是讲数据文件，映射到逻辑地址中。在进行查询的时候，是直接查询一个虚拟内存地址，然后首次访问可能会比较慢（缺页），但读取一次之后这页就补全了，后面访问该页的速度就会变快。当然还是有很多细节的，比如什么时候该逐出，页替换算法如何优化。