Synchronizing on multiple distinict resources

Synchronizing on multiple distinict resources

[Chad R. Meiners]

Task and protected objects are great for synchronizing on resources that are
always grouped together.  However, resources that must be grouped together
before they can be used, such as the chopsticks in the dining philosophers
problem, seem to require the developer to write their own resource
synchronization algorithm.  Is there any standard method for synchronizing
on multiple resources in Ada 95?  If so, are there any links or articles on
this topic?

-CRM

Re: Synchronizing on multiple distinict resources

[Jim Rogers]

crmeiners@yahoo.com (Chad R. Meiners) wrote in
news:7ebaa24d.0408021054.4abc6e73@posting.google.com: 

> Task and protected objects are great for synchronizing on resources
> that are always grouped together.  However, resources that must be
> grouped together before they can be used, such as the chopsticks in
> the dining philosophers problem, seem to require the developer to
> write their own resource synchronization algorithm.  Is there any
> standard method for synchronizing on multiple resources in Ada 95?  If
> so, are there any links or articles on this topic?

There are many cases where the best answer is to group resources together.
Other possibilities are to use a set of requeue calls, possibly from an
entry in one protected object to another entry in a different protected
object.

Jim Rogers

Re: Synchronizing on multiple distinict resources

[Dmitry A. Kazakov]

On 2 Aug 2004 11:54:30 -0700, Chad R. Meiners wrote:

> Task and protected objects are great for synchronizing on resources that are
> always grouped together.  However, resources that must be grouped together
> before they can be used, such as the chopsticks in the dining philosophers
> problem, seem to require the developer to write their own resource
> synchronization algorithm.  Is there any standard method for synchronizing
> on multiple resources in Ada 95?

Standard pattern is to prioritize resources and to seize them in that
order.

One could also speculate about further Ada extensions towards:

1. multiple protected actions / rendezvous (to queue to two chopsticks)
2. extensible protected objects / tasks with multiple inheritance (to
inherit a pair of chopsticks twice from a chopstick)

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Synchronizing on multiple distinict resources

[Chad R. Meiners]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message news:<v7v0o7xngp1y.15u6pnygwg6id$.dlg@40tude.net>...
> Standard pattern is to prioritize resources and to seize them in that
> order.

*nod*  This is what I have had to do in the past.  Fortunately it
seems that I can often design away many cases that at first glance
seem to need to use multiple resources.

> One could also speculate about further Ada extensions towards:

Such speculation would be welcome ;)  For instance I became more
interested in the problem with sychronizing upon multiple resources
after reading a colleague's paper.

http://www.cse.msu.edu/~behrends/universe/fse00.pdf

Which handles multiple synchronizations with synchronization
contracts.

> 1. multiple protected actions / rendezvous (to queue to two chopsticks)

Perhaps something like 

procedure Eat(Left, Right : in out Chop_Stick) is
  Synchronize Left and Right;  -- Exclusive access until end of
procedure
begin
  ...
end Eat;

> 2. extensible protected objects / tasks with multiple inheritance (to
> inherit a pair of chopsticks twice from a chopstick)

Not sure how this would work.

-CRM

Re: Synchronizing on multiple distinict resources

[Dmitry A. Kazakov]

On 10 Aug 2004 11:51:11 -0700, Chad R. Meiners wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message news:<v7v0o7xngp1y.15u6pnygwg6id$.dlg@40tude.net>...

>> One could also speculate about further Ada extensions towards:
> 
> Such speculation would be welcome ;)  For instance I became more
> interested in the problem with sychronizing upon multiple resources
> after reading a colleague's paper.
> 
> http://www.cse.msu.edu/~behrends/universe/fse00.pdf
> 
> Which handles multiple synchronizations with synchronization
> contracts.

It is much desirable to have contracts. Especially is they would be
provable.

However, from the paper it is not clear to me how composability is
achieved. (Ada's protected objects and tasks are practically not
composable.) Well, what happens with the "concurrency" clause upon
inheritance? How to hide/expose/override such clauses? What about generic
and class-wide concurrency? Will separate compilation and linkage be
possible? How to deal with actions split across processes? I mean things
represented by the requeue statement in Ada. It seems that in the universe
model such things will be impossible. I cannot say whether this constraint
is important or not, but quite often I found requeueing the only way to do
some things. Further I'd like to preserve both views on concurrency, i.e.
tasks and protected objects. I am not convinced that protected/active
objects alone are enough flexible.

>> 1. multiple protected actions / rendezvous (to queue to two chopsticks)
> 
> Perhaps something like 
> 
> procedure Eat(Left, Right : in out Chop_Stick) is
>   Synchronize Left and Right;  -- Exclusive access until end of
> procedure
> begin
>   ...
> end Eat;

One could allow "free" entry points with normal syntax:

protected type Chop_Stick is
   procedure Release; -- A "member" procedure
private
   Free : Boolean;
end Chop_Stick;
   -- This is not Ada
