--- In liblf-dev@yahoogroups.com, Chris Purcell <chris.purcell.39@...>
wrote:
>
> There don't appear to be any memory barriers in your code. How are you
> avoiding the issue of out-of-order execution on multiprocessor machines?
>
> Chris

Thank you , Chris . Sorry for my poor english , I will try my best to
express my own opinion .
It is true that I don't use any memory barriers in my code and this queue
can only be used in single reader and single writer . First of all , we could
assume that the assignment is atomic on uniprocessor machine , Such as
int ret = 11 ;
in asm compiled by gcc 3.4.3 , it is
c7 45 fc 0b 00 00 00 movl $0xb,0xfffffffc(%ebp)

There are two key ways I used in the implementation :
1. Combination of queue with ring array ;
2.There is almost no same memory which the enqueue thread and the dequeue
thread need to access .
Look at the struct of queue_t :
#define MAX_RING_SIZE 3
typedef struct _queue_st queue_t ;
struct _queue_st{
qnode_t *nodes[MAX_RING_SIZE] ;

int enqueue ;
int dequeue ;

qnode_t *enlast ;
} ;

The enqueue function only use member enqueue/enlast/nodes , and the dequeue
function only use member dequeue and nodes . Nodes is a small ring array , when
enqueue function will put a node , it will find a NULL element of nodes ,
otherwise , it put this node into old link , pointed by member enlast ; if the
dequeue function want to get a node , it will get a node from a old link ,
indexed by member dequeue utill the link is NULL .
The enqueue function and dequeue function can not access the same memory
at the same time , only if queue_t's member enqueue is equal to dequeue . I
assume that the assignment is atomic on uniproccessor as before , so only after
queue->nodes[queue->dequeue] = NULL is successful , then enqueue function can
put its node to this link . On the other hand , only after queue->nodes[old] =
node is successful , then dequeue fucntion can get the node .
Even on multiproccessor machines , if movl instruction is atomic ,
the dequeue function only get the NULL value after odes[old] = node is
successful .
Best Regards .