论文部分内容阅读
摘要：笔者在开发一款基于Linux的网络服务器时，被要求设计一种高效的、并且碎片率很低的内存分配方法。为此，先对当前流行的动态存储管理方法进行了研究分析，这些方法由于各种各样的原因，不能直接应用于Linux网络服务器中。为此，本文中引入了一个全新的O(1)分配算法，形成了一个符合现实需求、高效的、并且内存碎片率很低的用户内存分配方案。
关键词：Linux；内存分配；网络服务器；响应时间
中图分类号：TP393.08文献标识码：A文章编号：1007-9599 (2013) 05-0000-03
1概述
笔者在开发一款基于Linux的网络服务器时，被要求设计一种高效的、并且碎片率很低的内存分配方法。为此，先对当前流行的动态存储管理方法进行了研究分析，例如：顺序搜索，buddy算法，分类搜索，索引搜索，位图搜索等。这些方法要么效率不高，时间复杂度是O(n)或者O(logn)；要么设计复杂、实现困难，而服务器要求7*24小时连续不间断的提供服务，这种复杂的设计在服务器运行中容易出错；要么会产生较高的内存碎片率，服务器被要求长年累月的运转，较高的内存碎片率很影响服务器的效率。因此，不能将这些内存分配方法直接应用于Linux网络服务器的开发中。笔者在Linux内核代码的研究中，发现在内核代码的某个模块中存在一种O(1)分配算法。因此，笔者在Linux网络服务器的研发中，引入了这个O(1)分配算法的思想，并且融入了新的设计，形成了一个符合现实需求、高效的、并且内存碎片率很低的用户内存分配方案。
2内存分配方法设计
2.1需求分析
Linux网络服务器是整个项目系统的一部分，它位于上位机和终端设备之间。这个系统对服务器的内存分配方法有具体的要求：
（1）提高实时性。分配和释放内存都必须在一个确定的时间内完成。
（2）减少内存碎片。服务器程序需要7*24小时连续不间断的提供服务，产生过多的内存碎片会影响系统的性能。
（3）分配内存的大小固定。本系统处理的网络数据都是介于90到110字节之间的长度。由于TCP链路众多，并且每条链路的业务量很大，因此在服务器上这些数据包的分配和释放是非常频繁的。
2.2方案设计之数据结构
在Linux服务器程序初始化的时候，一次申请一大块内存，应用程序再把这块内存分成多份等大的基本单元，每个单元可以存放一个数据包。另外，在服务器运行中，如果系统需要，可以再一次或者多次分配足够的大量的内存，将这些内存块格式化成设计的管理格局。在应用程序申请小块内存时，就从上一步的管理格局中分配一个基本单元。
在这个方案中有三个重要的数据结构，其数据成员以及含义见表1。
数据结构（结构体） 数据成员 含义
System name 该system结构体的名字
fulllists Dentry的链表，其中每个dentry的基本单元都已经分配完毕
emputylists_head Dentry的链表，其中每个dentry都有部分内存空闲没有分配
emputylists_rear 指向上一项dentry链表的尾部
totalcount 该system中基本单元的总数
totalused 该system中已经分配的基本单元的个数
fixedunit 该system中基本单元的有效数据的大小
Dentry count 该dentry管理的基本单元的总数
free 该dentry中第一个空闲基本单元的编号
used 该dentry中已经分配的基本单元的个数
system 该dentry隸属的system
start 该dentry管理的第一个基本单元的地址
pre 用于形成dentry的链表，pre指向前一个dentry
next 用于形成dentry的链表，next指向后一个dentry
Item id 基本单元的编号
nextid 下一个基本单元的编号
dentry 该基本单元隶属的dentry
used 该基本单元是否已经被分配
data 该基本单元管理的有效内存的起始地址，该有效内存位于每个item之后
表1核心数据结构以及含义
2.3方案设计之算法介绍
在介绍整个方案之前，先说明一下单个dentry是如何管理内存的。在创建某个dentry时，将dentry和它管理的item，初始化成链表，如图1。最左侧的圆圈表示dentry中的free成员。右侧的8个矩形表示8个item。矩形中的数字表示item中的nextid值。矩形下方的数字表示item的编号。
图1初始化dentry
应用程序申请一个item后，dentry的布局如图2所示。
图2申请一个item后的dentry布局
其后，又连续申请了两个item，布局如图3所示。
图3申请三个item后的dentry布局
接着，释放编号为1的item，其布局如图4所示。
图4释放编号为1的item后的布局
最后再释放一个编号为2的item，其布局如图5所示。
图5释放编号为2的item后的布局
其上本文分析了单个dentry是如何分配和释放基本单元item的，下文将对网络服务器中内存分配机制的整个原理进行设计说明。其中，下文中用emputylists表示emputylists_head和emputylists_rear构成的链表。
（1）在网络服务器初始化过程中，创建一个system结构、一个dentry结构、以及这个dentry所管理的若干个基本单元和有效内存区域。每个system结构规定了它所支持的基本单元中有效内存的最大值，在这个项目中设置成120字节。并且把这个dentry列入fulllists链表。
（2）服务器申请小块内存时，直接从emputylists指向的第一个dentry中分配，此时的分配机制请见前面的介绍。分配内存的算法是先找到将要分配的item，然后返回其后的有效内存的起始地址了。如果分配后发现这个dentry的内存都使用了，则将该dentry放入fulllists链表中。
如果在分配时发现emputylists已经成为空链表，则再创建一个dentry以及它管理的若干item。并将新建的dentry加入到emputylists链表中。
（3）应用程序释放内存时，将item归还给对应的dentry，如果该dentry在fulllists链表中，则将它列入emputylists的尾部。释放内存的函数先根据地址参数找到对应的item结构体，然后将这个item归还给dentry。
（4）经过长期运行，系统中会形成如图6所示的布局。
图6系统布局
3试验结果
3.1试验程序设计
将本文设计的内存分配方法和C语言传统的malloc/free机制进行比较。
（1）首先根据输入参数，随机的计算出如图7所示的申请和释放的操作序列。
图7申请和释放的序列
其中，alloc_free用于保存申请后的内存地址，在第一步中不做任何设置。而flag_arr用于保存申请和释放的序列，其中，+1表示申请内存，并把申请到得内存地址保存在allc_arr中；-1表示释放内存，释放哪块内存由free_arr指明。free_arr中保存的是alloc_arr的下标号。
（2）再用C语言中的malloc/free函数实现上一步中产生的操作序列。用本文设计的方法同样实现以上的序列。比较这二者响应时间的不同。
3.2试验结果
测试是在Pentium(R)Dual-Core CPU、1024M内存、CentOS5.4操作系统的机器上进行的。笔者没有采用ptrace跟踪程序实际使用的指令数，而是使用Linux提供的gettimeofday函数计算时间差，笔者认为后者更能准确的反应响应时间。并且为了避免进程调度对测试产生影响，测试初始化时将测试程序置为实时进程。本文设计的方法，不仅可以避免内存泄露，而且由于它是O(1)算法，所以响应时间是能够得到保障的。试验中每次申请和释放都是100字节，以下是多次的试验情况，详情见表1。图8中展示的是响应时间的比较，本文设计的方法从响应时间上优于malloc/free函数。
申请次数 释放次数 C语言malloc/free所需时间（按微妙计算） 本文设计方案所需时间（按微妙计算） 效率提高幅度
100 0 96 9 91%
105 8 92%
97 8 92%
1000 0 297 78 74%
367 81 78%
247 77 69%
10000 0 2165 843 61%
2094 763 64%
2046 770 62%
100000 0 22222 7896 64%
23291 8460 64%
20571 7802 62%
100 100 179 8 96%
113 8 93%
171 8 95%
1000 1000 210 68 68%
245 65 73%
311 70 77%
10000 10000 1216 622 49%
1128 660 41%
1169 680 42%
100000 100000 10308 6492 37%
10092 6939 31%
10576 7160 32%
表1响应时间表
图8响应时间图
试验表明本文设计的方案能够大大提高内存的分配效率，其中，连续分配和释放的次数越少，越能体现本文设计方案的效率改善幅度。同时申请释放内存，与申请内存而不释放的情况相比，效率要高。效率总体提高了67%。本设计满足服务器关于响应时间的要求。
4结束语
筆者将Linux内核中关于分配的思想应用在网络服务器应用程序的开发中，并且其中融入了新的设计和思路。该设计不仅避免了内存碎片的问题、而且由于是O(1)算法，提高了实时性。进一步的工作是根据本文的设计优化网络服务器程序，使得服务器达到安全、稳定、高效的设计要求。
参考文献：
[1]Comfort W T.Multiword list Items[J].Communications of the ACM,1964,7(6):357-362.
[2]王明路,王希敏,王哲.嵌入式系统中池式内存分配方法的分析[J].计算机与数字工程,2008,36(2):57-61.
[3]孙晓辉,王劲林,陈晓.实时系统中的动态内存分配算法[J].计算机工程,2008,34(8):80-84.
关键词：Linux；内存分配；网络服务器；响应时间
中图分类号：TP393.08文献标识码：A文章编号：1007-9599 (2013) 05-0000-03
1概述
笔者在开发一款基于Linux的网络服务器时，被要求设计一种高效的、并且碎片率很低的内存分配方法。为此，先对当前流行的动态存储管理方法进行了研究分析，例如：顺序搜索，buddy算法，分类搜索，索引搜索，位图搜索等。这些方法要么效率不高，时间复杂度是O(n)或者O(logn)；要么设计复杂、实现困难，而服务器要求7*24小时连续不间断的提供服务，这种复杂的设计在服务器运行中容易出错；要么会产生较高的内存碎片率，服务器被要求长年累月的运转，较高的内存碎片率很影响服务器的效率。因此，不能将这些内存分配方法直接应用于Linux网络服务器的开发中。笔者在Linux内核代码的研究中，发现在内核代码的某个模块中存在一种O(1)分配算法。因此，笔者在Linux网络服务器的研发中，引入了这个O(1)分配算法的思想，并且融入了新的设计，形成了一个符合现实需求、高效的、并且内存碎片率很低的用户内存分配方案。
2内存分配方法设计
2.1需求分析
Linux网络服务器是整个项目系统的一部分，它位于上位机和终端设备之间。这个系统对服务器的内存分配方法有具体的要求：
（1）提高实时性。分配和释放内存都必须在一个确定的时间内完成。
（2）减少内存碎片。服务器程序需要7*24小时连续不间断的提供服务，产生过多的内存碎片会影响系统的性能。
（3）分配内存的大小固定。本系统处理的网络数据都是介于90到110字节之间的长度。由于TCP链路众多，并且每条链路的业务量很大，因此在服务器上这些数据包的分配和释放是非常频繁的。
2.2方案设计之数据结构
在Linux服务器程序初始化的时候，一次申请一大块内存，应用程序再把这块内存分成多份等大的基本单元，每个单元可以存放一个数据包。另外，在服务器运行中，如果系统需要，可以再一次或者多次分配足够的大量的内存，将这些内存块格式化成设计的管理格局。在应用程序申请小块内存时，就从上一步的管理格局中分配一个基本单元。
在这个方案中有三个重要的数据结构，其数据成员以及含义见表1。
数据结构（结构体） 数据成员 含义
System name 该system结构体的名字
fulllists Dentry的链表，其中每个dentry的基本单元都已经分配完毕
emputylists_head Dentry的链表，其中每个dentry都有部分内存空闲没有分配
emputylists_rear 指向上一项dentry链表的尾部
totalcount 该system中基本单元的总数
totalused 该system中已经分配的基本单元的个数
fixedunit 该system中基本单元的有效数据的大小
Dentry count 该dentry管理的基本单元的总数
free 该dentry中第一个空闲基本单元的编号
used 该dentry中已经分配的基本单元的个数
system 该dentry隸属的system
start 该dentry管理的第一个基本单元的地址
pre 用于形成dentry的链表，pre指向前一个dentry
next 用于形成dentry的链表，next指向后一个dentry
Item id 基本单元的编号
nextid 下一个基本单元的编号
dentry 该基本单元隶属的dentry
used 该基本单元是否已经被分配
data 该基本单元管理的有效内存的起始地址，该有效内存位于每个item之后
表1核心数据结构以及含义
2.3方案设计之算法介绍
在介绍整个方案之前，先说明一下单个dentry是如何管理内存的。在创建某个dentry时，将dentry和它管理的item，初始化成链表，如图1。最左侧的圆圈表示dentry中的free成员。右侧的8个矩形表示8个item。矩形中的数字表示item中的nextid值。矩形下方的数字表示item的编号。
图1初始化dentry
应用程序申请一个item后，dentry的布局如图2所示。
图2申请一个item后的dentry布局
其后，又连续申请了两个item，布局如图3所示。
图3申请三个item后的dentry布局
接着，释放编号为1的item，其布局如图4所示。
图4释放编号为1的item后的布局
最后再释放一个编号为2的item，其布局如图5所示。
图5释放编号为2的item后的布局
其上本文分析了单个dentry是如何分配和释放基本单元item的，下文将对网络服务器中内存分配机制的整个原理进行设计说明。其中，下文中用emputylists表示emputylists_head和emputylists_rear构成的链表。
（1）在网络服务器初始化过程中，创建一个system结构、一个dentry结构、以及这个dentry所管理的若干个基本单元和有效内存区域。每个system结构规定了它所支持的基本单元中有效内存的最大值，在这个项目中设置成120字节。并且把这个dentry列入fulllists链表。
（2）服务器申请小块内存时，直接从emputylists指向的第一个dentry中分配，此时的分配机制请见前面的介绍。分配内存的算法是先找到将要分配的item，然后返回其后的有效内存的起始地址了。如果分配后发现这个dentry的内存都使用了，则将该dentry放入fulllists链表中。
如果在分配时发现emputylists已经成为空链表，则再创建一个dentry以及它管理的若干item。并将新建的dentry加入到emputylists链表中。
（3）应用程序释放内存时，将item归还给对应的dentry，如果该dentry在fulllists链表中，则将它列入emputylists的尾部。释放内存的函数先根据地址参数找到对应的item结构体，然后将这个item归还给dentry。
（4）经过长期运行，系统中会形成如图6所示的布局。
图6系统布局
3试验结果
3.1试验程序设计
将本文设计的内存分配方法和C语言传统的malloc/free机制进行比较。
（1）首先根据输入参数，随机的计算出如图7所示的申请和释放的操作序列。
图7申请和释放的序列
其中，alloc_free用于保存申请后的内存地址，在第一步中不做任何设置。而flag_arr用于保存申请和释放的序列，其中，+1表示申请内存，并把申请到得内存地址保存在allc_arr中；-1表示释放内存，释放哪块内存由free_arr指明。free_arr中保存的是alloc_arr的下标号。
（2）再用C语言中的malloc/free函数实现上一步中产生的操作序列。用本文设计的方法同样实现以上的序列。比较这二者响应时间的不同。
3.2试验结果
测试是在Pentium(R)Dual-Core CPU、1024M内存、CentOS5.4操作系统的机器上进行的。笔者没有采用ptrace跟踪程序实际使用的指令数，而是使用Linux提供的gettimeofday函数计算时间差，笔者认为后者更能准确的反应响应时间。并且为了避免进程调度对测试产生影响，测试初始化时将测试程序置为实时进程。本文设计的方法，不仅可以避免内存泄露，而且由于它是O(1)算法，所以响应时间是能够得到保障的。试验中每次申请和释放都是100字节，以下是多次的试验情况，详情见表1。图8中展示的是响应时间的比较，本文设计的方法从响应时间上优于malloc/free函数。
申请次数 释放次数 C语言malloc/free所需时间（按微妙计算） 本文设计方案所需时间（按微妙计算） 效率提高幅度
100 0 96 9 91%
105 8 92%
97 8 92%
1000 0 297 78 74%
367 81 78%
247 77 69%
10000 0 2165 843 61%
2094 763 64%
2046 770 62%
100000 0 22222 7896 64%
23291 8460 64%
20571 7802 62%
100 100 179 8 96%
113 8 93%
171 8 95%
1000 1000 210 68 68%
245 65 73%
311 70 77%
10000 10000 1216 622 49%
1128 660 41%
1169 680 42%
100000 100000 10308 6492 37%
10092 6939 31%
10576 7160 32%
表1响应时间表
图8响应时间图
试验表明本文设计的方案能够大大提高内存的分配效率，其中，连续分配和释放的次数越少，越能体现本文设计方案的效率改善幅度。同时申请释放内存，与申请内存而不释放的情况相比，效率要高。效率总体提高了67%。本设计满足服务器关于响应时间的要求。
4结束语
筆者将Linux内核中关于分配的思想应用在网络服务器应用程序的开发中，并且其中融入了新的设计和思路。该设计不仅避免了内存碎片的问题、而且由于是O(1)算法，提高了实时性。进一步的工作是根据本文的设计优化网络服务器程序，使得服务器达到安全、稳定、高效的设计要求。
参考文献：
[1]Comfort W T.Multiword list Items[J].Communications of the ACM,1964,7(6):357-362.
[2]王明路,王希敏,王哲.嵌入式系统中池式内存分配方法的分析[J].计算机与数字工程,2008,36(2):57-61.
[3]孙晓辉,王劲林,陈晓.实时系统中的动态内存分配算法[J].计算机工程,2008,34(8):80-84.