<div class="gmail_quote">On Tue, Mar 27, 2012 at 2:41 PM, Daniel Herring <span dir="ltr"><<a href="mailto:dherring@tentpost.com">dherring@tentpost.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">

<div id=":y1">Here are some thoughts to make a fair lock fast:  Quickly detect and take the fast path (atomics to bypass all locking).</div></blockquote><div><br></div><div>This is already throughout ECL's code. Atomics have been incorporated via libatomics and their intelligent headers that expand to assembly code</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div id=":y1">  Minimize the cost of queuing.</div></blockquote><div><br></div><div>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.</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div id=":y1">Balance polling between CPU use and wasted time (possibly user-selectable balance for each lock?).</div>

</blockquote><div><br></div><div>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</div>

<div><br></div><div>1* try to atomically lock</div><div>2* enter some brief waiting period which stops on interrupts</div><div><br></div><div>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.</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div id=":y1">Quickly detect and wake the first fair thread.<br></div></blockquote><div><br></div><div>FIFO should be fair enough, I believe. I do not want to enter in to the considerations of RT threads :)</div>

<div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div id=":y1">Practically speaking, how important is improved locking with relation to your other ECL tasks?<br>

</div></blockquote></div><br>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.<div>

<br></div><div>Juanjo<br clear="all"><div><br></div>-- <br>Instituto de Física Fundamental, CSIC<br>c/ Serrano, 113b, Madrid 28006 (Spain) <br><a href="http://juanjose.garciaripoll.googlepages.com" target="_blank">http://juanjose.garciaripoll.googlepages.com</a><br>


</div>