Multitasking and containers

Multitasking and containers

[Maciej Sobczak]

Hi,

Paragraph 3 in Annex A says that it's OK to call any standard subprogram 
from concurrent tasks as long as the parameters do not overlap. John 
Barnes ("Progamming in Ada 2005") suggests that in order to (for 
example) read from the same container, the operations need to be 
protected "by using the normal techniques such as protected objects".

But reading from the protected object is not mutually exclusive (many 
readers are allowed) - so where's the gain? What's the difference 
between concurrent reads of, say, a Vector via protected object vs. 
direct access?

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: Multitasking and containers

[Georg Bauhaus]

Maciej Sobczak wrote:

> But reading from the protected object is not mutually exclusive (many 
> readers are allowed) - so where's the gain? What's the difference 
> between concurrent reads of, say, a Vector via protected object vs. 
> direct access?

Supposing that some operations perform a write on the container,
for example while filling or updating,
then if there is any potential overlap of a read and a write,
the gain of protection is that none of the writes can ever interfere
with one of the read operations.

If there is no write after some point, I would say that "normal means
of protection" includes "no protection is necessary after this point".



-- Georg 

Re: Multitasking and containers

[Dmitry A. Kazakov]

On Fri, 24 Nov 2006 09:51:24 +0100, Maciej Sobczak wrote:

> Paragraph 3 in Annex A says that it's OK to call any standard subprogram 
> from concurrent tasks as long as the parameters do not overlap. John 
> Barnes ("Progamming in Ada 2005") suggests that in order to (for 
> example) read from the same container, the operations need to be 
> protected "by using the normal techniques such as protected objects".
> 
> But reading from the protected object is not mutually exclusive (many 
> readers are allowed) - so where's the gain? What's the difference 
> between concurrent reads of, say, a Vector via protected object vs. 
> direct access?

I think he didn't mean container being a protected object. It would be
difficult to do, because protected types alas aren't tagged. So I read it
as "by using a locking/serialization technique, such as mutex, which can be
implemented as a protected object."

[ I don't know if ARM 2005 permits mutable implementations of read
operations on the containers. I suppose it does, so the need to lock upon
read. ]

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

Re: Multitasking and containers

[Maciej Sobczak]

Dmitry A. Kazakov wrote:

>> Paragraph 3 in Annex A says that it's OK to call any standard subprogram 
>> from concurrent tasks as long as the parameters do not overlap. John 
>> Barnes ("Progamming in Ada 2005") suggests that in order to (for 
>> example) read from the same container, the operations need to be 
>> protected "by using the normal techniques such as protected objects".
>>
>> But reading from the protected object is not mutually exclusive (many 
>> readers are allowed) - so where's the gain? What's the difference 
>> between concurrent reads of, say, a Vector via protected object vs. 
>> direct access?
> 
> I think he didn't mean container being a protected object.

No, but you might want to encapsulate a container within a protected 
object and have some protected procedures and functions forwarding to 
relevant ones in the container.

> [ I don't know if ARM 2005 permits mutable implementations of read
> operations on the containers. I suppose it does, so the need to lock upon
> read. ]

That would be interesting, but would break apart when encapsulated 
within a protected object, because there multiple readers would be allowed.

Having a mutex for readers sounds like a concurrency killer and relying 
on protected wrappers seems to be fragile because of this possible 
mutability. So - what is The Solution (tm) for multiple tasks reading 
from the same container?

Let's say you want to have N worker tasks consulting a shared dictionary 
(map) that was initialized before the tasks started their work. How 
would you solve this?

-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: Multitasking and containers

[Dmitry A. Kazakov]

On Fri, 24 Nov 2006 11:35:11 +0100, Maciej Sobczak wrote:

> Dmitry A. Kazakov wrote:
> 
>>> Paragraph 3 in Annex A says that it's OK to call any standard subprogram 
>>> from concurrent tasks as long as the parameters do not overlap. John 
>>> Barnes ("Progamming in Ada 2005") suggests that in order to (for 
>>> example) read from the same container, the operations need to be 
>>> protected "by using the normal techniques such as protected objects".
>>>
>>> But reading from the protected object is not mutually exclusive (many 
>>> readers are allowed) - so where's the gain? What's the difference 
>>> between concurrent reads of, say, a Vector via protected object vs. 
>>> direct access?
>> 
>> I think he didn't mean container being a protected object.
> 
> No, but you might want to encapsulate a container within a protected 
> object and have some protected procedures and functions forwarding to 
> relevant ones in the container.

