Ada Protected Object Tutorial #1

Ada Protected Object Tutorial #1

[James S. Rogers]

This is the first of hopefully several examples of uses for Ada Protected
Objects.

What is a protected object?

Ada provides the ability to create data that can safely be shared by several
tasks
or "threads". The data in a protected object is supported by full mutual
exclusion
characteristics.

The data in a protected object can be accessed in three ways.
Protected Functions:

 The protected function merely reports the value of some data component in
the
protected object. Although it is possible, it is STRONGLY recommended that
protected functions DO NOT change the values of any data components in the
protected object. Any parameters to a protected function must have the "IN"
mode, indicating that the parameters are read-only. Multiple tasks may
simultaneously access a protected object through functions because the
data values are not changed. Protected procedures and protected entries
may not access the protected object while it is being accessed by a
protected function.

Protected Procedures:

Protected procedures are typically used to alter the value of one or more
data
components in a protected object. The parameters of a protected procedure
may have the "IN" mode, like functions. They may also have "OUT" mode,
indicating that the value is write only, or "IN OUT" mode indicating that
the
parameter value can be read and updated. Only one task at a time may
execute a protected procedure. Protected functions cannot access the
protected object while it is being accessed by a protected procedure.

Protected Entries:

Protected entries are just like protected functions with one small
difference.
Protected entries block untils a boundary condition becomes true. For
example, you would use a protected entry to read from a protected
bounded queue. The entry would block as long as the queue was empty.

You can define only one instance of a protected object. Fortunately, Ada
also allows you to define protected types. Protected types use almost
the same syntax as a protected object. The advantage of a protected
type is that you may create as many instances of the type as you need.
You may also define an access type (similar to a pointer) to a protected
type. In this manner you may define an instance of a protected type, point
to it with an instance of the access type, and then pass that access type
to several tasks so that they can easily share the single instance of the
protected type.


Let's look at a first example of a protected type. This example will
illustrate how to create a protected buffer. The buffer has a protected
procedure to write to the buffer and a protected entry to read from the
buffer. The entry is used so that reading tasks will be suspended
until a writing task writes a first valid value.


The definition of the protected type is encapsulated in a generic package
so that it can be used for any data type. The package is divided into two
parts. The first part is the package specification, which defines the
interface
to the protected type. The second part is the package body which defines
the implementation of the package.

-----------------------------------------------------------------------
-- Package: Generic_Protected_Buffer
--
-- Purpose: This package defines a generic buffer allowing multiple
--          writers and multiple readers with full mutual exclusion
--          The readers cannot read until a writer has first written
--          to the buffer.
-----------------------------------------------------------------------
generic

   type Element_Type is private;

package Generic_Protected_Buffer is

   protected type Protected_Buffer is
      procedure Write(Item : in Element_Type);
      entry Read(Item : out Element_Type);
   private
      Data_Valid : Boolean := False;
      Buffer     : Element_Type;
   end Protected_Buffer;
end Generic_Protected_Buffer;

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

Note that the data component "Data_Valid" is given an initial
value of "False". This simplifies the job of making sure the
Read entry cannot be executed until a Write procedure has
been executed.

package body Generic_Protected_Buffer is

   ----------------------
   -- Protected_Buffer --
   ----------------------

   protected body Protected_Buffer is

      ----------
      -- Read --
      ----------

      entry Read (Item : out Element_Type) when Data_Valid is
      begin
         Item := Buffer;
      end Read;

      -----------
      -- Write --
      -----------

      procedure Write (Item : in Element_Type) is
      begin
         Buffer := Item;
         Data_Valid := True;
      end Write;

   end Protected_Buffer;

end Generic_Protected_Buffer;

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

Notice the boundary condition specified in the implementation of
the Read entry. Read will execute "when Data_Valid = True".
The Write procedure sets the value of the buffer then sets
Data_Valid to True, releasing all tasks queued on the blocked
Read entry.


Jim Rogers
Colorado Springs, Colorado

Re: Ada Protected Object Tutorial #1

[Kaz Kylheku]

On Wed, 15 Dec 1999 22:27:17 -0700, James S. Rogers
<jimmaureenrogers@worldnet.att.net> wrote:
>This is the first of hopefully several examples of uses for Ada Protected
>Objects.

[ snip ]

>Protected Procedures:
>
>Protected procedures are typically used to alter the value of one or more
>data
>components in a protected object. The parameters of a protected procedure
>may have the "IN" mode, like functions. They may also have "OUT" mode,
>indicating that the value is write only, or "IN OUT" mode indicating that
>the
>parameter value can be read and updated. Only one task at a time may
>execute a protected procedure. Protected functions cannot access the
>protected object while it is being accessed by a protected procedure.

What if a protected procedure of an object calls another
protected procedure? Presumably this is allowed, which means that some
recursive lock has to be used for the implementation, or else the compiler has
to generate code that passes around secret ``already locked'' flags into
procedures. 

How does the user of the protected object compose atomic operations?

This approach to design is generally wasteful. It's more reasonable to have
public methods which always lock and unlock, and unprotected methods which
assume that an object is already locked. It's also useful for an object
to expose lock and unlock methods, and expose unprotected operations, so that
the user of the object can compose a sequence of operations into an indivisible
block.
 
>Protected Entries:
>
>Protected entries are just like protected functions with one small
>difference.
>Protected entries block untils a boundary condition becomes true. For
>example, you would use a protected entry to read from a protected
>bounded queue. The entry would block as long as the queue was empty.

What if you want to block for something in the middle of the critical region?
I assume that you can call a protected entry from within a protected procedure.

Could you expand on what flexibilities there exist within this framework?

Re: Ada Protected Object Tutorial #1

[John English]

Kaz Kylheku wrote:
> This approach to design is generally wasteful. It's more reasonable to have
> public methods which always lock and unlock, and unprotected methods which
> assume that an object is already locked. It's also useful for an object
> to expose lock and unlock methods, and expose unprotected operations, so that
> the user of the object can compose a sequence of operations into an indivisible
> block.

Congratulations, you've just invented the semaphore... :-)

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Ada Protected Object Tutorial #1

[Ed Falis]

In article <3858E5B3.9AB004E9@bton.ac.uk>,
  John English <je@bton.ac.uk> wrote:


> Congratulations, you've just invented the semaphore... :-)

Hmmn, is this reminiscent of Brinch-Hansen's article in IEEE Computer, about
30 years of work in concurrency being ignored?	;-)

"Round and round and round we go ..."

- Ed


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ada Protected Object Tutorial #1

[Usenet Poster Boy]

Ed Falis <falis@ma.aonix.com> writes:

> In article <3858E5B3.9AB004E9@bton.ac.uk>,
>   John English <je@bton.ac.uk> wrote:
> 
> 
> > Congratulations, you've just invented the semaphore... :-)
> 
> Hmmn, is this reminiscent of Brinch-Hansen's article in IEEE Computer, about
> 30 years of work in concurrency being ignored?	;-)
> 

Yes.

Re: Ada Protected Object Tutorial #1

[James S. Rogers]

Kaz Kylheku wrote in message ...
>On Wed, 15 Dec 1999 22:27:17 -0700, James S. Rogers
>What if a protected procedure of an object calls another
>protected procedure? Presumably this is allowed, which means that some
>recursive lock has to be used for the implementation, or else the compiler
has
>to generate code that passes around secret ``already locked'' flags into
>procedures.


What you want is handled by having a protected entry call other protected
entries. The "other" protected entries can be in the same protected object
or in some other protected object.

Protected entries are subject to a very strict queueing policy. When a task
calls a protected entry and the boundary condition is closed, the entry call
is queued. The calling task will, by default, suspend until the boundary
condition opens.

Once the boundary condition opens, all the tasks queued on that entry are
given access (one at a time) to the entry. No other tasks are allowed to
even
evaluate the boundary condition until the queue is drained. This approach
is intended to allow as much internal progress in a protected object as
possible.

One of the rules of using a protected entry is that the operations should be
very fast, and certainly must not be potentially blocking, such as an I/O
read. For providing mutual exclusion for potentially blocking actions you
really do want to use some form of a semaphore.

>How does the user of the protected object compose atomic operations?
>
>This approach to design is generally wasteful. It's more reasonable to have
>public methods which always lock and unlock, and unprotected methods which
>assume that an object is already locked. It's also useful for an object
>to expose lock and unlock methods, and expose unprotected operations, so
that
>the user of the object can compose a sequence of operations into an
indivisible
>block.

Another approach to handling potentially blocking operations is to provide
a task whose responsibility is to perform the potentially blocking
operation.
A protected object can be used to initiate the operation. The requesting
task writes a request to the protected object. The servicing task reads
the protected object and performs the potentially blocking operation.
When the servicing task has completed its operation it can communicate
the results to the calling task through a second protected object. This time
the servicing task does the writing and the requesting task does the
reading.

You can look at the protected objects as providing two simplex serial
communication paths.

Your problem requires fairly complex set of actions to be taken in some
atomic manner. The scheme described above combines protected
objects with tasks to provide what you need.

You can limit the amount of actual task blocking for the above scenario
by implementing bounded queues as protected objects. This allows a
high degree of asynchronous behavior between the requesting task and
the servicing task.


>What if you want to block for something in the middle of the critical
region?
>I assume that you can call a protected entry from within a protected
procedure.


No, as I stated earlier, you can call a protected entry from another
protected
entry.

>Could you expand on what flexibilities there exist within this framework?

This will really be the subject of some future tutorials. I like an involved
student!

Ada tasking semantics provide several other useful tools beyond protected
objects. These include direct synchronizing calls between tasks, known as
rendezvous, and various forms of the select statement.

A select statement has many uses. One simple example is a select with a
delay alternative. This allows you to, for instance, call a protected entry
and
only wait for a specified duration before giving up and going on to
something
else.

Example:

select
   Buffer.Read(Item);
or
   delay 0.01;  -- Delay 0.01 seconds
end select;

This calls the Read entry on the protected object Buffer. It also starts a
timer.
If the Read completes before the timer alarms, the timer is aborted.
If the timer alarms before the Read completes, the Read is aborted.
This gives the programmer very strong control over the timing associated
with attempting a protected entry call. You could, for instance, simply loop
around and try again in another time slice, or go on to do something else
based upon the fact that the Buffer was unavailable.

