几点说明:
部分代码参考《数据结构》教材。
1、采用空闲分区链链接空闲分区,用循环首次适应算法分配内存。
2、假定内存块的大小、地址以“字”为单位计。空闲区、作业区边界采用标识。
“字”的数据结构如下:
leftLink |
tag |
size |
rightLink |
空闲空间 |
|||
upLink |
tag |
3、分配内存时,将符合要求的空闲区的高地址部分分配给作业,以减少修改指针的操作。
4、源程序:
// 空闲分区链,边界标识法 // 循环首次适应算法 #define _CRT_SECURE_NO_WARNINGS #define NDEBUG #include <iostream> #include <map> #include <string> #include <cstdio> #include <cstdlib> #include <cassert> using namespace std; const int MIN_REMAIN = 3; // 不保留<=MIN_REMAIN的剩余量 const int MEMORY_SIZE = 128; // 内存空间大小(以字计) enum State{FREE, ALLOC}; // 块标志:空闲FREE,占用ALLOC struct Word { union { Word *leftLink; // 头部:指向前驱结点 Word *upLink; // 尾部:指向本结点头部 }; State tag; // 头部、尾部:都设块标志 unsigned int size; // 头部:块大小 Word *rightLink; // 头部:指向后继结点 // 默认构造函数 Word() :leftLink(NULL), // 共用体只初始化一个成员即可 tag(FREE), size(0), rightLink(NULL){} }memory[MEMORY_SIZE]; // 假设内存总量为MEMORY_SIZE个字 struct Job { string name; unsigned int size; }; // 返回front所指向结点的尾部的地址。 inline Word * FootLoc(Word *front) // inline? { return front + front->size - 1; } // 初始只有一块空闲区,初始化它的首字和尾部,pav指向首字。 // 建立双向循环链表,不带头结点。 void Initiate(Word *&pav) { pav = memory; // 表中不设表头结点,表头指针pav可以指向表中任一结点 // 头部 pav->leftLink = memory; pav->rightLink = memory; pav->size = MEMORY_SIZE; pav->tag = FREE; // 尾部 FootLoc(pav)->upLink = memory; FootLoc(pav)->tag = FREE; } // 若有不小于n的空闲块,则分配相应的存储块,并返回其首地址; // 否则返回NULL。 // 若分配后可利用空间表不空,则pav指向表中刚分配过的结点的后继结点。 // n应>=3,包括头尾两个字,而实际分配时忽略不计? Word * AllocBoundTag (Word *&pav, unsigned int n) { if (n <= 2) { cout << "n<=2,不能分配空间!" << endl; return NULL; } Word *p = NULL; for (p = pav; NULL != p && p->size < n && p->rightLink != pav; p = p->rightLink); // 查找不小于n的空闲块 if (NULL == p || p->size < n) { cout << "内存可用空间不够,请先释放内存。" << endl; return NULL; // 找不到,返回空指针 } // p指向找到的空闲块 Word *f = FootLoc(p); // 指向底部 pav = p->rightLink; // “循环”:pav指向*p结点的后继结点 if (p->size - n <= MIN_REMAIN) { // 整块分配,不保留<=MIN_REMAIN的剩余量 if (pav == p) { pav = NULL; // 可利用空间表变为空表 } else { // 在表中删除分配的结点 pav->leftLink = p->leftLink; p->leftLink->rightLink = pav; } p->tag = ALLOC; f->tag = ALLOC; // 修改分配结点的头部和底部标志 } else { // 分配该块的后n个字使剩余块头部:leftLink, tag, rightLink不变 f->tag = ALLOC; // 分配块尾部:tag //f->upLink = FootLoc(p) + 1; // 分配块尾部:upLink p->size -= n; // 剩余块头部:size // 剩余块头部:leftLink, tag, rightLink不变 f = FootLoc(p); // f指向剩余块尾部 f->tag = FREE; // 剩余块尾部:tag f->upLink = p; // 剩余块尾部:upLink p = f + 1; // p指向分配块头部 p->tag = ALLOC; // 分配块头部:tag p->size = n; // 分配块头部:size //p->leftLink = NULL; // 分配块头部:leftLink //p->rightLink = NULL; // 分配块头部:rightLink } return p; // 返回分配块首地址 } // 1、前后相邻区都是作业 void Recycle_AA(Word *&pav, Word *&p) { p->tag = FREE; // 回收区头部:tag // 回收区头部:size 原来就存在 FootLoc(p)->upLink = p; // 回收区尾部:upLink FootLoc(p)->tag = FREE; // 回收区尾部:tag if (NULL == pav) { pav = p; p->leftLink = p; // 回收区头部:leftLink p->rightLink = p; // 回收区头部:rightLink } else { // 将p插到pav之前(双向链表的插入操作) p->rightLink = pav; // 回收区头部:rightLink p->leftLink = pav->leftLink; // 回收区头部:leftLink pav->leftLink->rightLink = p; // pav的前驱头部:rightLink pav->leftLink = p; // pav的头部:leftLink pav = p; // 令刚释放的结点为下次分配时的最先查询的结点 } } // 2、前空闲,后作业 void Recycle_FA(Word *&p) { unsigned int n = p->size; // 释放块的大小 Word *s = (p - 1)->upLink; // 左邻空闲区的头部地址 s->size += n; // 设置新的空闲块大小 Word *f = p + n - 1; // 设置新的空闲块底部 f->upLink = s; f->tag = FREE; } // 3、前作业,后空闲 void Recycle_AF(Word *&p) { Word *t = p + p->size; // t指向右邻空闲区的头部 FootLoc(t)->upLink = p; // 右邻空闲区头部:upLink p->size += t->size; // 回收区头部:size p->tag = FREE; // 回收区头部:tag p->leftLink = t->leftLink; // 回收区头部:leftLink t->leftLink->rightLink = p; // 原来右邻区的前驱头部:rightLink p->rightLink = t->rightLink;// 回收区头部:rightLink t->rightLink->leftLink = p; // 原来右邻区的后继头部:leftLink } // 4、前后相邻区都是空闲区 void Recycle_FF(Word *&p) { unsigned int n = p->size; // 回收区大小 Word *s = (p - 1)->upLink; // 指向左邻块,即新结点头部 Word *t = p + p->size; // 指向右邻块 s->size += n + t->size; // 设置新结点大小 // 删除右邻空闲块结点(双向链表的删除操作) t->leftLink->rightLink = t->rightLink; // s不一定等于t->leftLink t->rightLink->leftLink = t->leftLink; FootLoc(t)->upLink = s; // 新结点尾部:upLink指向其头部 } // 释放首地址为p的作业(头部中含该作业的大小信息) void Recycle(Word *&pav, Word *p) { if (!(memory <= p && p < memory + MEMORY_SIZE)) { cout << "释放区首地址越界!" << endl; return; } Word *low = p - 1; // 与其低地址紧邻的内存区的底部地址 Word *high = p + p->size; // 与其高地址紧邻的内存区的头部地址 State lowTag = low->tag; State highTag = high->tag; if (low < memory) // 当p是内存的第一块时 { lowTag = ALLOC; } if (high >= memory + MEMORY_SIZE) // 当p是内存的最后一块时 { highTag = ALLOC; } // 前后相邻区都是作业 if (ALLOC == lowTag && ALLOC == highTag) { Recycle_AA(pav, p); } // 前空闲,后作业 else if (FREE == lowTag && ALLOC == highTag) { Recycle_FA(p); } // 前作业,后空闲 else if (ALLOC == lowTag && FREE == highTag) { Recycle_AF(p); } // 前后相邻区都是空闲区 else if (FREE == lowTag && FREE == highTag) { Recycle_FF(p); } } // 输出内存中各区的信息 void PrintMInfo(map<Word *, string> &jobAddrToName) { cout << "\n************************************" << endl; cout << "起址\t大小\t状态\t(作业名)" << endl; for (Word *p = memory; p < memory + MEMORY_SIZE; p += p->size) { cout << p - memory << "\t" << p->size << "\t" << p->tag << "\t" << (p->tag == ALLOC ? jobAddrToName[p] : "(空闲)") << endl; } cout << "************************************\n" << endl; } int Flag(const string &option) { if (option == "1") return 1; if (option == "2") return 2; if (option == "3") return 3; return 0; } int main(int argc, char **argv) { freopen("cin.txt", "r", stdin); map<string, Word *> jobNameToAddr; // 根据作业名得到它的地址 map<Word *, string> jobAddrToName; // 根据作业地址得到它的名称 Word *pav = NULL; // pav为查询指针 Initiate(pav); string option; do { PrintMInfo(jobAddrToName); cout << "请选择:1、分配内存 2、回收内存 3、退出" << endl; cin >> option; switch (Flag(option)) { case 1: { // 防止error C2374:初始化操作由“case”标签跳过 cout << "请输入作业名和作业大小:" << endl; Job myJob; cin >> myJob.name >> myJob.size; Word *addr = AllocBoundTag(pav, myJob.size); if (addr == NULL) // 分配失败 { break; } jobNameToAddr[myJob.name] = addr; jobAddrToName[addr] = myJob.name; break; } case 2: { cout << "请输入要回收的作业名称:" << endl; string name; cin >> name; Word *addr = jobNameToAddr[name]; // 用户释放的内存区的头部地址为addr if (NULL == addr) { cout << "作业" << name << "不存在,无法释放!" << endl; break; } Recycle(pav, addr); int cnt = jobAddrToName.erase(addr); assert(cnt == 1); cnt = jobNameToAddr.erase(name); assert(cnt == 1); break; } case 3: return 0; default: cout << "输入错误!请重新输入。" << endl; break; } } while (true); return 0; } /* cin.txt 1 J5 96 1 J2 6 1 J4 12 1 J3 4 1 J1 5 1 OS 5 2 J4 2 J5 2 J3 1 J6 20 3 */
5、运行结果:
************************************ 起址 大小 状态 (作业名) 0 128 0 (空闲) ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请输入作业名和作业大小: ************************************ 起址 大小 状态 (作业名) 0 32 0 (空闲) 32 96 1 J5 ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请输入作业名和作业大小: ************************************ 起址 大小 状态 (作业名) 0 26 0 (空闲) 26 6 1 J2 32 96 1 J5 ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请输入作业名和作业大小: ************************************ 起址 大小 状态 (作业名) 0 14 0 (空闲) 14 12 1 J4 26 6 1 J2 32 96 1 J5 ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请输入作业名和作业大小: ************************************ 起址 大小 状态 (作业名) 0 10 0 (空闲) 10 4 1 J3 14 12 1 J4 26 6 1 J2 32 96 1 J5 ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请输入作业名和作业大小: ************************************ 起址 大小 状态 (作业名) 0 5 0 (空闲) 5 5 1 J1 10 4 1 J3 14 12 1 J4 26 6 1 J2 32 96 1 J5 ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请输入作业名和作业大小: ************************************ 起址 大小 状态 (作业名) 0 5 1 OS 5 5 1 J1 10 4 1 J3 14 12 1 J4 26 6 1 J2 32 96 1 J5 ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请输入要回收的作业名称: ************************************ 起址 大小 状态 (作业名) 0 5 1 OS 5 5 1 J1 10 4 1 J3 14 12 0 (空闲) 26 6 1 J2 32 96 1 J5 ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请输入要回收的作业名称: ************************************ 起址 大小 状态 (作业名) 0 5 1 OS 5 5 1 J1 10 4 1 J3 14 12 0 (空闲) 26 6 1 J2 32 96 0 (空闲) ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请输入要回收的作业名称: ************************************ 起址 大小 状态 (作业名) 0 5 1 OS 5 5 1 J1 10 16 0 (空闲) 26 6 1 J2 32 96 0 (空闲) ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请输入作业名和作业大小: ************************************ 起址 大小 状态 (作业名) 0 5 1 OS 5 5 1 J1 10 16 0 (空闲) 26 6 1 J2 32 76 0 (空闲) 108 20 1 J6 ************************************ 请选择:1、分配内存 2、回收内存 3、退出 请按任意键继续. . .