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
Reply by Grant Edwards●October 16, 20072007-10-16
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
Reply by Grant Edwards●October 16, 20072007-10-16
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"!
Reply by Paul Keinanen●October 16, 20072007-10-16
On Tue, 16 Oct 2007 15:19:49 -0000, Grant Edwards <grante@visi.com>
wrote:
>On 2007-10-16, Paul Keinanen <keinanen@sci.fi> wrote:
>> On Mon, 15 Oct 2007 21:57:56 -0500, Jack Klein <jackklein@spamcop.net>
>> wrote:
>>
>>>A bitmap scheduler, like mine, maintains a "ready" bitmap, where the
>>>bit for each task is set if it is ready to run, and not set if the
>>>task is blocked, for a shared resource or any other reason.
>>
>> Unless the computer hardware supports instructions like "find first
>> bit set" type instructions, what is the point of using a bitmap to
>> indicate if a task is runnable or not.
>>
>> On ordinary hardware, you still would have to shift one bit at the
>> time to detect if a task is runnable,
>
>No you don't -- there are far more efficient ways to do it with
>no shifting involved. Here's one method (which IIRC is used by
>uC/OS-II): first you search through the bits a byte at a time
>to find the first non-zero byte. [That allows you to check 8
>tasks in parallel with a single load or test instruction.] Once
>you find the byte with the first non-zero bit, you use that
>byte to index into a lookup table that gives you the highest
>set bit number.
>
>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.
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.
>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 :-).
Paul
Reply by Grant Edwards●October 16, 20072007-10-16
On 2007-10-16, ssubbarayan <ssubba@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 ...
Reply by Grant Edwards●October 16, 20072007-10-16
On 2007-10-16, Paul Keinanen <keinanen@sci.fi> wrote:
> On Mon, 15 Oct 2007 21:57:56 -0500, Jack Klein <jackklein@spamcop.net>
> wrote:
>
>>A bitmap scheduler, like mine, maintains a "ready" bitmap, where the
>>bit for each task is set if it is ready to run, and not set if the
>>task is blocked, for a shared resource or any other reason.
>
> Unless the computer hardware supports instructions like "find first
> bit set" type instructions, what is the point of using a bitmap to
> indicate if a task is runnable or not.
>
> On ordinary hardware, you still would have to shift one bit at the
> time to detect if a task is runnable,
No you don't -- there are far more efficient ways to do it with
no shifting involved. Here's one method (which IIRC is used by
uC/OS-II): first you search through the bits a byte at a time
to find the first non-zero byte. [That allows you to check 8
tasks in parallel with a single load or test instruction.] Once
you find the byte with the first non-zero bit, you use that
byte to index into a lookup table that gives you the highest
set bit number.
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.
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?).
> but stepping through an array is not much time consuming.
If you're stepping through an array one task per index, it's
more time consuming than doing it 8 tasks per index.
> The only advantage of using bitmaps to indicate if a task is
> runnable that I can think of, is that it can easily detect
> that _no_ tasks are runnable (mask == 0 ), so you can run the
> Null task. While this might save a _very_ minuscule amount of
> electric power, stepping through the task list when no
> activity is required should be irrelevant.
--
Grant Edwards grante Yow! I know things about
at TROY DONAHUE that can't
visi.com even be PRINTED!!
Reply by Paul Keinanen●October 16, 20072007-10-16
On Mon, 15 Oct 2007 21:57:56 -0500, Jack Klein <jackklein@spamcop.net>
wrote:
>A bitmap scheduler, like mine, maintains a "ready" bitmap, where the
>bit for each task is set if it is ready to run, and not set if the
>task is blocked, for a shared resource or any other reason.
Unless the computer hardware supports instructions like "find first
bit set" type instructions, what is the point of using a bitmap to
indicate if a task is runnable or not.
On ordinary hardware, you still would have to shift one bit at the
time to detect if a task is runnable, but stepping through an array is
not much time consuming.
The only advantage of using bitmaps to indicate if a task is runnable
that I can think of, is that it can easily detect that _no_ tasks are
runnable (mask == 0 ), so you can run the Null task. While this might
save a _very_ minuscule amount of electric power, stepping through the
task list when no activity is required should be irrelevant.
Paul
Reply by ssubbarayan●October 16, 20072007-10-16
On Oct 15, 11:10 am, ssubbarayan <ssu...@gmail.com> wrote:
> Dear experts,
> I was going through the query regarding Design of UCOS-II
> kernel.Most of the repliers have specified that to avoid priority
> inversion one must take care in design.
>
> 1)I am just curious to understand the specifics(How to stuff) of the
> design.Can some one throw some light on this or provide some links
> which shows how to design such an architecture?Mainly the server based
> approach was discussed there.I would be interested to know about this
> server based design as well as other alternatives which would help me
> to resolve priority inversion.
>
> 2)In the query about UCOS-II kernel,there was this sentence:
> "Unfortunately, RTOS like uC/OS can't support priority inheritance
> protocol since it does not allow kernel to have multiple tasks at the
> same priority. "
>
> I understand that when you boost priority then atleast the task whose
> priority will be boosted will be equal to the priority of the highest
> priority task pending for the resource under contention.Given that
> such a boosting happens how does the kernel handle the scheduling
> between the task which is currently boosted to higher priority and the
> one which already was pending(high priority among pending).In the
> sense,I intend to understand how the kernel is able to decide which
> among the these tasks in the condition mentioned above should be
> allowed to execute?
>
> Looking farward for your replies and advanced thanks for the same,
> Regards,
> s.subbarayan
Hi all,
Thanks for all your replies.But theres no reply regarding the design
stated.Can anyone help me understand this?
Regards,
s.subbarayan
Reply by Jack Klein●October 15, 20072007-10-15
On Mon, 15 Oct 2007 06:10:09 -0000, ssubbarayan <ssubba@gmail.com>
wrote in comp.arch.embedded:
> Dear experts,
> I was going through the query regarding Design of UCOS-II
> kernel.Most of the repliers have specified that to avoid priority
> inversion one must take care in design.
>
> 1)I am just curious to understand the specifics(How to stuff) of the
> design.Can some one throw some light on this or provide some links
> which shows how to design such an architecture?Mainly the server based
> approach was discussed there.I would be interested to know about this
> server based design as well as other alternatives which would help me
> to resolve priority inversion.
>
> 2)In the query about UCOS-II kernel,there was this sentence:
> "Unfortunately, RTOS like uC/OS can't support priority inheritance
> protocol since it does not allow kernel to have multiple tasks at the
> same priority. "
I cannot tell you how UCOS-II was designed, I have not used it, nor
have I looked at its source code. I can tell you what I did, to
support priority inheritance. This is in a preemptive multitasking
kernel with all priorities fixed at system start up, and no two tasks
allowed to have the same fixed priority.
> I understand that when you boost priority then atleast the task whose
> priority will be boosted will be equal to the priority of the highest
> priority task pending for the resource under contention.Given that
> such a boosting happens how does the kernel handle the scheduling
> between the task which is currently boosted to higher priority and the
> one which already was pending(high priority among pending).In the
> sense,I intend to understand how the kernel is able to decide which
> among the these tasks in the condition mentioned above should be
> allowed to execute?
A bitmap scheduler, like mine, maintains a "ready" bitmap, where the
bit for each task is set if it is ready to run, and not set if the
task is blocked, for a shared resource or any other reason.
It is not difficult for a fixed, unique priority kernel to handle
priority inheritance, as long as no two tasks with the same priority
are never both ready to run at the same time.
When high priority task H tries to get a mutex already held by lower
priority task L, it is blocked and its bit is removed from the "ready"
bitmap, and the priority of task L is temporarily raised to that of
task H.
So when the scheduler looks at only the tasks with bits set in the
"ready" bitmap, it does not look at task H because its bit is off, and
only sees task L as ready with that priority.
> Looking farward for your replies and advanced thanks for the same,
> Regards,
> s.subbarayan
On 2007-10-15, ssubbarayan <ssubba@gmail.com> wrote:
> I understand that when you boost priority then atleast the task whose
> priority will be boosted will be equal to the priority of the highest
> priority task pending for the resource under contention.Given that
> such a boosting happens how does the kernel handle the scheduling
> between the task which is currently boosted to higher priority and the
> one which already was pending(high priority among pending).
One of the is blocked, one of them isn't.
> In the sense,I intend to understand how the kernel is able to
> decide which among the these tasks in the condition mentioned
> above should be allowed to execute?
Only one of them is ready. One is blocked waiting on a
resource that's locked by the other.
--
Grant Edwards grante Yow! ... the HIGHWAY is
at made out of LIME JELLO and
visi.com my HONDA is a barbequeued
OYSTER! Yum!