操作系统是如何管理内存的

背景

最近在学《操作系统真相还原》，深入了解了操作系统是如何管理内存的。内容主要包括：

1. 操作系统使用什么数据结构管理内存？
2. 管理内存的数据结构的存放地址？
3. 操作系统管理的是什么区域的内存？
4. 如何进行地址的分配和释放？

操作系统使用什么数据结构管理内存？

管理内存的核心思想

虽然现在一个电脑中的内存越来越大，但是内存仍然是计算机的重要的资源，操作系统对内存管理的核心思想是使用占用少量的内存的数据结构去尽可能管理更大的内存空间，并且对能够监测内存的使用情况避免内存泄漏（内存泄漏的含义就是操作系统失去了对这块内存的控制，即使这块内存空闲操作系统也无法对其进行分配）

使用 bitmap数据结构—分配粒度是4KB（一个页的大小）

操作系统进入分页机制后，在加载操作系统内核和加载用户进程的时候，都是按照一个个物理页4KB的大小进行分配的。计算机中的物理内存都是几个G的，操作系统一定是需要先划分出一定的内存空间用于管理内存的，并且用于管理内存空间的内存一定足够小，这样可利用的内存就足够大。假设计算机中物理内存有100MB，管理内存的数据结构就要占30MB甚至更多，那这个操作系统一定非常低效。bitmap本质上是一串二进制位，用一个bit位表示一个4KB大小的物理页有没有被分配， 1表示该位分配，0表示未分配。128KB的bitmap就可以管理4GB的物理地址空间。

bitmap的数据结构是

struct bitmap{
	uint32_t btmp_bytes_len;  //btmp_bytes_len:该位图的大小（以字节为单位）
	uint8_t* bits;            //bits:该位图的位置
}

3. 操作系统管理内核的bitmap处于什么位置？为什么？

如下图所示，这是Linux操作系统在4KB的页粒度上管理内存的方式。

计算机的发展一直是一个向上兼容的过程，开机自启的时候处于实模式，在实模式下的计算机的物理内存只有1MB，这1MB的物理内存空间基本被占满，包括Interrupt Vector Table、Bios Data Area、MBR区、显示适配器存储区等。当加载操作内核时，开启保护模式，打开A20地址线防止地址超过 1MB 时回滚，这样就能访问到全部的物理内存空间。假设现在物理内存只有 32MB，使用bitmap数据结构进行分配，一个bit表示一个物理页是否被分配出去。那么我们只需要使用 32MB/4kB=1KB大小的bitmap就可以。这1KB只需要在低1MB内存中找到一个空闲位置存放就可以。注意：操作系统在刚加载之初只会管理那些还没有被分配的内存（也就是高1MB内存），而低1MB的内存几乎被使用完，那么bitmap是不会管理低1MB的，换句话说，内存管理数据结构是不会管理自己的。

bitmap管理大容量数据的例子——腾讯一面

问题：40亿的QQ号，不超过1G内存，如何对QQ号去重？

先来算一下40亿的QQ号如果全部放在内存中能占多少空间，因为有set这个数据结构天然具备去重功能，假设一个QQ号码是32位的
$$
40亿 * 8B = 320亿 * B
$$

$$
32,000,000,000 * B / 1024 /1024 /1024 = 29.8 GB
$$

显然40GB的QQ占用29.8GB的内存远远高于实际的1GB内存，所以将这些QQ数据放到 set数据结构中是不可以的。但是使用bitmap可以，我们计算一下40亿的不同的数据用bitmap来映射需要占用多少内存空间
$$
40亿 / 8 = 500,000,000;
$$

$$
500,000,000 / 1024 / 1024 /1024 = 0.466GB
$$

我们对这40亿的QQ数据去重处理的做法就是：

1. 初始化0.466GB的内存空间
1. 遍历40亿的QQ，将其映射到bitmap中将对应的位置1。遍历完成后，bitmap中所有的1位的集合就是去重后的QQ号

操作系统管理什么内存？

加载时静态内存的分配

在加载资源操作系统内核时和加载用户进程时，需要按照页表4KB的粒度分配内存，存放进程的代码段、数据段等

需要维护物理地址池

注意：物理内存池只有两个：内核物理内存池、用户物理内存池，它们是全局的

将整个物理地址空间按照一定的比例进行分配，假设1:1分配，内核物理内存池和用户物理内存池的大小均是总物理内存大小的一半。划分内存池的目的在于：用户进程只能从用户物理内存池中申请，操作系统进程只能从内核物理内存池中申请，因为用户进程理论上可以运行无数个（在没有进程描述符等参数的限制下），每当加载一个用户进程就要分配出一些内存空间，当用户进程越来越多，可供分配的物理内存越来越少，当操作系统运行过程中动态分配内存就会失败，那么系统就会崩溃掉。

