动态存储管理

缘起

在学习数据结构的过程中，每一种数据结构我们都介绍了它们在内存中的映像. 但那是借助高级语言（C/C++）实现的. 高级语言的特点是使用变量标识符取代了低级语言(汇编)的内存地址. 程序员已经不需要和内存地址直接打交道了. 而这些变量对应的标识符都是由编译器在编译或者执行的时候进行内存分配的. 因此内存管理不论对于操作系统还是编译器而言，都是一个极为重要的问题(内存管理是操作系统的基本问题之一). 我们来简易探究一下.

分析

先来看看动态内存管理的应用场景.

显然，不管是什么样的动态存储管理系统，在刚开工的时候，整块内存就是一个大的空闲块（在编译器中称之为”堆（Heap）”）. 随着系统进程和用户进程的并起，它们纷纷提出内存申请, 则编译器或者操作系统响应请求并一一分配内存给相应进程使用. 比如我们假设每次分配内存从地地址开始. 则经过若干次分配之后，堆变成如下的样子

但是有些进程运行完毕之后，操作系统必须要回收其内存, 则一段时间之后，堆变成了如下的样子

如果此时再来一个进程，要申请内存空间的话，我该拿哪块内存分配给这个进程呢? 显然有以下两种方案

  1. 不理会已经空余出来的内存, 继续往高地址段分配内存，直至再也无法继续下去，则重新组织内存. 将空闲内存合并成大块的内存（这个过程叫做回收），再分配给该进程
  2. 每当一个进程结束，内存空闲，就要考虑回收内存

所以总结上面的讨论，我们可以得出如下结论

动态内存管理要考虑的两个基本问题就是 1. 内存的分配 2. 内存的回收

显然，如果仅仅按照上面的1和2进回收的话，效率很低的. 所以我们想到了空间换时间——也就是使用可用空间链表来维护可用内存块. （很多数据库引擎（例如mysql的innodb）甚至是操作系统，用的就是这种办法）.

即可用空间链表（下简称ASL available space linkedlist）长下面这个样子

也即刻画了下面的内存使用情况

或者用图示

ASL的每个节点的数据结构是

1
2
3
4
5
6
typedef struct MemoryBlock{
    int tag = 0; // 0表示空闲，1表示占用
    int size; // 表示内存块的大小
    MemoryBlock *nxt; // 指向ASL下一个节点的指针变量
    char space[INITIALSIZE]; // 占据的内存块空间，INITIALSIZE是初始内存的大小
} MemoryBlock, *Space; // Space指针指向了可用列表的首地址

也就是说，目前的内存块的结构是

​ 图1

那么第一个基本问题就好解决了，即内存分配问题. 假设一个进程P申请M内存， 至少有以下三种方案

  1. 首次分配法

    遍历ASL, 遇到第一个>=M的ASL节点first，就将M大小的内存分配给P. 并修改first的size域，如果size域归零，则从ASL中移除first节点.

  2. 差距最小分配法

    首先ASL需要按照size域大小升序排序，然后遍历ASL, 找到第一个size域>=M的ASL节点first，分配M内存出去，然后修改first的size域（如果归零的话，直接从ASL中移除first节点，否则的话，需要卸下first，重新找位置插入, 毕竟要维护升序嘛~）

  3. 差距最大分配法

    首先ASL需要按照size域降序排序，然后只需要取出第一个节点first（这点比较好——无需遍历ASL），如果其size>=M, 则分配M内存出去并修改first的size域. 然后卸下first,重新找到位置插入.

至于回收的基本问题，我们至少可以做到

  1. 对于首次分配法，直接将空闲内存块头插到ASL
  2. 对于差距最小分配法，需要找到合适位置插入
  3. 对于差距最大分配法，需要找到合适位置插入

所以我们不难得出以下结论

