1、位视图法

分配

这种方式分配内存采取的数据结构可以是二维数组。如下图所示，其中每一块代表一个页。其中的数字为1代表这块内存被分配出去了。没有标识为1，代表可以被分配。当我们需要一块4页大小的内存的时候，就会从头找是否标识为1，是1跳过，不是1则看看在同一行是否可以找到连续的4块位置。否则继续遍历。

20211226124914.png

回收

我们写死每个进程申请内存的时候都会有进程控制块。这个进程控制块（PCB）都会有指向这个进程使用的内存的指针。当要回收内存的时候就会给操作系统发信号，这时候操作系统就会记录下要结束进程指针所指向的内存地址，当进程结束的时候就会把内存回收。将对应的标识置为0。其他几种回收内存的方式和这种类似，后面不在赘述。

2、链式分配法

分配

上面的一个个查询过于繁琐，每次都要从开始位置向后面一个个遍历，而且也不能判断有空闲的页是否能分配给要申请的内存，这时候操作系统来利用链表这种数据结构来分配和回收内存，结构如下图。其中第一位代表标识，p(process)代表被进程占用。F(free)代表空闲。进程控制块中会有信息指向这个标记位，以便于回收内存。这第二位代表的是地址，第三位代表长度。最后一位代表指向下一个结点的指针。

第一个结点的信息就代表起始地址是0号的页，后面的连续四个页（包括0页）被进程占用。当需要申请内存的时候就从链表头部开始遍历，找到符合要求的地址，拆分这个结点的信息，分出一部分地址。比如比如要申请一块三个页的内存，就把第二个结点拆成两个结点。其中分出来三个页给进程使用。

20211226124924.png

回收

当要回收内存的时候。就会把这个标识位清空，删掉这个结点。改变为空闲区的长度和起始地址（参考==存储管理之内存分配与回收==的回收部分）

3、伙伴系统分配法

3.1、概念

伙伴系统是一种经典的内存管理方法，提供了一种用于==分配一组连续的页==而建立的一种高效的分配策略，并有效的解决了外碎片问题。

  • ==外碎片问题==：在内存管理中，如果频繁地请求和释放不同大小的内存，会导致在内存池存在很多碎片化的内存区域。简单的说，因为释放的内存不是连续的，导致这里释放一块，哪里释放一块。这样就很容易出现问题，当一个请求过来，需要开辟5M的空间，在内存池中有很多4M的，就是没有5M的，既没有足够大的==空闲连续内存区域==满足要求，这就是外碎片问题。
  • ==内存池存在太多的碎片区域导致无法分配一个大块的连续内存==

3.2、伙伴系统的组织结构

Linux中的内存管理的“页”大小为4KB。 把所有的空闲页分组为11个块链表，每个块链表分别包含==大小为==1，2，4，8，16，32，64，128，256，512和1024个连续页框的页块。最大可以申请1024个连续页，对应4MB大小的连续内存。每个页块的第一个页的物理地址是该块大小的整数倍。

20211226124937.png

20211226124949.png

3.3、分配

我们知道内存时很大的，每个页的内存是4K，而对于我们4G的计算机来说，上面那种链式的结构虽然有些改进，但是对于我们查询链表然后分配内存还是不够乐观。这时候出现了伙伴分配的方式。

当向内核**请求分配(2^(i-1)，2^i]**数目的页块时，按照2^i页块请求处理。如果对应的块链表中没有空闲页块，则在更大的页块链表中找。

当分配的页块中有多余的页时，内核会自动根据未用的页的大小插入到对应的链表中。

3.4、回收

释放单页

https://www.cnblogs.com/xudong-bupt/archive/2013/03/22/2976289.html

释放多页

当释放多页的块时，内核首先计算出该内存块的伙伴的地址。如果找到了该内存块的伙伴，确保该伙伴的所有页都是空闲的，以便进行合并。内存继续检查合并后页块的“伙伴”并检查是否可以合并，依次类推。

内核将满足以下条件的三个块称为伙伴：

  1. 两个块具有相同的大小，记作b。
  2. 它们的物理地址是连续的。
  3. 第一块的第一个页的物理地址是2*(2^b)的倍数。

3.5、伙伴系统的反碎片机制

物理内存的碎片化一直是Linux的一大问题，内核对于该问题仿照文件系统的方式，通过碎片化合并的方式解决该问题。但是由于许多的物理内存页是不能够移动到任意位置的地方，阻碍了该方法的实施，所以内核采用的是反碎片化，即试图从最开始就尽可能的防止碎片问题。

  • 内核将已分配页分为以下三种不同的类型：
    • ==不可移动页==：这些页在内存中有固定的位置，不能移动。核心内核分配的大多数内存属于该类型。
    • ==可回收页==：这些页不能移动，但可以删除。内核在**回收页占据了太多的内存时？**或者内存短缺时进行页面回收。
    • ==可移动页==：这些页可以任意移动，用户控件应用程序使用的页都属于该类别。他们是通过页表映射的。当他们移动到新的位置，页表项也会相应的更新，应用程序不会注意到任何事。