[Ecls-list] Mutex & fairness

[Daniel Herring]

On Sun, 25 Mar 2012, Juan Jose Garcia-Ripoll wrote:

> Working further on the userspace implementation locks, I realized that it is hard to come up with an implementation that is both fast and fair, understanding by the last concept the fact that all threads have more or less the same
> chances to acquire a lock. POSIX threads seem to acomplish this nicely, at least on OS X, but they can afford some collaboration with the OS scheduler that we do not have.
> So far the trick that works best at this seems to be a trivial change: before acquiring a lock, verify whether the lock wait queue is empty or not. If it is not empty, queue its own process and wait. This has the disadvantage that a
> thread that might be ready might not end up using the resource which is locked.
> 
> So my question is to what extend is fairness something that has to be implemented by the operating system or by the user him/herself? Is it something that has to be contemplated at the application level?

My opinion:  Fairness should be optional.  In some situations, there are 
good reasons to trade fairness for performance.

That said, it can be very hard to implement fairness on unfair constructs.

Thus, I believe a high-quality implementation provides both.

Probably not the answer you were looking for.  Users can be demanding.  ;)

I would recommend trying for an implementation that is approximately fair. 
If it is fast enough, there will be little demand for an unfair 
implementation.  If there are cases where it is unfair for a transient but 
no thread is systematically ignored, then there will be little demand for 
a fairer implementation.  Such an implementation may be mythical, but it 
seems like a good objective.

Here are some thoughts to make a fair lock fast:  Quickly detect and take 
the fast path (atomics to bypass all locking).  Minimize the cost of 
queuing.  Balance polling between CPU use and wasted time (possibly 
user-selectable balance for each lock?).  Quickly detect and wake the 
first fair thread.

Practically speaking, how important is improved locking with relation to 
your other ECL tasks?

Hope that helps,
Daniel