操作系统课程设计内存管理

1、仲恺农业工程学院课程设计报告课程名称：操作系统实验题目：内存管理院 系：信息科学与技术学院班 级：姓 名：学 号：二O十五年十二月三十日目录1 系统分析1.1 目的和意义操作系统课程主要讲述的内容是多道操作系统的原理与技术， 与其它计算机原理、编译原理、汇编语言、计算机网络、程序设计 等专业课程关系十分密切。本课程设计的目的综合应用学生所学知识，建立系统和完整的 计算机系统概念，理解和巩固操作系统基本理论、原理和方法，掌 握操作系统开发的基本技能。1.2 目标分析1.2.1 采用可变分区方式完成对存储空间的管理（即存储空间的 分配与回收工作） 。1.2.2 设计用来记录主存使用情况的数据结构：

2、已分区表和空闲 分区表或链表。1.2.3 在设计好的数据结构上设计一个主存分配算法。1.2.4 在设计好的数据结构上设计一个主存回收算法。其中，若回收的分区有上邻空闲分区和（或）下邻空闲分区，要求合并为一个空闲分区登记在空闲分区表的一个表项里。2总体设计2.1程序设计组成框图系统分为4个子模块：初始化模块，首次适应算法模块、最 佳适应算法模块、最差适应算法模块的四个算法模块。初始化模块：（）初始化函数，给每个相关的算法分配内存赋 值。首次适应算法模块，利用首次适应算法实现主存空间的分配 并可以查看主存空间的分配情况和内存的回收。最佳适应算法模块，利用首次适应算法实现主存空间的分配并可以查看主存

3、空间的分配情况和内存的回收。最差适应算法模块，利用首次适应算法实现主存空间的分配并可以查看主存空间的分配情况和内存的回收。2.2流程图3 详细设计3.1 设计思路动态分区分配动态分区分配又称为可变分区分配， 它是根据进程的实际需要， 动态的为之分配内存空间。在实现动态分区分配时，将涉与到分区 分配中所用的数据结构，分区分配算法和分区的分配与回收操作这 样三方面的问题。动态分区分配中的数据结构为了实现动态分区分配，系统中必须配置相应的数据结构，用 以描述空闲分区和已分配分区的情况，为分配提供依据。常用的数 据结构有以下两种形式 :（1）空闲分区表， 在系统中设置一张空闲分区表， 用于记录每 个空

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

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

6、查找时，只要看第一个分区是否满足作业要求即可。 回收内存（1）回收分区与插入点的后一空闲分区 F2 相邻接。此时也可 将两分区合并，形成新的空闲分区，但用（2）回收区的首址作为新空闲区的首址，大小为两者之和。（3）回收区同时与插入点的前、 后两个分区邻接，此时将三个 分区合并，使用 F1 的表项和 F1 的首址，取消 F2 的表项，大小为 三者之和。（4 ）回收区既不与 F1 邻接，也不与 F2 邻接。这时应为回收 区单独建立一个新表项，填写回收区的首址和大小，并根据其首址 插入到空闲链表中的适当位置。3.2 参数定义1 完成0 出错J头结点尾结点记录要删除的分区序号3.3 数据结构定义一个空

7、闲区说明表结构; 分区序号; 起始地址分区大小; 分区状态;线性表的双向链表存储结构J*前趋指针*后继指针,*;3.4 函数定义（）初始化函数（ ） 首次适应算法（ ） 最佳适应算法（ ） 最差适应算法3.5 算法分析首次适应算法（ ）： 从空闲分区表的第一个表目起查找该表， 把最先能够满足要求的空闲区分配给作业，这种方法目的在于减 少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空 闲分区要按地址由低到高进行排序。该算法优先使用低址部分空 闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的 空闲区。最佳适应算法（ ）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这