首次分配法只需要在分配的时候遍历ASL，差距最大分配法只需在回收的时候遍历ASL，而差距最小分配法在分配和回收的时候都需要遍历ASL. 从效率上看，因为ASL不是双向链表，所以差距最小分配法的性能最差. 但是应用场景是

  1. 差距最小分配法因为总拿最恰如其分的内存块来分配, 所以最后ASL上节点之间size域的差距很大. 所以差距最小分配法适用于进程请求内存分布比较两极分化的情况.（即方差较大的情形）
  2. 差距最大分配法因为总拿最大的那块内存来消费，所以最后ASL上节点之间size域的差距比较小，所以差距最大分配法适用于进程请求内存分布比较集中（即方差较小）的情况
  3. 首次分配法介于1和2，适用于操作系统对于进程申请内存的分布尚无知的应用场景.

所以不难臆测一下操作系统分配内存算法的形式——应该是启发式的, 一开始是首次分配法，系统运行一段时间之后，等到操作系统收集到了足够多的统计信息，就可以改变策略，使用更加适合的内存管理算法.

到这里就完了? nonono!!! 内存分配基本完了，但是回收只是做了一部分. 因为可能回收之后，导致ASL上相邻若干个节点的内存块其实是相邻的. 则可以合并为一块大的内存(这就是所谓的内存碎片整理). 那么内存的碎片整理怎么做呢? 简而言之就是一旦回收一块内存的话，则根据回收内存的范围，如果左边右边的内存块也是空闲的, 则合并. 否则仅仅插入（采用头插法）. 那么怎么判断相邻的内存块是空闲的呢? 目前的数据结构是无法支撑这种判断的. 所以我们需要将内存块的结构变成下图

​ 图2

即比图1多了一个foot. 新的MemoryBlock的数据结构是

1
2
3
4
5
6
7
8
9
10
typedef struct MemoryBlock{
    union {
        MemoryBlock *llink; // 对于head，这里是ASL前驱节点指针
        MemoryBlock *uplink; // 对于foot, 这里指向本MemoryBlock
    };
    int tag; // 同图1
    int size; // 同图1
    MemoryBlock *rlink; // ASL链表的后继节点
    char space[INITIALSIZE]; // 同图1
} MemoryBlock, *Space; // Space指针指向了可用列表的首地址

因为采用了双向链表，所以ASL长的像下面的样子

具体边界标识法的算法实现如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include "stdafx.h"
#include <iostream>

using namespace std;

const int INITIALSIZE = 200; // 模拟200字节的堆空间
const int e = 3; // 表示如果一块内存空间-申请的内存空间大小<=3字节的话，就干脆把整块内存空间分配给它, 不要留着3字节这么小的空间了.

typedef struct MemoryBlock
{
	union{
		MemoryBlock *llink; // ASL链表的前驱
		MemoryBlock *uplink; // 指向本MemoryBlock节点
	};
	int tag; // 0表示空闲，1表示占用
	int size; // 本内存块大小,是整个节点的大小，不仅仅是space的大小
	MemoryBlock *rlink; // ASL链表的后继
	char space[INITIALSIZE]; // 内存块

	MemoryBlock():size(INITIALSIZE), tag(0), rlink(this), llink(this){}

}MemoryBlock, *Space; // Space表示初始的堆（模拟了200字节）

inline int footsize() // 底部的大小
{
	return sizeof(Space) + sizeof(int); // 一个uplink一个tag
}

inline int headsize() // 头部的大小
{
	return (sizeof(Space)+sizeof(int))<<1; // 2个link 2个int
}

inline int controlsize() // 一个块的控制信息（是一个块至少要占据的大小）
{
	return footsize()+headsize();
}

inline Space getFoot(Space p) // 得到p指向块的底部位置(即foot指针)
{
	return (Space)((int)p+p->size-footsize()); // 注意, 不能直接写 p+p->size-footsize(), 指针加1和指针地址值+1是完全不同的, 举个例子就是p=int *的话, p+1其实是加了4, 但是(int)p+1 才是加了1, 如果只是想地址值+1的话, 可以这样做——体现了C语言指针的强大
}

inline Space leftneighbor(Space p) // p的左邻
{
	return ((Space)((int)p-footsize()))->uplink;
}

inline Space rightneighbor(Space p) // p的右舍
{
	return (Space)((int)p+p->size);
}

