[cpp]
一、何谓无锁队列
一、何谓无锁队列无锁队列，顾名思义，即不需要加锁的队列；之所以不需要额外加锁，是因为其本身已经是线程安全的。
二、为什么要在队列中集成线程安全的机制？
这里我想采用对比的方式来讲述。有锁队列，这可能是最简单的一种队列了，比如我们在多线程情况下使用标准STD的deque，那么毫无疑问需要对其加锁。加锁其实是将协调过程交给了操作系统来管理，但无锁队列却是在CPU层面就做到了协调，所以在效率上会高很多。更详细的解释请参见http://www.searchtb.com/2012/10/introduction_to_disruptor.html
三、如何实现？
这里主要是采用ACS。
1. 定义队列。这里由于测试的缘故，队列节点内的数据比较简单。
[cpp]
/* ACS node define. */
typedef struct acs_node_t {
std::string id;
int index;
struct acs_node_t* next;
} acs_node_t;
/* ACS deque define. */
typedef struct acs_deque_t {
struct acs_node_t head;
struct acs_node_t* tail;
} acs_deque_t;
/* ACS node define. */
typedef struct acs_node_t {
std::string id;
int index;
struct acs_node_t* next;
} acs_node_t;
/* ACS deque define. */
typedef struct acs_deque_t {
struct acs_node_t head;
struct acs_node_t* tail;
} acs_deque_t;
2. 定义接口。这里定义了队列初始化，入队列以及出队列三个接口。
[cpp]
void acs_deque_init(acs_deque_t* deq);
int acs_deque_empty(acs_deque_t* deq);
void acs_deque_push(acs_deque_t* deq, acs_node_t* node);
acs_node_t* acs_deque_pop(acs_deque_t* deq);
void acs_deque_init(acs_deque_t* deq);
int acs_deque_empty(acs_deque_t* deq);
void acs_deque_push(acs_deque_t* deq, acs_node_t* node);
acs_node_t* acs_deque_pop(acs_deque_t* deq);
3.下面是接口的实现。
[html]
void acs_deque_init(acs_deque_t* deq)
{
if (deq) {
deq->tail = &deq->head;
deq->head.next = NULL;
}
}
int acs_deque_empty(acs_deque_t* deq)
{
if (!deq)
return 1;
return deq->head.next == NULL;
}
void acs_deque_push(acs_deque_t* deq, acs_node_t* node)
{
acs_node_t* q = NULL;
do {
q = deq->tail;
} while (InterlockedCompareExchangePointer((PVOID*)&q->next, 0, node) != q->next);
InterlockedCompareExchangePointer((PVOID*)&deq->tail, q, node);
}
acs_node_t* acs_deque_pop(acs_deque_t* deq)
{
acs_node_t* q = NULL;
do {
q = deq->head.next;
if (q == NULL)
return NULL;
} while (InterlockedCompareExchangePointer((PVOID*)&deq->head.next, q, q->next) != deq->head.next);
return q;
}
void acs_deque_init(acs_deque_t* deq)
{
if (deq) {
deq->tail = &deq->head;
deq->head.next = NULL;
}
}
int acs_deque_empty(acs_deque_t* deq)
{
if (!deq)
return 1;
return deq->head.next == NULL;
}
void acs_deque_push(acs_deque_t* deq, acs_node_t* node)
{
acs_node_t* q = NULL;
do {
q = deq->tail;
} while (InterlockedCompareExchangePointer((PVOID*)&q->next, 0, node) != q->next);
InterlockedCompareExchangePointer((PVOID*)&deq->tail, q, node);
}
acs_node_t* acs_deque_pop(acs_deque_t* deq)
{
acs_node_t* q = NULL;
do {
q = deq->head.next;
if (q == NULL)
return NULL;
} while (InterlockedCompareExchangePointer((PVOID*)&deq->head.next, q, q->next) != deq->head.next);
return q;
}接口采用了Windows的ACS函数，当然你也可以将其更改为linux版本的ACS函数。
4. 其他代码为测试代码，全部代码为
[cpp]
#include
#include
#define WIN32_LEAN_AND_MEAN
#include
#include
static const int knThreadCount = 4;
static const int knMaxNodeCount = 50000;
static const int knPopedCount = 5000;
/* ACS node define. */
typedef struct acs_node_t {
std::string id;
int index;
struct acs_node_t* next;
} acs_node_t;
/* ACS deque define. */
typede