Re: Robert Dewar's great article about the Strengths of Ada over other langauges in multiprocessing!

[Ole-Hjalmar Kristensen <ole-hjalmar.kristensen@substitute_employer_here.com>]

>>>>> "FW" == Florian Weimer <fw@deneb.enyo.de> writes:

    FW> * Ole-Hjalmar Kristensen:
    >> If you mean that it may be difficult to optimize, I agree, but I
    >> cannot agree that you need *more* than an entryless protected object
    >> to implement a hash table, since it guarantees that each operation on
    >> the object is indivisible. 

    FW> You need some kind of signaling construct.  Suppose you put some access
    FW> value as a value into the hash table.  If there's no signaling (the case
    FW> of an entryless protected object, it seems), a task that retrieves the
    FW> value from the table cannot make any assumptions regarding the object
    FW> the access value refers to, unless there is some other form of
    FW> synchronization.

First, I never said it can be used to synchronize something which is
outside the protected object or the hash table. But it will serialize
the access to the protected object, so any task will see consistent
key, value pairs, which is all the synchronization you need for the
hash table itself.

Second, I cannot find anything in the RM which says you can make *any*
assumptions about objects which are outside the protected object so I
cannot see how signaling will help you.

Actually there are two cases here:

1. The task is calling a protected function or procedure to retrieve
   the pointer and accesses the object through the pointer after the
   call. This is obviously bad code unless the object is atomic, which
   in practice means a single word.

2. The task is calling a protected function or procedure and accesses
   the object through the pointer while it is inside the protected
   object. In both cases you are guaranteed that you will see any
   previous updates to the protected object itself and that no one is
   updating the protected object while you are inside, but unless the
   other object is atomic I do not think you have the guarantee that
   you even see previous updates to it, at least in the multiprocessor
   case. You may speculate that since the implementation of a
   protected call typically involves a memory barrier, it will be safe
   to access data outside the protected object, but I would not bet on
   it.

    >> On the other hand, I cannot see any reason why Annex C just couldn't
    >> say that intrinsic subprograms for compare-amd-swap and similar
    >> machine operations shall be provided *if* they are available on a
    >> platform.

    FW> CAS alone is not sufficient, you also need some sort of barrier (both
    FW> against compiler optimizations and reordering in the silicon).

Which is why I said compare-and-swap and similar machine operations.

With respect to compiler optimizations, I assume you are thinking of
the kind of reordering decribed by Boehm in his paper where some
compilers introduced extra reads and writes while the pthread mutex
was not held? This is obviously a problem, the compiler needs to know
whether a variable may be accessed by multiple threads or not to do
sensible optimizations. But I assume that pragma atomic would be
sufficient to take care of such cases (all atomic objects are volatile):

"15   For an atomic object (including an atomic component) all reads and
updates of the object as a whole are indivisible.

16   For a volatile object all reads and updates of the object as a whole are
performed directly to memory.

        16.a   Implementation Note:  This precludes any use of register
        temporaries, caches, and other similar optimizations for that object."

When it comes to reordering in the silicon, at least in the Solaris
case, this is already taken care of in the atomic library operations,
see under NOTES in the excerpt from the man page below. Only if you
need synchronization between *different* variables do you need memory
barriers.


Standard C Library Functions                       atomic_ops(3C)

NAME
     atomic_ops - atomic operations

SYNOPSIS
     #include <atomic.h>

DESCRIPTION
     This collection of functions provides atomic  memory  opera-
     tions. There are 8 different classes of atomic operations:

     atomic_add(3C)  These functions provide an  atomic  addition
                     of a signed value to a variable.

     atomic_and(3C)  These functions provide  an  atomic  logical
                     'and' of a value to a variable.

     atomic_bits(3C) These functions provide atomic  bit  setting
                     and clearing within a variable.

     atomic_cas(3C)  These functions provide an atomic comparison
                     of  a  value  with  a  variable. If the com-
                     parison is equal, then swap in a  new  value
                     for the variable, returning the old value of
                     the variable in either case.

     atomic_dec(3C)  These functions provide an atomic  decrement
                     on a variable.

     atomic_inc(3C)  These functions provide an atomic  increment
                     on a variable.

     atomic_or(3C)   These functions provide  an  atomic  logical
                     'or' of a value to a variable.

     atomic_swap(3C) These functions provide an atomic swap of  a
                     value  with  a  variable,  returning the old
                     value of the variable.

<snip>

NOTES
     Atomic instructions ensure global visibility of  atomically-
     modified  variables on completion.  In a relaxed store order
     system, this does not guarantee that the visibility of other
     variables  will  be  synchronized with the completion of the
     atomic instruction. If  such  synchronization  is  required,
     memory    barrier    instructions    must   be   used.   See
     membar_ops(3C).


-- 
   C++: The power, elegance and simplicity of a hand grenade.