From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Thread: 103376,e0e1d3b3f7c994b8 X-Google-Attributes: gid103376,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news4.google.com!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: "(see below)" Newsgroups: comp.lang.ada Subject: Re: Robert Dewar's great article about the Strengths of Ada over other langauges in multiprocessing! Date: Mon, 31 Mar 2008 15:17:56 +0100 Message-ID: References: <13t4b2kkjem20f3@corp.supernews.com> <89af8399-94fb-42b3-909d-edf3c98d32e5@n75g2000hsh.googlegroups.com> <87bq56peg1.fsf@mid.deneb.enyo.de> <87bq516uri.fsf@mid.deneb.enyo.de> <87prtfzrtl.fsf@mid.deneb.enyo.de> <87wsnmg1ju.fsf@mid.deneb.enyo.de> Mime-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Trace: individual.net PoDff0PV2VA/brKczxqQlwG69Gdz2s0jZFkngCIvy6UxLUgRtb Cancel-Lock: sha1:ZjKPGx7ddXuhzAxWnVtDTr6iMDw= User-Agent: Microsoft-Entourage/12.1.0.080305 Thread-Topic: Robert Dewar's great article about the Strengths of Ada over other langauges in multiprocessing! Thread-Index: AciTL5OmGcTUZU5UYkOkhLJVFWAqSQACnAXo Xref: g2news1.google.com comp.lang.ada:20671 Date: 2008-03-31T15:17:56+01:00 List-Id: On 31/03/2008 14:03, in article C4169FA1.E214C%yaldnif.w@blueyonder.co.uk, "(see below)" wrote: > On 31/03/2008 08:59, in article wvbrd4pbz5mj.fsf@astra06.norway.sun.com, > "Ole-Hjalmar Kristensen" > 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 chez blueyonder.co.uk