OK, but that's same to me. Aggregation + delegation = inheritance for
poor...

>> [ I don't know if ARM 2005 permits mutable implementations of read
>> operations on the containers. I suppose it does, so the need to lock upon
>> read. ]
> 
> That would be interesting, but would break apart when encapsulated 
> within a protected object, because there multiple readers would be allowed.
> 
> Having a mutex for readers sounds like a concurrency killer and relying 
> on protected wrappers seems to be fragile because of this possible 
> mutability. So - what is The Solution (tm) for multiple tasks reading 
> from the same container?
> 
> Let's say you want to have N worker tasks consulting a shared dictionary 
> (map) that was initialized before the tasks started their work. How 
> would you solve this?

I would try to decouple the mutable part. [ It is a quite common problem,
not necessarily in the context of concurrent programming. ] The cache that
does not belong to the container should be associated with the caller's
task. That would eliminate any need of locking. The cache shared between
the callers should be locked when changed. So a protected object should be
associated with that cache, not with the container as a whole.

Write your own container. Parallel systems require delicate handmade work.

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

Re: Multitasking and containers

[Matthew Heaney]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> Write your own container. Parallel systems require delicate handmade work.

Horrible advice.  Just declare the container inside a protect object, and
manipulate the container by calling protected procedures.  Works great...

Re: Multitasking and containers

[Jeffrey R. Carter]

Matthew Heaney wrote:
> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> Write your own container. Parallel systems require delicate handmade work.
> 
> Horrible advice.  Just declare the container inside a protect object, and
> manipulate the container by calling protected procedures.  Works great...

Not at all, even for sequential systems. Standard libraries are 
necessarily compromises among various concerns such as safety, 
performance, ease of use, and so on. Specific projects may, and 
sometimes will, have requirements that are not met by such libraries. In 
such cases, custom versions are needed.

In this case, we may have an instance of premature optimization; the OP 
seems to be worrying about the overhead of wrapping a container in a 
protected object without any evidence that this approach won't meet the 
project's requirements (indeed, it seems there is no project and no 
specific requirements are involved). In that case, it probably will 
"work great". But in specific cases a custom version that does allow 
unprotected multiple readers may be required.

-- 
Jeff Carter
"There's no messiah here. There's a mess all right, but no messiah."
Monty Python's Life of Brian
84

Re: Multitasking and containers

[Georg Bauhaus]

On Mon, 2006-11-27 at 04:17 +0000, Jeffrey R. Carter wrote:
> Matthew Heaney wrote:
> > "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> > 
> >> Write your own container. Parallel systems require delicate handmade work.
> > 
> > Horrible advice.  Just declare the container inside a protect object, and
> > manipulate the container by calling protected procedures.  Works great...
> 
> Not at all, [...]. Specific projects may, and 
> sometimes will, have requirements that are not met by such libraries.

But "parallel systems require delicate handmade work" is probably
not good advice at all, because (a) parallel systems operate in parallel
and there isn't a sharing issue in the first place, no protection is
needed. (b) When systems start communicating, and if it were true
that concurrency requires delicate handmade work, why then use a
language like Ada? The delicacies of the mechanisms behind tasks
and shared protected objects are hidden in Ada RTSs. Therefore, if
parallel systems do require delicate handmade work, the language
designers should abandon Ada tasks and protected objects, because
obviously they cannot meet the requirements of parallel systems.

Re: Multitasking and containers

[Jeffrey R. Carter]

Georg Bauhaus wrote:
> 
> But "parallel systems require delicate handmade work" is probably
> not good advice at all, because (a) parallel systems operate in parallel
> and there isn't a sharing issue in the first place, no protection is
> needed. (b) When systems start communicating, and if it were true
> that concurrency requires delicate handmade work, why then use a
> language like Ada? The delicacies of the mechanisms behind tasks
> and shared protected objects are hidden in Ada RTSs. Therefore, if
> parallel systems do require delicate handmade work, the language
> designers should abandon Ada tasks and protected objects, because
> obviously they cannot meet the requirements of parallel systems.

