重生之我是操作系统(七)----内存管理(上)
简介一个操作系统，要实现对内存的管理，需要实现如下几个核心目标：
[*]分配与回收
高效分配，减少内存碎片和内存利用率
[*]空间扩充
内存虚拟化，让进程享受近乎无限的内存地址。
[*]存储隔离
保证各个进程之间不会越界访问。
[*]高效通信
支持进程间内存共享，提高交换效率。
分配与回收
先来分享一个前置知识:
1.内部碎片
分配给进程的内存区域中，有些部分是空闲没有用上。
比如SQL Server , .NET CLR 。 他们自己内部一套实现了内存管理，因此要先预申请大量内存。
2.外部碎片
内存中某些空闲分区由于太小难以利用上
连续内存分配
为进程分配的必须是一个连续的内存空间
单一连续分配
long long years ago ，单任务系统时代(MS-DOS)，由于是单任务操作系统。所以内存中只会有一道用户程序。该程序独享整个用户态空间。
[*]优点
实现简单：直接采用覆盖技术扩充内存，且不需要进程隔离
无外部碎片：就一个程序能有啥碎片？
[*]缺点：
有内部碎片
固定分配
随着多任务操作系统的兴起，单一连续分配已经不能满足需求。因此发展成，讲整个用户态空间划分为若干个固定大小的分区，每一个分区中只运行一个进程。形成了最早，最原始的多进程内存管理。
[*]优点
实现简单，不会产生外部碎片。
[*]缺点
-. 当程序太大，分区表中所有分区都无法满足，此时就需要采用覆盖技术来解决。但会降低性能。
-. 会产生内部碎片，一个10M大小的分区，只放了一个9M的程序，还有1M空间被浪费。
-. 分区固定，缺乏灵活性
虽然也有将要分区表划分为不同大小的分区，以此提交灵活性。但依旧是固定分配的范畴。
动态分配
为了解决固定分配的痛点，操作系统又发展出动态分区分配策略。
这种分配方式不会预先划分内存区域，而是在进程装入内存时，根据进程大小动态建立分区。
[*]优点
不会产生内部碎片，外部碎片可以通过压缩来缓解。
[*]缺点
实现复杂，内存回收时要考虑前后相邻，合并的情况。
动态分配算法
首次适应(First Fit)
[*]原理
从低地址/起始地址开始搜索，选择满足大小的第一个空闲空间。分割后分配(剩余部分仍为空闲块)。
[*]优点
快速，无需遍历所有空闲块。
[*]缺点
在低地址区域留下大量碎片
【100kb,200kb,50kb】,申请150，选择第二个，变成【100kb,50kb,50kb】
邻近适应(Next Fit)
由首次适应演变而来
[*]原理
从上一次分配结束的位置开始搜索，找到第一个足够大的空闲块(类似首次适应)
[*]优点
平衡内存碎片分配位置，较少低地址碎片的堆积，且搜索效率高于首次适应
[*]缺点
只是平衡内存碎片分配的位置，但碎片问题依旧存在，可能导致大分区被分割为小碎片。
最佳适应(Best Fit)
[*]原理
搜索所有空闲块，选择满足大小的最小空闲块。分割后分配(剩余部分仍为空闲块)。
[*]优点
内存利用率最高，会有更多大分区被保留下来，能够满足大进程需求
[*]缺点
产生大量极小内存碎片，且难以利用。
【100kb,200kb,50kb】,申请49，选择第三个，变成【100kb,200kb,1kb】
最坏适应(Worst Fit)
为了解决最佳适应的缺点，又衍生出最坏适应
[*]原理
搜索所有空闲块，选择满足大小的最大空闲块。分割后分配(剩余部分仍为空闲块)。
[*]优点
避免产生微小碎片
[*]缺点
提前消耗大内存块，等大进程来时无法满足。
【100kb,200kb,50kb】,申请15个10，选择第二个，变成【100kb,50kb,50kb】，此时再申请200，无空间可用。
总结
算法核心策略优点缺点典型场景首次适应第一个足够大的块分配速度快，实现简单低地址碎片多实时性要求高的系统最佳适应最小足够大的块内存利用率高微小碎片多，效率低内存紧张、小内存请求多最坏适应最大空闲块分割减少微小碎片大内存块可能提前耗尽中等大小内存请求为主邻近适应从上一次位置开始搜索分配均衡，减少碎片堆积性能中等通用多任务系统tips: 一个反直觉的知识
由于最佳适应/最坏使用需要检索整个空闲块，所以为了提高搜索效率。往往要对空闲块进行排序操作。而邻近适应在实际应用中，并没什么卵用，反而影响大进程的调度。
因此综合下来，反而是首次适应的综合效率更好。
动态回收算法
边界标记法
每个内存块头部记录块大小和分配状态，尾部存储前一个块的头部地址（或状态），释放时通过前后块地址判断是否相邻空闲：
前向合并：后一个块是空闲块，合并为一个大空闲块。
后向合并：前一个块是空闲块，合并为一个大空闲块。
双向合并：前后块均为空闲块，合并为一个更大的块。
非连续内存分配
为进程分配的是一些分散的空间
从上面可以看出，连续内存分配的有如下几个痛点：
[*]外部碎片严重，内存利用率低
动态分配在申请和释放过程中，会产生大量不连续的空闲块。需要定期"压缩"内存，而压缩会消耗大量CPU时间。
[*]开销大
动态分配算法中(首次适应，最佳适应，最坏适应)等算法需要遍历整个空闲块,时间复杂度为O(n).
释放算法中，需要合并相邻的空闲块，逻辑复杂且耗时。
[*]不支持虚拟化
动态分配要求是对物理内存的的规划，需要对物理内存进行动态分配。因此无法运行大于物理内存的程序。
[*]管理困难
因为进程地址是单一连续区域，所以难以对程序进行单独的隔离与管理（如代码段、数据段）。
为解决上述问题，又进化出了非连续的分配管理方式。
页(Paging)
原理：将物理内存划分为固定大小的页框(Page Frame,4kb)，而程序的逻辑地址空间页划分为相同大小的页(Page，4KB)。通过页表(Page Table)完成页到页框的映射，并允许页在物理内存中的不连续。
[*]优点
完全消除外部碎片，支持虚拟内存地址
[*]缺点
存在页内碎片(最后一页可能未填满)，页表本身也占用内存
页表转换过程没有图示如此简单，有兴趣可以自行查找资料。
硬件对页的优化
为了加速页表的转换，硬件也使出了多种手段。
[*]TLB
缓存近期访问的页表项，将地址转换从两次降为一次，(查页表+访问物理内存)=>直接访问物理内存。
[*]多级列表
将页表分页存储，减少内存占用。例如，x86-64采用五级页表，支持64位虚拟地址空间。
页管理方式很好，但依旧难以对程序进行单独的隔离与管理（如代码段、数据段）。
段(Segmentation)
原理：将程序的逻辑模块(如代码段，数据段，栈)分组，每个段在逻辑上连续，但在物理上不连续，通过段表(Segment Table)来实现转换。
[*]优点
符合程序逻辑的结构，很方便的按照分组来实现共享和保护。
比如：多个进程共享同一段代码段。代码段设置只读，数据段设置可写。
[*]缺点
可能产生外部碎片，因为段与动态分配很像，不确定大小，所以在分配过程中难免产生碎片。
段也可以引用TLB机制与多级段表来优化效率。
段页(Segmentd Paging)
原理：结合分页与分段的优势，先将程序划分为段，再将每个段划分为页。通过段表和页表的多级映射实现地址转换。
[*]优点
兼顾逻辑分段和物理分页的效率，支持虚拟内存和内存保护
[*]缺点
空间占用大，地址转换效率低，需要三次(查段表+查页表+访问物理内存)。
现代操作系统的设计应用
[*]Linux
采用分页方案，使用四级页表（64 位系统），支持大页（Huge Pages，如2MB/1GB）减少页表开销。
[*]Windows
使用段页方案，使用简化版的段与页，同样使用四级页表与大页。
空间扩充(虚拟化)
为什么我们需要虚拟化内存？
在上述的连续分配/非连续内存分配方案中，进程必须一次性全部载入内存后才能开始运行。很多暂时用不到的数据/代码也会长期占用内存，导致内存利用率不高。
举个例子，有一个经典游戏叫，他的容量大小将近100g，如果按照目前的方式，内存容量完全不够。
虚拟化的理论支持：局部性原理
[*]时间局部性
如果执行了进程中的某条指令，那么不久后这条指令很有可能再次执行，如果某个数据被访问过，也很有可能再次被访问。
[*]空间局部性
一旦程序访问了某个存储单元，那么其附近的存储单元页很有可能被访问。
int i;int a;//空间局限性，变量/存储单元基本上都是集中定义在一起，连续存放for(i=0;i
页:
[1]