C++多线程-无锁链表
前面，为了使得写操作快速进行，我们定义了顺序锁。但是顺序锁有个缺点，那就是处理的数据不能是指针，否则可能会导致exception。那么有没有办法使得处理的数据包括指针呢？当然要是这个链表没有锁，那就更好了。 针对这种无锁链表，我们可以初步分析一下，应该怎么设计呢？ （1）读操作没有锁，那么怎么判断读操作正在进行呢，只能靠标志位了； （2）写操作没有锁，那么读操作只能一个线程完成； （3）写操作中如果是添加，那么直接加在末尾即可； （4）写操作中如果是删除，那么应该先删除数据，然后等到当前没有操作访问删除数据时，释放内存，但是首节点不能删除。
普通链表的结构为，
typedef struct _LINK
{
int data;
struct _LINK* next;
}LINK; 假设此时有32个线程在访问链表，那么可以定义一个全局变量value，每一个bit表示一个thread，读操作怎么进行呢，
void read_process()
{
int index = get_index_from_threadid(GetThreadId());
InterLockedOr(&value, 1 << index);
/* read operation */
InterLockedAnd(&value, ~(1<< index));
} 那么，写操作怎么进行呢，
void write_process_add(LINK* pHead, LINK* pLink)
{
/* add link to the tail of list */
}
void write_process_del(LINK* pHead, LINK* pLink)
{
delete_link_from_list(pHead, pLink);
while(1){
if(0 == value)
break;
Sleep(100);
}
free(pLink);
} 其中链表的删除操作为，
/*
* From:
* -> a -> b -> c -> d
*
* To:
* -----------------
* | V
* -> a b -> c ->d
*
*/ 总结： （1）这种无锁链表有很多局限：多读少写、注意使用原子操作、不能删除头结点、数据只能添加到尾部、注意删除顺序和方法、读线程个数有限制等等； （2）写操作在操作前需要等待所有的读操作，否则有可能发生异常； （3）写操作不能被多个线程使用； （4）无锁链表应用范围有限，只是特殊情况下的一种方案而已。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-01-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读