操作系统笔记(5)-空闲空间管理
操作系统笔记(5)-空闲空间管理
简介
在堆上管理空闲空间的数据结构通常称为
空闲列表（free list)，该结构包含了管理内存区域中所有空闲块的引用外部碎片是指空闲列表中出现了很多小的内存块，导致无法分配一块较大的内存内部碎片是指分配了多余的内存，浪费发生在已分配单元的内部
底层机制
分割与合并
- 假设有一段
0~30字节的地址空间，其中10~20已经被使用了，那么剩余的就是空闲空间，用空闲列表表示如下：
如果要申请一块大小为
5字节的空间，可以将第一个节点分割如果要释放原来的空间，也可以与空闲列表中的结点
合并成一个更大的结点，以满足较大内存的需求
追踪已分配空间的大小
在 C 语言中，
free()函数可以释放空间，但是它只接受一个指针为参数，所以要知道待释放的空间的大小，需要在头块中保存一点额外的信息，这个头块通常就在返回的内存块之前该头块至少包含所分配空间的大小，也可能包含一些额外的指针来加速空间释放，包含一个幻数来提供完整性检查，以及其它信息
typedef struct header_t { int size; int magic; } header_t;用户调用
free(ptr)时，库会通过简单的指针运算得到头块的位置void free(void *ptr) { header_t *hptr = (void*)ptr - sizeof(header_t); }
基本策略
为了更好地管理空闲空闲，出现了一些基本策略：
最优匹配(best fit) ：在空闲列表中找到一块最接近请求的块的大小的结点并分配
最差匹配(worst fit) : 与最优匹配相反，它尝试找到最大的空闲块，分割并满足用户需求后，将剩余的块（很大）加入空闲列表
首次匹配(first fit) : 找到第一个足够大的块，将请求的空间返回给用户
下次匹配(next fit) ：多维护一个指针，指向上一次场照的结束位置
C 语言模拟基本策略
首先，我们的策略是支持空闲块合并的，并且为了方便合并，空闲列表结点按地址从小到大排列
其次，我们考虑了头部结点的大小，因此在申请内存块时需要加上头部结点的大小
最后，对于分配失败的操作，返回
NULL，否则返回内存块的指针，如上图的ptr所示
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
typedef struct node_t {
int addr; // 空闲块的起始地址
int size; // 分配的地址空间大小
struct node_t *next; // 指向下一个结点的指针
} node_t;
typedef struct freelist {
node_t *head;
} freelist;
// 初始化空闲列表, 提供地址块的起始地址和大小
freelist* initList(int addr_, int size_) {
freelist* flist = (freelist*)malloc(sizeof(freelist));
flist->head = (node_t*)malloc(sizeof(node_t)); // 虚拟头结点, 便于操作实现
node_t* node = (node_t*)malloc(sizeof(node_t));
node->addr = addr_;
node->size = size_;
node->next = NULL;
flist->head->next = node;
return flist;
}
node_t* best_fit(freelist* flist, int size_) {
node_t *pre = flist->head, *cur = pre->next;
node_t* pp = NULL;
node_t *p = NULL;
int minsz = INT_MAX;
while (cur) {
if (cur->size >= (size_ + sizeof(node_t))) {
if (cur->size < minsz) {
minsz = cur->size;
p = cur;
pp = pre;
}
}
cur = cur->next;
}
if (!p) return NULL;
node_t* node = (node_t*)malloc(sizeof(node_t));
node->addr = p->addr + sizeof(node_t);
node->size = size_;
node->next = NULL;
p->addr += size_ + sizeof(node_t);
p->size -= size_ + sizeof(node_t);
if (p->size == 0) {
pp->next = p->next;
free(p);
}
return node;
}
node_t* worst_fit(freelist* flist, int size_) {
node_t *pre = flist->head, *cur = pre->next;
node_t* pp = NULL;
node_t *p = NULL;
int maxsz = INT_MIN;
while (cur) {
if (cur->size >= (size_ + sizeof(node_t))) {
if (cur->size > maxsz) {
maxsz = cur->size;
p = cur;
pp = pre;
}
}
cur = cur->next;
}
if (!p) return NULL;
node_t* node = (node_t*)malloc(sizeof(node_t));
node->addr = p->addr + sizeof(node_t);
node->size = size_;
node->next = NULL;
p->addr += size_ + sizeof(node_t);
p->size -= size_ + sizeof(node_t);
if (p->size == 0) {
pp->next = p->next;
free(p);
}
return node;
}
node_t* first_fit(freelist* flist, int size_) {
node_t *pre = flist->head, *cur = pre->next;
node_t* pp = NULL;
node_t* p = NULL;
while (cur) {
if (cur->size >= (size_ + sizeof(node_t))) {
p = cur;
pp = pre;
break;
}
cur = cur->next;
}
if (!p) return NULL;
node_t* node = (node_t*)malloc(sizeof(node_t));
node->addr = p->addr + sizeof(node_t);
node->size = size_;
node->next = NULL;
p->addr += size_ + sizeof(node_t);
p->size -= size_ + sizeof(node_t);
if (p->size == 0) {
pp->next = p->next;
free(p);
}
return node;
}
// 申请空间, 提供申请大小和分配策略
// 0 : 最优匹配
// 1 : 最差匹配
// 2 : 首次匹配
node_t* alloc(freelist* flist, int size_, int policy) {
if (policy == 0) {
return best_fit(flist, size_);
}
else if (policy == 1) {
return worst_fit(flist, size_);
}
return first_fit(flist, size_);
}
// 回收内存
void recovery(freelist* flist, node_t* node) {
if (!node) return;
node_t *pre = flist->head;
node_t *cur = pre->next;
node->addr -= sizeof(node_t);
node->size += sizeof(node_t);
while (cur) {
if (cur->addr > node->addr) {
// 检查是否可以合并
if (cur->addr == node->addr + node->size) { // 可以合并
cur->addr = node->addr;
cur->size += node->size;
free(node);
// 检查能不能和 pre 合并
if (pre != flist->head && pre->addr + pre->size == cur->addr) {
pre->size += cur->size;
pre->next = cur->next;
free(cur);
}
return;
}
else if (pre != flist->head && pre->addr + pre->size == node->addr) {
pre->size += node->size;
free(node);
return;
}
else {
node->next = cur;
pre->next = node;
return;
}
}
pre = pre->next;
cur = cur->next;
}
pre->next = node;
}
// 打印空闲块信息
void printNode(node_t* node) {
if (!node) {
puts("alloc error!");
return;
}
printf("( addr : %d sz : %d )\n", node->addr, node->size);
}
// 打印空闲列表中的空闲块
void printList(freelist* flist) {
node_t* cur = flist->head->next;
while (cur) {
printf("[ addr: %d sz: %d ] ", cur->addr, cur->size);
cur = cur->next;
}
puts("");
}
// 释放空闲列表
void freeList(freelist* flist) {
node_t *pre = flist->head, *cur = pre->next;
while (cur) {
free(pre);
pre = cur;
cur = cur->next;
}
free(pre);
free(flist);
}测试
int main(int argc, char* argv[]) {
freelist* flist = initList(1000, 300); // 初始化一块地址空间, 从 1000 开始, 大小为 300 B
printf("头块大小为: %ld \n", sizeof(node_t));
// 最优匹配测试
node_t* b1 = alloc(flist, 20, 0); // addr : 1016
printNode(b1);
node_t* b2 = alloc(flist, 30, 0); // addr : 1052
printNode(b2);
node_t* b3 = alloc(flist, 300, 0); // error
printNode(b3);
printList(flist); // addr : 1082 sz : 218 (300 - (20 + 16) - (30 + 16))
recovery(flist, b1);
printList(flist); // (addr : 1000 sz : 36) + (addr : 1082 sz : 218)
node_t* b4 = alloc(flist, 4, 0); // addr : 1016
printNode(b4);
printList(flist); // (addr : 1020 sz : 16) + (addr : 1082 sz : 218)
recovery(flist, b2);
recovery(flist, b3);
printList(flist); // (addr : 1020 sz : 280)
recovery(flist, b4);
freeList(flist);
// 最差匹配测试
flist = initList(2000, 500);
node_t* w1 = alloc(flist, 200, 1); // addr : 2016
printNode(w1);
node_t* w2 = alloc(flist, 100, 1); // addr : 2232
printNode(w2);
recovery(flist, w1);
printList(flist); // (addr : 2000 sz : 216) + (addr : 2332 sz : 168)
node_t* w3 = alloc(flist, 50, 1); // (addr : 2016 sz : 50)
printNode(w3);
printList(flist); // (addr : 2066 sz : 150) + (addr : 2332 sz : 168)
recovery(flist, w2);
recovery(flist, w3);
freeList(flist);
// 首次匹配测试
flist = initList(3000, 1000);
node_t* f1 = alloc(flist, 100, 2); // addr : 3016
printNode(f1);
node_t* f2 = alloc(flist, 200, 2);
recovery(flist, f1);
printList(flist); // (addr : 3000 sz : 116) + (addr : 3332 sz : 668)
node_t* f3 = alloc(flist, 50, 2); // addr : 3016
printNode(f3);
node_t* f4 = alloc(flist, 100, 2); // addr : 3348
printNode(f4);
recovery(flist, f3);
printList(flist); // (addr : 3000 sz : 116) + (addr : 3348 sz : 552)
recovery(flist, f2);
recovery(flist, f4);
freeList(flist);
return 0;
}其它方式
分离空闲列表
- 如果某个应用程序经常申请一种（或几种）大小的内存空间，那就用一个独立的列表，值管理这样大小的对象，其它大小的请求都交给更通用的内存分配程序
伙伴系统
二分伙伴分配程序（binary buddy allocator） 让合并变得简单，空闲空间首先从概念上被看出大小为 $2^N$ 的大空间
当有一个内存分配请求时，空闲空间被递归地一分为二，直到刚好可以满足请求的大小（再分就不行了）
当释放空间后，会找到相邻的
伙伴合并
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