I guess we have different interpretations of "delicate handmade work". I 
took it simply to mean custom implementations tailored to the specific 
project (such as a container that does not need protection for reads). I 
guess only Kazakov can tell us for sure.

-- 
Jeff Carter
"My brain hurts!"
Monty Python's Flying Circus
21

Re: Multitasking and containers

[Dmitry A. Kazakov]

On Mon, 27 Nov 2006 18:41:00 GMT, Jeffrey R. Carter wrote:

> Georg Bauhaus wrote:
>> 
>> But "parallel systems require delicate handmade work" is probably
>> not good advice at all, because (a) parallel systems operate in parallel
>> and there isn't a sharing issue in the first place, no protection is
>> needed. (b) When systems start communicating, and if it were true
>> that concurrency requires delicate handmade work, why then use a
>> language like Ada? The delicacies of the mechanisms behind tasks
>> and shared protected objects are hidden in Ada RTSs. Therefore, if
>> parallel systems do require delicate handmade work, the language
>> designers should abandon Ada tasks and protected objects, because
>> obviously they cannot meet the requirements of parallel systems.
> 
> I guess we have different interpretations of "delicate handmade work". I 
> took it simply to mean custom implementations tailored to the specific 
> project (such as a container that does not need protection for reads). I 
> guess only Kazakov can tell us for sure.

Actually, you did it better than me. Thanks.

I also agree with your point about premature optimization. It is a common
disease, which costs much work and many bad designs, which in the end turn
neither efficient nor clean. I suffer it as well, this in a human nature of
many programmers.

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

Re: Multitasking and containers

[Matthew Heaney]

Jeffrey R. Carter wrote:
>
> I guess we have different interpretations of "delicate handmade work". I
> took it simply to mean custom implementations tailored to the specific
> project (such as a container that does not need protection for reads).

But that's the same as saying you can not use anything in the
predefined library.  If so then the container library is the least of
your problems!

Re: Multitasking and containers

[Simon Wright]

"Matthew Heaney" <mheaney@on2.com> writes:

> Jeffrey R. Carter wrote:
>>
>> I guess we have different interpretations of "delicate handmade work". I
>> took it simply to mean custom implementations tailored to the specific
>> project (such as a container that does not need protection for reads).
>
> But that's the same as saying you can not use anything in the
> predefined library.  If so then the container library is the least of
> your problems!

If the predefined library doesn't meet your needs you do indeed have a
lot of work ahead of you; often small beer in the overall scope (eg,
safety-related systems with SIL4 software => no runtime at all [GNAT
high integrity edition for example] highly desirable if not absolutely
necessary precondition for certification).

But if it does meet your needs you're crazy not to use it!

Re: Multitasking and containers

[Dr. Adrian Wrigley]

On Mon, 27 Nov 2006 11:45:08 -0800, Matthew Heaney wrote:
> Jeffrey R. Carter wrote:
>>
>> I guess we have different interpretations of "delicate handmade work". I
>> took it simply to mean custom implementations tailored to the specific
>> project (such as a container that does not need protection for reads).
> 
> But that's the same as saying you can not use anything in the
> predefined library.  If so then the container library is the least of
> your problems!

Dmitry wrote:
>> Write your own container. Parallel systems require delicate handmade work.

(noting a breakdown in logic in this argument...
Dmitry said handmade work is required.  This does not mean that
*only* handmade work is allowed, as Matthew seems to infer.)

Actually, I think Dmitry's view is largely valid in practice, if
somewhat extreme.
--
Adrian

Re: Multitasking and containers

[Matthew Heaney]

"Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> writes:

> Actually, I think Dmitry's view is largely valid in practice, if
> somewhat extreme.

But we were talking specifically about using a protected object to implement a
multiple readers schema vs. using a protected object to implement a Hoare-style
monitor.  Because reads must by synchronized, the standard container library
requires a monitor-style synchronization scheme.

