Ceiling priority and priority inversion

Ceiling priority and priority inversion

[Mathias]

I an pretty new with Ada and wonder if someone out there can help me clarify
how the pragma Locking_Policy(Ceiling_Priority) works.

To prevent priority inversion when multiple tasks simultaneously access a
protected object you should apply the pragma
Locking_Policy(Ceiling_Priority).

As I interpret the book "Concurrency in Ada" by Burns and Wellings it works
as follows:
The effect of the pragma Locking_Policy(Ceiling_Priority) is that all tasks
accessing subroutines in a protected object execute these with the ceiling
priority. If you omit the pragma Priority in the protected object, the
compiler assigns the ceiling priority of the protected object to the highest
priority defined for the system.

Let's say for an example that the protected object is a buffer shared
between a number of tasks, among which one is a  low priority application
task and another is an interrupt handler. Using Ceiling_Priority will cause
all tasks executing within the protected object do so with interrupt
priority. Doesn't this potentially cause a kind of priority inversion? When
the application task executes within the buffer it preempts all other tasks
in the system, even interrupts.

Shouldn't it instead work like the following? If a low priority task is
executing within a protected object and a task with a higher priority tries
to gain access this object. Then the low priority task should be raised to
the priority level of the waiting task. But if there is no concurrent access
the low priority task executes with its base priority.


Thanks for any help

/Mathias Larsson

Re: Ceiling priority and priority inversion

[Pat Rogers]

"Mathias" <l_mathias@hotmail.com> wrote in message
news:9b051957.0209020707.562bdac4@posting.google.com...
> I an pretty new with Ada and wonder if someone out there can help me
clarify
> how the pragma Locking_Policy(Ceiling_Priority) works.
<snip>
> Let's say for an example that the protected object is a buffer
shared
> between a number of tasks, among which one is a  low priority
application
> task and another is an interrupt handler. Using Ceiling_Priority
will cause
> all tasks executing within the protected object do so with interrupt
> priority. Doesn't this potentially cause a kind of priority
inversion? When
> the application task executes within the buffer it preempts all
other tasks
> in the system, even interrupts.

Interrupts at that level or below, yes.  With the design you describe,
that's what you want -- while the accessing task is within the PO you
don't want another of those interrupts to be handled and you don't
want any other tasks accessing the encapsulated data within the PO.
That's probably OK since interrupt handlers should be short and sweet.

> Shouldn't it instead work like the following? If a low priority task
is
> executing within a protected object and a task with a higher
priority tries
> to gain access this object. Then the low priority task should be
raised to
> the priority level of the waiting task. But if there is no
concurrent access
> the low priority task executes with its base priority.

Ada uses the *Immediate* Ceiling Priority Protocol, because it is more
efficient to implement.


--
Patrick Rogers                       Consulting and Training in:
http://www.classwide.com       Real-Time/OO Languages
progers@classwide.com          Hard Deadline Schedulability Analysis
(281)648-3165                            Software Fault Tolerance

Re: Ceiling priority and priority inversion

[Jim Rogers]

Mathias wrote:

> I an pretty new with Ada and wonder if someone out there can help me clarify
> how the pragma Locking_Policy(Ceiling_Priority) works.
> 
> To prevent priority inversion when multiple tasks simultaneously access a
> protected object you should apply the pragma
> Locking_Policy(Ceiling_Priority).
> 
> As I interpret the book "Concurrency in Ada" by Burns and Wellings it works
> as follows:
> The effect of the pragma Locking_Policy(Ceiling_Priority) is that all tasks
> accessing subroutines in a protected object execute these with the ceiling
> priority. If you omit the pragma Priority in the protected object, the
> compiler assigns the ceiling priority of the protected object to the highest
> priority defined for the system.
> 
> Let's say for an example that the protected object is a buffer shared
> between a number of tasks, among which one is a  low priority application
> task and another is an interrupt handler. Using Ceiling_Priority will cause
> all tasks executing within the protected object do so with interrupt
> priority. Doesn't this potentially cause a kind of priority inversion? When
> the application task executes within the buffer it preempts all other tasks
> in the system, even interrupts.
> 
> Shouldn't it instead work like the following? If a low priority task is
> executing within a protected object and a task with a higher priority tries
> to gain access this object. Then the low priority task should be raised to
> the priority level of the waiting task. But if there is no concurrent access
> the low priority task executes with its base priority.


Quoting from "Ada as a Second Language":

"Under the Ceiling_Locking policy, a Priority pragma in a protected declaration
specifies the ceiling priority for protected objects of the corresponding
protected type. This priority is established when the protected object is
created, and cannot be changed afterward. ... If the Ceiling_Locking policy
is in effect and a given protected declaration does not have a Priority pragma,
Priority'Last is used as the ceiling priority for that protected type.

If an operation of a protected object with a given ceiling priority is called
by a task with an active priority higher than that ceiling priority, it is a
symptom of a design error, and exception Program_Error is raised. Together,
these rules ensure that if a higher priority task calls a protected action of
the same protected object (and at least one of the protected operations is not
a protected function, so the high-priority task must be kept waiting to
ensure mutual exclusion), the protected action is completed with at least the
urgency of the task that must be kept waiting until the protected operation is
complete."

The active priority of a task is set when it starts executing a protected
action, and may be changed upon completion of the protected operation. There
is no provision for changing the priority of a task during the execution of
a protected operation. Your scheme would require such priority changes. It
would also be very much more complicated to implement than the current
Ada scheme. Protected operations, to be effective and safe, must be
fast and atomic. Atomic operations are achieved by ensuring that the
protected action is not interrupted by another task. Fast operations are the
responsibility of the person implementing the protected action.

Jim Rogers