| Weekly edition | Kernel | Security | Distributions | Search |
| Archives | Calendar | Subscribe | Write for LWN | LWN.net FAQ |
The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services
The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services
Posted Feb 21, 2008 19:03 UTC (Thu) by bronson (subscriber, #4806)Parent article: KHB: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services
I played around with lock-free algorithms a year ago and came away with a rather dim view of them. It's easy to write a provably correct lock-free queue when you assume infinite memory (something that most papers seem to do). It's a lot messier when you need to ensure the safe disposal of list items when you're done with them. You mention he's using an atomic CAS. Does he explicitly solve CAS's ABBA problem? It's easily solved if you assume infinite memory of course. If you're on a real-world system, if you're not careful, you can easily open yourself up to situations where CAS assures you that a value is unchanged when in reality you lost out a long time ago and the ring has just wrapped. (yes, it's not hard to solve if you're watching for it, but always having to worry about this sort of subtlety is what makes working lock-free such a pain) After realizing they were anything but maintainable, I chucked lock-free algorithms on my shelf of stuff that is academically fascinating but unrealistic for the real world. Should I take them back down and re-examine them? > When the callback for queue empty happens, the code to operate on the queue is switched to use the lock-free synchronization code. When the quaject's queue-not-empty callback is invoked, the quajects switch back to the synchronization-free code. Whoa... that ran shivers down my spine. What an outrageously cool idea.
(Log in to post comments)
The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services
Posted Feb 21, 2008 21:42 UTC (Thu) by valhenson (subscriber, #38407) [Link]
> After realizing they were anything but maintainable, I chucked lock-free algorithms on my > shelf of stuff that is academically fascinating but unrealistic for the real world. Should I > take them back down and re-examine them? My personal opinion is that lock-free algorithms are not a good generic synchronization technique, and are definitely very very complex and difficult to understand. However, in certain specific cases, lock-free can be simple, elegant, and a huge performance advantage over traditional approaches. It's much like RCU - you wouldn't want to use RCU for every synchronization problem, but when it comes to highly-shared read-mostly data in the hot path (e.g., the dcache), it's worth the trouble. It's kind of like my advice on choosing a file system: Use ext3 unless it's not fast/big/whatever enough for you, in which case use XFS. My recommendation is use locks unless they have too much contention/complexity/whatever, in which case look into lock-free. > > When the callback for queue empty happens, the code to operate on the queue is switched to > > use the lock-free synchronization code. When the quaject's queue-not-empty callback is > > invoked, the quajects switch back to the synchronization-free code. > > Whoa... that ran shivers down my spine. What an outrageously cool idea. I know... The whole damn dissertation is like that.
The Kernel Hacker's Bookshelf: Synthesis: An Efficient Implementation of Fundamental Operating Systems Services
Posted Feb 28, 2008 19:11 UTC (Thu) by renox (guest, #23785) [Link]
>> When the callback for queue empty happens, the code to operate on the queue is switched to use the lock-free synchronization code. When the quaject's queue-not-empty callback is invoked, the quajects switch back to the synchronization-free code. > >Whoa... that ran shivers down my spine. What an outrageously cool idea. Uh? I don't think that it's a particulary original idea.. But implementing this efficiently on the other hand, this seems quite hard to do! I have some difficulties downloading the PDF, so I cannot read the paper yet..