Introduction
The Reader-Writer-Lock mechanism is used to synchronize access to a resource. At any given time, it allows either concurrent read access for multiple threads, or write access for a single thread. In a situation where a resource is changed infrequently, Reader-Writer-Lock provides better throughput than a simple one-at-a-time lock, such as CriticalSection or Mutex.
Background
The System.Threading.ReaderWriterLock class in the .NET Framework provides a new synchronization method that Win32 doesn't. If you have never heard about the concept of Reader-Writer locks, then the .NET document is a good place for you. Following is my summary on the features of the ReaderWriterLock implemented in the .NET Framework:
ReaderWriterLock is used to synchronize access to a resource. At any given time, it allows either concurrent read access for multiple threads, or write access for a single thread. - The class works best where most accesses are reads, while writes are infrequent and of short duration. In such situations, a
ReaderWriterLock provides better throughput than a simple one-at-a-time lock, such as CriticalSection or Mutex.
- While a writer is waiting for active reader locks to be released, threads requesting new reader locks will have to wait in the reader queue. Their requests are not granted, even though they could share concurrent access with existing reader-lock holders; this helps protect writers against indefinite blockage by readers.
- Supports reentrance (allows call to
AcquireReaderLock/AcquireWriterLock multiple times in the same thread) and lock escalation (UpgradeToWriterLock when being a reader).
The C++ Reader-Writer-Lock Classes
My implementation of the Reader-Writer-Lock mechanism has all the characteristics of the .NET class except "lock cookie". Moreover, there are two classes in this implementation: each of them has its own convenience (and inconvenience of course). Following are the brief descriptions of their considerable methods:
CReaderWriterLockNonReentrance
AcquireReaderLock |
Acquires the reader lock. When calling this method, be sure that the calling thread has not owned any lock (reader or writer) yet; otherwise deadlock might happen. |
ReleaseReaderLock |
Releases the reader lock. When calling this method, be sure that the calling thread has already owned the reader lock; otherwise the object's behavior is undefined. |
AcquireWriterLock |
Acquires the writer lock. When calling this method, be sure that the calling thread has not owned any lock (reader or writer) yet; otherwise deadlock might happen. |
ReleaseWriterLock |
Releases the writer lock. When calling this method, be sure that the calling thread has already owned the writer lock; otherwise the object's behavior is undefined. |
DowngradeFromWriterLock |
Releases the writer lock and acquires reader lock in an atomic operation. When calling this method, be sure that the calling thread has already owned the writer lock; otherwise the object's behavior is undefined. |
UpgradeToWriterLock |
Releases the reader lock and acquires the writer lock. If "timeout" occurs, this method will automatically re-acquire the reader lock before it returns. In other words: if "upgrade" is failed due to "timeout", the calling thread still holds (owns) the reader lock. When calling this method, be sure that the thread has already owned the reader lock; otherwise the object's behavior is undefined.
IMPORTANT: If "timeout" != 0, other threads might write to the resource before this method returns regardless of whether the calling thread is upgraded successfully or not.
|
The demo project (attached with this article) also shows a non-intended behavior of the CReaderWriterLockNonReentrance class (call AcquireXXX in a thread then call ReleaseXXX in another thread). Although the non-intended feature is not recommended, it is very useful in some situations; let's use it with care.
CReaderWriterLock
AcquireReaderLock |
A thread can call AcquireReaderLock multiple times, which increments the reader lock counter each time. You must call ReleaseReaderLock once for each time you call AcquireReaderLock. Alternatively, you can call ReleaseAllLocks to reduce the lock count to zero immediately.
NOTE: A reader lock request is always granted immediately when one of the following two conditions is satisfied:
a) Current thread already owned the writer lock; this is to prevent a thread from blocking on itself.
b) Current thread already owned the reader lock (support recursive lock) |
ReleaseReaderLock |
Decrements the reader lock counter. When the counter reaches zero, the lock is released. When calling this method, be sure that the calling thread already owned the reader lock; otherwise exception will be raised in DEBUG mode. |
AcquireWriterLock |
A thread can call AcquireWriterLock multiple times, which increments the writer lock counter each time. You must call ReleaseWriterLock once for each time you call AcquireWriterLock. Alternatively, you can call ReleaseAllLocks to reduce the lock count to zero immediately.
NOTE:
a) To prevent a thread from blocking on itself, a writer lock request is always granted immediately when current thread already owned the writer lock.
b) If calling thread already owned the reader but not the writer lock, it will be "upgraded" to own the writer lock implicitly.
IMPORTANT: If an implicit "upgrade" was made and "timeout" != 0, other threads might write to the resource before this method returns regardless whether the calling thread is upgraded successfully or not.
|
ReleaseWriterLock |
Decrements the writer lock counter. When the counter reaches zero, the lock is released. When calling this method, be sure that the calling thread already owned the writer lock; otherwise exception will be raised in DEBUG mode.
NOTE: If the object detects that this request is corresponding to a previous auto-upgrade, it will also downgrade automatically (releases writer lock but still keep reader lock). |
ReleaseAllLocks |
Resets all lock counters (writer and reader counters) of calling thread to zero and releases both the writer & the reader lock regardless of how many times the thread owned reader or writer locks.
NOTE: After which, any call to ReleaseWriterLock or ReleaseReaderLock will raise an exception in DEBUG mode. |
GetCurrentThreadStatus |
Retrieves lock counters (both reader & writer counters) of calling thread. |
As someone may notice, there is neither "upgrade" nor "downgrade" method as in the CReaderWriterLockNonReentrance class. Actually, we don't need these methods since these actions ("upgrade" or "downgrade") will be done implicitly and automatically.
Some Helper Classes
CAutoReadLock(T) and CAutoWriteLock(T) would let a thread acquire a lock in a body of code, and not have to worry about explicitly releasing that lock if an exception is encountered in that piece of code or if there are multiple return points out of that piece.
Internal Implementation & Efficiency
In this implementation, each Reader-Writer-Lock object consists of three synchronization objects:
- A
CriticalSection object. This object is needed to guard all the other members so that manipulating them can be accomplished atomically. Internally, a CriticalSection object is a block of memory (24 bytes) plus a kernel event object (use the CreateEvent function). See "Break Free of Code Deadlocks in Critical Sections Under Windows" to understand why I said that. The event object is dynamically created on demand if there is more than one thread waiting on a CriticalSection object. If a critical section code is very small (enters and then leaves in a very short time), the event object will almost never be created. That explains why a CriticalSection is the fastest synchronization method in Win32. Taking a look at the source code, you would see that my implementation satisfies this condition � the code inside each critical section is very small/short. As a result, the event object will almost never be created.
- A manual�reset event object. This object is dynamically created when new readers have to wait until there is no writer on the
Reader-Writer-Lock object. This event object will be automatically deleted to save system resources when no longer needed. This event object plays the role of what the .NET team calls a "reader queue."
- An auto-reset event object. This object is dynamically created when new writers have to wait until the
Reader-Writer-Lock object is not locked by any active thread (readers or a writer). It will also be automatically deleted to save system resources when no longer needed. This event object plays the role of what the .NET team calls a "writer queue."
To summarise, when using the classes in a right way (multiple readers, almost no writer), a Reader-Writer-Lock object almost doesn't use any kernel object, and reader threads almost never do WaitForXXX operations. This algorithm determines the efficiency of my implementation: fast, and consumes very little kernel resource. "Consume very little kernel resource" will be a great feature in case you need many Reader-Writer-Lock objects in your application at the same time.
Discussion
In comparison to the CReaderWriterLockNonReentrance class, the CReaderWriterLock one is easier to use and end-users (developers) don't have to worry about deadlock as with the non-reentrance version. However the non-reentrance version is faster and more efficient in memory usage: it doesn't have a hash-table to maintain a counter for each thread so it avoids the overhead of dynamic memory allocation. Naturally, a common question will occur in our mind: which one should we use? It's not easy to answer this question and what follows are just my own thoughts:
- If your team members (colleagues) didn't spend enough time with multi-threading & synchronization then
CriticalSection & Mutex is a good choice to reduce the risk of wrong usage.
- If concurrence and high-speech are essential, an experienced person would prefer the non-reentrance version (
CReaderWriterLockNonReentrance) because he/she could control everything.
- If concurrence and high-speech are essential but reentrance problem is very hard to avoid,
the CReaderWriterLock one seems to be a must. In this case, consider replacing the STL map class by a more appropriate one to reduce overhead of dynamic memory allocation. For your reference, I would like to introduce the article "A Custom Block Allocator for Speeding Up VC++ STL" by Joaqu�n M L�pez Mu�oz which could be integrated into this library just in few minutes, but I left this task for you to keep my source code simple.
- If you don't want to waste a
CriticalSection object, consider using Spin Lock to replace it.
History
- Oct-17-2007: Version 2.0
- Timeout supported
- In the class
CReaderWriterLockNonReentrance, renamed the method ReleaseReaderAndAcquireWriterLock to UpgradeToWriterLock
- Jan-14-2007: Version 1.2
- Revised some methods to make code inside the Critical Section to be as short as possible
- Added more methods into
CReaderWriterLock class for convenience
- Last but most important,
CReaderWriterLockNonReentrance has been revised deeply to make it more usable in real work than in the previous version
- Feb-28-2006: Version 1.1
- Changed the license to "Lesser General Public License" (thanks to Mitchel Haas)
- Added support for non-MFC projects by re-defining the
ASSERT and VERIFY macros
- Added some helper classes,
CAutoReadLock and CAutoWriteLock (thanks to Andy318)
- Modified the demo project to show a non-intended behavior of the
CReaderWriterLockNonReentrance class
- Feb-01-2006: Version 1.0
