Red-Black-Tree for Priority Queues
joel.sherrill at OARcorp.com
Fri Nov 15 17:27:34 UTC 2013
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
> 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:
>>> 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.
>> 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
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
More information about the devel