LSN002.MutExc

This LSN examines unifying the priority model to handle tasking,
interrupts, and mutual exclusion.

----------------------------------------------------

Language Study Note on Priorities, Interrupts, and Mutual-Exclusion

Offer Pazy

March 25, 1991

Introduction:

There are two different approaches that can be taken in designing
the relationship between non-queuing locking primitives, priori-
ties, and interrupts.

 1.  The low level operations are separate entities,  and do not
     implicitly affect each other.  Instead, a set of design
     "rules" is specified to allow the creation of a safe and
     reliable system.  The user must enforce the "rules" himself.
     For example, if a lock is shared between an interrupt
     handler and the rest of the program, the "rule" is that the
     interrupt must be disabled before the program attempts to
     gain the lock.  There are many other such rules.

 2.  The low level operations are combined into a unified whole
     by bundling all of the operations into a single priority
     scheme.

The General model:

We have decided to take the second approach and to combine the
semantics of locks with priorities.  This approach allows for a
clean unifying model for the scheduling, dispatching, and preemp-
tion control in the RTS.  Separating the locking and interrupt
mechanisms from priorities will require a much more complicated
semantic definition to address the various issues of dynamic
priority management and priority inheritance.  Therefore, all
tasks, protected records, and interrupts have a priority in an
interleaved range (i.e. a task priority may be higher than that
of an interrupt handler).  The priority of an interrupt handler
is usually the same as that of the hardware interrupt, if such a
notion exists on the specific platform.

     For the purpose of this discussion we define two kinds of
priorities: The base priority of a task and its currently active
one.  The base priority is the only one that may be directly set
or changed by the program.  The active priority is the one that
actually determines the priority of a task.  It may be viewed as
a demand function of the task's base priority (and potentially
the active priorities of other tasks) that is evaluated whenever
needed.  Also, we assume that each task in the program has some
base priority (i.e no "undefined priority" in the Ada83 sense).

     The active priority of task T is the maximum of:

 1.  its base priority

 2.  the active priority of any calling task in a rendezvous with
     T

 3.  the active priority of any calling task waiting to enter a
     rendezvous with T, if priority inheritance is in effect

 4.  the ceiling priority of any lock held by T

Rules for Manipulating and Querying Tasks' Priorities:


   * Both the ACTIVE and the BASE priorities of a task can be
     interrogated.

   * The base priority of a task is considered a shared variable
     between the tasks that change and/or interrogate it.

   * Only the base priority can be changed by the program expli-
     citly.  As a result of this change, the task's active prior-
     ity will be reevaluated according to the specific rules
     which apply in each case.  Under certain circumstances, the
     active priority of other tasks may be changed as well (e.g.
     when priority inheritance is in effect).  Changing the
     priority of a task will take effect before the calling task
     returns.

   * While a task is executing a change priority operation, its
     active priority will implicitly be raised to the maximum
     priority of its own and all the new base priorities of the
     tasks affected by the call.  This is done in order to ensure
     that the calling task is not preempted in the middle of
     changing the priorities of a group of tasks (this will hap-
     pen if the new base priority of one of the affected tasks is
     higher than that of the caller).

Note that when we talk about the effect of changing priorities,
we refer to the activity which takes place in order to make the
system consistent with respect to priorities, including:
reevaluating and restructuring queues, preempting or dispatching
new tasks, and performing all other active priorities adjustments
when priority inheritance is in effect.

     If the target task is the caller in a rendezvous, the active
priority of the acceptor task will be modified (though only tem-
porarily, until the end of the rendezvous); the acceptor's new
active priority will be the maximum of the caller's new active
priority and acceptor's old active priority.  If the target task
is the acceptor in a rendezvous, the priority of the caller is
not affected.  Another example; if an acceptor lowers its base
priority, while in a rendezvous, and the new value is still lower
than that of the caller, its active priority will not be changed
immediately, but rather take effect after the end of the rendez-
vous.  If a task is in a locking operation and its base priority
is lowered, its active priority will not be changed until it com-
pletes the operation. (i.e., the effect of the priority change
will not happen immediately).  If priority inheritance is in
effect, then the priority change will be transitive, based on the
scheduling policy.  For example, if a task becomes the highest
priority task in an entry queue (as a result of changing its base
priority), then the active priority of the acceptor will be
elevated as well, even though the two are not currently engaged
in a rendezvous.

     If a set of tasks is specified in the statement, then it is
not guaranteed that no other task will see an intermediate state.
i.e. two consecutive queries for tasks' priorities in the
affected set, may yield the new priority of one and the old of
another.  However, the calling task is guaranteed that all tasks
will be affected when it returns.  Furthermore, changing priority
of a task is guaranteed to take effect no later than its next
synchronization point.

     As a consequence of the above rules, if transitive priority
inheritance is in effect, the effective priority of a task is
always the maximum of its own base priority and the effective
priorities of all the tasks that are currently "waiting for it".

Locks (Protected Records) and Mutual Exclusion:

Locking subprograms are assumed to be non-preemptable within
their priority levels (we are assuming a dispatching policy of
"run until blocked", i.e. no time-slicing or round-robin).
Hence, they never require a queue for a mono-processor, but might
have to (busy) wait on a multi-processor.

     Each lock within the application has a ceiling priority
