chris@mimsy.UUCP (Chris Torek) (05/24/88)
In article <199@gannet.cl.cam.ac.uk> scc@cl.cam.ac.uk (Stephen Crawley) writes: >... multi-process applications that use shared memory. Consider two >processes A and B with a shared variable v, and the following code > int x = v /* A1 */ | v = 2 /* B1 */ > int y = v /* A2 */ | Even *with* volatile declarations, you get no solid guarantee. Suppose that v is a `volatile int', and that you are running on a bit-oriented binary machine and v has been placed across two different memory banks. The sequence might be A1, B1 <first half>, A2, B1 <second half>: A1: x = 1 | v = 0...0 1 B1: v = 2 <first half> | v = 0...0 0 <lower write complete> A2: y = 0 | v = 0...0 0 <upper write incomplete> | v = 0...1 0 <upper write complete> This is perhaps unlikely, but in fact something similar could easily happen on a multi-cpu R2000-based system (assuming 32 bit integers), although not with the values 1 and 2. Volatility is only part of what you need for synchronisation. -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
stuart@cs.rochester.edu (Stuart Friedberg) (05/24/88)
In article <199@gannet.cl.cam.ac.uk> scc@cl.cam.ac.uk (Stephen Crawley) writes: >... multi-process applications that use shared memory. Consider two >processes A and B with a shared variable v, and the following code > int x = v /* A1 */ | v = 2 /* B1 */ > int y = v /* A2 */ | In article <11629@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: >Even *with* volatile declarations, you get no solid guarantee. Suppose >that v is a `volatile int', and that you are running on a bit-oriented >binary machine and v has been placed across two different memory >banks. [...] >This is perhaps unlikely, but in fact something similar could >easily happen on a multi-cpu R2000-based system (assuming 32 bit >integers), although not with the values 1 and 2. The BBN Butterfly (but not the Butterfly+ nor the Butterfly 2, I believe) has exactly this problem. Each processor node is based on the MC68000, with lots of fancy coprocessor support to allow each 68K to issue memory references transparently to both local and remote physical memory. Any memory location can be accessed by as many as 256 processors. *Really* volatile. :-) However, only the initial coprocessors (PNC's) only supported 16-bit (word) operations atomically. 32-bit operations could, and very *often* did, have unwanted interleavings. To do the 32-bit ops, you have to lock the memory you want first in your software. Needless to say, this is less efficient than letting the hardware do it for you. It was doubly obnoxious, since we have people here investigating highly concurrent data structures that don't need locking *provided* some basic operations like add or compare-and-swap could be done atomically. Stu Friedberg {ames,cmcl2,rutgers}!rochester!stuart stuart@cs.rochester.edu
firth@sei.cmu.edu (Robert Firth) (05/25/88)
In article <11629@mimsy.UUCP> chris@mimsy.UUCP (Chris Torek) writes: [ volatile variables are still vulnerable to the "interrupted update" error] >Volatility is only part of what you need for synchronisation. It might be worth pointing out that the Ada programming language provides the pragma "Shared" to indicate shared variables. The language reference manual says [RM 9.11 (11)] An implementation must restrict the objects for which the pragma SHARED is allowed to objects for which each of direct reading and direct updating is implemented as an indivisible operation. I believe this captures the required semantics. (Of course, the RM also explains you can't slave local copies &c either)