本文主要介绍内存的基本概念以及操作系统的内存管理算法。
1. 记忆的基本概念
内存是计算机系统中除了处理器之外最重要的资源。它用于存储当前正在执行的程序和数据。内存是相对于 CPU 而言的。 CPU可以直接寻址的存储空间称为内存，CPU需要通过驱动程序访问的存储空间称为外部存储器。
2. ROM&RAM&闪存
存储器一般采用半导体存储单元，分为只读存储器（ROM、ReadOnly Mem或y）和随机存储器（RAM、 Random Accessaccess Memory）ROM一般只能读不能写，断电后里面的数据也不会丢失。 RAM可以读写，但断电后其中的数据会丢失。内存一般指的是RAM。
ROM一般用在嵌入式系统中，用来存储BootLoader和操作系统或程序代码或直接用作硬盘。近年来，闪存（Flash）已经完全取代了嵌入式系统中的ROM。它结合了ROM和RAM的优点。它不仅具有电子可擦除而且具有编程功能，并且断电时数据不会丢失，并且可以快速读取数据。
3、两种内存管理方式： 内存管理模块管理系统的内存资源。它是操作系统的核心模块之一。主要包括内存的初始化、分配和释放。
根据分配的内存是否连续，可以分为两类。
连续内存管理是不断地给进程分配内存空间，但这种分配方式容易产生内存碎片（碎片是很难使用的空闲内存，通常是小内存），降低内存利用率。连续内存管理主要分为两种：单一连续内存管理和分区内存管理。
非连续内存管理将进程分散到多个不连续的内存空间中，可以减少内存碎片，获得更高的内存利用率。如果分配的基本单位是页，则称为分页内存管理；如果基本单位是段，则称为分段内存管理。
当前的操作系统一般采用非连续内存管理。但由于分配粒度较大，对于内存较小的嵌入式系统一般采用连续内存管理。本文主要介绍嵌入式系统中常用的连续内存管理的分区内存管理。
4.分区内存管理分区内存管理分为固定分区和动态分区。固定隔断
内存被预先划分为若干个固定大小的区域。分区大小可以相等或不相等。固定分区很容易实现，但是会造成分区内碎片的浪费，而且分区总数是固定的，这就限制了可以并发执行的进程数量。
动态分区根据进程的实际需要，动态地为进程分配所需的内存。
5.动态分区内存管理运行机制
动态分区管理一般采用空闲链表方式，基于双向链表来保存空闲分区。对于初始状态，整个内存块将作为一个大的空闲分区添加到空闲列表中。当一个进程申请内存时，它会从这个空闲链表中找到一个大小符合要求的空闲分区。
如果分区大于所需内存，则从分区中分割出所需大小的内存交给进程，并将分割后的内存从空闲链表中移除，剩余内存仍挂在空闲链表中列表。自由分区。
数据结构
有很多数据结构可以实现自由链表方法。这里我们介绍一个更简单的数据结构。每个空闲分区的数据结构包含该分区的大小以及指向上一个分区和下一个分区的指针，这样每个空闲分区就可以链接成一个双向链表。
内存分配算法First Fit（第一种适配算法） First Fit要求空闲分区链表按照地址从小到大的顺序链接起来。分配内存时，从链表中第一个空闲分区开始查找，将第一个符合要求的空闲分区分配给进程。
Next Fit（循环第一适应算法） Next Fit是从First Fit算法演变而来的。分配内存时，会从上次刚刚分配的下一个空闲分区开始查找，直到找到符合要求的空闲分区。搜索会采用循环搜索的方式，即如果直到链表的最后一个空闲分区仍不能满足要求，则返回到第一个空闲分区并开始搜索。
Best Fit（最佳拟合算法）从所有空闲分区中找出满足要求的最小空闲分区。为了加快搜索速度，Best Fit算法会将所有空闲分区按照容量从小到大的顺序链接起来，这样第一次找到的满足大小要求的内存一定是最小的空闲分区。 Worst Fit（最差适应度算法）从所有空闲分区中找出满足要求的最大空闲分区。
最差拟合算法按容量降序链接所有空闲分区。两级隔离拟合（TLSF）使用两级链表来管理空闲内存并对空闲分区大小进行分类。每个类别由一个空闲链表表示，空闲内存大小在特定值或范围内。空闲链表有多个，因此使用一个索引链表来管理这些空闲链表。链表中的每一项对应一种类型的空闲链表，并记录该类型的空闲链表的头指针。
第一级链表将空闲内存块的大小按照2的幂进行分类。第二级链表是对每一类空闲内存块按照一定范围进行具体的线性分段。例如25被分为4个内存区间23或8[25, 25+8], [25+8, 25+16), [25+16, 25+24], [25+24, 25+32 );
类别216分为4个小区间有214[216, 216+214)、[216+214, 216+2*214)、[216+2*214, 216+3*214]、[216+3* 214、216+4*214）。同时，为了快速检索空闲块。
每级链表都有一个位图，用于标记对应链表中是否有空闲块。例如，第一层位图的最后三位是010，表示25的内存区间有空闲块。对应的第二层位图是0100，表示这个区间[25+16]有空闲块，25+24]，也就是下面的52Byte。 Buddysystems（好友算法）
分离拟合算法的一种变体，具有更好的内存分割和回收合并效率。 buddy算法有很多种，比如BinaryBuddies、FibonacciBuddies等。BinaryBuddies是最简单也是最流行的一种，它根据分区的大小对所有空闲分区进行分类。每个类别都是相同大小的空闲分区的集合，用空闲双向链表表示。
BinaryBuddies中的所有内存分区都是2的幂。因为无论是已分配分区还是空闲分区，其大小都是2的幂。即使进程请求的内存小于分配给它的内存块，多余的内存也会不会被拆分出来供其他进程使用。这很容易造成内部碎片。当进程申请大小为n的内存时，分配步骤为：
1. 计算 i 值，使得 2i-1
2、在空闲分区大小为2i的空闲链表中查找
3. 如果找到空闲块，则将其分配给进程
4、如果2i的空闲分区已经用完，则在分区大小为2i+1的空闲链表中查找
5. 如果存在 2i+1 的空闲分区，则将该空闲块分成两个相等的分区。两个分区是一对伙伴，其中一个分配给进程，另一个挂在空闲链表中，分区大小为2i。
6、如果2i+1的空闲分区仍然不存在，则继续寻找大小为2i+2的空闲分区。如果找到，则需要进行两次拆分。第一个分区被分成两个大小为 2i+1 的分区。一个分区挂在大小为 2i+1 的空闲链表中。另一个分区进一步分为两个大小为 2i 的空闲分区，其中一个分配给进程。 ，另一块挂在大小为 2i
7、如果找不到2i+2的空闲分区，则继续寻找2i+3，以此类推
内存回收时，如果要回收的内存块和空闲链表中的一块内存是伙伴，它们就会合并成一个更大的内存块。如果合并的内存块在空闲链表中有伙伴，则继续Merge，直到无法合并为止，将合并的内存块挂到对应的空闲链表中。
编辑：jq
