Re: Ada Protected Object Tutorial #1

["Vladimir Olensky" <vladimir_olensky@yahoo.com>]

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.