Red-Black-Tree for Priority Queues

[Gedare Bloom]

On Fri, Nov 15, 2013 at 12:27 PM, Joel Sherrill
<joel.sherrill at oarcorp.com> wrote:
> On 11/15/2013 11:26 AM, Gedare Bloom wrote:
>> 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.
>
> With 256 priorities, what does that mean in practical search
> length? The insertion time is bounded once you find it.
>
I'm not certain, but here is a guess. If you had a perfectly balanced
tree of 256 nodes the tree would be 8 levels deep thus 8 node accesses
for a search. Since the imbalance in a red-black tree can be 2x, I
suppose there could be some node at level 8 and some node at level 16
in a really badly balanced tree. So the upper bound would be 16 nodes
accessed during a search. The insert/remove code will be similar, plus
the cost of at most 3 rotations.

I'm guessing the search through the block2N structure is much worse,
but probably the insert/remove is smaller once you know the slot?

-Gedare

>>> 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
>
>
>
> --
> 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