www.pudn.com > DynamicMemoryManage.rar > memory.cpp
///实验 :动态分区存储管理方式的主存分配回收
/*实验内容:编写程序完成动态分区存储管理方式的主存分配回收的实现。*/
//////////实验具体包括：首先确定主存空间分配表；然后采用最优适应
/////////算法完成主存空间的分配，完成主存空间的回收；最后编写主函数对所作工作进程测试。
#include
#include
#define FREE 10 //假定系统允许的空闲区表最大为FREE
#define TASK 10 //假定系统允许的最大作业数量为TASK
#define MINSIZE 1000 //分区最小字节数，小于该值的区域为碎片
typedef struct used
{
float address; //已分分区起始地址
float length; //已分分区长度
int flag; //已分配区表登记栏标志，0表示空栏目，实验中只支持数字作业名
}USED_TABLE; //已分配区表结构
typedef struct free
{
float address; //空闲区起始地址
float length; //空闲区长度
int flag; //空闲区表登记栏标志，0表示空栏目，1表示未分配
}FREE_TABLE; //空闲区表结构
typedef struct task
{
int pId; //任务标识
float length; //任务所需长度
}sTASK; //任务结构
USED_TABLE used_table[TASK]; //已分配分区表
FREE_TABLE free_table[FREE]; //空闲区表
//分配函数//////////////////////////////////////////
int assign(int pId, float pLength)
{ int n;
for( n=0; n= pLength))
{ //如果i区是未分配的且满足作业要求
if(best == -1)
{ //如果i是第一个未分配的
best = i; //则记i为当前查找到的最符合作业要求的空闲区
}
else if(free_table[i].length < free_table[best].length)
{ //或i空闲区的长度小于best空闲区的长度
best = i; //则记i为当前查找到的最符合作业要求的空闲区
}
}
}
//查找完毕
//未找到满足需求的分区
if(best == -1) //如果未找到满足需求的分区
{
printf("主存分配失败\n"); //打印错误信息
return -1; //退出
}
//找到满足需求的分区,开始主存分配
if((free_table[best].length - pLength) <= MINSIZE) //如果best的长度－作业需求长度 小于 MINSIZE
{ //分配给作业整个分区
free_table[best].flag = 0; //状态置为空
address = free_table[best].address; //记录下best的地址
pLength = free_table[best].length; //记录下best的长度
}
else
{ //切割空闲区
free_table[best].length = free_table[best].length - pLength; //best栏的长度减去作业要求的长度
address = free_table[best].address + free_table[best].length; //记录下分配给作业的主存地址
}
int j = 0; //访问已分配区表的指针
while(j < TASK) //第j栏属于已分配表的栏
{
if(used_table[j].flag == 0) //如果第j栏为空
break; //则跳出
j++; //指针后移
}
if(j < TASK) //如果第j栏是已分配表中的一栏
{ //填写已分配区表
used_table[j].address = address; //填写地址
used_table[j].length = pLength; //填写长度
used_table[j].flag = pId; //填写作业名
return 1; //成功
}
else //第j栏不是已分配表中的一栏
{
if(free_table[best].flag == 0) //best为空
{
printf("主存未分配\n"); //打印分配失败
}
else //best不为空
{
free_table[best].length += pLength; //恢复best的原长度
}
printf("已分配区表长度不足，分配失败\n"); //打印分配失败信息
return -1; //失败
}
}
//分配函数结束/////////////////////////////////////
//回收函数//////////////////////////////////////////
int recycle(int pId)
{
///回收作业pId的内存空间
int rId; //标识要回收的作业号对应的在已分配表中的序号
rId = 0; //赋初值为0
while(rId < TASK) //当rId为已分配区表中的一栏
{
if(used_table[rId].flag == pId) //当找到要回收的作业号对应的在已分配表中的序号
break; //跳出循环
rId++; //指针后移
}
if(rId >= TASK) //如果rId不是已分配区表中的一栏，则
{
printf("未找到作业%d，回收失败\n", pId); //未找到作业
return -1; //退出
}
//rId是已分配区表中的一栏，开始回收
int up = -1; //上邻空闲区序号
int down = -1; //下邻空闲区序号
float rAddress; //记录已分配区表中第rId栏的起始地址
float rLength; //记录已分配区表中第rId栏的长度
rAddress = used_table[rId].address; //记录已分配区表中第rId栏的起始地址
rLength = used_table[rId].length; //记录已分配区表中第rId栏的长度
used_table[rId].flag = 0; //变为空栏
for(int i = 0; i < FREE; i++)
{ //第i栏是空闲区表中的一栏或回收的上邻和下邻未找完
if(free_table[i].flag == 0) //如果第i栏为未分配，则
continue; //继续下一次循环，终止以下的工作
if((free_table[i].address + free_table[i].length) == rAddress) //如果第i栏是回收区的上邻
up = i; //记录下上邻号
else if(free_table[i].address == (rAddress + rLength)) //如果第i栏是回收区的下邻
down = i; //记录下下邻号
if((up != -1) && (down != -1)) //如果找到了上邻和下邻
break; //跳出循环
}
if(up != -1) //回收区有上邻
{
if(down != -1) //回收区有下邻
{
free_table[up].length += free_table[down].length + rLength; //修改上邻的长度
free_table[down].flag = 0; //下邻置为空
free_table[down].address = -1; //置其地址为无效
free_table[down].length = 0; //长度为0
}
else //没有下邻
{
free_table[up].length += rLength; //修改上邻长度
}
}
else //没有上邻
{
if(down != -1) //有下邻
{
free_table[down].length += rLength; //下邻长度加上回收的长度
free_table[down].address = rAddress; //下邻地址改为回收区的地址
}
else //没有下邻
{
int t = 0; //访问指针
for(t = 0; t < FREE; t++) //寻找一个未分配的栏
{
if(free_table[t].flag == 0) //找到一个为空的栏
break; //跳出循环
}
if(t < FREE) //第t栏是空闲区表中的一栏
{ //归还分区填入空闲区表
free_table[t].address = rAddress; //填写地址
free_table[t].length = rLength; //填写长度
free_table[t].flag = 1; //未分配
}
else
{
used_table[rId].flag = pId; //恢复已分配区表要回收的作业号
printf("空闲区长度不足，回收失败\n"); //打印错误信息
return -1;
}
}
}
return 1; //返回成功
}
//回收函数结束//////////////////////////////////////
//初始化函数////////////////////////////////////////
void initial()
{
///初始化已分配区表和空闲区表
//初始化已分配区表
for(int i = 0; i < TASK; i++)
{
used_table[i].address = -1; //初始化为无效地址
used_table[i].flag = 0; //初始化为空
used_table[i].length = 0; //初始化长度为0
}
//初始化空闲区表，初始主存为一个大的空闲块
free_table[0].address = 0; //初始地址从0开始
free_table[0].length = 100000; //设空闲区大小为100k
free_table[0].flag = 1; //初始为未分配
for(int j = 1; j < FREE; j++) //将其余栏初始为空
{
free_table[j].address = -1; //初始化为无效地址
free_table[j].length = 0; //长度为0
free_table[j].flag = 0; //初始化主存为空
}
}
//初始化函数结束///////////////////////////////////
//从文件导入任务队列创建 函数////////////////////////////
int importToCreate(char *file, char *sFile)
{
FILE *fp, *sFp; //文件指针
if((fp = fopen(file, "rb")) == NULL) //打开文件（只读）
{
printf("文件打开错误\n"); //打印错误信息
return -1; //退出
}
if((sFp = fopen(sFile, "a")) == NULL) //打开文件（追加）
{
printf("文件打开错误\n"); //打印错误信息
return -1; //退出
}
sTASK task; //任务，保存从文件读出的任务
int suc; //标识是否成功
while(!feof(fp)) //文件不到结尾则继续
{
fscanf(fp, "%d, %f", &task.pId, &task.length); //从文件中读出一条任务
suc = assign(task.pId, task.length); //分配主存
if(suc == 1) //成功分配
{
fprintf(sFp, "成功为作业%d 分配主存\n", task.pId); //写入文件
printf("成功为作业%d 分配主存\n", task.pId); //打印信息
}
else
{
fprintf(sFp, "为作业%d 分配主存失败\n", task.pId); //写入文件
}
//
//写表状态信息到文件sFile
char line[] = "----------------------------------------------------"; //分隔线
char header1[] = "任务:\npId address length"; //表头1
char header2[] = "主存:\naddress length flag"; //表头2
fprintf(sFp, "%s\n", line); //写入分隔线
fprintf(sFp, "%s\n", header1); //写表头1
for(int i = 0; i < TASK; i++)
{ ///遍历所有已分配区表栏
if(used_table[i].flag != 0) //如果该栏有任务
{
//打印该栏数据
fprintf(sFp, "%2d%9.0f%12.0f\n", used_table[i].flag,used_table[i].address,used_table[i].length);
}
}
fprintf(sFp, "\n%s\n", header2); //打印表头2
for(int j = 0; j < FREE; j++) //打印所有空闲区表内容
{
//内容
fprintf(sFp, "%3.0f%12.0f%5d\n",free_table[j].address,free_table[j].length,free_table[j].flag);
}
fprintf(sFp, "%s\n", line); //写入分隔线
////////////////////////////////////
}
fclose(sFp); //关闭文件sFp
fclose(fp); //关闭文件fp
return 1; //返回成功
}
//导入创建 函数结束////////////////////////////
//导入回收 函数/////////////////////////////////
int importToRecycle(char *file, char *sFile)
{
FILE *fp, *sFp; //文件指针
if((fp = fopen(file, "rb")) == NULL) //打开文件（只读）
{
printf("文件打开错误\n"); //打印错误信息
return -1; //退出
}
if((sFp = fopen(sFile, "a")) == NULL) //打开文件（追加）
{
printf("文件打开错误\n"); //打印错误信息
return -1; //退出
}
//开始读文件并回收
int suc; //标识是否成功
int pId; //记录读出的任务标识
while(!feof(fp)) //文件不到结尾则继续
{
fscanf(fp, "%d", &pId); //从文件中读出一条记录
suc = recycle(pId); //回收
if(suc == 1) //回收成功
{
fprintf(sFp, "回收作业%d 空间成功\n", pId); //写入文件
printf("成功回收任务%d 的空间\n", pId); //提示信息
}
else //回收失败
{
fprintf(sFp, "回收作业%d 空间失败\n", pId); //写入文件
}
//写表状态到文件
char line[] = "----------------------------------------------------"; //分隔线
char header1[] = "任务:\npId address length"; //表头1
char header2[] = "主存:\naddress length flag"; //表头2
fprintf(sFp, "%s\n", line); //写入分隔线
fprintf(sFp, "%s\n", header1); //写表头1
for(int i = 0; i < TASK; i++)
{ ///遍历所有已分配区表栏
if(used_table[i].flag != 0) //如果该栏有任务
{
//打印该栏数据
fprintf(sFp, "%2d%9.0f%12.0f\n", used_table[i].flag,used_table[i].address,used_table[i].length);
}
}
fprintf(sFp, "\n%s\n", header2); //打印表头2
for(int j = 0; j < FREE; j++) //打印所有空闲区表内容
{
//内容
fprintf(sFp, "%3.0f%12.0f%5d\n",free_table[j].address,free_table[j].length,free_table[j].flag);
}
fprintf(sFp, "%s\n", line); //写入分隔线
//////////////////////////////////////////////
}
fclose(sFp); //关闭文件sFp
fclose(fp); //关闭文件fp
return 1; //成功完成
}
//导入回收函数结束/////////////////////////////
//保存当前状态到文件函数///////////////////////////
int saveToFile(char *file)
{
FILE *fp; //文件指针
if((fp = fopen(file, "a")) == NULL) //打开文件（追加）
{
printf("文件打开错误\n"); //打印错误信息
return -1; //退出
}
char line[] = "----------------------------------------------------"; //分隔线
char header1[] = "任务:\npId address length"; //表头1
char header2[] = "主存:\naddress length flag"; //表头2
fprintf(fp, "%s\n", line); //写入分隔线
fprintf(fp, "%s\n", header1); //写表头1
for(int i = 0; i < TASK; i++)
{ ///遍历所有已分配区表栏
if(used_table[i].flag != 0) //如果该栏有任务
{
//打印该栏数据
fprintf(fp, "%2d%9.0f%12.0f\n", used_table[i].flag,used_table[i].address,used_table[i].length);
}
}
fprintf(fp, "\n%s\n", header2); //打印表头2
for(int j = 0; j < FREE; j++) //打印所有空闲区表内容
{
//内容
fprintf(fp, "%3.0f%12.0f%5d\n",free_table[j].address,free_table[j].length,free_table[j].flag);
}
fprintf(fp, "%s\n", line); //写入分隔线
fclose(fp);
return 1; //返回成功
}
//保存当前状态到文件 函数结束///////////////////////
//打印内存使用情况////////////////////////////////
void prtMem()
{
printf("----------------------------------------------------\n"); //分隔线
printf("任务:\npId address length\n"); //打印标题
for(int i = 0; i < TASK; i++)
{ ///遍历所有已分配区表栏
if(used_table[i].flag != 0) //如果该栏有任务
{
//打印该栏数据
printf("%2d%9.0f%12.0f\n", used_table[i].flag,used_table[i].address,used_table[i].length);
}
}
printf("\n"); //打印一个空行
printf("主存:\naddress length flag\n"); //打印标题
for(int j = 0; j < FREE; j++) //打印所有空闲区表内容
{
//内容
printf("%3.0f%12.0f%5d\n",free_table[j].address,free_table[j].length,free_table[j].flag);
}
printf("----------------------------------------------------\n"); //分隔线
}
//打印结束////////////////////////////////////////
//打印菜单函数////////////////////////////////////
void menu()
{
//打印菜单
printf("\t1: 创建"); //选项1
printf("\t2: 回收"); //选项2
printf("\t3: 用文件导入创建或者导入回收"); //选项3
printf("\t4: 退出\n"); //选项4
printf("请选择："); //提示选择
}
void menu1()
{
printf("\t1: 导入任务并创建\n"); //选项3
printf("\t2: 导入任务并回收\n");//选项4
printf("\t3: 退回上一级菜单\n");//选项5
printf("请选择：");
}
//打印菜单函数结束///////////////////////////////
//main/////////////////////////////////////////////
void main()
{
///初始化
initial();
int c; //选择指针
printf(" 实验二 动态分区存储管理方式的主存分配回收 \n"); //打印标题
hello: menu(); //打印菜单
scanf("%d", &c);//输入选择
while(c != 4) //没选择退出，则继续
{
if(c == 1)
{ //创建任务，为之分配主存空间
int p; //任务标识
float m; //任务所需主存空间
printf("输入任务ID: "); //提示输入任务标识
scanf("%d", &p); //输入任务标识
printf("输入占用的主存空间: ", p); //提示输入其所需主存空间
scanf("%f", &m); //输入其所需主存空间
assign(p, m); //为任务p分配其所需主存空间
prtMem(); //打印当前已分配区表和空闲区表状态
}
else if(c == 2)
{ //回收主存空间
int pi; //任务标识
printf("输入要回收的任务ID: "); //提示输入任务标识
scanf("%d", &pi); //输入任务标识
recycle(pi); //回收任务pi的主存空间
prtMem(); //打印当前已分配区表和空闲区表状态
}
else if(c == 3)
{ int choose;//选择选项
menu1();
scanf("%d",&choose);
if(choose ==3)
{goto hello;}
while(choose !=3)
{
if (choose == 1)
//从文件导入任务队列创建
{
int suc; //标识是否成功创建
char *fileName; //文件名
char *sFileName; //保存表状态的文件名
fileName = (char *)malloc(10); //为fileName分配内存
sFileName = (char *)malloc(10); //为sFileName分配内存
printf("输入任务列表文件名: "); //提示输入文件名
scanf("%s", fileName); //输入文件名
printf("输入保存表状态的文件名:"); //提示输入文件名
scanf("%s", sFileName); //输入文件名
suc = importToCreate(fileName, sFileName); //从文件导入任务并分配主存
if(suc == 1) //成功创建
printf("已成功完成分配任务\n"); //打印信息
prtMem(); //打印当前已分配区表和空闲区表状态
}
else if(choose == 2)
{
//从文件导入回收队列回收
int suc; //标识是否成功完成
char *fileName; //文件名
char *sFileName; //保存表状态的文件名
fileName = (char *)malloc(10); //为fileName分配内存
sFileName = (char *)malloc(10); //为sFileName分配内存
printf("输入回收队列文件名："); //提示输入文件名
scanf("%s", fileName); //输入文件名
printf("输入保存表状态的文件名:"); //提示输入文件名
scanf("%s", sFileName); //输入文件名
suc = importToRecycle(fileName, sFileName); //回收
if(suc == 1) //成功
printf("回收完毕\n"); //打印信息
}
else
printf("choose error\n");
menu1();
scanf("%d",&choose);
}
}
// else
// printf("您输入了错误字符");
menu(); //打印菜单
scanf("%d", &c);//接受选择
}
}
//end of main//////////////////////////////////////