操作系统课程设计内存管理含源代码

1、课程设计说明书（操作系统） 题目: 内存管理_ 院 系：计算机科学与工程学院 专业班级：_信息安全13-2班_ 学 号： _ _ 学生姓名： _ 指导教师： _ _ 2015年 11月21 日 安徽理工大学课程设计（论文）任务书计算机科学与工程学院 学 号2013302970学生姓名谷郁专业（班级）信息安全13-2设计题目内存管理设计技术参数1、采用可变分区方式完成对存储空间的管理（即存储空间的分配与回收工作）。2、设计用来记录主存使用情况的数据结构：已分区表和空闲分区表或链表。3、在设计好的数据结构上设计一个主存分配算法。4、在设计好的数据结构上设计一个主存回收算法。其中，若回收的分区有上邻

2、空闲分区和（或）下邻空闲分区，要求合并为一个空闲分区登记在空闲分区表的一个表项里。设计要求1、编写程序实现采用可变分区方法管理内存，通过实验加强对内存管理方法的理解和掌握； 2、在完成电子设计后，要求写一份详细的设计报告。工作量编写代码不少于200行；程设计说明书不少于15页。工作计划参考资料指导教师签字教研室主任签字 安徽理工大学课程设计（论文）成绩评定表学生姓名： 谷郁 学号： 2013302970 专业班级： 信息安全13-2 程序设计训练题目： 内存管理 评价单元评价要素评价内涵满分评分知识水平30%文献查阅与知识运用能力能独立查阅文献资料，并能合理地运用到程序设计训练之中；能将所学课

3、程（专业）知识准确地运用到程序设计之中，并归纳总结本程序设计训练所涉及的有关课程知识20程序设计方案设计能力程序设计整体思路清晰，程序设计方案合理可行10说明书质量50%难度等级与程序设计训练任务书题目难度等级相当10写作水平整体思路清晰，结构合理，层次分明，语言表达流畅，综合概括能力强30写作规范符合程序设计训练报告的基本要求，用语、格式、图表、数据及各种资料引用规范（符合标准）10学习表现20%工作量程序设计训练工作量饱满，能按时完成程序设计训练规定的工作量10学习态度学习态度认真，遵守程序设计阶段的纪律，作风严谨，按时完成程序设计规定的任务，按时上交程序设计训练有关资料10成绩： 指导教

4、师： 年 月 日摘要存储器历来都是计算机系统的重要组成部分。近年来，随着计算机技术的发展更，系统软件和应用类软件在种类、功能上都急剧的膨胀，虽然存储器容量一直在不断扩大，但仍不能满足现代软件发展的需要。因此，存储器仍然是一种宝贵而又稀缺的资源。如果对他加以有效的管理，不仅直接影响到存储器的利用率，而且对系统性能也有重大影响。关键词：存储器，存储器容量，存储器管理，利用率。目录1 系统分析1目的和意义1目标分析12概要设计2设计思路2动态分区分配2动态分区分配中的数据结构22.1.3 动态分区分配算法22.1.4 回收内存22.2 流程图32.3 主要参数33 核心代码实现4首次适应算法43.2

5、 最佳适应算法5最差适应算法6回收内存7分配内存11回收内存及合并分区124 总结145 参考文献141 系统分析 操作系统课程主要讲述的内容是多道操作系统的原理与技术，与其它计算机原理、编译原理、汇编语言、计算机网络、程序设计等专业课程关系十分密切。本课程设计的目的综合应用学生所学知识，建立系统和完整的计算机系统概念，理解和巩固操作系统基本理论、原理和方法，掌握操作系统开发的基本技能。 教师需求分析1、采用可变分区方式完成对存储空间的管理（即存储空间的分配与回收工作）。2、设计用来记录主存使用情况的数据结构：已分区表和空闲分区表或链表。 3、在设计好的数据结构上设计一个主存分配算法。4、 在

