《操作系统课程设计-内存管理》由会员分享，可在线阅读，更多相关《操作系统课程设计-内存管理（26页珍藏版）》请在金锄头文库上搜索。
1、仲恺农业工程学院课程设计报告课程名称：操作系统实验题目：内存管理院 系：信息科学与技术学院班 级： 姓 名： 学 号： 二十五年十二月三十日目录1 系统分析31.1目的和意义31.2目标分析32总体设计42.1程序设计组成框图4系统分为4个子模块：初始化模块，4初始化模块：42.2流程图53详细设计63.1设计思路63.1.1.动态分区分配63.1.2.动态分区分配中的数据结构63.1.3.动态分区分配算法63.1.4.回收内存73.2参数定义73.3数据结构73.4函数定义73.5算法分析84核心代码实现84.1首次适应算法84.2最佳适应算法94.3最差适应算法115 程序调试133.3分
2、配内存143.4回收内存及合并分区156 总结177参考文件178源代码181 系统分析1.1 目的和意义操作系统课程主要讲述的内容是多道操作系统的原理与技术，与其它计算机原理、编译原理、汇编语言、计算机网络、程序设计等专业课程关系十分密切。本课程设计的目的综合应用学生所学知识，建立系统和完整的计算机系统概念，理解和巩固操作系统基本理论、原理和方法，掌握操作系统开发的基本技能。1.2 目标分析11.111.11.1.111.11.1.1.1.2.1 采用可变分区方式完成对存储空间的管理（即存储空间的分配与回收工作）。1.2.2 设计用来记录主存使用情况的数据结构：已分区表和空闲分区表或链表。1
3、.2.3 在设计好的数据结构上设计一个主存分配算法。1.2.4 在设计好的数据结构上设计一个主存回收算法。其中，若回收的分区有上邻空闲分区和（或）下邻空闲分区，要求合并为一个空闲分区登记在空闲分区表的一个表项里。2总体设计122.1 程序设计组成框图系统分为4个子模块：初始化模块，首次适应算法模块、最佳适应算法模块、最差适应算法模块的四个算法模块。 初始化模块：allocation( )初始化函数，给每个相关的算法分配内存赋值。首次适应算法模块，利用首次适应算法实现主存空间的分配并可以查看主存空间的分配情况和内存的回收。最佳适应算法模块，利用首次适应算法实现主存空间的分配并可以查看主存空间的分
4、配情况和内存的回收。最差适应算法模块，利用首次适应算法实现主存空间的分配并可以查看主存空间的分配情况和内存的回收。Main（）allocation( )初始化最差适应算法最佳适应算法首次适应算法回收内存分配内存回收内存分配内存回收内存分配内存2.2 流程图分配成功表头移动错误退出查找下一个可用内存是否足够设定内存分配可用内存回收内存表头不变，区间合并表头移动至上领区间并合并是否含有上领或下领区间3详细设计1233.1 设计思路1.2.3.3.1.3.1.1. 动态分区分配动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态的为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用
5、的数据结构，分区分配算法和分区的分配与回收操作这样三方面的问题。3.1.2. 动态分区分配中的数据结构为了实现动态分区分配，系统中必须配置相应的数据结构，用以描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有以下两种形式:（1）空闲分区表，在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区号，分区大小和分区始址等数据项。（2）空闲分区链，为实现对空闲分区的分配和链接，在每个分区的其实部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针，在分区尾部则设置一后向指针。通过前后相链接指针，可将所有的空闲分区链接成一个双向链。3
6、.1.3. 动态分区分配算法首次适应算法（FF算法）：FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存空间，分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则表示系统中已没有足够大的内存分配给该进程，内存分配失败，返回。最佳适应（BF算法）：BF算法是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链。这样，第一次找
7、到的能满足要求的空闲区必然是最佳的。最坏适应算法（WF算法)：与最佳适应算法正好相反，在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，从中分割一小部分存储空间给作业使用，以至于存储器中缺失大的空闲分区。该算法要求，将所有的空闲分区，按其容量以从大到小的顺序形成一空闲分区链，查找时，只要看第一个分区是否满足作业要求即可。3.1.4. 回收内存（1）回收分区与插入点的后一空闲分区F2相邻接。此时也可将两分区合并，形成新的空闲分区，但用（2）回收区的首址作为新空闲区的首址，大小为两者之和。（3）回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并，使用F1的表项和F1的首址，取消F2的
8、表项，大小为三者之和。（4）回收区既不与F1邻接，也不与F2邻接。这时应为回收区单独建立一个新表项，填写回收区的首址和大小，并根据其首址插入到空闲链表中的适当位置。3.2 参数定义#define OK 1 /完成 #define ERROR 0 /出错typedef int Status;LinkList first;/头结点LinkList end;/尾结点int flag;/记录要删除的分区序号3.3 数据结构typedef struct free_table/定义一个空闲区说明表结构int num; /分区序号long address; /起始地址long length;/分区大小 in
9、t state; /分区状态 ElemType;typedef struct Node/线性表的双向链表存储结构ElemType data;struct Node*prior;/前趋指针struct Node *next;/后继指针Node,*LinkList;3.4 函数定义Status Initblock()/初始化函数Status First_fit(int request) /首次适应算法Status Best_fit(int request)/最佳适应算法Status Worst_fit(int request) /最差适应算法3.5 算法分析首次适应算法（First Fit）： 从
10、空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。最佳适应算法（Best Fit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。最差适应算法（Worst Fit）也称最差适配算法：它从
11、全部空闲区中找出能满足作业要求的、且大小最大的空闲分区，从而使链表中的结点大小趋于均匀，适用于请求分配的内存大小范围较窄的系统。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按大小从大到小进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留小的空闲区，尽量减少小的碎片产生。4 核心代码实现4.1 首次适应算法Status First_fit(int request) /首次适应算法Node *p=first-next;/为申请作业开辟新空间且初始化 LinkList temp=(LinkList)malloc(sizeof(Node);temp-data.length=req
12、uest;temp-data.state=1;p-data.num=1;while(p)if(p-data.state=0)&(p-data.length=request)/有大小恰好合适的空闲块p-data.state=1;return OK;break;else if(p-data.state=0) & (p-data.lengthrequest)/有空闲块能满足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;temp-data.num=p-data.num;p-prior-next=temp;p-
13、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;4.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-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;/没有找到空闲块