Space alloc(Space &pav, int n) // 分配n字节的内存空间(但是算法中我们其实会再为n加上控制信息的空间, 因为回收回来的时候, 我要往该内存块中写控制信息的, 如果不额外奉送控制信息的内存块的话(虽然是奉送，但是用户不能在这控制信息中写内容,不然回收时会有问题),则回收后怎么写控制信息呢? 比如申请9个字节空间，不额外分配24字节控制信息，则回收回来，9字节里面怎么存放控制信息呢? 所以这里分配的时候额外将24字节的控制信息也分配出去了 ), pav 是链表的可用空间列表的头结点 分配策略是首次分配法
{
	Space p; // p开始扫描
	for (p = pav; p->size<n+controlsize()&&p->rlink!=pav; p=p->rlink); // p从pav开始, 只要p还不够大小，并且p还不是最后那块，p就继续沿着rlink游动. 注意，这里不能用 p!=pav, 不然的话，for的初始条件就不满足而跳出循环了
	if (p->size<n+controlsize()*2) return 0; // 跳出上述循环要么是已经足够大了，要么是已经是最后那块了，如果还是不够大（注意，我们要保留控制信息的空间），那么说明无法分配n字节的内存 返回NULL,
	// 走到这里说明存在一块内存p的size>=n, 可以分配
	Space foot = getFoot(p); //  foot指针的位置
	pav = p->rlink; // pav 移动到下一块地址（这是为了防止每次都从头结点查找，势必造成大量小的节点密集在pav附近集结，这样会增加查询较大块内存空间的时间. ）
	if (p->size-n <= e + controlsize()) // 如果这块内存和待分配的差距不大的话, 就直接分配给请求了
	{
		if (pav == p) // 如果仅剩一块内存了，则分配掉，pav也别剩下了.
		{
			pav  = 0;
		}
		else // 注意，此时pav已经是p的rlink那块内存了,现在要把p这块内存从链表上卸载掉
		{
			pav->llink = p->llink;
			p->llink->rlink = pav;
		}
		foot->tag = 1; // 此块已经是占用块了
	}
	else // 如果远比需求的n个字节来的大, 则可不能豪放的一口气给他——我们仅仅打算将此节点p的后n个字节分配给他, 而且此块不需要从链表上移除
	{
		foot->tag = 1; // 此块(即分配出去的块)已被占用，这样设置的目的是为了后面回收算法（边界标识法）做准备
		foot->uplink = (Space)((int)p+p->size-n-controlsize()); // 此时被占用块的底部的uplink指针要回指到正确的地方, 不然的话, 回收算法的时候leftneighbor就会错误.
		p->size -=(n+controlsize()); // 此块大小要减掉n个字节外加控制信息
		foot = getFoot(p); // p不是瘦身了么? 我们要得到p新的底部.
		foot->tag = 0; // 依旧没被占用（是空闲块），因为p瘦身后的块是没被占用的.
		foot->uplink = p; // 回指顶部
		p = (Space)((int)foot+footsize()); // p指向分配出去去的那个块
		p->tag = 1;
		p->size = n +controlsize(); // 设置分配出去的块
	}
	return p; // 返回Space（一根指针）给请求，至于请求者要在这块大小为n(或者n+e)的内存中干什么，本内存管理系统管不着（注意，申请者只能在n个字节的空间中写东西, 不能覆盖了控制信息, 不然回收算法的时候，就无法判断左邻右舍了(回收算法第一行就要用)）, 其实这里只管内存的分配，并未对客户程序往未授权分配区域写数据的时候报错，这个就涉及操作系统中的权限问题了
}