6、设计好的数据结构上设计一个主存回收算法。其中，若回收的分区有上邻空闲分区和（或）下邻空闲分区，要求合并为一个空闲分区登记在空闲分区表的一个表项里。2概要设计动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态的为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构，分区分配算法和分区的分配与回收操作这样三方面的问题。 为了实现动态分区分配，系统中必须配置相应的数据结构，用以描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有以下两种形式: （1）空闲分区表，在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号，分

7、区大小和分区始址等数据项。 （2）空闲分区链，为实现对空闲分区的分配和链接，在每个分区的其实部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。通过前后相链接指针，可将所有的空闲分区链接成一个双向链。2.1.3 动态分区分配算法（1） 首次适应算法（FF算法）：FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表示系统中已没有足够大的内存

8、分配给该进程，内存分配失败，返回。（2） 最佳适应（BF算法）：BF算法是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区必然是最佳的。（3） 最坏适应算法（WF算法)：与最佳适应算法正好相反，在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一小部分存储空间给作业使用，以至于存储器中缺失大的空闲分区。该算法要求，将所有的空闲分区，按其容量以从大到小的顺序形成一空闲分区链，查找时，只要看第一个分区是否满足作业要求即可。2

9、.1.4 回收内存 当进程运行完毕释放内存时，系统根据回收的首址，从空闲区链表中找到相应的插入点，此时可能出线以下四种情况之一： （1）回收区与插入点的前一个空闲分区F1相邻接，此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区F1的大小。 （2）回收分区与插入点的后一空闲分区F2相邻接。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。 （3）回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。 （4）回收区既不与F1邻接，也不与F2邻接。这时应为回

10、收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链表中的适当位置。2.2 流程图分配成功表头移动错误退出查找下一个可用内存是否足够设定内存分配可用内存回收内存表头不变，区间合并表头移动至上领区间并合并是否含有上领或下领区间2.3 主要参数 1、typedef struct free table定义空间区，说明空间区，包含以下参数（1） sum 分区序号，整型；（2） address 起始地址，长整型；（3） length 分区大小，长整型；（4） state 分区状态，整型；2、typedef struct Node线性表的双向链表存储结构，包含以下参数（1） *prio

11、r 前趋指针；（2） *next 后继指针；3、flag 记录要删除的分区序号，整型；4、Linklist first 头结点；5、Linklist end 尾结点；6、Status Initblock() 开创带头节点的内存空间链表；7、Void sort（） 分区序号重新排列函数；8、Void show（） 显示主存分配函数；9、Status First_fit(int requset) 首次适应算法；10、Status Best_fit（int request）最佳适应算法；11、Status Worst_fit（int request）最坏适应算法；12、Status deal（Nod

12、e *p）处理回收空间；13、Void main（）主函数。3 核心代码实现Status First_fit(int request) Node *p=first->next;/为申请作业开辟新空间且初始化 LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.length=request;temp->data.state=1;p->data.num=1;while(p) if(p->data.state=0)&&(p->data.length=request) /有大小恰好合适的空闲块

13、 p->data.state=1; return OK; break;else if(p->data.state=0) && (p->data.length>request)/有空闲块能满足需求且有剩余temp->prior=p->prior;temp->next=p; temp->data.address=p->data.address;temp->data.num=p->data.num;p->prior->next=temp;p->prior=temp; p->data.addres

14、s=temp->data.address+temp->data.length;p->data.length-=request;p->data.num+=1;return OK;break;p=p->next;return ERROR;3.2 最佳适应算法Status Best_fit(int request)int ch;/记录最小剩余空间Node *p=first;Node *q=NULL;/记录最佳插入位置LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.length=request;temp-

15、>data.state=1;p->data.num=1;while(p)/初始化最小空间和最佳位置if(p->data.state=0) && (p->data.length>=request) )if(q=NULL)q=p;ch=p->data.length-request; else if(q->data.length > p->data.length) q=p; ch=p->data.length-request; p=p->next; if(q=NULL) return ERROR;/没有找到空闲块els

16、e if(q->data.length=request)q->data.state=1;return OK;else temp->prior=q->prior; temp->next=q; temp->data.address=q->data.address; temp->data.num=q->data.num; q->prior->next=temp; q->prior=temp; q->data.address+=request; q->data.length=ch; q->data.num+=1;