8、种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进 行排序，自表头开始查找到第一个满足要求的自由分区分配。该 算法保留大的空闲区，但造成许多小的空闲区。最差适应算法 （ ）也称最差适配算法： 它从全部空闲区中找 出能满足作业要求的、且大小最大的空闲分区，从而使链表中的 结点大小趋于均匀， 适用于请求分配的内存大小范围较窄的系统。为适应此算法，空闲分区表(空闲区链)中的空闲分区要按大小从大到小进行排序，自表头开始查找到第一个满足要求的自由分 区分配。该算法保留小的空闲区，尽量减少小的碎片产生。4 核心代码实现4.1 首次适应算法( ) 首次适应算法*> 为

9、申请作业开辟新空间且初始化()();>>1;>1;(p)(>0)(>)有大小恰好合适的空闲块>1;(>0) (>>)有空闲块能满足需求且有剩余>>J>J>>J>>J>>J>J>>>>>1;>J4.2 最佳适应算法( ) 最佳适应算法 记录最小剩余空间 *;J*记录最佳插入位置()();>>1;>1;(p) 初始化最小空间和最佳位置(>0) (>>) ) () J>(> > >)>&

10、gt;() 没有找到空闲块(>) >1;J>>>>>>>>>>>>>1;JJ4.3 最差适应算法( ) 最差适应算法记录最大剩余空间*>J*记录最佳插入位置()();>>1;>1;(p)初始化最大空间和最佳位置(>0 (>>) )()J> (><>)J>>() 没有找到空闲块(>)>1;J>>>>>>>>>>>>>1;J ;5 程序调试以最

11、佳适应算法为例进行程序调试，调试结果如下4.1 开始界面4.2选择最佳适应算法铝最差适应算法bstA所使用的內营分配聲辽=2主存空间分配情况分区状态Kl - T-H起始地址分区大小已分配049空闲406S0内存回收内存退岀0WMFXEFMEXXMEMKFXKjO（耳 XEFMIfJfElCKWXKifKIC 豪 KK 豪 賈恒氈 JCWKJCWJtJCJeJOtJfatlfWK.用以下二种方法实现主存空间的分g己一 «*使用最隹适应鼻注=*3.3分配内存1 = Jrffi内存回收內存的操荷1 请井配的壬童大小£单位:KB>：22 *配成功！ *主存空间分配情况0：退出

12、分区序号起始地址弁区大小分区状态已分配0已分配40空闲62578空闲406Q3E内存2：回收內存 0=退出主早冃就啤存 2=回收内存0：退岀.莽酉諭玉膏大小电单位= KB>=33*）酉己成功! *王存空间分配情况分区序号起始地址分区大小分区状态43已分配己分配已分配空闲彳|己内存 2-回收内存 创退岀 -吉覇鼻津半二3.4回收内存与合并分区塑肉存 2=回收内存王存空间分配情况0：退出起始地址分区大小分区状态已分配4Q空闲4022已分配已分配空闲104?0=回收內存0：退出識人您茁鑽 存土冃青2：回收内存0：退出1=邠己内存翳燥籍£醮区巳2 浮主存空间分配情况分区序号起始地址分区

13、大小分区狀态040已分配4055空闲9555已分配150490空闲韓辭矇心丁收内存审女t滸体旨威俞入袪半：0 :退出-1iso490空闲H-se1=分配内存矚邃豔鬻紘号:回收内存 0：退岀iMKUHWrMiKXiCXZMXXXXXKHXl!:MXMfXlMXXXiMKUJtXMZKXHlCMXXKlCXKNiClCJeHMriMXXXWZMX起始地址分区大小分区状态8己分配40110空闲10490空闲MMOtWf aHCMIOyWWJiiKKMiKHZKK耳鼻；KK豪鼻図区画序耳算耳豪耳耳K豪101耳KU拯豪W审殳简袜-百詹输入法 毛6总结本次课程设计使我加深了请求页式存储管理中置换算法的理解

