Expand description
A simple mutex implementation.
Differently from super::Mutex, this implementation does not require pinning, so the
ergonomics are much improved, though the implementation is not as feature-rich as the C-based
one. The main advantage is that it doesn’t impose unsafe blocks on callers.
The mutex is made up of 2 words in addition to the data it protects. The first one is accessed concurrently by threads trying to acquire and release the mutex, it contains a “stack” of waiters and a “locked” bit; the second one is only accessible by the thread holding the mutex, it contains a queue of waiters. Waiters are moved from the stack to the queue when the mutex is next unlocked while the stack is non-empty and the queue is empty. A single waiter is popped from the wait queue when the owner of the mutex unlocks it.
The initial state of the mutex is <locked=0, stack=[], queue=[]>, meaning that it isn’t
locked and both the waiter stack and queue are empty.
A lock operation transitions the mutex to state <locked=1, stack=[], queue=[]>.
An unlock operation transitions the mutex back to the initial state, however, an attempt to
lock the mutex while it’s already locked results in a waiter being created (on the stack) and
pushed onto the stack, so the state is <locked=1, stack=[W1], queue=[]>.
Another thread trying to lock the mutex results in another waiter being pushed onto the stack,
so the state becomes <locked=1, stack=[W2, W1], queue=[]>.
In such states (queue is empty but stack is non-empty), the unlock operation is performed in three steps:
- The stack is popped (but the mutex remains locked), so the state is:
<locked=1, stack=[], queue=[]> - The stack is turned into a queue by reversing it, so the state is: `<locked=1, stack=[], queue=[W1, W2]>
- Finally, the lock is released, and the first waiter is awakened, so the state is:
<locked=0, stack=[], queue=[W2]>
The mutex remains accessible to any threads attempting to lock it in any of the intermediate states above. For example, while it is locked, other threads may add waiters to the stack (which is ok because we want to release the ones on the queue first); another example is that another thread may acquire the mutex before waiter W1 in the example above, this makes the mutex unfair but this is desirable because the thread is running already and may in fact release the lock before W1 manages to get scheduled – it also mitigates the lock convoy problem when the releasing thread wants to immediately acquire the lock again: it will be allowed to do so (as long as W1 doesn’t get to it first).
When the waiter queue is non-empty, unlocking the mutex always results in the first waiter being popped form the queue and awakened.