Hi, I am looking for a queue structure which can handle elements with different priorities. Let say a thread can handle three different messages A, B and C. A messages have a bigger priority than B messages and B messages have bigger priority than C message. Here is an illustration of what I am looking for. This example is with a queue length of 6. At the beginning the queue is empty (next element popped is the one to the right): First we add a message B noted B1 -> [0 0 0 0 0 B1] Then message C noted C1 -> [0 0 0 0 C1 B1] Then message A noted A1 -> [0 0 0 C1 B1 A1] -> A1 is pushed in front of the queue because the A1 priority is Higher Now another message B noted B2 -> [0 0 C1 B2 B1 A1] -> B2 is placed before C1 because it has an higher priority than C1 An improvement could be to choose if the messages are pushed in back or in front compare to his priority: Push another message B noted B3 in front of his priority -> [0 C1 B2 B1 B3 A1] This kind of queue seems usefull but i didn’t find any questions or implementation of this. Is there any reasons to don’t use it? By using one queue for each priority this problem can be solved by using several Queue with queue set but it will not be flexible and efficient. Did someone already needed it ? How this problem is solved using freeRTOS ? Thank you Regards, Mickaël

At the moment the only options are to push to the back of a queue, or insert high priority message into the front of a queue. This fits most use cases. Even inserting into the front of a queue is rare, but can be used to insert control messages (for example, insert a message that tells a task to stop processing following messages until a lost link comes back online).

One thought for how to do it with just a few levels of priority would be to make a seperate queue for each priority, and then have a counting semaphore to keep track of how many messages are available. To post a message, add it to the appropriate queue and then increment the semaphore. The consuming task decrements the semaphore (and blocks while it is zero), and then tries to remove with 0 wait from each queue in order until it finds one. If you have a lot of levels, you might be able to implement it with a buffer to store the data, guarded by a mutex, with counting semaphores to block on as above for data to be ready (you may need a second one to allow blocking if the buffer is full). One big issue is that depending on the data packet size, sorting a new item may caus a need for a lot of data movement, so you might add a level of indirection, so you have one arrray of data that you don’t move, and a second array of just pointers keeping track of the order/free list.

Thanks for your answers, Real Time Engineers ltd, thanks for the warning, I will check if I really need this kind of queue. Richard Damon, If I need queues with different priorities (and if I have enough time) I will prefer to go with your second proposition. I think it is cleaner. In RTOS, as the semaphore are based on queues, I was thinking about using one queue instead of two counting semaphores to block on full and empty cases. What do you think? I will tell you wich solution I choose.

You need to block on your data block being full before you get access to the data block (so the reader can get access to empty a slot), and unblock the reader after you access the data block to fill the data, so you can’t use a single syncronization object unless you make sure the writers are always higher priority than the reader, and never block during the fill operation, otherwise the reader can get started looking for data before it is there.

Maybe I misunderstood something but the queues are double synchronization objects. I could use one queue instead of two semaphore because queues block on empty and full states. Anyway I will look deeper to understand how the FreeRTOS queues work.

The problem with using a single counting semaphore to block a task if the priority queue if full or empty is that the adding task needs to signal the semaphore before adding data to the storage structure so that it blocks if the structure is full, but if that is the only semaphore, then the reading task if it is of higher (or possibly same) priority starts then, but the data isn’t in the structure yet, and there isn’t anything left to pend on to wait for it. This option did NOT store the data in a FreeRTOS queue, but an ordinary memory structure protected by FreeRTOS primatives. Yes, if you are using the option of having a couple of FreeRTOS queus to store the data, then you only need 1 counting semaphore (or perhaps a queue set) for the reader to wait for before testing for the data.