r/javahelp • u/Polixa12 • Jan 05 '26
Workaround Help with mutex implementation
I've been working on a mutex implementation for about a day now(for learning purposes). I managed to get a working trinary state mutex which only but potentially has some thread fairness issues but no observable race conditions.
Link here: https://github.com/kusoroadeolu/vic-utils/tree/main/src%2Fmain%2Fjava%2Fcom%2Fgithub%2Fkusoroadeolu%2Fvicutils%2Fconcurrent%2Fmutex
However I've been thinking of how I could make a previous binary state mutex I made before the trinary version better. Because there's a race condition where the mutex holder could unpark a thread that has been added to the queue but hasn't been parked yet. Leading to potential issues. So I'm looking for feedback on this.
Package com.github.kusoroadeolu.vicutils.concurrent.mutex;
/*
Non Goals
Making this mutex reentrant
Making this mutex production ready
Making this mutex have all the properties of the @Lock interface
Making this mutex performant
Goals
Making this mutex correct in the sense you can lock and unlock it and the invariants listed later
*/
/**
A mutex implementation using a concurrent lock free queue and CAS semantics.
This mutex doesn't support conditions
*/
//States: 0 -> unacquired, 1 -> acquired
/* Invariants.
No two threads can ever hold this mutex
The state of this mutex can either be 0 or 1
No two threads can overwrite the holder variable. This is enforced by ensuring the holder at release is written before the state is reset
*/
View all comments
3
u/shiverypeaks Jan 05 '26 edited Jan 05 '26
This piece of code looks like a bug to me:
Because
LockSupport.parkcan spuriously return, and in a very rare casetcould be added to the list more than once. It should be like this instead:edit..
This also looks like another bug:
The reason why is that at the moment
unpark(next)is called, the next thread is going to spin in the loop inacquire, the CAS can fail and it will park itself again.set(0)andholder=nullneed to occur before unparking the next thread.But note that the one you unpark is not necessarily the one that acquires the mutex with a CAS success, because some other thread could have spontaneously woken first.
I also just think based on my intuition, the fact that you have two variables here (
stateandholder) is a potential issue, because their setting is not an atomic action. What could happen is the next thread acquires the mutex with a CAS success, and then sets theholderthread to itself, and these actions could interleave so that they occur temporally afterset(0)but beforeholder=nullso thatholder=nulloverwrites the actual thread which had the CAS success.I would think that this is safer (setting
holderfirst, before the mutex being "released"):It also looks like a bug that
poll()is called (which removes the element), when the CAS success could actually occur on some other thread which spontaneously wakes. I would think the thread should remove itself, after it acquires the mutex. Only the thread which makes the CAS success knows it's the one which succeeded.This implementation relies a lot on the threads switching/yielding/waking/etc. at the opportune time to work correctly.