The OP made the argument that this isn't very efficient, and Dmitry responded
by saying, "well of course systems require custom hand-made solutions." But the
premise is all wrong, so what Dmitry said is irrelevant.  The OP (not Dmitry)
seems to be confused (he was asking the question, after all) about the
difference between a mutex and a monitor.  He (the OP) probably doesn't
understand that monitor-type synchronization executes on the current thread, so
there's no context switch, and so there's no efficiency loss.

The only time when monitor-style synchronization would be inappropriate is if
the protected operation needed to make a "potentially-blocking call," but
that's not the case here so there's no reason (certainly there's no efficiency
reason) not to use a monitor.

Re: Multitasking and containers

[Dmitry A. Kazakov]

On Tue, 28 Nov 2006 02:19:55 GMT, Matthew Heaney wrote:

> "Dr. Adrian Wrigley" <amtw@linuxchip.demon.co.uk.uk.uk> writes:
> 
>> Actually, I think Dmitry's view is largely valid in practice, if
>> somewhat extreme.
> 
> But we were talking specifically about using a protected object to implement a
> multiple readers schema vs. using a protected object to implement a Hoare-style
> monitor.  Because reads must by synchronized, the standard container library
> requires a monitor-style synchronization scheme.
> 
> The OP made the argument that this isn't very efficient, and Dmitry responded
> by saying, "well of course systems require custom hand-made solutions." But the
> premise is all wrong, so what Dmitry said is irrelevant.  The OP (not Dmitry)
> seems to be confused (he was asking the question, after all) about the
> difference between a mutex and a monitor.  He (the OP) probably doesn't
> understand that monitor-type synchronization executes on the current thread, so
> there's no context switch, and so there's no efficiency loss.

I read OP question very differently. He said (let Maciej correct me):

1. That accessing a mutable operation disguised as a protected object's
function were wrong.

2. Using a protected object's procedure/entry would kill concurrency by
serialization of the action to undertake.

Both statements are evidently true.

My comments considered possible solutions *provided* that 2 were really a
problem, because as Jeffrey rightly pointed out, the loss of performance
could be actually minor. But that depends. It is easy to imagine a
situation (massively parallel computing with shared memory) where the loss
could be huge.

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

Re: Multitasking and containers

[Georg Bauhaus]

On Tue, 2006-11-28 at 09:50 +0100, Dmitry A. Kazakov wrote:
> On Tue, 28 Nov 2006 02:19:55 GMT, Matthew Heaney wrote:
>  It is easy to imagine a
> situation (massively parallel computing with shared memory) where the loss
> could be huge.

I have learned that Ada tasking is defined at a relatively
high level. Suppose you are writing highly specialized low
level software, such as when taking advantage of a specific
computer's architecture at the system or hardware level.
It is easy for me to imagine that you are working way below
Ada's tasking level. Are you suggesting that this is the
normal mode of using a high level programming language
that supports tasking?

Re: Multitasking and containers

[Dmitry A. Kazakov]

On Tue, 28 Nov 2006 11:31:13 +0100, Georg Bauhaus wrote:

> On Tue, 2006-11-28 at 09:50 +0100, Dmitry A. Kazakov wrote:
>> On Tue, 28 Nov 2006 02:19:55 GMT, Matthew Heaney wrote:
>>  It is easy to imagine a
>> situation (massively parallel computing with shared memory) where the loss
>> could be huge.
> 
> I have learned that Ada tasking is defined at a relatively
> high level. Suppose you are writing highly specialized low
> level software, such as when taking advantage of a specific
> computer's architecture at the system or hardware level.
> It is easy for me to imagine that you are working way below
> Ada's tasking level. Are you suggesting that this is the
> normal mode of using a high level programming language
> that supports tasking?

I didn't mean Ada tasking at all [*]. I meant explicitly one concrete
design solution: a container with mutable reads wrapped into a protected
object's procedure.

What makes you think that my proposal to decouple the mutable context from
the container data type is any lower level than fighting with side-effects
by rough locking? It is merely a design question. You replace:

   function Find
            (  Container : access Dictionary;
               Token     : Key
            )  return Topic;

with

   function Find
            (  Container : Dictionary;
               Token     : Key;
               Context   : access Environment
            )  return Topic;

where Context provides protected interface to shared mutable data, which
hopefully need not to changed upon each call.

or else you use mix-in on the container type:

   type Dictionary (Context : access Environment) is ...;

