Red-Black-Tree for Priority Queues

[Joel Sherrill]

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.

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