[Haskell-cafe] Software Transactional Memory and LWN

[Neil Brown]

Ketil Malde wrote:
> Hi,
>
> Browsing LWN, I ran across this comment:
>
> http://lwn.net/Articles/336039/
>
> The author makes a bunch of unsubstantiated claims about STM, namely
> that all implementations use locking under the hood, and that STM can
> live- and deadlock.  I've seen a lot of similar sentiments in other
> places as well (comp.arch springs to mind).
>
> Now, I'm no expert on STM, but I was pretty sure these are incorrect,
> and I certainly had the impression that Haskell's STM guarantees some
> progress - which it couldn't in a deadlock situation.
>   
I think there needs to be some differentiation here between the 
implementation of STM, and the programmer's use of STM.

The implementation of STM does effectively use locks (from memory, it's 
this paper that explains it: 
http://research.microsoft.com/en-us/um/people/tharris/papers/2007-tocs.pdf).  
I'm not sure how optimistic algorithms work, so maybe they can usually 
avoid locks -- but I suspect there are cases in every STM algorithm 
where locks are needed as a last resort.  The implementation of STM 
cannot deadlock.  There will always be at least one process making 
progress, but potentially at the expense of starving others indefinitely 
(a form of livelock).  So the implementation has locks, can't deadlock, 
can sort of livelock.

The use of STM does not involve locks, and one of STM's main advantages 
is that it hides explicit locks from the user.  If you have retry in STM 
(as Haskell does, but not all other implementations do) then you can 
write deadlocking code with it, and indeed you can simulate mutexes and 
so on using retry, hence allowing you to use your own constructed locks 
with STM.  So in using STM you can deadlock, and you can make some locks 
to use if you want, but it's not required.

Neil.