-------------------------------------------
*  If your question concerns whether Ada's tasking primitives are
composable with other language features. Then the answer is clear and
unambiguous. They are *not*.

There are many *objective* reasons for this unhappy situation. Objective in
the sense that it would be unfair and just wrong to address them to the
language design faults. If you disagree with that, then you should have
dismissed the design of Ada.Containers for being task-unsafe. Because the
following two statements are mutually incompatible:

1. Ada.Containers may be task-unsafe
2. Ada tasking primitives are composable

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

Re: Multitasking and containers

[Georg Bauhaus]

On Tue, 2006-11-28 at 12:24 +0100, Dmitry A. Kazakov wrote:
> On Tue, 28 Nov 2006 11:31:13 +0100, Georg Bauhaus wrote:
> 
> > On Tue, 2006-11-28 at 09:50 +0100, Dmitry A. Kazakov wrote:
> >> On Tue, 28 Nov 2006 02:19:55 GMT, Matthew Heaney wrote:
> >>  It is easy to imagine a
> >> situation (massively parallel computing with shared memory) where the loss
> >> could be huge.
> > 
> > I have learned that Ada tasking is defined at a relatively
> > high level. Suppose you are writing highly specialized low
> > level software, such as when taking advantage of a specific
> > computer's architecture at the system or hardware level.
> > It is easy for me to imagine that you are working way below
> > Ada's tasking level. Are you suggesting that this is the
> > normal mode of using a high level programming language
> > that supports tasking?
> 
> I didn't mean Ada tasking at all [*]. I meant explicitly one concrete
> design solution: a container with mutable reads wrapped into a protected
> object's procedure.

Well, your design solution ("have the user take care of any concurrency
issues by providing access to some Environment context" IIUC) seemed to
me to refer to a multi-CPU system with shared memory. Then there was
massively parallel computing. To me, this sounds like it  could be
image/video processing, sound production, pattern recognition and the
like. Smells like matrices and specially designed algorithms, not like
standard containers and Maps of Maps.

If your algorithm can guarantee that no read operation tampers with
anything in your shared data, fine. If some out of the box algorithms
and standard containers are to be used in a less specialized concurrent
program, imagining off the street programmers, will you profit from
using Ada if programmers will have to trigger semaphores hoisting flags
and the like? 

This is what made me think that your proposal is low level.

Incidentally, the design solution blends well with your other design
decisions that I can remember.
E.g. have the compiler at most help the user to flesh out an
Array interface, instead of providing a stinking array construct defined
by the language. :-)

As Matt has said,
"The reason is a conflict between safety and flexibility,
a conflict that was resolved in favor of safety."

Isn't this true of Ada in general?

 -- Georg 

Re: Multitasking and containers

[Matthew Heaney]

Dmitry A. Kazakov wrote:
> 2. Using a protected object's procedure/entry would kill concurrency by
> serialization of the action to undertake.

There is a difference between "synchronizing access to a shared
resource" and "waiting for a resource to become available".

Calling a protected function or procedure is an example of the former.
Calling a protected procedure would hardly "kill concurrency".  In a
monitor there is only synchronization.  (I think it's the case that the
task stays in a running state.)

Calling a protected entry whose barrier condition is false is an
example of the latter.  If the barrier condition were false this would
mean the task waits (it transitions to a blocked state).  I would be
loathe to say that that would "kill" concurrency since in typical
designs that's exactly what the task is supposed to do.

Re: Multitasking and containers

[Dmitry A. Kazakov]

On 28 Nov 2006 09:12:27 -0800, Matthew Heaney wrote:

> Dmitry A. Kazakov wrote:
>> 2. Using a protected object's procedure/entry would kill concurrency by
>> serialization of the action to undertake.
> 
> There is a difference between "synchronizing access to a shared
> resource" and "waiting for a resource to become available".
> 
> Calling a protected function or procedure is an example of the former.
> Calling a protected procedure would hardly "kill concurrency".  In a
> monitor there is only synchronization.  (I think it's the case that the
> task stays in a running state.)

Ah, you mean: in absence of preemptive scheduling.

