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.
> 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 _______________________________________________ rtems-devel mailing list rtems-devel@rtems.org http://www.rtems.org/mailman/listinfo/rtems-devel
