| |||||||||||||
KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems ServicesKHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems ServicesPosted Jul 26, 2009 16:28 UTC (Sun) by asdlfiui788b (guest, #58839)Parent article: KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services
Perhaps this is trolling but... I used to think that lock free algorithms based on CAS were a good idea, until I saw how the Alpha handled this. Load-Linked / Store-Conditional is more natural for hardware and also a damn sight more useful as it prevents the ABA problem (I've played with some quiescence algorithms for memory allocators to get round this but it's still ugly and difficult to implement). If you're interested in this sort of thing I'd strongly recommend looking up LL/SC and this kind of problem. While you're at it, look at Hans Boehm's paper on implementing LL/SC with 1 bit and a trivial amount of circuitry; it's so much easier that CAS and pretty much trivial to implement.
(Log in to post comments)
KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services Posted Jul 27, 2009 8:27 UTC (Mon) by xoddam (subscriber, #2322) [Link]
Any concurrency primitive for shared-memory multiprocessors on commodity hardware must for performance reasons be implemented at the cache-coherency level, using message passing (rather than having to hit the underlying slow, shared RAM on every synchronous operation) and is therefore several orders of magnitude more complex in silicon than anything that can be done "with 1 bit".
See http://lwn.net/Articles/252125/ (scroll down to section 3.3.4, Multi-processor support).
CAS and the spicier double-word CAS are obviously 'trickier' in some sense than LL/SC but both must be implemented by grabbing exclusive access over a cache line (maybe two in the case of double-word, I suppose). The underlying mechanics are the same.
|
|||||||||||||