void recycle(Space &pav, Space p) // 回收内存块p到pav链表中去, 份四种情形
{
	// 情形1. p的左邻右舍都是占用块, 则简单将p修改属性后插入到pav链表中去即可, 这里采用的实现是插入到pav之前
	if (leftneighbor(p)->tag && rightneighbor(p)->tag)
	{
		p->tag = 0;
		getFoot(p)->tag = 0; // 修改p为空闲块
		if (!pav) // 如果原本可用空间链表就是一个空链表的话，则将p设置为pav节点即可，即p本身就是头结点
		{
			pav = p->llink = p->rlink = p;
		}
		else // 则将p插入到pav的前面
		{
			Space q = pav->llink;
			p->rlink = pav;
			p->llink = q;
			q->rlink = pav->llink = p;
			pav = p; // pav 头指针指向p 去了 ,回收和分配都是要移动头指针的
		}
	}
	// 情形2. p的左邻是空闲块，p的右舍是占用块, 则p应该要和左邻合并成大的空闲块即可，注意, 因为左邻是空闲块，所以已经在链表中了，所以可以直接修改左邻属性即可（因为llink和rlink都在左邻的头部, 所以很方便）
	else if (rightneighbor(p)->tag) 
	{
		Space ln = leftneighbor(p); // 左邻
		int n = p->size; // 回收块的大小
		ln->size+=n; // 因为回收，所以大小增加
		getFoot(p)->uplink = ln; // 原先p的底部的uplink要指向p的左邻的头部
		getFoot(p)->tag = 0; // p已经回收了, 所以为空闲块
	}
	// 清新3. p的左邻是占用块，p的右舍是空闲块, 注意，右舍是在pav链表中的，但是如果合并进入p的右舍的话，则右舍的地址就要发生变化了，则原先链表就要发生异动，这是和情形2不同的地方
	else if (leftneighbor(p)->tag)
	{
		Space rn = rightneighbor(p); // 右舍
		p->tag = 0; // 合并之后,p 才是新的头部, 取代了原先右邻的头部
		Space q = rn->llink;
		p->llink = q; // 开始改变原本q, 原本q的右邻是rn,但是现在要改成p了
		q->rlink = p;
		Space ql = rn->rlink; // 同样修改原本rn的右邻, 它的左邻原本是rn, 现在要改成p
		p->rlink = ql;
		ql->llink = p;
		p->size += rn->size; // 更新节点大小
		getFoot(p)->uplink = p; // 更新底部的回指指针指向不再是rn，而是p
	}
	// 情形4. p的左邻右舍都是空闲块，则全部并入左邻
	else
	{
		int n = p->size; // 回收块的大小
		Space ln = leftneighbor(p); // 左邻
		Space rn = rightneighbor(p); // 右舍
		ln->size += (n+rn->size); // 因为左邻将成为新的节点，所以全部加入到左邻的大小.
		Space q = rn->llink; // 右邻的左邻
		Space ql = rn->rlink; // 右邻的右邻
		q->rlink = ql; // 删除右邻
		ql->llink = q;
		getFoot(rn)->uplink = ln; // 指向新的头结点——ln
	}
}


int main()
{
	Space heap = new MemoryBlock(); // 初始化堆内存
	Space m1 =  alloc(heap, 13); // 请求分配13字节的内存空间, 但是因为要奉送额外的控制信息，所以其实初始堆少了13+24（controlsize大小为24字节）=37字节
	if (!m1) puts("空间不足, 请求失败!");
	Space m2 = alloc(heap, 35);  // 请求分配35字节的内存空间，同上，堆其实少了35+24=59字节
	if (!m2) puts("空间不足, 请求失败!");
	Space m3 = alloc(heap, 38); // 请求分配38字节的内存空间，堆少了38+24=62字节
	if (!m3) puts("空间不足, 请求失败!");
	Space m4 = alloc(heap, 9); // 请求分配9字节的内存空间，实际需要9+24=33字节，但因为200-37-59-62-33<24(最后这个24字节要为剩下的内存空间的控制信息做准备的, 所以不能分配了此次请求后就少于24字节了),所以m4申请失败，因为空间不足了
	if (!m4) puts("空间不足, 请求失败!");
	Space m5 = alloc(heap, 19); // 请求分配19字节的内存空间
	if (!m5) puts("空间不足, 请求失败!");
	recycle(heap, m2); // 回收m2这块内存空间(比较大的一块内存)
	return 0;
}

从上述算法实现可以看到，正因为我们在每个内存块（MemoryBlock结构体）中加了控制信息（头部的和尾部的），所以能快速定位到左邻右舍，所以碎片的整理就能被支持了. 从而更加高效的利用整个堆空间.

注意，回收的时候只需要判断左邻右舍一次即可，因为不可能存在左邻空闲，左邻的左邻依旧空闲这种情况，否则的话，在左邻回收的时候就被左邻合并了。

这就是动态内存管理之边界标识法.

参考

【1】严蔚敏，吴伟民 数据结构（C语言版） 清华大学出版社