17、 return OK;return OK;Status Worst_fit(int request) int ch;/记录最大剩余空间 Node *p=first->next; Node *q=NULL;/记录最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.length=request;temp->data.state=1;p->data.num=1; while(p)/初始化最大空间和最佳位置if(p->data.state=0 && (p->data.length

18、>=request) )if(q=NULL)q=p;ch=p->data.length-request;else if(q->data.length<p->data.length)q=p;ch=p->data.length-request;p=p->next;if(q=NULL) return ERROR;/没有找到空闲块else if(q->data.length=request)q->data.length=1;return OK;elsetemp->prior=q->prior;temp->next=q;temp-&

19、gt;data.address=q->data.address;temp->data.num=q->data.num;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.length=ch;q->data.num+=1;return OK; return OK; Status deal1(Node *p)/处理回收空间Node *q=first;for(;q!=NULL;q=q->next)if(q=p)if(q->prior->data.s

20、tate=0&&q->next->data.state!=0)q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;if(q->prior->data.state!=0&&q->next->data.state=0)q->data.length+

21、=q->next->data.length; q->next=q->next->next; q->next->next->prior=q;q->data.state=0;q->data.num=flag;if(q->prior->data.state=0&&q->next->data.state=0)q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior

22、=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;if(q->prior->data.state!=0&&q->next->data.state!=0)q->data.state=0;return OK;Status deal2(Node *p)/处理回收空间Node *q=first;for(;q!=NULL;q=q->next)if(q=p)if(q->prior->data.state=0&&q->next->d

23、ata.state!=0)q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=p->prior;q->data.state=0;q->data.num=flag-1; if(q->prior->data.state!=0&&q->next->data.state=0)q->data.state=0;if(q->prior->data.state=

24、0&&q->next->data.state=0) q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;if(q->prior->data.state!=0&&q->next->data.state!=0)q->data.state=0;ret

25、urn OK; /主存回收Status recovery(int flag)Node *p=first;for(;p!=NULL;p=p->next)if(p->data.num=flag)if(p->prior=first)if(p->next!=end)/当前P指向的下一个不是最后一个时if(p->next->data.state=0)/与后面的空闲块相连p->data.length+=p->next->data.length;p->next->next->prior=p;p->next=p->next-&

