On Fri, Nov 15, 2013 at 12:27 PM, Joel Sherrill <joel.sherr...@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.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. > 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.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