I will be showing more uses of protected objects, tasks, and their
interactions
in future messages.

Jim Rogers
Colorado Springs, Colorado

Re: Ada Protected Object Tutorial #1

[Robert A Duff]

"James S. Rogers" <jimmaureenrogers@worldnet.att.net> writes:

> This is the first of hopefully several examples of uses for Ada Protected
> Objects.

People seem to get confused about the difference between waiting for a
lock to become free, and waiting for a barrier to become true.  Only the
latter is called "blocking" in Ada 95 terms, and the former is sort of
swept under the rug.  If your tutorial can explain all that clearly and
simply, you will have done a great service.

- Bob

Re: Ada Protected Object Tutorial #1

[Robert A Duff]

kaz@ashi.footprints.net (Kaz Kylheku) writes:

> What if a protected procedure of an object calls another
> protected procedure? Presumably this is allowed, which means that some
> recursive lock has to be used for the implementation, or else the compiler has
> to generate code that passes around secret ``already locked'' flags into
> procedures. 

No, there's no such fancy run-time stuff in Ada 95's protected objects.
The rules ensure that it is known at compile time whether a lock should
be grabbed.  (And there is, of course, some potential for deadlock.)

> What if you want to block for something in the middle of the critical region?
> I assume that you can call a protected entry from within a protected procedure.

No, you can't.  If you want to block in the middle, then you have to
call the thing an "entry" and not a "procedure".  One common thing to do
is to have an entry with a True barrier, so it always goes right ahead,
but then it can block by requeuing to a different entry (of the same
protected object, or a different one); it will then block on a new
barrier.  Protected procedures, on the other had, can't block.

- Bob

Re: Ada Protected Object Tutorial #1

[Vladimir Olensky]

Robert A Duff wrote in message ...
>kaz@ashi.footprints.net (Kaz Kylheku) writes:


>> What if you want to block for something in the middle of the critical
region?
>> I assume that you can call a protected entry from within a protected
procedure.
>
>No, you can't.  If you want to block in the middle, then you have to
>call the thing an "entry" and not a "procedure".  One common thing to do
>is to have an entry with a True barrier, so it always goes right ahead,
>but then it can block by requeuing to a different entry (of the same
>protected object, or a different one); it will then block on a new
>barrier.  Protected procedures, on the other had, can't block.



Below is example with full explanation ( from Ada Rational ) which
is an excellent illustration to that.
Hope it will be helpful.

Regards,
Vladimir Olensky

=======================================
Ada Rational is available at:
http://www.adahome.com/LRM/95/Rationale/rat95html/rat95-contents.html
=====================================
Our final example introduces the ability to
requeue a call on another entry.

It sometimes happens that a service needs to be
provided in two parts and that the calling task has
to be suspended after the first part until
conditions are such that the second part can be
done. Two entry calls are then necessary but
attempts to program this in Ada 83 usually run into
difficulties; race conditions can arise in the
interval between the calls and there is often
unnecessary visibility of the internal protocol.


The example is of a broadcast signal. Tasks wait for
some event and then when it occurs all the waiting
tasks are released and the event reset. The
difficulty is to prevent tasks that call the wait
operation after the event has occurred, but before
the signal can be reset, from getting through. In
other words, we must reset the signal in preference
to letting new tasks through. The requeue statement
allows us to program such preference control. An
implementation is


   protected Event is
      entry Wait;
      entry Signal;
   private
      entry Reset;
      Occurred: Boolean := False;
   end Event;

   protected body Event is

      entry Wait when Occurred is
      begin
         null;        -- note null body
      end Wait;

      entry Signal when True is
      -- barrier is always true
      begin
         if Wait'Count > 0 then
            Occurred := True;
            requeue Reset;
         end if;
      end Signal;

      entry Reset when Wait'Count = 0 is
      begin
         Occurred := False;
      end Reset;

   end Event;

Tasks indicate that they wish to wait for the event
by the call

   Event.Wait;

and the happening of the event is notified by some
task calling

   Event.Signal;

whereupon all the waiting tasks are allowed to
proceed and the event is reset so that future calls
of Wait work properly.


The Boolean variable Occurred is normally false and
is only true while tasks are being released. The
entry Wait has no body but just exists so that
calling tasks can suspend themselves on its queue
while waiting for Occurred to become true.


The entry Signal is interesting. It has a
permanently true barrier and so is always processed.
If there are no tasks on the queue of Wait (that is
no tasks are waiting), then there is nothing to do
and so it exits. On the other hand if there are
tasks waiting then it must release them in such a
way that no further tasks can get on the queue but
then regain control so that it can reset the flag.
It does this by requeuing itself on the entry Reset
after setting Occurred to true to indicate that the
event has occurred.


The semantics of requeue are such that this
completes the action of Signal. However, remember
that at the end of the body of a protected entry or
procedure the barriers are reevaluated for those
entries which have tasks queued. In this case there
are indeed tasks on the queue for Wait and there is
also a task on the queue for Reset (the task that
called Signal in the first place); the barrier for
Wait is now true but of course the barrier for Reset
is false since there are still tasks on the queue
for Wait. A waiting task is thus allowed to execute
the body of Wait (being null this does nothing) and
the task thus proceeds and then the barrier
evaluation repeats. The same process continues until
all the waiting tasks have gone when finally the
barrier of Reset also becomes true. The original
task which called signal now executes the body of
Reset thus resetting Occurred to false so that the
system is once more in its initial state. The
protected object as a whole is now finally left
since there are no waiting tasks on any of the
barriers.


Note carefully that if any tasks had tried to call
Wait or Signal while the whole process was in
progress then they would not have been able to do so
because the protected object as a whole was busy.
This illustrates the two levels of protection and is
the underlying reason why a race condition does not
arise.

Another consequence of the two levels is that it
still all works properly even in the face of such
difficulties as timed and conditional calls and
aborts. The reader may recall, for example, that by
contrast, the Count attribute for entries in tasks
cannot be relied upon in the face of timed entry
calls.


A minor point to note is that the entry Reset is
declared in the private part of the protected type
and thus cannot be called from outside. Ada 95 also
allows a task to have a private part containing
private entries.


The above example has been used for illustration
only. The astute reader will have observed that the
condition is not strictly needed inside Signal;
without it the caller will simply always requeue and
then immediately be processed if there are no
waiting tasks. But the condition clarifies the
description. Indeed, the very astute reader might
care to note that we can actually program this
example in Ada 95 without using requeue at all. A
more realistic classic example is the disk scheduler
where a caller is requeued if the head is currently
over the wrong track.

In this section we have outlined the main features
of protected types. There are a number of detailed
aspects that we have not covered. The general
intent, however, should be clear. Protected types
provide a data-oriented approach to synchronization
which couples the high-level conditions (the
barriers) with the efficiency of monitors.
Furthermore the requeue statement provides a means
of programming preference control and thus enables
race conditions to be avoided.

It must be remembered, of course, that the existing
task model remains; the rendezvous will continue to
be a necessary approach in many circumstances of a
general nature (such as for directly passing
messages). But the protected object provides a
better paradigm for most data-oriented situations.

Re: Ada Protected Object Tutorial #1

[Mike Silva]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1702 bytes --]

(Ada newbie warning still in effect...)

If you don't allow clairvoyance or semaphores to indicate the beginning and
end of the transaction, how about building a "transaction request" (could be
a list or a set of ON bits in a modular <unsigned> type) and passing this
request to the protected object.  Then, each requested entry could, upon
finishing, examine the transaction request and requeue on the next requested
entry (requeue is an atomic action).  You'd also need to pass a parameter
that could accomodate all the requested transactions (e.g. an IN OUT record
<in C you'd pass a pointer to a struct>), since each requeued entry must
have either the same (original) parameters or no parameters.

Ada experts are of course invited to comment on the correctness of the
above...

Mike

Karel Th�nissen wrote in message <385984BC.1FB1@hello.nl>...
>....
>I am wondering whether there is a clean solution to the problem that Mr
>Kylheku presented: how can we combine several protected type services
>into one transaction-like construct without requiring clairvoyance or
>retrofitting. Of course we can always go back and change the code in the
>protected type and offer the combined invocation of the multiplicity of
>services as a single integrated service, but this option requires
>recoding, recompilation and re-verification.
>
>Solutions that do not use protected types are also welcome, if they are
>safe and clean. So bluntly providing the services without any
>concurrency protection and counting for the caller's willingness to use
>a semaphore is outside the competition.
>
>--
>
>Groeten, Karel Th�nissen
>
>Hello Technologies develops high integrity software for complex systems

Re: Ada Protected Object Tutorial #1

[Tucker Taft]

Kaz Kylheku wrote:
> ...
> 
> What if a protected procedure of an object calls another
> protected procedure? Presumably this is allowed, which means that some
> recursive lock has to be used for the implementation, or else the compiler has
> to generate code that passes around secret ``already locked'' flags into
> procedures.

As pointed out in another response, the compiler generates a different
call when calling a protected subprogram from the "inside" versus
calling it from the "outside" of the protected unit.  It can do that
because all "unlocked" calls are textually included within the protected unit.

This is just one illustration of the advantage provided by 
the fact that the protected type is a *language* construct rather 
than simply a part of a class library or operating system API.
Although I am sympathetic with the idea of doing as much as
possible just with class libraries, etc., synchronization is
a place where you can get a lot of advantage from getting the compiler
involved.  As a second example, the semantics for protected entry
bodies are such that the "convenient" thread can execute them when
the thread detects that the barrier is true.  This capability can
result in dramatically fewer thread context switches than an equivalent
synchronization mechanism built using typical mutex/condition-variable
primitives.  

Trying to provide this same capability via an "API"
is quite awkward, as it requires the programmer to bundle up an operation and
"submit" it along with some kind of boolean function, and allow the
underlying run-time system decide who evaluates the boolean function
and who executes the operation.  Almost all APIs instead are set up
so that the programmer's code evaluates the boolean condition outside
of the run-time system, and must do so repeatedly each time control
returns to the user's code, to ensure that the boolean is true by
at the moment when the user's code gets control.  This can result
in even more unnecessary context switches, and/or bugs if the
programmer neglects to build the evaluation of the boolean condition
into a loop around the condition-variable "wait" operation.

As one data point, a classic producer/consumer example with a
bounded buffer, when coded using a protected type versus using
mutex/condition variables, results in typically half as many
locks and unlocks, and one third as many context switches between
the producer and the consumer.  The mutex/condition variable
approach involves so much more work because each thread ends up
doing all the work "itself," rather than allowing the other thread
to do a little bit of work on its behalf while it already holds the lock.

> 
> How does the user of the protected object compose atomic operations?
> 
> This approach to design is generally wasteful. It's more reasonable to have
> public methods which always lock and unlock, and unprotected methods which
> assume that an object is already locked. It's also useful for an object
> to expose lock and unlock methods, and expose unprotected operations, so that
> the user of the object can compose a sequence of operations into an indivisible
> block.

One of the key principles of the "monitor" construct, on which protected
types is based, is that *all* critical sections associated with a given
lockable entity are gathered into a single module.  
Allowing random collections of operations to be made 
atomic makes any kind of analysis of a real-time system
significantly more difficult.  Also, if you expose operations that presume
all callers already have a lock, either they must themselves check,
or you have a situation ripe for bugs.  (Note that although
Java largely adheres to the monitor model, they violate it
in enough ways that the guarantees provided by the monitor model
are lost.  For example, they allow public unsynchronized operations
for objects that also have synchronized operations.  Also, they
allow synchronized blocks on a particular object *anywhere*, including
places that have no other methods accessible on the object.) 
    
> ...
-- 
-Tucker Taft   stt@averstar.com   http://www.averstar.com/~stt/
Technical Director, Distributed IT Solutions  (www.averstar.com/tools)
AverStar (formerly Intermetrics, Inc.)   Burlington, MA  USA

Re: Ada Protected Object Tutorial #1

[Karel Th�nissen]

John English wrote:
> 
> Kaz Kylheku wrote:
> > This approach to design is generally wasteful. It's more reasonable to have
> > public methods which always lock and unlock, and unprotected methods which
> > assume that an object is already locked. It's also useful for an object
> > to expose lock and unlock methods, and expose unprotected operations, so that
> > the user of the object can compose a sequence of operations into an indivisible
> > block.
> 
> Congratulations, you've just invented the semaphore... :-)

I noticed the smiley, but to be fair to the original poster this is not
quite true. He noticed that protected types are great if the caller
needs a single service from the protected type, but they are not that
great if you need more than one service from the same protected type.
Not only does the protected type solution require locking and unlocking
for every single service invocation, instead of one pair for the whole
deal, it also cannot avoid the situation that other tasks are serviced
in between two calls. This can make correctness difficult to prove.

Mr Kylheku did not claim any invention, he was just pointing out a
disadvantage of the protected type mechanism. BTW, even the protected
type uses a semaphore so his idea would not have been original and not
patentable (-8

I am wondering whether there is a clean solution to the problem that Mr
Kylheku presented: how can we combine several protected type services
into one transaction-like construct without requiring clairvoyance or
retrofitting. Of course we can always go back and change the code in the
protected type and offer the combined invocation of the multiplicity of
services as a single integrated service, but this option requires
recoding, recompilation and re-verification.

Solutions that do not use protected types are also welcome, if they are
safe and clean. So bluntly providing the services without any
concurrency protection and counting for the caller's willingness to use
a semaphore is outside the competition.

-- 

Groeten, Karel Th�nissen

Hello Technologies develops high integrity software for complex systems

Re: Ada Protected Object Tutorial #1

[Laurent Guerby]

"James S. Rogers" <jimmaureenrogers@worldnet.att.net> writes:
> Example:
> 
> select
>    Buffer.Read(Item);
> or
>    delay 0.01;  -- Delay 0.01 seconds
> end select;
> 
> This calls the Read entry on the protected object Buffer. It also starts a
> timer.
> If the Read completes before the timer alarms, the timer is aborted.
> If the timer alarms before the Read completes, the Read is aborted.

The semantic you describe here is the one of the (9.7.4) Asynchronous
Transfer of Control (select ... then abort), and it is different from
the (9.7.2) Timed Entry Calls that you used in your code. To describe
what your code does, you should change "Read completes" by "Read is
selected" (no longuer waiting on a queue. Once Read code has started,
it no longuer matters what the timer does (except in case of use of
requeue).

--LG

Re: Ada Protected Object Tutorial #1

[Laurent Guerby]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2704 bytes --]

Karel Th�nissen <thoenissen@hello.nl> writes:
> [...] He noticed that protected types are great if the caller
> needs a single service from the protected type, but they are not that
> great if you need more than one service from the same protected type.
> Not only does the protected type solution require locking and unlocking
> for every single service invocation, instead of one pair for the whole
> deal, it also cannot avoid the situation that other tasks are serviced
> in between two calls. 

This claim is wrong, when you're inside a protected procedure, calls
to other protected procedure on the same object are done
without locking of course.

> I am wondering whether there is a clean solution to the problem that Mr
> Kylheku presented: how can we combine several protected type services
> into one transaction-like construct without requiring clairvoyance or
> retrofitting. 

Retrofitting is easy and seems to be the cleaner solution to me
(that's where I would put the stuff by default).

protected P is
   procedure S1;
   procedure S2;
   procedure Retrofitted_S1_S2;
end P;

package body P is
  ...
  procedure Retrofitted_S1_S2 is
  begin
     S1; -- no locking happens
     S2;
  end Retrofitted_S1_S2;

end P;

> Of course we can always go back and change the code in the
> protected type and offer the combined invocation of the multiplicity of
> services as a single integrated service, but this option requires
> recoding, recompilation and re-verification.

You can avoid a bit of it with a "dynamic" clairvoyant solution: you
define a data structure describing the individual services to be called,
and have a protected procedure taking the data structure and calling
whatever it needs according to the parameter. I assume it would do
most of the job here. You can even use objects and dispatching
for the data structure ;-).

The general solution and to have a general transaction type, and to
manage locks according to what's going on just like a database
transaction manager would do, it requires lots of code and thinking
(and I don't think the language matters here if you're
talking about implementing the scheme).

What the Ada protected object offer is a clean solution (exclusion
trivially insured, no need for caller care on mutexes) for 99% of the
problems, and the remaining 1% is hard in any language I know anyway
;-).

> Solutions that do not use protected types are also welcome, if they are
> safe and clean. So bluntly providing the services without any
> concurrency protection and counting for the caller's willingness to use
> a semaphore is outside the competition.

Unless I'm mistaken, that was the solution Kal proposed (caller
willingness).

--LG

Re: Ada Protected Object Tutorial #1

[Kaz Kylheku]

On 17 Dec 1999 20:29:25 +0100, Laurent Guerby <guerby@acm.org> wrote:
>Karel Th�nissen <thoenissen@hello.nl> writes:
>> [...] He noticed that protected types are great if the caller
>> needs a single service from the protected type, but they are not that
>> great if you need more than one service from the same protected type.
>> Not only does the protected type solution require locking and unlocking
>> for every single service invocation, instead of one pair for the whole
>> deal, it also cannot avoid the situation that other tasks are serviced
>> in between two calls. 
>
>This claim is wrong, when you're inside a protected procedure, calls
>to other protected procedure on the same object are done
>without locking of course.

This requires the procedures to be passed information about whether the
object is locked by this thread or not. For example, a hidden parameterr.
In C++-like pseudocode, this might look like:

    void object::frobnicate(bool already_locked = false)
    {
	if (!already_locked);
	    lock();

	// frobnicate

	if (!already_locked)
	    unlock();
    }

That is overhead. Another thing that is possible is that the compiler might
generate two function images: one that assumes the lock and one that does not.
When a protected procedure calls another one for the same object, the compiler
will generate a call to the variant which does not acquire the lock. 

These solution requires some measure of clairvoyance: what if the protected
procedure calls into another subsystem which then calls back into a protected
procedure on the same object? How do you pass the ``already_locked'' knowledge
across calls to foreign subsystems?

The solution is probably to use recursive locks, which check the ID of the
calling against an ownership ID stored in the lock. Recursive locks are
slightly inefficient because they have to retrieve the ID of the current thread
and compare it.

Re: Ada Protected Object Tutorial #1

[Kaz Kylheku]

On Fri, 17 Dec 1999 00:41:27 GMT, Robert A Duff <bobduff@world.std.com> wrote:
>"James S. Rogers" <jimmaureenrogers@worldnet.att.net> writes:
>
>> This is the first of hopefully several examples of uses for Ada Protected
>> Objects.
>
>People seem to get confused about the difference between waiting for a
>lock to become free, and waiting for a barrier to become true.  Only the
>latter is called "blocking" in Ada 95 terms, and the former is sort of
>swept under the rug.  If your tutorial can explain all that clearly and
>simply, you will have done a great service.

Waiting for locks is inherently different from waiting for conditions to become
true. In the abstract sense, they are both similar: a thread has to be delayed.
But in practical terms, locks are held briefly, so waiting on a lock can be done
without using heavy weight scheduling; e.g. using spinlocks.  Or, in a kernel
running on the bare hardware, a combination of disabling interrupts and
spinning (multiple processors are present). In other words, techniques that
would be disastrous if applied to long waits.

Re: Ada Protected Object Tutorial #1

[Kaz Kylheku]

On Fri, 17 Dec 1999 23:28:22 GMT, Tucker Taft <stt@averstar.com> wrote:
>Trying to provide this same capability via an "API"
>is quite awkward, as it requires the programmer to bundle up an operation and
>"submit" it along with some kind of boolean function, and allow the
>underlying run-time system decide who evaluates the boolean function
>and who executes the operation.  Almost all APIs instead are set up
>so that the programmer's code evaluates the boolean condition outside
>of the run-time system, and must do so repeatedly each time control
>returns to the user's code, to ensure that the boolean is true by
>at the moment when the user's code gets control.  This can result

This is practical. The condition variable wait might be done inside a
protected kernel. It would be impractical to have, say, a UNIX kernel
call back into application code to determine if some predicate is true.

>in even more unnecessary context switches, and/or bugs if the
>programmer neglects to build the evaluation of the boolean condition
>into a loop around the condition-variable "wait" operation.

