Version 1.2 of ais/ai-00250.txt

Unformatted version of ais/ai-00250.txt version 1.2
Other versions for file ais/ai-00250.txt

!standard 09.04 (04)          00-11-21 AI95-00250/01
!standard 09.05.02 (02)
!class amendment 00-12-04
!status work item 00-12-04
!status received 00-12-04
!priority Medium
!difficulty Hard
!subject Protected Types, Extensible, Tagged, Abstract
!summary
This proposal suggests that protected types support extensibility similar to the way that record types are extensible in Ada 95. In an extension of a "tagged" protected type, additional data components and protected operations can be defined, and inherited protected operations can be overridden. This proposal is based on work done during the original Ada 9X project (in particular LSN-1030 -- See appendix below) as well as more recent writings by Burns and Welling [Concurrency in Ada], and Wellings, Johnson, Sanden, Kienzle, Wolf, and Michell [ACM TOPLAS May 2000, vol 22.3].
!problem
[Is this a solution is search of a problem? - ED]
!proposal
The following syntax revision is proposed (protected_type_declaration is here for reference only -- it isn't changed):
protected_type_declaration ::= protected type defining_identifier [known_discriminant_part] is protected_definition;
protected_definition ::= [abstract] [tagged | new subtype_indication with] {protected_operation_declaration} [private {protected_element_declaration}] end [protected_identifier] | [abstract] new subtype_indication with private | [abstract] tagged private
protected_operation_declaration ::= -- as before ... | abstract_subprogram_declaration | abstract_entry_declaration
abstract_entry_declaration ::= entry defining_identfier [(discrete_subtype_definition)] parameter_profile is abstract;
The proposal allows ABSTRACT, and TAGGED or "NEW subtype_indication WITH", following the "IS." In the case of "NEW subtype_indication WITH" the subtype indication would have to specify a tagged protected type as the parent. This form defines a "protected extension" of its parent.
If the word ABSTRACT appears, no objects of the protected type may be created. In addition one or more of the protected operations may be declared ABSTRACT, as may one or more of the primitive operations of the protected type (remember that the primitives of a protected type are defined outside the protected type declaration, just like that of any other type).
If the "NEW ... WITH PRIVATE" or "TAGGED PRIVATE" form is used, the type declaration must appear in the visible part of a package, or as a generic formal type. In the non-generic case, a non-private tagged protected declaration must appear in the private part of the package, and in the NEW ... WITH case, it must be a descendant of the specified ancestor protected type. If ABSTRACT does not appear, the full type must not be abstract. In the generic formal type case, the corresponding actual parameter must be a protected tagged type, descended from the specified ancestor type in the NEW ... WITH case. If ABSTRACT does not appear, the actual type must not be abstract.
[NOTE: It is not clear there is a lot of value in the TAGGED PRIVATE case, except perhaps for generic mix-ins. However, it may be valuable to identify a type as protected tagged, even if none of its protected operations are directly visible, simply to indicate that the type supports simultaneous access from multiple tasks, and to enable extensions that take advantage of the parent type's mutex.]
A protected tagged type does not match/complete a non-protected (limited) tagged type, because the rules for extension are different.
The Class attribute may be applied to a tagged protected type. Presuming PT is a tagged protected type, PT'Class supports implicit conversion from all descendants of PT, and their corresponding class-wide types; i.e., PT'Class covers all of PT's descendants, and their class-wide types.
Within a protected extension, the private operations and the data components of the parent are visible only if the extension is declared within the immediate scope of the full declaration of the parent protected type. This includes within a child unit, if the parent is defined immediately within a library package. This ensures that changes to the private components and operations do not affect code outside the subsystem within which it is defined.
If NPT is an extension of PT, or a descendant of an extension, explicit conversion from NPT to PT is not permitted, except within the body of NPT itself. Even within the body, it is only permitted if PT is the immediate parent of NPT, or if NPT has visibility on the private declaration part of all intervening extensions (e.g. in a child package). It is always legal to convert to PT'Class, and to convert from PT'Class to NPT'Class (a run-time tag check is required in this case). Analogous rules would makes sense for non-protected private type extensions, because converting to an ancestor specific type is privacy-breaking if any extensions are private. It was probably a mistake that Ada 95 allowed such conversions, and a configuration pragma to disallow them has been discussed in the past (probably should be another amendment AI).
From within a protected extension, it is possible to call an overridden protected subprogram of an ancestor type, using the following syntax:
ancestor_protected_subtype_mark .
protected_subprogram_identifier actual_parameter_part
To preserve abstraction, analogous to the conversion restriction above, this kind of call would only be permitted if the ancestor is the immediate parent, or if the extension has visibility on the private declarations of all intervening extensions (e.g. is in a child package).
To redispatch as part of an internal protected operation call, the following syntax is proposed:
protected_subtype_mark'Class .
protected_subprogram_identifier actual_parameter_part
Supporting this new syntax comes down to defining the meaning of an expanded name where the prefix denotes an ancestor/classwide subtype of a protected extension, and the selector_name denotes a potentially overridden protected subprogram, when inside the body of the protected extension. [Note that there is no need for identifying the entry of an ancestor once it has been overridden, since this proposal presumes there is only one entry queue per entry, and only one entry body handling it -- see Dynamic Semantics below.]
The above special kinds of expanded names are not strictly necessary; we could alternatively require the use of a view conversion applied to the protected extension's identifier, where the extension's identifier identifies the "current instance." For example:
PT(NPT).Proc(3,5)
could be used to call the PT implementation of "proc" rather than the NPT one which overrides it. It would be important to consider this form an "internal" call so no new lock is acquired. The syntax "PT.Proc(3,5)" seems more natural, and is probably worth supporting.
Dynamic Semantics
When a protected extension is defined, a single mutex is used for the components and operations inherited from the parent, as well as the new components and operations defined in the extension.
There remains only one entry queue per entry, whether an entry is inherited or overridden in an extension. This means that all entry calls or requeues to a given entry are added to its one entry queue, and when serviced, all are handled by the "current" entry body, which is either an inherited one or an overriding one. This may be considered equivalent to saying that all entry calls/requeues are "dispatching." For example, if an inherited entry does a requeue to another entry, it always "redispatches" to any overriding body of the target entry.
protected subprograms, on the other hand, work the same way as "normal" primitive subprograms, namely an internal call from one protected subprogram to another is statically bound, unless the classwide subtype is used as the prefix of the call.
!discussion
This proposal is a combination of ideas from LSN-1030, and those arising out of the more recent writings. The more recent proposals suggest various mechanisms for allowing calling of overridden entries, but those suggestions require substantial added complexity in terms of exposing entry barriers, incrementally strengthening entry barriers, dealing with ancestor barriers that are no longer true at the point of requeue/call, etc. For this proposal, the added benefit of calling overridden entries was not felt to outweigh this added complexity.
Certainly one of the challenges with extensible protected types is the lack of compelling examples. There seems almost a faith that inheritance is a "good" thing, and hence it should be supported for protected types. However, there are some indications that polymorphism is in some ways a more important capability than (implementation) inheritance. Hence, the ability to "pass the buck" to overridden code seems less critical. More important is the ability to do "classwide" programming with protected types. This also implies that abstract protected types are important, and in many cases, the type hierarchy will be very shallow, with just an abstract type at the root of the hierarchy, and multiple concrete descendants just one level down forming the leaves of the hierarchy. There are some examples that might justify more than two levels in the tree, but they seem more the exception than the rule. Note that in the DRAGOON language built on Ada 83, only the leaves were allowed to be non-abstract.
One thing that seems to have been forgotten in the writings on extensible protected types is that they are still types, and hence in addition to the protected operations, they also have "normal" primitive operations. In many situations, it may be better to only expose the "normal" primitive operations, and hide the protected operations completely. This is possible in Ada 95 as it is, by declaring the type as "limited private," and then completing it with a protected type. This proposal would also allow a type to be declared "protected tagged private." Such a type would have no visible protected operations. However, it would be extensible in a way that would allow an extension to share the lock with the original type. This capability is difficult to achieve currently, and could represent an important new OO flexibility.
!wording
!example
Examples based on May 2000 TOPLAS article
Signal Example:
package Signals is protected type Signal is abstract tagged procedure Send; entry Wait is abstract; private Signal_Arrived : Boolean := True; end Signal; type All_Signals is access Signal'Class; end Signals; package body Signals is protected body Signal is procedure Send is begin Signal_Arrived := True; end Send; end Signal; end Signals;
Now to create a persistent signal:
package Signals.Persistent is protected type Persistent_Signal is new Signal with entry Wait; end Persistent_Signal; end Signals.Persistent; package body Signals.Persistent is protected body Persistent_Signal is entry Wait when Signal_Arrived is begin Signal_Arrived := False; end; end Persistent_Signal; end Signals.Persistent;
To create a transient signal:
package Signals.Transient is protected type Transient_Signal is new Signal with procedure Send; entry Wait; end Transient_Signal; end Signals.Transient; package body Signals.Transient is protected body Transient_Signal is procedure Send is begin if Wait'Count = 0 then return; end if; Signal.Send; end Send; entry Wait when Signal_Arrived is begin Signal_Arrived := False; end; end Transient_Signal; end Signals.Transient;
Now, of course,
My_Signal : All_Signals := new ...; My_Signal.Send;
will dispatch to the appropriate signal handler.
Advanced Resource Control Example:
This example involves adding an Allocate_N operation to an existing resource controller that originally only supported allocating a single resource at a time.
package Rsc_Controller is Max_Resources_Available : constant Natural := 100; -- For example No_Resources_Allocated : exception; -- raised by deallocate
protected type Simple_Resource_Controller is tagged entry Allocate; procedure Deallocate; entry Hold; entry Resume; private Free : Natural := Max_Resources_Available; Taken : Natural := 0; Locked : Boolean := False; end Simple_Resource_Controller; end Rsc_Controller;
package body Rsc_Controller is protected body Simple_Resource_Controller is entry Allocate when Free > 0 and not Locked and Hold'Count = 0 is begin Free := Free -1; -- allocate resource Taken := Taken + 1; end Allocate; procedure Deallocate is begin if Taken = 0 then raise No_Resources_Allocated; end if; Free := Free + 1; -- return resource Taken := Taken - 1; end Deallocate; entry Hold when not Locked is begin Locked := True; end Hold; entry Resume when Locked is begin Locked := False; end Resume; end Simple_Resource_Controller; end Rsc_Controller;
package Rsc_Controller.Advanced is protected type Advanced_Resource_Controller is new Simple_Resource_Controller with entry Allocate_N (N : in Natural); procedure Deallocate; pragma overriding(Deallocate); private entry Wait_For_N (Boolean)(N : in Natural); -- Entry family with two members, used as a parking lot -- for Allocate_N requests that cannot be immediately -- satisfied. Current_Queue : Boolean := False; -- Indicates which of the two 'Wait_For_N' entry queues is the one -- that currently shall be used. (Two queues are used: one queue -- is used when trying to satisfy requests, requests that cannot -- be satisfied are requeued to the other. Then, the roles of the -- two queues are swapped. This avoids problems when the calling -- tasks have different priorities.) Changed : Boolean := False; -- Set whenever something is deallocated. Needed for correct -- implementation of 'Allocate_N' and 'Wait_For_N'. Reset each -- time outstanding calls to these routines have been serviced. -- 'Changed' actually encodes the history information 'Wait_For_N' -- is only accepted after a call to 'Deallocate'. end Advanced_Resource_Controller; end Rsc_Controller.Advanced;
package body Rsc_Controller.Advanced protected body Advanced_Resource_Controller is procedure Deallocate is -- Overridden to account for new history information encoding -- needed for access to parameter in the barrier of Allocate_N. begin Changed := True; Simple_Resource_Controller.Deallocate; end Deallocate; entry Allocate_N (N : in Natural) when Free > 0 and not Locked and Hold'Count = 0 is begin if Free >= N then Free := Free - N; Taken := Taken + N; else requeue Wait_For_N(Current_Queue); end if; end Allocate_N; entry Wait_For_N (for Queue in Boolean)(N : in Natural) when not Locked and Hold'Count = 0 and (Queue = Current_Queue) and Changed is begin if Wait_For_N(Queue)'Count = 0 then Current_Queue := not Current_Queue; Changed := False; end if; if Free >= N then Free := Free - N; Taken := Taken + N; else requeue Wait_For_N(not Queue); end if; end Wait_For_N; end Advanced_Resource_Controller; end Rsc_Controller.Advanced;
!ACATS test
!appendix

From: Tucker Taft
Sent: Wednesday, November 22, 2000  3:06 PM

I received the May 2000 issue of TOPLAS today, and lo and behold
it included an article on integrating object-oriented programming
and Protected objects in Ada 95, with our very own Steve Michell
as a co-author.  The article inspired me to produce an alternative,
simpler proposal than that implied by the article, more along the lines
of the original LSN-1030.  I have included the proposal here.
Steve may want to prepare his own alternative as well, if he
is not satisfied with this one.  Alternatively, he could refine
this one.
-Tuck
---------------
!standard 09.04    (04)                               00-11-21  AI95-xxx/01
!standard 09.05.02 (02)
!class amendment 00-11-21
!priority Medium
!difficulty Hard
!subject Protected Types, Extensible, Tagged, Abstract

!summary

This proposes that protected types support extensibility similar
to the way that record types are extensible in Ada 95.  In an
extension of a "tagged" protected type, additional data components
and protected operations can be defined, and inherited
protected operations can be overridden.  This proposal is
based on work done during the original Ada 9X project (in particular
LSN-1030 -- See appendix below) as well as more recent writings by
Burns and Welling [Concurrency in Ada], and Wellings, Johnson,
Sanden, Kienzle, Wolf, and Michell [ACM TOPLAS May 2000, vol 22.3].

!question


!recommendation


Here is the proposed revised syntax (protected_type_declaration is here for
reference only -- it isn't changed):

   protected_type_declaration ::=
     PROTECTED TYPE defining_identifier [known_discriminant_part] IS
       protected_definition;

   protected_definition ::=
     [ABSTRACT] [TAGGED | NEW subtype_indication WITH]
        {protected_operation_declaration}
      [PRIVATE
        {protected_element_declaration}]
      END [protected_identifier]
    | [ABSTRACT] NEW subtype_indication WITH PRIVATE
    | [ABSTRACT] TAGGED PRIVATE

   protected_operation_declaration  ::=
      -- as before ...
      | abstract_subprogram_declaration
      | abstract_entry_declaration

   abstract_entry_declaration ::=
     ENTRY defining_identfier [(discrete_subtype_definition)]
       parameter_profile IS ABSTRACT;

We have allowed ABSTRACT, and TAGGED or "NEW subtype_indication WITH",
following the "IS."  In the case of "NEW subtype_indication WITH" the subtype
indication would have to specify a tagged protected type as the parent.
This form defines a "protected extension" of its parent.

If the word ABSTRACT appears, no objects of the protected type may
be created.  In addition one or more of the protected operations
may be declared ABSTRACT, as may one or more of the primitive
operations of the protected type (remember that the primitives
of a protected type are defined *outside* the protected type
declaration, just like that of any other type).

If the "NEW ... WITH PRIVATE" or "TAGGED PRIVATE" form is used, the type
declaration must appear in the visible part of a package, or as a generic
formal type.  In the non-generic case, a non-private tagged
protected declaration must appear in the private part of the package, and
in the NEW ... WITH case, it must be a descendant of the specified
ancestor protected type.  If ABSTRACT does not appear, the full
type must not be abstract.  In the generic formal type case,
the corresponding actual parameter must be a protected tagged type,
descended from the specified ancestor type in the NEW ... WITH case.
If ABSTRACT does not appear, the actual type must not be abstract.

[NOTE: It is not clear there is a lot of value in the TAGGED PRIVATE
case, except perhaps for generic mix-ins.  However, it may be valuable
to identify a type as protected tagged, even if none of its protected
operations are directly visible, simply to indicate that the type
supports simultaneous access from multiple tasks, and to enable
extensions that take advantage of the parent type's mutex.]

A protected tagged type does not match/complete a non-protected
(limited) tagged type, because the rules for extension are different.

The Class attribute may be applied to a tagged protected type.
Presuming PT is a tagged protected type, PT'Class supports
implicit conversion from all descendants of PT, and their
corresponding class-wide types; i.e., PT'Class covers all of
PT's descendants, and their class-wide types.

Within a protected extension, the private operations
and the data components of the parent are visible only if the extension
is declared within the immediate scope of the full declaration of the
parent protected type.  This includes within a child unit, if the
parent is defined immediately within a library package.  This ensures
that changes to the private components and operations do not affect
code outside the subsystem within which it is defined.

If NPT is an extension of PT, or a descendant of an extension,
explicit conversion from NPT to PT is not permitted, except
within the body of NPT itself.  Even within the body, it is
only permitted if PT is the immediate parent of NPT, or if
NPT has visibility on the private declaration part of all intervening
extensions (e.g. in a child package).  It is always legal to convert
to PT'Class, and to convert from PT'Class to NPT'Class (a run-time tag check
is required in this case).  Analogous rules would makes sense
for non-protected private type extensions, because converting
to an ancestor specific type is privacy-breaking if any extensions
are private.  It was probably a mistake that Ada 95 allowed such
conversions, and a configuration pragma to disallow them has been
discussed in the past (probably should be another amendment AI).

From within a protected extension, it is possible to call an overridden
protected subprogram of an ancestor type, using the following syntax:

    ancestor_protected_subtype_mark .
      protected_subprogram_identifier actual_parameter_part

To preserve abstraction, analogous to the conversion restriction above,
this kind of call would only be permitted if the ancestor
is the immediate parent, or if the extension has visibility on
the private declarations of all intervening extensions (e.g. is
in a child package).

To redispatch as part of an internal protected operation call, the
following syntax is proposed:

    protected_subtype_mark'Class .
      protected_subprogram_identifier actual_parameter_part

Supporting this new syntax comes down to defining the meaning of an expanded
name where the prefix denotes an ancestor/classwide subtype of a protected
extension, and the selector_name denotes a potentially overridden protected
subprogram, when inside the body of the protected extension.  [Note that
there is no need for identifying the entry of an ancestor once it
has been overridden, since this proposal presumes there is only one
entry queue per entry, and only one entry body handling it -- see
Dynamic Semantics below.]

The above special kinds of expanded names are not strictly necessary;
we could alternatively require the use of a view conversion applied to
the protected extension's identifier, where the extension's identifier
identifies the "current instance."  For example:

    PT(NPT).Proc(3,5)

could be used to call the PT implementation of "proc" rather than
the NPT one which overrides it.  It would be important to consider
this form an "internal" call so no new lock is acquired.
The syntax "PT.Proc(3,5)" seems more natural, and is probably
worth supporting.

        Dynamic Semantics

When a protected extension is defined,
a single mutex is used for the components and operations
inherited from the parent, as well as the new components and
operations defined in the extension.

There remains only one entry queue per entry, whether an entry
is inherited or overridden in an extension.  This means that all
entry calls or requeues to a given entry are added to its
one entry queue, and when serviced, all are handled by
the "current" entry body, which is either an inherited
one or an overriding one.  This may be considered equivalent to
saying that all entry calls/requeues are "dispatching." For example,
if an inherited entry does a requeue to another entry, it always
"redispatches" to any overriding body of the target entry.

Protected subprograms, on the other hand, work the same
way as "normal" primitive subprograms, namely an internal call from
one protected subprogram to another is statically bound,
unless the classwide subtype is used as the prefix of the call.

!discussion

This proposal is a combination of ideas from LSN-1030, and those
arising out of the more recent writings.  The more recent proposals
suggest various mechanisms for allowing calling of overridden
entries, but those suggestions require substantial added complexity
in terms of exposing entry barriers, incrementally strengthening
entry barriers, dealing with ancestor barriers that are no longer
true at the point of requeue/call, etc.  For this proposal, the added benefit
of calling overridden entries was not felt to outweigh this added
complexity.

Certainly one of the challenges with extensible protected types
is the lack of compelling examples.  There seems almost a faith
that inheritance is a "good" thing, and hence it should be supported
for protected types.  However, there are some indications that
polymorphism is in some ways a more important capability than
(implementation) inheritance.  Hence, the ability to "pass the buck"
to overridden code seems less critical.  More important is the
ability to do "classwide" programming with protected types.
This also implies that abstract protected types are important,
and in many cases, the type hierarchy will be very shallow, with
just an abstract type at the root of the hierarchy, and multiple
concrete descendants just one level down forming the leaves of the
hierarchy.  There are some examples that might justify more than
two levels in the tree, but they seem more the exception than
the rule.  Note that in the DRAGOON language built on Ada 83,
only the leaves were allowed to be non-abstract.

One thing that seems to have been forgotten in the writings
on extensible protected types is that they are still types,
and hence in addition to the protected operations, they also
have "normal" primitive operations.  In many situations, it
may be better to only expose the "normal" primitive operations,
and hide the protected operations completely.  This is possible
in Ada 95 as it is, by declaring the type as "limited private,"
and then completing it with a protected type.  This proposal
would also allow a type to be declared "protected tagged private."
Such a type would have no visible protected operations.  However,
it would be extensible in a way that would allow an extension
to share the lock with the original type.  This capability is
difficult to achieve currently, and could represent an important
new OO flexibility.

-------------------------------------------
Examples based on May 2000 TOPLAS article

Signal Example:

package Signals is
    protected type Signal is abstract tagged
        procedure Send;
        entry Wait is abstract;
    private
        Signal_Arrived : Boolean := True;
    end Signal;
    type All_Signals is access Signal'Class;
end Signals;
package body Signals is
    protected body Signal is
        procedure Send is
        begin
            Signal_Arrived := True;
        end Send;
    end Signal;
end Signals;

Now to create a persistent signal:

package Signals.Persistent is
    protected type Persistent_Signal is new Signal with
        entry Wait;
    end Persistent_Signal;
end Signals.Persistent;
package body Signals.Persistent is
    protected body Persistent_Signal is
        entry Wait when Signal_Arrived is
        begin
            Signal_Arrived := False;
        end;
    end Persistent_Signal;
end Signals.Persistent;

To create a transient signal:

package Signals.Transient is
    protected type Transient_Signal is new Signal with
        procedure Send;
        entry Wait;
    end Transient_Signal;
end Signals.Transient;
package body Signals.Transient is
    protected body Transient_Signal is
        procedure Send is
        begin
            if Wait'Count = 0 then
                return;
            end if;
            Signal.Send;
        end Send;
        entry Wait when Signal_Arrived is
        begin
            Signal_Arrived := False;
        end;
    end Transient_Signal;
end Signals.Transient;

Now, of course,

    My_Signal : All_Signals := new ...;
    My_Signal.Send;

will dispatch to the appropriate signal handler.


Advanced Resource Control Example:

This example involves adding an Allocate_N operation to an
existing resource controller that originally only supported
allocating a single resource at a time.

package Rsc_Controller is
    Max_Resources_Available : constant Natural := 100; -- For example
    No_Resources_Allocated : exception; -- raised by deallocate

    protected type Simple_Resource_Controller is tagged
        entry Allocate;
        procedure Deallocate;
        entry Hold;
        entry Resume;
    private
        Free : Natural := Max_Resources_Available;
        Taken : Natural := 0;
        Locked : Boolean := False;
    end Simple_Resource_Controller;
end Rsc_Controller;

package body Rsc_Controller is
    protected body Simple_Resource_Controller is
        entry Allocate when Free > 0 and not Locked and
            Hold'Count = 0 is
        begin
            Free := Free -1; -- allocate resource
            Taken := Taken + 1;
        end Allocate;
        procedure Deallocate is
        begin
            if Taken = 0 then
                raise No_Resources_Allocated;
            end if;
            Free := Free + 1; -- return resource
            Taken := Taken - 1;
        end Deallocate;
        entry Hold when not Locked is
        begin
            Locked := True;
        end Hold;
        entry Resume when Locked is
        begin
            Locked := False;
        end Resume;
    end Simple_Resource_Controller;
end Rsc_Controller;


package Rsc_Controller.Advanced is
    protected type Advanced_Resource_Controller is
      new Simple_Resource_Controller with
        entry Allocate_N (N : in Natural);
        procedure Deallocate;
            pragma Overriding(Deallocate);
    private
        entry Wait_For_N (Boolean)(N : in Natural);
        -- Entry family with two members, used as a parking lot
        -- for Allocate_N requests that cannot be immediately
        -- satisfied.
        Current_Queue : Boolean := False;
        -- Indicates which of the two 'Wait_For_N' entry queues is the one
        -- that currently shall be used. (Two queues are used: one queue
        -- is used when trying to satisfy requests, requests that cannot
        -- be satisfied are requeued to the other. Then, the roles of the
        -- two queues are swapped. This avoids problems when the calling
        -- tasks have different priorities.)
        Changed : Boolean := False;
        -- Set whenever something is deallocated. Needed for correct
        -- implementation of 'Allocate_N' and 'Wait_For_N'. Reset each
        -- time outstanding calls to these routines have been serviced.
        -- 'Changed' actually encodes the history information 'Wait_For_N'
        -- is only accepted after a call to 'Deallocate'.
    end Advanced_Resource_Controller;
end Rsc_Controller.Advanced;

package body Rsc_Controller.Advanced
    protected body Advanced_Resource_Controller is
        procedure Deallocate is
        -- Overridden to account for new history information encoding
        -- needed for access to parameter in the barrier of Allocate_N.
        begin
            Changed := True;
            Simple_Resource_Controller.Deallocate;
        end Deallocate;
        entry Allocate_N (N : in Natural) when
          Free > 0 and not Locked and Hold'Count = 0 is
        begin
            if Free >= N then
                Free := Free - N;
                Taken := Taken + N;
            else
                requeue Wait_For_N(Current_Queue);
            end if;
        end Allocate_N;
        entry Wait_For_N (for Queue in Boolean)(N : in Natural) when
          not Locked and Hold'Count = 0 and
          (Queue = Current_Queue) and Changed is
        begin
            if Wait_For_N(Queue)'Count = 0 then
                Current_Queue := not Current_Queue;
                Changed := False;
            end if;
            if Free >= N then
                Free := Free - N;
                Taken := Taken + N;
            else
                requeue Wait_For_N(not Queue);
            end if;
        end Wait_For_N;
    end Advanced_Resource_Controller;
end Rsc_Controller.Advanced;

!appendix

/* ---------- "LSN on Extensible Protected Types" ---------- */
From stt  Mon Jun  1 18:46:55 1992
From: stt (Tucker Taft)
Subject: LSN on Extensible Protected Types

!topic LSN on Extensible protected types
!key LSN-1030
!reference MS-9.5;4.0
!reference MS-3.4.1;4.0
!from Tucker Taft 92-06-01
!discussion

[Note, we are numbering this LSN 1030 to avoid colliding with
Art's sequence numbers for non-MRT LSNs]

Now that we have pretty much agreed to have OOP in Ada 9X,
as well as some kind of special syntax to support fast
mutual exclusion (e.g. protected types), it seems appropriate
to reopen the question of whether there should be a way
to have extensible protected types.  In an early
Mapping Document we suggested a syntax, but gave no
further explanation, and after some thought about implementation
concerns, we dropped the idea.

Recently, Ted Baker and others
have been experimenting with adding concurrency control
to abstract data types, and have found that the lack of
"tagged" protected types makes the solutions awkward.
In particular, one must shift from using a syntax-based
non-queued mutual exclusion over to an explicit locking
approach, using a protected object as a component.
Here is an example of the approach:

     package Synch_Pkg is
         -- Define a type to be used as a component,
         -- and a type to be used as an exclusive handle on
         -- the component
         protected type Lock is
             entry Acquire;
             procedure Release;
         private record
             Locked : Boolean := False;
         end Lock;

         type Exclusive_Handle(On_Lock : access Lock) is
           new System.Controlled with null;

         procedure Initialize(Handle : in out Exclusive_Handle);
         procedure Finalize(Handle : in out Exclusive_Handle);
     end Synch_Pkg;

     package body Synch_Pkg is
         protected body Lock is
             entry Acquire when not Locked is
             begin
                 Locked := True;
             end Acquire;
             procedure Release is
             begin
                 Locked := False;
             end Release;
         end Lock;

         type Exclusive_Handle(On_Lock : access Lock) is
           new System.Controlled with null;
             -- Declare an object of this type
             -- to acquire a lock; it will be released
             -- automatically.

         procedure Initialize(Handle : in out Exclusive_Handle) is
         begin
             Handle.On_Lock.Acquire;  -- acquire lock during init
         end Initialize;

         procedure Finalize(Handle : in out Exclusive_Handle) is
         begin
             Handle.On_Lock.Release;  -- release lock when exiting
         end Finalize;
     end Synch_Pkg;

Given the above package, we can embed such a lock
in the root type of a tagged class, or we can use a generic
to add it to any type.  Here is how you could use it
with a tagged type:

     with Synch_Pkg;
     package Whatever is
         type Concurrent_Type is tagged record
             Lock : Synch_Pkg.Lock;
             -- Other components to be added by extension
         end record;
     end Whatever;

Now we can extend the root pkg with some components,
and define some operations:

     with Whatever;
     package Another_Pkg is
         type Extension is new Whatever.Concurrent_Type with record
             Some_Component;
         end record;
         procedure Some_Operation(X : in out Extension);
     end Another_Pkg;

     with Synch_Pkg;
     package body Another_Pkg is
         procedure Some_Operation(X : in out Extension) is
             Handle : Synch_Pkg.Exclusive_Handle(X.Lock'ACCESS);
             -- X.Lock is now acquired
         begin
             X.Some_Component := X.Some_Component + 1;
             -- X.Lock is released automatically
         end Some_Operation;
     end Another_Pkg;

Here is how you could add a "lock" to any type with
a generic:

    with Synch_Pkg;
    generic
        type Contents_Type is limited private;
          -- Type to be inside the locked box
    package Locking_Pkg is
        type Locked_Box is limited private;
          -- Type representing the locked box
        generic
            with procedure Operation(Contents : in out Contents_Type);
        procedure Locking_Operation(Box : in out Locked_Box);
          -- Instantiate this to produce a locking operation
    private
        type Locked_Box is record
            Contents : Contents_Type;
            Lock : Synch_Pkg.Lock;
        end record;
    end Locking_Pkg;

    package body Locking_Pkg is
        procedure Locking_Operation(Box : in out Locked_Box) is
            Handle : Synch_Pkg.Exclusive_Handle(Box.Lock'ACCESS);
            -- Box.Lock is now acquired
        begin
            Operation(Box.Contents);
            -- Box.Lock is released automatically
        end Locking_Operation;
    end Locking_Pkg;

We could use a more complex lock if we wanted to,
e.g. one that provided both exclusive read/write and
shared read/only type access, with two different "Handle"
types, one that got the exclusive lock when initialized,
the other than got the shared lock when initialized.

By using finalization to release the locks, we get automatic
release on unhandled exceptions and abort/ATC.

Unfortunately, these approaches have some drawbacks:

   a) They require that each locking operation include the declaration
      of the local "handle" object.  The generic approach ensures that
      this is always done, but it is a bit clumsy.

   b) The locking is queued, rather than non-queued.

   c) There is no protection against priority inversion.

   d) Getting a shared lock still requires the Lock component
      to be read/write, so either the Lock would have to be
      pointed-to, or the object would have to be an IN OUT parameter
      even when the operation was a read-only operation.

   e) One locking operation cannot call another such operation, because
      deadlock would occur when the second operation tried
      to initialize the exclusive handle.  With the generic approach,
      there is presumably a full set of non-locking operations that operate
      on the "contents" type, so this is less of a problem.

Arguably a more natural approach is to simply make the type
a tagged protected type (or the moral equivalent), and then
add more protected operations and components as part of type
extension.  A possible syntax for this would be (upper case = bold):

    PROTECTED TYPE identifier [discriminant_part] IS
     [TAGGED | NEW subtype_indication WITH]
        {protected_operation_declaration}
      PRIVATE
        {protected_operation_declaration}
      RECORD
        component_list
      END [protected_simple_name];

We have allowed TAGGED or "NEW subtype_indication WITH" following
the "IS."  In the case of "NEW subtype_indication WITH" the subtype
indication would have to specify a tagged protected type as the parent.
By so doing, a single non-queued lock would be used for the
components and operations inherited from the parent, as well as
the new components and operations defined in the derived type.

This seems like a relatively straightforward approach.  There
are nevertheless some subtle semantic and implemention issues associated
with overriding existing entries, or even just adding new ones.
The general idea would be that for a tagged protected type,
at the end of a protected operation, one would "redispatch"
to reevaluate all of the entry barriers.  One would *not* be
able to optimize barrier evaluation, since in general one
operation might be overridden while another might not be.
Similarly, a "requeue" would always be a redispatch,
meaning that the requeuer could not build in any knowledge
of the target entry's barrier.

(Note: By "redispatch" we mean that one goes back to the
"original" tag of the object, even if some intermediate
conversions to ancestor types have occurred implicitly or explicitly
as part of calling inherited operations.)

Even the number of entries wouldn't be knowable statically
when generating the code for a protected operation, because
it might be inherited into a type that has more entries.
The storage allocation problem for a protected type might
also be a little trickier, if a bit-vector approach is used for
entry barriers, or an array of entries is used, since one would be
adding potentially more components as well as more entries.

One possible approach to solving some of these problems
is to regenerate the code for *all* of the protected operations,
even those that are inherited "as is."  However, this does
not necessarily solve the problem, since we probably want
a redispatch for entry-queue servicing
to occur at the end of a protected operation even
if it is reached by explicit conversion to a parent type.

Here is an example of a possible tagged protected
type with an extension, to illustrate some of the
conversion and "redispatching" issues.

     protected type PT1 is tagged
       -- A simple exclusive lock
         procedure Release;
         entry Acquire;
     private record
         Locked : Boolean := False;
     end PT1;

     protected body PT1 is
         procedure Release is
         begin
             Locked := False;
         end Release;
         entry Acquire when not Locked is
         begin
             Locked := True;
         end Acquire;
     end PT1;

     protected type PT2 is new PT1 with
       -- Add operations to support shared locks
         procedure Release_Shared;
         entry Acquire_Shared;
         entry Acquire;  -- Override
         -- inherit Release as is.
     private record
         Reader_Count : Natural := 0;
     end PT2;

     protected body PT2 is
         procedure Release_Shared is
         begin
             Reader_Count := Reader_Count - 1;
         end Release_Shared;
         entry Acquire_Shared when not Locked is
         begin
             Reader_Count := Reader_Count + 1;
         end Acquire_Shared;

         entry Acquire when not Locked and then Reader_Count = 0 is
            -- Obviously this is non-optimal;
            -- A single counter would be better, where < 0 means exclusive,
            -- and > 0 means shared.  But this is an example, remember?
         begin
             Locked := True;
         end Acquire;
     end PT2;

Suppose we have an instance of PT2, and we convert it to
PT1 and call Release.  We still want both entries of the
object to be serviced, even though the operation was called after
converting to a type that only had one entry.

A more interesting question is what happens if we convert it to
PT1 and call the entry Acquire.  In this case, does it use the barrier
expression and body from PT1.Acquire, or PT2.Acquire?
It seems just too weird (and painful to implement
if using a bit-vector approach to barrier expressions)
to allow it to reach PT1.Acquire.
Hence, we could consider the semantics of an entry call to be
roughly, add the call to the appropriate queue, and then
redispatch to service the queues.  In other words, it wouldn't
matter whether you converted a tagged protected object to some
ancestor type, an entry call would end up the same place,
namely the "true" entry based on the original tag of the object.

This distinction between subprogram and entry operations
is somewhat disconcerting, but from an implementation
point of view, it tends to agree with the general approach
of "directly" calling protected subprograms, while only
indirectly calling entries via the RTS.  Similarly, it jibes
with the fact that the caller always executes their "own"
protected subprograms, whereas entry body execution and
barrier evaluation takes place somewhere in the "ether."
Finally, it is consistent with calls between protected subprograms,
since these bypass the locking completely, and can be totally
statically bound, corresponding to calls between primitives
of non-protected types.  Entries may not call one another directly,
and redispatching does seem appropriate for "requeue."

We could "punt" on the issue and simply disallow overriding
existing entries, but that will only lead the user to
asking "why on earth did you put in that restriction?"
And of course, for situations where one is just using
mutual exclusion and no entries, there is no issue about
which barriers to evaluate and which entry bodies to execute.
Certainly, in the above example it would be natural
to have class-wide operations on PT1'CLASS that call only
Acquire and Release, but we certainly want such operations
to get our overridden Acquire instead of the original one.

All of the above issues seem relatively soluble.  The question is
whether the benefit of being able to naturally combine the
OOP concepts and protected type concepts is sufficient to
justify whatever added implementation (and conceptual) complexity
is involved.  Or, alternatively, is it cheaper to just implement
tagged protected types than to take flak about having no good
support for concurrent object oriented programming.

Note that if barriers were restricted to being
boolean variables, then we would have to override protected
procedures to make them update additional boolean variables,
but we wouldn't have to update entries just to change their
barrier.  Interesting tradeoff, and probably one that is
better left to the designer (since they can choose to use
boolean variables instead of expressions if they so desire).

By the way, with a "PT2" kind of lock (readers and writers)
there is a classic fairness issue that can be partially
resolved by disallowing new readers if there are too many
writers stacked up.  This implies using Acquire'COUNT
in the barrier for Acquire_Shared (and perhaps vice-versa).
This is a case where it is more difficult to solve this
problem without 'COUNT in a barrier, since the writers
may all stack up between calls to Acquire_Shared.

We welcome comments on these issues!

****************************************************************

From: Tucker Taft
Sent: Saturday, November 25, 2000 2:06 PM

Jean-Pierre Rosen wrote:
>
> We had a paper at Ada-Europe about all the semantic implications, which
> convinced me that it was really not simple...
> Does your proposal address all these issues ? And what problems does it solve
> that cannot be solved with a protected type embedded into a tagged type ?

I think perhaps the most important is the issue of sharing a lock
between a parent type and a descendant type.

> The big argument for inheritance is that it avoids code duplication. I would
> expect most of protected operations to be in the range of tens of LOC, so
> duplication is not a big deal, especially considering that a typical PO user:
> - is sensitive about execution speed
> - wants to see exactly what is executed

I agree that inheritance is not all it is cracked up to be,
especially for types with any synchronization.  On the other hand,
polymorphism can be quite useful, and the ability to share a lock
could also be an important paradigm in a layered system.

I know when we were designing our Ada 95 run-time system, there
was a natural application for extensible protected types.  We have
a low-level "thread" abstraction, which is extended to become
a higher-level "Ada task" abstraction.  It would be nice if
the higher-level abstraction and the lower-level abstraction could
all share a single lock.  We currently use tagged types, with
a protected object inside, but it is a bit awkward and unnatural.

****************************************************************

Questions? Ask the ACAA Technical Agent