| |||||||||||||
|
| |||||||||||||
Transactional MemoryTransactional MemoryPosted Jun 4, 2009 14:38 UTC (Thu) by mitchskin (subscriber, #32405)In reply to: Transactional Memory by wahern Parent article: A look at two new languages: Vala and Clojure
The only real STM implementations are on paper, or maybe in a lab w/ a custom ASIC.It sounds like you're thinking about hardware transactional memory. Software transactional memory (STM) may indeed be implemented using locks, but it does provide an interface that means client code can avoid using locks directly. You're right that there still may be locking somewhere, but that can still be a win since it isolates locking to one widely shared piece of code.
(Log in to post comments)
Transactional Memory Posted Jun 4, 2009 17:51 UTC (Thu) by wahern (subscriber, #37304) [Link]
Actually, Software Transactional Memory is the correct term. To wit:
"Software Transactional Memory", Nir Shavit and Dan Toutiou, 1997.
The confusion is part of what I'm raging about ;) You can't simply say, "well, by 'software' I mean whatever I want it to mean, and not what I'm implying".
Fact is, real STM does not exist. It doesn't exist in the JVM, it doesn't exist anywhere in production (notwithstanding the Rock CPU mention). It can only exist w/ a universal primitive like LL/SC, as proven by, I believe, Herlihy.
Everything else can deadlock, and can livelock (if you're providing STM semantics).
Now, as pointed out elsethread, yes, STM can provide conceptual amelioration regarding the semantics of a language. But when that new language is running on your desktop, there is no way to "fake" it.
Existing STM is analagous to Perl5/6's "quantum" operators. Conceptually useful, but it's not literally doing it.
But don't take my word for it. Here's a small list of relevant material. These are the papers I still have in my research directory:
"Software Transactional Memory", Shavit and Toutiou, 1997.
"A Methodology for Implementing Highly Concurrent Data Objects", Herlihy, 1993.
"A Methodology for Implementing Highly Concurrent Data Structures", Herlihy, 1990.
"A Practical Multi-Word Compare-and-Swap Operation", Harris, Fraser, Pratt, 2002.
"Impossibility and Universality Results for Wait-Free Synchronization", Herlihy, 1988.
"Practical Lock-Free and Wait-Free LL:SC:VL Implementations Using 64-bit CAS", Michael, 2004.
"Wait-Free Synchronization", Herlihy, 1991.
Transactional Memory Posted Jun 4, 2009 20:08 UTC (Thu) by Frej (subscriber, #4165) [Link]
I think your angle on (software) transactional memory is lockfree/nonblocking/wait-free stuff (the terms are somewhat vaguely defined imo).
But it's not the only point of STM (today). It's about safety and ease of concurrent programming on shared memory architectures.
Secondly, you missed the paper that inspired Software TM:
Note that transactional hardware as an idea goes further back. But the above paper is pure hardware. Shavit and Toutiou later introduced Software Transactional Memory in the paper you posted.
So it is correct to distinguish between Transactional Memory and Software (assisted) Transactional Memory. Also, it does not make it pen and paper because the implementation uses locks. So surely STM exists, there are many implementations - The best are compiler/language assisted.
Transactional Memory Posted Jun 11, 2009 14:06 UTC (Thu) by tvld (subscriber, #59052) [Link]
First, compare-and-set (CAS, cmpxchg,...) is universal, as is LL/SC.
Therefore, you can build nonblocking STMs, and people actually do (see, for example, the paper describing DSTM (one of the first STMs)).
Assuming that your memory transactions don't block by waiting for external events to happen, no sane (S)TM will deadlock. Some might live-lock, but that is just a question of contention management, and not a principal limitation (remember that CAS is universal...).
Please actually do read the relevant literature.
|
|
||||||||||||