That loop around a condition variable wait is needed to resolve
spurious wakeups and race conditions. The logic gives more ways to
the implementor to provide a correct implementation.

Suppose your thread is waiting on a condition, and the condition is signalled.
It's time to reacquire the monitor (or mutex). But a thread running on another
CPU grabs it first and changes the object so that the condition the original
thread waited for is no longer valid.

I believe that providing guarantees against this sort of occurence introduces
overhead; that is, the cure may be worse than the ailment, particularly
on multiprocessors.

>As one data point, a classic producer/consumer example with a
>bounded buffer, when coded using a protected type versus using
>mutex/condition variables, results in typically half as many
>locks and unlocks, and one third as many context switches between
>the producer and the consumer.  The mutex/condition variable
>approach involves so much more work because each thread ends up
>doing all the work "itself," rather than allowing the other thread
>to do a little bit of work on its behalf while it already holds the lock.

Is there a paper about this which argues the case in more detail?

Re: Ada Protected Object Tutorial #1

[Robert A Duff]

kaz@ashi.footprints.net (Kaz Kylheku) writes:

> This requires the procedures to be passed information about whether the
> object is locked by this thread or not. For example, a hidden parameterr.

No, the Ada rules require a compile-time determination of whether a
given call is an "internal" call (no locking; assumed already locked),
or an "external" call.  There is no run-time overhead.

> These solution requires some measure of clairvoyance: what if the protected
> procedure calls into another subsystem which then calls back into a protected
> procedure on the same object? How do you pass the ``already_locked'' knowledge
> across calls to foreign subsystems?

That situation is, by definition, an "external" call.  It will attempt
to lock the protected object, and since it's the same object, it will
deadlock.  It's only in well-defined (compile-time-known) cases that are
defined as "internal" calls.

By the way, I'm not sure exactly what you mean by "clairvoyance" in this
case.

> The solution is probably to use recursive locks, which check the ID of the
> calling against an ownership ID stored in the lock. Recursive locks are
> slightly inefficient because they have to retrieve the ID of the current thread
> and compare it.

If you want recursive locks in Ada, you have to program them yourself --
the run-time system doesn't do that automatically.

- Bob

Re: Ada Protected Object Tutorial #1

[Robert A Duff]

kaz@ashi.footprints.net (Kaz Kylheku) writes:

> This is practical. The condition variable wait might be done inside a
> protected kernel. It would be impractical to have, say, a UNIX kernel
> call back into application code to determine if some predicate is true.

Please explain that in more detail.  I'm not sure what you're getting at
(efficiency, security, something else...).

> >in even more unnecessary context switches, and/or bugs if the
> >programmer neglects to build the evaluation of the boolean condition
> >into a loop around the condition-variable "wait" operation.
> 
> That loop around a condition variable wait is needed to resolve
> spurious wakeups and race conditions.

But the point is that with an Ada protected object, the loop is *not*
necessary -- when the task wakes up after waiting for some barrier
condition, it already owns the lock, and the condition is necessarily
True, because no other task can sneak in and modify things.

To be more precise, I should say that when an entry body is executed,
its barrier condition is True -- this execution can be done by any
task/thread, so it doesn't necessarily involve "waking up" as I said
above.  The point is that there's a piece of code depending on (say) the
fact that "this queue is empty", and when that code runs, the system
ensures that the queue is, in fact, empty -- that piece of code need not
check.

I understand why the loop is needed with Posix threads.

> I believe that providing guarantees against this sort of occurence introduces
> overhead; that is, the cure may be worse than the ailment, particularly
> on multiprocessors.

I'm not convinced.  It seems to me that repeatedly checking the same
condition is a cost, and the extra context switches (because one thread
can't check barriers on behalf of other threads) is another cost, which
Ada avoids.  Am I missing something?

- Bob

Re: Ada Protected Object Tutorial #1

[Kaz Kylheku]

On 18 Dec 1999 21:52:53 +0100, Laurent Guerby <guerby@acm.org> wrote:
>There is no clairvoyance involved, it is just that the Ada language is
>designed to allow an efficient implementation of protected
>procedures. The language defines as a bounded error when potentially
>blocking operation is called from a protected procedure, or when
>jumping around brings you back to the original protected object.

That's good. I follow the same principles generally, but without
language help it's easy to make mistakes like do some blocking
thing inside a tight critical section or create deadlock.

What do you do if you need a protected procedure to call out into
some other module which then calls back? 

Using explicit locks, I just unlock, do the call, lock again
thereby avoiding deadlock.

>See RM 9.5.1 for details.

Though I don't use Ada, I have a hard copy of the standard somewhere under my
desk, so I can take a look.

Re: Ada Protected Object Tutorial #1

[Kaz Kylheku]

On Sat, 18 Dec 1999 20:38:19 GMT, Robert A Duff <bobduff@world.std.com> wrote:
>> These solution requires some measure of clairvoyance: what if the protected
>> procedure calls into another subsystem which then calls back into a protected
>> procedure on the same object? How do you pass the ``already_locked'' knowledge
>> across calls to foreign subsystems?
>
>That situation is, by definition, an "external" call.  It will attempt
>to lock the protected object, and since it's the same object, it will
>deadlock.  It's only in well-defined (compile-time-known) cases that are
>defined as "internal" calls.

That's good! I like that. (I mean, I don't like deadlock, but I like the
rules :).

>> The solution is probably to use recursive locks, which check the ID of the
>> calling against an ownership ID stored in the lock. Recursive locks are
>> slightly inefficient because they have to retrieve the ID of the current thread
>> and compare it.
>
>If you want recursive locks in Ada, you have to program them yourself --
>the run-time system doesn't do that automatically.

Again, that is good. Recursive locks are brain-damaged.

Re: Ada Protected Object Tutorial #1

[Kaz Kylheku]

On Sat, 18 Dec 1999 20:55:05 GMT, Robert A Duff <bobduff@world.std.com> wrote:
>kaz@ashi.footprints.net (Kaz Kylheku) writes:
>
>> This is practical. The condition variable wait might be done inside a
>> protected kernel. It would be impractical to have, say, a UNIX kernel
>> call back into application code to determine if some predicate is true.
>
>Please explain that in more detail.  I'm not sure what you're getting at
>(efficiency, security, something else...).

All of the above. Think about  implementations in which all synchronizaiont
and scheduling is done in a protected kernel. 

>> >in even more unnecessary context switches, and/or bugs if the
>> >programmer neglects to build the evaluation of the boolean condition
>> >into a loop around the condition-variable "wait" operation.
>> 
>> That loop around a condition variable wait is needed to resolve
>> spurious wakeups and race conditions.
>
>But the point is that with an Ada protected object, the loop is *not*
>necessary -- when the task wakes up after waiting for some barrier
>condition, it already owns the lock, and the condition is necessarily
>True, because no other task can sneak in and modify things.

I believe that this either requires Hoare monitor semantics, or
it requires the compiler to generate a loop as necessary. 
E.g. if you were implementing Ada over POSIX threads, the loop would
be necessary, so your compiler would have to generate it.

>To be more precise, I should say that when an entry body is executed,
>its barrier condition is True -- this execution can be done by any
>task/thread, so it doesn't necessarily involve "waking up" as I said
>above.  The point is that there's a piece of code depending on (say) the
>fact that "this queue is empty", and when that code runs, the system
>ensures that the queue is, in fact, empty -- that piece of code need not
>check.

But the compiler may have to generate the loop nevertheless, depending
on the semantics of the underlying system interface. All it does is hide the
loop from the programmer, so it's a form of syntactic sugar.

It's not that the run-time is guaranteeing Hoare monitor semantics.

>I understand why the loop is needed with Posix threads.
>
>> I believe that providing guarantees against this sort of occurence introduces
>> overhead; that is, the cure may be worse than the ailment, particularly
>> on multiprocessors.
>
>I'm not convinced.  It seems to me that repeatedly checking the same
>condition is a cost, and the extra context switches (because one thread

It is a cost. I'm not convinced that it's not a cost that is also present
in Ada implementations, albeit hidden from the programmer. Unless the Ada
implementation has complete control over thread scheduling, which is obviously
not true of Ada implementations that run on top of many kinds of operating
systems.

In other words, it's not always easy to implement the operation ``select this
thread to be the next owner of this lock''. It also may mean delaying a thread
which is more ready to be the owner, because it is already running on another
processor and is a few instructions away from trying to grab the lock.

The cost of evaluating predicates should be weighed against the cost of forcing
a particular execution order, and the scheduling overheads that implies.

>can't check barriers on behalf of other threads) is another cost, which
>Ada avoids.  Am I missing something?

I see; to put this into perspective, doing this in a language that doesn't have
explicit support for these barriers, what you could do (for example) have each
waiting thread register a pointer to a callback function which evaluates the
predicate on behalf of that thread. It's an intriguing technique. I don't
see how it can eliminate redundant predicate evaluations though, unless
the implementation controls scheduling. You need to implement some sort of
``atomically pass ownership of the protected object to this thread'' operation.

Re: Ada Protected Object Tutorial #1

[Karel Th�nissen]

Laurent Guerby wrote:
> Karel Th�nissen <thoenissen@hello.nl> writes:

> > [...] He noticed that protected types are great if the caller
> > needs a single service from the protected type, but they are not that
> > great if you need more than one service from the same protected type.
> > Not only does the protected type solution require locking and unlocking
> > for every single service invocation, instead of one pair for the whole
> > deal, it also cannot avoid the situation that other tasks are serviced
> > in between two calls.
> 
> This claim is wrong, when you're inside a protected procedure, calls
> to other protected procedure on the same object are done
> without locking of course.

You object to a claim that I never made. The difference between the
problem I presented and your observation is that in my problem
description services on the protected instance are strung together by,
and on behalf of, the client code (=caller), whereas your observation is
about stringing together service invocations inside the supplier code.
Totally different piece of cake. However, it provides the solution if
the designer of the protected class can predict all the series of
service invocations that clients are going to make and has freedom to
change the code of the protected class.

> > I am wondering whether there is a clean solution to the problem that Mr
> > Kylheku presented: how can we combine several protected type services
> > into one transaction-like construct without requiring clairvoyance or
> > retrofitting.
> 
> Retrofitting is easy and seems to be the cleaner solution to me
> (that's where I would put the stuff by default).
> 
> protected P is
>    procedure S1;
>    procedure S2;
>    procedure Retrofitted_S1_S2;
> end P;
> 
> package body P is
>   ...
>   procedure Retrofitted_S1_S2 is
>   begin
>      S1; -- no locking happens
>      S2;
>   end Retrofitted_S1_S2;
> 
> end P;

Yes, this works, if you have the source code... And even if you have the
source code, quality assurance policies can inhibit your opening it.
However, I agree that it is easy if you are free to open the code.
 
> > Of course we can always go back and change the code in the
> > protected type and offer the combined invocation of the multiplicity of
> > services as a single integrated service, but this option requires
> > recoding, recompilation and re-verification.

This is the solution that you showed.
 
> You can avoid a bit of it with a "dynamic" clairvoyant solution: you
> define a data structure describing the individual services to be called,
> and have a protected procedure taking the data structure and calling
> whatever it needs according to the parameter. I assume it would do
> most of the job here. You can even use objects and dispatching
> for the data structure ;-).

Well, this is the best I came up with. This is some sort of interpreter!

> The general solution and to have a general transaction type, and to
> manage locks according to what's going on just like a database
> transaction manager would do, it requires lots of code and thinking
> (and I don't think the language matters here if you're
> talking about implementing the scheme).
> 
> What the Ada protected object offer is a clean solution (exclusion
> trivially insured, no need for caller care on mutexes) for 99% of the
> problems, and the remaining 1% is hard in any language I know anyway
> ;-).

