Services Technologies
Non-blocking
|
3 (4) |
A
wait-free queue
We
will now explain of how one actually can
design non-blocking programs for larger
operations, as example for ordinary data
structures. In the code below the program
code is shown for a "wait-free" queue.
#define MAX_QUEUE_SIZE 1000
void *buffer[MAX_QUEUE_SIZE];
int volatile indexHead=0;
int volatile indexTail=0;
int Enqueue(void *item) {
int nextTail=(indexTail+1)%MAX_QUEUE_SIZE;
if(nextTail==indexHead)
return 0;
buffer[indexTail]=item;
indexTail=nextTail;
return 1;
}
void *Dequeue() {
void *item;
if(indexHead==indexTail)
return NULL;
item=buffer[indexHead];
indexHead=(indexHead+1)%MAX_QUEUE_SIZE;
return item;
}
It is
built upon a cyclic buffer for saving the
elements in the queue, where the index "indexTail"
indicates the next free position and "indexHead"
indicates the latest not collected position.
In order to make it wait-free, the variable
"indexTail" is only updated by the "Enqueue"
function, and the variable "indexHead" is
only updated by the "Dequeue" function.
Observe though that this queue
implementation only works for up to two
threads, one thread that are performing "Enqueue"
and another thread that is performing "Dequeue".
If we want to permit more threads, it
becomes at once much more complicated.
|