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

["(see below)" <yaldnif.w@blueyonder.co.uk>]

On 31/03/2008 14:03, in article C4169FA1.E214C%yaldnif.w@blueyonder.co.uk,
"(see below)" <yaldnif.w@blueyonder.co.uk> wrote:

> On 31/03/2008 08:59, in article wvbrd4pbz5mj.fsf@astra06.norway.sun.com,
> "Ole-Hjalmar Kristensen"
> <ole-hjalmar.kristensen@substitute_employer_here.com> wrote:
>> If you do not refresh the cache at the beginning of a protected
>> procedure, how do you avoid reading stale data within the protected
>> object on a multiprocessor? And why the wording "cannot be used to
>> synchronize access to other *nonvolatile* shared variables"? Is the
>> implication that it *can* be used to synchronize other *volatile*
>> shared variables?
> 
> I think the wording is trying to cover all the bases.
> One clue is the phrase "_full_ cache consistency".
> The caches certainly need to be consistent with respect to the
> protected data, even for protected functions and procedures,
> but only entries ensure global consistency and so provide
> synchronization of data that is not local to the protected object.

In practice, I would expect even protected functions and procedures to need
a mutex, and that that would execute a memory barrier operation, so
enforcing global consistency. To verify this I ran some simple tests myself.

I implemented Simpson's algorithm for a lock-free shared variable.
Here is the relevant code:

> package Wait_Free_Atomicity is
> 
>     type an_Atomic is limited private;
>     
>     procedure Update  (Atomic_Item : in out an_Atomic; Item : in  an_Item);
>     procedure Inspect (Atomic_Item : in out an_Atomic; Item : out an_Item);
> 
> private
> 
>     type a_Bistate is new Boolean;
>     pragma Atomic (a_Bistate);
> 
>     type a_Slot_Matrix is array (a_Bistate, a_Bistate) of an_Item;
>     pragma Volatile_Components (a_Slot_Matrix);
>             
>     type a_Full_Column is array (a_Bistate) of a_Bistate;
>     pragma Atomic_Components (a_Full_Column);
>    
>    type an_Atomic is
>       limited record
>             Data_Slot_Matrix    : a_Slot_Matrix;
>             Last_Column_Updated : a_Full_Column  :=
>                   (others => a_Bistate'First);
>             Last_Row_Inspected, Last_Row_Updated : a_Bistate :=
>                   a_Bistate'First;
>             pragma Atomic (Last_Row_Inspected);
>             pragma Atomic (Last_Row_Updated);
>         end record;
> 
> end Wait_Free_Atomicity;
> 
> package body Wait_Free_Atomicity is
>         
>     procedure Update (Atomic_Item : in out an_Atomic; Item : in  an_Item) is
>         Row : constant a_Bistate := not Atomic_Item.Last_Row_Inspected;
>         Col : constant a_Bistate := not Atomic_Item.Last_Column_Updated(Row);
>     begin
>         Atomic_Item.Data_Slot_Matrix(Row, Col) := Item;
>         Atomic_Item.Last_Column_Updated(Row) := Col;
>         Atomic_Item.Last_Row_Updated := Row;
>         -- no explicit membar sync
>     end Update;
>     
>     procedure Inspect (Atomic_Item : in out an_Atomic; Item : out an_Item) is
>         Row : constant a_Bistate := Atomic_Item.Last_Row_Updated;
>         Col : a_Bistate;
>         pragma Atomic (Col);
>     begin
>         Atomic_Item.Last_Row_Inspected := Row;
>         Col  := Atomic_Item.Last_Column_Updated(Row);
>         Item := Atomic_Item.Data_Slot_Matrix(Row, Col);
>         -- no explicit membar sync
>     end Inspect;
> 
> end Wait_Free_Atomicity;

The test was to run it with the Item type being a 5-tuple of consecutive
integers, and checking that the inspecting task received correct tuples.

When run on a single-processor machine (Mac PowerBook) there were no
consistency failures.

When run on a dual-core machine (MacBook Pro with Core 2 Duo CPU) there
were many consistency failures.

When the body was modified as follows:

> package body Wait_Free_Atomicity is
>     
>     protected Mem_Bar is
>        entry Sync;
>     end Mem_Bar;
>     
>     protected body Mem_Bar is
>        entry Sync when Boolean'(True) is
>        begin
>           null;
>        end Sync;
>     end Mem_Bar;
>     
>     procedure Update (Atomic_Item : in out an_Atomic; Item : in  an_Item) is
>         Row : constant a_Bistate := not Atomic_Item.Last_Row_Inspected;
>         Col : constant a_Bistate := not Atomic_Item.Last_Column_Updated(Row);
>     begin
>         Atomic_Item.Data_Slot_Matrix(Row, Col) := Item;
>         Atomic_Item.Last_Column_Updated(Row) := Col;
>         Atomic_Item.Last_Row_Updated := Row;
>         Mem_Bar.Sync;
>     end Update;
>     
>     procedure Inspect (Atomic_Item : in out an_Atomic; Item : out an_Item) is
>         Row : constant a_Bistate := Atomic_Item.Last_Row_Updated;
>         Col : a_Bistate;
>         pragma Atomic (Col);
>     begin
>         Atomic_Item.Last_Row_Inspected := Row;
>         Col  := Atomic_Item.Last_Column_Updated(Row);
>         Item := Atomic_Item.Data_Slot_Matrix(Row, Col);
>         Mem_Bar.Sync;
>     end Inspect;
> 
> end Wait_Free_Atomicity;

Note that the tuples are external to the protected object.

The consistency failures went away.
The same result held when the Mem_Bar.Sync entry was replaced by a protected
procedure; ditto with a protected function.

For the sake of interest, here are the test results, with execution times
(CPU times exceed real times because there are 2 cores working
simultaneously):

20_000_000 updates

with no sync:
3689 consistency failures.
        0.90 real         0.73 user         0.09 sys

with entry sync:
No consistency failures.
      222.90 real       138.52 user       265.78 sys

with procedure sync:
No consistency failures.
      149.36 real       127.65 user       164.96 sys

with function sync:
No consistency failures.
      142.43 real       120.33 user       155.93 sys

-- 
Bill Findlay
<surname><forename> chez blueyonder.co.uk