I agree completely, and I would not plea for the dismissal of this
feature in Ada.

> > Solutions that do not use protected types are also welcome, if they are
> > safe and clean. So bluntly providing the services without any
> > concurrency protection and counting for the caller's willingness to use
> > a semaphore is outside the competition.
> 
> Unless I'm mistaken, that was the solution Kal proposed (caller
> willingness).

-- 

Groeten, Karel Th�nissen

Hello Technologies develops high integrity software for complex systems

Re: Ada Protected Object Tutorial #1

[Laurent Guerby]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 740 bytes --]

Karel Th�nissen <thoenissen@hello.nl> writes:
> [...] Yes, this works, if you have the source code... And even if
> you have the source code, quality assurance policies can inhibit
> your opening it. [...]

I assume any QA policy will beat down programs where clients do all
the locking work, that's just too dangerous, and need a complete proof
again each time one line of client code is added.  I have a hard time
imagining QA forcing you to work around an incomplete API by damaging
the safety of the system, instead of letting you put your stuff where
it belongs and where it's easy to prove correct. (That's why I didn't
understand your earlier clain, sorry about that ;-).

Do you have any concrete example of such policy?

--LG

Re: Ada Protected Object Tutorial #1

[Laurent Guerby]

kaz@ashi.footprints.net (Kaz Kylheku) writes:
> >This claim is wrong, when you're inside a protected procedure, calls
> >to other protected procedure on the same object are done
> >without locking of course.
> 
> This requires the procedures to be passed information about whether
> the object is locked by this thread or not. For example, a hidden
> parameterr.

No, the Ada compiler can statically make the difference between an
internal and external call. There is no locking involved at all for
internal calls. That is the fundamental point of protected procedures,
they are lightweight and efficient, but you are of course restricted
on what you do inside them.  If you need to do more things, you use an
entry, and then there are locks and all the stuff you mention.

> Another thing that is possible is that the compiler might generate
> two function images: one that assumes the lock and one that does
> not.  When a protected procedure calls another one for the same
> object, the compiler will generate a call to the variant which does
> not acquire the lock.

That is exactly what GNAT does (and I assume other Ada compilers do
the same).

> These solution requires some measure of clairvoyance: what if the
> protected procedure calls into another subsystem which then calls
> back into a protected procedure on the same object? How do you pass
> the ``already_locked'' knowledge across calls to foreign subsystems?

There is no clairvoyance involved, it is just that the Ada language is
designed to allow an efficient implementation of protected
procedures. The language defines as a bounded error when potentially
blocking operation is called from a protected procedure, or when
jumping around brings you back to the original protected object.

See RM 9.5.1 for details.

--LG

Re: Ada Protected Object Tutorial #1

[Laurent Guerby]

kaz@ashi.footprints.net (Kaz Kylheku) writes:
> That's good. I follow the same principles generally, but without
> language help it's easy to make mistakes like do some blocking
> thing inside a tight critical section or create deadlock.

Agreed.

> What do you do if you need a protected procedure to call out into
> some other module which then calls back? 

You wouldn't do this inside the protected procedure code.

> Using explicit locks, I just unlock, do the call, lock again
> thereby avoiding deadlock.

That's how you would do it in Ada too (with an explicit mutex and
caller care). The protected objects aren't designed to solve this kind
of problem, they solve cleany most of the cases, if you have a complex
nested locks scheme, you have to do it by hand (note that the GNAT
runtime just does this, it has a very fine grained locking model by
default to allow concurrency inside itself).

> Though I don't use Ada, I have a hard copy of the standard somewhere under my
> desk, so I can take a look.

Or online: <http://www.adahome.com/rm95/>

You can get the annotated version (giving the insight on
the language design) in ASCII at 

<http://www.adaic.org/standards/95lrm/LRMascii/aarm.txt>

(There is also a PostScript version, beware it's 800 pages ;-).

--LG

Re: Ada Protected Object Tutorial #1

[swhalen]

In comp.lang.ada Kaz Kylheku <kaz@ashi.footprints.net> wrote:
...
: It is a cost. I'm not convinced that it's not a cost that is also present
: in Ada implementations, albeit hidden from the programmer. Unless the Ada
: implementation has complete control over thread scheduling, 
  which is obviously
: not true of Ada implementations that run on top of many kinds of operating
: systems.
...

This "clairvoyance" we seem to be talking about is _not_ "hidden from
the programmer".  In Ada you (the programmer) pay a one time "price"
in learning the Ada95 language and you get the benefit of some very
well thought out tools like protected objects.

Once you pay the price of learning how to use Ada95 properly, you gain
the benefit of the compiler and run-time being able to handle many
common situations without the comiler having to ever call any
underlying operating system facility at all. Thus there is a genuine
reduction in overhead compared to using POSIX or other system
facilities in the manner you discuss.  Ada95's tools do _not_ try to
cover all situations, but try to cover many of the problems most
commonly encountered in the real world.

In otherwords: the Ada95 programmer pays a price in the discipline of
knowing the language and using it properly. In return you get a
certain amount of "clairvoyance" in that the compiler can and does do
some of the things you've been assuming it cannot do (which C or C++
or POSIX can't do).  It's not magic: it's the benefit of a rigorously
defined set of semantics that allow the compiler to "know" that it can
control certain things you are used to turning over to POSIX or
another API to the OS.

Steve

-- 
{===--------------------------------------------------------------===}
                Steve Whalen     swhalen@netcom.com
{===--------------------------------------------------------------===}

Re: Ada Protected Object Tutorial #1

[Kaz Kylheku]

On 19 Dec 1999 03:07:52 GMT, swhalen@netcom.com <swhalen@netcom.com> wrote:
>In comp.lang.ada Kaz Kylheku <kaz@ashi.footprints.net> wrote:
>...
>: It is a cost. I'm not convinced that it's not a cost that is also present
>: in Ada implementations, albeit hidden from the programmer. Unless the Ada
>: implementation has complete control over thread scheduling, 
>  which is obviously
>: not true of Ada implementations that run on top of many kinds of operating
>: systems.
>...
>
>This "clairvoyance" we seem to be talking about is _not_ "hidden from
>the programmer".  In Ada you (the programmer) pay a one time "price"
>in learning the Ada95 language and you get the benefit of some very
>well thought out tools like protected objects.
>
>Once you pay the price of learning how to use Ada95 properly, you gain
>the benefit of the compiler and run-time being able to handle many
>common situations without the comiler having to ever call any
>underlying operating system facility at all. Thus there is a genuine
>reduction in overhead compared to using POSIX or other system
>facilities in the manner you discuss.

POSIX is an interface which can also be implemented such that it handles common
situations without calling into an operating system.  A trivial example of that
would be seizing a pthread_mutex_t lock when there is no contention.
The POSIX threading functions are not necessarily system calls.

Just because something is not built into the language syntax, and the name
of its specification rhymes with UNIX doesn't mean that it's a call into the
opearting system.

> Ada95's tools do _not_ try to
>cover all situations, but try to cover many of the problems most
>commonly encountered in the real world.

The protected types as described are utterly useless to me because of the
limitations of what they can do. I can't think of any software I have written
in the past two years in which protected types could have been applied (had I
been working in Ada). In almost everything I have done, there are complex
relationship among the collaborating objects. There are calls among the objects
from within critical regions, as well as condition waits in arbitrary places.

>In otherwords: the Ada95 programmer pays a price in the discipline of
>knowing the language and using it properly.

Non sequitur. I was talking about the cost of implementing specific semantics,
such as atomically passing ownership of a locked object to a specific thread so
that the thread doesn't have to re-evaluate a predicate. Not some human
resource cost of learning. I don't appreciate people going wishy washy on me in
a technical debate.

The fact is, if you have a thread running on another processor that is about to
seize a lock, and you have to suspend that thread because the current owner is
passing ownership of the lock to some specific thread, that is a waste of
processor time. 

I'd like to hear from somone who has experience with these so-called protected 
types on a machine with 16 processors or more. What is the scalability like of
existing implementations?

Re: Ada Protected Object Tutorial #1

[Robert Dewar]

In article <slrn85om2b.dog.kaz@ashi.FootPrints.net>,
  kaz@ashi.footprints.net wrote:
> The protected types as described are utterly useless to me
> because of the limitations of what they can do. I can't think
> of any software I have written in the past two years in which
> protected types could have been applied (had I been working in
> Ada). In almost everything I have done, there are complex
> relationship among the collaborating objects. There are calls
> among the objects from within critical regions, as well as
> condition waits in arbitrary places.

You have not quite got the idea yet :-)

For such complex collaborating objects, we use tasks in Ada.
Indeed everything that can be done with a protected object
can be done with a task, it is just that tasks require more
apparatus and hence have higher overhead.