associated with it.  This priority should be set by the user to
the maximum of the active priorities of all of the tasks or
interrupt handlers (IH's) that will ever attempt to acquire the
lock.  It is an error for a task (or an IH) to attempt to acquire
a lock if the tasks (or IH's) active priority is higher than the
ceiling priority of the lock.  When a task or an IH holds a lock,
its active priority is raised to that of the lock (if it is not
already that high), and the RTS does whatever is necessary to
ensure that no other executing tasks will attempt the lock (i.e.
disabling the scheduling of equal or lower priority tasks, mask-
ing all interrupts whose handlers may contend for the lock, and
refusing to acquire a lock of a lower-priority by a higher prior-
ity task or IH, by raising an error).  Non-preemption in this
approach can be mapped to raising the priority of the current
task to the highest among all tasks and disabling interrupts, by
raising it to the highest of all IH's as well.

     Whenever the application needs are such, the priorities of
tasks and interrupt handlers may overlap.  As a consequence, a
running task with a high priority can block the execution of a
lower priority interrupt handler.  This is intentional.  If the
application has defined the priorities in such a manner, then not
preempting the interrupt handler would create priority inversion
within the application.

Interrupt Masking:

In addition to specifying a ceiling priority, a lock may mask one
(or more) specific interrupts.  This permits one of its locking
procedures to be called from the interrupt level.  Specific mask-
ing is not strictly necessary if ceiling priorities in the range
reserved for interrupts are allowed, and have the effect of mask-
ing interrupts at the associated levels and below.  However, on
some architectures, specific masking is efficient and desirable.

     Also, on hardware systems where no prioritized levels of
interrupt exist, then all interrupts would be mapped to the same
priority level, and masking of specific interrupts will be used
to ensure mutual exclusion.  Finally, on some architectures
(which support arbitrary locked bus cycles), an efficient lock
implementation may use "bus locks".  A vendor may supply another
pragma, BUS_LOCK, to allow the creation of protected records with
arbitrary code, protected using bus locks, if supported by the
architecture.



Immediacy:


     It is expected that whenever possible, the entire effect of
changing priorities will take place immediately.  In particular,
for implementations targeted to real-time systems, this behavior
is required.  However, in some cases, this is not practical.
Some hardware systems (e.g. distributed systems, non-
interruptible CPU's), cannot support this functionality without
imposing undue complexity and latencies on the implementation.
If the full state change is not possible for those architectures
without freezing the system, and delaying the caller for a long
time, then, at the minimum, the new priority must be recorded and
subsequent queries for the base priority should return this new
value.

Rationale:


     We explicitly define two kinds of priorities: base and
active.  The need for this duality is not a result of our choice
of semantics but rather inherent to the problem of managing
priority inheritance.  The base priority of a task is the one
that may explicitly modified by itself or any other task (which
has visibility to it).  The active priority of a task is
reevaluated each time its base priority is modified or another
event occurs in the system.

     We have considered several options regarding the immediacy
in which the priority change takes effect.  The ideal one, from
the point of view of correctness and determinism, would be to
require these operations to be atomic with regard to the rest of
the system.  When multiple tasks are affected, then the inter-
mediate state (some tasks have their new priorities, while other
still use their old ones) should not be visible, i.e. will behave
as a transaction.  This is particularly ideal for mode changes,
where it is very difficult to design, analyze, and verify the
behavior of the program while it is in the transient period when
some tasks operate with the old mode's parameters, while others
have their new parameters.

     However, this required behavior may be very costly to imple-
ment and may be impossible in distributed environments or when
the CPU's are not interruptible (the entire system will have to
freeze).

     Another option was to allow postponing the actual priority
change to the next synchronization point, or to the next time the
scheduler is invoked.

     The drawbacks of this approach are quite apparent: the user
has less control on the effect of the priority change and new
mechanisms will have to be incorporated into the implementation
to "remember" and  buffer the requests.  Finally, the semantics
of priority queries will be non-intuitive

     Another argument for allowing the "deferral" approach is to
allow one task to sequentially request the priority change of
other tasks without incurring the overhead of each call and with
no danger of being preempted in the process, leaving the system
in an inconsistent state (this will happen if one of the new
priorities is higher than that of the calling task).  By provid-
ing the capability to specify a set of tasks in one, "non-
preemptable" operation, this is no longer an issue.

     The compromise that we have chosen guarantees that the cal-
ling task will always return after all priority changes (and, for
most cases, their full effects as well) have taken place, and
that the target task(s) will be affected no later than their next
synchronization point.  Even though we have not required indi-
visibility, the semantics of the primitives are consistent and
usable.  The danger of inconsistent state while changing modes of
operation is thus minimized (but not eliminated).

     The base priorities of the affected tasks, as perceived by
the calling task via the Base_Priority_Of function, shall be
changed before the operation returns.  If the affected task is
the same as the caller, or is not executing and is eligible to
execute on the same processor, any effect on its active priority
shall also be felt before the operation returns.  If the affected
task is executing on a different processor, or is not eligible to
execute on the same processor, such an effect shall not occur
later than the next time the affected task reaches a dispatching
point.