6   show_question_marks_default := false;

     6   Printer.show_question_marks_default := false;

    14   locking of resources. Locking of resources ensures...  Priorities

    14   locking of resources. Locking of resources ensures mutual exclusion

    15   are needed so that some processes can finish their work within ``hard''

    15   when accessing shared data or devices. Priorities allow schedulling

    16   deadlines.  Unfortunately both features interact in subtle ways

    16   of processes that need to finish their work within hard deadlines.

    17   leading to the problem, called Priority Inversion. Suppose three

    17   Unfortunately, both features can interact in subtle ways leading to a

    18   processes with priorities $H$(igh), $M$(edium) and $L$(ow). We would

    18   problem, called \emph{Priority Inversion}. Suppose three processes

    19   assume that process $H$ cannot be blocked by any process with lower

    19   having priorities $H$(igh), $M$(edium) and $L$(ow). We would expect

    20   priority. Unfortunately in a naive implementation, this can happen

    20   that the process $H$ blocks any other process with lower priority

    21   and $H$ even can be delayed indefinitely by processes with lower

    21   and itself cannot be blocked by a process with lower priority. Alas,

    22   priorities. For this let $L$ be in the posession of lock for a

    22   in a naive implementation of resource looking and priorities this

    23   research which also $H$ needs. $H$ must therefore wait for $L$ to

    23   property can be violated. Even worse, $H$ can be delayed

    24   release this lock. Unfortunately, $L$ can in turn be blocked by any

    24   indefinitely by processes with lower priorities. For this let $L$ be

    25   process with priority $M$, and so $H$ sits there potentially waiting

    25   in the possession of a lock for a resource that also $H$ needs. $H$

    26   indefinitely.

    26   must therefore wait for $L$ to release this lock. The problem is that 

    27 

    27   $L$ might be in turn blocked by any process with priority $M$, and so

    28   If this problem of inversion of priorities is left untreated,

    28   $H$ sits there potentially waiting indefinitely. Since $H$ is blocked

    29   systems can become unpredictable and have dire consequences.  The

    29   by processes with lower priorities, the problem

    30   classic example where this happened in practice is the software on

    30   is called Priority Inversion.

    31   the Mars pathfinder project.  This software shut down at irregulare

    31 

    32   intervals leading to loss of project time (the mission and data was

    32   If the problem of Priority Inversion is ignored, realtime systems

    33   fortunately not lost, because of clever system design). The problem

    33   can become unpredictable and resulting bugs can be hard to diagnose.

    34   was that a high priority process and could only be restarted the

    34   The classic example where this happened is the software that

    35   next day.

    35   controlled the Mars Pathfinder mission in 1997.  Once the spacecraft

    36  

    36   landed, the software shut down at irregular intervals leading to

    37 

    37   loss of project time, as normal operation of the craft could only

    38   resume the next day (the mission and data already collected was

    39   fortunately not lost, because of a clever system design).  The

    40   problem was that the schedulling software fell victim of Priority

    41   Inversion: a low priority task locking a resource prevented a high

    42   priority process from running.  Once found, the problem could be

    43   rectified by enabling the Priority Inheritance Protocol in the

    44   schedulling software.

    45 

    46   The idea behind the \emph{Priority Inheritance Protocol} (PIP) is to

    47   temporarily inherit the low priority process the higher priority

    48   until it released the locked resource.

    49 

    50   However, there are further subtleties: just lowering the priority 

    51   of the process $L$ to its low priority, as proposed in ???, is 

    52   incorrect.\bigskip

    53   

    54   \noindent