大家好！数据结构与算法这一讲
我们学习第十二章，高级数据结构中的
存储管理。我们是把存储管理当作
高级线性结构的应用。那其中会涉及到 线性表还有广义表的内容。
那内存里面最基本的问题呢，
就是分配和回收。我们分配这些内存的单元的时候
有可能会产生一些碎片。这个包括内部的和外部的碎片。
对碎片问题呢我们可能会需要用存储压缩技术来处理。
另外，如果我们对内存的这个需求特别大，程序运行了很长时间以后，
有可能这个系统呢分不出相应的内存单元的时候呢，
那也许我们要动用这个失败策略的
这么一个内存的组织，也就是说扫描整个这个内存，
看一下哪一些无用单元在那闲挂着。那我们就把这些无用单元呢
进行标记，而且呢还用到前面的存储压缩，然后我们得到一个比较完整的存储单元
来给程序使用。 那首先呢，我们来看一个最简单的情况，就是可利用空间表。
这个呢，是把整个存储器看作一个定长块组成的数组。
那这个技术其实在我们自己编程的时候也是可以用的。
也就是说如果我是经常需要new， delete这样的指针。
如果我每一次都是从内存里面呢去new那么一小块，然后delete一小块
那这个操作呢，会太频繁，效率会低，那我如果知道
我有多大的这个需求量，我一次可以申请一个比较完整的大空间。
然后后面呢我就自己把这个空间组织起来。需要一块的时候
从里面拿。然后我退回的时候呢也退回到我这个存储值。
那我们来看一下这个可利用空间表的这么一个图示，
首先申请一大块，然后呢我这里面呢细分成一小块。 然后我利用这个棧结构把它们穿起来。
那在运行到一定的时候呢，可以看到存储区域里面呢有些块是被占用，
然后有些块是这个空闲的。这种白的颜色。那我们这些空闲块呢，
其实是一直有avail指针呢给指向。
然后呢我就把这些空闲块组织起来。虽然说他们
在物理上并不相连，但是在逻辑上呢我给它穿成一个
单面的结构。然后我需要的时候呢我从这个空闲块的这个表头取数据。
退回来呢也回到这个空闲块的表头。当然它实际上就是一种链式的棧结构。
那我们来看它的实现，首先呢就是我们需要
对new和delete这两个函数呢进行一个重载， 那我们看一下我们怎么改写new，
首先我就是看一下这个avail这个表是不是空？
如果是空呢就是现在需要从系统里面申请一大块连续区域，
然后给avail作为后面的使用。
那如果不空的情况下呢，那我就是可以从这个avail这个表头
取出一个元素，然后呢，这个指针往后面指一位。
delete的时候呢就是一个逆过程啦，元素p我释放它的空间呢，
我给它释放到这个avail表里头，我把它作为一个新的表头指向原来的那个表头。
然后呢这个表头呢也是挪到刚删除的那个p，
其实这就是一个链式栈的一个结构。
然后我们要注意呢，
对这样的new和delete进行重载以后，如果要用系统的delete和new，
那我要用这样的双冒号来强制的使用一下，特别是
当我整个这个可利用空间表它所占的这个程序
我是怎么样退出，那我要把这段空间呢返回给内存的时候，
那我要强制的去delete我这个整个可利用空间表。
更多的情况呢就是我们是变长的这样呢数据请求，
那如果是我们还把这个内存看作是连续的一大块，
那每次请求的时候需要多少我给你割下来多少。
那运行到一段时间以后呢，我们其实整个这个表里面就是
有大大小小的各种长度的这样呢的子序列。不同的长度的这些空闲块呢，
我们可以用分离的这样的可利用空间表把它组织起来。
然后这个块呢其实我们也不一定是必须是等长的。
我可以是一定范围内的这样的块，我组织在一个表里面。
这样的话呢，我们在申请空间的时候就能够知道
从哪一个这样的可利用空间表头去找相应的空闲块，然后分给我来使用。
那对于这种， 变长块的分配和回收，那我们注意呢
就是分配的时候，我找到一个合适块，有可能
是大于你的请求的，那我们
剩下的那一部分呢，我还可以把它截取了以后，
再排回到可利用空间表的合适的可利用的链里面，然后等着以后来使用。
那我们在回收的时候呢，就需要注意我是不是能够跟它的物理相邻的块合并，
然后形成更大的空闲块，因为这个
更大的这种连续块呢我们能够支持一些
对数据要求连续更大块的这样的情况。
我们来看一下空闲块的数据结构。
整个这个块我没有别的人来使用它，那我是可以
把它使用起来，存放我自己需要的信息。那哪些信息是需要的呢？ 首先我要有一个标记，它是不是空闲块。
另外呢，就是这个块，它的长度是多少？那我们这个首尾都需要进行一个标记。
因为当有邻居释放的时候呢，那这个
左邻居或者是右邻居，它都要看一下如果我这个块是空闲块，
它跟我合并的时候它需要推算出，我这个头是多少，或者是说这个尾是多少。所以这首尾的
长度值呢都是需要存的。
另外呢这个空闲块，我不能是游离的，
放在这样的一个内存区域里面，等着你去便利去找。
那我们还是需要给它组织起来。那这个组织呢，
我们最简单的情况就是可以把它放在一个列表里面，
那我就是它的前区是谁，它的后继是谁。我能够把它组织起来。
那这种链表的组织呢，我也可以是
根据它的这个物理的地址，然后排一个序，这样组织起来。
那我也可以是根据这个空闲块的大小来排序组织起来。当然我们
还可以用BST的形式来组织或者甚至用散列来组织。
那就是需要看你需要什么样的信息，然后呢我们
把这些相应的信息呢，尽量的放在这个空闲块里面。
那对于已分配块呢，它总体来说是由占用它的那个函数，
来使用的。只需要呢标记一些最简单的信息。
这个最简单的信息它的标记最主要的是首先，
有一个占用的标记位。这样的话呢，当别的这个空闲块
进来它想合并的时候，它不会随便把我这个已占用块给合并。
另外呢就是块的长度， 那这个长度呢主要是当我们这一块要返回给这个内存管理器的时候呢
那我知道我这个块它长度是多少。我们就可以加入到
相应长的那样一个空闲的子链里面。
当然，我们返回的时候呢，也可能会需要对它进行一个
合并，就是看看它的左右邻居是不是可以跟它合并。那合并了以后的新的块长，
当然也是要跟我们这个块长的标记是相关的。
在存储分配里面呢，它有一个碎片问题，
这个碎片呢，有两种，一种呢就是内部碎片，
这个内部碎片主要的原因是产生于，在很多存储管理系统里面呢，
它都有这样的一个对齐的要求，比如说八字节对齐啊，或者说四字节对齐啊，这样的一些要求。
那这样的话呢，也需要多给它分配一些这样的空间，
然后呢使得我分出的这个区域呢，它能够很好的对齐。
另外还有，我们在一些特殊的存储系统里面比如说
像伙伴系统，每次分的时候呢就是大于等于你这个存储要求的
2的k次方这样大小的一个存储单元。
那显然我不是说所有的这个存储要求都正好是2的k次方
那剩下的呢那就是多余的这样的内部的碎片。
那外部的碎片呢就是因为我们整个这个分配和回收呢
是不断的动态的进行的，返回的时候呢可能有那么一块区域
那将来这块区域呢又能够分出去，那分出去的时候有可能
大于它的需求，那就会被切分，然后剩余一小块在那儿
那有时候剩的这个小块太小这将来永远分不出去了
那这种情况我们可能就需要进行一些存储的压缩。
分配呢我们主要是有三种顺序适配的方案
当然相应于顺序适配，我们还有一些其它的这种分配方案
比如说像伙伴系统里面去找到它的一个相应的这个大小的伙伴的块
然后呢再去对它进行分配，那如果是这个块太大
那我们可能就可以去把它分成一个合适这个块请求的
2的k次方那个最紧的那个k那个块
那那就是其它的这种分配方式。那我们顺序分配呢其实本质上
就是说我这些块呢我可能是组织在这样的一个链里面
然后呢我在找的时候是顺着顺着来看哪一个块 合适我，然后我分配出合适的这么一个子块。
那我们来看一下这几种分配方案。首先就是一个叫做首先适配的这么一个方案。
在这个方案里面呢我们这个例子其实是有三个这样的
空闲块，这个空闲块它们物理上并不是邻居
那它只是说逻辑上我们是先后看到这几块，那其实我是把它放在一个线性表里面
对于这样的几个请求序列，首先看到的是1200这个块，那我是直接给它
在里面切分，然后剩余的呢留着再继续作为空闲块
然后再500又接着切分，然后再900从1000里面切。
然后2200呢它就正好就可以切出来了，那我们就完成了这个分配。
那再来看最佳适配呢就是想，誒你刚才这个首先适配
你也许不是最合算的，那我如果能够找到一个适合你这个请求的
最小的那个空闲块，然后我切出来，然后剩下来的还在那儿呆着。
那我是不是会能够得到更好的空间利用效果呢？ 那我们来看一下这个例子。
那我们切分了首先找到1000，然后只剩下400，那分不了给500
那我们接着找1200再分，那又是剩一个小块，然后后面900用不了
然后900分完以后呢 那我们最后可以看到只剩下这个最大的是2100
这个块，那这个2200呢它就分配不了了。
因此其实我们可以看到最佳适配它的问题就是
我现在是说精打细算的去考虑，但是呢你有可能
把本来就是不太大的这样的块，你这样切了以后呢
切出了一些外部的小碎片，这个碎片呢太小了， 我后面的请求呢
都满足不了，我就分不出去，那总体来看
现在说，这里面可用的这个空间
加起来的和大于你的需求，但是呢我还是不能分免去的这两千二这么大小的块。
那因此人们就想那我换一种方法
我就是先从这个最大块里面去切，这样的话呢我们就能够
减少这个外部的碎片，对这样的一个请求的
序列呢我首先从最大的这个3000里面切，我希望切完以后剩下的这个
还足够大，能够满足其它的需求接着再去切，切完以后到这个
在接着要分配2200的时候呢
那前面因为它们物理上都不连续，所以我找不到合适的地方
来放这个2200这么一块区域
我们再来看在回收的时候
怎么来考虑这个相邻块的合并问题。
那假设中间这个区域它是回收了
那我看它的这个左邻和右邻因为我自己知道我的物理存储地址是多少
那我这边往前减一下呢就知道前面的这个是什么样的
然后往后面加一下呢知道后面的是什么样的，如果是说它的前后都是
被占用了，那我就不能合并，我把自己作为一个新的空闲块
加到我的这个空闲链里边去。如果说它的这个左右都可以
合并 那相当于我原来这个空闲链里面是有两个
独立的这个空闲块，那现在我们三个一起合并了以后呢
就减少了一个空闲块。那我们要删掉一个而且呢要把剩下的那一个呢
它的这个长度变成这三块的和。
还有一种情况呢就是只有左边的可以合并，右边的不能
或者是说就右边的可以合并那左边的不能，那么在这两种
情况下呢都是我们的空闲块的个数是没有发生变化，
但是呢它的大小需要修改，你也许变得更大了
要换到一个分离的一个空闲块子链里面去。
我们再来看如果是内存，我实在是没有东西可分了
那怎么办呢？因为我们前面提到过有一些外部碎片的问题。
那这个时候我们就可以有两种方案了，第一种呢
我什么也不做，就告诉你我是失败了，你自己看着办。
那第二种情况呢就是我们来动用一个叫做
失败策略，那最主要的是进行存储压缩。
也就是说我有那么多可能的外部碎片，那我是不是
能够把这些已分配的块挤一挤，挤到最前端，然后
把这些空闲块呢就都搁在后面，那可以再形成更大的块
那继续支持我们的这种内存的请求。我们来看一下这个压缩的
这么一个事例。这个压缩呢一般来说呢就是你这个空间实在是不够用了
或者是说你后面进行了这种悬挂单元的这么一个收集整理，然后你希望给它
挤出更大的这样的连续的可分配块的时候才动用。
那这个动用呢我们首先呢就是要有一个叫做
句柄的技术，我每一个这个
程序的话呢我都是我的这么一个内存块，我只是一个相对的一个存储
位置，其它的这些变量啊这些东西呢都是只得在我这个存储块里面的偏移。
那我需要压缩的时候呢，我是对整个这个程序块里面的这些相应的数据呢
我进行相应的这个移动，那包括这个
变量啊还有一些数据啊都是一起来移动。
那移动的时候呢，我只是根据
你的这个压缩需求你给我一个新的位置，然后我只是把这个句柄呢
对应新的位置，那程序内部的那些变量其实是不需要修改的。
那这种存储压缩呢我们能够比较高效的进行。
那压缩之前我们可能是这么一个状况，就是有很多这种外部的小碎片。
那压缩之后呢我们就得到了一大片的这个存储的区域。
其实还有一种情况呢就是如果整个存储的区域呢有可能
连这个外部碎片我也都用过了压缩过了，但是我觉得还是不够用，
那这个时候有可能你的这个存储单元的浪费
是因为程序员忘了给你delete这个空间，
忘了把这个没有用的空间给回收，那这个时候我们就要
来动用一个终极的手段就是无用单元的收集
那其实呢我就是来编立这个程序它所指向的这个内存区域，
然后我每一个程序都把自己负责的这个内存区域呢标记一下
那所有的这个标记完成以后呢那些没被标记的那可能就是说这个程序死了以后呢
那没有人管的这个内存，那这种情况呢我们就可以把
这样的没人管的区域呢我就是当作是这种外部的碎片我可以回收。
那我们刚才说的这样的程序来编立自己的所使用的内存这个工作呢
其实就对应到我们前面介绍过的广义表，它其实这种内存的引用
它本质上是一种广义表的这个结构，那我们这个标记呢就是相当于广义表的一次便利，
那如果没有被便利到，那这个单元呢就是可以被回收
那回收呢其实就是用我们刚才的在那个存储压缩
我能够把这些碎片呢集合在一起，然后呢供后面的那些程序来使用。
最后给大家留几个思考题。
大家考虑一下，首先适配、最佳适配和最差适配这几种顺序适配的方案
它们各有什么特点以及它们的适用场景是什么样的？
另外呢这几个方案里面是哪一种特别容易产生外部的碎片？第二个问题呢就是
对于空闲块我们应该怎么样更有效的去组织？
那前面其实呢我们也都说到过空闲块的一些简单的
组织方式，例如用链表，用链式的这样的形式
那其实对于空闲块我们最主要的就是我能快速的找到 合适大小的块
那还有一种场景呢可能是我们能够要快速的找到它的
邻居的这种块，所谓邻居是物理上相邻的这些块。
除了这个线性结构来组织以外我们是不是可以用树形的结构来组织。例如
红黑树还有石碑树啊等等
大家可以去看一下另一种系统里的开元代码。
然后看一下它的内存组织管理是怎么样去实现的。
谢谢大家。