On 11/15/2013 11:26 AM, Gedare Bloom wrote: > On Fri, Nov 15, 2013 at 12:12 PM, Joel Sherrill > <joel.sherr...@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.sherr...@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@rtems.org >> http://www.rtems.org/mailman/listinfo/rtems-devel -- Joel Sherrill, Ph.D. Director of Research & Development joel.sherr...@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@rtems.org http://www.rtems.org/mailman/listinfo/rtems-devel
