begin quoting Andrew Lentvorski as of Tue, Apr 03, 2007 at 08:29:21PM -0700:
> Stewart Stremler wrote:
> >So instead of Test And Set, we have Compare And Swap as our atomic
> >operation. Okay. This is less clever than it first seemed, as it's a new
> >atomic instruction.
>
> Not really. Compare and Swap and Test and Set are isomorphic. If you
> have one, you can do the other.
Yeah, I get that. I was working under the impression (dangerous, y'know)
that TAS was register->RAM, while CAS was RAM->RAM. I suspect I'm just
projecting "what I'm used to" onto the wider semantics.
But it pretty much comes down to having an atomic comare and set
instruction *somewhere*.
> The issue is that you *must* have an atomic hardware instruction and you
> will need some form of memory barrier instruction. All modern
> microprocessors have had this for quite a while. It's not a big burden.
...and you need to be able to get at this behavior from within the
language.
> >Still, this sort of atomic instruction offers some interesting ways to
> >tackle concurrent programming problems -- and is the sort of thing that
> >probably _ought_ to be introduced into concurrent languages.
>
> See: "Purely Functional Data Structures" by Okasaki. The issue is how
> to create a data structure that persists even while being mutated or,
> alternatively, to create efficient data structures that persist even as
> newer versions are getting created.
>
> Warning: Okasaki makes my brain hurt.
Okay, I got the PDF. I'll see how much my brain bleeds...
Amortized data structures, fun!
> >Atomicity is the hard nut. If we could have a language that had atomic
> >sections, we'd probably have a lot more fun with concurrent programming.
> >I'd *love* to be able to say:
> >
> > atomic {
> > do_something();
> > do_something_else();
> > }
> >
> >But that's probably a really hard feature to implement. :)
>
> Congratulations, you just described "Composable Memory Transactions".
Heh.
I wasn't trying to describe the concept, but rather the syntax I'd
like to see. The concept is pretty old, I should think.
> http://research.microsoft.com/~simonpj/papers/stm/stm.pdf
>
> This is one of the cornerstones of Shared Transactional Memory.
Heh. Yup. There it is.
I wasn't thinking about transactions, as those "retry until success",
like locks, but with bigger pieces of code.
--
Process A: while true twiddle X. Process B: atomic { delay. twiddle X. }
Stewart Stremler
--
[email protected]
http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
