存储管理---动态分区分配算法的模拟(共27页).doc

《存储管理---动态分区分配算法的模拟(共27页).doc》由会员分享，可在线阅读，更多相关《存储管理---动态分区分配算法的模拟(共27页).doc（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上一、设计任务 完成存储器动态分区分配算法的模拟实现。二、设计思想 在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法（首次适应算法，最佳适应算法，最后适应算法，最坏适应算法），实现分区存储管理的内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接，等等相关的内容。三、预期目的让我们了解操作系统的基本概念，理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。通过课程设计，我们可以进一步理解在计算机系统上运行的其它各类

2、操作系统，并懂得在操作系统的支持下建立自己的应用系统。操作系统课程设计，对于训练学生掌握程序设计、熟悉上机操作和程序调试技术都有重要作用。重点培养学生的思维能力、设计能力、创新能力和排错能力。四、设计方案 首先是对相关知识的掌握，例如数据结构，计算方法，组成原理以及操作系统等。在这些基本知识的基础上进行扩展，用语言的形式从函数，数据结构原代码，原程序等方面来达到自己想要的目的。该设计就是要达到对各个细节的问题的解决将各个数据块连接起来，最终达到存储器动态分区分配算法的模拟实现。五、数据结构1 设计合理的数据结构来描述存储空间：1） 对于未分配出去的部分，用空闲分区链表来描述。struct fr

3、eeList int startAddress; /* 分区起始地址 */int size; /* 分区大小 */struct freeList *next; /* 分区链表指针 */ 2） 对于已经分配出去的部分，由装入内存的作业占据。struct usedList int startAddress; /* 分区起始地址 */int jobID; /* 分区中存放作业ID */struct usedList *next; /* 分区链表指针 */3） 将作业组织成链表。struct jobListint id; /* 作业ID */int size; /* 作业大小（需要的存储空间大小） *

4、/int status; /* 作业状态 0 : new job ,1 : in the memory , 2 : finished . */struct jobList *next; /* 作业链表指针 */以上将存储空间分为空闲可占用两部分，在usedlist中设jobID而不设size，可以在不增加空间复杂度（与freelist相比）的同时更方便的实现可变分区存储管理（从后面的一些函数的实现上可以得出这个结论）。尽管设置joblist增加了空间复杂度，但它的存在，使得该程序可以方便的直接利用D盘中的JOB文件。该文件可以认为是一个和其他进程共享的资源。通过这个文件，其他进程写入数据供读取

5、。这中思想在操作系统设计中体现的很多。2 实现分区存储管理的内存分配功能，选择适应算法（首次适应算法，最佳适应算法，最后适应算法，最坏适应算法）。基本原理分析： 1） Best fit ：将空闲分区按大小从小到大排序，从头找到大小合适的分区。2） Worst fit：将空闲分区按大小从大到小排序，从头找到大小合适的分区。3） First fit ：将空闲分区按起始地址大小从小到大排序，4） Last fit ：将空闲分区按起始地址大小从大到小排序，由此，可将空闲分区先做合适的排序后用对应的适应算法给作业分配存储空间。排序函数 order（bySize为零则按分区大小排序，否则按分区起始地址；i

6、nc为零从小到大排序，否则从大到小排序；通过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 si

