search

Tracktion / choc

A collection of header only classes, permissively licensed, to provide basic useful tasks with the bare-minimum of dependencies.
Other
529 stars 47 forks source link

no mutex ≠ lock-free #11

Closed lfnoise closed 1 year ago

lfnoise commented 1 year ago

DirtyList::markAsDirty() is not lock-free because SingleReaderMultipleWriterFIFO::push() is not lock-free. Lock-free does not mean that you don't use a mutex, it means that there is no condition where all threads are blocked and none can make progress.

If thread A calls SingleReaderMultipleWriterFIFO::push(), locks the SpinLock and is then suspended by the thread scheduler to switch to thread B, which then also calls SingleReaderMultipleWriterFIFO::push(), both threads will be blocked for the as long as thread B is scheduled. If the thread scheduler then goes on to schedule thread C, which also tries to push the queue, then three threads are blocked on the SpinLock. And similarly for threads D and beyond. No threads are making progress. It doesn't matter that this is unlikely. If it can happen, it is not lock-free.

See https://preshing.com/20120612/an-introduction-to-lock-free-programming/

julianstorer commented 1 year ago

Yeah, I think you've misunderstood what this class is for, and that's my fault because don't explain it very well, and will improve that..

The main use for the class is to allow random threads to push work items into a fifo for an audio thread to process. So the single reader thread is real-time and lock-free, but the writers aren't. They can block each other very briefly, which is fine, but won't block the reader.

julianstorer commented 1 year ago

oh, hang on - you were talking about DirtyList, not SingleReaderMultipleWriterFIFO... Hmm, that's actually a fair point, because it could be called from a realtime thread. I'll take a look..

julianstorer commented 1 year ago

Right - I'm just going to clarify the docs to avoid anyone else nit-picking the same technicality, but don't think I'll change the code.

If there's only one thread calling markAsDirty() (which is how I was using the class) then it is lock-free.. You'd need to have multiple realtime threads all hammering markAsDirty() at the same time for the lock to actually ever get contested. Given that it's far from trivial to make the writing fully lock-free, then that's not something I'd want to spend time on when there's a chance nobody will ever need it.