Contributed by marco on from the random-thoughts dept.
On a different note, besides Jordan visiting, Thomas Nordin (nordin@) also showed up. He is finishing up his PhD and has not been hacking OpenBSD because of that. To keep himself sane he has done some "light reading" on Software Transactional Memory and for good measure he has also written a working implementation of this in user space. What this does is making memory writes to shared data structures behave the same way as a database writes out a record. This is all done without any locks! Here is a simple description:
- Open a handle to a shared data structure
- If its opened for writing copy the data locally
- If its opened for reading read the variables as you would as if you had locks and close the read handle
- If no one changed the global data structure from underneath you atomically replace the whole global data structure with your local copy
- If someone did change the global data structure restart the transaction
Anyway the reason i bring this up is because STM might start making its appearance in hardware in the future. The reason why this in interesting is because the current SMP locking mechanisms, big-lock and fine-grained-lock, simply suck. Big-lock hurts performance, fine-grained is too complex and puts the onus on the programmer to do it right. Not everyone can be an (instant) expert on all data structures in any given system. There are complex interactions and idiosyncrasies implicit to any system that can require a long bumpy road to learn and understand. STM does not seem to suffer from these issues. All that said I believe that locking mechanisms are bad and that we need something else. I am not smart enough to determine if it is STM but it sounds at least like a plausible alternative. Enough theoretical mambo-jambo! time will tell.
(Comments are closed)
By Stefan Sonnenberg-Carstens (193.22.160.2) on
Comments
By phessler (209.204.157.106) on
By art (194.237.150.170) on
By Alejo (212.161.126.5) on
By Anton Maksimenkov (212.57.174.2) on
And where I can see mentioned example (source code) "and for good measure he has also written a working implementation of this in user space"? And as far as it working, may it already be used for some userland programming?
Comments
By Marco Peereboom (67.64.89.177) marco@peereboom.us on http://www.peereboom.us
I reported this because it is an interesting mind puzzle. I think it would be cute to put this into a userland library though. I'll try to convince nordin@ to do that.
Comments
By Anton Maksimenkov (212.57.174.2) on
Anyhow, as you approve, it will be very interesting in userland arena too. For example, sometimes I avoid to use pthreads because of interlock snare and try to adapt all to some kind of FSM (less effective in some simple cases but with low cost in developing and debugging). But as far as I understand explained technology (STM) in the manner of userland lib may help and increase performance without lock design overhead in such cases.
And in couple with arising 'rthread' library it may become VERY powerful weapon!
Comments
By Anonymous Coward (69.36.252.2) on
And when you use them, the remainder of your application tends to fall into place easier.
They're a little clumsy sometimes when written in particular languages, which is why you find so many people who develop a bad habit of avoiding them. But, they work well within the structure of C programs.
Today you see many people beatup and tired of writing threaded code. They're writing network daemons again with select()/poll() (or the upgrades: kqueue()/epoll()). And of course, writing FSM's again.
I suspect STM will find niche uses. A well designed library would go a long way toward quickly developing good practices regarding when and when not to use the method. The library in LibTLX is about the opposite of what I'd consider well designed. Hopefully it's really nothing more than a proof of concept.
Comments
By djm@ (203.217.30.86) on
By Marco Peereboom (67.64.89.177) marco@peereboom.us on http://www.peereboom.us
By tedu (69.12.168.114) on
Comments
By beck (129.128.11.43) beck@openbsd.org on http://www.seizurerobots.com/
>nearly so many problems with concurrency. real dining philosophers
>rarely starve.
Yes, real dining philisophers don't starve, but in practice they stab each other with their forks. that's the problem - this "natural mapping" s horsehit. workers fight amongst each other - and don't always solve things amicably, they occasionally sabotage each others work or duplicate effort needlessly - the "natural mapping" of threads to "workers" completely ignores this reality.
"workers" map to threads in a perfect world. In a perfect world I'd be a communist - unfortunately communism only works in a fantasy world where people are not fundamentally lazy and greedy (don't feel bad about it, I don't - it's genetic) - similarly threads only "naturally" map to problems where "workers" can't disagree/ignore/sabotage/duplicate etc. etc. Implementations for perfect worlds cause security/reliability problems when exposed to the cold harsh light of reality.
Of course there are places where threads, like communists, have their
redeeming values, they're just over/mis-used at the moment.
By dons@ (220.233.48.34) on
I don't think it's been explained clearly, but STM is already implemented and widely used in Haskell. You can use it right now with GHC 6.4 or later, which runs nicely on OpenBSD x86 and amd64 (and others with some porting effort).
One notable real world app already making heavy use of STM is Pugs, the Perl 6 compiler/interpreter written in Haskell. STM is almost certainly going to be the foundation for a new generation of concurrency abstractions emerging in Haskell.
Some links:
* The original STM paper
* The STM API visible to Haskell programmers
By Ober (192.35.232.241) Ober@linbsd.org on http://www.linbsd.org
By Amit Kulkarni (67.142.130.13) on http://forestlaw.blogspot.com/
Comments
By igi (83.208.110.151) on
data structure cannot be modified during reading. you either read tho whole old version, or the new version. never mix of them since the writing process atomically changes it (e.g. redirecting pointer with a single op mov).
Comments
By Wouter Coene (213.84.53.206) on http://web.irdc.nl/
So erm.. how precisely do you atomically replace a datastructure of, say, 512 bytes? I'm having a hard time visualising this in terms of CPU instructions (other than simply locking the bus).
Or is this left as an exercise for the reader? :)
Comments
By Wouter Coene (213.84.53.206) on http://web.irdc.nl/
By m0rf (68.104.17.51) on
Comments
By Anonymous Coward (70.27.15.123) on
Comments
By m0rf (68.104.17.51) on
The main advantage to using the MVCC model of concurrency control rather than locking is that in MVCC locks acquired for querying (reading) data do not conflict with locks acquired for writing data, and so reading never blocks writing and writing never blocks reading. "
no obviously not
Comments
By Anonymous Coward (70.27.15.123) on
So no, postgresql does not have a dirty read problem. And if you bothered to read, neither does STM. Writes are atomic, you either read the old data, or the new data, there is no in between.
By Anonymous Coward (162.58.82.244) on
http://leaf.dragonflybsd.org/mailarchive/kernel/2005-12/msg00072.html
Comments
By Anonymous Coward (203.26.136.135) on