Re: Q: Protected types and entries (long)

Re: Q: Protected types and entries (long)

[Wilhelm Spickermann]

Erik Margraf wrote:
> 
> Recently I started to learn about protected types. I tried to do
> something like the following:
> 
> (Not 100% Ada :-)
> 
> ...
>    type buffer is array (...) of character;
>    protected type Object is
>      entry put (data : in buffer);
>    private
>      internal_buffer : array (BIG_Enough) of character;
>      items_in_buffer : integer := 0;
>    end;
> ...
>    protected Object body
> 
>    entry put (data : in buffer)
>         when data'size + items_in_buffer <= internal_buffer�size is
>    begin
>     ...
>    end;
>    end Object;
> 
> Since the reference to a formal parameter of an entry is not allowed,
> gnat
> refused to compile this ;-). I changed the code to
> 
>    type buffer is array (...) of character;
>    protected type Object is
>      entry put (data : in buffer);
>    private
>      entry p_put (data : in buffer);
>      internal_buffer : array (BIG_Enough) of character;
>      data_size : integer;
>      items_in_buffer : integer := 0;
>    end;
> ...
>    protected Object body
>    entry put (data : in buffer)
>         when true is
>    begin
>       data_size := data�size;
>       if data_size + items_in_buffer > internal_buffer�size then
>         requeue p_put;
>       end if;
>    end;
> 
>    entry p_put (data : in buffer)
>         when data_size + items_in_buffer <= internal_buffer�size is
>    begin
>     ...
>    end;
>    end Object;
> 
> This compiles.
> Now my questions:
> 
>         - Can someone tell me WHY this limitation in the barrier exists?
>         - Is my "solution" really a solution to this problem?
>         - (What) Should I do something different?
> Thanks
> 
> Erik Margraf
> 
> --
> --------------------------------------------------------------------
> -- Erik Margraf
> -- Siemens Austria PSE KB2
> -- erik.margraf@siemens.at
> -- +43 1 1707 45887
> --------------------------------------------------------------------
I think the second solution will not work. Think of several tasks
waiting
for the barrier of p_put to become open. Then one task with a small
data'size enters put: It will change data_size and open the barrier for
all of them...
(The barrier does not belong to a call -- it belongs to the entry!)

The solution to your problem is decribed in Burns, Wellings: Concurrency 
in Ada (8.1.2).

The reason for the limitations on barriers is the high efficiency of 
implementation which was achieved by it. Protected objects are even more
efficient than semaphores, because one thread of control can execute the
protected operation of another and continue to work without any context
switch. 

Example: We have a one element buffer which is initially empty, a task R
         which is reading elements all day long and task W which is
writing
         all day:
 - task R tries to read and gets blocked
 - task W writes
 - task W executes the protected read of R and makes R executable
 - task W writes
 - task W tries to write the third element and gets blocked
 (cf. Ada 95 Rationale: 9.1.3)

Wilhelm Spickermann

Q: Protected types and entries (long)

[Erik Margraf]

Recently I started to learn about protected types. I tried to do 
something like the following:

(Not 100% Ada :-)

...
   type buffer is array (...) of character;
   protected type Object is
     entry put (data : in buffer);
   private
     internal_buffer : array (BIG_Enough) of character;
     items_in_buffer : integer := 0;
   end; 
...
   protected Object body

   entry put (data : in buffer) 
	when data'size + items_in_buffer <= internal_buffer´size is
   begin
    ...
   end;
   end Object;

Since the reference to a formal parameter of an entry is not allowed,
gnat
refused to compile this ;-). I changed the code to

   type buffer is array (...) of character;
   protected type Object is
     entry put (data : in buffer);
   private
     entry p_put (data : in buffer);
     internal_buffer : array (BIG_Enough) of character;
     data_size : integer;
     items_in_buffer : integer := 0;
   end; 
...
   protected Object body
   entry put (data : in buffer) 
	when true is
   begin
      data_size := data´size;
      if data_size + items_in_buffer > internal_buffer´size then 
        requeue p_put;
      end if;
   end;

   entry p_put (data : in buffer) 
	when data_size + items_in_buffer <= internal_buffer´size is
   begin
    ...
   end;
   end Object;

This compiles. 
Now my questions:

	- Can someone tell me WHY this limitation in the barrier exists?
	- Is my "solution" really a solution to this problem?
	- (What) Should I do something different?
