[Ecls-list] Mutex & fairness

[Juan Jose Garcia-Ripoll]

On Tue, Mar 27, 2012 at 2:41 PM, Daniel Herring <dherring at tentpost.com>wrote:

> Here are some thoughts to make a fair lock fast:  Quickly detect and take
> the fast path (atomics to bypass all locking).
>

This is already throughout ECL's code. Atomics have been incorporated via
libatomics and their intelligent headers that expand to assembly code


>  Minimize the cost of queuing.
>

This is much harder. Queueing currently costs memory and may involve the
garbage collector. I originally thought that this could be done at no cost,
for each process should at most be on a single queue, but the fact that we
have interrupts means that a waiting process may be interrupted and try to
wait on a different object.


> Balance polling between CPU use and wasted time (possibly user-selectable
> balance for each lock?).
>

This is tricky. Ideally we should not need any polling at all. The only
reason for polling to exist is because we do not have a portable
implementation of a wait queue, such as C++'s new eventcount. In other
words, we the slow path looks like

1* try to atomically lock
2* enter some brief waiting period which stops on interrupts

because the signal might be delivered between 1 and 2 and get lost. A
possible solution passes through masking the interrupts before 1* and using
pthread_sigwait() for 2*, but this gets tricky.


> Quickly detect and wake the first fair thread.
>

FIFO should be fair enough, I believe. I do not want to enter in to the
considerations of RT threads :)


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

This is not about improvements, but it is a blocking issue. I have realized
that the existing POSIX implementations does not work with Common Lisp
users's expectations on interrupts. It is simply impossible to have a
thread accept interrupts and at the same time use mutexes, because POSIX
threads have no way to query whether a mutex is locked or not and
pthread_mutex_lock() does not provide a path for existing on the arrival of
a signal. In practive this leads to a very fair (works nicely with the
scheduler) but very unstable implementation.

Juanjo

-- 
Instituto de Física Fundamental, CSIC
c/ Serrano, 113b, Madrid 28006 (Spain)
http://juanjose.garciaripoll.googlepages.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/ecl-devel/attachments/20120327/ab5f0948/attachment.html>