entry Seize (Left, Right : in out Chop_Stick);
   -- Not a "member", but still a primitive operation

entry Seize (Left, Right : in out Chop_Stick)
   when Left.Free and Right.Free is
      -- Dispatching parameters are allowed to appear in barriers
begin
   Left.Free  := False;
   Right.Free := False;
end Seize;

>> 2. extensible protected objects / tasks with multiple inheritance (to
>> inherit a pair of chopsticks twice from a chopstick)
> 
> Not sure how this would work.

In the case of philosophers it will not, because chopsticks pairs overlap.
But the rationale is same: let I want to combine two protected objects in
one:

   -- This is not Ada
   protected type Pair_Of_Sticks is private
      entry Seize;
      procedure Release;
   end Pair_Of_Sticks;
   ...
private
   protected type Pair_Of_Sticks is
      new Left : Chop_Stick; Right : Chop_Stick;

-- Implementation:
entry Seize when Left.Free and Right.Free is
   -- Can use inherited members in barriers
begin
   Left.Free  := False;
   Right.Free := False;   
end Seize;

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Synchronizing on multiple distinict resources

[Chad R. Meiners]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message news:<1f4ugyz3ig9rc$.785e2wqt1qyg$.dlg@40tude.net>...
> >> 1. multiple protected actions / rendezvous (to queue to two chopsticks)
> > 
> > Perhaps something like 
> > 
> > procedure Eat(Left, Right : in out Chop_Stick) is
> >   Synchronize Left and Right;  -- Exclusive access until end of
> > procedure
> > begin
> >   ...
> > end Eat;
> 
> One could allow "free" entry points with normal syntax:
> 
> protected type Chop_Stick is
>    procedure Release; -- A "member" procedure
> private
>    Free : Boolean;
> end Chop_Stick;
>    -- This is not Ada
> entry Seize (Left, Right : in out Chop_Stick);
>    -- Not a "member", but still a primitive operation
> 
> entry Seize (Left, Right : in out Chop_Stick)
>    when Left.Free and Right.Free is
>       -- Dispatching parameters are allowed to appear in barriers
> begin
>    Left.Free  := False;
>    Right.Free := False;
> end Seize;


I think that the when clause isn't even needed since it would need
exclusive access to both left and right.   The question becomes
whether this syntax breaks the encapsulation of the protected types.

For example:

protected type Signal is
  entry Wait;
  procedure Signal;
private
  entry Release;
  On : boolean := false;
end

entry Wait(One, Two : Signal);

protected body Signal is
  entry Wait when not On is
  begin
    requeue Release;
  end Wait;
  procedure Signal is
  begin
    On := true;
  end Signal;
  entry Release when On is
  begin
    On := Release'Count > 0;
  end Release;
end Signal;

entry Wait(One, Two : Signal) when One.On and Two.On is
begin
  null;
end Wait;

Re: Synchronizing on multiple distinict resources

[Dmitry A. Kazakov]

On 19 Aug 2004 15:18:44 -0700, Chad R. Meiners wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> wrote in message news:<1f4ugyz3ig9rc$.785e2wqt1qyg$.dlg@40tude.net>...
>>>> 1. multiple protected actions / rendezvous (to queue to two chopsticks)
>>> 
>>> Perhaps something like 
>>> 
>>> procedure Eat(Left, Right : in out Chop_Stick) is
>>>   Synchronize Left and Right;  -- Exclusive access until end of
>>> procedure
>>> begin
>>>   ...
>>> end Eat;
>> 
>> One could allow "free" entry points with normal syntax:
>> 
>> protected type Chop_Stick is
>>    procedure Release; -- A "member" procedure
>> private
>>    Free : Boolean;
>> end Chop_Stick;
>>    -- This is not Ada
>> entry Seize (Left, Right : in out Chop_Stick);
>>    -- Not a "member", but still a primitive operation
>> 
>> entry Seize (Left, Right : in out Chop_Stick)
>>    when Left.Free and Right.Free is
>>       -- Dispatching parameters are allowed to appear in barriers
>> begin
>>    Left.Free  := False;
>>    Right.Free := False;
>> end Seize;

> I think that the when clause isn't even needed since it would need
> exclusive access to both left and right.   The question becomes
> whether this syntax breaks the encapsulation of the protected types.

Yes it does. The syntax I used was of course imaginary. The problem you
mentioned arise because protected types fall out of standard Ada visibility
rules based on packages. With packages one has an advantage to see private
parts of many things simultaneously. Protected objects rather mimic C++,
which approaches the problem by its nasty "friend"s. I hate to see
something like that in Ada. I would rather allow primitive operations to
look into the private parts of dispatching parameters.

BTW the solution (2) based on multiple inheritance will have no such
problem. But it has another. One could access private parts of
non-dispatching (alien) parameters:

type protected Pair is new Left, Right : Chop_Stick with null record;

procedure Criminal (Baz : Pair; Victim : Chop_Stick'Class) is
begin
   Victim.Free := True;
end Criminal;

This should be made illegal.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de