> Calling a protected entry whose barrier condition is false is an
> example of the latter.  If the barrier condition were false this would
> mean the task waits (it transitions to a blocked state).  I would be
> loathe to say that that would "kill" concurrency since in typical
> designs that's exactly what the task is supposed to do.

No difference if the above premise holds, i.e. no task switches as long as
the barrier is closed.

But, the above is true *only* for a single-CPU system. So for a truly
parallel system it could become a problem. Dual-cores aren't that expensive
in these days.

Further, even on a single CPU, where protected functions and procedures are
equivalent, the requirement "no task switches while lock held" might be
unacceptable if you hold it for too long. Searching a container within a
protected action ... well, one should be a quite strong believer for this.
I wouldn't dismiss it completely, but I definitely don't like it. For
hashes I would at least take one with an external hash function computed
outside the protected action.

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

Re: Multitasking and containers

[Matthew Heaney]

Dmitry A. Kazakov wrote:
>
> Further, even on a single CPU, where protected functions and procedures are
> equivalent, the requirement "no task switches while lock held" might be
> unacceptable if you hold it for too long.

But this is already a precondition for using a protected object as a
monitor.  The RM makes it clear that you shouldn't be doing anything
that takes "too long" inside a protected operation.


> Searching a container within a
> protected action ... well, one should be a quite strong believer for this.

If this is an associative container then no problem.  If this is a
sequence container with many elements, well that's another story.


> I wouldn't dismiss it completely, but I definitely don't like it. For
> hashes I would at least take one with an external hash function computed
> outside the protected action.

The issue with hash tables is not the computation of the hash value,
but rather if the hash function is poor and there are many collisions.
If that's the case then the time to compare the key to items already in
that bucket will be large compared to the cost of computing the hash
value itself.

Re: Multitasking and containers

[Dmitry A. Kazakov]

On 28 Nov 2006 11:17:33 -0800, Matthew Heaney wrote:

> The issue with hash tables is not the computation of the hash value,
> but rather if the hash function is poor and there are many collisions.
> If that's the case then the time to compare the key to items already in
> that bucket will be large compared to the cost of computing the hash
> value itself.

Yes. This is why one should look into the container, as I said before. You
lock not the container as a whole, but the bucket. The advantage is that in
this case you can lock buckets in a preemptive way, lifting the problem of
too long waits, while loosing little: doubled overhead of a protected
action. This is how our middleware works. Actually it is just a specialized
hash table of process variables. Because it were too expensive to maintain
a lock per bucket, I grouped them into a lesser number of "access
channels."

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

Re: Multitasking and containers

[Maciej Sobczak]

Dmitry A. Kazakov wrote:

>> The OP (not Dmitry)
>> seems to be confused (he was asking the question, after all) about the
>> difference between a mutex and a monitor.

I was asking a question about strategy to use a standard container in a 
multitasking environment, not what's the difference between a mutex and 
a monitor. I don't see any implication for confusion in the latter.

>> He (the OP) probably doesn't
>> understand that monitor-type synchronization executes on the current thread, so
>> there's no context switch, and so there's no efficiency loss.

The efficiency loss might be possible due to contention on the shared 
resource. It is clear that with single CPU there is nothing to fuss 
over, but the concept of "single CPU" became somewhat fuzzy nowadays.

> I read OP question very differently. He said (let Maciej correct me):
> 
> 1. That accessing a mutable operation disguised as a protected object's
> function were wrong.
> 
> 2. Using a protected object's procedure/entry would kill concurrency by
> serialization of the action to undertake.
> 
> Both statements are evidently true.

And that's exactly what I meant.

> My comments considered possible solutions *provided* that 2 were really a
> problem

And that's absolutely a non-issue. I'm interested in principles and 
rationale - a clear understanding of the tools is crucial at the very 
early stages of project development, because it's when the decisions 
have the biggest impact on later phases.

What I've learned in this thread is that:
1. Ada standard containers should be protected against concurrent 
accesses (in the general meaning of "access") and it's the obligation of 
the user to do it.
2. This serializes all users of the container with obvious consequences.

Whether any of these two is a problem in any particular project is a 
non-issue. The point is that these two facts are to be understood, so 
that they can be taken into account when there's a time to do so.


-- 
Maciej Sobczak : http://www.msobczak.com/
Programming    : http://www.msobczak.com/prog/

