TheOneManyLock Class

I have created my own reader-writer construct that is faster than the FCL’s ReaderWriterLockSlim class.4 My class is called OneManyLock because it allows access to either one writer thread or many reader threads. The class basically looks like this.

public sealed class OneManyLock : IDisposable { public OneManyLock();

public void Dispose();

public void Enter(Boolean exclusive); public void Leave();

}

Now I’d like to give you a sense of how it works. Internally, the class has an Int32 field for the state of the lock, a Semaphore object that reader threads block on, and an AutoResetEvent object that writer threads block on. The Int64 state field is divided into five subfields as follows:

■ Four bits represent the state of the lock itself. The possibilities are 0=Free, 1=OwnedByWriter, 2=OwnedByReaders, 3=OwnedByReadersAndWriterPending, and 4=ReservedForWriter. The other values are not used.

■ Twenty bits (a number from 0 to 1,048,575) represent the number of reader threads reading (RR) that the lock has currently allowed in.

■ Twenty bits represent the number of reader threads waiting (RW) to get into the lock. These threads block on the auto-reset event object.

4 The code is inside the Ch30-1-HybridThreadSync.cs file that is part of the code that accompanies this book. You can

download this code from http://Wintellect.com/Books.

■ Twenty bits represent the number of writer threads waiting (WW) to get into the lock. These threads block on the other semaphore object.

Now, because all the information about the lock fits in a single Int64 field, I can manipulate this field by using the methods of the Interlocked class so the lock is incredibly fast and causes a thread to block only when there is contention.

Here’s what happens when a thread enters the lock for shared access.

■ If the lock is Free: Set state to OwnedByReaders, RR=1, Return.

■ If the lock is OwnedByReaders: RR++, Return.

■ Else: RW++, Block reader thread. When the thread wakes, loop around and try again.

Here’s what happens when a thread that has shared access leaves the lock.

■ RR--

■ If RR > 0: Return

■ If WW > 0: Set state to ReservedForWriter, WW--, Release 1 blocked writer thread, Return

■ If RW == 0 && WW == 0: Set state to Free, Return

Here’s what happens when a thread enters the lock for exclusive access:

■ If the lock is Free: Set state to OwnedByWriter, Return.

■ If the lock is ReservedForWriter: Set state to OwnedByWriter, Return.

■ If the lock is OwnedByWriter: WW++, Block writer thread. When thread wakes, loop around and try again.

■ Else: Set state to OwnedByReadersAndWriterPending, WW++, Block writer thread. When thread wakes, loop around and try again.

Here’s what happens when a thread that has exclusive access leaves the lock:

■ If WW == 0 && RW == 0: Set state to Free, Return

■ If WW > 0: Set state to ReservedForWriter, WW--, Release 1 blocked writer thread, Return

■ If WW == 0 && RW > 0: Set state to Free , RW=0, Wake all blocked reader threads, Return Let’s say that there is currently one thread reading from the lock and another thread wants to

enter the lock for writing. The writer thread will first check to see if the lock is Free, and because it is not, the thread will advance to perform the next check. However, at this point, the reader thread could leave the lock, and seeing that RR and WW are both 0, the thread could set the lock’s state to

Free. This is a problem because the writer thread has already performed this test and moved on. Basi- cally what happened is that the reader thread changed the state that the writer thread was accessing behind its back. I needed to solve this problem so that the lock would function correctly.

To solve the problem, all of these bit manipulations are performed using the technique I showed in the “The Interlocked Anything Pattern” section from Chapter 29. If you recall, this pattern lets you turn any operation into a thread-safe atomic operation. This is what allows this lock to be so fast and have less state in it than other reader-writer locks. When I run performance tests comparing my OneManyLock against the FCL’s ReaderWriterLockSlim and ReaderWriterLock classes, I get the following results.

Incrementing x in OneManyLock: 330 Fastest Incrementing x in ReaderWriterLockSlim: 554 ~1.7x slower Incrementing x in ReaderWriterLock: 984 ~3x slower

Of course, because all reader-writer locks perform more logic than a mutually exclusive lock, their performance can be slightly worse. However, you have to weigh this against the fact that a reader- writer lock allows multiple readers into the lock simultaneously.

Before leaving this section, I’ll also mention that my Power Threading library (downloadable for free from http://Wintellect.com/PowerThreading.aspx) offers a slightly different version of this lock, called OneManyResourceLock. This lock and others in the library offer many additional features, such as deadlock detection, the ability to turn on lock ownership and recursion (albeit at a performance cost), a unified programming model for all locks, and the ability to observe the run-time behavior of the locks. For observing behavior, you can see the maximum amount of time that a thread ever waited to acquire a lock, and you can see the minimum and maximum amount of time that a lock was held.

Date: 2016-03-03; view: 891