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

Groups > comp.programming.threads > #669

Re: Locking primitives in userspace

Show all headers | View raw

On Sun, 06 Nov 2011 06:54:37 -0500, Steve Thompson
<thomps2048@yahoo.ca> wrote:

>On Sun, Oct 30, 2011 at 04:26:05PM -0400, Steve Thompson wrote:
>> 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
>> 
>
>No comments?  The implementation has interesting properties that I was
>looking forward to discussing, as well as any remarks concerning
>scalability or interactions with the scheduler.

Since no-one else has replied then I'll chip in.  I'm not an academic
so am not really interested in examining obscure locking mechanisms.
However I would avoid such features and would stick to POSIX thread
features since my code has to be portable.

Sorry I can't offer any real help ;-)
-- 
(\__/)  M.
(='.'=) Due to the amount of spam posted via googlegroups and
(")_(") their inaction to the problem. I am blocking some articles
posted from there.  If you wish your postings to be seen by
everyone you will need use a different method of posting.

Back to comp.programming.threads | Previous | Next — Previous in thread | 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