Re: Multitasking and containers

[Matthew Heaney]

Maciej Sobczak wrote:
> And that's absolutely a non-issue. I'm interested in principles and
> rationale - a clear understanding of the tools is crucial at the very
> early stages of project development, because it's when the decisions
> have the biggest impact on later phases.

The rule about synchronizing access to operations declared in the
predefined library is an old rule.  It was true in Ada83 when using
Text_IO.  There are no new issues here.


> What I've learned in this thread is that:
> 1. Ada standard containers should be protected against concurrent
> accesses (in the general meaning of "access") and it's the obligation of
> the user to do it.

Yes, the same as for any other unit in the predefined library.  (Do
note that monitor-style synchronization of container calls is allowed,
since the operations in the container library are not "potentially
blocking" calls.)


> 2. This serializes all users of the container with obvious consequences.

Well the consequences aren't so obvious to me!  I have no idea what
you're talking about, especially since you claimed above that
synchronization was a "non-issue" for you.


> Whether any of these two is a problem in any particular project is a
> non-issue. The point is that these two facts are to be understood, so
> that they can be taken into account when there's a time to do so.

Yes, you have to synchronize access to a units in the predefined
library.  That fact certainly needs to be understood.

Re: Multitasking and containers

[Matthew Heaney]

Maciej Sobczak <no.spam@no.spam.com> writes:

> That would be interesting, but would break apart when encapsulated within a
> protected object, because there multiple readers would be allowed.

But I think that's true only when multiple readers are calling protected
functions.  (There is a subtle difference in semantics between protected
functions and protected procedures.)  It does seem you'd need to use a
protected procedure when manipulating a container nested inside a protected
object, since a protected function wouldn't provide the level of
synchronization required.


> Having a mutex for readers sounds like a concurrency killer and relying on
> protected wrappers seems to be fragile because of this possible
> mutability. So - what is The Solution (tm) for multiple tasks reading from
> the same container?

Declare the container object inside a protected object, and use protected
procedures to manipulate the container.  Protected wrappers should be fine, as
long as you use protected procedures, not protected functions.


> Let's say you want to have N worker tasks consulting a shared dictionary
> (map) that was initialized before the tasks started their work. How would you
> solve this?

As above: declare the container object inside a protected object, and use
protected procedures to manipulate the container.

Re: Multitasking and containers

[Matthew Heaney]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> [ I don't know if ARM 2005 permits mutable implementations of read
> operations on the containers. I suppose it does, so the need to lock upon
> read. ]

Yes, some read operations mutate the container temporarily.  That's why the
user needs to always synchronize access to the container (even for read
operations) if the container can be accessed by several tasks.

Re: Multitasking and containers

[Matthew Heaney]

Maciej Sobczak <no.spam@no.spam.com> writes:

> Paragraph 3 in Annex A says that it's OK to call any standard subprogram from
> concurrent tasks as long as the parameters do not overlap. John Barnes
> ("Progamming in Ada 2005") suggests that in order to (for example) read from
> the same container, the operations need to be protected "by using the normal
> techniques such as protected objects".

Right.


> But reading from the protected object is not mutually exclusive (many readers
> are allowed) - so where's the gain? What's the difference between concurrent
> reads of, say, a Vector via protected object vs. direct access?

The reason is a conflict between safety and flexibility, a conflict that was
resolved in favor of safety.

The container must set some internal state to indicate that Query_Element is
executing, in order to prevent you from doing things inside Query_Element that
would potentially destroy the element (such as Delete'ing it).

Even though Query_Element is technically a read-only operation, that's true
only in the logical sense, not the physical sense.  It doesn't look like
Query_Element modifies the container, but it really does modify the container,
to set some state that indicates a Query_Element is in progress.

Yes, it would seem as if it should be possible for multiple tasks to all be
reading from the container simultaneously.  But it's impossible to do that and
also satisfy the requirement that the container detect potentially harmful
manipulation of the container while Query_Element is executing.

So multiple tasks -- even tasks only calling (logically) read-only operations
-- cannot simultaneously call container operations without also synchronizing
the tasks, by wrapping the container inside a protected object, using a
critical section, etc.

-Matt