Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #661

Locking primitives in userspace

Show key headers only | View raw

I've been writing some multi-threaded code and have some question
about userspace locking primitives and best practices.

Firstly, I've written my own locking primitives, possibly for no other
reason than to be familiar with the low-level details.  I've read
Ulrich Drepper's paper[0] on "fast userspace mutexes", which discusses
the kernel futex facility and considered the pthread_mutex_* calls
which one might use.  There are also POSIX semaphores.

Obviously, I would normally prefer to avoid context switching as much as
possible, and it seems that doing it with hand-written code is the way
to go with that constraint in mind.  Mind you, I'm still in the early
stage of figuring out how I will organize threaded applications, so
nothing is fixed in stone.

My code uses an atomic inc instruction to increment a 32 bit quantity
and checks to see whether the value is what is expected.  If the value
is greater than one, the code knows there is contention and backs off
for a short delay before trying again.  I've dubbed this thing a
semaphore, although it is nothing like a POSIX semaphore.  On top of
this primitive, I have written 'read' and 'write' lock methods.  Write
locks are completely exclusive while read locks exclude only writers,
however the read-lock methods are biased to defer to waiting writers.

This seems to satisfy my general requirements, and it should be fast
because I can control how many times a waiting process will spin on the
semaphore primitive, and the duration that the thread might
nanosleep() if the lock is tied up for a long time by another
process.  Note I've said "process" instead of thread since these locks
ought to work to synchronize both inter-thread and inter-process data
if instantiated in a shared memory segment.  Of course, I don't get
any help from the scheduler this way, and at some point I guess I'll
have data on just how much this matters to an application.

I am interested in comments on this scheme and invite any criticisms
regarding portability or performance that might arise by my avoidance
of operating system-provided locking primitives.

Another issue floating around in the back of my mind concerns hardware
cache-line synchronization in multi-core systems.  My understanding is
that (at least on x86), the 'lock' prefix causes the processor to
share the relevant cache line with all processors in the system in
some way.  I'm not clear on how this works, but I assume there is some
magic that causes memory access delay only in circumstances where two
cores are holding the same cache line because a lock is contended
between threads.

Further reading suggests this is even more critical on NUMA
architectures.  So, if I have a bunch of locks spread throughout an
application, should they be scattered through memory, or might it be
better to manage them as an array of cache-line sized objects?

My experience with x86 assembler is very limited, and the other
systems I've used prior were all much smaller.  Worse, I'm writing my
threaded code 'on spec' from available documentation and anticipate
difficulty proving the correctness of my design.  Any tips on how to
best go about verifying that everything works as intended?  Debugging
threaded applications looks as though it could be very difficult.


[0] http://people.redhat.com/drepper/futex.pdf




Steve Thompson

Back to comp.programming.threads | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Locking primitives in userspace Steve Thompson <thomps2048@yahoo.ca> - 2011-10-30 16:26 -0400
  Re: Locking primitives in userspace Steve Thompson <thomps2048@yahoo.ca> - 2011-11-06 06:54 -0500
    Re: Locking primitives in userspace Mark <i@dontgetlotsofspamanymore.invalid> - 2011-11-07 11:42 +0000
      Re: Locking primitives in userspace Steve Thompson <thomps2048@yahoo.ca> - 2011-11-10 09:42 -0500
  Re: Locking primitives in userspace Alexander Terekhov <terekhov@web.de> - 2011-11-08 08:30 +0100

csiph-web