在学习操作系统时，讲到CPU对内存的寻址，会涉及到内存的管理方式，内存管理方式有如下四种：
1.单连续分区存储管理
2.页式存储管理
3.段式存储管理
4.段页式存储管理
其中，单连续分区存储管理可以分为1.固定分区存储管理和2.可变分区存储管理。
其中最复杂的是可变分区存储管理，内存管理效果最好，但是实际应用最多的是段页式存储管理。段页式存储管理实现考虑情况较少，实现起来相对简单，但是效率也很高。但是如果明白了可变分区存储管理，应该其他内存管理方式也明白了。
单连续分区存储管理
思想
维护两个数据结构：
1.用于存放空闲分区的双向链表
2.是用于存放内存中作业信息的线性表
将内存看成是一个大的块，当有作业申请内存时，就找第一个足够大小的空闲分区，将作业放入该分区，同时更新线性表和链表。如果没有足够大小的空间，就启动主存紧凑（将所有的主存外零头汇聚到高地址处），得到一个大的空闲分区块，然后判断是否满足分配条件。
算法实现
分配内存
只考虑三种情况
|1.作业C不能放入空闲分区。
|2.作业C可以放入空闲分区
___|2.1剩下的内存大小不足以形成内存碎片，直接分配给该作业。
___|2.2.作业C可以放入空闲分区，剩下的内存大小也足以形成内存碎片
void addTable(int name, int size,int addr) {
//往任务分配表中添加新任务
for (int i = 0; i < 100; i++) {
if (tab[i].flag == false) {
tab[i].name = name;
tab[i].addr = addr;
tab[i].length = size;
tab[i].flag = true; //该内存块被占用
return;
}
}
}
void alterTable() {
//修改任务分配表
std::sort(tab, tab + 100, cmp); //将任务分配表按从大到小的顺序排序
tab[0].addr = 0;
for (int i = 1; i < 100; i++) {
if (!tab[i].flag) break;
tab[i].addr = tab[i - 1].addr + tab[i - 1].length; //更改任务起始地址
}
}
void compactMem(pFreePartition p) {
//递归将p空闲分区合并到p.next中
if (p == NULL) {
return;
}
if (p->next == NULL) {
head = p;
p->back = NULL;
return;
}
p->next->size += p->size; //更改空闲分区的大小
p->next->address -= p->size; //更改空闲分区的地址
compactMem(p->next);
free(p);
}
void ffcolection() {
//模拟分配内存模块
int size;
int name;
bool flag = false; //用于标识分配了一个完整的分区
printf("\n----------模拟分配作业内存模块----------\n\n");
printf("\n请输入需要分配的作业名：\n");
scanf("%d", &name);
printf("\n请输入需要分配的内存大小(单位 B)：\n");
scanf("%d", &size);
pFreePartition p = head; //设置指针遍历空闲分区链表
while (p != NULL) {
if (p->size > size) {
//当前内存区满足分配条件
if (p->size - size > MIN) {
//分配内存以后的空间满足内存碎片
addTable(name, size, p->address); //修改作业分配表
p->size = p->size - size; //修改空闲区链表
p->address += size;
}
else {
//分配内存以后的空间不满足内存碎片的条件，直接分配给原进程
addTable(name, p->size, p->address);
flag = true;
if (p == head) {
//头结点为分区
head = p->next; //空闲区链表为空
free(p);
p = NULL;
}
else {
//非头结点为分区
p->back->next = p->next;
free(p);
p = NULL;
}
}
break;
}
//当前内存区不满足内存分配条件
p = p->next;
}
if (p == NULL && flag == false) {
//p==NULL有可能分配了一个完整的分区，有可能没有找到一个分区,flag==fasle标识没有找到一个完整的分区
//尝试主存紧凑
//printf("test1:%d\n", head->address);
compactMem(head);
//printf("test2:%d\n", head->address);
//更改任务分配表
alterTable();
if (head==NULL||head->size < size) {
printf("无法为任务提供足够内存!!\n");
}
else {
addTable(name, size, head->address);
head->size -= size;
head->address += size;
if (head->size == 0) {
free(head);
head = NULL;
}
}
}
}
释放内存
四种情况：
情况一：情况2：
情况3：情况4：
实际上四种情况可以当成两种情况处理，先将空闲内存块插入，最后再进行空闲块整合。
void recolection() {
//模拟释放内存模块
int name; //记录删除的进程名
int address = -1; //记录删除的进程地址
int length; //记录删除的进程长度
printf("\n----------模拟释放内存模块----------\n\n");
printf("\n请输入要释放的作业名:\n\n");
scanf("%d", &name);
for (int i = 0; i < 100; i++) { //任务分配表中删除任务name
if (name == tab[i].name) {
address = tab[i].addr;
length = tab[i].length;
tab[i].flag = false;
tab[i].addr = INF;
}
}
if (address == -1) {
printf("任务名不存在！！\n");
return;
}
pFreePartition p = head;
pFreePartition pre = head;
while (p != NULL) {
if (p->address > address) {
//p空闲分区在address之后
break;
}
pre = p;
p = p->next;
}
if (p == NULL) {
//释放的任务后无空闲区
p = (pFreePartition)malloc(sizeof(freePartition));
p->address = address;
p->next = NULL;
p->back = pre;
p->size = length;
if (p->back != NULL) {
//p不是头结点
p->back->next = p;
}
else {
//p是头结点
head = p;
}
}
else {
//释放的任务后有空闲区
pFreePartition temp = (pFreePartition)malloc(sizeof(freePartition));
//检测一下p->back是否是空
temp->next = p;
temp->back = p->back;
p->back = temp;
if (temp->back != NULL) {
//p不是头结点
temp->back->next = temp;
}
else {
//p是头结点
head = temp;
}
temp->address = address;
temp->size = length;
}
/*任务内存恢复测试
p = head;
while (p != NULL) {
printf("test: address:%d size:%d\n", p->address, p->size);
p = p->next;
}
*/
p = head->next;
while (p!=NULL&&p->back!=NULL) {
//将多个连续的分区合并为一个分区
if (p->back->address + p->back->size == p->address) {
//printf("p->address:%d p->size:%d p->next->addreee:%d\n", p->address, p->size, p->next->address);
pFreePartition temp = p->back;
p->size += p->back->size;
p->address = p->back->address;
head = p;
free(temp);
}
p = p->next;
}
printf("内存释放完成\n");
}
查看内存使用情况和作业管理表使用情况
void seeSimulateMemory() {
//查看当前模拟内存使用情况
printf("\n空闲分区使用情况:\n\n");
pFreePartition p = head;
while (p != NULL) {
printf("address:%d size:%d\n", p->address,p->size);
p = p->next;
}
printf("\n-----------任务分配情况----------\n\n");
for (int i = 0; i < 100; i++) {
if (tab[i].flag==true) {
printf("name:%d address:%d length:%d\n", tab[i].name, tab[i].addr, tab[i].length);
}
}
printf("空闲分区查看完成");
}
完整代码
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<algorithm>
#define debug(x) printf("debug:%s",x);
#define freep NULL;
const int INF = 0x3f3f3f3f;
const int MIN = 5; //定义碎片最小容量
typedef unsigned int Uint;
//空闲区链表
typedef struct node {
Uint size; //空区大小（以字节计），包括区头所占空间
struct node* next; //后一分区地址
struct node* back; //前一分区地址
Uint address; //本分区首地址
}freePartition,*pFreePartition;
//作业分配表
typedef struct table {
int name; //用户作业名
Uint length; //作业区大小
int addr; //作业区首地址
bool flag; //标记内存的状态，flag=true为占用
}memTable;
pFreePartition head; //空闲区表头
memTable tab[100]; //作业分配表，最多支持100个作业
void init() {
//初始化空闲分区表
int size;
head = (pFreePartition)malloc(sizeof(freePartition));
printf("请输入总分区大小：");
scanf("%d", &size);
assert(size > 5); //判断总分区的合理性
head->next = freep;
head->address = 0;
head->back = freep;
head->size = size;
for (int i = 0; i < 100; i++) {
tab[i].addr = INF;
tab[i].flag = false;
}
return ;
}
void addTable(int name, int size,int addr) {
//往任务分配表中添加新任务
for (int i = 0; i < 100; i++) {
if (tab[i].flag == false) {
tab[i].name = name;
tab[i].addr = addr;
tab[i].length = size;
tab[i].flag = true; //该内存块被占用
return;
}
}
}
bool cmp(memTable a, memTable b) {
return a.addr < b.addr;
}
void alterTable() {
//修改任务分配表
std::sort(tab, tab + 100, cmp); //将任务分配表按从大到小的顺序排序
tab[0].addr = 0;
for (int i = 1; i < 100; i++) {
if (!tab[i].flag) break;
tab[i].addr = tab[i - 1].addr + tab[i - 1].length; //更改任务起始地址
}
}
void compactMem(pFreePartition p) {
//递归将p空闲分区合并到p.next中
if (p == NULL) {
return;
}
if (p->next == NULL) {
head = p;
p->back = NULL;
return;
}
p->next->size += p->size; //更改空闲分区的大小
p->next->address -= p->size; //更改空闲分区的地址
compactMem(p->next);
free(p);
}
void ffcolection() {
//模拟分配内存模块
int size;
int name;
bool flag = false; //用于标识分配了一个完整的分区
printf("\n----------模拟分配作业内存模块----------\n\n");
printf("\n请输入需要分配的作业名：\n");
scanf("%d", &name);
printf("\n请输入需要分配的内存大小(单位 B)：\n");
scanf("%d", &size);
pFreePartition p = head; //设置指针遍历空闲分区链表
while (p != NULL) {
if (p->size > size) {
//当前内存区满足分配条件
if (p->size - size > MIN) {
//分配内存以后的空间满足内存碎片
addTable(name, size, p->address); //修改作业分配表
p->size = p->size - size; //修改空闲区链表
p->address += size;
}
else {
//分配内存以后的空间不满足内存碎片的条件，直接分配给原进程
addTable(name, p->size, p->address);
flag = true;
if (p == head) {
//头结点为分区
head = p->next; //空闲区链表为空
free(p);
p = NULL;
}
else {
//非头结点为分区
p->back->next = p->next;
free(p);
p = NULL;
}
}
break;
}
//当前内存区不满足内存分配条件
p = p->next;
}
if (p == NULL && flag == false) {
//p==NULL有可能分配了一个完整的分区，有可能没有找到一个分区,flag==fasle标识没有找到一个完整的分区
//尝试主存紧凑
//printf("test1:%d\n", head->address);
compactMem(head);
//printf("test2:%d\n", head->address);
//更改任务分配表
alterTable();
if (head==NULL||head->size < size) {
printf("无法为任务提供足够内存!!\n");
}
else {
addTable(name, size, head->address);
head->size -= size;
head->address += size;
if (head->size == 0) {
free(head);
head = NULL;
}
}
}
}
void recolection() {
//模拟释放内存模块
int name; //记录删除的进程名
int address = -1; //记录删除的进程地址
int length; //记录删除的进程长度
printf("\n----------模拟释放内存模块----------\n\n");
printf("\n请输入要释放的作业名:\n\n");
scanf("%d", &name);
for (int i = 0; i < 100; i++) { //任务分配表中删除任务name
if (name == tab[i].name) {
address = tab[i].addr;
length = tab[i].length;
tab[i].flag = false;
tab[i].addr = INF;
}
}
if (address == -1) {
printf("任务名不存在！！\n");
return;
}
pFreePartition p = head;
pFreePartition pre = head;
while (p != NULL) {
if (p->address > address) {
//p空闲分区在address之后
break;
}
pre = p;
p = p->next;
}
if (p == NULL) {
//释放的任务后无空闲区
p = (pFreePartition)malloc(sizeof(freePartition));
p->address = address;
p->next = NULL;
p->back = pre;
p->size = length;
if (p->back != NULL) {
//p不是头结点
p->back->next = p;
}
else {
//p是头结点
head = p;
}
}
else {
//释放的任务后有空闲区
pFreePartition temp = (pFreePartition)malloc(sizeof(freePartition));
//检测一下p->back是否是空
temp->next = p;
temp->back = p->back;
p->back = temp;
if (temp->back != NULL) {
//p不是头结点
temp->back->next = temp;
}
else {
//p是头结点
head = temp;
}
temp->address = address;
temp->size = length;
}
/*任务内存恢复测试
p = head;
while (p != NULL) {
printf("test: address:%d size:%d\n", p->address, p->size);
p = p->next;
}
*/
p = head->next;
while (p!=NULL&&p->back!=NULL) {
//将多个连续的分区合并为一个分区
if (p->back->address + p->back->size == p->address) {
//printf("p->address:%d p->size:%d p->next->addreee:%d\n", p->address, p->size, p->next->address);
pFreePartition temp = p->back;
p->size += p->back->size;
p->address = p->back->address;
head = p;
free(temp);
}
p = p->next;
}
printf("内存释放完成\n");
}
void recolectionALL() {
//释放链表的的所有进程
int size = 0;
printf("\n释放链表的的所有内存\n\n");
pFreePartition p = head;
while (p != NULL) {
//收集空闲分区内存
pFreePartition temp = p;
p = p->next;
size += p->size;
free(temp);
}
for (int i = 0; i < 100; i++) {
//收集所有任务表的内存
if (tab[i].flag) {
size += tab[i].length;
}
}
p = (pFreePartition)malloc(sizeof(freePartition));
p->back = NULL;
p->next = NULL;
p->address = 0;
p->size = size;
printf("内存释放完成");
}
void seeSimulateMemory() {
//查看当前模拟内存使用情况
printf("\n空闲分区使用情况:\n\n");
pFreePartition p = head;
while (p != NULL) {
printf("address:%d size:%d\n", p->address,p->size);
p = p->next;
}
printf("\n-----------任务分配情况----------\n\n");
for (int i = 0; i < 100; i++) {
if (tab[i].flag==true) {
printf("name:%d address:%d length:%d\n", tab[i].name, tab[i].addr, tab[i].length);
}
}
printf("空闲分区查看完成");
}
void menu() {
int key; //接受命令信息
init();
while (1) {
printf("------------------模拟命令菜单------------------\n\n");
printf("---------------模拟分配内存 键入1--------------\n\n");
printf("---------------模拟释放内存 键入2--------------\n\n");
printf("-------------模拟释放所有内存 键入3--------------\n\n");
printf("----------------退出系统 键入0----------------\n\n");
printf("目前内存使用情况如下：\n");
seeSimulateMemory();
printf("请输入命令：");
scanf("%d", &key);
switch (key) {
case 1:
ffcolection();
break;
case 2:
recolection();
break;
case 3:
recolectionALL();
break;
case 0:
recolectionALL();
exit(0);
default:
printf("\n命令不存在，请重新输入\n\n");
}
}
}