Thanks

Erik Margraf

-- 
--------------------------------------------------------------------
-- Erik Margraf
-- Siemens Austria PSE KB2
-- erik.margraf@siemens.at
-- +43 1 1707 45887
--------------------------------------------------------------------

Re: Q: Protected types and entries (long)

[Samuel Mize]

Erik Margraf <erik.margraf@siemens.at> wrote:
>    entry put (data : in buffer) 
>    when data'size + items_in_buffer <= internal_buffer'size is
>    begin
...
>    - Can someone tell me WHY this limitation in the barrier exists?

Because the barrier expression applies to the whole entry queue, not
to each call in the queue individually.

Why?

Remember that "a protected object is designed to be a very efficient
conditional critical region[1]."

Now, there are two ways that the reference to "data" could be
interpreted.  It could mean to look at the call at the head of the
queue, or it it could mean to review each call individually and
see if it can execute.

If it looks only at the call at the head of the queue, one task trying
to add a large item might block any number of tasks trying to add
items that would fit, depending on whether or not it got there first.
This kind of race condition makes the system's behavior much less
predictable, which is a bad thing in hard-deadline real-time systems.

If it looks at all entries in the queue, then the amount of time that
it takes to evaluate the barriers can grow without limit, also a bad
thing in a hard real-time environment.

So the most efficient construct is the one chosen for Ada.  However,
sometimes one does need to have each queue element examined in turn,
and that's where Ada's "requeue" come into play, as you thought.

However, your solution has two flaws.  First, if the object fits
into the buffer, it won't be added -- you don't do anything in the
body of "put".  That's a nit, and you can fix it by always requeueing
in put.[2]

Second, and much more important, consider the case where you have
two entries queued up on "put", the first with a larger "data" than
the second has, and both larger than your current free space.  The
first will queue up on "p_put", then the second will queue up on
"p_put", and data_size will show the second (smaller) size request.
Then a consumer task frees up just that much space, and the first
call is free to execute without enough space in the internal buffer.

So, how do you solve your problem?

1. If you want the entries to be processed in order of arrival, you
   can prevent a second "put" call from resetting "data_size" by
   guarding "put" with an initially-true boolean -- call it
   "data_size_unset".  Then, in the body of "put", you set data_size
   and set "data_size_unset" to false, and requeue on "p_put".
   "p_put" would set "data_size_unset" back to true.

2. If you want the entries to be scanned, and any that are small
   enough processed, do this.

   Have "put" add the item to the internal buffer if there is room.
   Otherwise it sets a boolean to false, and requeues the call on an
   internal entry, whose barrier is that boolean.

   When your consumer task frees up some space, it sets that boolean
   to be true.  The internal entry just requeues on "put".  Thus,
   each time some space is freed up, everybody tries "put" again and
   either succeeds or get requeued once more.

You can fancy up that second approach.  For instance, "p_put" might save
the largest data size that would fit, and then requeue everybody on
"p_p_put", which would requeue one request of that size to "put" and
everybody else back to "p_put" (or something like that, you need to
carefully think through the queue behavior in a design like this, and
I haven't done so for this example.)

The point is, you can create arbitrarily complex scanning behavior with
inter-acting queues.  And you aren't paying task switching overhead to
do it, because of the way that protected objects operate.  But you *are*
creating a lot more overhead than they wanted to put into the base
design of Ada, so you have to code it manually.

Best,
Sam Mize

[1] Ada 95 Rationale, 9.1

[2] Or, you can duplicate the code from "p_put" in the body of "put",
which would give precedence to callers with smaller "data" buffers.
If you do this, you should encapsulate the shared code in a procedure,
and call that procedure in both entries.


-- 
Samuel Mize -- smize@imagin.net (home email) -- Team Ada
Fight Spam: see http://www.cauce.org/ \\\ Smert Spamonam

Re: Q: Protected types and entries (long)

[Robert A Duff]

Erik Margraf <erik.margraf@siemens.at> writes:

> ...Since the reference to a formal parameter of an entry is not
> allowed [in a barrier],...

When you wish you could do that, it often makes sense to use an entry
family.  The family index behaves somewhat like a parameter, but you
*can* use it in the barrier.  Another alternative is requeue, which you
already knew.

- Bob
-- 
Change robert to bob to get my real email address.  Sorry.