Software Transactional Memory

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Software Transactional Memory

Postby Berengal » Fri Feb 20, 2009 6:59 pm UTC

Long story

Short story: In concurrent software, STM is a way to synchronize reads and writes to shared memory between threads. A set of reads and writes and intermediate computations is called a transaction, and each transaction is atomic. What happens is that during a transaction, each read and write is recorded, and at the end of the transaction the log is validated before any changes are committed. If the program detects that another thread has modified the shared memory, the transaction is rolled back and retried. This way the programmer doesn't have to worry about taking locks himself, and after the transaction has finished, you're guaranteed the transaction completed without seeing any inconsistent state.

Is this to synchronizing what garbage collection is to memory management? What about other methods of thread communication such as message passing? How do you implement this in a sane way in the mainstream languages of today, such as Java?
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: Software Transactional Memory

Postby scwizard » Fri Feb 20, 2009 7:38 pm UTC

Seems like it. It requires the program to pretty much be aware of itself, in the same manner as garbage collection.

As for implementing this, just keep track of memory accesses, in the same way you'd keep track of references.
~= scwizard =~

Tac-Tics
Posts: 536
Joined: Thu Sep 13, 2007 7:58 pm UTC

Re: Software Transactional Memory

Postby Tac-Tics » Mon Mar 02, 2009 4:11 pm UTC

Berengal wrote:Is this to synchronizing what garbage collection is to memory management? What about other methods of thread communication such as message passing? How do you implement this in a sane way in the mainstream languages of today, such as Java?


I wouldn't say "synchronizing" is the best analog. Probably STM itself is the garbage collector of concurrency. You basically can't get it wrong. It's amazing sauce. The only problem, as far as I understand it, is that currently, there are no ways to get it to scale properly. It has a lot of overhead to it, and if a transaction is preempted by a competing thread, the computation must be restarted. But it's so simple and elegant, it's sure to gain popularity in future years.

Message passing is a little more practical and straightforward, currently. The idea is that state is never shared. When a foreign thread wants to make an update to your state, they have to send you a message asking you to do that. Then, it's up to you to read your inbox from time to time and follow through on requests. But that's all I know about it.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Software Transactional Memory

Postby Yakk » Mon Mar 02, 2009 7:09 pm UTC

So, with memory management, you get a bounded performance hit, and guarantees of correctness.

Does STM have that guarantee? (I see no claims that starvation is impossible)

It also requires solving the halting problem (to determine if a read transaction is doomed to run forever because it read inconsistent state, and should thus be terminated), or bounding the running time of a given transaction to a finite value (meaning that your in-transaction code is not Turing complete, but your between-transaction code can be), or having people who write transactions take care not to generate bad internal behaviour based off of inconsistent state.

STM seems to be at least as good as reference counting is for the memory leak problem, however.

On top of that, highly multi threaded programs need a threading system that scales.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Carnildo
Posts: 2023
Joined: Fri Jul 18, 2008 8:43 am UTC

Re: Software Transactional Memory

Postby Carnildo » Tue Mar 03, 2009 4:44 am UTC

Tac-Tics wrote:Message passing is a little more practical and straightforward, currently. The idea is that state is never shared. When a foreign thread wants to make an update to your state, they have to send you a message asking you to do that. Then, it's up to you to read your inbox from time to time and follow through on requests. But that's all I know about it.


As someone who's done a good deal of programming using message-passing, I'd have to say that it's the easiest method of coordinating between processes I've come across. It's very easy to reason about and very hard to mess up. The downsides I've encountered are an inability to maintain a coherent program state (you need to design around the fact that each process has its own idea of what the program as a whole looks like) and that moving large datasets around a small piece at a time is slow.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Software Transactional Memory

Postby Berengal » Tue Mar 03, 2009 11:49 am UTC

