Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Steve Thompson Newsgroups: comp.programming.threads Subject: Re: Locking primitives in userspace Date: Sun, 06 Nov 2011 06:54:37 -0500 Organization: A poorly organized news site. Lines: 74 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Injection-Info: mx04.eternal-september.org; posting-host="iyFSt7Y7BGsyUke8Uoi8DA"; logging-data="32106"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+Sv99o2i4M30ThDyVWVBxS" User-Agent: KNqde/0.10.9 Cancel-Lock: sha1:4NjgLRzjXXCVGOz6mEhymVp/2uc= Xref: x330-a1.tempe.blueboxinc.net comp.programming.threads:667 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