2022年存储管理---动态分区分配算法的模拟 .pdf

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

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

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

3、t int startAddress; /* 分区起始地址 */ int size; /* 分区大小 */ struct freeList *next; /* 分区链表指针 */ 2） 对于已经分配出去的部分，由装入内存的作业占据。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 27 页 - - - - - - - - - 课程设计书第 2 页struct usedList int startAddress; /* 分区起始地址 */ int jobID; /* 分区中存

4、放作业 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相

5、比）的同时更方便的实现可变分区存储管理（从后面的一些函数的实现上可以得出这个结论） 。尽管设置 joblist增加了空间复杂度，但它的存在，使得该程序可以方便的直接利用D盘中的 JOB文件。该文件可以认为是一个和其他进程共享的资源。通过这个文件，其他进程写入数据供读取。这中思想在操作系统设计中体现的很多。2 实现分区存储管理的内存分配功能，选择适应算法（首次适应算法，最佳适应算法，最后适应算法，最坏适应算法）。基本原理分析：1） Best fit ：将空闲分区按大小从小到大排序，从头找到大小合适的分区。2） Worst fit：将空闲分区按大小从大到小排序，从头找到大小合适的分区。3） Fir

6、st fit ：将空闲分区按起始地址大小从小到大排序，4） Last fit ：将空闲分区按起始地址大小从大到小排序，由此， 可将空闲分区先做合适的排序后用对应的适应算法给作业分配存储空间。排序函数 order （bySize 为零则按分区大小排序，否则按分区起始地址；inc 为零从小到大排序，否则从大到小排序；通过empty 指针返回结果） 。void order(struct freeList *empty,int bySize,int inc) struct freeList *p,*q,*temp; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

7、- - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 27 页 - - - - - - - - - 课程设计书第 3 页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 size) temp = q;break; default:i

8、f(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 = temp-startAddress; p-

9、size = temp-size; temp-startAddress = startAddress; temp-size = size; 3 实现分区存储管理的内存回收算法。void insertFreeNode(struct freeList *empty,int startAddress,int size) 插入回收的空节点分区，处理回收分区与空闲分区的四种邻接关系。 struct freeList *p,*q,*r; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共

10、 27 页 - - - - - - - - - 课程设计书第 4 页for(p = *empty;p - next;p = p - next) ; /* 处理链表尾部的邻接情况 */ if(p = *empty | p - startAddress + p - size next = p - next; /* 插入独立的空闲节点 */ p - next = r; return ; if(p - startAddress + p - size = startAddress) /* 与尾部上邻 */ p - size += size; /* 合并尾部节点 */ return ; q = (*emp

11、ty) - next; /* 处理链表首节点的邻接情况 */ if(startAddress + size = q - startAddress) /* 与首节点下邻 */ q - startAddress = startAddress; /* 合并首节点 */ q - size += size; else if(startAddress + size startAddress) /* 与首节点不相邻 */ makeFreeNode(&r,startAddress,size); r - next = (*empty) - next; (*empty) - next = r; else /* 处

12、理链表中间的邻接情况 */ while(q - next & q - startAddress next; if(p - startAddress + p - size = startAddress & q - startAddress = startAddress + size) /* 上下邻，合并节点 */ p - size += size + q - size; p - next = q - next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 27 页 -

13、- - - - - - - - 课程设计书第 5 页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 = s

14、tartAddress; /* 修改节点起始地址 */ 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 =

15、 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 = ad

16、dress; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 27 页 - - - - - - - - - 课程设计书第 6 页getJobInfo(jobs,p - jobID,&size,&status); /* 由作业 ID 获得作业大小 */ address += size; (*empty)-next-startAddress = address; /* 修改空闲分区的首节点始址、 大小*/ (*empty) - next - size = memorySize

17、 - (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 从

18、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 si

19、ze) 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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理

20、 - - - - - - - 第 6 页，共 27 页 - - - - - - - - - 课程设计书第 7 页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,i

21、nt 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()

22、 、allocate()、insertUsedNode() （选择利用 D盘 JOB文件时先将状态为 1 的作业放到存储空间中，以恢复上次的模拟实验，或使本次模拟时不出错） selectFitMethod()等自编函数。2、Put job into memory(allocate memory)按顺序利用了 showJobList() （选手动逐个为作业分配存储空间时）、 openFile()、order()、 allocate()、errorMessage() 、insertUsedNode() 、updateJobStatus()updateJobFile()函数3、Finish job(

23、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按顺序利用了 openF

24、ile()、moveFragment()函数。7、Exit 按顺序利用了 openFile()、exit(0)函数。七、程序清单 1 、原程序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 27 页 - - - - - - - - - 课程设计书第 8 页#include #include #include int memoryStartAddress = -1; int memorySize = -1; struct jobList int id; /* 作业 ID *

25、/ 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 j

26、obID; /* 分区中存放作业 ID */ struct usedList *next; /* 分区链表指针 */ ; void errorMessage(void) /*出现严重错误时显示信息并结束程序*/ printf(ntError !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(nCant open

27、%s in mode %s.,filename,mode); errorMessage(); void makeFreeNode(struct freeList *empty,int startAddress,int size) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 27 页 - - - - - - - - - 课程设计书第 9 页 /* 根据参数 startAddress、size 创建空闲节点， 由 empty指针返回 */ if(*empty = mall

28、oc(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 !);

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

30、 (First fit) n 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 27 页 - - - - - - - - - 课程设计书第 10 页ca

31、se 2: fprintf(fp,nnnntWorst fit); fprintf(fp,n*); break; case 3: fprintf(fp,nnnntFirst fit); fprintf(fp,n*); break; case 4: fprintf(fp,nnnntLast fit); fprintf(fp,n*); break; fclose(fp); return fitMethod; void inputJob(void) /*从键盘输入作业到D盘的 JOB文件*/ int /*id,size, */status = 0,jobnum = 0; FILE *fp; char

32、 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 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); /* f

33、printf(fp,n%dt%dt%d,id,size,status); */ jobnum+; else break; while(1); if(jobnum) printf(nFinished to input the jobs !); else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 27 页 - - - - - - - - - 课程设计书第 11页printf(nNo job was given .); errorMessage(); fclose(fp

34、); 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); er

35、rorMessage(); 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

36、; rear - id = atoi(jobID); rear - size = atoi(size); rear - status = atoi(status); fclose(fp); return 0; int updateJobFile(struct jobList *jobs) /*更新作业链表中作业的状态名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 27 页 - - - - - - - - - 课程设计书第 12 页*/ FILE *fp; struct

37、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-status); fclose(fp); return 0; int showFreeList(struct freeList *empty) /*空闲分区队列显示 */ FILE *fp; struct freeList *p = empty - next; int count = 0; openFile(&fp,

38、d:result.cl,a); fprintf(fp,nnNow show the free list.); printf(nnNow show the free list.); if(p) fprintf(fp,nnumbertsizetstartAddress); printf(nnumbertsizetstartAddress); 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); fc

39、lose(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) /*获取作业的信息 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 27 页 - - -

40、 - - - - - - 课程设计书第 13 页 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 = (*job

41、s)-next; while(p & p-id != id) p = p-next; if(p = NULL) printf(nCant 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; openF

42、ile(&fp,d:result.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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 27

43、 页 - - - - - - - - - 课程设计书第 14 页 getJobInfo(jobs,p - jobID,&size,&status); fprintf(fp,n%dt%dt%dt%d,+count,p-jobID,size,p- startAddress); printf(n%dt%dt%dt%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(n

44、No 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(nnThe job list is as fallow :njob_IDtsizetstatus); wh

45、ile(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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 27 页 - - - - - - - - -

46、 课程设计书第 15 页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) /* 循环的修改占用分区的始址

47、*/ 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(s

48、truct 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 size) temp = q;break; default:if(q-si

49、ze temp-size) temp = q;break; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 27 页 - - - - - - - - - 课程设计书第 16 页default: switch(inc) case 0:if(q-startAddress startAddress) temp = q;break; default:if(q-startAddress temp-startAddress) temp = q;break; break

50、; /* 交换节点的成员值 */ 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