1.多个线程同时读（查找/遍历）
2.单线程写（添加/删除/更新）
考虑到多线程的效率，我不想加锁
基于整数赋值都是原子操作的前提，单写多读延迟释放
例如：
A->B->C(双向链表)
<- <-
1.删除B时，原子操作修改AC指针，延迟释放B
2.更新B时，先生成一个新节点B"，原子修改AC指针到B"，延迟释放B
下面测试程序验证感觉没有问题，但是延迟释放的契机无法把握，
请教高手有没有更好的办法？
测试程序：
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <signal.h>
#include <sys/timeb.h>
#include <inttypes.h>
#include <stdint.h>
#include <assert.h>
#include <string.h>
#include <unistd.h>
#include <sys/time.h>
struct Node
{
Node * next;
int key;
char val[50];
Node()
{
memset(this,0,sizeof(Node));
}
};
class MyList
{
public:
MyList()
{
m_pHead = new Node;
assert(m_pHead!=NULL);
m_pHead->next = NULL;
m_pHead->key = 0;
//m_pHead->val = 0;
}
~MyList()
{
while(m_pHead != NULL)
{
Node * pTmp = m_pHead->next;
delete m_pHead;
m_pHead = pTmp;
}
}
/*int Get(int aikey)
{
Node * pTmp = m_pHead->next;
while(pTmp != NULL)
{
if(pTmp->key == aikey)
{
return pTmp->val;
}else
{
pTmp = pTmp->next;
}
}
return 0;
}*/
char* Get(int aikey)
{
Node * pTmp = m_pHead->next;
while(pTmp != NULL)
{
if(pTmp->key == aikey)
{
return pTmp->val;
}else
{
pTmp = pTmp->next;
}
}
return NULL;
}
int Set(int aikey, int aival)
{
Node * pTmp = new Node;
assert(pTmp!=NULL);
pTmp->key = aikey;
//pTmp->val = aival;
sprintf(pTmp->val,"%d",aival);
pTmp->next = m_pHead->next;
m_pHead->next = pTmp; //atomic?
return 1;
}
int Del(int aikey)
{
Node * pfront = m_pHead;
Node * pnext = m_pHead->next;
while(pnext != NULL)
{
if(pnext->key == aikey)
{
pfront->next = pnext->next; //atomic?
//free(pnext); //wait
return 1;
}else
{
pfront = pnext;
pnext = pnext->next;
}
}
return 0;
}
int Upd(int aikey,int aival)
{
//create new node
Node * pTmp = new Node;
assert(pTmp!=NULL);
pTmp->key = aikey;
sprintf(pTmp->val,"%d",aival);
//insert head
pTmp->next = m_pHead->next;
m_pHead->next = pTmp; //atomic?
//remove old key
return Del(aikey);
}
private:
Node *m_pHead;
};
int g_threadnum;
MyList loList;
int g_nodenum;
static void create_worker(void *(*func)(void *), void *arg) {
pthread_t thread;
pthread_attr_t attr;
int ret;
pthread_attr_init(&attr);
if ((ret = pthread_create(&thread, &attr, func, arg)) != 0) {
fprintf(stderr, "Can't create thread: %s\n",
strerror(ret));
exit(1);
}
}
static void *ReadFunc(void *arg)
{
MyList *mc = (MyList*)arg;
while(1)
{
//usleep(g_sleeptime);
int liRand = (rand()%g_nodenum) +1 ;
int liVal = atoi(mc->Get(liRand));
if(liVal)
{
if((liVal % liRand) !=0 )
{
printf("Get Error Key=%d Val=%d\n",liRand,liVal);
exit(1);
}else
{
;//printf("Get Success Key=%d Val=%d\n",liRand,liVal);
}
}
}
exit(0);
}
static void *WriteFunc(void *arg)
{
MyList *mc = (MyList*)arg;
int licount = 0;
while(1)
{
//usleep(g_sleeptime);
int liRand = (rand()%g_nodenum) +1 ;
if(mc->Del(liRand))
{
licount++;
printf("Del Key=%d\n",liRand);
if(licount%1000==0)
{
printf("Del Count[=%d]\n",licount);
}
}
}
exit(0);
}
static void *UpdateFunc(void *arg)
{
MyList *mc = (MyList*)arg;
int licount = 0;
while(1)
{
//usleep(g_sleeptime);
int liRand = (rand()%g_nodenum) +1 ;
int liplus = (liRand%10) +1;
if(mc->Upd(liRand,liRand*liplus))
{
licount++;
//printf("Upd Key=%d\n",liRand);
if(licount%1000==0)
{
printf("Upd Count[=%d]\n",licount);
}
}
}
exit(0);
}
int main(int argc, char** agrv)
{
int i = 0;
g_threadnum = atoi(agrv[1]);
g_nodenum = atoi(agrv[2]);
for(i=0; i< g_nodenum; i++)
{
loList.Set(i+1,i+1);
}
for(int i=0; i< g_threadnum; i++)
{
create_worker(ReadFunc,&loList);
}
//create_worker(WriteFunc,&loList);
create_worker(UpdateFunc,&loList);
while(1)
{
usleep(10);
}
return 0;
}
8 个解决方案
#1
需要加锁。
#2
linux 下，建议读写锁，比较快。
#3
这都不想用锁。。。。。
linux下直接读写锁，windows下自己实现个读写锁大概效率高点，可以百度
linux下直接读写锁，windows下自己实现个读写锁大概效率高点，可以百度
#4
如果是写一个字节，不用加锁。(^_^)
#5
如果只是修改，单一数据4个字节以下也不用加（32位系统），但是删除和添加数据是不行的
#6
无论写一个字节还是一位 都需要加锁
#7
no，原子操作无需加锁
#8
加呗！总不会错！
#1
需要加锁。
#2
linux 下，建议读写锁，比较快。
#3
这都不想用锁。。。。。
linux下直接读写锁，windows下自己实现个读写锁大概效率高点，可以百度
linux下直接读写锁，windows下自己实现个读写锁大概效率高点，可以百度
#4
如果是写一个字节，不用加锁。(^_^)
#5
如果只是修改，单一数据4个字节以下也不用加（32位系统），但是删除和添加数据是不行的
#6
无论写一个字节还是一位 都需要加锁
#7
no，原子操作无需加锁
#8
加呗！总不会错！