Uneasy thoughts about priorities, priority inversion and protected objects

Uneasy thoughts about priorities, priority inversion and protected objects

[Jean François Martinez]

Both Burns in his "Concurrent and Real Time Programming in Ada" and JP Rosen in his wikibook (in French) about software engineering "implement" (note the scare quotes) protected objects by giving a priority to the protected object that is inherited by a task when it runs in it.  This prioriry must be at least equal to the maximum priority of the tasks that might access the protected object (a task with a higher priority gets an exception). ¨Purpose is to avoid priority inversion when a task with high priority cannot enter a protected object because a task with low priority is in it and this cannot get the processor (and out of the protected object) because a task with medium priority is running.  The merit of this model is that it makes protected objects very easy to implement (on monoprocessors): no need of semaphores: once a task is in a protected object no other task can enter it because it cannot get the processor.

Burns tells this model is recommended/mandated (don't remember) by the ARM.

Problem is: there are still priority inversions.  Let's consider the following scenario.  Task High is sleeping, Task Medium is waiting for I/O, Task Low is in protected Object.  Now I/O completes so Task Medium should get the processor but it doesn't because Low is in protected object with High's priority or more.  But nobody is waiting for the protected object so there is no hurry in getting Low out of it and no reason to delay Medium jsut because Low is in Protected Object.  Agreed you are not supposed to spend much time in Protected Objects so you can consider it is no big deal but it is not satisfactory.  It also raises the question of if such a model really allows concurrent readers in practice when in monoprocessors.

It seems to me a task on a protected object should have its priority raised only when a task with a higher priority queues behind it.  In that case its priority should become 
Max(Own_Priority, Max(Priority_of_Processes_in_the_Queue)).  With this model:
Low is in Protected_Object running at Low priority, Medium's I/O ends so Medium gets the processor, High awakes, grabs the processor from Medium and queues on the protected object, Low gets its priority raised to High, resumes running, leaves the protected object and returns to its  normal priority (Low), High gets the processor, enters the protected object and keeps running until it decides to release it.  Medium gets the processor.  
Zero priority inversions.   Also we can have multiple readers, even in monoprocessors.  At least when second reader has ahigher priority than first one.  

Since I don't think for a second none of the smart people who designed Ada and none of the smart people who have read either the ARM, Burns'book or Rosen's wikibook haven't ever had a so obvious idea why is that we still are in the model I described on the first paragraph?  Because it is simpler to implement?  Because it is no big deal?  (You are supposed to leave the protected object _fast_).  Or is it because I missed someting? 

---

Jean-François Martinez

Re: Uneasy thoughts about priorities, priority inversion and protected objects

[J-P. Rosen]

Le 27/02/2015 12:59, Jean François Martinez a écrit :
> Both Burns in his "Concurrent and Real Time Programming in Ada" and
> JP Rosen in his wikibook (in French) about software engineering
> "implement" (note the scare quotes) protected objects by giving a
> priority to the protected object that is inherited by a task when it
> runs in it. [...]
This is required only if you specify pragma Locking_Policy (Ceiling_Locking)

> Problem is: there are still priority inversions.  Let's consider the
> following scenario.  Task High is sleeping, Task Medium is waiting
> for I/O, Task Low is in protected Object.  Now I/O completes so Task
> Medium should get the processor but it doesn't because Low is in
> protected object with High's priority or more.  But nobody is waiting
> for the protected object so there is no hurry in getting Low out of
> it and no reason to delay Medium jsut because Low is in Protected
> Object.  
Scheduling is based on the active priority,  so when Low inherits a high
priority, it won't let Medium run (on a mono-processor).

> It seems to me a task on a protected object should have its priority
> raised only when a task with a higher priority queues behind it.  
This is called priority inheritance. It has the benefit of saving
useless priority changes, at the cost of a more complicated priority
change when required (a task has to change the priority of another task
while it is in the PO).

> Since I don't think for a second none of the smart people who
> designed Ada and none of the smart people who have read either the
> ARM, Burns'book or Rosen's wikibook haven't ever had a so obvious
> idea why is that we still are in the model I described on the first
> paragraph?  Because it is simpler to implement?  Because it is no big
> deal?  (You are supposed to leave the protected object _fast_).  Or
> is it because I missed someting?
When it comes to scheduling, for any algorithm, you can find an example
where it makes perfect sense, and an example where it would be
catastrophic. The "best" algorithm depends highly on your requirements
and your application profile.


-- 
J-P. Rosen
Adalog
2 rue du Docteur Lombard, 92441 Issy-les-Moulineaux CEDEX
Tel: +33 1 45 29 21 52, Fax: +33 1 45 29 25 00
http://www.adalog.fr

Re: Uneasy thoughts about priorities, priority inversion and protected objects

[Dmitry A. Kazakov]

On Fri, 27 Feb 2015 03:59:02 -0800 (PST), Jean François Martinez wrote:

...

> Since I don't think for a second none of the smart people who designed Ada
> and none of the smart people who have read either the ARM, Burns'book or
> Rosen's wikibook haven't ever had a so obvious idea why is that we still
> are in the model I described on the first paragraph?  Because it is
> simpler to implement?  Because it is no big deal?  (You are supposed to
> leave the protected object _fast_).  Or is it because I missed someting? 

I would say it is because there is no good reason to interrupt protected
actions regardless priorities. It simply does not pay off, and whatever
gain might result of doing this will be lost on context switching (at least
two in your scenario).

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Uneasy thoughts about priorities, priority inversion and protected objects

[Jean François Martinez]

> 
> Burns tells this model is recommended/mandated (don't remember) by the ARM.
> 

Actually I misunderstood Burns.  Burns never discussing other policies than Ceiling_Locking and some hasty reading fom my part made me believe Ceiling_Locking was the only possible policy in Ada.  Actually the ARM _mandates_ the Ceiling Locking Policy being implemented and _allows_ other policies.  At least that is what I understood of it.  So I investigated Gnat's .ads and it looks there are two other policies one of them being the one I "invented" following my highly successful inventions of the wheel and hot water.  :-)

Anyway "Earth swallow me!"

Jean François Martinez