技术领域
本发明涉及计算机内存管理和数据通信领域，具体涉及一种基于共享内存池的通用数据
存储方法。
背景技术
随着科技日新月异地进步和计算机技术的发展，信息化已经融入到现代社会的方方面面，从科研到工业，从金融到日常生活都与计算机密切相关。伴随着网络带宽的增加和智能设备
的普及，计算机应用场景日趋丰富，实时交互业务逐渐增多，各种业务对服务器端的可靠性
和处理速度提出了越来越高的要求。无论是单机应用还是集部署，服务器端如何保证高可用，低延迟得到了开发者的广泛关注。因此，优化服务端软件性能，充分挖掘硬件潜能始终
是后台开发者要面对的一个重要问题。
在服务端程序中，数据存储和检索是计算机应用的重要方面，也是性能优化的一个关键点。系统默认的申
请释放内存方式，应对最普遍最复杂的内存使用场景。每次显示调用malloc/free对应着若干底层系统调用（参考：吴捷，陶志荣，一种自适应变长块内存池SVBSMP，计算机应用，2008，第28卷）。每次内存请求通常隐含着互斥区保护，空闲链表查，内存 块匹配，空闲区分割或邻近空闲区合并，链表更新等一系列复杂的算法和操作。因此，频繁
地在堆上分配和释放内存会导致性能损失，并且会使系统中出现大量的内存碎片，降低内存
的利用率（参考：冯宏华，徐莹，程远，汪磊等，C++应用程序性能优化，北京：电子工业出版社，2010）。对于特定的应用，程序根据自身特点构建内存池是解决系统频繁分配释放内存的最直接方案。应用程序先申请一块较大内存，然后由程序控制在此内存池空间中申请释放
内存，这可以避免默认方法产生的一些额外操作，从而得到更高的时间效率和空间效率。
经典内存池mempool把内存区分成大小相同的小块(unit)，将空闲块形成单链表，每次申请时从空闲链取下结点，释放时挂回到空闲链上，若当前内存区(block)空间不足，再申请新
内存区(block)加入链表。这种方式可以获得极高的时间效率，其内存分配过程多数情况下复
杂度为O(1)，开销最多时是在开辟新内存区(block)时初始化和加入原有block链的过程。此
种方法比较适合小的空间请求。
现在有数量庞大web服务器运行着源自Apache的APR_pool内存管理方法。APR_pool
按对象的不同生命周期划分多级内存池，支持变长内存块索引。这种内存管理以业务处理的
层次性为设计基础，不同层次的池具有不同生命周期。对于单个对象不需要考虑申请和释放
成对，通过销毁池来销毁一批对象，释放的开销相对较低，但释放后的空间直接归还到系统而不能回归到池里，因此这种结构的内管理也存一些弊端且结构复杂。
还有一些内存管理思路，如自适应变长块内存池SVBSMP（参考：吴捷，陶志荣，一种自适应变长块内存池SVBSMP，计算机应用，2008，第28卷）。SVBSMP按内存单元递增速率不同管理了两个链表，分别管理0-512B和512B-16KB两种规则变化的内存块，针对每次请求，从目标链中到符合要求的块返回给用户。空闲链不足时，继续申请新内存加入管理。当用户单次申请的空间大于512B时，分配和释放工作直接交给系统处理，回收空间也不纳入SVBSMP内存管理。这种方式比较适合请求的数据块空间变化较大，大小不同的空间请求接近均匀分布的情况。在应对大量尺寸集中的空间申请时碎片线性增加，内存利用率下降。 在进程间通讯技术方面，类Unix系统为数据共享和同步提供了多种方式：有父子进程间的管道（pipe)、
有改进的半双工有名管道（named pipe）、有通知式的信号、有链式队列、有socket套接字和共享内存等。它们各有特点，但综合起来，管道、信号和socket套接字方式存在或容量小或效率低或易阻塞的问题。相比之下，共享内存方式通过将一块内存区域映射到进程虚拟地址空间中，使相关进程在用户态即可完成数据共享，因而成为效率最高并且支持大容量数据共享的进程间通讯方式。
发明内容
针对堆内存池在多进程环境下数据共享乏力，传统内存池对存储的数据缺少顺序维护，可变内存池易产生外部碎片的情况。本发明设计了一种基于共享内存池的通用数据存储方法。
本发明的技术方案为：
一种基于共享内存池的通用数据存储方法，其步骤包括：
1）为目标应用申请一块共享内存，根据该目标应用要存储内容类别的不同将该共享内存分为m个内存块；其中，每一个内存块的头部存储该内存块的管理者结构，内存块剩余空间分为n个内存单元，在每一内存块中构建一个共享内存池；
2）在每一内存块里构建两个双向循环链表，即空闲链表和繁忙链表；其中空闲链表用于维护内存块的空闲内存单元，繁忙链表用于维护内存块的繁忙内存单元；初始化时所有内存单元属于空闲链表，繁忙
链表为空，管理者结构的空闲链表索引iFree 指向当前内存块的空闲链表头节点，繁忙链表索引iBusy指向繁忙链表头节点索引； 3）当该目标应用每次存储数据时，调用一次存储接口；在存储接口内根据待存储数据大小从该共享内存中进行若干次内存单元申请直至本次数据存储完成，并将本次申请到的内存单元形成单链表，将本次申请到的第一个内存单元作为首节点加入繁忙链表，
后续申请到的内存单元作为子节点，挂在首节点后形成单链表，将单链表中的节点通过子索引串联起来。
进一步的，所述管理者结构记录当前内存块内存单元总数totalNum、空闲单元数freeNum、繁忙单元数busyNum、空闲链表头索引iFree、繁忙链表头索引iBusy和内存块编号信息；每一所述内存单元中具有一内存单元结构，用于记录内存单元在当前内存块中的索引值index、内存单元的前驱节点索引pre、内存单元的后继节点索引next、存储数据的key值、key值长度、数据内容、数据内容长度、写入时间、子节点个数subCnt、节点子索引subIndex以及子节点后继索引值subNextIndex；节点子索引subIndex是指节点在单链表中的索引。
进一步的，步骤3）中，每次存储数据时，先根据待存储数据大小和内存单元数据区大小计算此次存储所需内存单元数，如果所需内存单元数超过空闲单元数，则此次申请失败；若申请的内存单元数小于或
等于空闲单元数，则根据内存单元的需求数量循环申请空闲单元，每次申请时直接取管理者结构空闲链表头索引iFree指向的节点，如果是存储接口第一次申请空闲单元，则将取到的节点插入到繁忙链表头索引iBusy指向的节点之前作为新的头节点；通过双向循环链表增删操作，使加入新单元的繁忙链表和摘掉iFree节点的空闲链表重新形成双向循环链表；如果存储接口不是第一次申请空闲单元，则把申请到的内存单元依次挂到单链表首节点后面；每次申请空闲单元后修改管理者结构的空闲单元数freeNum减一，繁忙单元数busyNum数量加一；然后向申请到的内存单元写入数据key值和key长度，向数据区写入数据片段，如果当前所申请的内存单元是此次申请所需的最后一个内存单元，则数据长度为剩余的数据长度，否则数据长度为内存单元数据区长度。
进一步的，存储数据时更新对应内存单元的内存单元结构的子节点个数subCnt和子节点索引subIndex，同时将内存单元的索引值记录到数组中作为前一个申请到的内存单元的subNextIndex值，直到申请完本次存储全部所需内存单元，最后申请到的内存单元的subNextIndex值为-1。
进一步的，将内存块的编号作为该内存块对应的内存池编号，各内存池共用信号量编号semid，将内存池编号作为对应内存池的信号量数组索引sem_num值。
进一步的，当进行检索数据时，根据输入的内存块编号、key值和查顺序搜索繁忙链表，匹配到存储数据的首节点后，依靠该首节点中记录的后继节点信息到下一个数据片段的存储位置，再把不同片段连接起来返回。
进一步的，通过一删除接口释放存内存单元，其方法为：首先定位待释放内存单元对应的目标节点，然后到要删除数据的首节点，然后逐个删除由该首节点引导到的单链表节点；如果当前到删除的是首节点，则将该首节点从繁忙链表中取出插入到空闲链表头索引iFree
后，如果当前删除的是非首节点，则将删除的节点从单链表中取出插入到空闲链表头索引iFree后，如果空闲链表头索引iFree为空，则将当前删除的节点作为新的空闲链表头索引iFree 节点；当删除的目标节点是繁忙链表头索引iBusy时，删除该目标节点后，新的繁忙链表头索引iBusy指向该目标节点的后继节点索引next。
进一步的，通过一修改接口修改内存单元中的数据，其方法为：首先定位到待修改数据所在的目标内存单元，该目标内存单元中记录着原数据占用的总内存单元数；根据新数据和节点数据区大小计算新数据所需内存单元个数，如果原数据已占用的内存单元数等于新数据所需内存单元数，则直接遍历该目标内存单元所对应目标节点引导的单链表，重写数据区；如果已占用的内存单元数大于新数据所需内存单元数，则把新数据用到的内存单元数据区重写，修改子节点个数subCnt和节点子索引subIndex，再将剩余的内存单元从繁忙链中删除；如果新数据占用的内存单元数大于原数据已占用内存单元数，则遍历该目标内存单元所对应目标节点引导的单链表i，重写数据区，当到达该单链表i的链尾时申请新内存单元直到新数据存储完成。
进一步的，为该目标应用申请所述共享内存的方法为：通过系统调用函数shmget将一段物理内存映射到该目标应用的地址空间中。
本发明运用共享内存（System V标准）和信号量原理，以双向循环链表组和单链表相结合的方式作为数据结构，实现了可以有序存储和检索的共享内存池，再以共享内存池为基础，封装一套增删改查方法，使用户可以以key-value方式对任何类型数据进行读写操作。本系统以API形式对外提供存储和检索方法，具体包括下面步骤：
1.内存划分。初始化时通过系统调用函数shmget为目标应用申请一块足够大的共享内存（shmget系统函数会把一段物理内存映射到目标应用地址空间中；Int shmget(key_t key, size_t size, int shmflg); 不同进程调用shmget时传入相同的key值，即可在各自进程空间访问到同一块内存）。根据应用要存储内容类别的不同把这块大的共享内存分为m个内存块（memory block)。每一个内存块的头部取固定大小存储管理者（node manager)结构，再将当前内存块剩余空间划分为等大小的n个内存单元(memory unit)，在每一内存块中构建一个共享内存池。管理者结构记录当前内存块内存单元总数totalNum、空闲单元数freeNum，繁忙单元数busyNum，空闲链表头索引iFree，繁忙链表头索引iBusy、内存块编号等信息，如图1所示。内存单元结构记录了本单元在当前内存块中的索引值index、本单元前驱节点索引pre、后继节点索引next、存储数据的key值、key值长度、数据内容、数据内容长度、写入时间、子节点个数subCnt、节点子索引subIndex（节点在单链表中的索引）以及子节点后继索引值
subNextIndex等信息。具体内存单元结构见图2。由于共享内存被多进程访问，因此不能直接使用逻辑地址去标记内存单元，又因为各个内存单元是等大小分割，因此可以通过索引值计算内存单元在本内存块内的偏移值，从而得到地址值。为了便于表述，下文仍将把通过内存单元索引值串联起来的内存链称为链表（每块内存区里有两种链表：一组循环双向链表，和若干单链表，一次存储接口调用形成一个单链表），链表中的每一个内存单元称为一个节点。为了对多进程访问做代码保护，引入一个互斥信号量，初始信号量值为1，因此管理者除了记录上面所述空间划分相关信息外，还要记录互斥信号量编号semid和信号量数组索引
sem_num。由于我们在内存块空间内构建内存池，因此可以把内存块编号（0到m）做为信号量数组索引，从而达到各进程对内存池互斥访问。
2.链表建立。初始化时为每个内存单元设置了索引编号（索引值index），索引编号表示内存单元位于本内存块（memory block)中的位置，索引范围从0到n-1。在每个内存单元内记录它的前驱和后继单元的索引值，这样，在一个内存块里可以构建两个双向循环链表，分别维护空闲内存单元和繁忙内存单元。初始化时所有内存单元都属于空闲链表，繁忙链表为空，管理者（node manager)的空闲链表索引iFree 指向当前块的空闲链表头节点，繁忙链表索引iBusy指向繁忙链表头节点索引（初始化时无繁忙节点，此值为-1），管理者的内存单元总数等于空闲单元数，繁忙单元数为0。初始化时存储单元的子节点个数默认为1（1即是指子节点是自已），节点子索引值subIndex默认为0，子节点后继索引subNextIndex值为-
1（-1表示无后继子节点）。本内存管理机制中采用一次接口调用多次申请空闲单元，分片段存储数据的方式。即每次存储数据，调用一次存储接口，在存储接口内根据数据大小，可能会多次申请内存单元；在空间申请完成后，把每次申请到的内存单元通过单链表连接起来，即每次调存储接口都会产生一个单链表（可能只有一个节点；单链表中的节点通过子索引串联起来）。第一个申请到的内存单元作为此单链表的首节点，首节点由繁忙链表管理，后申请到的内存单元是子节点，子节点挂在首节点后面排队，首节点与子节以及各子节点间通过子节点后继索引串联起来。首节点既属于双链表又属于单链表，子节点只属于由首节点引导单链表。
这种链式存储方法应对大字节数据会分片段存储，不要求内存连续，因此这种方案不会产生不可利用的外部碎片，只是在最后一个申请的内存单元尾可能形成不可用空间，或称为内存碎片。内部碎片是临时存在的，当数据释放时，内存单元回归到可用。在具体应用系统中，根据数据大小设置合适的内存单元大小，可以减少空间浪费。
3.接口调用。任何接口调用首先都要连接到共享内存，根据共享内存地址和内存块编号计算出目标共享内存池的起始地址，进而可以得到此共享内存池的管理者和内存单元的首地址。在操作某一个共享内存池时先执行P操作检查资源数，当资源数大于等于0时本进程才
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议