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
Avoiding priority inversion with software design
Started by ●October 15, 2007
Reply by ●October 15, 20072007-10-15
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.subbarayanHi Subbarayan, Let me answer your last question. After boosting priority scheduler checks for the highest priority task for execution. Note that other task even though with same priority is still pending on Mutex and is the pended queue/not in ready queue. Hence sheduler goes on to execute the task with boosted prioirty which ready for execution (in this case is the highest priority task ready for execution at that point of time) Cheers Gaurav
Reply by ●October 15, 20072007-10-15
On Oct 15, 2: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.subbarayansubbarayan, Here is a link to a great example of how multi-threading works and what some of the main issues around multithreading (including priority inversion) are and how to avoid them. http://en.wikipedia.org/wiki/Dining_philosophers_problem Keith http://www.doubleblackdesign.com
Reply by ●October 15, 20072007-10-15
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!
Reply by ●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-- Jack Klein Home: http://JK-Technology.Com FAQs for comp.lang.c http://c-faq.com/ comp.lang.c++ http://www.parashift.com/c++-faq-lite/ alt.comp.lang.learn.c-c++ http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html
Reply by ●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.subbarayanHi 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 ●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 ●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 ●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 ●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
