Re: priority inheritance (Tornado 202)

AFAIK, semaphores are independent entities: thay are not "owned" by a task.

In your case, A will return to B's priority when C releases the
semaphore. At least, that is what it should be, IMHO.

In VxWorks, only mutex semaphores allow priority inheritance. To be
honest, I don't know if the new reader-writer semaphores in 6.6 allow
it or not, but for the purposes of this post, that does not matter.
For the remainder of this post, unless otherwise specified, assume
that all mutex semaphores are inversion safe (though in practice one
must explicitly set the option).

One may argue that ideally, when the inherited priority level is
lowered, it will be done in a step-wise fashion. That is, as each
dependency that caused the priority level to be bumped up is removed,
the inherited priority level should drop down to the priority level of
the highest remaining dependency. Gawd, I get too wordy sometimes.
Example ... task A (pri 100 bumped up to 80) has two mutexes (X & Y)
that tasks B (pri 90) and task C (pri 80) are respectively pending
for. When task A gives up mutex Y to task C, we might expect that its
priority will drop to 90. When it finally gives up mutex X to task B,
we would expect its priority level to drop back to 100.

Priority inheritance does not work that way in VxWorks.

Here is how it used to work (before 6.0).

The priority level remains "bumped up" until the task that has the
lock on the mutex semaphore gives up its last inversion safe mutex
semaphore. Using the example from above, when task A gives up mutex Y
to task C, its priority remains at 80. After it gives up mutex X to
task B, then its priority will drop back to 100 (skipping 90). Let's
throw curve ball #1 into the mix. What if task A had a lock on mutex
Z while all this was going on, but no one was pending on Z? In that
case, the priority level will remain at 80 until Z is given up--then
it will drop back to 100.

Why do it this way? It's simple, and for most cases, it is good
enough. However, it does mean that when "curve ball #1" comes into
play, the priority will remain higher for a longer period of time than
is necessary (or wanted).

As of VxWorks 6.0, the algorithm changed. The priority level now
remains elevated until the task that has the lock on the mutex
semaphore gives up its last inversion safe mutex that contributed to
raising the priority level. This improvement avoids the problem of
"curve ball #1". It does have its own limitations. For example, if
task B and/or task C time(s) out while waiting for task A to give up
the semaphores, task A's priority level does not get recalculated
until later. If I remember correctly, "later" is when it tries to
give up the semaphore.

Some years ago, I explored various methods to allow the step-wise
lowering of priority levels. It was doable, but the solutions had
undesirable impacts upon memory usage, and/or determinism--two
criteria that were considered very important.

pcm

.

Relevant Pages

  • [PATCH] Document futex PI design
    ... +Unbounded Priority Inversion ... +to use a resource that a lower priority process has (a mutex for example), ... +waiter - A waiter is a struct that is stored on the stack of a blocked ... +The mutex structure contains a pointer to the owner of the mutex. ...
    (Linux-Kernel)
  • Re: [PATCH] Document futex PI design
    ... +Unbounded Priority Inversion ... +to use a resource that a lower priority process has (a mutex for example), ... +waiter - A waiter is a struct that is stored on the stack of a blocked ... +The mutex structure contains a pointer to the owner of the mutex. ...
    (Linux-Kernel)
  • [PATCH -mm 01/02] Update rt-mutex-design.txt per Randy Dunlap
    ... The classic example of unbounded priority inversion is were you have three ... the PI locks will be called a mutex. ... waiter - A waiter is a struct that is stored on the stack of a blocked ... The mutex structure contains a pointer to the owner of the mutex. ...
    (Linux-Kernel)
  • Re: [PATCH] Document futex PI design
    ... +processes, lets call them processes A, B, and C, where A is the highest priority ... +waiter - A waiter is a struct that is stored on the stack of a blocked ... +blocked on mutex L2. ... In this case, the task is removed from the pi_list of the owner, ...
    (Linux-Kernel)
  • Re: [RFC 3/5] sched: Add CPU rate hard caps
    ... A hard cap of 1/1000 could lead to interesting starvation scenarios where a mutex or semaphore was held by a task that hardly ever got cpu. ... It's currently relying on the way tasks with prio less than MAX_RT_PRIO are treated to prevent the priority of tasks who are inheriting a priority from having that priority reset to their normal priority at various places in sched.c. ...
    (Linux-Kernel)