物理地址池的数据结构

struct pool{
	struct bitmap pool_bitmap;     //该内存池的bitmap结构
	uint32_t phy_addr_start;       //该内存池的起始物理地址
	uint32_t pool_size;            //本内存池的字节容量
}

维护虚拟物理地址池

以32位的操作系统为例

计算机开启分页机制后，使用的内存地址都是虚拟地址，需要通过段机制和页表将虚拟地址转换成物理地址进行访存，所以操作系统中还需要为每个进程分配一个虚拟地址池，虚拟地址池的大小和计算机总线一致，32位操作系统的虚拟地址空间大小是4GB。为每一个进程都分配一个虚拟地址池，这个虚拟地址池也是用bitmap数据结构管理的，既然是bitmap数据结构它也需要占用内存，所以在创建进程之初，若是用户进程，理论上需要由操作系统在内核物理内存池中分配32个物理页分配给进程（一个物理页4KB， 32个物理页的bitmap可以表示4GB的内存空间），实际上需要的物理页要少于32个，因为用户进程的高1GB是内核空间，用户进程加载的虚拟地址的起始地址一般是 0x08048000, 而0xc0000000~0xffffffff是内核空间，所以用户进程的虚拟地址位图所占用的空间是：(0xc0000000-0x0804800) / 4KB / B, 这个大小就是用户进程的虚拟地址池所占用的大小

虚拟地址池的数据结构

struct virtual_addr{
	struct bitmap vaddr_bitmap;   //虚拟地址用到的位图结构
	uint32_t vaddr_start;         //虚拟地址的起始地址
}

操作系统全局内存分布图

**总结：**操作系统是使用bitmap数据结构对内存进行管理，将可分配的物理内存（除了低1MB和内核页表和页目录表占用的空间）按照1:1分配为内核物理内存池、用户物理内存池，这两个物理内存池的参数包括内存池位图的起始地址、位图的大小，当我们操作系统加载用户进程时，需要在内核物理内存池中分配几个物理页作为用户进程的虚拟地址池的bitmap（用户进程的虚拟地址池位图为什么不在用户进程地址池中获取呢？因为即使是用户进程，但是资源的分配和管理还是需要交由操作系统来管），然后在加载用户进程的程序体和数据时，在用户进程的物理地址池中分配物理页存储，然后扫描用户进程的虚拟地址池找到空闲的虚拟地址，最后在用户进程的页表中完成虚拟地址到物理的映射。

运行时动态内存分配

系统在运行时，总是需要动态申请内存空间的，例如使用库函数malloc、使用C++的new描述符，那么申请的内存是哪块内存？

通常在面试中问到new分配的是什么内存空间？答：堆空间。 malloc申请的是什么内存空间？答：自由存储区。局部变量存储在什么空间上？答：栈空间。

那栈空间，堆空间，自由存储区的本质是什么？本质就是用户物理内存池的中物理页。

通过malloc申请的内存需要指定申请的内存大小，前面说的内存池分配内存都按照一个物理页的粒度区分配的，但是当要申请64B的内存空间时如果分配4KB，那必然早造成内存的大量浪费。这时我们需要创建一个新的数据结构arena，每个arena都是一个物理页，被分成两部分，分别是12字节的arena元信息，剩下来的都是大小相等的内存块，图中展示8中arena，分别是内存块大小为16B、32B、64B、128B、256B、512B、1024B和4KB-12B。

那在动态的分配内存时，如何找到分配入口？怎么找到最合适的内存块分配呢？

需要为每一个小的内存块创建一个内存块描述符，我们一共创建了7中小内存，就需要使用一个大小为7的内存块描述符数组表示，一个内存块描述符包含三个信息，内存块大小、一个arena可以小内存块的数量、可供分配的小内存的链表

内存块描述符内存结构
struct mem_bloc_desc{
	uint32_t bolck_size;        //内存块大小
	uint32_t block_per_arena;   //一个arena可以分出多少个大小为block_size的内存块
	struct list free_list;      //可以分配出去的小内存块串成链表
}
arena数据结构
struct arena{
	struct memblock_desc* desc;  //该arena关联到的内存块描述符
	uint32_t cnt;                //该arena可以分配出多少个同类小内存块
	bool large;                  //该arena的大小是否大于1024B，是则不关联任何描述符
}

在加载操作系统和用户进程时，需要给每个进程初始化一个数组大小为7的内存块描述符，当申请一块小内存时，如果存在可供分配的内存，直接将这块内存中删除，当释放时再将这块内存插入到链表中。如果没有可以分配的内存，就到对应的物理内存池中申请一个物理页作为新的arena，将这个arena中的元信息指向它所对应的内存块描述符，然后将空闲的小内存块全部加入可分配链表中