Re: Hiding Concurrency

Re: Hiding Concurrency

[stt]

Re: Hiding Concurrency; semaphores in ADTs, etc.

Providing better support for data-oriented synchronization
is a high priority for the Ada 9X revision.  We are addressing
both the issue of synchronizing access to shared data without
introducing an additional task, as well as the importance of
by-reference parameter passing when passing shared or volatile
data objects.  For now, explicit use of access values to prevent
by-copy parameter passing may be the only "portable" solution,
though most compilers have an upper bound on the size of the
object they will pass by copy.

S. Tucker Taft
Ada 9X Mapping/Revision Team
Intermetrics, Inc.
Cambridge, MA  02138

Hiding Concurrency

[Steven J. Zeil]

While reviewing some code for portability problems, I recently became
suspicious of a rather ugly case of "feature interaction" in Ada.

Consider the following package, intended for use in concurrent
applications:

    with Semaphores;  -- assume a reasonable definition
    with Attribute_Types;  use Attribute_Types;
    package ADTs is
 
       type ADT is limited private;

       function Attribute1 (A: ADT) return Attribute1_Type;
       procedure Put_Attribute1 (A: in out ADT;
                                 Attr_Value : in Attribute1_Type);

       function Attribute2 (A: ADT) return Attribute2_Type;
       procedure Put_Attribute2 (A: in out ADT;
                                 Attr_Value : in Attribute2_Type);


       ADT_Instance : ADT;

    private

       type ADT is record
           Controller : Semaphores.Semaphore;
           Attr1      : Attribute1_Type;
           Attr2      : Attribute1_Type;
       end record;

    end ADTs;


    package body ADTs is

       use Semaphores;
 
       function Attribute1 (A: ADT) return Attribute1_Type is
           Attr : Attribute1_Type;
       begin
           Seize (A.Controller);
           Attr := A.Attr1;
           Release (A.Controller);
           return Attr;
       edn Attribute1;

       procedure Put_Attribute1 (A: in out ADT;
                                 Attr_Value : in Attribute1_Type) is
       begin
           Seize (A.Controller);
           A.Attr1 := Attr_Value;
           Release (A.Controller);
       end Put_Attribute1;

       .
       .  and so on
       .

    end ADTs;



Now, it looks to me as if I have done all the proper and careful
things to protect my ADT objects during concurrent access, while
hiding that protection behind the procedural interface just in case I
later want an unprotected form of the same ADT for use in
non-concurrent applications.


But how safe is this, really, if the compiler exercises its option to
pass parameters by copy-in/copy-out?  Suppose that I have one task
that attempts:
      Put_Attribute1 (ADT_Instance, X);
just as another is about to attempt:
      Put_Attribute2 (ADT_Instance, X);

It appears to me that I could get in trouble if the first task is only
part-way through copying the ADT value back out when the second begins
copying it in.  Similar problems seem to occur if the second task
instead were attempting to call the Attribute1 function, and possibly
even the Attribute2 function.

These problems do not arise if the compiler opts to pass the ADT
parameters by reference.




My conclusion is that hiding concurrency control among operations with
"in out" parameters behind a procedural interface is generally
"erroneous" (in the sense that LRM 6.2.7 declares all program
executions erroneous whose "effect depends on which [parameter
passing] mechanism is selected by the implementation.")

To get around this, I would need to either make all of the operations
explicit task entries, in which case I cannot easily later replace
this package with a sequential version, or I must redesign the
interface to eliminate all but "in" parameters among the operations
that could be called "simultaneously".  Most likely, this means
redefining ADT as a pointer to the record structure used above. Such a
redefinition is plausible, but may have other unfortunate and
far-reaching consequences.




Does anyone see a flaw in my analysis of this problem?




                                                          Steve Zeil

Re: Hiding Concurrency

[madmats]

In article <1991Apr15.211346.15760@cs.odu.edu>, zeil@cs.odu.edu (Steven J. Zeil) writes:
> 
> My conclusion is that hiding concurrency control among operations with
> "in out" parameters behind a procedural interface is generally
> "erroneous" (in the sense that LRM 6.2.7 declares all program
> executions erroneous whose "effect depends on which [parameter
> passing] mechanism is selected by the implementation.")
> 
Yes, you are absolutely right. Using semaphores embedded within ADTs is
erroneous because it depends on the parameter passing mechanism selected
by the implementation. This makes all of Booch's concurrent components 
erroneous. A recent paper in Ada Letters has already shown that problem:

[Gonzales 90] Dean W. Gonzales, "Multitasking Software Components", Ada
Letters Vol. X, No. 2, January/February 1990.

The best solution I can imagine to that problem is to put all data 
implementing the ADT into a task and access it through entries, one for each
operation. The problem with this solution, however, is that entries are not
enough for specifying all operations you need on your ADT: entries cannot be
functions and cannot be generic, which makes it difficult to write iterators.

I am currently working on extensions to the Ada language that should solve this
problem: I will propose a package type construct equivalent to the task type
construct, which I will enhance so that it can include generic entries. Package
and task types would then be equivalent except for concurrency. Then, through
inheritance, a package implementing a non-concurrent ADT can be made into a
concurrent one with minimal change.

Mats Weber
Swiss Federal Institute of Technology
EPFL DI LGL
1015 Lausanne
Switzerland

E-mail : madmats@elcgl.epfl.ch
phone  : +41 21 693 52 92
fax    : +41 21 693 39 09

Re: Hiding Concurrency

[Jim Showalter]

Why did you use semaphores instead of tasking for this problem?
If you had used tasking, your concurrency problems would have
gone away--that is, after all, what tasking is FOR.
--
* The opinions expressed herein are my own, except in the realm of software *
* engineering, in which case I borrowed them from incredibly smart people.  *
*                                                                           *
* Rational: cutting-edge software engineering technology and services.      *

Re: Hiding Concurrency

[madmats]

In article <jls.671951147@rutabaga>, jls@rutabaga.Rational.COM (Jim Showalter) writes:
> Why did you use semaphores instead of tasking for this problem?
> If you had used tasking, your concurrency problems would have
> gone away--that is, after all, what tasking is FOR.

Because tasks can only be accessed through entries, and composite ADTs often
require iterators (implemented as generic procedures in non-concurrent ADTs).

For instance, try to convert this to a concurrent ADT without using semaphores:

generic
   type Item_Type is private;
   with function "<" (Left, Right : Item_Type) return Boolean is <>;
package Sets is

   type Set is limited private;

   procedure Insert (Item : in Item_Type;
                     Into : in out Set);

   procedure Remove (Item : in Item_Type;
                     From : in out Set);

   generic
      with procedure Action (Item : in Item_Type);
   procedure Enumerate (The_Set : in Set);

end Sets;

You will have much trouble specifying Enumerate as a task entry (not to
speak of implementation, as Enumerate will be recursive if the Sets
are implemented as binary trees).

Mats