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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
