存储管理动态分区分配算法的模拟
一、设计任务
完成存储器动态分区分配算法的模拟实现。
二、设计思想
在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法（首次适应算法，最佳适应算法，最后适应算法，最坏适应算法），实现分区存储管理的内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接，等等相关的内容。
三、预期目的
让我们了解操作系统的基本概念，理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。通过课程设计，我们可以进一步理解在计算机系统上运行的其它各类操作系统，并懂得在操作系统的支持下建立自己的应用系统。操作系统课程设计，对于训练学生掌握程序设计、熟悉上机操作和程序调试技术都有重要作用。重点培养学生的思维能力、设计能力、创新能力和排错能力。
四、设计方案
首先是对相关知识的掌握，例如数据结构，计算方法，组成原理以及操作系统等。在这些基本知识的基础上进行扩展，用语言的形式从函数，数据结构原代码，原程序等方面来达到自己想要的目的。该设计就是要达到对各个细节的问题的解决将各个数据块连接起来，最终达到存储器动态分区分配算法的模拟实现。
五、数据结构
1．设计合理的数据结构来描述存储空间：
1）对于未分配出去的部分，用空闲分区链表来描述。
struct freeList
{
int startAddress; /* 分区起始地址 */
int size; /* 分区大小 */
struct freeList *next; /* 分区链表指针 */ }
2）对于已经分配出去的部分，由装入内存的作业占据。
struct usedList
{
int startAddress; /* 分区起始地址 */
int jobID; /* 分区中存放作业ID */
struct usedList *next; /* 分区链表指针 */ }
3）将作业组织成链表。
struct jobList
{
int id; /* 作业ID */
int size; /* 作业大小（需要的存储空间大小）*/
int status; /* 作业状态 0 : new job ,1 : in the memory , 2 : finished . */
struct jobList *next; /* 作业链表指针 */
}
以上将存储空间分为空闲可占用两部分，在usedlist中设jobID而不设size，可以在不增加空间复杂度（与freelist相比）的同时更方便的实现可变分区存储管理（从后面的一些函数的实现上可以得出这个结论）。
尽管设置joblist增加了空间复杂度，但它的存在，使得该程序可以方便的直接利用D盘中的JOB文件。该文件可以认为是一个和其他进程共享的资源。通过这个文件，其他进程写入数据供读取。这中思想在操作系统设计中体现的很多。
2．实现分区存储管理的内存分配功能，选择适应算法（首次适应算法，最佳适应算法，最后适应算法，最坏适应算法）。
基本原理分析：
1） Best fit ：将空闲分区按大小从小到大排序，从头找到大小合适的分区。
2） Worst fit：将空闲分区按大小从大到小排序，从头找到大小合适的分区。
3） First fit ：将空闲分区按起始地址大小从小到大排序，……
4） Last fit ：将空闲分区按起始地址大小从大到小排序，……
由此，可将空闲分区先做合适的排序后用对应的适应算法给作业分配存储空间。排序函数 order（bySize为零则按分区大小排序，否则按分区起始地址；inc为零从小到大排序，否则从大到小排序；通过empty指针返回结果）。
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)
{ /* 按bySize和inc两个参数寻找合适的节点，用temp指向它 */ 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;
}
}
}
3．实现分区存储管理的内存回收算法。
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指针返回创建的空闲节点*/ 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;
}
}
}
4．当碎片产生时，进行碎片的拼接。
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("\nThe memory was used out at all.\nMay be you should finish some jobs first or press any key to try again !");
getch();
return;
}
for(p = (*used) -> next;p;p = p-> next)
/* 循环的修改占用分区的始址 */ {
p -> startAddress = address;
getJobInfo(jobs,p -> jobID,&size,&status);
/* 由作业ID获得作业大小 */ address += size;
}
(*empty)->next->startAddress = address;
/*修改空闲分区的首节点始址、大小*/ (*empty) -> next -> size = memorySize - (address - memoryStartAddress);
(*empty) -> next -> next = NULL; /* 删除首节点后的所有节点 */ }
5．空闲分区队列显示：int showFreeList(struct freeList *empty) 6．作业占用链表显示：int showUsedList(struct jobList
*jobs,struct usedList *used)
从头到尾显示used链，同时通过其中的作业ID在jobs中查对应的大小。
7．从键盘输入作业到D盘的JOB文件：void inputJob(void)
8．从JOB文件中读出作业并创建作业链表：int
makeJobList(struct jobList **jobs)
9．显示作业链表：int showJobList(struct jobList *jobs)
10.更新作业链表中作业的状态：int updateJobFile(struct jobList
*jobs)
11.根据作业链表更新JOB文件： int updateJobFile(struct jobList
*jobs)
12.为作业分配存储空间、状态必须为0：int allocate(struct freeList
**empty,int size)
13.结束一个作业号为id的作业，释放存储空间（由*startAddress返
回空间的起始地址）：int finishJob(struct usedList **used,int id,int *startAddress)
14.插入释放的空间到used链表中（作业号为id，startAddress由函数
13返回）：
void insertUsedNode(struct usedList **used,int id,int startAddress)
15.获取作业的信息：void getJobInfo(struct jobList *jobs,int id,int
*size,int *status)
16.初始化存储空间起始地址、大小：void iniMemory(void)
17.选择适应算法：char selectFitMethod(void)
18.根据参数startAddress、size创建空闲节点，由empty指针返回：
void makeFreeNode(struct freeList **empty,int startAddress,int size)
19.以要求的方式打开文件：void openFile(FILE **fp,char
*filename,char *mode)
20.出现严重错误时显示信息并结束程序；void errorMessage(void)
六、算法流程
1、Dynamic Zonal Memory Management
其中1、Initializiation.按顺序利用了openFile()、iniMemory()、makeFreeNode()、inputJob()（选择利用D盘JOB文件时提供作业信息）、makeJobList()、allocate()、insertUsedNode()（选择利用D盘JOB文件时先将状态为1的作业放到存储空间中，以恢复上次的模拟实验，或使本次模拟时不出错）selectFitMethod()等自编函数。
2、Put job into memory(allocate memory)按顺序利用了showJobList()（选手动逐个为作业分配存储空间时）、openFile()、order()、allocate()、errorMessage()、insertUsedNode()、updateJobStatus()updateJobFile()函数
3、Finish job(reuse memory)按顺序利用了openFile()、showUsedList()、getJobInfo()、insert FreeNode()、updateJobStatus()、updateJobFile()、errorMessage()等自编函数。
4、Show current free list 按顺序利用了openFile()、showFreeList()函数。
5、Show current memory used by jobs按顺序利用了openFile()、showUsedList()函数。
6、Move fragment together按顺序利用了openFile()、moveFragment()函数。
7、Exit按顺序利用了openFile()、exit(0)函数。
七、程序清单
1、原程序
#include
#include
#include
int memoryStartAddress = -1;
int memorySize = -1;
struct jobList
{
int id; /* 作业ID */
int size; /* 作业大小（需要的存储空间大小） */
int status;
/* 作业状态 0 : new job ,1 : in the memory , 2 : finished . */
struct jobList *next; /* 作业链表指针 */
};
struct freeList
{
int startAddress; /* 分区起始地址 */
int size; /* 分区大小 */
struct freeList *next; /* 分区链表指针 */
};
struct usedList
{
int startAddress; /* 分区起始地址 */
int jobID; /* 分区中存放作业ID */
struct usedList *next; /* 分区链表指针 */
};
void errorMessage(void) /*出现严重错误时显示信息并结束程序*/
{
printf("\n\tError !\a");
printf("\nPress any key to exit !");
getch();
exit(1);
}
void openFile(FILE **fp,char *filename,char *mode)
/*以要求的方式打开文件*/
{
if((*fp = fopen(filename,mode)) == NULL)
{
printf("\nCan't open %s in mode %s.",filename,mode);
errorMessage();
}
}
void makeFreeNode(struct freeList **empty,int startAddress,int size) /*根据参数startAddress、size创建空闲节点，由empty指针返回*/ {
if((*empty = malloc(sizeof(struct freeList))) == NULL)
{
printf("\nNot enough to allocate for the free node .");
errorMessage();
}
(*empty)->startAddress = startAddress;
(*empty)->size = size;
(*empty)->next = NULL;
}
void iniMemory(void) /*初始化存储空间起始地址、大小*/
{
char MSA[10],MS[10];
printf("\nPlease input the start address of the memory !");
scanf("%s",MSA);
memoryStartAddress = atoi(MSA);
printf("\nPlease input the size of the memory !");
scanf("%s",MS);
memorySize = atoi(MS);
}
char selectFitMethod(void) /*选择适应算法*/
{
FILE *fp;
char fitMethod;
do{
printf("\n\nPlease input a char as fallow to select the fit method !\
\n 1 (Best fit) \
\n 2 (Worst fit) \
\n 3 (First fit) \
\n 4 (Last fit)\n");
fitMethod = getche();
}while(fitMethod < '1' || fitMethod > '4');
openFile(&fp,"d:\\result.cl","a");
switch(fitMethod)
{
case '1':
fprintf(fp,"\n\n\n\n\tBest fit");
fprintf(fp,"\n**********************************************");
break;
case '2':
fprintf(fp,"\n\n\n\n\tWorst fit");
fprintf(fp,"\n**********************************************");
break;
case '3':
fprintf(fp,"\n\n\n\n\tFirst fit");
fprintf(fp,"\n**********************************************");
break;
case '4': fprintf(fp,"\n\n\n\n\tLast fit");
fprintf(fp,"\n**********************************************");
break;
}
fclose(fp);
return fitMethod;
}
void inputJob(void) /*从键盘输入作业到D盘的JOB文件*/
{
int /*id,size, */status = 0,jobnum = 0;
FILE *fp;
char id[10],size[10];
openFile(&fp,"d:\\job.cl","w");
fprintf(fp,"job_ID\tsize\tstatus");
printf("\n\n\n\nPlease input the jobs as fallow !\
\nEnter a integer smaller than 1 to quit .\njob_ID\tsize\n");
do{
/* scanf("%d%d",&id,&size); */
scanf("%s\t%s",id,size);
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("\nFinished to input the jobs !");
else
{
printf("\nNo job was given .");
errorMessage();
}
fclose(fp);
}
int makeJobList(struct jobList **jobs)
/*从JOB文件中读出作业并创建作业链表*/ {
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("\nNot enough to allocate for the job .");
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("\nNot enough to allocate for the job .");
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\nNow show the free list...");
printf("\n\nNow show the free list...");
if(p)
{
fprintf(fp,"\nnumber\tsize\tstartAddress");
printf("\nnumber\tsize\tstartAddress");
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,"\nThe memory was used out !");
printf("\nThe memory was used out !");
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("\nCan't find the job which id is : %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("\nCan't find the job which id is : %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\nNow show the used list...");
printf("\n\nNow show the used list...");
if(p)
{
fprintf(fp,"\nnumber\tjobID\tsize\tstartAddress");
printf("\nnumber\tjobID\tsize\tstartAddress");
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,"\nNo job in the memory ! You should input some jobs to it.");
printf("\nNo job in the memory ! You should input some jobs to it.");
fclose(fp);
return 0;
}
}
int showJobList(struct jobList *jobs) /*显示作业链表*/
{
struct jobList *p;
p = jobs->next;
if(p == NULL)
{
printf("\nNo job in the list ! Try again next time.");
return 0;
}
printf("\n\nThe job list is as fallow :\njob_ID\tsize\tstatus");
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("\nThe memory was used out at all.\nMay be you should finish some jobs first or press any key to try again !");
getch();
return;
}
for(p = (*used) -> next;p;p = p-> next)
/* 循环的修改占用分区的始址 */ {
p -> startAddress = address;
getJobInfo(jobs,p -> jobID,&size,&status);
/* 由作业ID获得作业大小 */ 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)
{ /* 按bySize和inc两个参数寻找合适的节点，用temp指向它 */ 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)
/*为作业分配存储空间、状态必须为0*/
{
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("\nMay be you should move the fragment together ."); /* Unsuccessful ! */
return startAddress;
}
void insertUsedNode(struct usedList **used,int id,int startAddress) /*插入释放的空间到used链表中（作业号为id，startAddress由函数13返回）*/
{
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)
/*结束一个作业号为id的作业，释放存储空间（由*startAddress返回空间的起始地址）*/
{
struct usedList *p,*prep;
prep = *used;
p = prep -> next;
while(p && p -> jobID != id)
{
prep = p;
p = p -> next;
}
if(p == NULL)
{
printf("\nThe job which id is : %d is not in the memory !",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指针返回创建的空闲节点*/ 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("\nNot enough to allocate for the used node.");
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("\n1-----------Initializiation.\
\n2-----------Put job into memory(allocate memory).\
\n3-----------Finish job(reuse memory).\
\n4-----------Show current free list.\
\n5-----------Show current memory used by jobs.\
\n6-----------Move fragment together.\
\n7-----------Exit.");
printf("\nPlease select a digit to continue.\n");
step = getche();
printf("\n");
switch(step)
{
case '1':
openFile(&fp,"d:\\result.cl","a");
fprintf(fp,"\n\n\tInitializiation :)");
used -> next = NULL;
empty->next = NULL;
iniMemory();
makeFreeNode(&(empty->next),memoryStartAddress,memorySize);
fprintf(fp,"\n\n\nDo you want to use your job file directly ?\
\nDefault is \'N\' . Y/N : ");
printf("\n\n\nDo you want to use your job file directly ?\
\nDefault is \'N\' . Y/N : \n");
ch = getche();
fprintf(fp,"\n%c",ch);
实验三动态分区存储管理方式的主
实验三动态分区存储管理方式的主存分配回收 一、实验目的 深入了解动态分区存储管理方式主存分配回收的实现。 二、实验预备知识 存储管理中动态分区的管理方式。 三、实验内容 编写程序完成动态分区存储管理方式的主存分配回收的实现。实验具体包括： 首先确定主存空间分配表；然后采用最优适应算法完成主存空间的分配和回收；最后编写主函数对所做工作进行测试。 四、提示与讲解 动态分区管理方式预先不将主存划分成几个区域，而把主存除操作系统占用区域外的空间看作一个大的空闲区。当作业要求装入主存时，根据作业需要主存空间的大小查询主存内各个空闲区，当从主存空间中找到一个大于或等于该作业大小的主存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装入该作业。作业执行完后，它所占的主存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 实现动态分区的分配和回收，主要考虑的问题有三个： 第一，设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计主存分配算法；第三，在设计的数据表格基础上设计主存回收算法。 首先，考虑第一个问题： 设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域。 由于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主
存中的起始地址和长度。由于分配时空闲区有时会变成两个分区： 空闲区和已分分区，回收主存分区时，可能会合并空闲分区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。 由此可见，主存的分配和回收主要是对空闲区的操作。这样为了便于对主存空间的分配和回收，就建立两张分区表记录主存使用情况，一张表格记录作业占用分区的 “已分配区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种，一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分配区表”还是“空闲区 表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因而在多数情况下，无论是“已分配区表”还是“空闲区表”都有空闲栏目。已分配区表中除了分区起始地址、长度外，也至少还要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；空闲区表中除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个空闲区的登记项，内容为“未分配”。在实际系统中，这两表格的内容可能还要多，实验中仅仅使用上述必须的数据。为此, “已分配区表”和“空闲区表”在实验中有如下的结构定义。 已分配区表的定义： #define n 10// 假定系统允许的最大作业数量为n struct {float address;// 已分分区起始地址 float length; // 已分分区长度，单位为字节 int flag;// 已分配区表登记栏标志, “0表”示空栏目，实验中只支持一个字符的作业名}used_table[n];// 已分配区表 空闲区表的定义：
计算机操作系统内存管理系统可变分区存储管理方式的内存分配回收
精心整理课程设计2 可变分区存储管理方式的内存分配回收 一、课程设计目的 深入了解采用可变分区存储管理方式的内存分配回收的实现。 二、预备知识 存储管理中可变分区的管理方式。 给作业。但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值minsize，如果空闲区的大小减去作业需求长度得到的值小于等于minsize，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。 内存分配与回收所使用的结构体：
为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。 关于分配留下的内存小碎片问题： 当要装入一个作业时，从“空闲分区表”中查找标志为“1”（未分配）且满足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值小于或等于minsize，把该分区全部分 “0” 下邻（1 的作业名 }used_table[n]; //已分配区表 （2）空闲分区表的定义： struct {float address; //空闲区起始地址
float length; //空闲区长度，单位为字节 int flag; //空闲区表登记栏标志，用"0"表示空栏目，用"1"表示未分配}free_table[m]; //空闲区表 (3)全局变量 float minsize=5; // { // { } { if((free_table[k].length-need_length)<=minsize) //整个分配 { free_table[k].flag=0; ads=free_table[k].address; len=free_table[k].length; } else { //切割空闲区 ads=free_table[k].address; len=need_length; free_table[k].address+=need_length;
分区分配算法的实现
分区分配算法的实现 实验要求： ?分区空闲表要表示出分区号、始址、大小 ?作业序列能够动态输入 ?内存不足，必须有提示功能 ?总结收获体会及对该题解的改进意见和见解 （红色字体为再修改处）
源代码： /********************操作系统实验四:首次适应(first fit)算法的分区分配算法*******************/ #include } } } printf("\n---------首次适应算法按地址从小到大排列后空闲区---------\n"); printf("\t分区号\t\t大小\t\t起始地址\n"); for(i=0;i 实验五动态分区存储管理 一、实验目的 深入了解采用动态分区存储管理方式的内存分配回收的实现。通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉动态分区存储管理的内存分配和回收。 二、实验内容 编写程序完成动态分区存储管理方式的内存分配回收。 具体包括：确定内存空间分配表； 采用最优适应算法完成内存空间的分配和回收； 编写主函数对所做工作进行测试。 三、设计思路 整体思路： 动态分区管理方式将内存除操作系统占用区域外的空间看成一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 设计所采用的算法： 采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值minsize，如果空闲区的大小减去作业需求长度得到的值小于等于minsize，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。 内存分配与回收所使用的结构体： 为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分 区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。 一．实验目的 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的内存分配和回收。 二．实验内容 1．确定内存空间分配表； 2．采用最优适应算法完成内存空间的分配和回收； 3．编写主函数对所做工作进行测试。 三．实验背景材料 由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。 “已分分区表”的结构定义 #define n 10 //假定系统允许的最大作业数量为n struct { float address; //已分分区起始地址 float length; //已分分区长度、单位为字节 int flag; //已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名 }used_table[n]; //已分分区表 “空闲区表”的结构定义 #define m 10 //假定系统允许的空闲区最大为m struct { float address; //空闲区起始地址 float length; //空闲区长度、单位为字节 int flag; //空闲区表登记栏标志，“0”表示空栏目，“1”表示未分配 }used_table[n]; //空闲区表 第二，在设计的数据表格基础上设计内存分配。 装入一个作业时，从空闲区表中查找满足作业长度的未分配区，如大于作业，空闲区划分成两个分区，一个给作业，一个成为小空闲分区。 实验中内存分配的算法采用“最优适应”算法，即选择一个能满足要求的最小空闲分区。 第三，在设计的数据表格基础上设计内存回收问题。内存回收时若相邻有空闲分区则合并空闲区，修改空闲区表。 四、参考程序 #define n 10 //假定系统允许的最大作业数量为n 操作系统实验四 【实验题目】：动态分区分配算法 【实验学时】：4学时 【实验目的】 通过这次实验，加深对动态分区分配算法的理解，进一步掌握首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的实现方法。 【实验内容及要求】 问题描述： 设计程序模拟四种动态分区分配算法：首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法的工作过程。假设内存中空闲分区个数为n，空闲分区大小分别为P1, … ,P n，在动态分区分配过程中需要分配的进程个数为m（m≤n），它们需要的分区大小分别为S1, … ,S m，分别利用四种动态分区分配算法将m个进程放入n个空闲分区，给出进程在空闲分区中的分配情况。 程序要求： 1）利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。 2）模拟四种算法的分区分配过程，给出每种算法进程在空闲分区中的分配情况。 3）输入：空闲分区个数n，空闲分区大小P1, … ,P n，进程个数m，进程需要的分区大小S1, … ,S m。 4）输出：首次适应算法，循环首次适应算法，最佳适应算法，最坏适应算法，最终内存空闲分区的分配情况。 实现源代码： #include 可变分区存储管理 设计思路： 整体思路： 可变分区管理方式将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存中的各个 空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。 设计所才用的算法： 采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值min size，如果空闲区的大小减去作业需求长度得到的值小于等于min size，不再将空闲区分成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。 内存分配与回收所使用的结构体： 为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名/标志（为0时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（0表空栏目，1表未分配）。两张表都采用顺序表形式。 关于分配留下的内存小碎片问题： 当要装入一个作业时，从“空闲分区表”中查找标志为“ 1”（未分配）且满足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值小于或等于min size，把该分区全部分配给作业，并把该空闲区的标志改为“0”（空栏目）。同时，在已分配区表中找到一个标志为“ 0”的栏目登记新装人作业所占用分区的起始地址，长度和作业名。若空闲区的大小与作业所需大小的差值大于 使用动态分区分配方式的模拟 1内容 （1）用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。 （2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：?作业1申请130KB。 ?作业2申请60KB。 ?作业3申请100KB。 ?作业2释放60KB。 ?作业4申请200KB。 ?作业3释放100KB。 ?作业1释放130KB。 ?作业5申请140KB。 ?作业6申请60KB。 ?作业7申请50KB。 ?作业6释放60KB。 请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。 2、示例程序： //Tittle: 使用动态分区算法的模拟 //author: XuYongzhen #include 动态分区分配算法 一实验内容与要求 内容：动态分区分配是根据进程的实际需要，动态地为之分配内存空间，而在分配时，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。在本实验中运用了三种分配算法，分别是1.首次适应算法，2.循环首次适应算法，3.最佳适应算法。 要求：动态分区算法也称为可变分区分配算法，常见的空闲区查找算法有首次适应算法，循环首次适应算法，最佳适应算法。特别注意分区回收时，相邻空闲分区需要合并。 (1)参考操作系统教材理解这3种分配算法以及回收算法。 (2)实现3种分配算法以及回收算法。 (3)已知作业申请内存和释放内存的序列，给出内存的使用情况。 (4)作业申请内存和释放内存的序列可以存放在文本文件中。 (5)设计简单的交互界面，演示所设计的功能。(可以使用MFC进行界面的设计) (6)可根据自己能力，在完成以上基本要求后，对程序功能进行适当扩充。 二、需求分析 本次实验通过用C语言进行编程并调试、运行，形象地表现出动态分区的分配方式，直观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之间的区别。加深了我们对两种算法优缺点的理解，帮助我们了解一些数据结构和分配算法，进一步加深我们对动态分区存储器管理方式及其实现过程的理解。主要的问题在于，如何解决两种算法对内存的释放和回收空间的表示。 动态分区分配：又称为可变分区分配，这种分配方式并不事先先将主存划分成一块块的分区，而是在作业进入主存时，根据作业的大小动态地建立分区。并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数 目也是可变的。 分区分配算法： 1.首次适应法： 为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。 特点：优先利用内存中底地址部分的空闲分区 (将所有空闲区,按其地址递增的顺序链接) 2.循环首次适应算法 该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业，为实现本算法，设置一个全局变量f，来控制循环查找，当f%N==0时，f=0；若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。 3.最佳适应算法： 接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配;为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。 三、概要设计 动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示： typedef struct freearea//定义一个空闲区说明表结构 { int ID; //分区号 long size; //分区大小 long address; //分区地址 int state; //状态 }ElemType; typedef struct DuLNode //double linked list { ElemType data; struct DuLNode *prior; //前趋指针 struct DuLNode *next; //后继指针 }DuLNode,*DuLinkList; 理工大学信息工程与自动化学院学生实验报告 （ 2013 —2014 学年第一学期） 课程名称：操作系统开课实验室：信自楼444 2013年 11月28 日 注：报告容按下列的要求进行。 一、实验目的 通过编写固定分区存储管理的模拟程序，加深对操作系统存储管理功能中的固定分区管理方式、主存分配表等相应知识的理解。 通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的存分配和回收。 二、实验题目 1.设计一个固定分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 2.必须建立分区表，记录空闲区与占用区的状况。 本系统将存用户空间划分为五个大小不固定的分区，其分区大小由用户输入决定。在每个分区只装入一道作业，这样把用户空间划分为几个分区，便允许几道作业并发运行。当有一个空闲分区时，便可以从外存的后备队列中选择一个适当大小的作业装入该分区，当该作业结束时又可以从后备作业队列中找出另一作业调入该分区。 每个存空间是一个Node型的对象。Node类有一个三个参数的构造函数。分别为：分区号、起始地址、大小。然后就是一些属性的get、set方法和一个打印其属性的函数。四个数据域分别为：属性m_No用来表示该存空间的序号。属性m_Addr用来表示存分区的起始地址。属性m_Size用来表示存空间的大小。属性m_State表示存空间的是否已分配的状态标志。若该存空间已分配，m_TaskNo表示占有该存空间的任务序号。否则没有实际意义。 在用户申请任务的存空间时，提示用户输入任务号和其需要的存空间大小。 流程图 主程序： 释放存空间算法 操作系统实验（三）可变分区存储管理模拟实验 作者：顾熙杰 准考证号：4 报到号：177 实验地点：浙工大计算机中心 1)实验目的 理解操作系统中可变分区管理的算法， 掌握分配和回收算法 掌握空闲分区的合并方法 掌握不同的适应算法 2)实验内容 建立数据结构 建立空闲分区队列 根据不同的适应算法建立队列 编写分配算法 编写回收算法 3)数据结构 Private Type MEM_tp fenqu_shouzhi As Integer '分区首地址 fenqu_changdu As Integer '分区长度 fenqu_zhuangtai As Integer '分区状态-1表示不存在，0表示空闲分区，1表示已经分配的分区 fenqu_huodongjincheng As Integer '该分区正在活动的进程代号 End Type 4)程序流程图 面向对象程序设计由事件驱动，画流程图比较困难。 （1）分配新的分区 最先适应按地址找 最优适应，找最小可以满足的 最坏适应，找最大可以满足的 （2）分区回收 既无上邻又无下邻 既有上邻又有下邻 只有上邻 只有下邻 5)实验中需要改进的地方 由于没有使用链表，程序结构比较混乱，需要大大改进，提高可阅读性。 6)程序代码(VB) Option Explicit Private Declare Function ShellExecute Lib "Shell32.dll" Alias "ShellExecuteA" (ByVal hwnd As Long, ByVal lpOperation As String, ByVal lp String, ByVal lpParameters As String, ByVal lpDirectory As String, ByVal nShowCmd As Long) As Long '表示内存分区的结构信息类型的变量类型 Private Type MEM_tp fenqu_shouzhi As Integer '分区首地址 fenqu_changdu As Integer '分区长度 fenqu_zhuangtai As Integer '分区状态-1表示不存在，0表示空闲分区，1表示已经分配的分区 fenqu_huodongjincheng As Integer '该分区正在活动的进程代号 End Type '定义最多640个，总共640K内存数组 Dim MEM(1 To 640) As MEM_tp '表示可以使用的进程代号 Dim jincheng(1 To 640) As Integer '0表示该进程号可以使用 '.>=1表示该进程号不可以使用 '表示分配方法 Dim fenPEI_fangfa As Integer '0=最先分配 '1=最优分配 '2=最坏分配 Function get_jincheng() As Integer '取可以使用的进程号 Dim i As Integer For i = 1 To 640 If jincheng(i) = 0 Then jincheng(i) = 1 get_jincheng = i Exit Function End If Next get_jincheng = 0 End Function Function get_FENQU() As Integer '取可以使用的为了表示分区的存储空间，模拟c语言的指针 Dim i As Integer For i = 1 To 640 南昌大学实验报告 学生姓名：马江涛学号： 8000612091 专业班级：计算机软件121班 实验类型：□验证□综合□设计□创新实验日期： 2014-05-08 实验成绩： 【实验要求】 1、编程实现首次适应算法和最佳适应算法的动态分区分配的分配过程和回收过程。其中，空闲分区通过分区链来管理；在进行内存分配时，系统优先使用空闲区低端的空间。 2、假设初始状态下，可用内存空间为640K，并依次有下列请求序列： 1)作业1申请130KB。 2)作业2申请60KB。 3)作业3申请100KB。 4)作业2释放60KB。 5)作业4申请200KB。 6)作业3释放100KB。 7)作业1释放130KB。 8)作业5申请140KB。 9)作业6申请60KB。 10)作业7申请50KB。 11)作业6释放60KB。 请分别用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况【可参考后文的实验提示】。 3、上机时认真的进行测试，输入不同的资源分配请求，写出实验结果； 4、具体要求： （1）对你的程序关键代码处进行注释。 （2）给出实验数据，对结果进行分析，说明对相关知识点的理解。 【实验目的】 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。 【实验思路】 首次适应算法（First-fit）：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，则从空闲表中取消该项；如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。 最佳适应算法（Best-fit）：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则 操作系统原理 课程设计报告 题目：动态分区分配存储管理系统 所在学院：计算机科学与技术学院 班级： 11级计算机科学与技术(非师) 学号： 20111202052 姓名：吴创连 指导教师：黄侠剑 2014年3月18 目录 1 引言 (1) 2 需求分析 (1) 3 概要设计 (1) 4 详细设计 (1) 4.1问题描述和分析 (1) 4.2程序流程图 (2) 4.3数据结构体分析 (3) 4.4主要程序代码分析 (4) 5 调试与操作说明 (11) 5.1初始界面 (11) 5.2模拟内存分配 (12) 5.3回收内存界面 (12) 5.4最佳适应算法的实现 (13) 5.5最坏适应算法的实现 (13) 6总结与体会 (13) 1 引言 操作系统是最重要的系统软件，同时也是最活跃的学科之一。我们通过操作系统可以理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。 存储器是计算机系统的重要组成部分，近年来，存储器容量虽然一直在不断扩大，但仍不能满足现代软件发展的需要，因此，存储器仍然是一种宝贵而又紧俏的资源。如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大影响。而动态分区分配属于连续分配的一种方式，它至今仍在内存分配方式中占有一席之地。 2 需求分析 动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。常用的数据结构有动态分区表和动态分区链。在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法（最佳适应算法，最坏适应算法），在动态分区存储管理方式中主要实现内存分配和内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接等相关的内容。 3 概要设计 本程序采用机构化模块化的设计方法，共分为两大模块。 1．最佳适应算法实现 它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。 2.最坏算法实现 最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。 4 详细设计 4.1 问题描述和分析 系统应利用某种分配算法，从空闲分区链表中找到所需大小的分区，如果空闲分区大小 实验三使用动态分区分配方式的模拟 1、实验目的 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。 2、实验内容 (1) 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。 (2) 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列： ?作业1申请130KB。 ?作业2申请60KB。 ?作业3申请100KB。 ?作业2释放60KB。 ?作业4申请200KB。 ?作业3释放100KB。 ?作业1释放130KB。 ?作业5申请140KB。 ?作业6申请60KB。 ?作业7申请50KB。 ?作业6释放60KB。 请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。 程序代码——C语言实现 #include void Init() //空闲分区链的初始化 { node *p; p=(node *)malloc(sizeof(node)); p->before=&L; p->after=NULL; p->size=640; p->address=0; p->state=0; L.after=p; L.before=NULL; L.size=0; U.next=NULL; n=&U; } node *search(int a) { node *p=L.after; if(p==NULL) { printf("没有空闲的区域!"); p=NULL; return p; } else { while(p!=NULL && a>p->size) p=p->after; if(p==NULL) { printf("没有找到合适的空闲空间!"); p=NULL; return p; } else return p; } } void recovery(int a,int b) //内存回收算法 { #include 课程设计报告 课程设计题目：循环首次适应的动态分区分配算法模拟 专业：计算机科学与技术 班级：10204102 姓名：谱 学号: 10204102 指导教师:高小辉 2013年1月11 日 目录 一．循环首次适应算法 (3) 1. 概述 (3) 2．需求分析 (3) 二．实验指导 (4) 1.基本思想 (4) 2．数据结构 (4) 三．运行环境 (6) 四．流程图 (6) 五．循环首次适应算法代码 (5) 六．调试结果 (11) 七、总结 (14) 八．参考文献 (14) 一．循环首次适应算法 1.概述： 该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块的请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查找指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式，即如果最后一个（链尾）空闲分区的大小仍不能满足要求，则返回到第一个空闲分区，比较大小是否满足，找到后，应调整起始查询指针。 2. 需求分析 了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。采用首次适应算法的动态分区分配过程alloc()和回收过程free()。 空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间，即每次分配内存空间是总是从低址部分开始进行循环，找到第一个合适的空间，便按作业所需分配的大小分配给作业。 作业完成时，需要释放作业所占空间，此时要考虑到四种情况： (1)回收区与插入点的前一个空闲分区相邻接。此时将二者合并，修改前一 分区的大小。 (2)回收区与插入点的后一空闲分区相邻接，将二者合并，用回收区的首址 作为新空闲区的首址。 (3)回收区同时与插入点的前后两个空闲分区相邻接，三者合并，使用前一空 闲分区的表项和首址。 (4)回收区单独存在。 二、实验指导 1．基本思想 动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。 2．数据结构 动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。 c++动态分区分配算法模拟(操作系统课程 设计) 课程设计 课程设计名称：操作系统课程设计 专业班级： 学生姓名： 学号： 指导教师： 课程设计时间：6月13日-——6月17日 计算机科学专业课程设计任务书 说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页 1：需求分析 （1）用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。 （2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200 KB；作业3释放100 KB；作业1释放 130 KB；作业5申请140 KB；作业6申请60 KB；作业7申请 50KB；作业6释放60 KB。采用首次适应算法进行内存块的分配和回 收，同时显示内存块分配和回收后空闲内存分区链的情况。 2：概要设计 （1）数据结构：作业队列数据结构，用于存储待处理作业；阻塞作业队列数据结构，用于存储阻塞的作业。已分配内存块的双向链表，记录当前系 统已分配的各个内存块；未分配内存块的双向链表，记录系统中剩余的 各个内存块；系统内存分配总情况的结点对象，记录系统中阻塞的作业 总数，已分配的内存块数，剩余的内存块数。 （2）主函数：对作业队列、阻塞队列、已分配内存块链表、未分配内存块链表、系统总内存分配情况结点对象进行初始化，调用分配函数或回收函 数，循环处理11个作业步。 （3）分配函数alloc()：首次适应算法检索未分配的内存块链表，若找到合适的内存块，则加以判断，空闲内存块大小减去作业去请求内存块大小小于 青岛农业大学 理学与信息科学学院 操作系统课程设计报告 设计题目仿真实现动态可变分区存储管理模拟系统 —最佳适应算法和最先适应算法 学生专业班级计算机科学与技术2011级03班 学生姓名（学号）张明珠（H20110684 ） 设计小组其他同学姓名（学号）刘玉婷（H20110661） 宋璇（H20110162） 指导教师牟春莲 完成时间 2014. 06.15 实习（设计）地点信息楼218 2014年6月16日 一、课程设计目的 操作系统的理论知识只有通过操作系统的实际操作和编程才能真正地理解 和掌握，没有实践操作系统的操作和编程，学习操作系统就是纸上谈兵。操作系统课程设计是在学习完《操作系统》课程后进行的一次全面、综合实习，是计算机科学与技术专业的重要实践性教学环节。通过课程设计，达到如下目的： 1、巩固和加深对操作系统原理的理解，提高综合运用本课程所学知识的能力。 2、培养学生选用参考书，查阅手册及文献资料的能力；培养独立思考、深 入研究、分析问题、解决问题的能力。 3、通过实际操作系统的分析设计、编程调试，掌握系统软件的分析方法和 工程设计方法。 4、能够按要求编写课程设计报告书，能正确阐述设计过程和实验结果、正 确绘制系统和程序框图。 5、通过课程设计，培养学生严谨的科学态度、严肃认真的工作作风和团队 协作精神。 二、设计任务 题目描述： 仿真实现动态可变分区存储管理模拟系统。内存调度策略可采用最先适应算法、最佳适应法等，并对各种算法进行性能比较。为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。常用的数据结构有两种形式：空闲分区表和空闲分区链。为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业.设计要求： 1．采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形： ⑴随机出现的进程i申请jKB内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址Faddress，并要求输出内存使用情况和空闲情况。 内存情况输出的格式为：Faddress该分区的首地址；Eaddress该分区的尾地址Len 分区长度；Process 如果使用，使用的进程号，否则为0。 ⑵主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能。成员分工： 张明珠申请内存、查看进程之间的前后的区域状态、释放进程实验五 动态分区存储管理
可变分区存储管理方式的内存分配和回收实验报告(最优算法)
操作系统实验四实验报告动态分区分配算法
动态分区式存储管理
动态分区分配方式模拟
动态分区分配算法资料
固定分区存储管理
操作系统可变分区存储管理模拟
实验报告-动态分区分配算法
动态分区存储管理系统分解
动态分区分配方式的模拟C语言代码和C代码
可变分区存储管理方案模拟
循环首次适应的动态分区分配算法模拟
最新c++动态分区分配算法模拟(操作系统课程设计)
动态可变分区存储管理模拟系统解析
- 动态分区分配方式的模拟实验报告模板
- 动态分区分配方式的模拟实验报告模板
- 动态分区分配方式的模拟实验报告模板
- 存储管理——动态分区分配回收算法的模拟
- 存储管理动态分区分配算法的模拟
- 采用首次适应算法实现动态分区分配过程的模拟
- 循环首次适应的动态分区分配算法模拟
- A.5动态分区分配方式的模拟实验报告
- 实验四 动态分区分配方式内存管理模拟
- c++动态分区分配算法模拟(操作系统课程设计
- 动态分区分配方式模拟
- 实验四--动态分区分配方式的模拟-答案
- 使用动态分区分配方式的模拟
- 动态分区分配方式的模拟实验报告材料实用模板
- 存储管理---动态分区分配算法的模拟
- 最新c++动态分区分配算法模拟(操作系统课程设计)
- 动态分区分配方式的模拟
- 动态分区分配与回收算法的模拟
- 操作系统实验—动态分区分配算法
- 动态分区分配方式的模拟