用C语言模拟内存分区分配管理最佳适应算法.doc

用C语言模拟内存分区分配管理最佳适应算法[摘要]本文用C语言程序设计中链表的思想，模拟了操作系统课程存储管理的最佳适应算法，其运行结果形象地展示了动态内存分配与回收的过程。这不仅能激发学生学习枯燥的操作系统，还有助于学生更好地掌握C语言知识的综合应用，提高学生的编程能力 [关键词] C语言；模拟；内存管理；最佳适应算法 Using C Programming Language to Simulate Best - Fit Algorithm of Memory Allocation and Recovery FU Ming-bai (Department of Computer Science, Zhaotong teacher’s College, Zhaotong 657000, China) 【Abstract】Using linked list of C programming language, the paper simulates best - fit algorithm and displays the results of memory allocation and recovery. It not only can arouse the student to study boring operating system, but also helps the student to grasp the C language knowledge, improves students’ comprehensive application programming ability. 【Key words】C Programming Languages; Simulation; Memory Management; Best -Fit Algorithm 1引言 内存管理和有效使用是操作系统十分重要的内容，而最佳适应算法是操作系统中内存管理的主要功能之一。迄今为止，操作系统教程和教学中都还没有设计和要求相应的实验，理论化的操作系统课程教学导致了教师讲不清、学生难理解、课程结束学生也只记得一些简单概念，失去了学习这门课程的意义。为此，用学生学过的编程语言来实现操作系统汉语化的算法是有着积极和现实意义的 2设计思想 在采用分区管理的计算机系统中，初始时，除了操作系统占用的内存外，其余存储区为用户可利用空间，称为自由区，每当为用户要求分配主存空间时，操作系统将查找和截取满足用户要求的空闲区分配给用户，将剩余量构成一个新的自由区；当终止某进程后，系统将回收用户释放的内存空间。由于系统不断地分配和回收，可利用空间将形“碎片” 最佳适应算法的思想就是将回收区与地址相邻的自由区有效合并，尽量减少“碎片”的形成，最大限度地利用内存空间；而分配时尽量挑选能满足申请长度的最小自由区，为了节省查找时间，需把自由区按其块大小从小到大排序。模拟算法用C语言程序设计中链表的方法来对空闲区进行管理 3算法设计 自由分区用C语言中的结构体FREE来描述，其结点由自由区首地址、大小以及指向下一个自由区的指针组成；分配算法用get_block()函数来实现，其中用变量maxblocknum记录最大自由区个数；回收算法用free_block ()函数完成；由于是模拟程序，用print()函数输出模拟结果，同时用check_block()函数检查输入数据的合法性 3.1数据结构 程序以整数为例，初始时分配内存的最大值宏定义为：#define MAX 32767，全局变量为：FREE *head,* recovery,* allocation1,*p *add_back; int application1,maxblocknum;它们具体作用将分别在各功能函数中介绍，描述内存分配的结点为： typedef struct node /*设置空闲块*/ { int address,size; /*地址和大小*/ struct node *next; /*后继结点的指针*/ }FREE; 3.2 main()函数 主函数的算法主要包括：建立头结点head；内存分配申请al和回收内存re的选择，如果输入al就输入申请的大小并调用分配函数get_block()，若分配成功，则调用print()函数输出分配结果；输入re将提示输入回收区的首地址和回收区的大小，然后调用check_block()函数检查输入的合法性，若输入合法，则调用free_block ()函数回收内存，并再次调用print()函数输出回收结果。用循环算法do-while();实现多次分