14、，在这次设计中，我学到了许多知识，由于之前的C语言、数据结构等基础打的不好，分析算法程序时感到很吃力，在刚幵始编程时很茫然，无从下手, 所以先看了老师之前的程序，也到网上看了别人写的相似程序，这才对存 储管理的各个算法的设计有一点眉目。在这次课程设计中，我不仅学会了一些知识，还知道了一个道理：有 些程序编写看起来很难，毫无头绪，一旦你尝试去写，最终你终能得到你 想要的结果，不怕你不会，就怕你不做。 通过各个置换算法的设计编程，使我在思维、看待问题的全面性等方面也 有了很大的提高。让我对实验原理有更深的理解，通过把该算法的内容， 算法的执行顺序在计算机上实现，知道和理解了该理论在计算机中是怎样

15、执行的，对该理论在实践中的应用有深刻的理解。并且这次课程设计把各 个学科之间的知识融合起来，把各门课程的知识联系起来，对计算机整体 的认识更加深刻。我希望今后能在动手方面加强，多上机。虽然现在的我 还不能独立的完成这样一个复杂的设计，但我相信经过这样一次又一次的 设计，最终我能做得更好。7 参考文件1. 陆松华 .操作系统 .电子工业出版社2. 李春葆 .数据结构（第 4 版） .清华大学出版社3. 石玉强语言程序设计 . 电子工业出版社8 源代码<><>1 完成0 出错J定义一个空闲区说明表结构; 分区序号; 起始地址分区大小; 分区状态;线性表的双向链表存储结构J*

16、前趋指针*后继指针,*;头结点尾结点记录要删除的分区序号()开创带头结点的内存空间链表()();()();>>>>>1;>40;>600;>0;J()分区序号重新排序*>,*q;>(>)(>>)(>>>)>1;()显示主存分配情况0 用来记录分区序号*;J>0;>0;>40;>1;();("ntt 主存空间分配情况 n");("*nn");(" 分区序号 t 起始地址 t 分区大小 t 分区状态 nn");(p

17、)("tt">>>);("tt 空闲 nn");("tt 已分配 nn");>("*nn" ( ) 首次适应算法*> 为申请作业开辟新空间且初始化()();>>1;>1;(p)(>0)(>)有大小恰好合适的空闲块>1;(>0) (>>)有空闲块能满足需求且有剩余>>J>J>>J>>J>>J>J>>>J>J>1;J J>JJ( ) 最佳适应

18、算法记录最小剩余空间*;J*记录最佳插入位置()();>>1;>1;(p) 初始化最小空间和最佳位置(>0) (>>) )()J>(> > >)J>>() ;没有找到空闲块(>)J>>>>>>>>>>>>>1;JJ( ) 最差适应算法记录最大剩余空间*>J*记录最佳插入位置()();>>1;>1;(p) 初始化最大空间和最佳位置(>0 (>>) )()J> (><>)J>

19、;>() 没有找到空闲块(>)>1;J>>>>>>>>>>>>>1;J ;分配主存( a)申请内存大小("请输入申请分配的主存大小 (单位 ):");("");(<0 0)(" 分配大小不合适，请重试！ ");(a) 1 默认首次适应算法()("t* 分配成功！);("t* 内存不足，分配失败！ *");2 选择最佳适应算法()("t* 分配成功！);("t* 内存不足，分配失败！ *

20、");3 选择最差适应算法()（"t* 分配成功！);（"t* 内存不足，分配失败！ *"）;1( *p) 处理回收空间*;J(>)()(>>0>>0)>>>>>>>>>>>0;(>>0>>0)>>>>>>>>>>0;>(>>0>>0)>>>>>>>>>>>0;>1;(>

21、>0>>0)2( *p) 处理回收空间*;J(>)()(>>0>>0)>>>>>>>>>>>0;>1;(>>0>>0)(>>0>>0) >>>>>>>>>>>0;>1;(>>0>>0) >0;主存回收( )*;J(>)(>)(>)(>) 当前 P 指向的下一个不是最后一个时(>>0) 与后面的空闲块相连>>>>>>>>>>0;&