Protected objects are typically used to provide low level
data oriented synchronization primitives. For example it is
straightforward to construct a classical semaphore using a
protected type, or (and this is the important point) any
other similar synchronization mechanism, customized to the
needs of your application.

> Non sequitur. I was talking about the cost of implementing
> specific semantics, such as atomically passing ownership of a
> locked object to a specific thread so that the thread doesn't
> have to re-evaluate a predicate.

But keeping track of ownership is pretty critical for the
purposes of implementing priority inheritance. One of the
important features of Ada is that much of the programmer's
job in avoiding priority inversion is automatic.

There was incidentally no wishy-washy in the response, you
just missed the underlying point :-)

> The fact is, if you have a thread running on another processor
> that is about to seize a lock, and you have to suspend that
> thread because the current owner is passing ownership of the
> lock to some specific thread, that is a waste of processor
> time.

It is never a waste of processor time to be careful about
priority inversions. The world is scattered with examples of
real time applications that have been written ferociously
carefully to minimize task switching etc, but because of
priority inversion fall on their faces. As always choosing
the correct algorithms is more important, and implementing
incorrect or dangerous algorithms efficiently is not a good
substitute!

You are really operating from an insufficient knowledge of
Ada here. I would recommend reading the Burns and Welling
book on real time programming (this is not entirely Ada
specific, but it does give a good view of how common real
time paradigms are implemented in Ada). See www.adapower.com
for a full reference.

> I'd like to hear from somone who has experience with these
> so-called protected types on a machine with 16 processors or
> more. What is the scalability like of existing
> implementations?

Our SGI customers use protected types routinely in SGI
multi-processor machines, and they work just fine. Again,
your problem is that you have the wrong view of protected
types. They are low level gizmos that simply provide basic
access to simple locking operations from which other primitives
can be constructed.

For example, if you want a little array that multiple processors
need to read and write with appropriate protection, then at the
OS level, you need a lock and you need to set and free the lock
appropriately, and you need to worry about priority inversion
effects that could happen if you don't worry about them (e.g.
from a high priority task preempting a low priority task that
owns the lock).

All this would be automated with a simple protected type in
Ada, including worrying about inversion (that's achieved by the
use of ceiling priority protocol, which is of course a super
efficient method on a single processor, and still probably the
best approach on a multi-processor, but you do need an OS level
lock in this case).

There is certainly nothing magic in Ada, but what Ada gives you
is

a) A semantic abstraction level that is one step above the
direct posix primitives, resulting in safer, easier to maintain
code. This abstraction is achieved without introducing any
significant inefficiency.

b) Full portability. Even fully standards compliant posix
implementations vary in ways that can compromise protability.
For example, if you raise your priority, and then lower it,
can you lose control to an equal priority task? Answer for
POSIX is may be -- implementation dependent. Answer for Ada
is no.


Robert Dewar
Ada Core Technologies

P.S. since this goes to comp.programming.threads, it is perhaps
appropriate to remind people that complete production quality
Ada 95 compilers for all common targets are freely available.
Go to the FTP directory pub/gnat at cs.nyu.edu for details.
There you will find public releases of the GNAT technology.
These are intended for student and research use, and are just
the thing for familiarizing yourself with the advantages that
Ada can bring to threads oriented programming.

Corresponding fully supported commercial versions of GNAT
Professional are available from Ada Core Technologies
(sales@gnat.com).


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ada Protected Object Tutorial #1

[Laurent Guerby]

kaz@ashi.footprints.net (Kaz Kylheku) writes:
> POSIX is an interface which can also be implemented such that it
> handles common situations without calling into an operating system.
> A trivial example of that would be seizing a pthread_mutex_t lock
> when there is no contention.  The POSIX threading functions are not
> necessarily system calls.
> 
> Just because something is not built into the language syntax, and
> the name of its specification rhymes with UNIX doesn't mean that
> it's a call into the opearting system.

I believe what Steve said had nothing to do at all with the
implementation of POSIX as system calls or whatever, he was talking
semantics. Some seemingly simple Ada concurrency constructs can lead
to a very complex POSIX calls/lock/condition scheme, complex not
necessarily meaning inefficient implementation in this context, just
that some of the semantic complexity is taken care of by your
implementation.

> The protected types as described are utterly useless to me because
> of the limitations of what they can do. I can't think of any
> software I have written in the past two years in which protected
> types could have been applied (had I been working in Ada). In almost
> everything I have done, there are complex relationship among the
> collaborating objects. There are calls among the objects from within
> critical regions, as well as condition waits in arbitrary places.

I believe you know about the Ada requeue statement (9.5.4) if you're
talking about collaborating objects, right?

> The fact is, if you have a thread running on another processor that
> is about to seize a lock, and you have to suspend that thread
> because the current owner is passing ownership of the lock to some
> specific thread, that is a waste of processor time.

One thing you're missing is that with protected objects and the Ada
queue/barrier model there is no mandatory unlocking/relocking involved
when there is "contention". The implementation can use same thread
that made the condition true for other threads to continue service
other threads that were blocked on an entry with a flase barrier.

- at t=t0, T1 is inside PO.S1, T2 is blocked on PO.S2 with barrier B2.

- at t=t1, T1 finishes PO.S1 code, the Ada runtime still in T1 context
reevaluate B2, finds it true and will execute PO.S2 still witin T1 context
at the end of PO.S2 code, T2 is released and T1 thread might continue
to do other things on PO.

Note here that it is one implementation model, but it is not the only
one, an implementation is free to do "inefficient" locking/unlocking
all over the place, or to use one or more internal thread to execute
PO code if it believes it is more efficient.

RM 9.5.3:

RM> 22 An implementation may perform the sequence of steps of a protected
RM> action using any thread of control; it need not be that of the task
RM> that started the protected action.  If an entry_body completes without
RM> requeuing, then the corresponding calling task may be made ready
RM> without waiting for the entire protected action to complete.
RM> 
RM> 	  22.a Reason: These permissions are intended to allow
RM> 	  flexibility for implementations on multiprocessors.  On a
RM> 	  monoprocessor, which thread of control executes the protected
RM> 	  action is essentially invisible, since the thread is not
RM> 	  abortable in any case, and the "current_task" function is not
RM> 	  guaranteed to work during a protected action (see C.7).

> I'd like to hear from somone who has experience with these so-called
> protected types on a machine with 16 processors or more. What is the
> scalability like of existing implementations?

As for anything related to performance, you have to provide a specific
benchmark that defines what "scalability" you are talking about here,
otherwise we'll be stuck in meaningless discussions. 

Also assuming that the Ada implementation uses POSIX thread, you can
always at least get the same "scalability" (if it proves to be good)
by coding directly your POSIX calls the way the Ada implementation
does, but then you'll probably get a more meaningful comparison by
looking at the POSIX vs Ada complexity of code.

Also I believe your experience is exceptional with super-complex
concurrent systems, what are you implementating for a living?

--LG

Re: Ada Protected Object Tutorial #1

[Stanley R. Allen]

Laurent Guerby wrote:
> 
> kaz@ashi.footprints.net (Kaz Kylheku) writes:
> 
> > Though I don't use Ada, I have a hard copy of the standard somewhere under my
> > desk, so I can take a look.

Make sure the version under your desk is the Ada 95 (not 83) standard.

> Or online: <http://www.adahome.com/rm95/>

This is it.

> You can get the annotated version (giving the insight on
> the language design) in ASCII at
> 
> <http://www.adaic.org/standards/95lrm/LRMascii/aarm.txt>
> 

But you are probably better off reading the higher-level
discussions in the Ada 95 Rationale, especially the
section having to do with Tasking and Protected Objects:

  http://www.adaic.org/standards/95rat/RAThtml/rat95-p2-9.html

The annotated reference manual is mainly intended for
language lawyers and compiler implementors.

-- 
Stanley Allen
mailto:s_allen@hso.link.com

Re: Ada Protected Object Tutorial #1

[Robert A Duff]

Brian Orpin <abuse@borpin.co.uk> writes:

> On 18 Dec 1999 21:52:53 +0100, Laurent Guerby <guerby@acm.org> wrote:

> >No, the Ada compiler can statically make the difference between an
>                           ^^^^^^^^^^
> >internal and external call. There is no locking involved at all for
> >internal calls. That is the fundamental point of protected procedures,
> >they are lightweight and efficient, but you are of course restricted
> >on what you do inside them.  If you need to do more things, you use an
> >entry, and then there are locks and all the stuff you mention.
> 
> I would hope that this could be forced on the compiler as in a
> multiprocessor system with some form of Dual-Port-RAM (or a VME bus) the
> compiler would not have a hope in hell of determining statically whether
> to lock or not.
> 
> It also needs a definition of internal and external.  Data may be passed
> 'internally' but if it is also available externally then it must be
> treated as an external call.

Yes, "internal" and "external" calls are defined in the Ada Reference
Manual.  This definition allows the compiler to distinguish the two at
compile time.  It has nothing to do with dual-port RAM and so forth.

- Bob

Re: Ada Protected Object Tutorial #1

[Vladimir Olensky]

Kaz Kylheku wrote in message ...
>On Fri, 17 Dec 1999 23:28:22 GMT, Tucker Taft <stt@averstar.com> wrote:
>>As one data point, a classic producer/consumer example with a
>>bounded buffer, when coded using a protected type versus
>>usingmutex/condition variables, results in typically half as many
>>locks and unlocks, and one third as many context switches
>>between the producer and the consumer.  The mutex/condition
>>variable approach involves so much more work because each
>>thread ends up doing all the work "itself," rather than allowing the
>>other threadto do a little bit of work on its behalf while it already
>> holds the lock.
>
>Is there a paper about this which argues the case in more detail?

Below is an example from Ada Rational:
http://www.adahome.com/LRM/95/Rationale/rat95html/rat95-contents.html

Regards,
Vladimir Olensky

==================================================
9.1.3 Efficiency of Protected Types

Protected types provide an extremely efficient mechanism; the
ability to use the thread of control of one task to execute a
protected operation on behalf of another task reduces the
overhead of context switching compared with other paradigms.
Protected types are thus  not only much more efficient than the
use of an agent task and associated rendezvous, they are also
 more efficient than traditional  monitors or semaphores in many
