User: Password:
Subscribe / Log in / New account

Transactional Memory

Transactional Memory

Posted Jun 4, 2009 17:51 UTC (Thu) by wahern (subscriber, #37304)
In reply to: Transactional Memory by mitchskin
Parent article: A look at two new languages: Vala and Clojure

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.

(Log in to post comments)

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:
Transactional Memory: Architectural Support for Lock-Free Data Structures
Herlihy & Moss (1993)

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 (guest, #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.

Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds