C课程设计论文存储管理分区分配算法

1、辽 宁 工 业 大 学 C语言程序设计 课程设计论文题目： 存储管理分区分配算法 院系： 专业班级： 学 号： 学生姓名： 指导教师： 教师职称： 起止时间： 课程设计报告任务及评语院系：软件学院 教研室：软件教研窒学 号学生姓名专业班级程序设计报告题目存储管理分区分配算法程序设计报告任务程序设计的任务与要求：1掌握C语言编程的根底知识。2较熟练地编写C语言应用程序。3了解C语言的常用标准函数、编程技巧、异常处理。5联系已学过的内容，稳固所学的理论，增强独立工作能力。6通过设计主要使学生有一个独立编写程序的过程，对理论学习及动手能力都有一个很大的提高。7通过本次设计，进一步培养学生热爱专业的思

2、想，同时对本专业综合素质的提高起一个积极的推动作用。课程设计过程中，要严格遵守实践环节的时间安排，听从指导教师的指导。正确地完成上述内容，记录实习日记，标准完整地撰写出课程设计报告。指导教师评语及成绩成绩： 指导教师签字： 2009 年 1 月 11 日目 录第1章 课程设计的目的与要求11.1 课程设计目的11.2 课程设计的实验环境11.3 课程设计的预备知识11.4 课程设计要求1第2章 课程设计内容2程序功能介绍2程序整体设计说明2设计思路2数据结构设计及用法说明3程序结构流程图9各模块的功能及程序说明12程序结果13程序源代码及注释13第3章 课程设计总结23参考资料24第1章 课程

3、设计的目的与要求1.1 课程设计目的本课程设计是计算机科学与技术专业重要的实践性环节之一，是在学生学习完?程序设计语言(C)?课程后进行的一次全面的综合练习。本课程设计的目的和任务： 1. 稳固和加深学生对C语言课程的根本知识的理解和掌握 2. 掌握C语言编程和程序调试的根本技能 3. 利用C语言进行根本的软件设计4. 掌握书写程序设计说明文档的能力5. 提高运用C语言解决实际问题的能力 课程设计的实验环境硬件要求能运行Windows 2000/XP操作系统的微机系统。C语言程序设计及相应的开发环境。 课程设计的预备知识熟悉C语言及C语言开发工具。 课程设计要求1. 分析课程设计题目的要求2.

4、 写出详细设计说明3. 编写程序代码，调试程序使其能正确运行4. 设计完成的软件要便于操作和使用5. 设计完成后提交课程设计报告第2章 课程设计内容程序功能介绍内存区域的分配和管理：通过建表、查表、改表和回收登录内存使用情况，系统或用户申请内存时按选定的分配算法确定分区等，保证分配和回收。存储管理分区分配的主要任务是管理存储器资源，为多道程序运行提供有力的支撑。存储管理的主要功能包括：1存储分配。存储管理将根据用户程序的需要给它分配存储器资源。2存储扩充。由于物理内存容量有限，难于满足用户程序的需求，存储管理还应该能从逻辑上来扩充内存储器，为用户提供一个比内存实际容量大得多的编程空间，方便用户

5、的编程和使用。首次适应算法，这种分配算法具有随机性，它介于最正确适应算法和最差适应算法之间，通常适用于系统事先不掌握运行期间可能出现的请求分配和释放回收的信息的情况。最正确适应算法将可利用空间表中一个大小不小于“请求且最接近“请求的空闲块的一局局部配给用户。分配与回收都需要对可利用空间表从头至尾查询一遍。为了防止每次分配都要查询整个链表，通常要求节点从大到小排序，由此只需找到第一个足够大的空闲块即可予以分配。但回收时，必须把回收的空闲块放置在符合大小顺序关系的链表位置。在分配时容易产生太小而无法利用的内存碎片，同时这种做法也保存了那些很大的内存块以备响应将来发生的内存量较大的用户“请求，从而使

6、整个链表逐渐趋向于节点大小差异甚远的状态。程序整体设计说明2.2.1设计思路在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最适宜的适应算法首次适应算法，最正确适应算法，最后适应算法，最坏适应算法，实现分区存储管理的内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接，等等相关的内容。2.2.2数据结构设计及用法说明 1设计合理的数据结构来描述存储空间：1对于未分配出去的局部，用空闲分区链表来描述。struct freeList int startAddress; /* 分区起始地址 */int size;

7、 /* 分区大小 */struct freeList *next; /* 分区链表指针 */ 2对于已经分配出去的局部，由装入内存的作业占据。struct usedList int startAddress; /* 分区起始地址 */int jobID; /* 分区中存放作业ID */struct usedList *next; /* 分区链表指针 */3将作业组织成链表。struct jobListint id; /* 作业ID */int size; /* 作业大小需要的存储空间大小 */int status; /* 作业状态 0 : new job ,1 : in the memory

8、, 2 : finished . */struct jobList *next; /* 作业链表指针 */以上将存储空间分为空闲可占用两局部，在usedlist中设jobID而不设size，可以在不增加空间复杂度与freelist相比的同时更方便的实现可变分区存储管理从后面的一些函数的实现上可以得出这个结论。尽管设置joblist增加了空间复杂度，但它的存在，使得该程序可以方便的直接利用D盘中的JOB文件。该文件可以认为是一个和其他进程共享的资源。通过这个文件，其他进程写入数据供读取。这中思想在操作系统设计中表达的很多。2实现分区存储管理的内存分配功能，选择适应算法首次适应算法，最正确适应算法

9、，最后适应算法，最坏适应算法。根本原理分析： 1 Best fit ：将空闲分区按大小从小到大排序，从头找到大小适宜的分区。2 Worst fit：将空闲分区按大小从大到小排序，从头找到大小适宜的分区。3 First fit ：将空闲分区按起始地址大小从小到大排序，4 Last fit ：将空闲分区按起始地址大小从大到小排序，由此，可将空闲分区先做适宜的排序后用对应的适应算法给作业分配存储空间。排序函数 orderbySize为零那么按分区大小排序，否那么按分区起始地址；inc为零从小到大排序，否那么从大到小排序；通过empty指针返回结果。void order(struct freeList

10、 *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-

11、>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->siz

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

13、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)

14、 /* 与尾部上邻 */p -> size += size; /* 合并尾部节点 */return ;q = (*empty) -> next; /* 处理链表首节点的邻接情况 */if(startAddress + size = q -> startAddress) /* 与首节点下邻 */q -> startAddress = startAddress; /* 合并首节点 */q -> size += size;else if(startAddress + size < q -> startAddress) /* 与首节点不相邻 */makeFre

15、eNode(&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 = startAdd

16、ress + 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 ->

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

18、ment(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 p

19、ress 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;/*修改空闲分区的首节点始址、大小*/(*emp

20、ty) -> 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

21、文件：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 s

22、ize) 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 *statu

23、s)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)2.2.3程序结构

24、流程图main主函数流程图Assignnment函数流程图Acceptment2函数2.2.4各模块的功能及程序说明void acceptment1(RECT *head,RECT *back1)/*首先适应*/void acceptment2(RECT *head,RECT *back1)/*最正确适应，back1为回收结点的地址*/void print(RECT *head) /*输出链表*/int backcheck(RECT *head,RECT *back1) 2.2.5程序结果程序源代码及注释/* 源程序*/*pcb.c*/#include "stdio.h"#

25、include "stdlib.h"#include "string.h"#define MAX 32767typedef struct node /*设置分区描述器*/ int address,size; struct node *next;RECT;/*函数原型*/RECT *assignment(RECT *head,int application);void acceptment1(RECT *head,RECT *back1);void acceptment2(RECT *head,RECT *back1) ;int backcheck(REC

26、T *head,RECT *back1);void print(RECT *head);/*变量声明*/RECT *head,*back,*assign1,*p;int application1,maxblocknum;char way;/*主函数*/main() char choose10; int check; head=malloc(sizeof(RECT); /*建立可利用区表的初始状态*/ p=malloc(sizeof(RECT); head->size=MAX; head->address=0; head->next=p; maxblocknum=1; p-&g

27、t;size=MAX; p->address=0; p->next=NULL; print(head); /*输出可利用表初始状态*/ printf("Enter the way(best or first(b/f)n");/*选择适应策略*/ scanf("%c",&way); do printf("Enter the assign or accept(as/ac)n"); scanf("%s",choose); /*选择分配或回收*/ if(strcmp(choose,"as&qu

28、ot;)=0) /*as为分配*/ printf("Input application:n"); scanf("%d",&application1);/*输入申请空间大小*/ assign1=assignment(head,application1);/*调用分配函数*/ if(assign1->address=-1)/*分配不成功*/ printf("Too large application!,assign fails!nn"); else printf("Success!ADDRESS=%5dn"

29、;,assign1->address); /*分配成功*/ print(head); /*输出*/ else if(strcmp(choose,"ac")=0) /*回收*/ back=malloc(sizeof(RECT); printf("Input Adress and Size!n"); scanf("%d%d",&back->address,&back->size);/*输入回收地址和大小*/ check=backcheck(head,back); /*检查*/ if(check=1) if

30、(tolower(way)='f')/*首先适应算法*/ acceptment1(head,back); /*首先适应*/ else acceptment2(head,back);/*最正确适应*/ print(head); while(!strcmp(choose,"as")|!strcmp(choose,"ac");/*分配函数*/RECT *assignment(RECT *head,int application) RECT *after,*before,*assign; assign=malloc(sizeof(RECT); /

31、*分配申请空间*/ assign->size=application; assign->next=NULL; if(application>head->size|application<=0) assign->address=-1; /*申请无效*/ else before=head; after=head->next; while(after->size<application)/*查找适应的结点*/ before=before->next; after=after->next; if(after->size=appli

32、cation) /*结点大小等于申请大小那么完全分配*/ if(after->size=head->size) maxblocknum-; before->next=after->next; assign->address=after->address; free(after); else if(after->size=head->size) maxblocknum-; after->size=after->size-application; /*大于申请空间那么截取相应大小分配*/ assign->address=after-

33、>address+after->size; if(tolower(way)='b')/*如果是最正确适应，将截取后剩余结点重新回收到适宜位置*/ before->next=after->next; back=after; acceptment2(head,back); if(maxblocknum=0) /*修改最大数和头结点值*/ before=head; head->size=0; maxblocknum=1; while(before!=NULL) if(before->size>head->size) head->s

34、ize=before->size; maxblocknum=1; else if(before->size=head->size) maxblocknum+; before=before->next; assign1=assign; return assign1; /*返回分配给用户的地址*/void acceptment1(RECT *head,RECT *back1)/*首先适应*/ RECT *before,*after; int insert; before=head; after=head->next; insert=0; while(!insert)

35、/*将回收区插入空闲区表*/ if(after=NULL)| (back1->address<=after->address)&& (back1->address>=before->address) before->next=back1; back1->next=after; insert=1; else before=before->next; after=after->next; if(back1->address=before->address+before->size)/*与上一块合并*/ b

36、efore->size=before->size+back1->size; before->next=back1->next; free(back1); back1=before; if(after!=NULL&&(after->address=back1->address+back1->size) /*与下一块合并*/ back1->size=back1->size+after->size; back1->next=after->next; free(after); if(head->size

37、<back1->size) /*修改最大块值和最大块个数*/ head->size=back1->size; maxblocknum=1; else if(head->size=back1->size) maxblocknum+;/*最正确适应，back1为回收结点的地址*/void acceptment2(RECT *head,RECT *back1) RECT *before,*after; int insert ; insert=0; before=head; after=head->next; if(head->next=NULL) /*

38、如果可利用区表为空*/ head->size=back1->size; head->next=back1; maxblocknum+; back1->next=NULL; else while(after!=NULL) /*与上一块合并*/ if(back1->address=after->size+after->address) before->next=after->next; back->size=after->size+back1->size; free(after); after=NULL; else after

39、=after->next; before=before->next; before=head; after=head->next; while(after!=NULL) if(after->address=back1->size+back1->address) /*与下一块合并*/ back1->size=back1->size+after->size; before->next=after->next; free(after); after=NULL; else before=before->next; after=af

40、ter->next; before=head;/*将回收结点插入到适宜的位置*/ after=head->next; do if(after=NULL|(after->size>back1->size) before->next=back1; back1->next=after; insert=1; else before=before->next; after=after->next; while(!insert); if(head->size<back1->size) /*修改最大块值和最大块数*/ head->

41、size=back1->size; maxblocknum+; else if(head->size=back1->size) maxblocknum+; void print(RECT *head) /*输出链表*/ RECT *before,*after; int index,k; before=head->next; index=1; if(head->next=NULL) printf("NO part for assignment!n"); else printf("*index*address*end*size*n&quo

42、t;); while(before!=NULL) printf("-n"); printf(" %-13d%-13d%-13d%-13dn",index,before->address,before->address+before->size-1,before->size); printf("-n"); index+; before=before->next; /*检查回收块的合法性，back1为要回收的结点地址*/int backcheck(RECT *head,RECT *back1) RECT *b

43、efore,*after; int check=1; if(back1->address<0|back1->size<0) check=0;/*地址和大小不能为负*/ before=head->next; while(before!=NULL)&&check)/*地址不能和空闲区表中结点出现重叠*/ if(back1->address<before->address) &&(back1->address+back1->size>before->address) |(back1->address>=before->address)&&(back1->address<before->address+before->siz