最快线程间数据交换算法.docx
- 文档编号:4599149
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:15
- 大小:17.92KB
最快线程间数据交换算法.docx
《最快线程间数据交换算法.docx》由会员分享,可在线阅读,更多相关《最快线程间数据交换算法.docx(15页珍藏版)》请在冰点文库上搜索。
最快线程间数据交换算法
最快线程间数据交换算法,有效避免锁竞争–TwoQueues
大升刷票整理
处理多线程数据共享问题注意的几个要点:
1、锁竞争:
尽量减少锁竞争的时间和次数。
2、内存:
尽量是使用已分配内存,减少内存分配和释放的次数。
尽量是用连续内存,减少共享占用的内存量。
多线程数据交换简单方案A:
定义一个list,再所有操作list的地方进行加锁和解锁。
简单模拟代码:
classCSimpleQueue
{
public:
CSimpleQueue()
{
InitializeCriticalSection(&m_crit);
}
~CSimpleQueue()
{
DeleteCriticalSection(&m_crit);
}
//添加数据
voidAddData(DATApData)
{
EnterCriticalSection(&m_crit);
m_listDATA.push_back(pData);
LeaveCriticalSection(&m_crit);
}
//获取数据
boolGetData(DATAdata)
{
EnterCriticalSection(&m_crit);
if(m_listDATA.size()>0)
{
data=m_listDATA.front();
m_listDATA.pop_front();
LeaveCriticalSection(&m_crit);
returntrue;
}
else
{
LeaveCriticalSection(&m_crit);
returnfalse;
}
}
private:
listm_listDATA;
CRITICAL_SECTIONm_crit;
};
多线程数据交换优化方案B--TwoQueues:
文章最后有TwoQueues的详细实现源代码。
TwoQueues的实现分析:
锁竞争:
TwoQueues使用双内存块交换的方式减少锁竞争,数据写入时会进行加锁和解锁操作,但读取数据时,只是当当前读取队列的数据读取完毕时,进行两个队列交换时才进行加锁和解锁操作。
可以说,数据的读取是不进行加锁的。
这样,最大限度的降低了锁竞争问题。
内存:
TwoQueues采用预先分配内存块的方式,初始化TwoQueues时就已经将存放数据的内存分配好了。
之后数据存放于已经分配的内存块上。
无需再次分配内存,不会再次进行内存分配。
TwoQueues的进一步优化,TwoQueues在存放数据时,完全可以模仿【数据长度+数据】的方式存放数据。
但是这种方式会增加数据存在性检测的效率。
TwoQueues则采用了一种链表的方式进行存放数据。
链表结构:
typedefstructtagDataHead
{
tagDataHead()
{
pHead=NULL;
nLen=0;
pNext=NULL;
}
voidReSet()
{
pHead=NULL;
nLen=0;
pNext=NULL;
}
char*pHead;
unsignedintnLen;
tagDataHead*pNext;
}DATAHEAD;
此链表存放了数据头指针和数据长度。
当TwoQueues中存在数据时,可以直接通过链表节点拿数据。
因为链表每次创建时也是需要进行申请内存,而内存申请是一个比较耗效率的事情,TwoQueues再此做了一个小小的处理,当链表头不存在时,会进行ReAlloc调用,一性申请MALLOC_SIZE个链表头结构。
并且链表从链表上解下时并不会释放内存而是放入一个pFreeDataHead链表上,当需要申请链表头结构时,会先从pFreeDataHead链表上取链表结构。
此处理减少了内存分配和释放的次数,提高了多线程数据共享的效率。
以上的各种优化处理,使TwoQueues的效率得到了极大的提升。
之前做过的内存共享的测试。
A线程不停的写入数据,B线程不停的读取数据。
debug版本
release版本
TwoQueues
80-100万次/秒
170-180万次/秒
CSimpleQueues
20万次/秒
5万次/秒
双队列的使用:
创建对象:
CTwoQueuesm_cTwoQueues;
//初始化双队列大小,因为是双队列,所以内存占用量是两份。
m_cTwoQueues.Init(0x0FFFFFFF);
写入方式:
m_cTwoQueues.PushData(sz,strlen(sz)+1);
读取方式:
constvoid*pData=NULL;
unsignedintnLen=0;
if(m_cTwoQueues.PrepareData(pData,nLen))
{
//处理数据 ...
//确认(丢弃)此数据
m_cTwoQueues.ConfimData();
}
//下面是TwoQueues的所有源代码 源代码下载
#pragmaonce
#include
namespaceclwCore
{
#defineMALLOC_SIZE128
typedefstructtagDataHead
{
tagDataHead()
{
pHead=NULL;
nLen=0;
pNext=NULL;
}
voidReSet()
{
pHead=NULL;
nLen=0;
pNext=NULL;
}
char*pHead;
unsignedintnLen;
tagDataHead*pNext;
}DATAHEAD;
typedefstructtagDataMem
{
tagDataMem(unsignedintnSize)
{
if(0==nSize)
{
assert(false);
return;
}
nMaxSize=nSize;
pDataMem=(char*)malloc(nSize*sizeof(char));
nDataPos=0;
if(NULL==pDataMem)
{
//CTwoQueues申请malloc内存失败。
assert(false);
}
pListDataHead=NULL;
pCurDataHead=NULL;
pFreeDataHead=NULL;
}
~tagDataMem()
{
//释放节点
ReSet();
while(NULL!
=pFreeDataHead)
{
DATAHEAD*pTempDataHead=pFreeDataHead;
pFreeDataHead=pFreeDataHead->pNext;
deletepTempDataHead;
pTempDataHead=NULL;
}
free(pDataMem);
pDataMem=NULL;
nDataPos=0;
}
boolReAlloc()
{
for(unsignedshorti=0;i { DATAHEAD*pTempDataHead=newDATAHEAD; //pTempDataHead->ReSet();//构造时已经初始化 if(NULL==pTempDataHead) { //申请DATAHEAD内存失败。 assert(false); returnfalse; } pTempDataHead->pNext=pFreeDataHead; pFreeDataHead=pTempDataHead; } returntrue; } DATAHEAD*GetDataHead() { if(NULL! =pFreeDataHead) { DATAHEAD*pTempDataHead=pFreeDataHead; pFreeDataHead=pFreeDataHead->pNext; returnpTempDataHead; } if(ReAlloc()) { if(NULL! =pFreeDataHead) { DATAHEAD*pTempDataHead=pFreeDataHead; pFreeDataHead=pFreeDataHead->pNext; returnpTempDataHead; } } //ASSERT("GetDataHead返回NULL。 "); assert(false); returnNULL; } unsignedintGetFreeLen()//空闲内存长度 { returnnMaxSize-nDataPos; } boolPushData(void*pData,unsignedintnLen) { if(nDataPos+nLen>=nMaxSize) { returnfalse; } DATAHEAD*pTempDataHead=GetDataHead(); if(NULL==pTempDataHead) { returnfalse; } //构造数据头结构 pTempDataHead->pHead=(pDataMem+nDataPos); pTempDataHead->nLen=nLen; pTempDataHead->pNext=NULL; //拷贝数据 memcpy(pDataMem+nDataPos,pData,nLen); nDataPos+=nLen; if(NULL==pListDataHead) { pListDataHead=pTempDataHead; pCurDataHead=pTempDataHead; returntrue; } else { pCurDataHead->pNext=pTempDataHead; pCurDataHead=pCurDataHead->pNext; returntrue; } } boolIsEmpty()//判断是否有数据 { return(NULL==pListDataHead)? true: false; } boolPrepareData(constvoid*&pData,unsignedint&nLen)//准备一条数据 { if(NULL! =pListDataHead) { pData=pListDataHead->pHead; nLen=pListDataHead->nLen; returntrue; } else { returnfalse; } } voidConfimData()//删除一条数据 { if(NULL==pListDataHead) { return; } DATAHEAD*pTempDataHead=pListDataHead; pListDataHead=pListDataHead->pNext; pTempDataHead->ReSet(); pTempDataHead->pNext=pFreeDataHead; pFreeDataHead=pTempDataHead; } voidReSet()//重置内存存储对象 { while(NULL! =pListDataHead) { DATAHEAD*pTempDataHead=pListDataHead; pListDataHead=pListDataHead->pNext; pTempDataHead->ReSet(); pTempDataHead->pNext=pFreeDataHead; pFreeDataHead=pTempDataHead; } nDataPos=0; pCurDataHead=NULL; } char*pDataMem;//数据内存区域 unsignedintnDataPos;//数据存储位置 unsignedintnMaxSize;//最大存储区域大小 DATAHEAD*pListDataHead; DATAHEAD*pCurDataHead; DATAHEAD*pFreeDataHead;//空闲头结构队列 }DATAMEM; classCTwoQueues { public: CTwoQueues(void) { InitializeCriticalSection(&m_crit); m_pDataMemPush=NULL; m_pDataMemPop=NULL; } ~CTwoQueues(void) { if(NULL! =m_pDataMemPush) { deletem_pDataMemPush; m_pDataMemPush=NULL; } if(NULL! =m_pDataMemPop) { deletem_pDataMemPop; m_pDataMemPop=NULL; } DeleteCriticalSection(&m_crit); } public: voidInit(unsignedintnSize) { if(0==nSize) { //初始化CTwoQueues对象失败。 assert(false); return; } m_pDataMemPush=newDATAMEM(nSize); m_pDataMemPop=newDATAMEM(nSize); } boolPushData(void*pData,unsignedintnLen) { //unsignedintnFreeLen=m_pDataMemPush->GetFreeLen(); boolbResult=false; EnterCriticalSection(&m_crit); bResult=m_pDataMemPush->PushData(pData,nLen); LeaveCriticalSection(&m_crit); returnbResult; } boolPrepareData(constvoid*&pData,unsignedint&nLen) { boolbCanRead=true; if(m_pDataMemPop->IsEmpty()) { //队列没有数据了 EnterCriticalSection(&m_crit); if(m_pDataMemPush->IsEmpty()) { //Push队列为空 LeaveCriticalSection(&m_crit); bCanRead=false; } else { m_pDataMemPop->ReSet();//充值读取队列 DATAMEM*pTempDataMem=m_pDataMemPush; m_pDataMemPush=m_pDataMemPop; m_pDataMemPop=pTempDataMem; LeaveCriticalSection(&m_crit); bCanRead=true; } } if(bCanRead) { returnm_pDataMemPop->PrepareData(pData,nLen); } else { returnfalse; } } voidConfimData() { m_pDataMemPop->ConfimData(); } private: DATAMEM*m_pDataMemPush; DATAMEM*m_pDataMemPop; CRITICAL_SECTIONm_crit; }; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最快 线程 数据 交换 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)