circumstances.

As an example consider the following very simple protected
 object which implements a single buffer between a producer
and a consumer task.


   protected Buffer is
      entry Put(X: in Item);
      entry Get(X: out Item);
   private
      Data: Item;
      Full: Boolean := False;
   end;

   protected body Buffer is
      entry Put(X: in Item) when not Full is
      begin
         Data := X;  Full := True;
      end Put;

      entry Get(X: out Item) when Full is
      begin
         X := Data;  Full := False;
      end Get;
   end Buffer;

This object can contain just a single buffered value of the type Item
in the variable Data; the boolean Full indicates whether or not the
buffer contains a value. The barriers ensure that reading and writing
 of the variable is interleaved so that each value is only used once.
 The buffer is initially empty so that the first call that will be
processed will be of Put.


A producer and consumer task might be


   task body Producer is
   begin
      loop
         ... -- generate a value
         Buffer.Put(New_Item);
      end loop;
   end Producer;

   task body Consumer is
   begin
      loop
         Buffer.Get(An_Item);
         ... -- use a value
      end loop;
   end Consumer;

In order to focus the discussion we will assume that both tasks
have the same priority and that a run until blocked scheduling
algorithm is used on a single processor. We will also start by
giving the processor to the task Consumer.


The task Consumer will issue a call of Get, acquire the lock and
 then find that the barrier is false thereby causing it to be queued
 and to release the lock. The Consumer is thus blocked and so a
 context switch occurs and control passes to the task Producer.
 This sequence of actions can be symbolically described by


   Get(An_Item);
      lock
         queue
      unlock
   switch context

The task Producer issues a first call of Put, acquires the lock,
 successfully executes the body of Put thereby filling the buffer
and setting Full to False. Before releasing the lock, it reevaluates
 the barriers and checks the queues to see whether a suspended
 operation can now be performed. It finds that it can and executes
 the body of the entry Get thereby emptying the buffer and causing
 the task Consumer to be marked as no longer blocked and thus
 eligible for processing. Note that the thread of control of the
 producer has effectively performed the call of Get on behalf of the
 consumer task; the overhead for doing this is essentially that of a
 subprogram call and a full context switch is not required. This
 completes the sequence of protected actions and the lock is
 released.


However, the task Producer still has the processor and so it
cycles around its loop and issues a second call of Put. It acquires
 the lock again, executes the body of Put thereby filling the buffer
 again. Before releasing the lock it checks the barriers but of
 course no task is queued and so nothing else can be done; it
 therefore releases the lock.


The task Producer still has the processor and so it cycles around
 its loop and issues yet a third call of Put. It acquires the lock but
this time it finds the barrier is false since the buffer is already full.
It is therefore queued and releases the lock. The producer task
is now blocked and so a context switch occurs and control at last
 passes to the consumer task. The full sequence of actions
 performed by the producer while it had the processor are


   Put(New_Item);
      lock
         Data := New_Item;  Full := True;
         scan: and then on behalf of Consumer
         An_Item := Data;  Full := False;
         set Consumer ready
      unlock
   Put(New_Item);
      lock
         Data := New_Item:  Full := True;
         scan: nothing to do
      unlock
   Put(New_Item);
      lock
         queue
      unlock
   switch context

The consumer task now performs a similar cycle of actions before
 control passes back to the producer and the whole pattern then
repeats. The net result is that three calls of Put or Get are
performed between each full context switch and that each call of
Put or Get involves just one lock operation.

This should be contrasted with the sequence required by the
corresponding program using primitive operations such as binary
semaphores (mutexes). This could be represented by


   package Buffer is
      procedure Put(X: in Item);
      procedure Get(X: out Item);
   private
      Data: Item;
      Full: Semaphore := busy;
      Empty: Semaphore := free;
   end;

   package body Buffer is
      procedure Put(X: in Item) is
      begin
         P(Empty);
         Data := X;
         V(Full);
      end Put;

      procedure Get(X: out Item) is
      begin
         P(Full);
         X := Data;
         V(Empty);
      end Get;
   end Buffer;

In this case there are two lock operations for each call of Put and
Get, one for each associated semaphore action. The behavior is
now as follows (assuming once more that the consumer has the
processor initially). The first call of Get by the consumer results in
the consumer being suspended by P(Full) and a context switch to
the producer occurs.

The first call of Put by the producer is successful, the buffer is filled
and the operation V(Full) clears the semaphore upon which the
consumer is waiting. The second call of Put is however blocked by
P(Empty) and so a context switch to the consumer occurs. The
consumer is now free to proceed and empties the buffer and
performs V(Empty) to clear the semaphore upon which the
producer is waiting. The next call of Get by the consumer is
blocked by P(Full) and so a context switch back to the producer
occurs.

The net result is that a context switch occurs for each call of Put or
Get. This contrasts markedly with the behavior of the protected
object where a context switch occurs for every three calls of Put or
Get.

In conclusion we see that the protected object is much more
efficient than a semaphore approach. In this example it as a factor
of three better regarding context switches and a factor of two better
regarding locks.


Observe that the saving in context switching overhead depends to
some degree on the run-until-blocked scheduling and on the
producer and consumer being of the same priority. However, the
saving on lock and unlock overheads is largely independent of
scheduling issues.


The interested reader should also consult [Hilzer 92] which
considers the more general bounded buffer and shows that
monitors are even worse than semaphores with regard to
potential context switches.

Re: Ada Protected Object Tutorial #1

[Robert I. Eachus]

Kaz Kylheku wrote:
  
> What do you do if you need a protected procedure to call out into
> some other module which then calls back?
> 
> Using explicit locks, I just unlock, do the call, lock again
> thereby avoiding deadlock.

    Although I think that the other issues have been explained
throughly, there are a couple of special things about using protected
objects in this situation.
First note that we are discussing protected OBJECTs.  A protected object
can and will have state variables which are protected by the object. 
But, since a protected object can and will run in multiple threads, per
thread locking is no help.

    However, if you want to do allow potentially recursive calls on a
per thread basis, it is not that hard to do, and surprisingly the
overhead is trivial.  Have the calling task pass in its
identity--Ada.Task_ID.Current_Task--and save it when locking.  Of course
the easy implementation is to use a value of Null_Task_ID to mean
unlocked.

    But there is a much more interesting case.   Assume you have an
array of state variable sets, including Task_IDs.   For example, you are
interfacing to a (local) database on behalf of many client tasks.  Each
task can have a transaction in process, with the protected object
serializing interaction with the data, while the calling tasks can
interleave other (potentially blocking) actions into the transaction.

-- 

                                        Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...

Re: Ada Protected Object Tutorial #1

[Kenneth Almquist]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 3290 bytes --]

Karel Th�nissen <thoenissen@hello.nl> wrote:
> I am wondering whether there is a clean solution to the problem that Mr
> Kylheku presented: how can we combine several protected type services
> into one transaction-like construct without requiring clairvoyance or
> retrofitting.

One approach is to have the client perform the locking, and to specify
an interface to the object which forces the client to lock the object
before performing any other operations on it.  E.g.:

    package Object_Package is

        type Object is limited private;
        type Object_Ptr is access all Obj;
            -- Object is the type of the objects we want to protect.

        type Object_Handle is limited private;
            -- An Object_Handle is used to refer to an Object.  Only one
            -- Object_Handle is allowed to refer to a given object at
            -- any one time, so if you have an Object_Handle referring
            -- to an Object, you can safely operate on that Object
            -- without worrying about another task modifying the
            -- Object.

        procedure Set_Handle(Handle : Object_Handle, Obj : Object_Ptr);
            -- If Obj is not null, then this routine will make Handle
            -- refer to the specified Object.  If another Object_Handle
            -- current refers to the Object, then this routine will
            -- block until that is no longer the case.
            --
            -- Since only one Object_Handle can refer to an Object at
            -- any one time, when you are done using an Object, you
            -- should make the Object_Handle stop referring to it,
            -- either by calling Set_Handle with the Obj parameter
            -- set to null, or by destroying the Object_Handle.

        procecure Op_1(Handle : Object_Handle);
        procecure Op_2(Handle : Object_Handle);
            -- These are operations which apply to Objects.  To call them,
            -- you pass an Object_Handle rather than an Object.  This
            -- ensures that two tasks cannot perform an operation on the
            -- same object at the same time.

        procedure Op_1(Obj : Object_Ptr);
            -- This is a convenience function, intended to be used when
            --  you only want to perform a single Op_1 on an object.  It
            -- is equivalent to:
            --
            --     procedure Op_1(Obj : Object_Ptr) is
            --         Handle : Object_Handle;
            --     begin
            --         Set_Handle(Handle, Obj);
            --         Op_1(Handle);
            --     end Op_1;

    end Object_Package;

Object is implemented as a protected type, and includes Lock and Unlock
operations.  An Object_Handle is a record containing an Object_Ptr.
Set_Handle unlocks the Object currently pointed to by the Object_Handle
(unless the handle is null), and locks the new Object (unless the new
Object_Ptr is null).  Object_Handle is implemented as a controlled type,
so that the Object it refers to can be freed when the handle is destroyed.

The second version of Op_1 can be implemented as shown in the specification,
but it may be more efficient to have it call a protected entry whose
barrier condition specifies that the semaphore is unlocked.
				Kenneth Almquist

Re: Ada Protected Object Tutorial #1

[Robert Dewar]

In article
<Pine.A41.3.96-heb-2.07.991226141254.25330A-100000@pluto.mscc.hu
ji.ac.il>,
> This very interesting article tries to explain why it
> is almost always better to use protected types, and create
> less tasks. It gives detailed examples of many tasking idiom,
> so it is also helpful as a guide to Ada tasking.


I disagree with this conclusion. Indeed my view is that it is
almost always better to use an intermediate task than a
protected object unless you specifically need the low level
efficiency that protected objects can provide in some
implementations.

Why? Because protected objects in Ada have relatively nasty low
level semantics that do not compose properly, because of the
restrictions on potentially blocking operations (these
restrictions are totally unnecessary from a semantic point
of view, they are there just to allow a more efficient
implementation on certain limited kinds of architectures).

This means that if you use protected objects you have to operate
at a lower level of abstraction.

