279 lines
5.9 KiB
C++
279 lines
5.9 KiB
C++
#include<stdio.h>
|
||
#include<stdlib.h>
|
||
|
||
enum STATE {
|
||
F, W
|
||
};
|
||
|
||
struct subAreaNode {
|
||
int addr; // 起始地址
|
||
int size; // 分区大小
|
||
int taskId; // 作业号
|
||
STATE state; // 分区状态
|
||
subAreaNode *pre; // 分区前向指针
|
||
subAreaNode *nxt; // 分区后向指针
|
||
} subHead;
|
||
|
||
|
||
// 初始化空闲分区链
|
||
void intSubArea() {
|
||
// 分配初始分区内存
|
||
subAreaNode *fir = (subAreaNode *)malloc(sizeof(subAreaNode));
|
||
// 给首个分区赋值
|
||
fir->addr = 0;
|
||
fir->size = 95; // 内存初始大小
|
||
fir->state = F;
|
||
fir->taskId = -1;
|
||
fir->pre = &subHead;
|
||
fir->nxt = NULL;
|
||
// 初始化分区头部信息
|
||
subHead.pre = NULL;
|
||
subHead.nxt = fir;
|
||
}
|
||
|
||
//// 首次适应算法
|
||
//int firstFit(int taskId, int size)
|
||
//{
|
||
//subAreaNode *p = subHead.nxt;
|
||
//while (p != NULL)
|
||
//{
|
||
//if (p->state == F && p->size >= size)
|
||
//{
|
||
//// 找到要分配的空闲分区
|
||
//if (p->size - size <= 10)
|
||
//{
|
||
//// 整块分配
|
||
//p->state = W;
|
||
//p->taskId = taskId;
|
||
//}
|
||
//else {
|
||
//// 分配大小为size的区间
|
||
//subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode));
|
||
//node->addr = p->addr + size;
|
||
//node->size = p->size - size;
|
||
//node->state = F;
|
||
//node->taskId = -1;
|
||
//// 修改分区链节点指针
|
||
//node->pre = p;
|
||
//node->nxt = p->nxt;
|
||
//if (p->nxt != NULL)
|
||
//{
|
||
//p->nxt->pre = node;
|
||
//}
|
||
//p->nxt = node;
|
||
//// 分配空闲区间
|
||
//p->size = size;
|
||
//p->state = W;
|
||
//p->taskId = taskId;
|
||
//}
|
||
//printf("内存分配成功！\n");
|
||
//return 1;
|
||
//}
|
||
//p = p->nxt;
|
||
//}
|
||
//printf("找不到合适的内存分区，分配失败...\n");
|
||
//return 0;
|
||
//}
|
||
|
||
|
||
//struct subAreaNode *node
|
||
|
||
void BestFit(int taskId, int size) { //最坏适应
|
||
//最佳块指针
|
||
struct subAreaNode *q = NULL;
|
||
subAreaNode *node = subHead.nxt;
|
||
//首先找到第一个满足条件的空闲块
|
||
while (node != NULL) {
|
||
if (node->state == F && node->size >= size) {
|
||
q = node;
|
||
break;
|
||
}
|
||
//如果下一个为空则说明没有空闲区可以分配
|
||
if (node->nxt == NULL) {
|
||
printf("分配失败，没有足够的空间！\n");
|
||
break;
|
||
} else {
|
||
node = node->nxt;
|
||
}
|
||
|
||
}
|
||
//遍历寻找最佳的空闲块
|
||
while (node != NULL) {
|
||
if (node->state == F && node->size >= size && node->size < q->size) { //空闲的空间
|
||
q = node;
|
||
}
|
||
node = node->nxt;
|
||
}
|
||
if (q->size > size) { //最佳空闲块的大小大于需求大小
|
||
//分配后剩余的空间
|
||
struct subAreaNode *p = (struct subAreaNode*)malloc(sizeof(struct subAreaNode));
|
||
p->addr = q->addr + size;
|
||
p->size = q->size - size;
|
||
p->state = F;
|
||
p->taskId = -1;
|
||
//分配的空间
|
||
q->taskId = taskId;
|
||
q->size = size;
|
||
q->state = W;
|
||
//改变节点的连接
|
||
p->nxt = q->nxt;
|
||
q->nxt = p;
|
||
} else if (q->size == size) { //最佳空闲块空间大小和需求相等
|
||
q->taskId = taskId;
|
||
q->size = size;
|
||
q->state = W;
|
||
}
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
int freeSubArea(int taskId) { // 回收内存
|
||
int flag = 0;
|
||
subAreaNode *p = subHead.nxt, *pp;
|
||
while (p != NULL) {
|
||
if (p->state == W && p->taskId == taskId) {
|
||
flag = 1;
|
||
if ((p->pre != &subHead && p->pre->state == F)
|
||
&& (p->nxt != NULL && p->nxt->state == F)) {
|
||
// 情况1：合并上下两个分区
|
||
// 先合并上区间
|
||
pp = p;
|
||
p = p->pre;
|
||
p->size += pp->size;
|
||
p->nxt = pp->nxt;
|
||
pp->nxt->pre = p;
|
||
free(pp);
|
||
// 后合并下区间
|
||
pp = p->nxt;
|
||
p->size += pp->size;
|
||
p->nxt = pp->nxt;
|
||
if (pp->nxt != NULL) {
|
||
pp->nxt->pre = p;
|
||
}
|
||
free(pp);
|
||
} else if ((p->pre == &subHead || p->pre->state == W)
|
||
&& (p->nxt != NULL && p->nxt->state == F)) {
|
||
// 情况2：只合并下面的分区
|
||
pp = p->nxt;
|
||
p->size += pp->size;
|
||
p->state = F;
|
||
p->taskId = -1;
|
||
p->nxt = pp->nxt;
|
||
if (pp->nxt != NULL) {
|
||
pp->nxt->pre = p;
|
||
}
|
||
free(pp);
|
||
} else if ((p->pre != &subHead && p->pre->state == F)
|
||
&& (p->nxt == NULL || p->nxt->state == W)) {
|
||
// 情况3：只合并上面的分区
|
||
pp = p;
|
||
p = p->pre;
|
||
p->size += pp->size;
|
||
p->nxt = pp->nxt;
|
||
if (pp->nxt != NULL) {
|
||
pp->nxt->pre = p;
|
||
}
|
||
free(pp);
|
||
} else {
|
||
// 情况4：上下分区均不用合并
|
||
p->state = F;
|
||
p->taskId = -1;
|
||
}
|
||
}
|
||
p = p->nxt;
|
||
}
|
||
if (flag == 1) {
|
||
// 回收成功
|
||
printf("内存分区回收成功...\n");
|
||
return 1;
|
||
} else {
|
||
// 找不到目标作业，回收失败
|
||
printf("找不到目标作业，内存分区回收失败...\n");
|
||
return 0;
|
||
}
|
||
}
|
||
|
||
// 显示空闲分区链情况
|
||
void showSubArea() {
|
||
printf("\n");
|
||
printf(" 当前的内存分配情况如下： \n");
|
||
printf(" W:工作状态 F:空闲状态 \n");
|
||
printf("___________________________________________\n");
|
||
printf("| 起始地址 | 空间大小 | 工作状态 | 作业号 |\n");
|
||
subAreaNode *p = subHead.nxt;
|
||
while (p != NULL) {
|
||
printf("___________________________________________\n");
|
||
|
||
printf(" %3d k |", p->addr);
|
||
printf(" %3d k |", p->size);
|
||
printf(" %s |", p->state == F ? "F" : "W");
|
||
if (p->taskId > 0) {
|
||
printf(" %2d ", p->taskId);
|
||
} else {
|
||
printf(" ");
|
||
}
|
||
printf("\n");
|
||
p = p->nxt;
|
||
}
|
||
printf("___________________________________________\n");
|
||
}
|
||
|
||
int main() {
|
||
int ope, taskId, size;
|
||
char name;
|
||
int ArriveTime;
|
||
int ServerTime;
|
||
// 初始化空闲分区链
|
||
intSubArea();
|
||
|
||
// 模拟动态分区分配算法
|
||
while (1) {
|
||
printf("默认FF(首次适应算法)\n");
|
||
printf("_________________________________________\n");
|
||
printf("| 1: 分配内存 2: 回收内存 0: 退出 |\n");
|
||
printf("|________________________________________|\n");
|
||
scanf("%d", &ope);
|
||
if (ope == 0) break;
|
||
if (ope == 1) {
|
||
// 模拟分配内存
|
||
printf("请输入作业号： ");
|
||
scanf("%d", &taskId);
|
||
printf("请输入作业名： ");
|
||
scanf("%s", &name);
|
||
printf("请输入到达时间： ");
|
||
scanf("%d", &ArriveTime);
|
||
printf("请输入服务时间： ");
|
||
scanf("%d", &ServerTime);
|
||
printf("请输入需要分配的内存大小(KB)： ");
|
||
scanf("%d", &size);
|
||
if (size <= 0) {
|
||
printf("错误：分配内存大小必须为正值\n");
|
||
continue;
|
||
}
|
||
// 调用分配算法
|
||
|
||
//firstFit(taskId, size);
|
||
BestFit(taskId, size);
|
||
|
||
// 显示空闲分区链情况
|
||
showSubArea();
|
||
} else if (ope == 2) {
|
||
// 模拟回收内存
|
||
printf("请输入要回收的作业号： ");
|
||
scanf("%d", &taskId);
|
||
freeSubArea(taskId);
|
||
// 显示空闲分区链情况
|
||
showSubArea();
|
||
} else {
|
||
printf("错误：请输入 0/1/2\n");
|
||
}
|
||
}
|
||
printf("分配算法模拟结束\n");
|
||
system("pause");
|
||
return 0;
|
||
}
|