Let’s spend some time on FIFO queue construction. A FIFO is a First In First Out queue. There are two methods of manipulation. The first is general purpose, in that it will work with any number of readers (consumers) and writers (producers). It does require a lock (also called a mutex or semaphore) to prevent concurrent threads from corrupting global data.
The second FIFO queue method does not employ locking; therefore it can only be used in the case of a single reader and writer. The trick to this new implementation is that we allow one slot in the queue to be wasted. This is the result of the rule that the head of the FIFO queue must NEVER be equal to the tail. So instead of space for one semaphore, we use the space as a place counter in the queue. But notice how the code is simplier. And the code is faster since we removed the mutexes.
The following FIFO queue code (for both methods) creates and performs GETs and PUTs on a FIFO. Notice the wonderful use of debug code.
-----------------------------------------------------------------
METHOD ONE - for multiple readers and writers.
-----------------------------------------------------------------
/*
* First In First Out (FIFO) structure.
* This FIFO stores integers.
* The FIFO is actually a circular buffer.
* A semaphore is used to support multiple readers and writers.
*/
struct fifo_
{
inthead; // first item in the fifo
inttail; // last item in the fifo
intsize; // number of slots in space[]
intsemid; // semaphore id - used for locking
int*space; // array of integers
};
/*
* Sanity check a FIFO.
*/
void
fifo_check (struct fifo_ *fifo)
{
assert(fifo->head == -1 || (fifo->head >= 0 && fifo->head < fifo->size));
assert(fifo->tail == -1 || (fifo->tail >= 0 && fifo->tail < fifo->size));
if (fifo->head == -1)
assert(fifo->tail == -1);
else
assert(fifo->tail != -1);
if (fifo->tail == -1)
assert(fifo->head == -1);
else
assert(fifo->head != -1);
assert(fifo->semid);
assert(fifo->space);
}
/*
* Initialize a FIFO.
*/void
fifo_init (struct fifo_ *fifo, int size)
{
assert(size > 0);
fifo->size = size;
fifo->head = -1;
fifo->tail = -1;
fifo->space = (void **) malloc(size * sizeof(void *));
assert(fifo->space);
bzero(fifo->space, size * sizeof(int));
fifo->semid = create_sem();
fifo_check(fifo);
}
/*
* Increment a FIFO index.
* Perform wrap around if need be.
*/
int
fifo_index_add (struct fifo_ *fifo, int old_index)
{
intnew_index = old_index++;
if (new_index >= fifo->size)
new_index = 0;
return new_index;
}
/*
* Perform a PUT to a FIFO.
*/boolean
fifo_put (int item, struct fifo_ *fifo)
{
booleanans;
lock(fifo->semid);
fifo_check(fifo);
if (fifo->head == -1)
{
fifo->space[0] = item;
fifo->head = 0;
fifo->tail = 0;
ans = true;
}
else
{
intnew_tail = fifo_index_add(fifo, fifo->tail);
if (new_tail == fifo->head)
{
ans = false;
}
else
{
fifo->space[new_tail] = item;
fifo->tail = new_tail;
ans = true;
}
}
fifo_check(fifo);
unlock(fifo->semid);
return ans;
}
/*
* Perform a GET from a FIFO.
* Upon success, item is filled in.
*/
boolean
fifo_get (struct fifo_ *fifo, int *item)
{
booleanans;
intindex;
lock(fifo->semid);
fifo_check(fifo);
if (fifo->head == -1)
{
ans = false;
}
else
{
index = fifo->head;
*item = fifo->space[index];
bzero(&fifo->space[index], sizeof(int));
if (fifo->head == fifo->tail)
{
fifo->head = 0;
fifo->tail = 0;
}
else
{
fifo->head = fifo_index_add(fifo, fifo->head);
}
ans = true;
}
fifo_check(fifo);
unlock(fifo->semid);
return ans;
}
----------------------------------------------------------
METHOD TWO - one reader and one writer.
----------------------------------------------------------
/*
* First In First Out (FIFO) structure.
* This FIFO stores integers.
* The FIFO is actually a circular buffer.
* This FIFO only supports a single consumer and producer.
*/
struct fifo_
{
inthead; // first item in the fifo
inttail; // last item in the fifo
intsize; // number of slots in space[]
int*space; // array of integers
};
/*
* Sanity check a FIFO.
*/
void
fifo_check (struct fifo_ *fifo)
{
assert(fifo->head >= 0 && fifo->head < fifo->size);
assert(fifo->tail >= 0 && fifo->tail < fifo->size);
assert(fifo->space);
}
/*
* Initialize a FIFO.
*/
void
fifo_init (struct fifo_ *fifo, int size)
{
assert(size > 0);
fifo->size = size;
fifo->head = 0;
fifo->tail = 1;
fifo->space = (void **) malloc(size * sizeof(void *));
assert(fifo->space);
bzero(fifo->space, size * sizeof(int));
fifo_check(fifo);
}
/*
* Increment a FIFO index.
* Perform wrap around if need be.
*/
int
fifo_index_add (struct fifo_ *fifo, int old_index)
{
intnew_index = old_index++;
if (new_index >= fifo->size)
new_index = 0;
return new_index;
}
/*
* Perform a PUT to a FIFO.
*/
boolean
fifo_put (int item, struct fifo_ *fifo)
{
intnew_tail;
booleanans;
fifo_check(fifo);
new_tail = fifo_index_add(fifo, fifo->tail);
if (new_tail == fifo->head)
{
ans = false;
}
else
{
fifo->space[new_tail] = item;
fifo->tail = new_tail;
ans = true;
}
fifo_check(fifo);
return ans;
}
/*
* Perform a GET from a FIFO.
* Upon success, item is filled in.*/
boolean
fifo_get (struct fifo_ *fifo, int *item)
{
booleanans;
intnew_head;
fifo_check(fifo);
new_head = fifo_index_add(fifo, fifo->head);
if (new_head == fifo->tail)
{
ans = false;
}
else
{
index = fifo->head;
*item = fifo->space[index];
bzero(&fifo->space[index], sizeof(int));
fifo->head = new_head;
ans = true;
}
fifo_check(fifo);
return ans;
}