Red-Black-Tree for Priority Queues

[Gedare Bloom]

On Fri, Nov 15, 2013 at 12:12 PM, Joel Sherrill
<joel.sherrill at oarcorp.com> wrote:
> The current implementation has a bounded maximum
> execution time. Does the Red-Black Tree have that
> guarantee?
>
As I recall, the red-black tree has an upper bound of 3 rotations
during an insert/remove, and the balance is bounded by 2x (meaning
there are at most twice as many nodes between the root and the
furthest leaf as there are from the root to the closest). In practice,
I think this means one could establish bounds on the execution time
through this data structure.

> Technically the code to unroll the loop could be
> deleted. In either case, how long would interrupts
> have to be disabled?
>
> On 11/15/2013 11:00 AM, Sebastian Huber wrote:
>> Hello,
>>
>> I consider to replace the current priority queue implementation used for thread
>> queues (not the scheduler ready queue) with red-black trees.  Currently we use
>> four chains and linear operations in the corresponding priority subset.  A
>> red-black tree root can be reduced to at most four pointers.  The four chain
>> controls need twelve pointers in contrast.  It helps also to simplify complex
>> functions like _Thread_queue_Enqueue_priority() which use _ISR_Flash().  Usage
>> of _ISR_Flash() will be highly problematic in case we introduce fine grained
>> locking for SMP.
>>
>> I have a question regarding the current red-black tree implementation.  In case
>> the key to insert is already present (multiple) times in the tree, are there
>> ordering guarantees with respect to the nodes with the same key?  Can I for
>> example insert a key so that the new node is minimal/maximal with respect to
>> the existing nodes with the same key value?
As I recall, the implementation is a stable priority queue, meaning
there is FIFO order among the duplicated keys. We can consider adding
an option for LIFO order if it would be useful. For scheduling
threads, we prefer FIFO to break ties to avoid starvation.

-Gedare

>>
>
>
>
> --
> Joel Sherrill, Ph.D.             Director of Research & Development
> joel.sherrill at OARcorp.com        On-Line Applications Research
> Ask me about RTEMS: a free RTOS  Huntsville AL 35805
> Support Available                (256) 722-9985
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel