Avoiding priority inversion with software design

On 2007-10-16, Paul Keinanen <keinanen@sci.fi> wrote:

>>If you've got less than nine tasks total, you can skip the
>>first step altogether and determine the highest priority task
>>in O(1) time time with 2-3 assembly instructions.
>
> Clever. 

Quite.  [I don't claim to have invented any of it.]

> So with 64 bit hardware, you first detect the first non-zero
> 64 word, after that you use 32 bit instructions to detect
> which 32 bit half contains the nonzero bit and repeating this
> with 16 bits will bring you down to the 8 bit case and with
> software to the 4, 2 and 1 bit cases. 

If you have enough tasks, it might be faster to start out with
bigger chunks.

>>Even with 9 or more tasks, the number of bytes is still usually
>>small enough that you can unroll the loop that's searchign for
>>the first non-zero byte and end up with something that's very
>>fast and still takes very little code space (maybe 300 bytes of
>>ROM space including the lookup table?).
>
> I guess that I am getting too old, since I think that using a 256 byte
> LUT on small hardware to find the highest bit set is quite
> extraordinary :-).  

It does seem sort of extravagant.  If the 256-byte lookup table
is a strain you can play tricks like using only 4 bits of every
byte and a 16-byte lookup table.  Or you can calculate the
highest bit number with 3 ANDs and a little bookeeping:

Here's the Python code for that:

def highestBitSet(m):
    n = 0
    if m & 0xf0:
        m &= 0xf0
        n |= 4
    if m & 0xcc:
        m &= 0xcc
        n |= 2
    if m & 0xaa:
        n |= 1
    return n

On a CPU like an ARM, that's pretty much one CPU instruction
per line of code.  Others might require a few conditional jumps
to be thrown in.
    
At that point, an unrolled shift-and-test loop is probably
about as fast.

-- 
Grant Edwards                   grante             Yow! Somewhere in Tenafly,
                                  at               New Jersey, a chiropractor
                               visi.com            is viewing "Leave it to
                                                   Beaver"!

On 2007-10-16, Grant Edwards <grante@visi.com> wrote:

> def highestBitSet(m):
>     n = 0
>     if m & 0xf0:
>         m &= 0xf0
>         n |= 4
>     if m & 0xcc:
>         m &= 0xcc
>         n |= 2
>     if m & 0xaa:
>         n |= 1
>     return n
>
> On a CPU like an ARM, that's pretty much one CPU instruction
> per line of code.

OTOH, people with ARM CPUs aren't generally given pause by the
thought of a 256-byte lookup table. :)

-- 
Grant Edwards                   grante             Yow! Civilization is fun!
                                  at               Anyway, it keeps me busy!!
                               visi.com            

On Oct 16, 8:22 pm, Grant Edwards <gra...@visi.com> wrote:
> On 2007-10-16, ssubbarayan <ssu...@gmail.com> wrote:
>
> > Thanks for all your replies. But theres no reply regarding the
> > design stated.
>
> Yes there were.
>
> > Can anyone help me understand this?
>
> Probably not.  We've already explained it to death.
>
> If you don't understand it yet, you should probably go read the
> uC/OS-II book along with some general OS theory texts.
>
> --
> Grant Edwards                   grante             Yow! I hope I bought the
>                                   at               right relish ... zzzzzzzzz
>                                visi.com            ...

Hi Edward,
I do understand whats stated here with respect to bitmap
scheduler.What I refered as not able to get reply is with respect to
server task design explained to over come priority inheritance.I agree
I should have stated it more clear,but still to me this is (server
approach) is not understandable.
Regards,
s.subbarayan