Blocking on multiple queues (revisited)

jcwren wrote on Wednesday, March 12, 2008:

Back in 2005/2006 there was some discussion about being able to block on multiple queues.  An example was given of a task waiting on two serial port queues and using a queue ID in the structure to determine the source.  This works well enough for queues of a similar type, but starts to break down when you have queues of differing types.  It also makes for less generic (and therefore easily reusable) code.

What I’d really like to see is an extension to xQueueReceive(), which I’ll call xQueueReceiveMultiple().  What I envision as an interface would be passing an array of xQueueHandles, the number of elements in the array, and a timeout value.  The return value would be the index of the queue handle which has data ready, or a value to indicate a timeout. 

My main application for this comes from user interfaces, where the main control task is waiting for timers to expire (the timers are implemented as a task, where a number of timers can be created without regard to their timeout value, and they’ll fire in order.  The RTC is used so the timer task can block), keyboard characters to be pressed, and serial or USB data to arrive.

It’s certainly possible to implement this by polling the various queues, but it lacks two important things:  The first is power management.  Since all my I/O is interrupt driven, I can put the processor into a low power mode.  The second (and arguably more important) is elegance.  It just ain’t there.

You mentioned recently about some nifty new improvements to FreeRTOS.  Any chance that support for blocking on multiple queues would be one of them?


rtel wrote on Wednesday, March 12, 2008:

Adding blocking on multiple queues is difficult using the current implementation - without compromising the code size at least.  Part of what makes so small is the embedding of event control within the queue and task primitives, rather than having it separate.

I am in active discussions currently with somebody regarding implementing event flags which would sort of do what you want, but I have yet to come up with (or have a suggestion put to me) an implementation for this that would be fast/deterministic.  Most implementations require lists to be traversed from within critical sections which is a big ‘no’ as far as I’m concerned.  The scheduler locking mechanism employed by could be used to alleviate this but it would not be elegant.

Can your controller task not get all the data from the various sources on one queue by posting a structure to the queue:

typedef struct
____portBASE_TYPE xDataType;
____void *pxData;
} xQueueData;

Where xDataType could be a constant or enum to say whether the data pointed to by pxData is a keypress, USB data, or any other type of data.

I think this type of scheme might be what you have discounted in your post, but I’m not sure.

If you blocked on multiple queues, how would you know which queue it was that caused you to unblock?


jcwren wrote on Wednesday, March 12, 2008:

>If you blocked on multiple queues, how would you know which queue it was that caused you to unblock?

In my suggested implementation where an array of queues is passed in to block on, the function would return the index entry of the array that unblocked.  A timeout would be indicated by either a -1, returning a value larger than the number of entries in the array, or possibly reserving index 0 to indicate a time (don’t like that idea much).

On the suggestion for adding a queue data or ID type, that’s certainly doable.  It just means queues are larger (admittedly, by only a byte or int), but I feel it removes a degree of portability.  It requires all projects that might re-use this code to implement queues with an ID byte.

I understand what you’re saying about the fast/deterministic issue. 


anonymous wrote on Thursday, March 13, 2008:

For event flags if there is only one ‘consumer’, then whenever a flags get set they can be posted to a queue that the consumer waits on. Flags can be cleared (typically by the comsumer) without queueing. The flags themselves are protected by a mutex or semaphore (so it is a 2 queue implementation, actually).

This scheme doesn’t need kernel changes, just a veneer over the queue primitive (like semaphores).

This is just a proposal. I have thought about it in the past but have never actually implemented it. Maybe there are some gotcha’s I haven’t picked upon.

I think event flags can then be used to front waiting on multiple queues. That’s where I started myself in fact, but never implemented the scheme because another design presented itself. It is based on an event registration/distribution mechanism more appropriate to our situation.