Re: [Caml-list] atomicity guarantees for threaded code

[skaller <skaller@users.sourceforge.net>]

On Sat, 2004-10-30 at 07:50, David Brown wrote:
> On Fri, Oct 29, 2004 at 09:39:07AM -0700, Ker Lutyn wrote:
> 
> > thread 1:
> > 
> >     mapref := StringMap.add key value !mapref
> > 
> > thread 2 through thread N:
> > 
> >     let value = StringMap.find key !mapref
> > 
> > Assume only thread 1 can update the reference. Is this code safe?
> 
> As long as the reference write is atomic, which it is going to be, I would
> suspect this is safe.  It probably would even be safe if multiple threads
> updated the reference, but you might just drop entries.

It isn't clear though. On x86 you can have 1 byte alignment
for an address. What happens if:

(a) thread 2 reads half an address, then gets a page fault
(b) thread 1 writes half an address, then gets a page fault,
(c) thread 1 writes the second half of the address
(d) thread 2 reads the second half of the WRONG address

The x86 can interrupt instructions in the middle ***
Actually, the 68K can do this too. On the x86 the
only way to get an atomic operation is on physical
memory, and by also locking the bus. CISC machines
get rather nasty ..

Bottom line: you have to use a specified atomic
access technique (eg sig_atomic_t, locks, etc) if you 
want to be sure an access is atomic.

It is likely as you say that there won't be a problem
on most processors (by which I mean the code
Ocaml generates will be effectively atomic wrt. threads)
and Ocaml could even guarrantee it, but there is a risk
for some processor extra code would have to generated
to ensure the guarrantee.

*** And I mean even with IRQs. In particular
I found a bug in the early 80186 hardware,
where if you used two prefixes such as with

	ES REP MOVB

then RTTI failed to restart the instruction correctly,
setting the PC to the REP instead of the ES prefix.
The MOVB instruction moves many bytes and must
be interruptible, even on the 186 which has no VM.


-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net