首页 > 程序开发 > 软件开发 > 其他 >

多线程的那点儿事(之无锁链表)

2011-12-14

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】前面,为了使得写操作快速进行,我们定义了顺序锁。但是顺序锁有个缺点,那就是处理的数据不能是指针,否则可能会导致exc...

【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】

前面,为了使得写操作快速进行,我们定义了顺序锁。但是顺序锁有个缺点,那就是处理的数据不能是指针,否则可能会导致exception。那么有没有办法使得处理的数据包括指针呢?当然要是这个链表没有锁,那就更好了。

针对这种无锁链表,我们可以初步分析一下,应该怎么设计呢?

(1)读操作没有锁,那么怎么判断读操作正在进行呢,只能靠标志位了;

(2)写操作没有锁,那么读操作只能一个线程完成;

(3)写操作中如果是添加,那么直接加在末尾即可;

(4)写操作中如果是删除,那么应该先删除数据,然后等到当前没有操作访问删除数据时,释放内存,但是首节点不能删除。

普通链表的结构为,

typedef struct _LINK

{

int data;

struct _LINK* next;

}LINK;

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 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);

}

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

*

*/

/*

* From:

* -> a -> b -> c -> d

*

* To:

* -----------------

* | V

* -> a b -> c ->d

*

*/

总结:

(1)这种无锁链表有很多局限:多读少写、注意使用原子操作、不能删除头结点、数据只能添加到尾部、注意删除顺序和方法、读线程个数有限制等等;

(2)写操作在操作前需要等待所有的读操作,否则有可能发生异常;

(3)写操作不能被多个线程使用;

(4)无锁链表应用范围有限,只是特殊情况下的一种方案而已。

相关文章
最新文章
热点推荐