动态内存分配范文（精选7篇）
动态内存分配 第1篇
首次适应算法[1,2,3,4]。将可用内存块安置在空闲链表中,分配时总是从空闲链表首部开始查询,并将首个满足的内存块分配出去,该算法有效的保留了高地址端的大空闲区。缺点:在空闲链表的首部(物理空间的首部)容易产生大量的小碎片,且增加了下一次的查询次数。
循环首次适应法[1,2]。与首次适应法相似,循环首次适应法可以将产生的小碎片均匀的分布,有效地缩短了下次查询的时间,但是仍然没有有效地解决存储空间碎片化的问题,而且会导致缺少大的空闲分区。
最佳适应法[1,2,4]。最佳适应法可以有效保留较大的内存块,以满足用户对较大连续存储空间的需求,但是在内存中会产生更小的碎片。
最差适应法[1,2]。将空闲链表中的内存块按照大小顺序,逆序排列(由大至小)。可以有效地减少碎片的产生,但是内存分区会缺乏较大的连续存储空间。
快速适应法[1,2]。将空闲块按照大小进行分类,同时建立一张管理索引表,此算法在查询内存块时效率较高O(1),主要缺点在于合并内存块时,要遍历所有的内存块时间复杂度为O(n)。
伙伴系统[1,2,5,6,7]。已分配或未分配的内存区大小均为2的k次幂,其时间性能比快速适应算法差,但是由于采用了索引搜索算法,比顺序搜索算法好。而其空间性能,由于对空闲分区进行合并,提高了内存空间的可使用率,故优于快速适应法,比顺序搜索法略差。
哈希算法[1]。哈希算法就是利用哈希快速查找的优点,哈希算法具有较高的查找效率,在实际动态内存分配中使用广泛,但是在合并内存时需要逐个查找可用内存块并检查是否为可用的邻区内存。因此,实际开发中亟待需求高效的内存分配与合并算法。基于顺序搜索的动态内存分配算法的特点是管理简单,但效率不高。基于索引搜索的动态内存分配算法的特点是,分配效率较高,但回收效率较低。
两类不同的分配算法在不同的实际应用中有着各自的优势,但是在大多数的应用开发中普遍存在大内存块不易保留,内存碎片化,合并内存块时间开销大等问题[8,9]。multimap映射算法就是指将内存块的大小作为multimap的键,对应的值会记录内存块的地址信息以供分配[10,11]。该算法可以较好地解决上述问题,可以满足不同应用的需求。
1 改进的内存分配算法
基于multimap映射的动态内存分配算法采用C++的STL中提供的multimap关联容器,允许多个相同的键存在,键与值为一一对应关系。算法以内存块的大小作为键,内存块的地址信息作为值,以键值对的形式存储内存块的地址,并在内存块实体的首部与尾部添加标识信息。
1.1 内存分配算法
算法使用STL中multimap关联容器来存储Mcb(自定义的内存控制块)的地址信息。multimap提供了一种可以有重复键值的STL map类型。multimap<int,Mcb*>作为为容器的类型,以内存块的大小作为键,便于查询内存块。当用户申请内存时,通过multimap提供的方法去查询可供用户使用的内存块。使用lower_bound(k),upper_bound(k)可以得到一组指向键为k的元素的迭代器(在有多个相同键值对的情况下,分别指向元素的首端和尾端),如不存在则两个迭代器均指向首个大于键的值元素[11]。
为了避免产生过小的碎片,定义一个常量MIN_SIZE。如果切割内存块后会产生小于MIN_SIZE的碎片,则不再经行切割,直接分配供用户使用。
1.2 内存释放、合并算法
内存块在使用后,为了避免产生内存大量的碎片。需要在释放内存块时,尽可能地将物理空间连续的内存块合并到一起。在合并内存块时,需要遍历空闲内存以查找左邻块、右邻块,时间复杂度为O(n)[12,13,14]。为提高合并效率,本次算法采用边界标识法[2]。在内存块的首部和尾部添加一些信息(首部添加Mcb类型,尾部添加unsigned类型记录此内存块的大小)。添加边界标识的内存块信息分布,如下图1所示:
图1中的指针p,为返回给用户的可用内存块首地址。Is Available用于标识内存块的可用状态,size的大小为包括Mcb与后边界标志在内的大小。通过边界标识法可使合并内存块的复杂度为O(1)。
算法步骤:
在合并内存块时会查找左邻块、右邻块,当释放指针p的内存区域时会发生以下步骤:
(1)将指针P回退到内存块的首部,得到Mcb*mcb(使其指向内存控制块的首部)。
(2)检查当前指针是否在堆区域,指针不可越界。
(3)将mcb->availeble=1变为可用状态。4p sizeof(unsigned)
(4)将指针p继续回退sizeof(unsigned)个字节,读取左邻区的长度。再将指针p回退size-sizeof(unsigned)字节,经过强制类型转换,读取Mcb并判断是否为空闲状态,若是则将其从空闲multimap记录中删除,与左邻块合并后,并将左邻块Mcb中的size改为size+mcb->size,将合并后内存块的尾部标识改为size+mcb->size,将指向向左合并后的内存块,重复执行步骤(4);否则直接跳至步骤(5)。
(5)将指针p向右偏移mcb->size个字节,将指针强制类型转换为Mcb,读取available。若右邻块为空闲块,则将其从空闲multimap记录中删除,并与p当前指向的内存块合并,将mcb->size更新为mcb->size+size,右邻块的尾部标志的值改为size+mcb->size,重复执行(5)步骤;否则跳至步骤(6)。
(6)将合并后的空闲块添加到multimap中。添加至multimap中的内存块可能是与左邻块合并后的内存块,与右邻块合并后的内存块,或者是未合并的内存块。
边界标识法使得在合并内存时,可以通过偏移指针直接获取物理相邻的内存可用信息,所以可使合并内存块的复杂度为O(1)。
2 实验对比分析
数据准备:为尽可能的体现每种分配算法的特征(如,体现循环首次适应的特征,应当至少将内存块的分配循环一次),本次数据元素的选取,将参考实际应用中使用内存块大小的概率,产生若干数据元素以组成数据集合。本次实验环境为:Windows8操作系统,开发工具为vc++6.0。
在实际使用中,申请的内存块大小近似服从正态分布。本次模拟中,可供分配的总空间大小为10000个字节。参考实际使用情况,设定正态分布中期望与方差,可以得到符合实际且较为合理的数据集合[15,16]。
假设数据元素x~N(500,32400),μ=500,σ=180
按照概率随机产生23个样本,作为申请内存的指定大小,并从中随机选取6个元素用于释放内存[16]。通过计算可以得到不同大小的内存块使用的概率,以及取样数量,如下表1所示。
通过取样得到的数据集合为:
执行顺序:
分配内存时,按照Malloc集合中元素的顺序进行分配。在为528,604,345,523,621,494大小的内存块分配内存后,按顺序分别释放Free集合中的元素。
对比不同分配算法下的实验结果,比较不同尺寸空闲块数量,以及空闲块最值可以得到图2、图3:
注:P{0<x≤100}=0.0132,此区间内存块被使用的概率很小,所以将大小在(0,100]的内存块视为内存碎片。
编号1,2,3,4,5分别代表者首次适应法,循环首次适应法,最佳适应法,最差适应法,基于multimap映射算法。
通过图2可以看出,在不同尺寸空闲块数量的比较上,首次适应法与最佳适应法具有相同的结果。循环首次适应法与最差适应法产生大于200个字节的内存块数量较多,首次适应法、循环首次适应法、最佳适应法均产生了不同数量的内存碎片。multimap映射法没有产生内存碎片,且大于200个字节的内存块数目不多。
通过图3可以看出,首次适应法、最佳适应法在空闲块的最值比较上具有相同的结果,保留了较大的连续空间,同
时产生了难以利用的内存碎片。循环首次适应法、最差适应法未能保留较大连续空间,且循环首次适应法产生了内存碎片,但碎片尺寸大于首次适应法与最佳适应法所产生的碎片。multimap映射法保留了较大的连续空间,且未产生内存碎片。
由图2、图3的分析表明,multimap映射法在保留较大连续空间、减少内存碎片方面具有一定的优势。
不同的分配算法选取的数据结构可能存在一定的差异,通过分析不同算法所采用的数据结构以及具体操作的时间开
销,并参考图2、图3的实验结果。可以对不同内存分配算法的效率进行比较,从而得到具有更低时间开销的分配算法。整理结果可得如下表2:
由表2可以看出,在分配内存上最差适应法与multimap映射法具有较低的时间复杂度,分别为O(1)、O(log n)。在回收内存上multimap映射法的时间复杂度为O(1),优势较为明显。经综合比较可以发现multimap映射法在降低时间开销、保留较大连续空间、减少内存碎片方面具有较为明显的优势。
3 结束语
对几种动态内存分配算法进行分析与对比,可以看出选取不同的数据结构会对效率产生显著地影响。multimap映射算法通过红黑树的组织存储形式,提高了内存块的分配与回收的效率,通过边界标识法极大地改善了内存块合并的效率。虽然边界标识法是以消耗一定空间的方式来提升速度,但是当消耗的空间所占有效空间的比例较小时,是可以接受的。总体上,multimap算法较好地解决了大内存块不易保留,易产生碎片,合并内存时间开销大等问题。
摘要：对多种不同的动态内存分配算法的特点与优劣进行对比、分析,在兼顾效率和内存碎片率指标的要求下,提出了基于multimap映射的动态内存分配算法。该算法以内存块的大小作为键,内存块的地址信息作为值,以键值对的形式存储内存块的地址,并在内存块实体的首部与尾部添加标识信息。为检验算法效果,设计了多组数据对新算法和现有经典内存管理算法效率进行比较,实验结果表明新算法在降低时间开销,保留较大连续空间,减少内存碎片等方面具有较明显的改善。
关键词：动态内存分配,内存碎片,边界标识法,multimap
参考文献
[1]汤小丹,梁红兵,哲凤屏,汤子瀛.计算机操作系统(第四版)[M].西安:西安电子科技大学出版社,2014.
[2]严蔚敏.数据结构C语言版[M].北京:清华大学出版社,2007.
[3]Weinstock C.Dynamic Storage Allocation Techniques[D].Carne-gie-Mellon University,Pittsburgh,1976.
[4]池元武.嵌入式实时操作系统动态内存管理优化方案的研究[D].上海交通大学软件学院,2011.
[5]Peterson J L,Norman T A.Buddy Systems[J].Communications ofthe ACM,2007,20(6):421-431.
[6]姜立波.Linux内存管理分析与研究[D].电子科技大学,2011:46-58.
[7]王振江.提高堆数据局部性的动态池分配技术[J].计算机学报,2011(4):665-675.
[8]Stephenson C J.Fast Fits:New Methods for dynamic storage al-location[C].Proceedings of the 9th Symposium on OperatingSystems,ACM,1983.
编程中内存分配总结 第2篇
堆，可以动态分配，大小可近似认为无限制，可以一直存在
堆：malloc(), free()需要自己申请与自己负责释放!适用于事先不知道需要分配多大空间的情况。
栈：void fun(int x){int y;...}系统帮你分配与释放。
/////////////////////////////////////////////////////////////////// 一个由C/C++编译的程序占用的内存分为以下几个部分
1、栈区（stack）— 由编译器自动分配释放，存放函数的参数值，局部变量的值等。其
操作方式类似于数据结构中的栈。
2、堆区（heap）— 一般由程序员分配释放，若程序员不释放，程序结束时可能由OS回
收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表，呵呵。
3、全局区（静态区）（static）—，全局变量和静态变量的存储是放在一块的，初始化的
全局变量和静态变量在一块区域，未初始化的全局变量和未初始化的静态变量在相邻的另
一块区域。已初始化全局/静态变量，在整个软件执行过程中有效；.bss函数调用栈，其中的内容在函数执行期间有效，并由编译器负责分配和收回；
.heap程序结束后由系统释放。
4、文字常量区 —常量字符串就是放在这里的。程序结束后由系统释放
5、程序代码区—存放函数体的二进制代码。
二、堆和栈的理论知识 2.1申请方式
stack: 由系统自动分配。例如，声明在函数中一个局部变量 int b;系统自动在栈中为b开辟空间 heap: 需要程序员自己申请，并指明大小，在c中malloc函数 如p1 =(char *)malloc(10);在C++中用new运算符 如p2 = new char[10];但是注意p1、p2本身是在栈中的。
2.2 申请后系统的响应
栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢 出。
堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表
中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的
首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。
另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部
分重新放入空闲链表中。
2.3申请大小的限制
栈：在Windows下,栈是向低地址扩展的数据结构，是一块连续的内存的区域。这句话的意
思是栈顶的地址和栈的最大容量是系统预先规定好的，在WINDOWS下，栈的大小是2M（也有 的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将
提示overflow。因此，能从栈获得的空间较小。
堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储 的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小
受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。
2.4申请效率的比较：
栈由系统自动分配，速度较快。但程序员是无法控制的。
堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，他不是在堆，也不是在栈是
直接在进程的地址空间中保留一块内存，虽然用起来最不方便。但是速度快，也最灵活。
2.5堆和栈中的存储内容
栈： 在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可
执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈 的，然后是函数中的局部变量。注意静态变量是不入栈的。
当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地
址，也就是主函数中的下一条指令，程序由该点继续运行。
堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。
2.6存取效率的比较
char s1[] = “aaaaaaaaaaaaaaa”;char *s2 = “bbbbbbbbbbbbbbbbb”;aaaaaaaaaaa是在运行时刻赋值的；
而bbbbbbbbbbb是在编译时就确定的；
但是，在以后的存取中，在栈上的数组比指针所指向的字符串(例如堆)快。
比如： #include void main(){ char a = 1;char c[] = “1234567890”;
char *p =“1234567890”;a = c[1];a = p[1];return;} 对应的汇编代码 10: a = c[1];
00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh] 0040106A 88 4D FC mov byte ptr [ebp-4],cl 11: a = p[1];
0040106D 8B 55 EC mov edx,dword ptr [ebp-14h] 00401070 8A 42 01 mov al,byte ptr [edx+1] 00401073 88 45 FC mov byte ptr [ebp-4],al 第一种在读取时直接就把字符串中的元素读到寄存器cl中，而第二种则要先把指针值读到
edx中，再根据edx读取字符，显然慢了。
2.7小结：
堆和栈的区别可以用如下的比喻来看出：
使用栈就象我们去饭馆里吃饭，只管点菜（发出申请）、付钱、和吃（使用），吃饱了就走，不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作，他的好处是快捷，但是自由度小。
Java虚拟机内存分配探析 第3篇
按照编译原理的观点把内存分配策略划分为3种:静态的、栈式的和堆式的。静态存储分配是指在编译时就能确定每个数据目标在运行时刻的存储空间需求, 因而在编译时就分配固定的内存空间, 这种分配策略要求程序代码中不允许有可变数据结构 (比如可变数组) 的存在。Java语言是面向对象, 并且具有多态性的特点, 因此JVM选用动态内存分配策略:堆和栈。
1 堆和栈
在函数中定义的一些基本类型的变量和对象的引用变量都在函数的栈内存中分配。
当在一段代码块定义一个变量时, Java就在栈中为这个变量分配内存空间, 当超过变量的作用域后, Java会自动释放掉为该变量所分配的内存空间, 该内存空间可以立即被另作他用。
堆内存用来存放由new创建的对象和数组。在堆中分配的内存, 由Java虚拟机的自动垃圾回收器来管理。在堆中产生了一个数组或对象后, 还可以在栈中定义一个特殊的变量, 让栈中这个变量的取值等于数组或对象在堆内存中的首地址, 栈中的这个变量就成了数组或对象的引用变量。引用变量就相当于是为数组或对象起的一个名称, 以后就可以在程序中使用栈中的引用变量来访问堆中的数组或对象。
Java是自动管理栈和堆, 程序员不能直接地设置栈或堆。
Java的堆是一个运行时数据存储区, 类的对象从中分配空间。对象通过new、newarray等方式建立, 不需要程序代码来显式地释放。堆是由垃圾回收来负责的, 堆的优势是可以动态地分配内存大小;缺点是, 存取速度较慢。
栈的优点是, 存取速度比堆要快, 仅次于寄存器。栈数据可以共享;缺点是, 存在栈中的数据大小与生存期必须是确定的, 缺乏灵活性。栈中主要存放一些基本类型的变量 (int, short, long, byte, float, double, boolean, char) 和对象句柄。
栈有一个重要特点, 就是存在栈中的数据可以共享。假设定义:
编译器先处理int a=3;首先会在栈中创建一个变量为a的引用, 然后查找栈中是否有3这个值, 如果没找到, 就将3存放进来, 然后将a指向3。接着处理int b=3;在创建完b的引用变量后, 因为在栈中已经有3这个值, 便将b直接指向3。这样, 就出现了a与b同时均指向3的情况。这时, 如果再令a=4;那么编译器会重新搜索栈中是否有4值, 如果没有, 则将4存放进来, 并令a指向4;如果已经有了, 则直接将a指向这个地址。因此a值的改变不会影响到b的值。要注意这种数据的共享与两个对象的引用同时指向一个对象的这种共享是不同的, 因为这种情况a的修改并不会影响到b, 它是由编译器完成的, 它有利于节省空间。而一个对象引用变量修改了这个对象的内部状态, 会影响到另一个对象引用变量。
2 String类对象举例说明
String是一个特殊的包装类数据。可以用:
两种的形式来创建, 第一种是用new () 来新建对象的, 它会在存放于堆中。每调用一次就会创建一个新的对象。
而第二种是先在栈中创建一个对String类的对象引用变量str, 然后查找栈中有没有存放“abc”, 如果没有, 则将“abc”存放进栈, 并令str指向“abc”, 如果已经有“abc”, 则直接令str指向“abc”。
比较类里面的数值是否相等时, 用equals () 方法;当测试两个包装类的引用是否指向同一个对象时, 用==, 下面用例子说明上面的理论。
因此用第二种方式创建多个“abc”字符串, 在内存中其实只存在一个对象而已。这种写法有利于节省内存空间。同时它可以在一定程度上提高程序的运行速度, 因为JVM会自动根据栈中数据的实际情况来决定是否有必要创建新对象。而对于String str=new String (“abc”) ;的代码, 则一概在堆中创建新对象, 而不管其字符串值是否相等, 是否有必要创建新对象, 从而加重了程序的负担。
尤其需要注意的是:在使用诸如String str=“abc”;的格式定义类时, 总是想当然地认为, 创建了String类的对象str。事实是对象可能并没有被创建, 而可能只是指向一个先前已经创建的对象。只有通过new () 方法才是每次都创建一个新的对象。
3 结束语
每一个Java应用都唯一对应一个JVM实例, 每一个实例唯一对应一个堆。应用程序在运行中所创建的所有类实例或数组都放在这个堆中, 并由应用所有的线程共享。Java中分配堆内存是自动初始化的。Java中所有对象的存储空间都是在堆中分配的, 但是这个对象的引用却是在栈中分配, 也就是说在建立一个对象时从两个地方都分配内存, 在堆中分配的内存实际建立这个对象, 而在堆栈中分配的内存只是一个指向这个堆对象的指针 (引用) 而已。
摘要：Java把内存划分为堆和栈。介绍了堆和栈的区别, 并以String类对象为例说明它们在内存分配中的不同, 及对程序编写的影响。
关键词：JVM,堆,栈,string类
参考文献
[1]任哲.Java技术应用基础——对象.模式.虚拟机[M].北京:机械工业出版社, 2009.
[2]Java虚拟机内存分配与回收机制[EB/OL].http://www.yqdown.com/chengxukaifa/Java/11580.htm.
[3][美]BILL VENNERS.深入Java虚拟机[M].北京:机械工业出版社, 2003.
动态内存分配 第4篇
通过编写和调试存储管理的模拟程序以加深对存储管理方案的理解，熟悉可变分区存储管理的内存分配和回收。二．实验内容
1．确定内存空间分配表；
2．采用最优适应算法完成内存空间的分配和回收； 3．编写主函数对所做工作进行测试。
三．实验背景材料
实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格基础上设计内存分配算法；第三，在设计的数据表格基础上设计内存回收算法。
首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占用的区域。
由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表”；一张是记录空闲区的“空闲区表”。这两张表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。
“已分分区表”的结构定义
#define n 10 //假定系统允许的最大作业数量为n struct { float address;//已分分区起始地址
float length;//已分分区长度、单位为字节 int flag;//已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名
}used_table[n];//已分分区表
“空闲区表”的结构定义
#define m 10 //假定系统允许的空闲区最大为m struct { float address;//空闲区起始地址
float length;//空闲区长度、单位为字节
int flag;//空闲区表登记栏标志，“0”表示空栏目，“1”表示未分配 }used_table[n];//空闲区表
第二，在设计的数据表格基础上设计内存分配。
装入一个作业时，从空闲区表中查找满足作业长度的未分配区，如大于作业，空闲区划
第1页 分成两个分区，一个给作业，一个成为小空闲分区。
实验中内存分配的算法采用“最优适应”算法，即选择一个能满足要求的最小空闲分区。第三，在设计的数据表格基础上设计内存回收问题。内存回收时若相邻有空闲分区则合并空闲区，修改空闲区表。
四、参考程序
#define n 10 //假定系统允许的最大作业数量为n #define m 10 //假定系统允许的空闲区最大为m #define minisize 100 struct { float address;//已分分区起始地址
float length;//已分分区长度、单位为字节
int flag;//已分分区表登记栏标志，“0”表示空栏目，实验中只支持一个字符的作业名
}used_table[n];//已分分区表 struct { float address;//空闲区起始地址
float length;//空闲区长度、单位为字节 int flag;//空闲区表登记栏标志，“0”表示空栏目，“1”表示未分配 }used_table[n];//空闲区表
allocate(J,xk)//采用最优分配算法分配xk大小的空间 char J;float xk;{int i,k;float ad;k=-1;for(i=0;i //找到可用空闲区，开始分配；若空闲区大小与要求分配的空间差小于minisize大小，则空闲区全部分配； //若空闲区大小与要求分配的空间差大于minisize大小，则从空闲区划分一部分分配 if(free_table[k].length-xk<=minisize){free_table[k].flag=0;ad=free_table[k].address; 第2页 xk=free_table[k].length;} else {free_table[k].length=free_table[k].length-xk;ad=free_table[k].address+free_table[k].length;} //修改已分配区表 i=0;while(used_table[i].flag!=0&&i reclaim(J)//回收作业名为J的作业所占的内存空间 char J: {int i,k,j,s,t;float S,L;//寻找已分分区表中对应的登记项 S=0;while((used_table[S].flag!=J||used_table[S].flag==0)&&S used_table[S].flag=0;//取得归还分区的起始地址S和长度L S=used_table[S].address;L=used_table[S].length;j=-1;k=-1;i=0; 第3页 //寻找回收分区的上下邻空闲区，上邻表目K，下邻表目J while(i {free_table[k].length=free_table[j].length+free_table[k].length+L;free_table[j].flag+0;} else //上邻空闲区，下邻非空闲区，与上邻合并 free_table[k].length=free_table[k].length+L;else if(j!=-1)//上邻非空闲区，下邻空闲区，与下邻合并 {free_table[j].address=S;free_table[j].length=free_table[j].length+L;} else { //上下邻均为非空闲区，回收区域直接填入 t=0;//在空闲区表中寻找空栏目 while(free_table[t].flag==1&&t {printf(“内存空闲表没有空间，回收空间失败n”);used_table[S].flag=J;return;} free_table[t].address=s;free_table[t].length=l;free_table[t].flag=1;} return(true);} //内存回收函数结束 main(){ int i,a;float xk;char J;//空闲区表初始化 free_table[0].address=10240; 第4页 free_table[0].length=102400;free_table[0].flag=1;for(i=1;i case 1;//a=1 分配内存空间 printf(“输入作业名J和作业所需长度XK：”);scanf(“%c%c%f”,&j,&xk);allocate(j,xk);//分配内存空间 break;case 2;//a=2 回收内存空间 printf(“输入要回放分区的作业名”);scanf(“%c%c”,&j);reclaim(j);//回收内存空间 break;case 3;//a=3显示内存情况，输出空闲区表和已分分区表 printf(“输出空闲区表：n起始地址 分区长度 标志n”);for(i=0;i C语言有两个基本特点。第一、它比大多数计算机语言都更接近机器语言,因而C程序运行时内存的分配对认识C程序是非常必要的,内存中的地址即指针概念在C程序中起着极其重要的作用。第二、C语言的设计思想是编写小巧清晰、快速灵活的程序[1],C程序因而不是由一个函数构成,而是通过主函数调用其它工具函数或称被调函数来完成。函数调用总是涉及到指针的使用,可以说,如何运用指针是C语言的最重要技能[2,3]。 但是,教学实践中,学生还是经常对指针理解不够透彻[4]。这其中一个重要原因是,C语言被认为是高级语言,教学实践强调程序的功能,而不重视运行时内存的分配和使用。例如,函数中数组和指针都能保存字符串,char*name=”JQK”,char letters []=”JQK”, 但指针变量name只是保存字符串的地址,字符串实际上保存在常量区,而数组letters则是保存了字符串的副本。这些知识对编程有很大影响。前一句,字符串是不能更改的,因为它保存在只读的常量区;后一句,字符串可以修改。C语言学习的困难主要就是这种指针或数组等在内存的占用情况。 为解决指针学习的困难,国内计算机教育近年来提倡一种重视内存的教学方法。这种方法有的是从最低级的机器语言开始,讲解操作码、入口地址、子程序调用等概念,从而自然地引出C语言的概念方法程序[2,5]。有的主张讲清堆和栈的特性[6]。有的强调用printf函数打印出变量地址[7]。这些方法对学习指针变量等起到了很好的作用。但是,它们在学习C语言的核心技术中的作用还需进一步研究。这些核心技术最令人困惑的地方是工具函数如何改变主函数的变量、数据存储在内存中不同区域的特性和在函数调用中如何使用函数指针等问题。 1 函数调用过程 C语言的风格是主函数大量调用其它函数,即使最简单的输出指令printf也是调用C标准库中的一个函数,没有其它函数,主函数几乎不能做任何事情。为完成特定功能,主函数不仅需要调用C标准库中的函数,还需要调用自定义函数来操作主函数内部的变量或数据结构。这里令初学者疑惑的是,被调函数如何能够操作主函数的变量、数组或链接等数据结构。这就需要了解程序执行的进程。 当一个可执行程序运行时,操作系统会把内存划分为几个区域,并把程序的不同部分装入不同区域运行。进程的内存空间分布可以模型化地表示如表一[1,6]。 整个内存可理想化为一个很长的字节序列,被分为几个不同性质的区域,依次是:栈、堆、全局区和具有只读性质的常量区、代码区。内存中每个字节有一个编号,它就是内存单元的地址。栈的地址最大、常量区和代码区的地址最小。程序运行时,全局变量被装入到全局区;函数的局部变量被装入到栈中;运行时动态申请的空间存放在堆中。运行中更重要的特性是,每个函数被存放在栈中的不同区域,每个函数的局部变量都被保存在自己函数的区域内,所以,不同函数中可使用相同名字的局部变量。当函数调用结束后,其占用空间被释放,其中的局部变量即消亡。 函数调用过程是操作系统把控制流从内存中一个函数占用区跳转到另一个函数区,同时把一个区域内的局部变量的值传递到另一个区域的局部变量。控制流接着在被调函数区执行。被调函数结束后,控制流返回到函数调用点。 这样,被调函数的运行结果对主调函数的影响有两种方式。第一、被调函数直接改变主调函数内的变量、数据结构的字段等。第二、被调函数把运行结果的值返回给主调函数。 2 被调函数如何改变主函数的局部变量 函数调用时,被调函数是在与主调函数不同的一块内存中运行的,其形参就存在于这块内存区域。操作系统会把控制流从主调函数区转到被调函数区,并把主调函数区内的实参数值传递给被调函数区的形参变量。参数传递是单向的值传递,只能从实参传给形参,不能从形参反传给实参[6]。随着被调函数结束,其在栈中的空间被释放,形参也无法再访问。由于两函数位于不同空间,被调函数改变其形参数值是不会对主调函数产生影响的。 但是,C程序的结构特点是主函数调用其它函数完成不同功能,那么,如何通过调用被调函数改变主函数的变量值呢?有两种方法。第一、让被调函数直接操作主函数,方法就是把实参变量或链表的地址传给被调函数的指针形参。因为被调函数可以通过* 运算符来操作指针形参地址内的变量,而这个地址是主函数实参变量的地址,所以,被调函数对形参变量的任何改变都是对栈中主函数区变量的操作,即改变了主函数实参变量的数值。这是一个函数操作另一个函数内变量的重要机制,也是所谓传址与传值的区别。可以说,学生对C语言的困惑很大一部分是对主函数和被调函数在内存中不同区域的关系没有清晰的概念。 第二种方法,虽然参数传递是从实参到形参,但是,被调函数可以把改变后的变量值或结构实例返回给主调函数。通过在主调函数里把返回值显性赋予给主调函数的变量或结构实例,主调函数就利用被调函数改变了自己的变量。 下面程序例示这两方法,让函数happybirthday改变主函数内学生结构的实例Fay的年龄字段。初学者常常不明白,在程序一中为什么happybirthday函数将形参变量stu的年龄字段增加了,可是主函数的结构实例Fay的年龄却没有变。结果显示,函数happybirthday中的年龄变为20,但是主函数的实例Fay的年龄没有变,还是19。 内存分配模型可以帮助初学者理解程序的函数调用。Main函数执行时,操作系统在栈中为它分配一块空间即栈帧,用来存放它的结构实例Fay。当执行到happybirthday函数时,又为happybirthday函数在栈中分配另一块栈帧,用于存放形参stu的每个字段,然后,进行参数传递,主函数的实例Fay被传给形参stu。代码happybirthday(Fay) 等价于stud stu=Fay,操作系统会把Fay的一个全新副本复制到stu。所以,在函数happybirthday内存区域内的结构实例stu是一个复制的Fay的副本,而不是实例Fay。happybirthday只是在栈中自己的空间改变了实例stu的年龄,main函数所在内存区域没有受到任何影响,所以实例Fay的年龄没有被改变,如图一所示。 为使happybirthday函数改变主函数内实例Fay的年龄,可以采用前述两种方法。第一、让happybirthday直接操作主函数中的结构实例。如前所述,操作另一个函数的机制是,把主函数中实例Fay的地址传给happybirthday中的指针形参stu。由于指针stu指向主函数内的结构实例Fay的地址,通过代码(*stu).age或stu->age,happybirthday函数操作的是主函数的实例Fay的年龄字段age,所以程序二中,Fay的年龄被改变,如图二。 因为参数单向传递,有些初学者会认为,改变主函数的变量,只有传址才行,传值是不行的。这其实是不对的。改变主函数的变量值还有第二种方法,即通过传值让被调函数改变主调函数内的变量。但是,这第二种方法需要显性地把被调函数内改变的结果(数值或实例)返回给主函数,而主函数必须把返回的变量值或结构实例显性地赋予自己的局部变量或实例。 如程序三所示,程序也可以不用传址,而改为传值,即把实例Fay传给形参stu。只要把被调函数的返回类型改为stud,就可以让被调函数把改变的结果传回给主函数的实例Fay,从而通过返回和赋值两种显性方式让被调函数改变主函数的变量,效果与传址一样。 3 数据存放位置 被调函数改变主函数变量的问题还有一个令人困惑的方面:被调函数中的变量是存放在栈上还是堆上。栈和堆特性不同。栈在函数结束后即被释放,里面的变量、实例即消亡,之后,主调函数再无法访问被调函数的形参。而用malloc函数动态申请的空间位于堆上,系统不会自动释放,除非用free函数显性释放。因此在函数调用结束后,主函数还可以继续访问。 堆与栈的区别可以在下面程序中利用内存分配模型得到进一步解释。程序取自[1],目的是记录一次跨岛之旅。行程包括一系列航班,从一个岛到另一个岛。程序建立一个结构island,包括岛名,营业时间和指向下一个岛的指针。任务是从键盘输入岛屿信息,然后把信息输出。由于需要增加新的岛屿信息,增加的数量又不确定,所以,需要动态地创建链表结构。 在输入两个岛屿名称创建实例后,主函数调用display函数显示岛屿信息,但是第一次输入的岛屿不见了,两次输出结果都是第二次输入的岛屿信息。为什么第一次输入的岛屿没有显示,而变成了第二个岛屿。 不正确程序: 原因在于,在create函数中,代码i->name=name表示,malloc为链表实例获取空间后,实例的name字段初始化为字符数组变量name,即数组name的首地址。换句话说,每个岛屿实例中的名字字段name,并没有保存输入的名字字符串,只是保存了主函数name数组的首地址。当输入第二个岛屿信息后,malloc函数在堆中获取另一个空间,保存另一个链表实例,但这个新实例的名字字段,同样没有保存输入的字符串,两次创建的实例的名字字段都指向name数组的首地址。如果name数组的内容改变了,不同的实例中的名字字段name也都将被更新。当调用display函数显示每个岛屿时,所有岛屿的名字字段都是name地址中的内容,即最新输入的岛屿名字。 如何能保持第一个岛屿的信息不被改变呢?因为保存在堆上的数据是不会改变的,除非使用free函数将这块内存释放,所以,可以在堆上的实例里放上名字字段的字符串,这样它就一直不变。解决的办法就是在调用malloc函数在堆上创建实例后,把输入的名字字符串复制到堆上的某个地址。这可以调用C语言中的字符串复制函数strdup来完成。这样修改代码后,主函数再调用display函数就能显示每次输入的岛屿信息了: 正确程序: 4 函数指针与函数调用 C程序的特点是主函数结构简洁清晰,这要求把主函数完成的复杂任务分解为多个小任务,每个小任务再由一个对应功能的工具函数去完成[1]。如果任务复杂,这种把任务分派出去的过程还可以层叠:主函数调用一个函数,这个函数再调用另一个函数。这种层叠调用常常给学生带来极大的困惑,学生往往想用一个函数完成一个复杂任务。 例如,编写一个程序完成性格匹配的任务,即从多个不同特征的人中找出符合期望的人并显示出来。不同的人可能有不同的爱好,有的人喜欢体育或健身;有的人喜欢美食或戏剧等等。程序先用数组保存不同特征的人,再调用函数从中搜索出有特定爱好的人,如喜欢美食或戏剧。但是,初学者的想法常常是用一个主函数完成,这样主函数就会很庞大、混乱。这不符合C语言结构小巧清晰的风格。更好的方法是把搜索任务分解,如分解成一个一般的搜索任务,由一个函数find完成,其形参为指针。这个函数再去调用搜索具体特征的函数,如搜索喜欢体育或健身的函数sports_or_workout或搜索喜欢艺术、戏剧或美食的函数arts_theater_or_dining。这样,主函数结构就非常清晰,如下所示。与前两节的函数调用不同的是,主函数不是把自己的变量或变量地址传给被调函数find,而是把其它函数的地址即函数指针传给这个一般的搜索函数find(int (*match)(char*)) 的形参,由这个一般搜索函数操作具体的搜索函数,找到符合条件的人。 可见,函数指针允许把函数层叠调用。把被调函数名称即函数指针传给find函数的重要好处是,你可以写出搜索各种条件的具体函数,让find函数反复调用,如可以增加一个搜索不吸烟且喜欢戏剧的函数让find调用。这样的程序虽然结构小巧,但功能非常强大。函数指针因而是C语言最强大的特性之一。 5 结语 传统上强调C语言是高级语言的观点忽略了C程序内存分配的过程。这样,学生不容易意识到把数据保存在内存的不同区域的特性,也难以理清如何让一个函数操作另一个函数中的变量、数组、结构、链表等数据结构以及如何传递函数指针等问题。朱立华、俞琼[2],谌卫东[6]等提出的通过认识计算机底层操作来掌握C语言的方法,开创了深入学习C语言的新思路。基于此思路的内存分配模型能够系统阐述函数调用等涉及指针使用的机制,对C程序的运行具有较强的解释力。 使用内存分配模型来学习C语言因而能够帮助学生克服学习的困难,对C程序的结构、功能和运行形成清晰而深刻的认识,这样掌握C语言的一些主要技能就会相对容易。因为内存分配模型告诉我们,主函数和被调函数是在内存中不同区域运行,所以,要想让被调函数操作主函数,需要使用两种方法:第一,把主函数变量的地址或其它工具函数的函数指针传给被调函数,这样被调函数就可以通过* 和-> 运算符或函数指针来直接操作主函数内的变量或其它工具函数;第二,让被调函数把改变后的数值或实例传回到主调函数,并显性赋予主调函数的变量。内存分配模型因而能够帮助学生更快地完成学习之旅,即一开始总是把所有的代码都放到一个函数里,随着水平的提高,他们把代码分别放到几个函数里。在水平继续提高后,他们最终学会如何用几个文件来构造一个程序。 摘要：指针是C语言最强大的特征之一,可以用来构建高效的程序。为理解指针在函数调用中的作用,需要确定内存分配。文章讨论的内存分配模型解释了如何由其它函数修改数据、如何把函数作为参数传递等问题。 关键词：指针,数组,函数指针,内存分配 参考文献 [1]Griffiths,D&Grffiths,D.深入浅出C语言(影印版)[M].南京:东南大学出版社,2013:267-324. [2]朱立华,俞琼.C语言教材建设的研究与实践[J].计算机教育,2009(13):151-153. [3]赵忠孝、杨亚蕾.对C语言指针教学问题的探究[J].计算机教育,2009(19):72-74. [4]于福生,刘玉铭,王加银.C语言课程中指针内容体系设置的改革尝试[J].计算机教育,2013(04):22-24. [5]朱立华.C语言程序设计[M].北京:人民邮电出版社,2009. [6]谌卫军.C程序设计课程中的堆和栈[J].计算机教育,2015(05):98-102. 关键词：链表,连续性,内存地址 在数据结构中, 链式存储结构是用内存中一组任意的存储单元存储线性表的数据元素, 这组存储单元可以是连续的, 也可以是不连续的[1]。数据元素是以结点的形式存储在链表中, 由链式存储结构的定义可知结点与结点之间的地址可以是连续的, 也可以是不连续的, 但结点内部成员之间是否连续呢, 本文就此问题进行分析。 1 链表中结点的内存地址分配 1.1 链表中结点的内部结构 结点的内部存储结构是如何分配的呢, 以下面程序为例分析一下结点内部成员之间地址分配问题。 运行结果如下: 各个成员长度分别为: 结构体长度:24 通过结果可发现结构体类型变量L的成员所占内存的大小为10+4+1+4=19, 结构体长度结果为:24, 这两个值不一致, 为什么产生这样的结果呢, 这就关系到结构体变量成员在内存中是如何分布的, 成员之间是连续的还是分散的?这些问题与具体的编程语言的编译器的特性相关, 编译器为了优化CPU访问内存的效率, 在生成结构体成员的起始地址时遵循着某种特定的规则, 这就是所谓的结构体成员“对齐”。下面在Windows XP (32位) 下用VC++6.0编译器来详细讨论结构体成员的“对齐”问题。 为了优化CPU的访问内存的效率, 程序语言的编译器在做变量的存储分配时就进行了分配优化处理, 优化规则大致如下:对于n字节的元素 (n=1, 2, 4, 8, 16) 它的首地址能被n整除, 这种原则称为“对齐”。对于结构体来说, 结构体的成员在内存中顺序存放, 所占内存地址依次增高, 第一个成员处于低地址处, 最后一个成员处于高地址处, 但结构体成员的分配不一定是连续的, 编译器会对其成员变量依据“对齐”原则进行处理。对待每个成员类似于对待单个n字节的元素一样, 依次为每个元素找一个适合的首地址, 使其符合上述“对齐”原则。通常编译器可以设置一个对齐参数n, VC++6.0中结构体的每个成员初建对齐参数N通常是这样计算得到的, N=min (sizeof (该成员类型) , n) (n为VC++6.0中可设置的值, 一般取n= (1, 2, 4, 8, 16) 。成员的内存分配规律是这样的:从结构体的首地址开始向后依次为每个成员寻找第一个满足条件的首地址x, 该条件是x%N=0, 并且整个结构体的长度必须为每个成员所使用的对齐参数中最大的那个值的最小整数倍, 不够就被填空字节[2]。结构体中所有成员的对齐参数N的最大值称为结构体的对齐参数。当结构体成员为数组时, 并不是将整个数组当成一个成员来对待, 而是将数组的每个元素当一个成员来分配, 其它分配规则不变。 VC++6.0中n默认为8byte, 可以修改这个设定的对齐参数, 用程序控制方式, 采用指令:#pragma pack (xx) 控制。如: #pragma pack (1) //1字节对齐 #pragma pack (4) //4字节对齐 #pragma pack (16) //16字节对齐 对于上面程序的结果做以下分析: (1) 当对齐参数n设置为1byte, 即#pragma pack (1) 时, 运行结果如下: 各个成员长度分别为: 结构体长度:19 其内存分配如图1所示: 结构体变量L的各成员地址分配分析如下, 由于此时N=min (sizeof (成员) , 1) , 取N=1, 由于1可以整除任何整数, 所以各个成员依次分配, 没有间隔, 如上图所示。由于所有成员的N值的最大值为1, 于是, 该结构体的对齐参数就是1byte, 所以整个结构体长度为1byte的整数倍, 即取19byte。 (2) 当对齐参数n设置为2byte, 即#pragma pack (2) 时, 运行结果如下: 各个成员长度分别为: 结构体长度:20 其内存分配如图2所示: 结构体变量L的各成员地址分配分析如下, L.num起始于一个2的整数倍的地址12FF6CH, 接下来要在L.num之后分配L.name, L.name为字符型数组, 对于它的每个数组元素都是char类型, 由于char类型为1字节, 取N=min (1, 2) =1, 所以取1字节对齐长度, 分配一个起始于1的整数倍的首地址, L.name分配10个字节, 所以取12FF6CH+4=12FF70H开始为L.name分配连续10个字节, 接着是L.sex, 同理, char所占字节数为1字节, 由于N=min (1, 2) =1, 所以取1字节对齐长度, 所以紧接L.name向后找第一个能被1整除的地址, 所以取12FF70H+10=12FF7AH开始为L.sex分配一个字节, 紧接着是next成员, 4字节, 由于N=min (4, 2) =2, 所以取2字节对齐长度, 所以L.sex后的一个字节补空, 紧接在L.sex向后找第一个能被2整除的地址, 所以取12FF7AH+2=12FF7CH开始为L.next分配4个字节。由于所有成员的N值的最大值为2, 于是, 该结构体的对齐参数就是2byte, 所以整个结构体长度为2byte的整数倍, 即取20byte. (3) 当对齐参数n设置为4byte, 即#pragma pack (4) 时, 运行结果如下: 各个成员长度分别为: 结构体长度:20 其内存分配如图3所示: 结构体变量L的各成员地址分配分析如下, L.num分配一个起始于4的整数倍的地址12FF6CH, L.num分配4个字节, 接下来要在L.num之后分配L.name, 由于L.name为字符型数组, 对于它的每个数组元素都是char类型, 由于char类型为1字节, 取N= (1, 4) =1, 所以取1字节对齐长度, 所以直接从L.num向后找第一个能被1整除的地址, 所以取12FF6CH+4=12FF70H开始为L.name分配连续10个字节, 接着是L.sex, 同理, char所占字节数为1字节, 由于N=min (1, 4) =1, 所以取1字节对齐长度, 所以紧接L.name向后找第一个能被1整除的地址, 所以取12FF70H+10=12FF7AH开始为L.sex分配一个字节, 紧接着是next成员, 4字节, 由于N=min (4, 4) =4, 所以取4字节对齐长度, 所以紧接在L.score向后找第一个能被4整除的地址, 所以取12FF7AH+2=12FF7CH开始为L.next分配4个字节中间12FF7AH地址单元补空。由于所有成员的N值的最大值为4, 于是, 该结构体的对齐参数就是4byte, 所以整个结构体长度为4byte的整数倍, 即取20byte。 (4) 当对齐参数n设置为8byte, 即#pragma pack (8) 时, 运行结果如下: 各个成员长度分别为: 结构体长度:20 其内存分配如图4所示: 结构体变量L的各成员地址分配分析如下, L.num分配一个起始于8的整数倍的地址12FF6CH, L.num分配4个字节, 接下来要在L.num之后分配L.name, 由于L.name为字符型数组, 对于它的每个数组元素都是char类型, 由于char类型为1字节, 取N= (1, 8) =1, 所以取1字节对齐长度, 所以直接从L.num向后找第一个能被1整除的地址, 所以取12FF6CH+4=12FF70H开始为L.name分配连续10个字节, 接着是L.sex, 同理, 紧接L.name向后找第一个能被1整除的地址, 所以取12FF70H+10=12FF7AH开始为L.sex分配一个字节, , 紧接着是next成员, 4字节, 由于N=min (4, 8) =4, 所以取4字节对齐长度, 所以紧接在L.score向后找第一个能被4整除的地址, 所以取1245048+4=1245052开始为L.next分配4个字节, 中间12FF7BH地址单元补空。由于所有成员的N值的最大值为4, 于是, 该结构体的对齐参数就是4byte, 所以整个结构体长度为4byte的整数倍, 即取20byte。 (5) 当对齐参数n设置为16byte时, 运行结果如下: 各个成员长度分别为: 结构体长度:20 其内存分配如图5所示。 结构体变量m的各成员地址分配分析如下, L.num分配一个起始于16的整数倍的地址12FF6CH, L.num分配4个字节, 接下来要在L.num之后分配L.name, 由于L.name为字符型数组, 对于它的每个数组元素都是char类型, 由于char类型为1字节, 取N= (1, 16) =1, 所以取1字节对齐长度, 所以直接从L.num向后找第一个能被1整除的地址, 所以取12FF6CH+4=12FF70H开始为L.name分配连续10个字节, 接着是L.sex, 同理, char所占字节数为1字节, 所以紧接L.name向后找第一个能被1整除的地址, 所以取12FF70H+10=12FF7AH开始为L.sex分配一个字节, 紧接着是next成员, 4字节, 由于N=min (4, 16) =4, 所以取4字节对齐长度, 所以紧接在L.score向后找第一个能被4整除的地址, 所以取12FF7AH+2=12FF7C开始为L.next分配4个字节, 中间12FF7BH地址单元补空。由于所有成员的N值的最大值为4, 于是, 该结构体的对齐参数就是4byte, 所以整个结构体长度为4byte的整数倍, 即取20byte。 1.2 链表中结点间的内存地址关系 如下面程序所示, 主要描述结点之间的地址关系。 程序运行结果如下所示: 每个结点的长度为:24 第1个结点的地址为:431DF0H 第2个结点的地址为:431DA0H 第3个结点的地址为:431D50H 第4个结点的地址为:431D00H 通过对程序中#pragma pack (n) 中n值取 (1, 2, 4, 8, 16) 不同的值, 通过验证可知, 不管n取何值, 结点的地址都是不连续分配的, 且结点之间的地址值呈递减分配。 2 合理安排结点内部成员顺序, 提高访问内存效率 内存对齐是操作系统为了快速访问内存而采取的一种策略, 操作系统在访问内存时, 每次读取一定的长度 (这个长度就是操作系统的默认对齐系数, 或者是默认对齐系数的整数倍) 。如果没有内存对齐, 为了读取一个变量时, 可能会产生总线的二次访问。下面程序假定在设置内存对齐方式的情况下, 如何保证读取内存数据时仅访问一次且结点占用内存空间更少一些。 通过运行程序, 可知结构体长度为16byte, 将程序中结点的成员顺序改变如下所示: 或改为 通过运行程序可知, 上面两种成员顺序结构体长度均为12字节, 通过不断修改成员的顺序以及对齐字节数 (此文不再一一罗列) , 可知, 在定义结构体时, 既要考虑内存对齐问题所带来的影响, 又要合理安排结构体成员顺序, 可使得操作系统快速访问内存且使程序所占内存空间尽可能的减少。 3 结语 通过对所有类型链表中结点内存地址分配连续性问题的分析与验证, 可知, 链表结点的内部成员之间不一定连续, 与对齐参数的设置有一定的关系, 成员之间的地址是按成员先后顺序相对递增分配的;结点之间是不连续的, 结点之间的地址按结点的按点的先后次序相对递减分配的。为了提高操作系统的访问速度且使程序占用内存尽可能地少, 需要合理地设置对齐参数、合理安排结构体中成员的先后次序。 参考文献 [1]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版社, 2001 嵌入式系统中最基本的内存管理方案有两种———静态分配和动态分配。一般说来，嵌入式系统总是两种方案的组合。μC/OS-II[1]也不例外，对一些数据结构，如内存控制块，任务控制块等采用静态内存分配，而其它的使用动态内存分配。纯粹的静态内存分配一般只使用在不计成本来保证严格实时性的场合，但是静态内存分配容易使系统失去灵活性。动态内存管理机制是嵌入式系统中的难点，是保证嵌入式系统实时性的一个重要方面，它必须满足以下三个特性[2,3,4,5]： 快速性：为保证系统实时性，要求简单、快速地分配内存。 可靠性：内存分配的请求必须得到满足，内存分配失败可能带来灾难性的后果。嵌入式系统应用的环境千变万化，其中有一些应用对可靠性要求极高，如航天等。 高效性：内存是有限、昂贵的资源，要尽可能少的浪费。 针对以上三个基本特性，市场上主流的嵌入式操作系统，如VxWorks、嵌入式Linux等均提出了一套有效的解决方案。本文针对开源的μC/OS-II，分析其内存管理是否有效地支持上述3个基本特性，讨论其存在的问题，并给出μC/OS-II内存管理的解决方案。 其次，μC/OS-II的内存管理接口很不友好，与众多程序员熟悉Windows接口相异较大。应用程序申请内存块时必须知道内存分区地址以及内存块的大小，并且在使用时不能超过其大小。在应用程序释放该内存块时，必须重新放回到它所属的内存分区中。这些问题都要求程序员非常清楚内存使用情况。 2 μC/OS-II的内存管理策略及问题 2.1 μC/OS-II内存管理简介 μC/OS-II中的内存管理模块把动态管理的内存分成多个不同大小的内存分区,每一个内存分区又划分成一定数量具有相同尺寸的内存块。在具体的μC/OS-II中，动态内存管理由源文件OS_MEM.c实现,总共只包含5个函数OSMenInit,OSMemCreate,OS-MemGet,OSMemPut与OSMemQuery,约100行代码,十分精炼。正是由于其精炼,μC/OS-II的动态内存管理提供的功能十分有限。本文主要讨论OSMemCreate,OSMemGet,OSMemPut这三个主要的功能函数，其作用分别是创建内存分区、获取内存块和回收内存块。 2.2 具体实现过程及存在的问题 μC/OS-II使用内存控制块OS_MEM[1]来跟踪每一个内存分区。μC/OS-II在启动时调用OSMenInit对内存管理进行初始化，建立一个空闲内存控制块链表，链表长度由系统决定，但至少要大于2。下面介绍内存管理的三个主要的功能函数： (1)OS_MEM*OSMemCreate(void*addr,INT32U nblks,INT32U blksize,INT8U*err); (2)Void*OSMemGet(OS_MEM*pmem,INT8U*err); (3)INT8U OSMemPut(OS_MEM*pmem,void*pblk); 第一个函数OSMemCreate()的功能是创建一个内存分区。共有四个参数：内存分区起始地址、内存块总数、每个内存块字节数、一个指向出错信息代码的指针。如果创建成功，则返回一个指向内存控制块的指针，否则返回NULL。 第二个函数OSMemGet()的功能是分配一个内存块。它从已经建立的内存分区中申请一个内存块，函数参数pmem是指向特定内存分区的指针，该指针是由OSMemCreat()返回的。此函数实现存在以下不足之处： (1)应用程序必须知道特定内存分区的内存块大小，并且在使用时不能超过其容量。一般而言，应用程序在需要使用内存时，只需告诉操作系统需要用多大的一块内存，而不用去关心内核是怎么管理内存、有哪些内存分区、每个内存分区有多大以及相应的起始地址这些问题。 (2)OSMemGet()无法知道参数pmem是否一定指向了一个合法的内存分区，它只能判断它是否是空指针，这需要程序员清楚内存使用情况。 (3)未提供向某一内存分区申请内存失败后如何向下一个内存分区申请内存的方法,而需要程序员自己提供,加重了程序员负担的同时更是降低了程序的可靠性与稳定性。 第三个函数OSMemPut()的功能是回收一个内存块。当应用程序不再使用某一个内存块时，必须及时把它释放，并放回到相应的内存分区中。存在不足之处在于：OSMemPut()并不知道该内存块是属于哪个内存分区的，这要求应用程序保证把内存块释放到合理的内存分区中。 3 μC/OS-II内存管理改进策略 经上述2.2小节的分析，了解到μC/OS-II内存管理的不足之处。本节针对以上缺点提出改进方案，该方案有效地避免了上述问题。 3.1 改进思路 将已经建立的内存分区按照内存块的大小从小到大用链表链接起来，当应用程序申请一个内存块时，只需指定要申请的内存块大小，余下的工作交由内核来完成。当应用程序要释放内存块时，不需要再考虑放回到哪个内存分区中，只需给出要释放的内存块即可。具体实现过程如下： 1)在内存控制块的数据结构中增加一个数据域：void*OSMemUsedList，它用来链接已经建立好的内存分区的控制块。 2)修改后的内存管理的三个主要功能函数： (1)void*OSMemCreate(void*addr,INT32U nblks,INT32U blksize,INT8U*err); (2)void*OSMemGet(INT32 size); (3)INT8U OSMemPut(void*pblk); 3.2 具体改进措施 1)对OSMemCreate()的改进：在函数体的最后用链表OSMemUsedList将建立的内存分区控制块链接起来，返回值为空。 2)对OSMemGet()的改进：修改从指定内存分区中获得内存块，而按最佳适应算法从链表OSMemUsedList中找到适合的内存分区，从中分配一个内存块，若该内存分区没有空闲内存块可分配，不再简单的返回分配失败，而是顺着链表寻找下一可用的内存分区的内存块。这样，应用程序总能分配到所需的内存块，而且由于内存控制块数的确定性，应用程序能在有限的时间内分配到内存。此改进方案增加了内存分配的可靠性。 3)对OSMemPut()的改进：函数参数只有指向将被释放的内存块的指针，遍历链表OSMemUsedList，找到内存块所属的内存分区，将内存块放回即可。 改进后的内存组织结构如图1所示： 4 性能分析 针对μC/OS-II的内存管理机制，制定一具有代表性的测试用例来分析μC/OS-II系统在改进前后的可靠性和内存块的分配速度。实验环境为华邦的W90P710,W90P710内核采用ARMTDMI，该内核不支持MMU，这点特性适合μC/OS-II这样的操作系统。 假设在内存初始化时建立了三个内存分区，大小分别为32K、80K和100K。此用例中的任务task在运行过程中每隔100个系统时钟周期申请80K大小的内存块，改进前的μC/OS-II在task循环10次后，就不会再分配到内存块，返回分配失败。而改进后的μC/OS-II可以在80K大小的内存分区分配完以后，可以在100K大小的内存分区中得到满足，从而提高了内存分配的可靠性。 虽然改进后的μC/OS-II在内存分配速度上不及改进前的μC/OS-II，在最坏的情况下，系统要遍历整个OSMemUsedList才能分配到内存，但是在内存分区数n一定的情况下，内存分配时间是可以预见的，时间复杂度为O(n)。该方案在内存分配的请求必须得到满足、内存分配失败可能带来灾难性后果的场合有很大的应用价值。 测试用例伪代码如下： 5 结论 本文的创新点在于针对μC/OS-II内存管理可靠性不高，函数接口不友好的缺点，对其进行了改进，改进后的方案使应用程序对内存块的申请能更大可能的得到满足，这在可靠性要求高的场合有很大的应用价值。同时改善了内存管理的功能函数接口，增强了易用性和用户亲和力，并减少了内存分配出错率。通过以上方法，希望使μC/OS-II能够在更多高可靠性的环境中得到应用。 参考文献 [1]Labrosse J.嵌入式实时操作系统μC/OS-II[M].邵贝贝,译.北京:北京航空航天大学出版社,2003:270-283. [2]田令平,嵌入式操作系统内存管理研究[J].电脑知识与技术,2006(11):169-171. [3]梁乘铭,韩坚华等,μC/OS-II中动态内存管理方案的改进与实现[J].微计算机信息,2008,2(2):44-46. [4]谢银桥,李广军,基于μC/OS-II的一种嵌入式系统内存管理方案[J].福建电脑,2006(7).内存分配在C指针教学中的作用 第5篇
链表结点的内存分配连续性问题研究 第6篇
动态内存分配 第7篇