On Sun, Nov 17, 2013 at 7:04 PM, Pavel Pisa <ppisa4li...@pikron.com> wrote: > Hello Gedare and Sebastian, > > there is my opinion and list of other relevant documentation > sources from Linux kernel. > > On Friday 15 of November 2013 18:40:40 Gedare Bloom wrote: >> On Fri, Nov 15, 2013 at 12:27 PM, Joel Sherrill >> >> <joel.sherr...@oarcorp.com> wrote: >> > 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? > > I expect that you do not attach (double linked) list to each allocated > priority. I.e. waiters would be directly inserted into R-B tree. > Then complexity is not bounded by maximal number of priorities > but by maximal number of threads waiting on given queue. > This can (in the theory) mean to use > 2 x log2(CONFIGURE_MAXIMUM_POSIX_THREADS + CONFIGURE_MAXIMUM_TASKS) > compare operations for search. The insert requires same maximal number > for search and traceback + that fixed maximal number of rotations > to balance. Delete by node pointer when parent pointer is present (if > I remember well this is RTEMS R-B case) requires only limited > number of rotation and same maximal traceback as insertion. > Thanks, you're right about the limit being due to threads not priorities.
> But anyway the actual result would be much better for larger amount > of waiters than linear search and insert in double linked list. > If you consider that competing tasks groups can differ in only in single > priority level then solution with fixed O(1) insert and removal time > is to have double linked list for each priority (256) for each wait queue. > This is nonsense. 4 queues are some compromise but in most cases it is > waste with list heads. There is no other option then full priority queue > for EDF and other schedulers because their "priorities" are finegrained > and cannot be distributed to the fixed number of queues. > Right. The current block protocol in RTEMS uses 4 queues with (IIRC) a non-uniform distribution of the priorities among the 4. > Above means that only reason to consider between R-B and double linked > list selection is R-B overhead for case of 1 and up to 4 waiters where > simpler linear search wins most probably. On more powerfull CPUs > with deeper queues is the main problem miss-prediction in left or right > condition in search. This can be optimized by conditional move/computed > index into left/right child pointers array. > > I have considered actual wait queues implementation in RTEMS as acceptable > compromise but with significant weakness and even show stopper for larger > applications where 10 or more tasks waits for same semaphore. > I would be very happy if implementation is changed to more scalable > one but some minimal timing tests should be run to that overhead for > case of 1, 2, 3, and 4 waiters is acceptable. When R-B tree is used > then optimized case for 1 would be with minimal overhead, for 2 maximal > and for 4 already winning for some priorities insert order sequences. > > One reason for choice of R-B tree for priority queues can be that Linux > kernel uses these in many similar places as well (scheduler, timers, etc). > But for mutexes with full priority inheritance other structure is used > in Linux kernel. It is plist which holds one double linked list of > all nodes (i.e. waiters) and other double linked list where only > the first node of given priority is stored. > > * pl:prio_list (only for plist_node) > * nl:node_list > * HEAD| NODE(S) > * | > * ||------------------------------------| > * ||->|pl|<->|pl|<--------------->|pl|<-| > * | |10| |21| |21| |21| |40| (prio) > * | | | | | | | | | | | > * | | | | | | | | | | | > * |->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<->|nl|<-| > * |-------------------------------------------| > > http://lxr.free-electrons.com/source/include/linux/plist.h > > What is more important on Linux RT-mutexes implementation is > immediate priority adjustment/decrease when one of multiple > held mutexes is released by holding task. RTEMS does adjustment > only when all mutexes held by task are released. > The behavior is correct when RTEMS_STRICT_ORDER_MUTEX is enabled > but then code has to strictly follow release in reverse order > than acquire. > There is a small bug in RTEMS implementation: https://www.rtems.org/bugzilla/show_bug.cgi?id=2124 > Linux solves this problem that it has priority list in each mutex > which holds sorted list of all waiting tasks and yet another > priority list for each task which provides information about > all held mutexes which provides immediate information > what is required actual task priority. But it costs all these > lists manipulation for each mutex acquire and wait before acquire. > > http://lxr.free-electrons.com/source/Documentation/rt-mutex-design.txt > This was one design proposed for fixing the bug. It is a lot of management. > In theory, use of RB-tree for both these list structures (instead of plist) > should be better choice from algorithmic complexity point of view. > The lists heads can be even single pointer for R-B tree. I think not > the case for RTEMS R-B tree now. The node structures can be preallocated > in task and mutex tsructures. Task can wait on only one mutex at time > and mutex can be owned only by one task in maximum as well. > > But doing this right and to do full testing requires significant > effort. > Thanks -Gedare > Best wishes, > > Pavel > > > _______________________________________________ rtems-devel mailing list rtems-devel@rtems.org http://www.rtems.org/mailman/listinfo/rtems-devel
