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

Groups > comp.programming.threads > #667

Re: Locking primitives in userspace

Show key headers only | View raw

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.




Steve Thompson

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