[Ecls-list] Locking strategy (best so far)

Juan Jose Garcia-Ripoll juanjose.garciaripoll at googlemail.com
Thu Mar 29 15:57:09 UTC 2012

This seems to be a good compromise, using the underlying operating system
for waiting and signaling and using a fast atomic path for detecting the
lock-free case. First the simple mutex

mp_get_lock_wait(cl_object lock)
if (ecl_atomic_queue_list(lock) != Cnil ||
    mp_get_lock_nowait(lock) == Cnil) {
 ecl_wait_on(get_lock_inner, lock);
@(return Ct)

Note that the first part of the conditional is what makes this a fair
implementation: if there are others waiting, we respect their precedence.
The nowait locking is very simple as well

static cl_object
get_lock_inner(cl_env_ptr env, cl_object lock)
cl_object output;
cl_object own_process = env->own_process;
        if (AO_compare_and_swap_full((AO_t*)&(lock->lock.owner),
     (AO_t)Cnil, (AO_t)own_process)) {
 lock->lock.counter = 1;
output = Ct;
print_lock("acquiring\t", lock, lock);
 } else  [...]
return output;

Now comes the hard part, which is waiting for the lock (or condition
variable or semaphore) to change. Apart from the polling version which is
in CVS, I came up with this other version which relies on POSIX signals and
seems to work reasonably fast -- at least as fast as the POSIX mutexes on
the same platform.

ecl_wait_on(cl_object (*condition)(cl_env_ptr, cl_object), cl_object o)
const cl_env_ptr the_env = ecl_process_env();
 volatile cl_object own_process = the_env->own_process;
volatile cl_object record;
 volatile sigset_t original;

/* 0) We reserve a record for the queue. In order to a void
 * using the garbage collector, we reuse records */
record = own_process->process.queue_record;
 unlikely_if (record == Cnil) {
record = ecl_list1(own_process);
} else {
 own_process->process.queue_record = Cnil;

/* 1) First we block all signals. */
sigset_t empty;
 pthread_sigmask(SIG_SETMASK, &original, &empty);

 /* 2) Now we add ourselves to the queue. In order to avoid a
 * call to the GC, we try to reuse records. */
 ecl_atomic_queue_nconc(the_env, o->lock.queue_list, record);
own_process->process.waiting_for = o;

/* 3) At this point we may receive signals, but we
 * might have missed a wakeup event if that happened
 * between 0) and 2), which is why we start with the
 * check*/
cl_object queue = ECL_CONS_CDR(o->lock.queue_list);
if (ECL_CONS_CAR(queue) != own_process ||
    condition(the_env, o) == Cnil)
do {
 /* This will wait until we get a signal that
 * demands some code being executed. Note that
 * this includes our communication signals and
 * the signals used by the GC. Note also that
 * as a consequence we might throw / return
 * which is why need to protect it all with
} while (condition(the_env, o) == Cnil);
/* 4) At this point we wrap up. We remove ourselves
   from the queue and restore signals, which were */
own_process->process.waiting_for = Cnil;
 ecl_atomic_queue_delete(the_env, o->lock.queue_list, own_process);
own_process->process.queue_record = record;
 ECL_RPLACD(record, Cnil);
pthread_sigmask(SIG_SETMASK, NULL, &original);

I am now working on small optimizations of this code and further testing. I
believe the same code can be used for Windows, because there we use a type
of signals that are not delivered until the code enters some specific
functions. Thus we could get rid of pthread_sigmask() (which do not exist
in Windows) and just replace sigsuspend() with a simple SleepEx().


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

More information about the ecl-devel mailing list