基于C语言的动态分区分配算法实现

ゝ一世哀愁。 2024-03-27 15:36 86阅读 0赞

目录  
1需求分析 3  
2概要设计 3  
总体结构 3  
数据结构. 4  
分区分配算法. 5  
回收分区算法. 5  
首次适应算法寻找分区位置. 6  
循环首次适应算法寻找分区位置. 7  
最佳适应算法寻找分区位置. 7  
最坏适应算法寻找分区位置. 7  
绘制状态图算法. 8  
程序界面. 8  
3运行环境 8  
硬件环境. 8  
软件环境. 9  
4开发工具和编程语言 9  
5详细设计 9  
链表初始化 9  
分配分区函数. 9  
回收分区函数. 10  
首次适应算法. 11  
循环首次适应算法. 12  
最佳适应算法. 12  
最坏适应算法. 13  
分配状态显示图与表. 13  
输入分配回收序列控制函数. 15  
6调试分析 17  
7测试结果 17  
8参考文献 21  
9心得体会 22

2 概要设计  
总体结构：  
在 C 语言面向过程编程方法中，常用分层方法进行编程，降低各模块之间的耦合度。在操作系统中，也用到了分层思想进行设计，每一步设计都建立在可靠的基础上，这样易于扩充和维护系统。  
在此次的课程设计中，同样也使用分层的方法，可以将各种算法很简单方便的一起实现。最底层是基本的数据结构，用来存储分区的信息。上一层是分配分区的函数 alloc()和回收分区的函数 free()。通过调用 alloc()和 free()函数可以实现四种算法。通过图形展示算法可以直观地显示分配和回收过程。最上一层是程序的界面，允许用户可以自由的对内存进行分配和回收，程序展示动态结果。  
总体结构如图 1。  
![在这里插入图片描述][369cac7a51984b66a93d0de1583ca20a.png]  
图 1 程序总体结构

数据结构：  
在实际的操作系统中，分配出去的内存记录在进程控制块中，为了加快内存的分配过程，动态分区最常采用的数据结构是空闲表或空闲链表，数据结构只记录未分配的内存分区。为了降低模拟程序的复杂度，本模拟将分配出去的和未分配出去的内存分区记录在同一个数据结构中，用一个标志表示是否已被分配。各分区按地址递增次序排列。内存的分配和回收只要是对数据结构做插入和删除操作，采用双向链表结构。  
为使程序具有扩展性灵活性， 分区大小采用宏定义方式（ \#define MEMORY\_SIZE 640），可修改分区的大小，展示在不同分区大小下的分配情况。

typedef struct SubAreaNode *SubAreaList;
    struct SubAreaNode
    {
        
    int addr;	//分区起始地址int size;	//分区大小
    int stat;	//分区状态 宏定义 ALLOCED 1	FREE 0 int pid;		//已分配分区的进程 id
    
    SubAreaList pre; SubAreaList next;
    };
    SubAreaList head;	//全局变量 分区链表首指针
    SubAreaList nowList;	//当前位置分区指针 用于循环首次适应算法

![在这里插入图片描述][81bb76fcb43249c4981baa5b6d5b8848.png_pic_center]  
![在这里插入图片描述][324290e2699e4c4c808d591492ac05ac.png_pic_center]  
![在这里插入图片描述][894b0135e8ea46bfb8492dd05d360e98.png_pic_center]  
![在这里插入图片描述][13752e0b42b8470a8bb508ea16bcf978.png_pic_center]  
![在这里插入图片描述][e2be94e154074799b041f70460eaff9f.png_pic_center]  
![在这里插入图片描述][4b2efc96babd4dfeb7078066066fbe4d.png_pic_center]  
![在这里插入图片描述][132780fa82fe4e40b9e4479adbb7fec9.png_pic_center]  
![在这里插入图片描述][4648921c649b4ee7919f02815f9c0dea.png_pic_center]  
![在这里插入图片描述][3aeedfd3ab16405a9e41ea8b32435e57.png_pic_center]  
![在这里插入图片描述][beff97494a5b410bae2c5cb1d5446d5a.png_pic_center]  
![在这里插入图片描述][5b0d2549c32149d294d4cb072035580f.png_pic_center]  
![在这里插入图片描述][d76c2cfc8f3946a88758ee1dd7f9fdd5.png_pic_center]

[369cac7a51984b66a93d0de1583ca20a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1d3cbdc68b9448069bac6efd153b55b8.png
[81bb76fcb43249c4981baa5b6d5b8848.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/43ac3e0148204d8d8bef73d09beacb87.png
[324290e2699e4c4c808d591492ac05ac.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/4f53d61fd91d4e298e8d329719d7672e.png
[894b0135e8ea46bfb8492dd05d360e98.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1d30ccc298d74bcf8de9313c8e62477b.png
[13752e0b42b8470a8bb508ea16bcf978.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/5fea64f9e2c7476280c38e2c617e3892.png
[e2be94e154074799b041f70460eaff9f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/86fbd999a8764c1bb7ec227ee7dc6e5c.png
[4b2efc96babd4dfeb7078066066fbe4d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/cb321088ddcc4ff1ba77191eb75a65d4.png
[132780fa82fe4e40b9e4479adbb7fec9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/5d534cd85b8243d0a52166b92dceeb33.png
[4648921c649b4ee7919f02815f9c0dea.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/92877e2efd534beba3e409f71b5dec9d.png
[3aeedfd3ab16405a9e41ea8b32435e57.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/598ca1935ec045db8d810c3e92f87d02.png
[beff97494a5b410bae2c5cb1d5446d5a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/ac6dbcc98ced4ef48bfb58a5a65356f1.png
[5b0d2549c32149d294d4cb072035580f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/1c4fd0b0fb9742778428632282f35bb1.png
[d76c2cfc8f3946a88758ee1dd7f9fdd5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/b609afafa0614e27ac29b2c291756324.png