哈尔滨理工大学
课 程 设 计
（操作系统）
题 目： 可变分区分配与回收—采用最坏算法
班 级： 计算机科学与技术学院 计算机系 10-8班 姓 名： 张兢 1004010813 指导教师： 高雪瑶 系主任： 林克正
2013年03月01日
哈尔滨理工大学课程设计报告
一、 课程设计目的
1、背景
主存是CPU可直接访问的信息空间，合理而有效的使用贮存将在很大程度上影响整个计算机系统的性能。
本课题要求模拟实现分区式主存管理机制。模拟实现各种分区管理方法以及相应的主存分配以及回收算法。
2、目的
通过该课题进一步加深对可变分区存储机制的理解。加深对存储器动态分区分配算法的认识。掌握“首次适应算法”、“下次适应算法”、“最佳适应算法发”、“最坏适应算法”的内存分配过程。掌握内存的回收策略。
二、 课题任务描述
1、设计可用的内存空闲空间，并能动态输入用户作业所需的内存大小。
2、编程模拟各种分配算法的实施过程，允许自行选择如“首次适应算法”、“下次适应算法”、“最佳适应算法发”、“最坏适应算法”等常用算法，要求实现不少于三种算法。
3、实现内存的回收。要求考虑回收时的内存合并问题。
三、 课题研发相关知识 （包含所用库函数的介绍）
1、首次适应算法（first fit）
FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能男足要求的空闲分区位置；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都
哈尔滨理工大学课程设计报告
不能找到一个能满足要求的分区，则此次内存分配失败，返回。但是，低址部分不断被划分，会留下许多难以利用的很小的空闲分区。
2、最佳适应算法（best fit）
所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。这样，在存储器中会留下许多难以利用的小空闲区。
3、最坏适应算法（worst fit）
要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中小作业有力，查找效率很高。但是它会使存储器中缺乏大的空闲分区。
4、回收内存
当进程运行完毕释放内存时，系统根据会收取的首址，从空闲区链中找到相应的插入点，并考虑回收区前后是否有空闲分区，如果有，则把两个分区合并成一个大的空闲分区。
5、库函数的介绍
1）stdio 就是指 “standard buffered input&output\意思就是说带缓冲的标准输入输出！ 所以了，用到标准输入输出函数时，就要调用这个头文件！
2）Stdlib.h即standard library 标准库文件。Stdlib头文件里包含了C,C++语言的最常用的系统函数。Stdlib.h里面定义了五中类型，一些宏和通用工具函数。 类型例如
：
size_t
,wchar_t,
div_t,
ldiv_t,lldiv_t;
宏
例
如
：
EXIT_FALIRE,EXIT_SUCCESS,RAND_MAX和MB_CUR_MAX。
以下是一些常用的函数：dec 置基数为10 相当于\；hex 置基数为16 相当于\；oct 置基数为8 相当于\；setw(n) 设域宽为n个字符
哈尔滨理工大学课程设计报告
四、 课题设计：总体结构、所使用的数据结构、主要功能的流程图、程序的
技术路线
1、总体结构
本系统采用了首次适应算法、最佳适应算法和最坏适应算法模拟存储器动态分区。系统利用其中某种分配算法，从空闲分区链中找到满足请求内存大小的分区并分配内存给作业。假设总的内存大小为size，作业请求的内存大小为request,内存碎片最小为f。当request>size时，内存溢出，出现系统错误；当request<=size时，在内存中根据上述算法寻找最佳的内存分区分配给作业。寻找到合适的内存分区之后，如果size-request<=f,将此分区上的内存全部分配给作业；如果size-request>f，就在此分区上分割request大小的内存给作业，剩余内存继续留在当前的分区中。当进程运行完毕，系统找到该进程并释放其内存，根据所释放内存的位置对内存进行合并。
系统流程图：如图1
哈尔滨理工大学课程设计报告
开始 输入option 选择分配算option=3N 根据option的值选择相应算法，输入Y 退出 ope=0? N Y 分配内存 ope=1? N 回收内存 Y ope=2? N ope=3? N 输入错误 Y Y 返回上一级 图1