Concurrent access to packed arrays

Concurrent access to packed arrays

[Florian Weimer]

For simplicity, assume the array is of type String.  Some machines
(early Alphas?) do not offer load/store functions for individual
octets, so the characters of a string might not be independently
addressable.  Now suppose we have a string object and a variable which
indicates the last position in the string which has been written:

        The_String : String (1 .. Some_Maximum);
        Last_Written : Natural;
        pragma Atomic (Last_Written);

Task A1, A2, ... make a copy of Last_Written and read data from
The_String (1 .. Copy_Of_Last_Written).  Task B continues to write to
The_String (Last_Written + 1 .. Some_Maximum) and update Last_Written.
This might result in concurrent read and write access to the same
memory location, but I think this will work anyway because task B
writes to the location without changing the part interpreted by the
reading tasks.  However, according to the Ada standard, this scenario
results in erroneous execution.

Now my question: Are there in fact platforms where this doesn't work?
Shall I play safe and apply pragma Atomic_Components (and use an
unpacked array instead of a packed one)?

Re: Concurrent access to packed arrays

[Robert Dewar]

In article <87g0id8939.fsf@deneb.enyo.de>,
  Florian Weimer <fw@deneb.enyo.de> wrote:
> Now my question: Are there in fact platforms where this
> doesn't work? Shall I play safe and apply pragma
> Atomic_Components (and use an
> unpacked array instead of a packed one)?


This is the general issue of independence, which is examined
in detail in Norman Schulman's PhD thesis on shared variables
(NYU, advisor me :-)

Ada 83 was badly messed up here, because it required packing
of packed arrays, and required independence (the ability of
tasks to access different components independently). This
was the result of a last minute editorial change, done in
the proofs, where someone suddently decided that it was a
typographical error that excluded array elements from the
independence rules in section 9.11. Well perhaps it was a
typographical error, but I had always registered this "error"
as a fundamental necessity for correctness, and was appalled
by the change :-) There is no way to implement Ada 83 as
described in the RM in this respect.

The fix for this in Ada 95 is to guarantee independence only
for non-packed arrays, and yes, it is definitely the case
that most certainly there *ARE* platforms where an assumption
of independence for packed strings is quite wrong (generic
alpha is one example, other word addressed machines are another
example).

It is definitely erroneous to have two different tasks access
elements of the same string without synchronization. If you
are asking "can I get away with erroneous code", no one is
going to tell you yes!.

For example, one can imagine a compiler where you have a
call

    procedure K (A : String_Ptr; B : String_Ptr) is
    begin
       ... code where one task works on A and one task works
       ... on B

       (compiler legitimately assumes that A and B cannot
        point to the same string, and generates code based
        on this conclusion).

so that your code malfunctions regardless of the target.

NEVER try to outguess a compiler when it comes to erroneous
code. ALWAYS avoid erroneous code ALL the time.

The proper approach is to use an unpacked array of characters.
On most targets, this will indeed pack, so you will lose
nothing except on targets where what you were trying was
seriously wrong.

The business of Atomic_Components is irrelevant. Indeed I would
say that by definition all components of a packed array are
atomic, because the only way you could tell they were not
atomic was if you had erroneous code where some other task
tried to access a component from the same array without
proper synchronization.




Sent via Deja.com
http://www.deja.com/

Re: Concurrent access to packed arrays

[Florian Weimer]

Mats Weber <matsw@mac.com> writes:

> Yes, I think there are. When task B writes the data, it will do
> something like
> 
>    The_String(Last_Written + 1) := ...
>    Last_Written := Last_Written + 1;
> 
> on modern architectures, the memory accesses can get reordered, i.e.
> Last_Written can get updated before The_String and reading tasks will
> read uninitialized data.

Very good point.  Thanks.  (Not every architecture has complex cache
coherency protocols like Intel's. ;-)

So I'm going to add an interface which uses a protected type.
(There's no need to use it by default because most of the time, no
concurrent access occurs.)

Re: Concurrent access to packed arrays

[Mats Weber]

Florian Weimer wrote:

> So I'm going to add an interface which uses a protected type.
> (There's no need to use it by default because most of the time, no
> concurrent access occurs.)

I don't know about Intel, but I know some version of the Alpha do
reorder memory accesses.

Re: Concurrent access to packed arrays

[Robert Dewar]

In article <3A735489.76FCC041@mail.com>,
  matsw@mail.com wrote:
> I don't know about Intel, but I know some version of the
> Alpha do reorder memory accesses.

You need to look at the manuals, obviously no architecture does
an arbitrary reordering of memory accesses.


Sent via Deja.com
http://www.deja.com/