7、ze)temp = q;break;default:if(q-size temp-size)temp = q;break; break;default: switch(inc)case 0:if(q-startAddress 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 = te

8、mp-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 |

9、 p - startAddress + p - size 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 = startAddr

10、ess; /* 合并首节点 */q - size += size;else if(startAddress + size startAddress) /* 与首节点不相邻 */makeFreeNode(&r,startAddress,size);r - next = (*empty) - next;(*empty) - next = r;else /* 处理链表中间的邻接情况 */while(q - next & q - startAddress next;if(p - startAddress + p - size = startAddress & q - startAddress = st

11、artAddress + 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 =

12、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

13、,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)/* 循环的修改

14、占用分区的始址 */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

15、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.更新作业链表中作业的

16、状态： 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链表中（作业号为

17、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 makeFreeNod

18、e(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文件时提供作业信息）、makeJobLi

19、st()、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 me

20、mory)按顺序利用了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()、moveFra

21、gment()函数。7、Exit按顺序利用了openFile()、exit(0)函数。七、程序清单 1、原程序#include#include#includeint memoryStartAddress = -1;int memorySize = -1;struct jobListint id; /* 作业ID */int size; /* 作业大小（需要的存储空间大小） */int status; /* 作业状态 0 : new job ,1 : in the memory , 2 : finished . */struct jobList *next; /* 作业链表指针 */;struc

22、t freeListint startAddress; /* 分区起始地址 */int size; /* 分区大小 */struct freeList *next; /* 分区链表指针 */;struct usedList int startAddress; /* 分区起始地址 */int jobID; /* 分区中存放作业ID */struct usedList *next; /* 分区链表指针 */;void errorMessage(void) /*出现严重错误时显示信息并结束程序*/printf(ntError !a);printf(nPress any key to exit !);

23、getch();exit(1);void openFile(FILE *fp,char *filename,char *mode) /*以要求的方式打开文件*/if(*fp = fopen(filename,mode) = NULL)printf(nCant open %s in mode %s.,filename,mode);errorMessage();void makeFreeNode(struct freeList *empty,int startAddress,int size) /*根据参数startAddress、size创建空闲节点，由empty指针返回*/if(*empty

24、= 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 MSA10,MS10;printf(nPlease input the start address of the memory !);sca

25、nf(%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;doprintf(nnPlease input a char as fallow to select the fit method !n 1 (Best fit) n 2 (Worst fit) n 3 (First fit) n

26、 4 (Last fit)n);fitMethod = getche();while(fitMethod 4); openFile(&fp,d:result.cl,a);switch(fitMethod)case 1: fprintf(fp,nnnntBest fit); fprintf(fp,n*); break;case 2: fprintf(fp,nnnntWorst fit); fprintf(fp,n*); break;case 3: fprintf(fp,nnnntFirst fit); fprintf(fp,n*); break;case 4: fprintf(fp,nnnntL

27、ast fit); fprintf(fp,n*); break;fclose(fp);return fitMethod;void inputJob(void) /*从键盘输入作业到D盘的JOB文件*/int /*id,size, */status = 0,jobnum = 0;FILE *fp;char id10,size10;openFile(&fp,d:job.cl,w);fprintf(fp,job_IDtsizetstatus);printf(nnnnPlease input the jobs as fallow !nEnter a integer smaller than 1 to

28、quit .njob_IDtsizen);do/*scanf(%d%d,&id,&size); */scanf(%st%s,id,size);if(atoi(id) 0 & atoi(size) 0)fprintf(fp,n%st%st%d,id,size,status);/*fprintf(fp,n%dt%dt%d,id,size,status); */jobnum+;elsebreak;while(1);if(jobnum)printf(nFinished to input the jobs !);elseprintf(nNo job was given .);errorMessage()

29、;fclose(fp);int makeJobList(struct jobList *jobs) /*从JOB文件中读出作业并创建作业链表*/char jobID10,size10,status10;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);err

30、orMessage();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 =

31、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_IDtsizetstatus);for(p = jobs - next;p;p = p - next)fprintf(fp,n%dt%dt%d,p-id,p-size,p-statu

32、s);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,nnNow show the free list.);printf(nnNow show the free list.);if(p)fprintf(fp,nnumbertsizetstartAddress);printf(nnumbertsizetstar

33、tAddress);for(;p;p = p - next)fprintf(fp,n%dt%dt%d,+count,p - size,p - startAddress);printf(n%dt%dt%d,count,p - size,p - startAddress);fclose(fp);return 1;elsefprintf(fp,nThe memory was used out !);printf(nThe memory was used out !); fclose(fp);return 0;void getJobInfo(struct jobList *jobs,int id,in

34、t *size,int *status) /*获取作业的信息*/struct jobList *p = jobs-next;while(p & p-id != id)p = p-next;if(p = NULL)printf(nCant 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)-

35、next;while(p & p-id != id)p = p-next;if(p = NULL)printf(nCant find the job which id is : %d .,id);errorMessage();elsep - 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.

36、cl,a);fprintf(fp,nnNow show the used list.);printf(nnNow show the used list.);if(p)fprintf(fp,nnumbertjobIDtsizetstartAddress);printf(nnumbertjobIDtsizetstartAddress);for(;p;p = p - next)getJobInfo(jobs,p - jobID,&size,&status);fprintf(fp,n%dt%dt%dt%d,+count,p-jobID,size,p- startAddress);printf(n%dt

37、%dt%dt%d,count,p-jobID,size,p- startAddress);fclose(fp);return 1;elsefprintf(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-

38、next;if(p = NULL)printf(nNo job in the list ! Try again next time.);return 0;printf(nnThe job list is as fallow :njob_IDtsizetstatus);while(p)printf(n%dt%dt%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