!topic LSN025 on Simplifying Protected Records $Revision: 1.1 $
!from Tucker Taft $Date: 92/02/04 10:58:05 $
!discussion

There are a few reviewers ("broken records" in their terms ;-) who feel
that protected records are overly complicated, baroque, ugly,
inconsistent with the rest of the language, etc.

On the other side, there are also a number of reviewers who have
indicated they think protected records are "elegant," smoothly
integrated with the rest of the language, a nice complement to the
active tasking features, etc.

In some ways, it seems like one either likes them or dislikes them.
There don't seem to be many "luke" reactions.

Let's look at their features:

  1) Encapsulation of data and (synchronizing) operations
	("protected" unit)
  2) Mutual exclusion   (protected operations)
  3) Conditional queueing based on boolean expressions
        ("entry" queues/barriers)
  4) No extra context switches upon state change
        ("servicing the entry queues")
  5) Distinguish read-only vs. read-write operations in the spec
        (protected function vs. procedure/entry)
  6) Distinguish conditionally queueing from non-queuing operations in
     the spec
	(entry vs. protected subprogram)
  7) All data declared in the spec to avoid need for indirection in data
     allocation
        (components declared after "record" keyword)

We believe that each of these features are important to many real-time
and parallel programs.  The syntax directly reflects the semantic
features.  We could certainly fiddle a bit with the reserved words, or
the ordering, but fundamentally, the syntax and the semantics are quite
closely linked.

To "simplify" protected records, one would presumably have to eliminate
some of the features, or simplify them.  However, we contend, based on
many examples, that eliminating any feature will make the usage *more*
complicated for certain problems (as we have argued before, in e-mail
messages, LSNs, rationale documents, MIs, etc).

In any case, let's look at the features one at a time:

  1) Encapsulation

One could eliminate encapsulation, but then it becomes more difficult to
distinguish synchronizing operations from others.  We started this way,
making all derivable/primitive subprograms automatically "locking," but
ran into a number of difficulties, as explained in the original MI
(RT05) on protected records, and reiterated in various other documents.
In particular, if there is more than one "controlling" parameter, do
they both get locked, and in what order?  If there is an object of the
type declared inside the package where the type is defined, is it locked
implicitly on operations like assignment and selection?  When, if ever,
is such a local object locked?

Giving up encapsulation could also lead to critical regions associated
with a given object being "scattered" throughout the code.  This would
tend to make correctness analysis more difficult, and would also
interfere with certain optimizations possible only when all
synchronizing operations are colocated.

   2) Mutual exclusion

We have heard no suggestions to give up this feature.

   3) Conditional queueing based on boolean expressions
        ("entry" queues/barriers)

There have been several suggestions that we could drop entries from the
proposal, leaving simply mutual exclusion.  However, this would mean
that there would no way to suspend waiting for the state of an object to
change, except by doing a task entry call.  One would have to add
suspend/resume primitives.  There are well known "race" conditions
associated with suspend/resume, so one would have to provide some kind
of two-state suspend/resume.  In our view of the tradeoffs, the
protected record approach with entries is simpler to use, and is better
integrated with the rest of the language.  Entries remain the primary
way to suspend a task, and timed entry calls nicely generalize to
provide timed suspensions.  Adding a timer feature to a two-state
suspend/resume would seem to be adding "gratuitous" complexity ;-).

   4) No extra context switches upon state change
        ("servicing the entry queues")

A common alternative to the proposed entry-barrier approach for
providing caller suspension is the signal/wait-on-condition paradigm
used in monitors and elsewhere.  However, signal/wait introduces the
issue of broadcast vs. wake single caller, and requires that any wait on
a condition be surrounded by an explicit loop to recheck the condition.
Furthermore, it requires that explicit calls on signal be coded in all
places where relevant state changes take place, introducing additional
possibilities for errors.  Again, based on a tradeoff analysis, we
believe the entry barrier approach is superior to the signal/wait
approach.  In any case, it seems clear that a signal/wait approach is
not significantly simpler.

   5) Distinguish read-only vs. read-write operations in the spec
        (protected function vs. procedure/entry)

There have been some suggestions for dropping the "function" vs.
"procedure" distinction.  Amusingly, there have also been suggestions
for adding a read-only entry.  We believe that it would be surprising
and inconsistent to provide a "procedure" operation without a "function"
operation.  Furthermore, because it is necessary to specify which PR
operations may be applied to an read-only PR object (e.g. a subcomponent
of an IN parameter), and because normal functions only have IN
parameters, we felt it was most natural to associate the read-only
distinction with the function vs. procedure distinction.

We did not believe it was useful to provide a read-only entry, because
the state of the entry queues (e.g. E'COUNT) is considered part of the
state of a protected record, so all entries may alter the state and
cannot be considered "read-only."

Read-only operations are important for two reasons: On a mono-processor,
they do not need to service the entry queues upon return, which
eliminates overhead; In a highly-parallel environment, shared read-only
locking can be important for minimizing contention.

One could use a pragma to identify read-only operations, but this would
not provide simplification of the semantics, and would be an
inappropriate way to address the issue of whether a given PR operation
may be applied to a read-only PR object.I Again, very little semantic
simplification would be achieved.

   6) Distinguish conditionally queueing from non-queuing operations
      in the spec  (entry vs. protected subprogram)

One could go to an approach where all operations were potentially
suspending with respect to the spec.  However, this would make it harder
to compose protected records properly, and would make the spec of a
protected record less expressive.  Furthermore, one would have to
identify "barrier-less" entries as a special case for interrupt
handlers, etc., meaning that an important distinction is being buried in
the body, and very little semantic simplification is being achieved.

   7) All data declared in the spec to avoid need for indirection in
      data allocation
        (components declared after "record" keyword)

An important space and time advantage of protected records is that all
data requirements are visible in the specification.  This allows data to
be allocated directly, rather than using dynamic allocation and a
pointer.  In any case, it doesn't seem to be a significant
simplification to move the data into the body, and it does add overhead.

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

We honestly believe that protected records have minimal "fat" in their
syntax or semantics.  Furthermore, based on numerous examples, we
believe that removing any of the features would make the use of
protected records more complicated and error prone.

For reviewers who continue to feel that PRs are too complicated, we
request that you recode the examples that have been provided in past
e-mail messages, particularly the mailbox examples, after dropping or
somehow simplifying one or more of the features.  We don't believe there
is much to be gained, and we believe there is the potential for losing a
lot of functionality.

Certainly there are alternatives, many of which we have evaluated.
However, in our analysis, the alternatives are not simpler to use and
maintain than PRs, and do not integrate as well as PRs with the existing
language support for timed and conditional entry calls.

-Tuck