DaviesCircularQueue

DaviesCircularQueue theory overview rules design considerations fifo object The itemTable The Circular Part prove it (the code)

theory

overview

This is a very simple and elegant circular queue that protects data against concurrency issues without the use of mutexes. This powerful design was shown to me by a colleague though the origin is unknown (to me).

The source writes its data, then increments the write count. The destination reads the lastest data, then increments the read count. The number of items in the queue is the difference between the write and read count.

Item 0 doesn't matter anymore because its been read, Item 1 through 4 have been written to the queue and are waiting to be read. Soon Item 5 will finish copying and the write count will increment. Until then Item 5 is protected from reading despite the lack of a mutex.

rules

• Read and write count incrementing must be atomic. Additionally they must be unsigned to allow the counts to wrap.
• The number of items in the queue is small compared to the size of read and write count
• The read count is less than or equal to the write count

design considerations

The theory of this queue is pretty straight forward and the implementation isn't much more complex. I did this implementation in C because its intended for use in a kernel module however it would be easy to implement in any language and would be a bit more elegant. By passing around a pointer to the fifo I am able to emulate this in C++.

fifo object

The main 'object' is the fifo struct. It contains the read and write counts as well as basic information about the fifo members. The fifo contains items which can be any type of data, in this case they are arrays of integers. The fifo has numItems positions available for the items. Each item has itemSize number of elements in it (think length of the array) and dBytes is the number of bytes in each element in the item (in this case 16-bit integers so dBytes=2).

itemTable is the magic of the fifo structure. It is a pointer to another block of memory that contains pointers to the actual data buffers. When the fifo is initialized itemTable allocates enough space for numItems pointers, or said another way, allocates an array that is numItems long.

typedef struct fifo
{
   unsigned int  written;    //count of items that have been written
   unsigned int  read;       //count of items that have been read
   unsigned int  numItems;   //number of items in the queue
   unsigned int  itemSize;   //size of each item in the queue 
   unsigned int  dBytes;     //size of a dataBit in an item   
   unsigned int* itemTable;  //pointer to the itemTable (more pointers are stored in the table)
} fifo;

The itemTable

Like I said above the itemTable is a table that points to the fifo items. It doesn't contain the actual data, just where to look for the actual data. During initialization the fifo allocates enough space to store an entire item (in the example it allocates an array that is 1024 long and stores 16-bit integers, therefore it allocates 2048 bytes per item) and then stores the location of the memory in the itemTable. This is usually where people lose C but stay with me.

Reviewing the image above you can see that when item 6 is added to the buffer it will be written to the first slot where item 1 is now. Item 1 will have to be read out of the fifo before item 6 can be written or that data will be lost. Because this is a circular buffer the head is constantly moving - after item 1 is read then item 2 becomes the head of the buffer and the location that item 1 was in becomes the tail of the buffer.

The Circular Part

The advantage of this circular buffer is there is a fixed amount of memory needed and it can all be allocated at initialization and is entirely managed internally. As the client you merely need to push and pop data from it. The fifo is initialized with some number of slots so once all of those slots are filled the internal organization wraps the write buffer back to the first postiion. The reader can't fall too far behind or data will be lost. Its the programmers choice if the newer or old data should be lost, but it will be lost if the reader falls behind and the writer laps it.

prove it (the code)

Here is my userspace implementation of the Davies Queue in C. The queue code is seperated from the example code so you can include it in your projects if you like. There isn't much to using it. Just initialize a fifo structure with your queue requirements and use FifoPut and FifoGet to push and pop buffers into the fifo.

ok, this is why you are here

• fifo.c: fifo function declarations
• fifo.h: fifo definitions and function prototypes
• fifo_demo.c: fifo example usage
• build.sh: simple script to build this demo

-- ChristopherPepe - 19 Jun 2007