Tag Archives: queue

Circular queues in Java

I’d like to see how deep the rabbit’s hole is, starting it with a quick round of Java queues. The most important one in low latency application context is the circular queues or ring buffers. These are the same. It’s a fixed size data buffer, connecting the end to the beginning creating a nice infinitive data ring, so your hamster could easily run around and around and around…

Another important architectural point of circular buffer is that it’s a FIFO (First In First Out) construction, easy data piping.

Major points of a low latency application:

  1. Lock Free
  2. Wait Free

Circular Buffer

Some major implementations

  • Fast Flow: FastFlow is a parallel programming framework for multicore platforms, which uses hybrid single-producer/single-consumer queues as a base underlying component for inter-thread communication
  • Thompson queue
  • Lamport queue: http://en.wikipedia.org/wiki/Lamport’s_bakery_algorithm

Basic Implementation

A possible implementation of this queue in Java is using an array based solution. It needs to enqueue the new items into the structure and to dequeue from there. It also needs to shift the data to the dequeued space in the array. Because it has always a fixed array size, it needs a starting array size and the implementation must be able to expand the size if it’s necessary.

Tagged , ,