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

　　[摘要]本文用C语言程序设计中链表的思想，模拟了操作系统课程存储管理的最佳适应算法，其运行结果形象地展示了动态内存分配与回收的过程。这不仅能激发学生学习枯燥的操作系统，还有助于学生更好地掌握C语言知识的综合应用，提高学生的编程能力。 中国论文网 http://www.xzbu.com/8/view-44054.htm　　 [关键词] 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();实现多次分配与回收过程。 　　3.3 get_block()函数 　　get_block()函数是分配内存块给用户。具体算法如下 　　(1)调用malloc（）函数分配得到一个结点，其size存放用户申请空间application的大小,结点的地址为allocate，如果申请的大小不为正值或超过当前可用空间的最大值，则无法分配，返回失败信息。 　　(2)设置移动指针output和seek，置初始态output=head->next,seek= head->next,在链表中查找seek。如果找到seek－>size==application,且seek－>size==head->size,则maxblocknum块数减1，将seek结点分配给用户，链表指针变为output->next=seek－> next，allocate－>address=seek－>address；如果找到的是seek－>size>=application，则截取需要的长度，即seek－>size=seek－>size－application，allocate－>address=seek－>address+ seek－>size，然后调用回收函数free_block()将剩余的部分插入到链表中的合适位置。 　　（3）如果自由区的最大块数不仅一个，则maxblocknum++。 　　（4）返回调用函数分配到的自由首地址。 　　3.4 free_block()函数 　　free_block()函数是按用户的要求释放内存自由块。具体实现如下： 　　(1)设置移动指针output和seek，置初始态output=head,seek= head->next，如果可利用的分区表为head->next＝＝NULL ，则回收结点的地址add_back将其赋给头结点head的后继结点，maxblocknum++；否则，在链表中查找seek。如果找到add_back->address==seek->size+seek->address，则output->next=seek->next， add_back->size=seek->size+add_back->size,实现与上一块的合并，然后调用free(seek)释放该结点；如果找到的是seek->address==add_back->size+add_back->address, 则 add_back->size=add_back->size+seek->size,output->next=seek->next,完成与下一块的合并，调用free(seek)释放此结点。 　　(2)如果找到的结点为空或大于用户输入的大小，即seek==NULL||(seek->size>add_back->size，则output->next=add_back， add_back->next=seek；否则output=output->next，seek=seek->next,将回收结点插入到合适的位置。 　　（3）如果遍历的内存块小于或等于回收结点的大小，则maxblocknum++。 　　3.5 check_block()函数 　　该函数的功能是检查用户输入的申请分配和回收的数据的合法性，即大小和地址必须为正，并且回收块的地址不能与已有块重叠。 　　3.6 print()函数 　　就是按一定的格式，从头结点的后继结点开始输出链表，直到链表为空。其关键语句有：output=head->next; while(output!=NULL){ printf("%-10d%-10d%-10d\n", output->address,output->address+output->size-1,output->size); output=output->next;} 　　4 模拟结果 　　 　　 　　最佳适应算法的链表是按照块大小排序的。 　　5 结束语 　　通过用C语言模拟实现内存分区分配与回收实验，不仅可以让学生进一步掌握C语言知识的综合应用、提高学生的编程能力，还有助于学生学习枯燥的操作系统课程。在计算机专业课程教学中，把教材中概念性的算法有选择地运用学过的编程语言来实现是值得重视的课题。 　　 　　参考文献： 　　1郭翠英.C语言课程设计案例精编[M].北京：中国水利水电出版社，2004. 　　2廖雷.C语言课程设计[M].北京：高等教育出版社，2003. 　　3李岩，杨断利，王福增.案例教学在高校计算机语言类课程中的应用[J].福建电脑，2008，第24卷（6）：28―29.省略