Fifo Queue

FIFO Queue

1 din 6

http://dev.emcelettronica.com/print/52007

Your Electronics Open Source (http://dev.emcelettronica.com) Home > Blog > frabs's blog > Contenuti

FIFO Queue By frabs Created 10/23/2008 - 09:49

Programming FIFO fifo queue first in first out FIFO queue can be explained as: what comes first is served first, what comes next have to wait until the first is finished. But what are we talking about? In embedded systems very often data is made available from the external world to be handled by the firmware. Depending from system requirements and capabilities, the data can or, more likely, must be processed as soon as it is acquired. Other times, especially for certain peripherals, it can be, or must be processed later on, so no fuss no muss! This is our case. So the problem usually is: data is coming from an external source, I don't want to lose it, on the other hand, I will process it as soon as my application needs to do it. The base concept here is "First In First Out" aka FIFO (First In, First Out) like a queue at the post office, where Mr. Smith arrived at 8:00, Mr. Abey at 8:01 and Miss Green at 8:02, at the same front desk. The clerk at the front desk, whose shift begins at 8:05, will first attend Mr. Smith requests then Mr. Abey's and finally Miss Green's. The service order respects the arrival order. We want to implement this system in our software. The general idea is to create a memory area for the temporary storage of incoming data and a few functions to write and read data in this area (usually called buffer). Let's have a look at the following diagram:

We here assume an area of 8 locations (an 8 elements, zero based array called Buffer)

23.10.2008 22:16

FIFO Queue

2 din 6

http://dev.emcelettronica.com/print/52007

without specifing data type. We also declared three variables : writePosQ, readPosQ, countItemQ, inizializing all of them to zero. This layout identifies our queue prototype. At the beginning the queue is empty, and we can testify this status by observing : 1. countItemQ equals zero. 2. writePosQ equals readPosQ. Ok, keep in mind the previous observations, we will make use of them later on. Now, an external event makes datum "X" available and we want to insert it in the queue, so we use a function called insertDataQueue(), here described step by step : 1. Write "X" in the array element Buffer[writePosQ], since writePosQ equals zero this is equivalent to Buffer[0]="X". 2. Increment writePosQ. 3. Increment countItemQ. The following diagram shows queue status after the first insertion:

Suppose one more external event makes datum "Y" available, again we want to insert it in the queue: 1. Write "Y" in the array element Buffer[writePosQ], since writePosQ equals 1 this is equivalent to Buffer[1]="Y". 2. Increment writePosQ. 3. Increment countItemQ.. The following diagram shows queue status after the second insertion:

23.10.2008 22:16

FIFO Queue

3 din 6

http://dev.emcelettronica.com/print/52007

Let's stop here about data insertion, we move to analyze data extraction, but we will come back here, since we left a few open questions. In the mean while our application wants to know whether incoming data is available or not. So we can think about a function that returns queue status, let's call it isQueueEmpty. "isQueueEmpty will return true if the queue is empty, false otherwise". A few paragraph ago, we noted that a queue is empty when countItemQ equals zero. So why don't we re write the previous definition in the following way ? "isQueueEmpty will return true if countItemQ equals zero, false otherwise". So far so good. Now we want to extract element from our queue with a function called extractDataQueue() here described step by step: 1. Return the array element Buffer[readPosQ], since readPosQ equals zero this is equivalent to return Buffer[0]. 2. Increment readPosQ. 3. Decrement countItemQ. The following diagram shows queue status after the first extraction:

Since the queue is not still empty (isQueueEmpty() tells us so..), we want to extract one more element from our queue calling again extractDataQueue(): As from the previous explanation: 1. Return the array element Buffer[readPosQ], since readPosQ equals one this is

23.10.2008 22:16

FIFO Queue

4 din 6

http://dev.emcelettronica.com/print/52007

equivalent to return Buffer[1]. 2. Increment readPosQ. 3. Decrement countItemQ.. The following diagram shows queue status after the second extraction:

Calling again isQueueEmpty() returns True, so we go on with our business. It looks quite simple to implement, and we all love simple things.... In the following C source you can find a first step implementation of these functions, assuming our incoming data are chars from a serial port. // Set the maximum queue length #define MAXQUEUELEN 8 #define QUEUEMASK MAXQUEUELEN-1 // Declare queue variables int writePosQ=0, readPosQ=0, countItemQ=0; char Buffer[MAXQUEUELEN]; // Returns TRUE if queue is empty int isQueueEmpty() { int retval=TRUE; if(countItemQ!=0) { retval=FALSE; } return retval; } // Inserts a new item in the queue void insertDataQueue(char d) { // Check if queue is not full if(countItemQ!=MAXQUEUELEN) { // There is still room for data Buffer[writePosQ]=d; // Move write pointer to next location writePosQ++; // Make it circular writePosQ&=QUEUEMASK; // On more item inserted, count it. countItemQ++; } } // // //

Extracts a new item in the queue We here assume we already tested queue status, and found data is available. So no further control is done on queue status.

23.10.2008 22:16

FIFO Queue

5 din 6

http://dev.emcelettronica.com/print/52007

char extractDataQueue(void) { char retval='\0'; retval=Buffer[readPosQ]; // Move write pointer to next location readPosQ++; // Make it circular readPosQ&=QUEUEMASK; // On more item extracted, count it. countItemQ--; return retval; }

Observing the code, we can see we tackled a couple of issues previously left open : 1. Circular Array 2. Buffer Overrun What should I do when one of the two pointers (writePosQ, readPosQ) reaches the end of the buffer array ? Simple, we set it back to the beginning of the buffer array. It's like a dog biting its own tail... we call this kind of structure circular array. This is done by the bitwise AND operation (&). This method is convenient in terms of speed, bitwise AND are fast. On the other hand it forces the programmer to use as MAXQUEUELEN powers of two (1,2,4,8,16,32,64,128,256,512....), and sometimes available RAM is not that much... If RAM (and not speed) is the issue then we can use MAXQUEUELEN sizes that are the right balance between RAM cost and system performance. In this case we must rewrite the code in the following way: // Make it circular if(readPosQ==MAXQUEUELEN) { readPosQ=0; }

What if the estracting process is slower than the inserting one? For this error, called buffer overrun we have two choices : 1. We loose all incoming data exceeding buffer size, existing data in the buffer is not overwritten. 2. We overwrite the last buffer location with the incoming data. Which of the two options should we adopt ? The first one makes more sense to me (take a look at the code again..), but there could be cases where number two is a better choice. As a matter of fact if a buffer overrun happens, we should seriously think to go back to the blackboard, and think again about system performance, capabilities and buffer dimensions.... Just a little usage example: void main(void) { while(1) { ................ ................

23.10.2008 22:16

FIFO Queue

6 din 6

http://dev.emcelettronica.com/print/52007

// Make sure incoming data is available if(EXERNALDATAAVAILABLE) { data=READPORT(); insertDataQueue(data); } ................ ................

while(!isQueeueEmpty()) { // Extract and process data mean=extractDataQueue(); // Do what you need ................ ................ ................ ................ } } }

Though the code is written in C, it can be easily implemented in other high level languages, and test it on your desktop computer. Anyway, please do note that when I wrote this code I assumed: Only one queue is managed in the program. Code is not optimized to handle more queues. Access to Buffer is not concurrent, meaning while an extraction is made no insertion is permitted and viceversa. This also means that if you adopt this code as it is in an application using queues in ISR, or in RTOS you are going to smash your face in a very hard wall.. Thinking about it, perhaps next article could focus on these two issues.... In the meanwhile, have fun. Trademarks

Source URL: http://dev.emcelettronica.com/fifo-queue

23.10.2008 22:16