Re: Red-Black-Tree for Priority Queues

2013-11-18 Thread Gedare Bloom
On Sun, Nov 17, 2013 at 7:04 PM, Pavel Pisa 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 >> >> wr

Re: Red-Black-Tree for Priority Queues

2013-11-18 Thread Sebastian Huber
Hello, thanks for all your input. I evaluate currently the RTEMS mutex with priority queues and priority inheritance as a role model. My aim is to determine what must be done to introduce fine grained locking on SMP. Currently we have one Giant lock (a recursive spin lock) that protects vi

Re: Red-Black-Tree for Priority Queues

2013-11-18 Thread Sebastian Huber
On 2013-11-15 21:54, Chris Johns wrote: On 16/11/2013 4:00 am, Sebastian Huber wrote: _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. Could you please explain the issue the _ISR_Flash

Re: Red-Black-Tree for Priority Queues

2013-11-17 Thread Pavel Pisa
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 > > wrote: > > With 256 priorities, what does that mean in practical se

Re: Red-Black-Tree for Priority Queues

2013-11-15 Thread Chris Johns
On 16/11/2013 4:00 am, Sebastian Huber wrote: _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. Could you please explain the issue the _ISR_Flash has in a little more detail ? chris@hu

Re: Red-Black-Tree for Priority Queues

2013-11-15 Thread Gedare Bloom
On Fri, Nov 15, 2013 at 12:27 PM, Joel Sherrill wrote: > On 11/15/2013 11:26 AM, Gedare Bloom wrote: >> On Fri, Nov 15, 2013 at 12:12 PM, Joel Sherrill >> wrote: >>> The current implementation has a bounded maximum >>> execution time. Does the Red-Black Tree have that >>> guarantee? >>> >> As I r

Re: Red-Black-Tree for Priority Queues

2013-11-15 Thread Joel Sherrill
On 11/15/2013 11:26 AM, Gedare Bloom wrote: > On Fri, Nov 15, 2013 at 12:12 PM, Joel Sherrill > 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 > dur

Re: Red-Black-Tree for Priority Queues

2013-11-15 Thread Gedare Bloom
On Fri, Nov 15, 2013 at 12:12 PM, Joel Sherrill 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 (

Re: Red-Black-Tree for Priority Queues

2013-11-15 Thread Joel Sherrill
The current implementation has a bounded maximum execution time. Does the Red-Black Tree have that guarantee? 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 con

Red-Black-Tree for Priority Queues

2013-11-15 Thread Sebastian Huber
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 po