共享内存中数据结构浅析

《共享内存中数据结构浅析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、共享内存中数据结构浅析增值业务部/林睿共享内存以高速访问特点，广泛应用于电信级系统中。我在此总结个人对共享内存的使用心得，希望能对部分开发人员有所帮助。限于个人水平，本文中不准确之处也请大家见谅。程序为访问共享内存时，需将共享内存地址空间映射程序的地址空间，不同程序或相同程序重启后共享内存映射的地址都各不同。所以在共享内存中，通常以数组下标方式指示相关节点信息。共享内存除为进程间通讯提供重要手段外，还常用来实现数据缓存匹配、数据快速检索等功能。如何以数组方式构造循环队列、散列队列、平衡二叉树等数据结构，下面

2、将做简要介绍：1．循环队列在共享内存中，常采用该类型数据结构构造进程间通讯管道。structEnQueue{unsignedintuHead;//循环队列头节点数组下标unsignedintuTail;//循环队列尾节点数组下标BodyaBody[QUEUESIZE];//队列数据区域};循环队列结构中包括头节点、尾节点和队列数组三个部分。消费进程在队列数组中从头节点为下标开始读取数据，读取到以尾节点为下标时结束；而生产进程则在队列数组中从尾节点为下标开始写入数据，写入到头节点为下标结束。消费进程读数据时，

3、头节点值自增，生产进程写数据时，尾节点值自增。队列长度为QUEUESIZE，头节点、尾节点若等于或超过该队列长度，需要循环到数组头，值置为0。¾循环队列示意图1/10uHead==uTailluHead==uTaill示意图1：空队列uHeaduTail示意图2：带数据的队列uTailuHead示意图3：带数据的队列uTailuHead=uTail+1示意图4：队列满uHead==uTaill示意图5：初始化队列¾队列初始化1）初始化数组队列；2）uHead和uTail都置为0。¾生产进程队列操作流程2/1

4、0¾消费进程队列操作流程0¾线程安全性消费进程只更新头节点，生产进程只更新尾节点，且数组中的任意节点在一个时刻内只能是空节点或者是有效数据节点，两类进程也不存在同时访问相同节点的可能。所以若消费进程和生产进程都只有一个的情况下，该结构是线程安全的，无需加互斥或信号量。2．散列队列在共享内存中，

5、常采用该类型数据结构实现数据缓存及快速匹配。structHashQueue{unsignedintuFree;//空闲链表头节点数组下标unsignedintuHead[HASHSIZE];//散列链表头节点3/10数组下标unsignedintuHash[QUEUESIZE];//链表节点指向下一节点下标数组BodyaQueue[QUEUESIZE];//队列数组};散列队列结构中包括空闲链表头节点、散列链表头节点数组、链表节点指向数组和队列数组四个部分。其中散列值范围为0－HASHSIZE，队列数组长度

6、为QUEUESIZE，一般QUEUESIZE远远大于HASHSIZE。队列数组主要存储普通业务数据，链表节点指向数组存放在队列数组中相同下标节点在链表中的下一节点下标。散列链表头节点数组存在各个散列值的链表头节点在队列数组的下标。具体示意如下：uHash……72080475000000050000000……8040731727……uFree8052uHead……37723……在一个散列队列中存在两种类型链表队列，其中一种为空闲节点链表队列，由数据缓存进程从该队列中获取空闲节点，该队列头节点下标存放在uFre

7、e变量中；另一种为各散列值链表队列，不同散列值分别构建不同的链表队列，各链表队列头节点下标存储以散列值为下标的的uHead数组中。不论uFree、uHead数组节点或uHash数组节点值为QUEUESIZE，都表示没有后续节点，如uFree＝QUEUESIZE，则表示散列队列满，没有可分配空闲节点；如uHead[31]＝QUEUESIZE，则表示散列值为31队列为空，没有可匹配节点；如uHash[31]＝QUEUESIZE，则表示aQueue[31]的位于队列尾，没有后续节点。¾散列队列示意图4/10空闲队

8、列散列队列01………………………HASHSIZE－1¾队列初始化1）初始化数组队列；2）将所有节点都添加到空闲队列中，即uFree置为0，uHash[i]=i+13）所有散列队列都置为空，即将uHead数组中所有值都置为QUEUESIZE；¾数据缓存进程队列操作流程5/10开始判断该散列链链表为空表是否为空链表不为空判断该散列链表是否为空链表不为空计算散列值遍历到该散列链表链表为空尾部新分配节点为链表互斥体或信号