存储管理实验报告
题目：1。存储管理
描述请求分页存储管理。
一. 产生一个作业及作业页面序列P(pi)，例如：P(0,2,3,4,1,5,2,3,0,4,1,5)。
二. 分配物理内存块数M。
三. 采用FIFO，LRU置换算法。
四. 设计原理：本程序提供两种分区管理法供用户使用，这两种算法是最佳适应算法和首次适应算法。
最佳适应算法要求将所有的空闲区，按其大小以递增的顺序形成一空闲区链。这样，第一次找到的满足要求的空闲区，必然是最优的。但该算法会留下许多这样难以利用的小空闲区。
首次适应算法要求空闲分区链以地址递增的次序链接。在进行内存分配时，从链首开始顺序查找，直至找到一个能满足其大小要求的空闲分区为止。然后，再按照作业的大小，从该分区中划出一快内存空间分配该请求者，余下的空闲分区仍留在空闲链中。
三．不足之处：
该程序可以用文件形式输入作业的信息，但是该文件没有绑定在程序中。不过，用户用键盘输入的作业的信息会自动保存到该文件中，下次当以文件形式输入作业信息时，文件中的内容是上一次用户用键盘输入的内容。
四．源程序以及解释：
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
int memoryStartAddress = -1;
int memorySize = -1;
struct jobList
//作业后备队列的链结点
{
int id; //作业的ID号
int size; //作业的大小
int status; //作业状态
struct jobList *next;
};
struct freeList //空闲链的链结点
{
int startAddress; //空闲分区的首地址
int size; //空闲分区的大小
struct freeList *next;
};
struct usedList //已分配内存的作业链
{
int startAddress; //以分配内存的首地址
int jobID;
struct usedList *next;
};
void errorMessage(void) //出错信息
{
printf("\n\t错误!\a");
printf("\n按任意键继续!");
getch();
exit(1);
}
void openFile(FILE **fp,char *filename,char *mode) //打开文件函数
{
if((*fp = fopen(filename,mode)) == NULL)
{
printf("\n不能打开 %s.",filename);
errorMessage();
}
}
void makeFreeNode(struct freeList **empty,int startAddress,int size)//申请内存空间
{
if((*empty = malloc(sizeof(struct freeList))) == NULL)
{
printf("\n没有足够空间.");
errorMessage();
}
(*empty)->startAddress = startAddress; //当有足够空间时，则分配
(*empty)->size = size;
(*empty)->next = NULL;
}
void iniMemory(void) //输入要求分配内存的首地址，大小
{
char MSA[10],MS[10];
printf("\n请输入要分配内存的首地址 !");
scanf("%s",MSA);
memoryStartAddress = atoi(MSA);
printf("\n请输入要分配内存的大小!");
scanf("%s",MS);
memorySize = atoi(MS);
}
char selectFitMethod(void) //选择分区管理算法
{
FILE *fp;
char fitMethod;
do{
printf("\n\n请选择分区管理的算法!\
\n 1 最佳适应算法 \
\n 2 首次适应算法\n");
fitMethod = getche();
}while(fitMethod < '1' || fitMethod > '3'); //选择出错时
openFile(&fp,"d:\\result.cl","a");
switch(fitMethod)
{
case '1':
fprintf(fp,"\n\n\n\n\t 最佳适应算法");
fprintf(fp,"\n**********************************************");
break;
case '2':
fprintf(fp,"\n\n\n\n\t首次适应算法");
fprintf(fp,"\n**********************************************");
break;
}
fclose(fp);
return fitMethod;
}
void inputJob(void) //输入作业的信息
{
int /*id,size, */status = 0,jobnum = 0;
FILE *fp;
char id[10],size[10];
openFile(&fp,"d:\\job.cl","w");
fprintf(fp,"作业名\t大小\t状态");
printf("\n\n\n\n请输入作业名和大小!
\n输入0 0退出 ，job_ID由数字组成\n\n\njob_ID\tsize\n");
do{
/* scanf("%d%d",&id,&size); */
scanf("%s\t%s",id,size); //保存作业ID，大小
if(atoi(id) > 0 && atoi(size) > 0)
{
fprintf(fp,"\n%s\t%s\t%d",id,size,status);
/* fprintf(fp,"\n%d\t%d\t%d",id,size,status); */
jobnum++;
}
else break;
}while(1);
if(jobnum)
printf("\n完成输入!");
else
{
printf("\n没有请求分配内存.");
errorMessage();
}
fclose(fp);
}
int makeJobList(struct jobList **jobs) //把作业插入分区
{
char jobID[10],size[10],status[10];
struct jobList *rear;
FILE *fp;
openFile(&fp,"d:\\job.cl","r");
fscanf(fp,"%s%s%s",jobID,size,status);
if((*jobs = malloc(sizeof(struct jobList))) == NULL) //当没有空闲分区时
{
printf("\n没有足够空间 .");
fclose(fp);
errorMessage();
}
rear = *jobs;
(*jobs) -> next = NULL;
while(!feof(fp))
{
struct jobList *p;
fscanf(fp,"%s%s%s",jobID,size,status);
if((p = malloc(sizeof(struct jobList))) == NULL)
{
printf("\n没有足够空间.");
fclose(fp);
errorMessage();
}
p -> next = rear -> next; //插入已在分区的作业队列中
rear -> next = p;
rear = rear -> next;
rear -> id = atoi(jobID);
rear -> size = atoi(size);
rear -> status = atoi(status);
}
fclose(fp);
return 0;
}
int updateJobFile(struct jobList *jobs)
{
FILE *fp;
struct jobList *p;
openFile(&fp,"d:\\job.cl","w");
fprintf(fp,"job_ID\tsize\tstatus");
for(p = jobs -> next;p;p = p -> next)
fprintf(fp,"\n%d\t%d\t%d",p -> id,p -> size,p -> status);
fclose(fp);
return 0;
}
int showFreeList(struct freeList *empty) //在屏幕上显示空闲分区
{
FILE *fp;
struct freeList *p = empty -> next;
int count = 0;
openFile(&fp,"d:\\result.cl","a");
fprintf(fp,"\n\n显示空闲内存");
printf("\n\n显示空闲内存");
if(p)
{
fprintf(fp,"\nnumber\tsize\tstartAddress");
printf("\n序号\t大小\t开始地址"); //显示空闲分区的大小和首地址
for(;p;p = p -> next)
{
fprintf(fp,"\n%d\t%d\t%d",++count,p -> size,p -> startAddress);
printf("\n%d\t%d\t%d",count,p -> size,p -> startAddress);
}
fclose(fp);
return 1;
}
Else //没有空闲分区
{
fprintf(fp,"\n内存已分配完 !");
printf("\n内存已分配完!");
fclose(fp);
return 0;
}
}
void getJobInfo(struct jobList *jobs,int id,int *size,int *status) //查找作业是否在分区中
{
struct jobList *p = jobs->next;
while(p && p->id != id) //删除作业
p = p->next;
if(p == NULL)
{
printf("\n不能找到作业 : %d .",id);
errorMessage();
}
else
{
*size = p -> size;
*status = p -> status;
}
}
void updateJobStatus(struct jobList **jobs,int id,int status) //改变作业的状态
{
struct jobList *p = (*jobs)->next;
while(p && p->id != id)
p = p->next;
if(p == NULL)
{
printf("\n不能找到作业 : %d .",id);
errorMessage();
}
else
p -> status = status; //作业状态
}
int showUsedList(struct jobList *jobs,struct usedList *used) //显示以分配的分区
{
FILE *fp;
struct usedList *p = used -> next;
int count = 0,size,status;
openFile(&fp,"d:\\result.cl","a");
fprintf(fp,"\n\n显示已分配的内存");
printf("\n\n显示已分配的内存");
if(p)
{
fprintf(fp,"\nnumber\t作业名\t大小\t开始地址");
printf("\nnumber\t作业名\t大小\t开始地址"); //显示分区中的作业信息
for(;p;p = p -> next)
{
getJobInfo(jobs,p -> jobID,&size,&status);
fprintf(fp,"\n%d\t%d\t%d\t%d",++count,p -> jobID,size,p -> startAddress);
printf("\n%d\t%d\t%d\t%d",count,p -> jobID,size,p -> startAddress);
}
fclose(fp);
return 1;
}
Else //分区中没有作业
{
fprintf(fp,"\n内存中没有作业.");
printf("\n内存中没有作业.");
fclose(fp);
return 0;
}
}
int showJobList(struct jobList *jobs) //分区上的作业
{
struct jobList *p;
p = jobs->next;
if(p == NULL)
{
printf("\n列表上没有作业.");
return 0;
}
printf("\n\nT列表上的作业如下 :\n作业名\t大小\t状态"); //显示作业信息
while(p)
{
printf("\n%d\t%d\t%d",p->id,p->size,p->status);
p = p->next;
}
return 1;
}
void moveFragment(struct jobList *jobs,struct freeList **empty,struct usedList **used) //当回收一部分分区后，进行碎片紧凑
{
int size,status;
struct usedList *p;
int address = memoryStartAddress;
if((*empty)->next == NULL) //当没有空闲分区分配时，可以回收已分配内存
{
printf("\n内存已用完.\
\n你可以先回收一些内存或者 \
\n按任意键再试一次 !");
getch();
return;
}
for(p = (*used) -> next;p;p = p-> next) //插入作业
{
p -> startAddress = address;
getJobInfo(jobs,p -> jobID,&size,&status);
address += size;
}
(*empty) -> next -> startAddress = address; //删除作业，回收内存
(*empty) -> next -> size = memorySize - (address - memoryStartAddress);
(*empty) -> next -> next = NULL;
}
void order(struct freeList **empty,int bySize,int inc) //按顺序排列分区的作业
{
struct freeList *p,*q,*temp;
int startAddress,size;
for(p = (*empty) -> next;p;p = p -> next)
{
for(temp = q = p;q;q = q -> next)
{
switch(bySize)
{
case 0 : switch(inc)
{
case 0:if(q->size < temp->size) //交换作业位置
temp = q;break;
default:if(q->size > temp->size) //交换作业位置
temp = q;break;
} break;
default: switch(inc)
{
case 0:if(q->startAddress < temp->startAddress)
temp = q;break; //交换作业位置
default:if(q->startAddress > temp->startAddress)
temp = q;break; //交换作业位置
} break;
}
}
if(temp != p)
{
startAddress = p->startAddress;
size = p->size;
p->startAddress = temp->startAddress;
p->size = temp->size;
temp->startAddress = startAddress;
temp->size = size;
}
}
}
int allocate(struct freeList **empty,int size) //按要求把分区分该作业
{
struct freeList *p,*prep;
int startAddress = -1;
p = (*empty) -> next;
while(p && p->size < size)
//没有足够分区，删除作业
p = p -> next;
if(p != NULL)
{
if(p -> size > size) //当有足够分区，直接分配
{
startAddress = p -> startAddress;
p -> startAddress += size;
p -> size -= size;
}
else //将整个分区分给一个作业
{
startAddress = p -> startAddress;
prep = *empty;
while(prep -> next != p)
prep = prep -> next;
prep -> next = p -> next;
free(p);
}
}
else printf("\n你可以拼接碎片."); /* Unsuccessful ! */
return startAddress;
}
void insertUsedNode(struct usedList **used,int id,int startAddress)
//在分区中插入作业
{
struct usedList *q,*r,*prer;
if((q = malloc(sizeof(struct usedList))) == NULL) //没有足够空间时
{
printf("\nNot enough to allocate for the used node .");
errorMessage();
}
q -> startAddress = startAddress; //插入作业
q -> jobID = id;
prer = *used;
r = (*used) -> next;
while(r && r->startAddress < startAddress)
{
prer = r;
r = r -> next;
}
q -> next = prer -> next;
prer -> next = q;
}
int finishJob(struct usedList **used,int id,int *startAddress) //删除作业，回收分区
{
struct usedList *p,*prep;
prep = *used;
p = prep -> next;
while(p && p -> jobID != id) //删除作业
{
prep = p;
p = p -> next;
}
if(p == NULL)
{
printf("\n作业: %d 不在内存 !",id); //找不到要删除的作业
return 0;
}
else
{
*startAddress = p->startAddress;
prep -> next = p -> next;
free(p);
return 1;
}
}
void insertFreeNode(struct freeList **empty,int startAddress,int size)//插入空闲分区
{
struct freeList *p,*q,*r;
for(p = *empty;p -> next;p = p -> next) ;
if(p == *empty || p -> startAddress + p -> size < startAddress)
//对空闲分区进行排列
{
makeFreeNode(&r,startAddress,size);
r -> next = p -> next;
p -> next = r;
return ;
}
if(p -> startAddress + p -> size == startAddress) //插入空闲分区
{
p -> size += size;
return ;
}
q = (*empty) -> next;
if(startAddress + size == q -> startAddress) //插入空闲分区
{
q -> startAddress = startAddress;
q -> size += size;
}
else if(startAddress + size < q -> startAddress) //插入空闲分区
{
makeFreeNode(&r,startAddress,size);
r -> next = (*empty) -> next;
(*empty) -> next = r;
}
else
{
while(q -> next && q -> startAddress < startAddress) //插入空闲分区
{
p = q;
q = q -> next;
}
if(p -> startAddress + p -> size == startAddress &&\
q -> startAddress == startAddress + size) //插入空闲分区
{
p -> size += size + q -> size;
p -> next = q -> next;
free(q);
}
else if(p -> startAddress + p -> size == startAddress &&\
q -> startAddress != startAddress + size) //插入空闲分区
{
p -> size += size;
}
else if(p -> startAddress + p -> size != startAddress &&\
q -> startAddress == startAddress + size) //插入空闲分区
{
q -> startAddress = startAddress;
q -> size += size;
}
else
{
makeFreeNode(&r,startAddress,size); //申请作业空间
r -> next = p -> next;
p -> next = r;
}
}
}
void main(void)
{
char fitMethod; //定义变量
FILE *fp; //定义变量
struct jobList *jobs; //定义一个队列
struct freeList *empty; //定义一个队列
struct usedList *used; //定义一个队列
if((used = malloc(sizeof(struct usedList))) == NULL)
{
printf("\n没有足够空间.");
errorMessage();
}
used -> next = NULL;
remove("d:\\result.cl");
makeFreeNode(&empty,0,0);
while(1) //界面设计
{
char ch,step; //定义变量
int id,size,startAddress,status; //定义变量
struct jobList *q;
printf("\n 1 输入作业的信息.\
\n 2 作业放到内存.\
\n 3 完成作业,并回收内存.\
\n 4 当前空闲的内存.\
\n 5 当前已分配的内存.\
\n 6 拼接碎片.\
\n 7 退出.");
printf("\n请选择.\n");
step = getche();
printf("\n");
switch(step)
{
case '1': //当选择1时
openFile(&fp,"d:\\result.cl","a");
fprintf(fp,"\n\n\t输入作业的信息 :)");
used -> next = NULL; //初始化队列
empty->next = NULL; //初始化队列
iniMemory();
makeFreeNode(&(empty->next),memoryStartAddress,memorySize);
fprintf(fp,"\n\n\n你用文件形式输入吗?(Y/N) : ");
//是否用文件形式输出
printf("\n\n\n你用文件形式输入吗 ?(Y/N ): \n");
ch = getche();
fprintf(fp,"\n%c",ch);
fclose(fp);
if(ch != 'Y'&& ch != 'y') //当选择用文件形式输出时
{
inputJob();
}
makeJobList(&jobs);
if(ch == 'Y'|| ch == 'y') //读入文件的作业信息
{
for(q = jobs->next;q;q = q->next)
{
if(q->status == 1)
{
startAddress = allocate(&empty,q->size);
if(startAddress != -1)
{
insertUsedNode(&used,q->id,startAddress);
}
}
}
}
fitMethod = selectFitMethod();
break;
case '2': //当选择2时
if(memoryStartAddress < 0 || memorySize < 1)
{
printf("\n\nBad memory allocated !\a");
break;
}
openFile(&fp,"d:\\result.cl","a"); //打开文件
fprintf(fp,"\n\n\t把作业放到内存");
fprintf(fp,"\n\n\n你用键盘输入作业信息吗?(Y/N): ");
printf("\n\n\n你用键盘输入作业信息吗?(Y/N): \n");
ch = getche();
fprintf(fp,"\n%c",ch);
fclose(fp);
if(ch != 'Y' && ch != 'y') //把作业放到分区中
{
for(q = jobs->next;q;q = q->next)
{
if(q->status == 0)
{
switch(fitMethod) //用不同分区管理算法
{
case '1': order(&empty,0,0);break;
case '2': order(&empty,0,1);break;
case '3': order(&empty,1,0);break;
case '4': order(&empty,1,1);break;
}
startAddress = allocate(&empty,q->size);
if(startAddress != -1)
{
insertUsedNode(&used,q->id,startAddress);
//把作业插入到以分配内存中
updateJobStatus(&jobs,q->id,1);
}
}
}
updateJobFile(jobs);
}
else
{
showJobList(jobs); //显示可操作的作业
openFile(&fp,"d:\\result.cl","a");
fprintf(fp,"\n请从上面的作业中选择一个作业，输入作业名.");
printf("\n请从上面的作业中选择一个作业，输入作业名.");
scanf("%d",&id);
fprintf(fp,"%d\n",id);
getJobInfo(jobs,id,&size,&status); //把作业放入内存
switch(status) //作业的不同状态
{
case 0: printf("\nOk !作业的状态是运行状态!");
fprintf(fp,"\nOk!作业的状态是运行状态 !");fclose(fp);break;
case 1: printf("\n作业在内存中 !");
fprintf(fp,"\n作业在内存中 !");fclose(fp);goto label;
case 2: printf("\n作业已完成!");
fprintf(fp,"\n作业已完成!");fclose(fp);goto label;
default:printf("\nUnexpected job status .Please check you job file.");
fprintf(fp,"\nUnexpected job status .Please check you job file.");
fclose(fp);errorMessage();
}
switch(fitMethod) //不同分区管理方法的实现
{
case '1': order(&empty,0,0);break;
case '2': order(&empty,0,1);break;
case '3': order(&empty,1,0);break;
case '4': order(&empty,1,1);break;
}
startAddress = allocate(&empty,size);
if(startAddress != -1)
{
insertUsedNode(&used,id,startAddress); //插入作业
updateJobStatus(&jobs,id,1); //改变作业状态
updateJobFile(jobs);
}
}
label : ;
break;
case '3': //当选择3时
if(memoryStartAddress < 0 || memorySize < 1)
{
printf("\n\nBad memory allocated !\a");
break;
}
do{
int i;
openFile(&fp,"d:\\result.cl","a");
fprintf(fp,"\n\n\t作业完成(回收内存)");
fclose(fp);
if(showUsedList(jobs,used) == 0)
break;
openFile(&fp,"d:\\result.cl","a"); //打开文件
fprintf(fp,"\n请从上面的作业中选择一个作业，输入作业名.\n输入-1来结束测试 .");
printf("\n请从上面的作业中选择一个作业，输入作业名 .\n输入-1来结束测试 .");
scanf("%d",&id);
fprintf(fp,"%d\n",id);
fclose(fp);
if(id == -1)
break;
getJobInfo(jobs,id,&size,&status); //把作业放入内存
if(status == 1) //作业状态为运行时
{
i = finishJob(&used,id,&startAddress);
if(i)
{
insertFreeNode(&empty,startAddress,size); //插入空闲分区
updateJobStatus(&jobs,id,2); //改变作业状态
updateJobFile(jobs);
}
}
else
{
if(status == 0 || status == 2)
{
if(status == 0)
printf("\n作业不在内存中 !");
else printf("\n作业已完成!");
}
else
{
printf("\nUnexpected job status .\
Please check you job file.");
errorMessage();
}
}
}while(1);
break;
case '4': //当选择4时
openFile(&fp,"d:\\result.cl","a");
fprintf(fp,"\n\n\t显示空闲内存");
fclose(fp);
showFreeList(empty);
break;
case '5': //当选择5时
openFile(&fp,"d:\\result.cl","a");
fprintf(fp,"\n\n\t显示已分配内存");
fclose(fp);
showUsedList(jobs,used);
break;
case '6': //当选择6时
openFile(&fp,"d:\\result.cl","a");
fprintf(fp,"\n\n\t拼接碎片");
fclose(fp);
moveFragment(jobs,&empty,&used);
break;
case '7': //当选择7时
openFile(&fp,"d:\\result.cl","a");
fprintf(fp,"\n\n\tExit :(");
fclose(fp);
exit(0);
default: printf("\n错误输入!");
}
}
getch();
}
五．运行效果：
1．运行EXE文件：
2．首先要选择1，输入要分配内存的首地址，分区大小，输入作业的信息：
3．按ENTER键后，选择分区管理算法：
4．然后选择2,把作业放到内存：
5．到此，用户就可以选择自己想要的操作功能，这里3为例：
6．用户也可以选择其他功能，这里不作介绍。