编写自己的内存管理器
内核资料直通车：
CPU执行指令符合28定律，大部分时间都在执行那一少部分指令，这一现象的发现奠定了精简指令集设计的基础。而程序操作的数据也符合类似的定律，只不过不叫28定律，而是叫principle of locality，程序局部性原理。如果我们访问内存中的一个数据A，那么很有可能接下来再次访问到，同时还很有可能访问与数据A相邻的数据B，这分别叫做时间局部性和空间局部性。
如图所示，该程序占据的内存空间只有一少部分在程序执行过程经常用到。有了这个发现重点就来了，既然只用到很少一部分，那么我们能不能把它们集中起来呢？就像这样：
集中起来然后呢？放到哪里呢？当然是放到一种比内存速度更快的存储介质上，这种介质就是我们熟悉的SRAM，普通内存一般是DRAM，这种读写速度更快的介质充当CPU和内存之间的Cache，这就是所谓的缓存。
我们把经常用到的数据放到cache中存储，CPU访问内存时首先查找cache，如果能找到，也就是命中，那么就赚到了，直接返回即可，找不到再去查找内存并更新cache。我们可以看到，有了cache，CPU不再直接与内存打交道了。
但cache的快速读写能力是有代价的，代价就是Money，造价不菲，因此我们不能把内存完全替换成cache的SRAM，那样的计算机你我都是买不起的。因此cache的容量不会很大，但由于程序局部性原理，因此很小的cache也能有很高的命中率，从而带来性能的极大提升，有个词叫四两拨千斤，用到cache这里再合适不过。
虽然小小的cache能带来性能的极大提升，但，这也是有代价的。这个代价出现在写内存时。当CPU需要写内存时该怎么办呢？现在有了cache，CPU不再直接与内存打交道，因此CPU直接写cache，但此时就会有一个问题，那就是cache中的值更新了，但内存中的值还是旧的，这就是所谓的不一致问题，inconsistent.就像下图这样，cache中变量的值是4，但内存中的值是2。
常用 redis 的同学应该很熟悉这个问题，可是你知道吗？这个问题早就在你读这篇文章用的计算设备其包含的CPU中已经遇到并已经解决了。最简单的方法是这样的，当我们更新cache时一并把内存也更新了，这种方法被称为 write-through，很形象吧。可是如果当CPU写cache时，cache中没有相应的内存数据该怎么呢？这就有点麻烦了，首先我们需要把该数据从内存加载到cache中，然后更新cache，再然后更新内存。
这种实现方法虽然简单，但有一个问题，那就是性能问题，在这种方案下写内存就不得不访问内存，上文也提到过CPU和内存可是有很大的速度差异哦，因此这种方案性能比较差。有办法解决吗？答案是肯定的。
这种方法性能差不是因为写内存慢，写内存确实是慢，更重要的原因是CPU在同步等待，因此很自然的，这类问题的统一解法就是把同步改为异步。异步的这种方法是这样的，当CPU写内存时，直接更新cache，然后，注意，更新完cache后CPU就可以认为写内存的操作已经完成了，尽管此时内存中保存的还是旧数据。当包含该数据的cache块被剔除时再更新到内存中，这样CPU更新cache与更新内存就解耦了，也就是说，CPU更新cache后不再等待内存更新，这就是异步，这种方案也被称之为write-back，这种方案相比write-through来说更复杂，但很显然，性能会更好。
现在你应该能看到，添加cache后会带来一系列问题，更不用说cache的替换算法，毕竟cache的容量有限，当cache已满时，增加一项新的数据就要剔除一项旧的数据，那么该剔除谁就是一个非常关键的问题，限于篇幅就不在这里详细讲述了，你可以参考《深入理解操作系统》第7章有关于该策略的讲解。
现代CPU为了增加CPU读写内存性能，已经在CPU和内存之间增加了多级cache，典型的有三级，L1、L2和L3，CPU读内存时首先从L1 cache找起，能找到直接返回，否则就要在L2 cache中找，L2 cache中找不到就要到L3 cache中找，还找不到就不得不访问内存了。因此我们可以看到，现代计算机系统CPU和内存之间其实是有一个cache的层级结构的。
越往上，存储介质速度越快，造价越高容量也越小；越往下，存储介质速度越慢，造价越低但容量也越大。现代操作系统巧妙的利用cache，以最小的代价获得了最大的性能。但是，注意这里的但是，要想获得极致性能是有前提的，那就是程序员写的程序必须具有良好的局部性，充分利用缓存。高性能程序在充分利用缓存这一环节可谓绞尽脑汁煞费苦心，关于这一话题值得单独成篇，关注公众号“码农的荒岛求生”，并回复“todo”，你可以看到之前所有挖坑的进展如何。鉴于cache的重要性，现在增大cache已经成为提升CPU性能的重要因素，因此你去看当今的CPU布局，其很大一部分面积都用在了cache上。
你以为这就完了吗？哈哈，哪有这么容易的，否则也不会是终面题目了。那么当CPU读写内存时除了面临上述问题外还需要处理哪些问题呢？
当摩尔定律渐渐失效后鸡贼的人类换了另一种提高CPU性能的方法，既然单个CPU性能不好提升了，我们还可以堆数量啊，这样，CPU进入多核时代，程序员开始进入苦逼时代。拥有一堆核心的CPU其实是没什么用的，关键需要有配套的多线程程序才能真正发挥多核的威力，但写过多线程程序的程序员都知道，能写出来不容易，能写出来并且能正确运行更不容易，关于多线程与多线程编程的详细阐述请参见《深入理解操作系统》第5、6两章(关注公众号“码农的荒岛求生”并回复“操作系统”)。CPU开始拥有多个核心后不但苦逼了软件工程师，硬件工程师也不能幸免。前文提到过，为提高CPU 访存性能，CPU和内存之间会有一个层cache，但当CPU有多个核心后新的问题来了：
现在假设内存中有一变量X，初始值为2。系统中有两个CPU核心C1和C2，现在C1和C2要分别读取内存中X的值，根据cache的工作原理，首次读取X不能命中cache，因此从内存中读取到X后更新相应的cache，现在C1 cache和C2 cache中都有变量X了，其值都是2。接下来C1需要对X执行+2操作，同样根据cache的工作原理，C1从cache中拿到X的值+2后更新cache，在然后更新内存，此时C1 cache和内存中的X值都变为了4。
然后C2也许需要对X执行加法操作，假设需要+4，同样根据cache的工作原理，C2从cache中拿到X的值+4后更新cache，此时cache中的值变为了6（2+4），再更新内存，此时C2 cache和内存中的X值都变为了6。
看出问题在哪里了吗？一个初始值为2的变量，在分别+2和+4后正确的结果应该是2+2+4 = 8，但从上图可以看出内存中X的值却为6，问题出在哪了呢？
有的同学可能已经发现了，问题出在了内存中一个X变量在C1和C2的cache中有共计两个副本，当C1更新cache时没有同步修改C2 cache中X的值。
解决方法是什么呢？显然，如果一个cache中待更新的变量同样存在于其它核心的cache，那么你需要一并将其它cache也更新好。现在你应该看到，CPU更新变量时不再简单的只关心自己的cache和内存，你还需要知道这个变量是不是同样存在于其它核心中的cache，如果存在需要一并更新。当然，这还只是简单的读，写就更加复杂了，实际上，现代CPU中有一套协议来专门维护缓存的一致性，比较经典的包括MESI协议等。为什么程序员需要关心这个问题呢？原因很简单，你最好写出对cache一致性协议友好的程序，因为cache频繁维护一致性也是有性能代价的。同样的，限于篇幅，这个话题不再详细阐述，该主题同样值得单独成篇，敬请期待。
怎么样？到目前为止，是不是CPU读写内存没有看上去那么简单？现代计算机中CPU和内存之间有多级cache，CPU读写内存时不但要维护cache和内存的一致性，同样需要维护多核间cache的一致性。
你以为这就完了，NONO，最大的谜团其实是接下来要讲的。
现代程序员写程序基本上不需要关心内存是不是足够这个问题，但这个问题在远古时代绝对是困扰程序员的一大难题。如果你去想一想，其实现代计算机内存也没有足够大的让我们随便申请的地步，但是你在写程序时是不是基本上没有考虑过内存不足该怎么办？为什么我们在内存资源依然处于匮乏的现代可以做到申请内存时却进入内存极大丰富的共产主义理想社会了呢？原来这背后的功臣是我们熟悉的操作系统。操作系统对每个进程都维护一个假象，即，每个进程独占系统内存资源；同时给程序员一个承诺，让程序员可以认为在写程序时有一大块连续的内存可以使用。这当然是不可能不现实的，因此操作系统给进程的地址空间必然不是真的，但我们又不好将其称之为“假的地址空间”，这会让人误以为计算机科学界里骗子横行，因此就换了一个好听的名字，虚拟内存，一个“假的地址空间”更高级的叫法。进程其实一直活在操作系统精心维护的幻觉当中，就像《盗梦空间》一样，
从这个角度看，其实最擅长包装的是计算机科学界，哦，对了，他们不但擅长包装还擅长抽象。
CPU真的是很傻很天真的存在。上一节讲的操作系统施加的障眼法把CPU也蒙在鼓里。CPU执行机器指令时，指令指示CPU从内存地址A中取出数据，然后CPU执行机器指令时下发命令：“给我从地址A中取出数据”，尽管真的能从地址A中取出数据，但这个地址A不是真的，不是真的，不是真的。因为这个地址A属于虚拟内存，也就是那个“假的地址空间”，现代CPU内部有一个叫做MMU的模块将这假的地址A转换为真的地址B，将地址A转换为真实的地址B之后才是本文之前讲述的关于cache的那一部分。
你以为这终于应该讲完了吧！NONO！CPU给出内存地址，此后该地址被转为真正的物理内存地址，接下来查L1 cache，L1 cache不命中查L2 cache，L2 cache不命中查L3 cache，L3 cache不能命中查内存。各单位注意，各单位注意，到查内存时还不算完，现在有了虚拟内存，内存其实也是一层cache，是磁盘的cache，也就是说查内存也有可能不会命中，因为内存中的数据可能被虚拟内存系统放到磁盘中了，如果内存也不能命中就要查磁盘。So crazy，限于篇幅这个过程不再展开，《深入理解操作系统》第七章有完整的讲述。至此，CPU读写内存时完整的过程阐述完毕。
现在你还认为CPU读写内存非常简单吗？这一过程涉及到的硬件以及硬件逻辑包括：L1 cache、L2 cache、L3 cache、多核缓存一致性协议、MMU、内存、磁盘；软件主要包括操作系统。这一看似简单的操作涉及几乎所有计算机系统中的核心组件，需要软件以及硬件密切配合才能完成。这个过程给程序员的启示是：1)，现代计算机系统是非常复杂的；2),你需要写出对cache友好的程序。
内存自己怎么写
现在我们已经明确要实现什么以及衡量其好坏的标准，接下来我们就要去设计实现细节了，让我们把任务拆分一下，怎么拆分呢？
我们可以自己想一下从内存的申请到释放需要哪些细节。
申请内存时，我们需要在内存中找到一块大小合适的空闲内存分配出去，那么我们怎么知道有哪些内存块是空闲的呢？
因此，第一个实现细节出现了，我们需要把内存块用某种方式组织起来，这样我们才能追踪到每一块内存的分配状态。
现在空闲内存块组织好了，那么一次内存申请可能有很多空闲内存块满足要求，那么我们该选择哪一个空闲内存块分配给用户呢？
因此，第二个实现细节出现了，我们该选择什么样的空闲内存块给到用户。
接下来我们找到了一块大小合适的内存块，假设用户需要16个字节，而我们找到的这块空闲内存块大小为32字节，那么将16字节分配给用户后还剩下16字节，这剩下的内存该怎么处理呢？
因此，第三个实现细节出现了，分配出去内存后，空闲内存块剩余的空间该怎么处理？
最后，分配给用户的内存使用完毕，这是第四个细节出现了，我们该怎么处理用户还给我们的内存呢？
以上四个问题是任何一个内存分配器必须要回答的，接下来我们就一一解决这些问题，解决完这些问题后一个崭新的内存分配器就诞生啦。
内存自己怎么写
至此，我们的内存分配器就已经设计完毕了。
我们的简单内存分配器采用了First Fit分配算法；找到一个满足要求的内存块后会进行切分，剩下的作为新的内存块；同时当释放内存时会立即合并相邻的空闲内存块，同时为加快合并速度，我们引入了Donald Knuth的设计方法，为每个内存块增加footer信息。
这样，我们自己实现的内存分配就可以运行起来了，可以真正的申请和释放内存。
本文从0到1实现了一个简单的内存分配器，但不希望这里的阐述给大家留下内存分配器实现很简单的印象，实际上本文实现的内存分配器还有大量的优化空间，同时我们也没有考虑线程安全问题，但这些都不是本文的目的。
本文的目的在于把内存分配器的本质告诉大家，对于想理解内存分配器实现原理的同学来说这些已经足够了，而对于要编写高性能程序的同学来说实现自己的内存池是必不可少的，内存池实现也离不开这里的讨论。
希望本文对大家理解内存分配器有帮助。
内存自己怎么写
有了上图，我们就可以将堆这块内存区域组织起来并进行内存分配与释放了，如图所示：
在这里我们的堆区还很小，每一方框代表4字节，其中红色区域表示已经分配出去的，灰色区域表示空闲内存，每一块内存都有一个header，用带斜线的方框表示，比如16/1，就表示该内存块大小是16字节，1表示已经分配出去了；而32/0表示该内存块大小是32字节，0表示该内存块当前空闲。
细心的同学可能会问，那最后一个方框0/1表示什么呢？原来，我们需要某种特殊标记来告诉我们的内存分配器是不是已经到末尾了，这就是最后4字节的作用。
通过引入header我们就能知道每一个内存块的大小，从而可以很方便的遍历整个堆区。遍历方法很简单，因为我们知道每一块的大小，那么从当前的位置加上当前块的大小就是下一个内存块的起始位置，如图所示：
通过每一个header的最后一个bit位就能知道每一块内存是空闲的还是已经分配出去了，这样我们就能追踪到每一个内存块的分配信息，因此上文提到的第一个问题解决了。
接下来我们看第二个问题。
内存自己怎么写
到目前为止，我们的malloc已经能够处理内存分配请求了，还差最后的内存释放。
内存释放和我们想象的不太一样，该过程并不比前几个环节简单。
首先，释放内存时不需要指定大小，原因很简单，因为我们从要释放的指针地址上移就能知道该内存块的所有信息：
其次我们要考虑到的关键一点就在于，与被释放的内存块相邻的内存块可能也是空闲的。如果释放一块内存后我们仅仅简单的将其标志位置为空闲，那么可能会出现下面的场景：
从图中我们可以看到，被释放内存的下一个内存块也是空闲的，如果我们仅仅将这16个字节的内存块标记为空闲的话，那么当下一次申请20字节时图中的这两个内存块都不能满足要求，尽管这两个空闲内存块的总数要超过20字节。
因此一种更好的方法是当应用程序向我们的malloc释放内存时，我们查看一下相邻的内存块是否是空闲的，如果是空闲的话我们需要合并空闲内存块，就像这样：
在这里我们又面临一个新的决策，那就是释放内存时我们要立即去检查能否够合并相邻空闲内存块吗？还是说我们可以推迟一段时间，推迟到下一次分配内存找不到满足要的空闲内存块时再合并相邻空闲内存块。
释放内存时立即合并空闲内存块相对简单，但每次释放内存时将引入合并内存块的开销，如果应用程序总是释放12字节然后申请12字节，然后在释放12字节等等这样重复的模式：
那么这种内存使用模式对立即合并空闲内存块这种策略非常不友好，我们的内存分配器会有很多的无用功。但这种策略最为简单，在这里我们依然选择使用这种简单的策略。
实际上我们需要意识到，实际使用的内存分配器都会有某种推迟合并空闲内存块的策略。
内存自己怎么写
实际上，现在这个年代的程序员是很幸福的，程序员很少去关心内存分配的问题。作为程序员，可以简单的认为我们的程序独占内存，注意，是独占哦。
写程序时你从来没有关心过如果我们的程序占用过多内存会不会影响到其它程序，我们可以简单的认为每个程序(进程)独占4G内存(32位操作系统)，即使我们的物理内存512M。不信你可以去试试，在即使只有512M大小的内存上你依然可以申请到2G内存来使用，可这是为什么呢？关于这个问题我们在后续文章中会详细阐述。
总之，程序员可以放心的认为我们的程序运行起来后在内存中是这样的：
作为程序员我们应该知道，内存动态申请和释放都发生在堆区，heap。
我们使用的malloc或者C++中的new申请内存时，就是从堆区这个区域中申请的。
接下来我们就要自己管理堆区这个内存区域。
堆区这个区域实际上非常简单，真的是非常简单，你可以将其看做一大数组，就像这样：
从内存分配器的角度看，内存分配器根本不管你是整数、浮点数、链表、二叉树等数据结构、还是对象、结构体等这些花哨的概念，在内存分配器眼里不过就是一个内存块，这些内存块中可以装入原生的字节序列，申请者拿到该内存块后可以塑造成整数、浮点数、链表、二叉树等数据结构以及对象、结构体等。
我们要在这片内存上解决两个问题：
这是内存分配器要解决的两个最核心的问题，接下来我们先去停车场看看能找到什么启示。