Yes, it is always reasonable to lower the level of abstraction
in the interests of gaining efficiency, but you only do this if
you need to. The fact that when you write a protected body, you
have to be aware of the *implementation* of any subprogram that
you call, to be sure that it has no blocking operations, is
a serious disadvantage of using PT's.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ada Protected Object Tutorial #1

[Kaz Kylheku]

On Sun, 26 Dec 1999 19:20:04 GMT, Robert Dewar <robert_dewar@my-deja.com> wrote:
>In article
><Pine.A41.3.96-heb-2.07.991226141254.25330A-100000@pluto.mscc.hu
>ji.ac.il>,
>> This very interesting article tries to explain why it
>> is almost always better to use protected types, and create
>> less tasks. It gives detailed examples of many tasking idiom,
>> so it is also helpful as a guide to Ada tasking.
>
>
>I disagree with this conclusion. Indeed my view is that it is
>almost always better to use an intermediate task than a
>protected object unless you specifically need the low level
>efficiency that protected objects can provide in some
>implementations.
>
>Why? Because protected objects in Ada have relatively nasty low
>level semantics that do not compose properly, because of the

That's the sense that I get. For example, earlier in the debate I was told that
when the requirements change in certain ways, you have to abandon protected
objects. E.g. if you need an object's operation to call into another subsystem
which may call back.

I buy the argument that it's often better to do with fewer threads.  When
software has to synchronize with itself internally via a rendezvous mechanism,
that is a waste of time. It's more efficient to just let threads go loose into
foreign objects and do as much work as possible in a non-blocking manner.
Using send/receive/reply discipline for synchronization is a waste of cycles.
Though it can lead to software that is easier to debug, no contest there.

Re: Ada Protected Object Tutorial #1

[Ehud Lamm]

|Kaz Kylheku wrote in message ...
|>On Fri, 17 Dec 1999 23:28:22 GMT, Tucker Taft <stt@averstar.com> wrote:
|>>As one data point, a classic producer/consumer example with a
|>>bounded buffer, when coded using a protected type versus
|>>usingmutex/condition variables, results in typically half as many
|>>locks and unlocks, and one third as many context switches
|>>between the producer and the consumer.  The mutex/condition
|>>variable approach involves so much more work because each
|>>thread ends up doing all the work "itself," rather than allowing the
|>>other threadto do a little bit of work on its behalf while it already
|>> holds the lock.
|>
|>Is there a paper about this which argues the case in more detail?

For my suggested reading page:
The Rendezvous is Dead -- Long Live the Protected Object
       This very interesting article tries to explain why it is almost
       always better to use protected types, and create less tasks. It
       gives detailed examples of many tasking idiom, so it is also
       helpful as a guide to Ada tasking.
http://www.cs.fsu.edu/~mueller/ftp/pub/mueller/papers/sigada98.ps.gz 

Ehud Lamm mslamm@mscc.huji.ac.il
http://purl.oclc.org/NET/ehudlamm <== My home on the web 
Check it out and subscribe to the E-List- for interesting essays and more!

Re: Ada Protected Object Tutorial #1

[Robert Dewar]

In article <slrn86d0ao.fbn.kaz@ashi.FootPrints.net>,
  kaz@ashi.footprints.net wrote:
> That's the sense that I get. For example, earlier in the
debate I was told that
> when the requirements change in certain ways, you have to
abandon protected
> objects. E.g. if you need an object's operation to call into
another subsystem
> which may call back.

Really the point is that protected objects are best thought of
as a framework for constructing very simple synchronization
primitives with a minimum of active code. As soon as a protected
object acquires complex internal logic, it is better represented
by a separate Ada task.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ada Protected Object Tutorial #1

[Robert Dewar]

In article <slrn86d0ao.fbn.kaz@ashi.FootPrints.net>,
  kaz@ashi.footprints.net wrote:
> That's the sense that I get. For example, earlier in the
debate I was told that
> when the requirements change in certain ways, you have to
abandon protected
> objects. E.g. if you need an object's operation to call into
another subsystem
> which may call back.

Really the point is that protected objects are best thought of
as a framework for constructing very simple synchronization
primitives with a minimum of active code. As soon as a protected
object acquires complex internal logic, it is better represented
by a separate Ada task.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ada Protected Object Tutorial #1

[Robert Dewar]

In article <848ajb$o39$1@nntp2.atl.mindspring.net>,
  Richard D Riehle <laoXhai@ix.netcom.com> wrote:
>  Protected objects represent a significant
> improvement over semaphores for mutual exclusion but need to
> be used sparingly in a multi-tasking design.  As your note
> implies, a protected object is not a substitute for a task.

I find this a type error :-)

Protected objects and semaphores are not the same kind of thing.

A semaphore is a particular synchronization mechanism with
advantages and disadvantages.

A protected object is a language mechanism for CREATING
synchrnonization mechanisms.

Indeed a very standard example of the use of protected types
is to implement a standard semaphore.


Sent via Deja.com http://www.deja.com/
Before you buy.

Re: Ada Protected Object Tutorial #1

[Jean-Pierre Rosen]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 1431 bytes --]


Robert Dewar <robert_dewar@my-deja.com> a �crit dans le message :
846rk7$gba$1@nnrp1.deja.com...
> In article <slrn86d0ao.fbn.kaz@ashi.FootPrints.net>,
>   kaz@ashi.footprints.net wrote:
> > That's the sense that I get. For example, earlier in the
> debate I was told that
> > when the requirements change in certain ways, you have to
> abandon protected
> > objects. E.g. if you need an object's operation to call into
> another subsystem
> > which may call back.
>
> Really the point is that protected objects are best thought of
> as a framework for constructing very simple synchronization
> primitives with a minimum of active code. As soon as a protected
> object acquires complex internal logic, it is better represented
> by a separate Ada task.
>
I fully agree here, but there is another issue that is worth mentionning:
If you use protected objects, all tasks are in the position of a *client*,
which makes termination much more tricky.
You must deal with termination by having explicit "termination" messages
between tasks, and you must make sure that these messages are sent in all
cases, including tasks terminating because of abort or unhandled exceptions.
This can be made often automatic if you use rendezvous and an a terminate
alternative.
--
---------------------------------------------------------
           J-P. Rosen (Rosen.Adalog@wanadoo.fr)
Visit Adalog's web site at http://pro.wanadoo.fr/adalog

Re: Ada Protected Object Tutorial #1

[Richard D Riehle]

In article <846rk7$gba$1@nnrp1.deja.com>,
	Robert Dewar <robert_dewar@my-deja.com> wrote:

>Really the point is that protected objects are best thought of
>as a framework for constructing very simple synchronization
>primitives with a minimum of active code. As soon as a protected
>object acquires complex internal logic, it is better represented
>by a separate Ada task.

Thanks for this clarification of your view.  The originaly phrasing
was something of a shock.  The real issue is that, when designing
for concurrency, one must select the mechanism best suited to the
problem to be solved.  Protected objects represent a significant
improvement over semaphores for mutual exclusion but need to be
used sparingly in a multi-tasking design.  As your note implies,
a protected object is not a substitute for a task.  Then again,
a task is not a substitute for a subprogram.  The difficulty of
designing with tasks is non-trivial, even when a rich set of
mechanisms is available, as in Ada.   

Richard Riehle
 

Re: Ada Protected Object Tutorial #1

[Richard D Riehle]

In article <848rus$s6v$1@nnrp1.deja.com>,
	Robert Dewar <robert_dewar@my-deja.com> wrote:

>A semaphore is a particular synchronization mechanism with
>advantages and disadvantages.

Lots of disadvantages.  More than commonly noted.  This is 
especially true when using languages other than Ada or when
using certain embedded R/T OS.   I ran across a very nice
exposition of this issue last week while browsing through
a new book, "An Embedded Systems Primer," my David Simon. 
This, by the way, is a good book for an introductory course
on embedded systems programming, although there is no mention
of Ada.  

>A protected object is a language mechanism for CREATING
>synchrnonization mechanisms.

Agreed.  Is it always the best choice?  Not sure.  When should
one use the semaphores provided by an embedded O/S, or the hardware
semaphores available in some environments?   

>Indeed a very standard example of the use of protected types
>is to implement a standard semaphore.

Yes, this is a common example and it sometimes leads the designer
away from the more robust option of a fully encapsulated set of
values.  

If one is determined to implement a semaphore, a protected object is a
better choice than a task.   However, Burns and Wellings in "Concurrency 
in Ada" note that  full encapsulation is the real value of a protected
resource, and express caution about low-level mechanisms such as
semaphores versus the reliability of a "monitor" mechanism a la the
protected object.   

Richard Riehle

Re: Ada Protected Object Tutorial #1

[Tucker Taft]

Robert Dewar wrote:
> 
> In article
> <Pine.A41.3.96-heb-2.07.991226141254.25330A-100000@pluto.mscc.hu
> ji.ac.il>,
> > This very interesting article tries to explain why it
> > is almost always better to use protected types, and create
> > less tasks. It gives detailed examples of many tasking idiom,
> > so it is also helpful as a guide to Ada tasking.
> 
> I disagree with this conclusion. Indeed my view is that it is
> almost always better to use an intermediate task than a
> protected object unless you specifically need the low level
> efficiency that protected objects can provide in some
> implementations...

One of the critical features of protected objects is the
guarantee of bounded priority inversion.  In non-real-time
systems, this is generally irrelevant.  In real-time systems,
it can be essential to achieving schedulability.  So
it is not so much "low level efficiency" as "bounded
priority inversion" that protected objects provide,
which is a somewhat higher level concern
in real-time systems.

Perhaps there should be two separate variants of protected types,
one that bounds priority inversion, and imposes other restrictions,
and one that has no particular restrictions, but makes no
guarantees.  This would clearly need to be a "spec" property of the
protected type, so which variant is wanted would need to be
identified somehow in the protected type specification.

Historically, we were trying to create a feature to address
real-time concerns with rendezvous.  The fact that the protected
type construct has since been recognized as a potentially useful
paradigm for non-real-time synchronization is nice, but may
require some liberalization of the language rules
to ensure this kind of use is portable across implementations.

-Tucker Taft  stt@averstar.com
AverStar, Inc.   Burlington, MA  01803