Yakk wrote:Does STM have that guarantee? (I see no claims that starvation is impossible)
I don't think STM has a guarantee as such. It's possible a thread will never exit a transaction in the pathological case where the memory transacted over will be constantly written to by another thread. If by starvation you mean priority inversion, then this doesn't really have anything to do with memory, making memory transactions unlikely to affect it. If you mean resource starvation, it does solve deadlocks and livelocks (since there are no locks).

Yakk wrote:It also requires solving the halting problem (to determine if a read transaction is doomed to run forever because it read inconsistent state, and should thus be terminated), or bounding the running time of a given transaction to a finite value (meaning that your in-transaction code is not Turing complete, but your between-transaction code can be), or having people who write transactions take care not to generate bad internal behaviour based off of inconsistent state.

That is a problem. One simple way of implementing STM is to have a single global lock a thread needs to aquire before it can enter a transaction, and this guarantees that it won't ever see inconsistent state. It also sucks in the general sense. Another way is for a thread to "register" with the memory it transacts over, and when it commits it notifies all the other registrants of the memory it has updated (unneccessary for memory it has only read), so they can abort their current transaction (or at least check if they need to). Making the transaction language not turing complete does actually seem like a somewhat viable option. It already needs to be restricted in other regards such as IO, as you need to be able to roll back the entire transaction.

Yakk wrote:On top of that, highly multi threaded programs need a threading system that scales.

STMs on SMPs can have the same time-complexity as manual locking, assuming the underlying implementation is fail-fast (detects it can't commit before the entire transaction is complete). In the common case of many reads - few writes STM can outperform manual locking because of it's optimistic non-locking evaluation. If you want clusters or need lots of threads to write to the same memory, message passing is the better solution anyway.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Software Transactional Memory

Postby Yakk » Tue Mar 03, 2009 5:14 pm UTC

Berengal wrote:
Yakk wrote:Does STM have that guarantee? (I see no claims that starvation is impossible)
I don't think STM has a guarantee as such. It's possible a thread will never exit a transaction in the pathological case where the memory transacted over will be constantly written to by another thread. If by starvation you mean priority inversion, then this doesn't really have anything to do with memory, making memory transactions unlikely to affect it. If you mean resource starvation, it does solve deadlocks and livelocks (since there are no locks).

In a sense, the pathological case is a live lock.

Especially with slow-fail, you have process A and B. Both run the following function:

Code: Select all

f(int* p) -> [transaction]{local x := *p; ++x; *p := x; SomeBusyWork; return --x;}[/transaction]

That is a basic atomic increment. I included the busywork to make it clearer where the livelock could occur -- both processes could end up thrashing over the same bit of memory, each rendering the other thread's reads inconsistent, causing them to abort.

Or are all of the changes caused by the transaction supposed to be 'not there' until the commit? That isn't very feasible.

I can see ways you can probabilistically make this unlikely -- include psuedo random exponential backoff of retries, for example.

Yakk wrote:It also requires solving the halting problem[...]
That is a problem.

;)
One simple way of implementing STM is to have a single global lock a thread needs to aquire before it can enter a transaction, and this guarantees that it won't ever see inconsistent state. It also sucks in the general sense. Another way is for a thread to "register" with the memory it transacts over, and when it commits it notifies all the other registrants of the memory it has updated (unneccessary for memory it has only read), so they can abort their current transaction (or at least check if they need to).
Ya, that would help. Then transactions reading inconsistent state would be inconsistent, yet would eventually check their 'transaction failed' flag, and abort.
Making the transaction language not turing complete does actually seem like a somewhat viable option. It already needs to be restricted in other regards such as IO, as you need to be able to roll back the entire transaction.
The problem with a non-turing complete sub language is that it is, in a fundamental sense, hard to make a language non-turing complete. And then you often end up with a language with some annoyingly crippled features when you do it...

