Lock-free multi-thread solutions for multi-core and more - Parallel Scalable Solutions Main menu for Parallel Scalable Solutions
TransparentArrow hider
Blank background bar
The digital road leads to massively multi-core computers needing non-blocking programming

 
SERVICES
-  OFFERS
TECHNOLOGIES
   -  NON-BLOCKING 1(4)
   -  NON-BLOCKING 2(4)
   -  NON-BLOCKING 3(4)
   -  NON-BLOCKING 4(4)
 

 

 

 





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.

Arrow left PREVIOUS

NEXT Arrow right

Click here to view the swedish language version of the siteCreated by Kobolt.se, www.kobolt.se. ©2008 Parallel Scalable Solutions AB.
To home page