26、gt;next;p->data.state=0;p->data.num=flag;else p->data.state=0;if(p->next=end)/当前P指向的下一个是最后一个时p->data.state=0;/结束if(p->prior=block_first)的情况else if(p->prior!=first)if(p->next!=end)deal1(p);elsedeal2(p);/结束if(p->prior!=block_first)的情况/结束if(p->data.num=flag)的情况printf("

27、;t*回收成功*");return OK;4 程序调试 以最佳适应算法为例进行程序调试，调试结果如下4.1开始界面 4 总结 本次课程设计使我加深了请求页式存储管理中置换算法的理解，在这次设计中，我学到了许多知识，由于之前的C语言、数据结构等基础打的不好，分析算法程序时感到很吃力，在刚开始编程时很茫然，无从下手，所以先看了老师之前的程序，也到网上看了别人写的相似程序，这才对存储管理的各个算法的设计有一点眉目。 在这次课程设计中，我不仅学会了一些C+知识，还知道了一个道理：有些程序编写看起来很难，毫无头绪，一旦你尝试去写，最终你终能得到你想要的结果，不怕你不会，就怕你不做。 

28、通过各个置换算法的设计编程，使我在思维、看待问题的全面性等方面也有了很大的提高。让我对实验原理有更深的理解，通过把该算法的内容，算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样执行的，对该理论在实践中的应用有深刻的理解。并且这次课程设计把各个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机整体的认识更加深刻。我希望今后能在动手方面加强，多上机。虽然现在的我还不能独立的完成这样一个复杂的设计，但我相信经过这样一次又一次的设计，最终我能做得更好。5 参考文献1.汤小丹计算机操作系统（第三版）西安：电子科技大学出版社2.张丽芬操作系统实验教程清华大学出版社源代码#inclu

29、de<stdio.h>#include<stdlib.h>#define OK 1 /完成 #define ERROR 0 /出错typedef int Status;typedef struct free_table/定义一个空闲区说明表结构int num; /分区序号long address; /起始地址long length;/分区大小 int state; /分区状态 ElemType;typedef struct Node/线性表的双向链表存储结构ElemType data;struct Node*prior;/前趋指针struct Node *next;/后

30、继指针Node,*LinkList;LinkList first;/头结点LinkList end;/尾结点int flag;/记录要删除的分区序号Status Initblock()/开创带头结点的内存空间链表first=(LinkList)malloc(sizeof(Node);end=(LinkList)malloc(sizeof(Node);first->prior=NULL;first->next=end;end->prior=first;end->next=NULL;end->data.num=1;end->data.address=40;end

31、->data.length=600;end->data.state=0;return OK;void sort()/分区序号重新排序Node *p=first->next,*q; q=p->next; for(;p!=NULL;p=p->next) for(q=p->next;q;q=q->next) if(p->data.num>=q->data.num) q->data.num+=1; /显示主存分配情况 void show() int flag=0;/用来记录分区序号 Node *p=first; p->data.n

32、um=0; p->data.address=0; p->data.length=40; p->data.state=1; sort(); printf("ntt主存空间分配情况n"); printf("*nn");printf("分区序号t起始地址t分区大小t分区状态nn");while(p) printf("%dtt%dtt%d",p->data.num,p->data.address,p->data.length); if(p->data.state=0) printf

33、("tt空闲nn"); else printf("tt已分配nn"); p=p->next; printf("*nn"); /首次适应算法Status First_fit(int request) /为申请作业开辟新空间且初始化Node *p=first->next; LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.length=request;temp->data.state=1;p->data.num=1;while(p) if(p->

34、;data.state=0)&&(p->data.length=request) /有大小恰好合适的空闲块 p->data.state=1; return OK; break;else if(p->data.state=0) && (p->data.length>request)/有空闲块能满足需求且有剩余temp->prior=p->prior;temp->next=p; temp->data.address=p->data.address;temp->data.num=p->data.n

35、um;p->prior->next=temp;p->prior=temp; p->data.address=temp->data.address+temp->data.length;p->data.length-=request;p->data.num+=1;return OK;break;p=p->next;return ERROR;/最佳适应算法Status Best_fit(int request)int ch;/记录最小剩余空间Node *p=first;Node *q=NULL;/记录最佳插入位置LinkList temp=(Li

36、nkList)malloc(sizeof(Node);temp->data.length=request;temp->data.state=1;p->data.num=1;while(p)/初始化最小空间和最佳位置if(p->data.state=0) && (p->data.length>=request) )if(q=NULL)q=p;ch=p->data.length-request; else if(q->data.length > p->data.length) q=p; ch=p->data.leng

37、th-request; p=p->next; if(q=NULL) return ERROR;/没有找到空闲块else if(q->data.length=request)q->data.state=1;return OK;else temp->prior=q->prior; temp->next=q; temp->data.address=q->data.address; temp->data.num=q->data.num; q->prior->next=temp; q->prior=temp; q->da

38、ta.address+=request; q->data.length=ch; q->data.num+=1; return OK;return OK;/最差适应算法Status Worst_fit(int request) int ch;/记录最大剩余空间 Node *p=first->next; Node *q=NULL;/记录最佳插入位置 LinkList temp=(LinkList)malloc(sizeof(Node);temp->data.length=request;temp->data.state=1;p->data.num=1; whil

39、e(p)/初始化最大空间和最佳位置if(p->data.state=0 && (p->data.length>=request) )if(q=NULL)q=p;ch=p->data.length-request;else if(q->data.length<p->data.length)q=p;ch=p->data.length-request;p=p->next;if(q=NULL) return ERROR;/没有找到空闲块else if(q->data.length=request)q->data.leng

40、th=1;return OK;elsetemp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;temp->data.num=q->data.num;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.length=ch;q->data.num+=1;return OK; return OK; /分配主存Status allocation(int a)int

41、 request;/申请内存大小printf("请输入申请分配的主存大小(单位:KB):");scanf("%d",&request);if(request<0 |request=0)printf("分配大小不合适，请重试！");return ERROR;switch(a)case 1:/默认首次适应算法 if(First_fit(request)=OK) printf("t*分配成功！*"); else printf("t*内存不足，分配失败！*"); return OK; br

42、eak;case 2:/选择最佳适应算法if(Best_fit(request)=OK)printf("t*分配成功！*");else printf("t*内存不足，分配失败！*");return OK;break;case 3:/选择最差适应算法if(Worst_fit(request)=OK)printf("t*分配成功！*");else printf("t*内存不足，分配失败！*");return OK; break; Status deal1(Node *p)/处理回收空间Node *q=first;for

43、(;q!=NULL;q=q->next)if(q=p)if(q->prior->data.state=0&&q->next->data.state!=0)q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;if(q->prior->data.state!=0&

44、amp;&q->next->data.state=0)q->data.length+=q->next->data.length; q->next=q->next->next; q->next->next->prior=q;q->data.state=0;q->data.num=flag;if(q->prior->data.state=0&&q->next->data.state=0)q->prior->data.length+=q->data.leng

45、th;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;if(q->prior->data.state!=0&&q->next->data.state!=0)q->data.state=0;return OK;Status deal2(Node *p)/处理回收空间Node *q=first;for(;q!=NULL;q=q->next)if(q=p)if

46、(q->prior->data.state=0&&q->next->data.state!=0)q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=p->prior;q->data.state=0;q->data.num=flag-1; if(q->prior->data.state!=0&&q->next->data.st

47、ate=0)q->data.state=0;if(q->prior->data.state=0&&q->next->data.state=0) q->prior->data.length+=q->data.length;q->prior->next=q->next;q->next->prior=q->prior;q=q->prior;q->data.state=0;q->data.num=flag-1;if(q->prior->data.state!=0&&

48、amp;q->next->data.state!=0)q->data.state=0;return OK; /主存回收Status recovery(int flag)Node *p=first;for(;p!=NULL;p=p->next)if(p->data.num=flag)if(p->prior=first)if(p->next!=end)/当前P指向的下一个不是最后一个时if(p->next->data.state=0)/与后面的空闲块相连p->data.length+=p->next->data.length;

49、p->next->next->prior=p;p->next=p->next->next;p->data.state=0;p->data.num=flag;else p->data.state=0;if(p->next=end)/当前P指向的下一个是最后一个时p->data.state=0;/结束if(p->prior=block_first)的情况else if(p->prior!=first)if(p->next!=end)deal1(p);elsedeal2(p);/结束if(p->prior!=b

50、lock_first)的情况/结束if(p->data.num=flag)的情况printf("t*回收成功*");return OK;/主函数void main() int i;/操作选择标记int a;/算法选择标记printf("*n");printf("tt用以下三种方法实现主存空间的分配n");printf("t(1)首次适应算法t(2)最佳适应算法t(3)最差适应算法n");printf("*n");printf("n");printf("请输入所

51、使用的内存分配算法:");scanf("%d",&a);while(a<1|a>3)printf("输入错误，请重新输入所使用的内存分配算法:n");scanf("%d",&a);switch(a)case 1:printf("nt*使用首次适应算法：*n");break; case 2:printf("nt*使用最佳适应算法：*n");break; case 3:printf("nt*使用最坏适应算法：*n");break;Initbl

52、ock();/开创空间表while(1)show();printf("t1: 分配内存t2: 回收内存t0: 退出n");printf("请输入您的操作：");scanf("%d",&i);if(i=1)allocation(a);/分配内存else if(i=2)/内存回收printf("请输入您要释放的分区号：");scanf("%d",&flag);recovery(flag);else if(i=0)printf("n退出程序n");break;/退出else/输入操作有误printf("输入有误，请重试！");continue;车辆制冷与空调第二次作业参考答案车辆隔热壁、制冷方法与制冷剂、蒸汽压缩式制冷一简答题1. 什么是隔热壁的传热系数？它的意义是什么？答：隔