Given that you can check for transactional consistency at the end of the transaction, doing a periodic check for transactional consistency during the execution of your transaction seems like a reasonable thing to do. Then an infinite loop due to inconsistent state would get caught eventually. As it happens, this is equivalent to being "registered' with lazy evaluation of the registration, up to an O-notation multiplier (checking each memory block you are transaction dependant on, as opposed to sending a message to each transaction registered with each memory block).
Yakk wrote:On top of that, highly multi threaded programs need a threading system that scales.

STMs on SMPs can have the same time-complexity as manual locking, assuming the underlying implementation is fail-fast (detects it can't commit before the entire transaction is complete). In the common case of many reads - few writes STM can outperform manual locking because of it's optimistic non-locking evaluation. If you want clusters or need lots of threads to write to the same memory, message passing is the better solution anyway.
Or use non-blocking algorithms ... then again, non-blocking algorithms end up relying on lower level primitives which scale poorly as well (unless implemented via message passing...).

Message passing itself scales poorly, because if you have some kind of central model, you end up having the bookkeeping of the messages in the threads of that model, while being bombarded with messages from an upward scaling number of threads.

So I guess the solution is tell the hardware developers to just make faster computers. Or start learning functional languages. :)
Last edited by Yakk on Tue Mar 03, 2009 8:00 pm UTC, edited 3 times in total.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Mach1ne
Posts: 35
Joined: Tue Feb 24, 2009 5:20 pm UTC
Location: This exact location but 3 minutes from now

Re: Software Transactional Memory

Postby Mach1ne » Tue Mar 03, 2009 5:19 pm UTC

Mental Note: STM...something else i need to read up and look up on wikipedia.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Software Transactional Memory

Postby Yakk » Wed Mar 04, 2009 3:44 am UTC

Ran into this today, haven't read it, but looks like it could be interesting (and on topic):

http://www.microsoft.com/presspass/even ... _15x20.jpg
http://research.microsoft.com/en-us/projects/orcs/
http://research.microsoft.com/pubs/7065 ... 08-152.pdf

It claims to have a lightweight transactional model in software, that doesn't use rollbacks.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

Tac-Tics
Posts: 536
Joined: Thu Sep 13, 2007 7:58 pm UTC

Re: Software Transactional Memory

Postby Tac-Tics » Wed Mar 04, 2009 6:28 pm UTC

Mach1ne wrote:Mental Note: STM...something else i need to read up and look up on wikipedia.


Do your self a favor and forget Wikipedia's crap article.

The best introduction to the subject is hands down SPJ's Beautiful Concurrency:

https://research.microsoft.com/en-us/um ... /index.htm

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Software Transactional Memory

Postby Berengal » Sat Mar 07, 2009 4:49 am UTC

Yakk wrote:Ran into this today, haven't read it, but looks like it could be interesting (and on topic):

http://www.microsoft.com/presspass/even ... _15x20.jpg
http://research.microsoft.com/en-us/projects/orcs/
http://research.microsoft.com/pubs/7065 ... 08-152.pdf

It claims to have a lightweight transactional model in software, that doesn't use rollbacks.

From what I gathered from that paper, they simply copy the shared state into each thread and operate locally on that, then merge the changes back into the state. In haskell, that would simply be something like

Code: Select all

someloop stateTVar = do
  oldState <- atomically $ readTVar stateTVar
  let newState = updateState oldState
  newState `seq`
    atomically $ do possiblyUpdatedState <- readTVar stateTVar
                    writeTVar stateTVar (mergeMyChanges newState possiblyUpdatedState)
  someloop stateTVar

The seq is ugly, but possibly not needed depending on the context.

Anyway, the achieve no rollbacks by simply not doing all the work in a single transaction, which is simply good sense.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

g_korland
Posts: 1
Joined: Fri May 29, 2009 2:38 pm UTC

Re: Software Transactional Memory

Postby g_korland » Fri May 29, 2009 2:40 pm UTC

Check out java STM called Deuce - http://www.deucestm.org


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 4 guests