Reply by Not Really Me October 18, 20072007-10-18
"Grant Edwards" <grante@visi.com> wrote in message 
news:13hadmtro10g160@corp.supernews.com...
> On 2007-10-16, Not Really Me <scott@validatedQWERTYsoftware.XYZZY.com> > wrote: > >>> If you've got tasks at priority 5,6,7 and 6 blocks on a >>> resource held by a task at priority 8, what do you do? >> >> You use the uCOS mutex facility and set the PIP (Priority >> Inheritance Priority) higher than any other task, i.e., 4 or >> less. > > That results in a different type of priority inversion. > If task 5 is ready, it should be running, but instead the task > which "inhereted" priority from task 6 is running. > >> This will prevent blocking by causing the pend from task 6 to >> temporarily raise the priority to the PIP (4 or less). The >> pend forces a call to the scheduler to make task 4 (original >> 8) run. When done the priority is returned to 8 and 6 goes >> merrily on its way. > > Except that while it's running at priority 4, it preempts the > task at priority 5, which it should not do, since it is > "supposed" to be running at priority 6. If you leave gaps > between tasks or temporarily swap 6 and 8, you don't have that > problem. > > IOW you end up with two lower priority tasks which are vying > for a resource being elevated above a task that should have > been higher than both of them. >
Agreed. This must be taken into account at design time. I can certainly imagine times when it causes additional problems, but it does provide a solution to a common priority inversion problem. Not perfect, but generally useable. Scott
Reply by J de Boyne Pollard October 17, 20072007-10-17
VV> Mucos is a toy.

CH> Certainly not.

VV> It is not a real OS, but a bare minimum. [...]

CH> It IS a real OS.  [...]

VV> Ok, here are the things that I routinely use which mucos doesn't
provide:
VV>
VV> 1. Multiple waiting.
VV> 2. Hardware abstraction layer concept. Drivers.
VV> 3. Priority elevation mechanism.
VV> 4. Timer based scheduling for non-realtime tasks.
VV> 5. Multicore scheduling.
VV> 6. Mucos has the peculiar API in C. I prefer simpler object
VV> oriented API in C++.
VV> 7. Mucos is not abstracted from compiler and hardware.
VV> 8. Memory protection and virtual memory.

I find it amusing to note that MS-DOS, PC-DOS, DR-DOS, Sinclair QDOS,
OS/2 Warp, OS/2 Warp SMP, Minix, version 6 Unix, HP/UX version 7, and
SunOS/4.x BSD don't qualify as "real" operating systems by your
definition.

Reply by Mindspring Newsgroups October 16, 20072007-10-16
"Paul Keinanen" <keinanen@sci.fi> wrote in message 
news:oav5h3tr858c12vbci9f1f28i6m20knr2g@4ax.com...
> On Sun, 14 Oct 2007 19:07:42 GMT, Vladimir Vassilevsky > <antispam_bogus@hotmail.com> wrote: > >> >> >>Tim Wescott wrote: >> >> >>> >>> I have _never_ written code that makes two separate tasks pend on one >>> resource -- I've always written a server task for that resource, and >>> avoided the whole resource locking/priority inversion issue. >> >>Client/server is a pretty heavy weight solution which has many problems, >>too. >> >>So you have to maintain a list of the requests to the server with the >>priorities for each request. And the server has to parse this list to >>fetch the request with the current highest priority. The access to the >>list has to be atomic; thus there should be a mutex protecting the list. >>How do you avoid the priority inversion regarding that mutex? Is it done >> by the OS core function? (hello mucos). > > In simple architectures, the task switch time does not have to be much > more than the interrupt handling time (which also saves and restores > the context), only some extra time is required to switch the stack > pointer from one task to an other. > > If the server transaction times are short, why bother with any > priority queuing mechanism ? Just build a FIFO in front of the server > process. The FIFO should not need any mutex, if the insertion and > extraction is coded correctly. > > If you need request handling with priority and you have only one > task/prioirity and they are blocked until the request is served, just > create a single element "queue" for each priority level and let the > server task scan those "queues" in priority order. With a low number > of priority levels and a single 32 bit word as the queue element > (which could either contain a value or an address to a descriptor > block, I have used even values for descriptor addresses and odd values > for numeric function code values :-), the memory consumption would not > be large compared to a FIFO and associated bookkeeping. > >>What if the list of the requests is overflown? > > In general, this would be design flaw. The server process should run > on a higher priority compared to the requesters. > > A queue size larger than the number of tasks that might issue > requests, should be sufficient as long as these tasks are blocked, > until their request is served. > > Anyway, either return an error code or put the requesting task to > sleep until the next clock tick and try again. > > Paul >
Question to Tim: Is your "server task" approach similar to, or different from, the approach Paul is suggesting? I've been using FreeRTOS and have taken an approach very similar to what Paul describes with FIFOs. The servicing of the FIFOs is done by a task that I could easily call a "server task" (i.e. what Tim is suggesting). In my case, I have a shared request queue that has one entry per requesting task. Each task has a single entry, task-specific, completion queue. I use some simple rules: - a task may have only a single pending request at any time - every request produces a corresponding completion - a task must consume the completion (or block waiting for it) for a pending request before it can queue another request (as a result there is always room in the completion queue when a request is pending) - requests are serviced in order of receipt (note that prioritizing requests invites starvation) ... i.e. Paul's FIFO??? So I have multiple tasks that make requests and a task that processes requests from the queue.... i.e. Tim's service task??? I hope this makes sense (it seems to work great). In some cases I have added a lock queue so that a requesting task can secure exclusive access of a resource (i.e. issue a sequence of uniterrupted operations). Obviously, locks need to be minimized both in time and frequency. TC
Reply by Grant Edwards October 16, 20072007-10-16
On 2007-10-16, Not Really Me <scott@validatedQWERTYsoftware.XYZZY.com> wrote:

>> If you've got tasks at priority 5,6,7 and 6 blocks on a >> resource held by a task at priority 8, what do you do? > > You use the uCOS mutex facility and set the PIP (Priority > Inheritance Priority) higher than any other task, i.e., 4 or > less.
That results in a different type of priority inversion. If task 5 is ready, it should be running, but instead the task which "inhereted" priority from task 6 is running.
> This will prevent blocking by causing the pend from task 6 to > temporarily raise the priority to the PIP (4 or less). The > pend forces a call to the scheduler to make task 4 (original > 8) run. When done the priority is returned to 8 and 6 goes > merrily on its way.
Except that while it's running at priority 4, it preempts the task at priority 5, which it should not do, since it is "supposed" to be running at priority 6. If you leave gaps between tasks or temporarily swap 6 and 8, you don't have that problem. IOW you end up with two lower priority tasks which are vying for a resource being elevated above a task that should have been higher than both of them. -- Grant Edwards grante Yow! This PORCUPINE knows at his ZIPCODE ... And he has visi.com "VISA"!!
Reply by Not Really Me October 16, 20072007-10-16
"Grant Edwards" <grante@visi.com> wrote in message 
news:13h6u7jo2livf3d@corp.supernews.com...
> On 2007-10-15, Jack Klein <jackklein@spamcop.net> wrote:
SNIP
> >> If you have, and think you know of some problem I have missed, >> I'd like to hear about it. Obviously, despite working in the >> field for years, some of my products are going to suddenly >> start missing their deadlines due to priority inversion any >> time now. > > If you've got tasks at priority 5,6,7 and 6 blocks on a > resource held by a task at priority 8, what do you do?
You use the uCOS mutex facility and set the PIP (Priority Inheritance Priority) higher than any other task, i.e., 4 or less. This will prevent blocking by causing the pend from task 6 to temporarily raise the priority to the PIP (4 or less). The pend forces a call to the scheduler to make task 4 (original 8) run. When done the priority is returned to 8 and 6 goes merrily on its way. Scott
Reply by Grant Edwards October 15, 20072007-10-15
On 2007-10-15, Jack Klein <jackklein@spamcop.net> wrote:

>> uC/OS-II uses a bitmap scheduler. Each task is represented as >> a single bit in a set of bits. When a task is runnable the bit >> is set. The highest priority task is then simply the one >> corresponding to the most significant bit in the set. This >> mechanism is very fast and compact. However, it also means it >> isn't possible to have two tasks at the same priority. There's >> no technical reason why a task's priority can't be temporarily >> boosted when using a bitmap scheduler, it just can't be boosted >> to a priority level that's already in use. > > It is quite possible to use a bitmap scheduler and allow priority > inheritance. I know, I've done it. It's quite simple. Here is a > typical scenario: > > 1. Low priority task L acquires a mutex. > > 2. High priority task H preempts L (with possible other intermediate > preemptions in between), and tries to acquire the same mutex. Task H > is now blocked, and task L is promoted to the priority of task H. > Since task H is now not ready, its bit in the ready bitmap is not > needed. It can refer to task L, no problem.
Yes. Temporarily creating a gap in the priorities by "removing" H from the bitmap would work. My original statement should have been that you have to leave _or_create_ a gap in priorities. -- Grant Edwards grante Yow! An air of FRENCH FRIES at permeates my nostrils!! visi.com
Reply by Grant Edwards October 15, 20072007-10-15
On 2007-10-15, Jack Klein <jackklein@spamcop.net> wrote:
> On Sun, 14 Oct 2007 16:39:47 GMT, "FreeRTOS.org" <noemal@address.com> > wrote in comp.arch.embedded: > >>> You would have to leave priority gaps between all of the user >>> tasks so that there are empty priority slots into which you can >>> elevate tasks temporarily. >> >> That would be one way for sure. I think there could be others >> too. Just thinking off the top of my head.....maybe >> temporarily swapping the priorities of the two offending >> tasks, then swapping them back when the inversion has been >> rectified? This would prevent the need to leave holes. I'm >> sure there are also more fancy ways, maybe temporarily >> removing a task so another task can take its priority, then >> bringing it back when the inversion has been rectified, etc. > > If you want to talk about the mechanics, it is not too > difficult without leaving any gaps. In the task control block > for each task, you have two entries for priority, "real" > priority (whether it is fixed or you allow priorities to be > changed at run-time) and "current" priority.
No, you can't do that with uC/OS-II. The tasks priority is determined by the position of a single bit in an fixed, ordered set of bits. What you're desribing would require completely re-writing the uC/OS-II scheduler.
> "current" priority is ordinarily the same value as the "real" > priority. That only changes when a task possessing a locking > object, such as a mutex, is pre-empted one or more times by > higher priority tasks, until one of the pre-empters tries to > acquire the same mutex. > > At that time, the lower priority task possessing the mutex has > its "current" priority set to that of the new higher priority > requester. Since the requester is blocked, pending on the > mutex, it does not appear on the ready task list, so it does > not contend with the elevated possessor on that list, which is > all that matters to the scheduler.
That would work, except it's just not possible given the design of uC/OS-II (which is what we were discussing). uC/OS-II doesn't have a ready list -- it uses a bitmap scheduler. It doesn't have a priority field in the task control block, priorities are determined by the position of the task's bit within the bitmap. Swapping the priority of two tasks would be feasible (which is just a convenient way of temporarily creating a gap in the used priorities). -- Grant Edwards grante Yow! I'm a fuschia bowling at ball somewhere in Brittany visi.com
Reply by Grant Edwards October 15, 20072007-10-15
On 2007-10-15, Jack Klein <jackklein@spamcop.net> wrote:
> On Sun, 14 Oct 2007 16:28:08 -0000, Grant Edwards <grante@visi.com> > wrote in comp.arch.embedded: > >> On 2007-10-14, FreeRTOS.org <noemal@address.com> wrote: >> >> >> 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. " >> > >> > As far as I know, this statement is just plain wrong. I don't >> > know whether uC/OS does or does not support priority >> > inheritance, but I don't see why only having one task at each >> > priority would prevent its use, with some care. >> >> You would have to leave priority gaps between all of the user >> tasks so that there are empty priority slots into which you can >> elevate tasks temporarily. Other than that, I don't see why it >> couldn't be done. OTOH, uC/OS is typically used on fairly >> small projects where priority inversion can be avoided by >> design rather than worked-around at run-time. > > I have no idea why you think, quite incorrectly, that you have to > leave priority gaps between all tasks to implement priority > inheritance.
Since you can't have two tasks with the same priority, you either have to leave or temporarily create an unused priority level for the lower priority task to "inherit". It can't be temporarily raised to the same priority as the higher-priority task from whom it is to inherit.
> I certainly never did, and I have priority inheritance in a > pre-emptive multitasking RTOS working just fine without them. > > Have you ever implemented an RTOS?
Yes.
> If you have, and think you know of some problem I have missed, > I'd like to hear about it. Obviously, despite working in the > field for years, some of my products are going to suddenly > start missing their deadlines due to priority inversion any > time now.
If you've got tasks at priority 5,6,7 and 6 blocks on a resource held by a task at priority 8, what do you do?
> The harder one to avoid, if you allow tasks to acquire more > than one locking object at the same time, is priority > deadlock. If you can run an RTOS that disallows this, > priority inheritance is a snap, and with no empty slots > needed. The low-level details are quite simple.
-- Grant Edwards grante Yow! I feel ... JUGULAR ... at visi.com
Reply by Paul Keinanen October 15, 20072007-10-15
On Sun, 14 Oct 2007 19:07:42 GMT, Vladimir Vassilevsky
<antispam_bogus@hotmail.com> wrote:

> > >Tim Wescott wrote: > > >> >> I have _never_ written code that makes two separate tasks pend on one >> resource -- I've always written a server task for that resource, and >> avoided the whole resource locking/priority inversion issue. > >Client/server is a pretty heavy weight solution which has many problems, >too. > >So you have to maintain a list of the requests to the server with the >priorities for each request. And the server has to parse this list to >fetch the request with the current highest priority. The access to the >list has to be atomic; thus there should be a mutex protecting the list. >How do you avoid the priority inversion regarding that mutex? Is it done > by the OS core function? (hello mucos).
In simple architectures, the task switch time does not have to be much more than the interrupt handling time (which also saves and restores the context), only some extra time is required to switch the stack pointer from one task to an other. If the server transaction times are short, why bother with any priority queuing mechanism ? Just build a FIFO in front of the server process. The FIFO should not need any mutex, if the insertion and extraction is coded correctly. If you need request handling with priority and you have only one task/prioirity and they are blocked until the request is served, just create a single element "queue" for each priority level and let the server task scan those "queues" in priority order. With a low number of priority levels and a single 32 bit word as the queue element (which could either contain a value or an address to a descriptor block, I have used even values for descriptor addresses and odd values for numeric function code values :-), the memory consumption would not be large compared to a FIFO and associated bookkeeping.
>What if the list of the requests is overflown?
In general, this would be design flaw. The server process should run on a higher priority compared to the requesters. A queue size larger than the number of tasks that might issue requests, should be sufficient as long as these tasks are blocked, until their request is served. Anyway, either return an error code or put the requesting task to sleep until the next clock tick and try again. Paul
Reply by Jack Klein October 15, 20072007-10-15
On Sun, 14 Oct 2007 16:21:14 -0000, Grant Edwards <grante@visi.com>
wrote in comp.arch.embedded:

> On 2007-10-14, Paul Keinanen <keinanen@sci.fi> wrote: > > >>Is it true that uC/OS does not support multiple tasks of same > >>priority? > > Yes. > > >>Any specific reason for such a design of uC/OS kernel? > > > > When you have two or more tasks at the same priority level, > > you usually would have to run some kind of round robin > > scheduling between these. > > That's often what is done, but it's not really required. You > can just pick one of the tasks and run it until it blocks. > > > In many simple kernels, the priority levels are fixed (e.g. > > the order in which they were created at compile or startup > > time), so the task list is always scanned in the same order > > with a strict sequence and there is no way to boost > > temporarily the priority of a single task (as needed by some > > priority avoidance protocols). > > uC/OS-II uses a bitmap scheduler. Each task is represented as > a single bit in a set of bits. When a task is runnable the bit > is set. The highest priority task is then simply the one > corresponding to the most significant bit in the set. This > mechanism is very fast and compact. However, it also means it > isn't possible to have two tasks at the same priority. There's > no technical reason why a task's priority can't be temporarily > boosted when using a bitmap scheduler, it just can't be boosted > to a priority level that's already in use.
It is quite possible to use a bitmap scheduler and allow priority inheritance. I know, I've done it. It's quite simple. Here is a typical scenario: 1. Low priority task L acquires a mutex. 2. High priority task H preempts L (with possible other intermediate preemptions in between), and tries to acquire the same mutex. Task H is now blocked, and task L is promoted to the priority of task H. Since task H is now not ready, its bit in the ready bitmap is not needed. It can refer to task L, no problem. There's other bookkeeping involved, but it's really not difficult.
> > Some priority inversion avoidance system might be useful in > > large systems with libraries form multiple vendors in which > > you have no control what internal resources each library is > > locking, but in small systems using some very simple RT > > kernels, I really do not see any need for any priority > > inversion avoidance protocol. > > Agreed.
-- 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