Why there aren't a single functions to query whether a queue is empty/full?

[Xavier]

Hi,

Why aren’t there functions to query whether a queue is empty/full?

While working with queues I wanted to fill one of them before being processed, but my program crashed. This problem has been around for a while (Check if queue is empty! - #13 by system) and FreeRTOS hasn’t add since then a single QueueIsEmpty() or QueueIsFull() queries. This next code, although logically correct, doesn’t work:

void producer_task( void* pvParameters )
{
   int data = 10;

   Serial.println( pcTaskGetName( NULL ) );

   while( 1 )
   {
      vTaskDelay( pdMS_TO_TICKS( 500 ) );

      while( uxQueueSpacesAvailable( g_queue_handler ) > 0 ){

         if( xQueueSend( g_queue_handler, (void*) &data, pdMS_TO_TICKS( 100 ) ) == pdFALSE ) {
            Serial.print( "TO(W): " );
         }

         data += 10;

         vTaskDelay( pdMS_TO_TICKS( 10 ) );
         // I simulate a delay on filling the queue
      }
   }
}

I already know that I can use the xQueueSend() return value to determine when the queue is full but, What if I only want to know whether the queue is full, without doing anything else? There are cases in which one needs to fill the queue before it’s used.

This next code works partially, but it is not what I want:

void producer_task( void* pvParameters )
{
   int data = 10;

   Serial.println( pcTaskGetName( NULL ) );

   while( 1 )
   {
      vTaskDelay( pdMS_TO_TICKS( 500 ) );

      while( xQueueSend( g_queue_handler, (void*) &data, 0 ) == pdTRUE ){ // I got stuck in this loop
         data += 10;
         vTaskDelay( pdMS_TO_TICKS( 10 ) );
      }
   }
}

void consumer_task( void* pvParameters )
{
   Serial.println( pcTaskGetName( NULL ) );

   while( 1 )
   {
      int data;

      while( xQueueReceive( g_queue_handler, &data, pdMS_TO_TICKS( 600 ) ) == pdTRUE ){
         Serial.println( data );
      }
   }
}

I could also use a for loop since I-fill-then-empty the queue:

void producer_task( void* pvParameters )
{
   QUEUE_TYPE data = 10;

   Serial.println( pcTaskGetName( NULL ) );

   while( 1 )
   {
      for( uint8_t i = 0; i < QUEUE_ELEMS; ++i ){
         if( xQueueSend( g_queue_handler, (void*) &data, pdMS_TO_TICKS( 100 ) ) != pdFALSE ){
            data += 10;
            vTaskDelay( pdMS_TO_TICKS( 10 ) );
            // I simulate a delay on filling the queue

         } else{ // timeout:
            Serial.println( "TO(W)" );
         }
      }

      vTaskDelay( pdMS_TO_TICKS( 500 ) );
   }
}

But under this schema, the functions uxQueueSpacesAvailable() and uxQueueMessagesWaiting() what are good for?

Thank you!

[RAc]

Hi Xavier,

there is xQueuePeek() as a test for emptiness, which I’m sure you know…

Please keep in mind that the current status of a queue is subject to race conditions. So if you could query a queue’s state and then make a decision what to do next depending on the result, the queue’s status may be changed by another thread of execution in the mean time, meaning you take the wrong path of decision.

I’m still not sure if I see a valid use case for testing on a full queue outside of an attempt to truly post something (in which case testing the return value would give you the “atomic” desired result). Could you outline such a case?

Thanks!

[richard-damon]

You mention the functions uxQueueMessagesWaiting() (Will return 0 if the Queue is empty), and uxQueueSpacesAvailable() (Will return 0 if Queue is full), but don’t say why they don’t meet your needs. Are you asking for a function to BLOCK until a queue is not empty or not full?

I don’t see a real use case for needing to wait for that when I don’t want to actually add an item to or get an item from the queue.

Remember, without a LOT of program assumptions, just because there is space on a queue at one point, doesn’t mean there will be space a bit later, as some other task could put something on the queue. I suspect what ever use case you are thinking of would be better done some other way.

[Xavier]

Hi @richard-damon,

As I mentioned, and that was commented too here years ago, uxQueueSpacesAvailable() fails:

while( uxQueueSpacesAvailable( g_queue_handler ) > 0 ){ // <-- Program gets stucked here
  
     // program never comes here:
     if( xQueueSend( g_queue_handler, (void*) &data, pdMS_TO_TICKS( 100 ) ) == pdFALSE ) {
        Serial.print( "TO(W): " );
     }

     data += 10;

     vTaskDelay( pdMS_TO_TICKS( 10 ) );
     // I simulate a delay on filling the queue
  }

The system gets stucked in uxQueueSpacesAvailable(). I’ll very happy if you (and @RAc) point me out to the problem with this line of code:

while( uxQueueSpacesAvailable( g_queue_handler ) > 0 ){ // <-- Program gets stuck here

And for that matter, in this code too:

      while( uxQueueMessagesWaiting( g_queue_handler ) > 0 ){ // <-- Program gets stucked here too

There are so many real cases, many of them fitting this next scenario: there’s a task that receives serial streams from a serial channel using some protocol. Such task decodes the streams and sends the COMPLETE payload (or at least a known number of items) to a second task using a queue. That second task needs the whole payload before to proceed, so the decoder task MUST fill a queue with the data.

Every other way of determining whether the queue is full/empty suffers from the same race condition problem. I’ve been told (by @RAc) to use the xQueuePeek() function to query the queue emptyness; however, an item might arrive from when the program asks the question and when the program processes an (not longer anymore) empty queue.

Why haven’t you add a simple yes/no functions at task level to query whether a queue is full/empty given the race conditions will be always present in concurrent programs?

You won’t add such functions to FreeRTOS because of me, that’s clear, so let me rephrase the question: How would you fill a queue before it’s processed by a second task, and how this second task processes the queue item by item until it is empty once it’s full?

Thank you!

[RAc]

@Xavier

You won’t add such functions to FreeRTOS because of me, that’s clear, so let me rephrase the question: How would you fill a queue before it’s processed by a second task, and how this second task processes the queue item by item until it is empty once it’s full?

ok, that’s your use case? Only two tasks (no ISRs) involved, in which one task only feeds the queue, and the other then (higher priority I presume?) reads from it? Sort of a producer/consumer setup? In that case naturally you wouldn’t worry about race conditions.

My solution here would be to let task A feed the queue until the xQueueSend() fails and use that condition as a task notification for B to wake up and process the queue until empty, then wait for the next notification. The priorities would then ensure the rest of the control flow.

That scheme will probably work even if you have multiple producers, but the trouble would begin with multiple consumers.

[Xavier]

Hi @Rac,

there is xQueuePeek() as a test for emptiness, which I’m sure you know…

How do you query whether a queue is full?

Please keep in mind that the current status of a queue is subject to race conditions

Every concurrent program is subject to race conditions, even the xQueuePeek() function you mentioned above. (And for that matter every concurrent program is subject to starving, priority inversion, and deadlocks, too.)

Ccp: @richard-damon:

With the current FreeRTOS mechanisms, How do you fill a queue before it’s processed by a second task? And how do you read from an already full queue, item by item, until it’s empty? I already know the answer using for loops and the queue’s length. How do you ask for emptiness/fullness?

Greetings!

[RAc]

Xavier: Another thing to consider is that in that use case you outlined, you wouldn’t need a queue in the first place, just a static sized linear buffer that is protected by a reverse reader-writer lock or something compatible. The very idea of a queue is to act as a “shock absorber,” meaning it can handle a varying load of contents between a producer and a consumer. When that relationship is always fixed (meaning the buffer always gets filled up to the brim before being flushed), there is no need for a queue. You can use one in conjunction with the strategy I outlined (task noticications upon fill up), but you can also go for something much simpler…

Edit: Musing about it a little more, I believe one could simplify this task even more; you wouldn’t need a separate task to consume the entries. All you would need is a function called FillNextEntryInBufAndFlushWhenFull() that is called from all producers, of course reentrancy/ mutual exclusion ensured. The caller to fill in the last entry would cause the inline consumtion of all entries in turn, leaving an empty buffer when finished. No real need for concurrency in this scenario, methinks…

[rtel (Richard Barry)]

So far I’m confused by this thread

There is a question as to why don’t we add in functions that say whether the queue is full or not - but uxQueueSpacesAvailable() does that already.

Second there is mention of a race condition - yes in a multithreaded system if you first check if there is space and then post to the queue you cannot assume there is still space as other tasks and interrupts could have executed in the interim. Are you suggesting there should be an atomic function that does this? If so, then I think there are other ways of achieving the same - for example try writing to a queue with a block time of zero - if the write fails then the queue is full and you know the item did not get posted.

Finally, I would very much advise against using a queue for this scenario:

@Xavier

There are so many real cases, many of them fitting this next scenario: there’s a task that receives serial streams from a serial channel using some protocol. Such task decodes the streams and sends the COMPLETE payload (or at least a known number of items) to a second task using a queue. That second task needs the whole payload before to proceed, so the decoder task MUST fill a queue with the data.

as it is very inefficient. You could instead use a stream buffer, or manage a buffer yourself and just post a pointer to the buffer to the queue when it holds a full message.

[Xavier]

Hi @rtel

1. Stream buffers are meant for single_task-to-single_task communications. Although I’ve remarked in my example that one task fills the buffer whilst other task consumes it, in a bigger plane two or more tasks might fill the queue before it’s consumed. I’ve also pointed it out that a solution with a for loop, along the queue’s size, works.

2. I’ve mentioned several times in this thread that uxQueueSpacesAvailable() doesn’t work. I’ll do it again, it’s free: uxQueueSpacesAvailable()` doesn’t work as the next snippet shows:

   while( uxQueueSpacesAvailable( g_queue_handler ) > 0 ){ // <-- Program gets stucked here!
   
       // program never comes here:
       if( xQueueSend( g_queue_handler, (void*) &data, pdMS_TO_TICKS( 100 ) ) == pdFALSE ) {
          Serial.print( "TO(W): " );
       }
   
       data += 10;
   
       vTaskDelay( pdMS_TO_TICKS( 10 ) );
       // I simulate a delay on filling the queue
   }
   

3. Let me ask again, if you don’t mind: How does a task can query whether a queue is fill/empty? I wonder myself, Why are there such functions for ISR like xQueueIsQueueEmptyFromISR() and xQueueIsQueueFullFromISR(), but there are not functions alike for regular tasks?

Greetings !

[Xavier]

Hi!

Ok, bad example as I couldn’t explain myself. My mistake. Let’s come back to the question, why this code doesn’t work:

void producer_task( void* pvParameters )
{
   int data = 10;

   while( 1 )
   {
      vTaskDelay( pdMS_TO_TICKS( 500 ) );

      while( uxQueueSpacesAvailable( g_queue_handler ) > 0 ){ // Program gets stucked here, why?

         // EDIT: Program never comes here:
         if( xQueueSend( g_queue_handler, (void*) &data, pdMS_TO_TICKS( 100 ) ) == pdFALSE ) {

            Serial.print( "TO(W): " );
         }

         data += 10;

         vTaskDelay( pdMS_TO_TICKS( 10 ) );
      }
   }
}

There was a guy (here) that pointed this problem out years ago, and his question was never answered.

Greetings !

[rtel (Richard Barry)]

Is it right then to reframe the original post to “the function used to query if a queue is full doesn’t work - please fix it”?

If my understanding is correct now then we can create a test case that demonstrates the issue to route cause it and fix it - knowing there is a regression test in place should the issue ever be repeated. Ignoring the variable declarations and return value - the implementation is actually only three lines: https://github.com/FreeRTOS/FreeRTOS-Kernel/blob/main/queue.c#L2001

[RAc]

@Xavier

    taskENTER_CRITICAL();
    {
        uxReturn = pxQueue->uxLength - pxQueue->uxMessagesWaiting;
    }
    taskEXIT_CRITICAL();

Actually, the source for uxQueueSpacesAvailable() is very straightforward (see above). The only way that this can block is if it is being called with the critical section taken - assuming that the implementation of the CS is correct, of course.

In your code, there is no indication that the task calling uxQueueSpacesAvailable() has claimed the CS, so some external faulty code must have claimed and not released it yet. Which is obnoxious because that implies that no task switch to your task calling uxQueueSpacesAvailable() can have occurred.

You could put an assert in your code between the vTaskDelay() and uxQueueSpacesAvailable() calls to check that the CS is not taken.

Edit: Unless, of course, this would be yet another manifestation of too small an application stack…

Yet another Edit: Or do you mean by “stuck” that the condition always holds, meaning the queue never gets “full”? Could it be that the 100ms delay could be enough for the other task to believe it has a full queue and work off the (in that case single) entry? What is the consumer code corresponding to the latest producer code you posted?

I still believe that the strategy you pursue here is error prone and the use case could be solved more elegantly…

[richard-damon]

@RAc, actually in the official version of FreeRTOS there can never be a block on taskENTER_CRITICAL, as all that function does is issue a disable interrupts command and increment a. critical section counter. Yes, in a SMP variant of FreeRTOS, it might need to acquire some cross processor mutex.

@Xavier, as explained, uxQueueSpacesAvailable is exactly a ‘is queue full’ query, that will always return the answer, so can’t ‘get stuck’ in the normal meaning.

[RAc]

@richard-damon

actually in the official version of FreeRTOS there can never be a block on taskENTER_CRITICAL, as all that function does is issue a disable interrupts command and increment a. critical section counter.

Of course you’re right, thanks for the clarification. Like you, I got confused by the word “stuck” which to me reads “hangs.” Of course my own continuation (that the task would never get to that point if the CS had been claimed) should have triggered me to rethink. Sorry!

[hs2 (Hartmut Schaefer)]

Program gets stucked… in a function which doesn’t block is strange…
@Xavier Is it possible that g_queue_handler is not (yet) initialized ? Or get’s the program stuck in your configASSERT defined or stack overflow handler ?

[Xavier]

Hi,

It’s initialized correctly:

QueueHandle_t g_queue_handler = NULL;

#define QUEUE_ELEMS ( 10 )
#define QUEUE_TYPE int
#define QUEUE_TYPE_SIZE ( sizeof( QUEUE_TYPE ) )

void setup()
{
   xTaskCreate( producer_task, "PROD", 128 * 3, NULL, tskIDLE_PRIORITY + 1, NULL );

   xTaskCreate( consumer_task, "CONS", 128 * 3, NULL, tskIDLE_PRIORITY, NULL );

   pinMode( 13, OUTPUT );
   Serial.begin( 115200 );
   Serial.println( "OUT OF RESET" );

   g_queue_handler = xQueueCreate( QUEUE_ELEMS, QUEUE_TYPE_SIZE );

   configASSERT( g_queue_handler );
   // Error creando a la cola

   vTaskStartScheduler();
}

[Xavier]

Hi,

English isn’t my mother tongue, so I confuse stuck with hang, but as you’ve mentioned, “the system hangs” is the correct expression.

[Xavier]

Hi to all @richard-damon, @rtel, @RAc and @hs2,

I found an interesting (miss)behavior in the code. I’ll show you the complete code at the end, but before this is the thing: without the else body in the consumer task (which has low priority) the system hangs (instead of “stuck”), and with the else body the system works as expected:

consumer_task(){

while( 1 )
{
      if( uxQueueMessagesWaiting( g_queue_handler ) > 0 ){
         // some code here that I'll show you later on
      } 

#if 0
      else{ // no data available:
         Serial.println( "ND" );
         vTaskDelay( pdMS_TO_TICKS( 200 ) );
      }
#endif  

} //while(1)

} // task

It’s not a problem with memory nor the queue initialization (I guess), it’s about my misunderstanding on what uxQueueMessagesWaiting() and uxQueueSpacesAvailable() does. It seems that

vTaskDelay( pdMS_TO_TICKS( 200 ) )

is playing a major role in the if-else construction.

Instead of printing large strings or using the configASSERT() macro (I’m working this project with Arduino UNO, which has limitations on its debugging capabilities) I used single letters to trace the program. Here is the complete program:

#include <FreeRTOS.h>
#include <task.h>
#include <queue.h>

QueueHandle_t g_queue_handler = NULL;

#define QUEUE_ELEMS ( 10 )
#define QUEUE_TYPE int
#define QUEUE_TYPE_SIZE ( sizeof( QUEUE_TYPE ) )

void producer_task( void* pvParameters )
{
   QUEUE_TYPE data = 10;

   Serial.println( "I'm the producer!" );

   while( 1 )
   {
      vTaskDelay( pdMS_TO_TICKS( 500 ) );

      Serial.println( "A" );

      while( uxQueueSpacesAvailable( g_queue_handler ) > 0 ){

      Serial.println( "B" );

         if( xQueueSend( g_queue_handler, (void*) &data, pdMS_TO_TICKS( 100 ) ) == pdFALSE ) {

            Serial.print( "TO(W): " );
         }

         data += 10;

         vTaskDelay( pdMS_TO_TICKS( 10 ) );
      }
   }
}

void consumer_task( void* pvParameters )
{
   Serial.println( "I'm the consumer!" );

   while( 1 )
   {
      Serial.println( "C" );

      if( uxQueueMessagesWaiting( g_queue_handler ) > 0 ){

      Serial.println( "D" );

         QUEUE_TYPE data;

         if( xQueueReceive( g_queue_handler, &data, pdMS_TO_TICKS( 500 ) ) == pdTRUE ){

            Serial.println( data );

         } else{ // timeout:

            Serial.print( "TO(R): " );
         }
      } 
#if 0
      else{ // no data available:
         Serial.println( "ND" );
         vTaskDelay( pdMS_TO_TICKS( 200 ) );
      }
#endif  

   } // while( 1 )
}

void setup()
{
   xTaskCreate( producer_task, "PROD", 128 * 3, NULL, tskIDLE_PRIORITY + 1, NULL );

   xTaskCreate( consumer_task, "CONS", 128 * 3, NULL, tskIDLE_PRIORITY, NULL );

   pinMode( 13, OUTPUT );

   Serial.begin( 115200 );

   Serial.println( "OUT OF RESET" );

   g_queue_handler = xQueueCreate( QUEUE_ELEMS, QUEUE_TYPE_SIZE );

   if( g_queue_handler == NULL ){

      Serial.println( "ERROR CREATING THE QUEUE" );
   }

   configASSERT( g_queue_handler );
   // Error creando a la cola

   vTaskStartScheduler();
}

void loop() {}

This screenshot shows the program’s output WITHOUT the else disabled (#if 0) in the consumer task:

This other screenshot shows the program’s output WITH the else enabled (#if 1) in the consumer task:

Greetings and thank you for your time and patience

PD: Do I need to create a new thread for this issue?

[richard-damon]

The thing to remember is that uxQueueMessagesWaiting will return immediately with the answer about if there are messages waiting. In your case if there are none, you immediately loop around and ask the question again, and just keep running that loop, possibly starving any task of a lower priority.

Generally, there is no reason to check if there is data in the queue or not, unless you have some other work to do in that case, and even then, I tend to just get the data with a zero timeout and act on it.

You really need to make sure that ALL tasks (except priority 0 tasks like IDLE) always block on something in their loop to let other tasks have time to run.

Also, if you don’t have preemption turned on, then even if a task is low priority, if it doesn’t block or yield, time will not be given to other tasks.

[Xavier]

@richard-damon

The thing to remember is that uxQueueMessagesWaiting will return immediately with the answer about if there are messages waiting. In your case if there are none, you immediately loop around and ask the question again, and just keep running that loop, possibly starving any task of a lower priority.

Yes, it seems to be an inversion priority problem somehow

@richard-damon

Generally, there is no reason to check if there is data in the queue or not, unless you have some other work to do in that case, and even then, I tend to just get the data with a zero timeout and act on it.

I just wanted to use the queues in the way I learnt they are used.

@richard-damon

You really need to make sure that ALL tasks (except priority 0 tasks like IDLE) always block on something in their loop to let other tasks have time to run.

Also, if you don’t have preemption turned on, then even if a task is low priority, if it doesn’t block or yield, time will not be given to other tasks.

My mistake. I assumed the consumer task was going to be preempted by tasks with higher priorities:

#define configUSE_PREEMPTION   1
#define configUSE_TIME_SLICING 0

But that advice of yours must be taken into account.

Is that possible that you write down the advice “Don’t use these functions as test expression in a while loop” in the official documentation?

Thank you all!