实验四 主存空间的分配和回收模拟
为了合理地分配和使用这些存储空间，当用户提出申请主存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间和使用情况，找出足够的空闲区域给申请者。当作业撤离归还主存资源时，则存储管理要收回占用的主存空间。主存的分配和回收的实现是与主存储器的管理方式有关的，通过本实验帮助我们理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。
用高级语言完成一个主存空间的分配和回收模拟程序，以加深对内存分配方式及其算法的理解。
2.1 模拟包括3部分：
1）实现特定的内存分配算法
2）实现内存回收模拟
3）每种内存分配策略对应的碎片数统计
2.2 固定分区存储管理
假设内存容量为120KB，并且分别划分成8,16,32,64KB大小的块各一块。
一个进程所需要的内存为0到100个KB。同时假设一个进程在运行过程中所需内存的大小不变。
模拟五个进程到达请求分配与运行完回收情况,输出主存分配表.
2.3 动态分区分配存储管理
采用连续分配方式之动态分区分配存储管理，使用首次适应算法、下次适应算法、最佳适应算法和最坏适应算法4种算法完成设计(任选两种算法)。
（1）在程序运行过程，由用户指定申请与释放。
（2）设计一个已占用分区表，以保存某时刻主存空间占用情况。
（3）设计一个空闲分区表，以保存某时刻主存空间剩余情况。
（4）用两个表的变化情况,反应各进程所需内存的申请与释放情况。
根据指定的实验课题，完成设计、编码和调试工作，完成实验报告。
可以选用Turbo C作为开发环境。也可以选用Windows下的VB，CB或其他可视化环境，利用各种控件较为方便。自主选择实验环境。
我自己编写，但是没有完成的代码，都不知道该怎么去实现
#include<stdio.h> typedef struct AAA{ char name[10]; //名字 int need; //所需空间 }ABC; typedef struct BBB{ char name[10]; int ka; //开始地址 int ja; //结束地址 }XZM //未分配 typedef struct CCC{ char name[10]; int ka; //开始地址 int ja; //结束地址 }WZJ //已分配 int n,which,aaa=0,bbb; int address=512; //内存大小 int system=100; //系统所需内存 ABC www[5]; XZM yyy[5]; // 未分配 WZJ zzz[5]; //已分配 show() { printf("已分配表\n"); printf("名字 开始地址 结束地址"); for(bbb=0;bbb<aaa;bbb++) { printf("%s %d %d",zzz[bbb].name,zzz[bbb].ka,zzz[bbb].ja); } printf("未分配表\n"); printf("名字 开始地址 结束地址"); for(bbb=0;bbb<aaa;bbb++) { printf("%s %d %d",yyy[bbb].name,yyy[bbb].ka,yyy[bbb].ja); } } getit() { printf("\n请选择：1.录入进程 2.回收进程"); scanf("%d",&n); if(n==1) { printf("\n现在请输入各进程的详细信息：\n"); printf("进程名字 所需空间\n"); scanf("%s",&www[aaa].name); scanf("%d",&www[aaa].nt); aaa++; } else { printf("\n请输入要撤回的进程的"); scanf("%d",&n); } } first() { } next() { } select() { int i; zzz[0].name="system"; zzz[0].ka=0; zzz[0].ja=system; printf("\n-------------------------美好生活从这里开始!------------------------\n"); printf("主存空间的分配和回收模拟：\n\n\t1,首次适应 \n\n\t2,下次适应\n"); printf("请选择：\n"); scanf("%d",&i); if(i==1) { printf("\n您选择的是首次适应\n"); getit(); } if(i==2) { printf("\n您选择的是下次适应\n"); getit(); } if(i>3) { printf("\n输入错误,请输入1-2之间的数!\n重新开始:\n"); } } void main() { select(); }
我在网上查找的，然后查考的代码
#include<stdio.h> #include<stdlib.h> #define SIZE 640 // 内存初始大小 #define MINSIZE 5 // 碎片最小值 enum STATE { Free, Busy }; 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 = SIZE; fir->state = Free; 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 == Free && p->size >= size) { // 找到要分配的空闲分区 if(p->size - size <= MINSIZE) { // 整块分配 p->state = Busy; p->taskId = taskId; } else { // 分配大小为size的区间 subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode)); node->addr = p->addr + size; node->size = p->size - size; node->state = Free; 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 = Busy; p->taskId = taskId; } printf("内存分配成功！\n"); return 1; } p = p->nxt; } printf("找不到合适的内存分区，分配失败...\n"); return 0; } // 最佳适应算法 int bestFit(int taskId, int size) { subAreaNode *tar = NULL; int tarSize = SIZE + 1; subAreaNode *p = subHead.nxt; while(p != NULL) { // 寻找最佳空闲区间 if(p->state == Free && p->size >= size && p->size < tarSize) { tar = p; tarSize = p->size; } p = p->nxt; } if(tar != NULL) { // 找到要分配的空闲分区 if(tar->size - size <= MINSIZE) { // 整块分配 tar->state = Busy; tar->taskId = taskId; } else { // 分配大小为size的区间 subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode)); node->addr = tar->addr + size; node->size = tar->size - size; node->state = Free; node->taskId = -1; // 修改分区链节点指针 node->pre = tar; node->nxt = tar->nxt; if(tar->nxt != NULL) { tar->nxt->pre = node; } tar->nxt = node; // 分配空闲区间 tar->size = size; tar->state = Busy; tar->taskId = taskId; } printf("内存分配成功！\n"); return 1; } else { // 找不到合适的空闲分区 printf("找不到合适的内存分区，分配失败...\n"); return 0; } } // 回收内存 int freeSubArea(int taskId) { int flag = 0; subAreaNode *p = subHead.nxt, *pp; while(p != NULL) { if(p->state == Busy && p->taskId == taskId) { flag = 1; if((p->pre != &subHead && p->pre->state == Free) && (p->nxt != NULL && p->nxt->state == Free)) { // 情况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 == Busy) && (p->nxt != NULL && p->nxt->state == Free)) { // 情况2：只合并下面的分区 pp = p->nxt; p->size += pp->size; p->state = Free; 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 == Free) && (p->nxt == NULL || p->nxt->state == Busy)) { // 情况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 = Free; 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("*********************************************\n"); printf("** 起始地址 | 空间大小 | 工作状态 | 作业号 **\n"); subAreaNode *p = subHead.nxt; while(p != NULL) { printf("**-----------------------------------------**\n"); printf("**"); printf("%d k |", p->addr); printf("%d k |", p->size); printf(" %s |", p->state == Free ? "Free" : "Busy"); if(p->taskId > 0) { printf("%d ", p->taskId); } else { printf(" "); } printf("**\n"); p = p->nxt; } printf("*********************************************\n"); } int main() { int option, ope, taskId, size; // 初始化空闲分区链 intSubArea(); // 选择分配算法 while(1) { printf("请选择要模拟的分配算法： 0 表示首次适应算法，1 表示最佳适应算法\n"); scanf("%d", &option); if(option == 0) { printf("你选择了首次适应算法，下面进行算法的模拟\n"); break; } else if(option == 1) { printf("你选择了最佳适应算法，下面进行算法的模拟\n"); break; } else { printf("错误：请输入 0/1\n\n"); } } // 模拟动态分区分配算法 while(1) { printf("\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("请输入需要分配的内存大小(KB)： "); scanf("%d", &size); if(size <= 0) { printf("错误：分配内存大小必须为正值\n"); continue; } // 调用分配算法 if(option == 0) { firstFit(taskId, size); } else { bestFit(taskId, size); } // 显示空闲分区链情况 showSubArea(); } else if(ope == 2) { // 模拟回收内存 printf("请输入要回收的作业号： "); scanf("%d", &taskId); freeSubArea(taskId); // 显示空闲分区链情况 showSubArea(); } else { printf("错误：请输入 0/1/2\n"); } } printf("分配算法模拟结束\n"); return 0; }
这是首次适应的
#include <stdio.h> #include <stdlib.h> #include <string.h> const int CANUSE = 1; const int CANTUSE = 0; //#define MSIZE 128; const int MSIZE = 128; //内存分区 struct MZone { //空闲区起始地址 int begin_addr; //一个连续空闲区的长度 int length; //状态 int state; //内存中任务名 char task_name[32]; //指向下一个空闲分区 struct MZone *next; }; //内存头指针 struct MZone *Mhead = NULL; //showmemory函数，显示当前内存分配情况 void showmemory() { struct MZone *Mpoint = Mhead; printf("内存的使用情况\n"); printf("beginaddr\tlength\tstate\ttask\n"); while( NULL!=Mpoint) { printf("%dk\t\t",Mpoint->begin_addr); printf("%dk\t",Mpoint->length); Mpoint->state?printf("CANUSE\t"):printf("CANTUSE\t"); printf("%s\n",Mpoint->task_name); Mpoint = Mpoint->next; } system("pause"); } //memoallocate函数，用于分配内纯 void memoallocate(void) { struct MZone *Mnew = (struct MZone*)malloc(sizeof(struct MZone)); printf("输入要分配内存大小(kb):\n"); scanf("%d",&Mnew->length); printf("输入任务名:\n"); scanf("%s",&Mnew->task_name); Minsert(Mnew)?printf("分配内存成功\n"):printf("没有符合大小的空闲分区，内存分配失败。\n"); system("pause"); free(Mnew); } //Minsert函数，功能插入任务到空闲分区 int Minsert(struct MZone* Mnew) { struct MZone *Zinsert = Mhead; //flag用于指示是Zinsert到了NULL，既没有内存可以分配 int flag = 1; while( Zinsert->length<Mnew->length || !Zinsert->state) { if( NULL!=Zinsert->next ) { Zinsert = Zinsert->next; } else { Zinsert = Zinsert->next; break; } } if( NULL==Zinsert ) { return 0; } if( MSIZE == Zinsert->begin_addr+Mnew->length ) { Zinsert->state = CANTUSE; strcpy(Zinsert->task_name , Mnew->task_name); Zinsert->next = NULL; return 1; } else { struct MZone *Ztail = (struct MZone *)malloc(sizeof(struct MZone)); Zinsert->state = CANTUSE; strcpy(Zinsert->task_name , Mnew->task_name); Zinsert->length = Mnew->length; Zinsert->next = Ztail; memset( Ztail, 0, sizeof(char)*32 ); Ztail->begin_addr = Zinsert->begin_addr + Mnew->length; Ztail->state = CANUSE; Ztail->length = MSIZE - Ztail->begin_addr; Ztail->next = NULL; return 1; } } //memoreturn函数，用于回收内存 void memoreturn(void) { char tname[32]; printf("输入要收回的任务名\n"); scanf("%s",tname); Mreturn(tname); system("pause"); } //Mreturn函数，功能回收内存 int Mreturn(char taskname[]) { struct MZone *front = NULL; struct MZone *position = Mhead; struct MZone *tail = Mhead->next; while( 0!=strcmp(position->task_name,taskname) ) { front = position; if( NULL!=position->next ) { position = position->next; } else { position = NULL; break; } tail = position->next; } if( NULL==position ) { printf("内存中没有此任务！"); } else { //不能用CANTUSE if( NULL!=tail&&NULL!=front ) { if( front->state&&tail->state ) { front->length = front->length + position->length + tail->length; front->next = tail->next; free(position); free(tail); } else if( front->state&&!tail->state ) { front->length = front->length + position->length; front->next = position->next; free(position); } else if( !front->state&&tail->state ) { position->length = position->length + tail->length; memset( position->task_name, 0, sizeof(char)*32 ); position->next = tail->next; position->state = CANUSE; free(tail); } else if( !front->state&&!tail->state ) { memset( position->task_name, 0, sizeof(char)*32 ); position->state = CANUSE; } } else if( NULL!=tail&&NULL==front ) { if( !tail->state ) { memset( position->task_name, 0, sizeof(char)*32 ); position->state = CANUSE; } else { position->length = position->length + tail->length; position->next = NULL; free(tail); } } else if( NULL==tail&&NULL!=front ) { if(front->state) { front->length = front->length + position->length; front->next = NULL; free(position); } else { memset( position->task_name, 0, sizeof(char)*32 ); position->state = CANUSE; } } else if( NULL==tail&&NULL==front ) { memset( position->task_name, 0, sizeof(char)*32 ); position->state = CANUSE; } printf("内存回收成功！\n"); } } int main(void) { int func_ = 0; //初始化Mhead Mhead = (struct MZone*)malloc(sizeof(struct MZone)); Mhead->begin_addr = 0; Mhead->length = MSIZE; Mhead->state = CANUSE; memset(Mhead->task_name, 0, sizeof(char)*32 ); Mhead->next = NULL; while( 1 ) { printf("******************首次适应算法实现主存分配和回收系统（内存MSIZE）***************"); printf("|1:查看内存分配情况\n"); printf("|2:申请分配内存\n"); printf("|3:申请回收内存\n"); printf("|4:退出程序\n"); printf("********************************************************************************"); scanf("%d",&func_); switch( func_ ) { case 1 :showmemory();break; case 2 :memoallocate();break; case 3 :memoreturn();break; case 4 :return 1; } system("cls"); } }
因为这个实验我一直做不出来，所以一直没有提及作业，后来在网上查找了一些代码，然后看了一下。学习了其他人的编程思路。虽然这些算法的基本思想什么的都懂，但是要我编写出来的时候，我发现没那么简单，所以就看了其他人的，然后学习一下。也很抱歉自己没有写出来，因为一到学期末就各种大作业，所以也一直在忙其他的。对这门课，还有老师的辛勤教学都深深地抱歉。实验也一直没有截图什么的，我会回去补回去的。真的觉得每一个实验都对我们的学习很有帮助。
原文：http://www.cnblogs.com/MyDring/p/5101737.html