Read/write lock with reduced reader lock sampling overhead in absence of writer lock acquisition

An improved reader-writer locking for synchronizing access to shared data. When writing the shared data, a writer flag is set and a lock is acquired on the shared data. The shared data may be accessed following the expiration of a grace period and a determination that there are no data readers accessing the shared data. When reading the shared data, the writer flag is tested that indicates whether a data writer is attempting to access the shared data. If the writer flag is not set, the shared data is accessed using a relatively fast read mechanism. If the writer flag is set, the shared data is accessed using a relatively slow read mechanism.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to computer systems and methods in which data resources are shared among concurrent data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the invention concerns an implementation of a mutual exclusion mechanism known as “reader-writer synchronization.”

2. Description of the Prior Art

By way of background, reader-writer synchronization, also known as “reader-writer locking,” is a mutual exclusion technique that is suitable for use in shared memory multiprocessor computing environments to protect a set of shared data. This form of locking allows read operations (readers) to share lock access in order to facilitate parallel data reads, but requires write operations (writers) to obtain exclusive lock access for writing the data. The technique is well suited to shared memory multiprocessor computing environments in which the number of readers accessing a shared data set is large in comparison to the number of writers, and wherein the overhead cost of requiring serialized lock acquisition for readers would be high. For example, a network routing table that is updated at most once every few minutes but searched many thousands of times per second is a case where serialized read-side locking would be quite burdensome.

Reader-writer locks are conventionally implemented using either a single global lock that is shared among processors, or as a set of distributed per-processor locks. The global reader-writer lock approach is illustrated inFIG. 1. It requires readers and writers to contend for one global lock on an equal footing, but produces memory contention delays due to cache line bouncing of the lock between each processor's cache. Insofar as reader-writer locks are premised on the existence of a read-intensive processing environment, readers may be unduly penalized, especially if their critical sections are short and their lock acquisition frequency is high. The distributed reader-writer lock approach is illustrated inFIG. 2. It requires the readers to acquire only a local per-processor lock that will usually reside in the memory cache of the processor that hosts the acquiring reader. However, the writers must acquire all of the local locks, which degrades writer performance due to memory contention and in some cases due to new readers being allowed to starve a writer while the latter is waiting for one of the local locks.

A further disadvantage associated with either type of reader-writer locking is that lock acquisition imposes a burden on readers, even in the absence of a writer. Reader-writer locks are typically implemented as semaphores, mutex locks and spinlocks. Acquiring each of these lock types often imposes the cost of atomic instructions and/or memory barriers. In a read-mostly computing environment, the overhead associated with these operations falls mostly on readers.

It is to solving the foregoing problems that the present invention is directed. In particular, what is required is a reader-writer locking technique that is fair to writers yet which reduces the overhead associated with read-side lock acquisition.

SUMMARY OF THE INVENTION

The foregoing problems are solved and an advance in the art is obtained by a method, system and computer program product for implementing improved reader-writer locking for synchronizing access to shared data. When writing the shared data, a writer flag is set and a lock is acquired on the shared data. If desired, the lock acquisition can be effectuated by setting the writer flag. The shared data may be accessed following the expiration of a grace period and a determination that there are no data readers accessing the shared data. When reading the shared data, the writer flag is tested that indicates whether a data writer is attempting to access the shared data. If the writer flag is not set, the shared data is accessed using a relatively fast read mechanism. If the writer flag is set, the shared data is accessed using a relatively slow read mechanism.

The relatively fast read mechanism may comprise incrementing a reader reference counter prior to a data reader accessing the shared data, and decrementing the reader reference counter after the data reader accesses the shared data. The relatively slow read mechanism may comprise acquiring the lock prior to a data reader accessing the shared data and releasing the lock after the data reader accesses the shared data. If the writer flag is tested after the writer flag is set, the grace period will guarantee that a data reader will see the writer flag in a set condition. If the writer flag is tested before the writer flag is set, the grace period will guarantee that the incrementation or decrementation of the reader reference counter will complete prior to a determination being made that no data readers are accessing the shared.

DETAILED DESCRIPTION OF EXEMPLARY EMBODIMENTS

Turning now to the figures, wherein like reference numerals represent like elements in all of the several views,FIG. 3illustrates an exemplary computing environment in which the present invention may be implemented. In particular, a symmetrical multiprocessor (SMP) computing system2is shown in which multiple processors41,42. . .4nare connected by way of a common bus6to a shared memory8. Respectively associated with each processor41,42. . .4nis a conventional cache memory101,102. . .10nand a cache controller121,122. . .12n. A conventional memory controller14is associated with the shared memory8. The computing system2is assumed to be under the management of a single multitasking operating system adapted for use in an SMP environment. In the alternative, a single processor computing environment could be used to implement the invention, as could a hardware multithreading environment, a multi-core environment and a NUMA (Non-Uniform Memory Access) environment, to name but a few.

It is further assumed that data write operations executed within kernel or user mode processes, threads, or other execution contexts will periodically perform updates on a set of shared data16stored in the shared memory8. Reference numerals181,182. . .18nillustrate individual data write operations (writers) that may periodically execute on the several processors41,42. . .4n. The updates performed by the writers181,182. . .18ncan include modifying elements of a linked list, inserting new elements into the list, deleting elements from the list, and many other types of operations. Each of the processors41,42. . .4nalso periodically executes read operations (readers)211,212. . .21non the shared data16. Such read operations will typically be performed far more often than updates, insofar as this is one of the premises underlying the use of read-writer locks. To facilitate synchronized reader-writer access to the shared data16, the several processors41,42. . .4nare programmed to implement a read-writer locking (RWL) subsystem20, as by periodically executing respective RWL instances201,202. . .20nas part of their operating system or user application functions. For reasons which will be described in more detail below, the RWL subsystem20includes a grace period processing mechanism that can be invoked by the writers181,182. . .18nto ensure that their RWL operations are synchronized with counterpart RWL operations performed by the readers211,212. . .21n. The concept of a grace period is used extensively in a mutual exclusion technique known as “read-copy update.” In the context of the present disclosure, the expiration of a grace period represents the point at which a writer181,182. . .18ncan guarantee that all readers211,212. . .21nthat were executing prior to the writer have completed execution.

As shown inFIG. 4, the RWL subsystem20includes a set of primitives that serve as an RWL subsystem API (Application Program Interface) that can be called by the writers181,182. . .18nand the readers211,212. . .21nprior to and following critical section processing of the shared data16. These primitives comprise fast path read acquisition logic22A, fast path read release logic22B, slow path read acquisition logic24A, slow path read release logic24B, write acquisition logic26A and write release logic26B. The operations of these primitives are described in detail below. The RWL subsystem20also provides one or more instances of a writer flag28, a distributed set of per-processor reader reference counters30one or more instances of and a reader-writer (R/W) lock32. As stated above, the RWL subsystem20further includes grace period processing logic34.

The RWL subsystem20supports improved reader-writer locking by reducing the overhead normally associated with read-side lock acquisition, which as described by way of background above, typically require costly memory barriers and atomic instructions. The RWL subsystem20allows the readers211,212. . .21nto access the shared data16via one of two locking routes, referred to herein as fast path read processing and slow path read processing. Fast path read processing is performed when there are no writers currently accessing or waiting to access to the shared data16, as indicated by the writer flag28. This mode of read processing requires no memory barriers or atomic instructions, only that the readers211,212. . .21nmanipulate their local reader reference counter30. Such processing is illustrated inFIG. 5A, wherein each of the readers211,212. . .21nhave invoked the fast path read acquisition logic22A to read the writer flag28, determine that there are no writers present (e.g., the writer181), increment one of the local reader reference counters30, and read the shared data16. After completing their critical sections, the readers211,212. . .21nsimply invoke the fast path read release logic22B to decrement their local reader reference counter30.

If one of the writers181,182. . .18n(e.g., the writer181) desires to update the shared data16, it will invoke the write acquisition logic26A to set the writer flag28and acquire the R/W lock32. This condition is shown inFIG. 5B. Note that the writer flag28may itself be used as a write-side portion of the R/W lock32. In an alternative implementation, the writer181could be required to set the writer flag28and acquire the R/W lock32as a separate write-side lock entity. The write acquisition logic26A then invokes the grace period processing logic34to track a grace period that ensures the readers211,212. . .21nwill see the new write flag value. After the grace period has expired, the reader reference counters30are summed and tested for zero. As shown inFIG. 5C, once it is determined that a grace period has expired and the reader reference counters30have reached zero, the writer may enter its critical section and write the shared data16.

Only if the writer flag28is set will the readers perform conventional reader-writer locking. In particular, as shown inFIG. 5D, when the fast path read acquisition logic22A finds the writer flag28set, it invokes the slow path read acquisition logic24A, which requires the readers211,212. . .21nto acquire the R/W lock32. The R/W lock32will prevent the readers211,212. . .21nfrom reading the shared data16until the writer181has completed its critical section. As further shown inFIG. 5D, the slow path read acquisition logic24A may also optionally increment the reader reference counters30. Thereafter, when readers211,212. . .21nhave read the shared data16and leave their critical sections, the slow path read release logic24B will be called to release the R/W lock32. The reader reference counters will also be decremented if they were incremented by the slow path read acquisition logic24A, or by the fast path read acquisition logic22A in the event that a writer181,182. . .18nset the writer flag28while the counter was incremented (see below).

If desired, the writer flag28could be implemented as a distributed set of local per-processor variables, which can be advantageous for the readers211,212. . .21non NUMA systems. However, this requires more work for the writers181,182. . .18ndue to having to write each write flag instance. Implementing the writer flag28as a global variable in the manner described above resolves this issue and will not normally delay fast path read processing by the readers211,212. . .21n. This is due to the fact that the writer flag28will only be updated infrequently by the writers181,182. . .18n, such that its value will tend to stay localized in the cache memories101,102. . .10nas a result of conventional operations of the cache controllers121,122. . .12n. The reader reference counters30could potentially be implemented as a single global variable. However, because it is written during fast path read processing by the readers211,212. . .21ndelays in such processing can be minimized if the reader reference counter30is implemented as described above, namely, as a distributed set of per-processor local variables. As a result of conventional operations of the cache controllers121,122. . .12n, these local variables will tend to be maintained in each of the cache memories101,102. . .10nassociated with one of the readers211,212. . .21n. The R/W lock32could be implemented as a distributed set of local per-processor variables. However, this requires more work for the writers181,182. . .18ndue to having to manipulate each R/W lock instance. Implementing the R/W lock32as a single global variable resolves this issue and will not unduly impact the readers211,212. . .21nbecause they will normally use fast path read processing given the infrequency of write operations.

Details of an exemplary implementation of the foregoing reader-writer locking technique will now be described with reference toFIGS. 6-10B. As shown inFIG. 6, the R/W lock32may be implemented as a data structure that comprises several elements. By way of example only, these elements may include the writer flag28, an R/W spin lock (36) to protect the data structure, a reader wait queue (38) for queuing readers211,212. . .21nwaiting for the R/W lock32, and a writer wait queue (40) for queuing writers181,182. . .18nwaiting for the R/W lock. The writer flag28may be set to one of three values. A value of 0x0000 represents a NO_WRITERS state and means that the writer flag28is cleared. A value of 0x0001 represents a WRITER_WAITING state and means that the writer flag28is set because a writer is waiting for the R/W lock32. A value of 0x0002 represents a WRITER_ACTIVE state and means that the writer flag28is set because a writer owns the R/W lock32. It should be noted that the indicated values 0x0000, 0x0001 and 0x0002 are for the purpose of illustration only, and that other values may also be used to represent the state of the writer flag28.

FIG. 7illustrates exemplary processing that may be performed by the fast path read acquisition logic22A (blocks50-60) and the fast path read release logic22B (blocks64-74). In blocks50and52, preemption is disabled in order to prevent disruption of the read acquisition operation (which is relatively fast) and the writer flag28is tested to determine if any writers181,182. . .18nare present (i.e. whether the writer flag28is set due to either a WRITER_WAITING or WRITER_ACTIVE state). If the writer flag28is not set, the reader reference counter30associated with the current reader211,212. . .21nis incremented (block54) and preemption is re-enabled to restore normal preemptable operation (block56). If the writer flag28is set, preemption is re-enabled (block58) and the slow path read acquisition logic24A is invoked (block60). Following blocks56or60, the reader enters its critical section in block62and references the shared data16. The operations of blocks64-74are then performed in order to gracefully exit the reader critical section by decrementing the reader reference counter30that was incremented in block54or, if a writer is now present and requesting access to the shared data16, by invoking the slow patch read release logic24B. In blocks64and66, preemption is disabled and the writer flag28is tested to determine if any writers181,182. . .18nare present (i.e. whether the writer flag28is set due to either a WRITER_WAITING or WRITERS_ACTIVE state). If the writer flag28is not set, the reader reference counter30associated with the current reader211,212. . .21nis decremented (block68) and preemption is re-enabled (block70). If the writer flag28is set, preemption is re-enabled (block72) and the slow path read release logic24B is invoked (block74).

FIG. 8illustrates exemplary processing that may be performed by the slow path read acquisition logic24A (blocks80-98). In block80, the R/W spinlock36guarding the R/W lock32is acquired. In block82, a test is made to determine if the writer flag28is set to the WRITER_WAITING state, and if any reader reference counter30for other readers211,212. . .21nis incremented. If not, the current reader211,212. . .21nis added to the R/W lock's reader wait queue38(block84) and the R/W spinlock36is released (block86). In block88, the reader211,212. . .21nis rescheduled until the R/W lock32can be acquired for reading. When this occurs, the reader211,212. . .21nis removed form the R/W lock's reader wait queue38(block90) and the R/W spinlock36is again acquired (block92). In block94, the reader reference counter30associated with the current reader211,212. . .21nis incremented and the R/W spinlock36is released in block96. Block94is also reached if the test in block82produces a true result because there are writers181,182. . .18nin the WRITER_WAITING state and other readers211,212. . .21nwhose reader reference counter30is set. This condition is used as an invitation to resume fast path read acquisition processing, the idea being to favor the current reader211,212. . .21nover the waiting writer(s)181,182. . .18nby allowing the reader to join with the other readers that are already reading the shared data16. Note that this operation may tend to starve the waiting writer(s)181,182. . .18nand thus may not be desirable in all cases.

FIG. 9illustrates exemplary processing that may be performed by the slow path read release logic24B (blocks100-110). In blocks100and102, the R/W spinlock36guarding the R/W lock32is acquired and the reader reference counter30associated with the current reader211,212. . .21nis decremented (having been previously incremented in block96of the slow path read acquisition processing or in block54of the fast path read acquisition processing22A (the latter in the case where a writer181,182. . .18narrived after the reader performed the block54counter incrementation but before it tested the writer flag28in block66). In block104, a check is made to determine if there are any writers181,182. . .18nwaiting in the R/W writer wait queue40for the R/W lock32and if there are no other readers211,212. . .21nwho have incremented their reader reference counter30. If this condition holds true, the writer flag28is set to the WRITER_ACTIVE state (block106) and the next writer181,182. . .18nwaiting in the R/W writer wait queue40is awoken (block108). The R/W spinlock36is then released in block110. Block110is also reached if the test in block104returns false.

FIGS. 10A and 10Bcollectively illustrate exemplary processing that may be performed by the write acquisition logic26A (blocks120-148) and the write release logic26B (blocks150-160). In block120ofFIG. 10A, the R/W spinlock36guarding the R/W lock32is acquired. In block122, a test is made to determine if any writers181,182. . .18nare present (i.e. whether the writer flag28is set due to either a WRITER_WAITING or WRITERS_ACTIVE state). If not, the write flag28is set to the WRITER_WAITING state in block124and the R/W spinlock is released in block126. In block128, the grace period processing logic34is invoked to await the expiration of a grace period. The grace period guarantees that all new readers211,212. . .21ninvoked following the current write acquisition processing will see the changed status of the writer flag28and thereby allow them to perform slow path read acquisition processing. The grace period processing logic34thus effects a memory barrier that allows the updated writer flag28to be seen on all processors41,42. . .4nbefore the write acquisition logic26A proceeds. The grace period will also guarantee that older readers211,212. . .21ninvoked prior to the current write acquisition processing have finished incrementing or decrementing their reader reference counters30before the write acquisition logic26A proceeds. This represents a quiescent state in which the older readers211,212. . .21nwill have finished manipulating (incrementing or decrementing) their reader reference counters30. One mechanism that may be used to implement the grace period processing logic34is the “synchronize_sched( )” primitive provided by conventional read-copy update implementations. This primitive is designed for grace period processing to protect processes that run non-preemptively (e.g., with preemption disabled), which is the case for the fast path read acquisition logic22A and the fast path read release logic22B. Following the expiration of a grace period in block128, the R/W spinlock36is acquired in block130and a test is made in block132to determine if the reader reference counters30are all zero. If they are, the writer flag28is set to the WRITER_ACTIVE state (block134), and the R/W spinlock is released (block136). The block134operation effects acquisition of the R/W lock32by the current writer181,182. . .18n. The writer181,182. . .18nmay then enter its critical section to write the shared data16in block138.

If it is determined in block122that there are other writers present, or if the reader reference counters36are not zero in block132, block140is implemented and the current writer181,182. . .18nis added to the R/W lock's writer wait queue40. After the R/W spinlock36is released (block142), the writer is rescheduled until the R/W lock32can be acquired for writing (block144) and the writer181,182. . .18nis removed from the R/W lock's writer wait queue40(block146).

In block148ofFIG. 10B, the R/W spinlock36is acquired and in block150the R/W lock's writer wait queue40is checked for waiting writers. If there are none, the writer flag28is placed in the NO_WRITERS state (block152) and the next reader211,212. . .21non the R/W reader wait queue38, if present, is woken up (block154). The R/W spinlock36is then released in block156. If there are writers181,182. . .18nwaiting on the writer wait queue40in block150, the next writer on this queue is woken up (block158) and the R/W spinlock is released (block156).

In a variation of the foregoing reader-writer locking technique, provision can be made for the readers211,212. . .21nto read the shared data16recursively. By way of example, a recursive read operation can arise when nested data structures are accessed (e.g., an RWL-protected list pointed to by another RWL-protected list). Another scenario is when an interrupt occurs while a process is performing a read operation on RWL-protected data, and the interrupt service routine also performs a read operation on RWL-protected data. When such recursion occurs, the fact that the reader211,212. . .21nis operating recursively can be tracked by using a per-task counter for each reader that is incremented each time a recursive read operation is performed and decremented each time a recursive read operation completes.

In a further variation of the foregoing reader-writer locking technique, provision can be made for a writer181,182. . .18nto wait for a grace period before exiting its critical section in order to ensure that readers will see the writer's critical section updates. This may be desirable when the writer181,182. . .18nchanges the writer flag28(block152) or wakes up another writer (block158) without first implementing a memory ordering instruction, such as occurs when the writer acquires the R/W spinlock36(block148) protecting the R/W lock32.

In a still further variation of the foregoing reader-writer locking technique based on conventional read-copy update primitives, the fast path read acquisition logic22A could be implemented using the rcu_read_lock( ) primitive (which increments a counter without disabling preemption) and the fast path read release logic22B could be implemented by the rcu_read_unlock( ) primitive (which decrements the counter incremented by rcu_read_lock( )). Instead of using the synchronize_sched( ) primitive to implement the grace period processing logic34, this logic could be implemented by synchronize_rcu( ), which is designed to be used in conjunction with rcu_read_lock( ) and rcu_read_unlock( ).

Accordingly, an improved reader-writer locking technique has been disclosed that allows readers to access shared data with minimal overhead in the absence of a writer contending for the same data. It will be appreciated that the foregoing concepts may be variously embodied in any of a data processing system, a machine implemented method, and a computer program product in which programming means are provided by one or more machine-readable media for use in controlling a data processing system to perform the required functions. Exemplary machine-readable media for providing such programming means are shown by reference numeral200inFIG. 11. The media100are shown as being portable optical storage disks of the type that are conventionally used for commercial software sales, such as compact disk-read only memory (CD-ROM) disks, compact disk-read/write (CD-R/W) disks, and digital versatile disks (DVDs). Such media can store the programming means of the invention, either alone or in conjunction with another software product that incorporates the required functionality. The programming means could also be provided by portable magnetic media (such as floppy disks, flash memory sticks, etc.), or magnetic media combined with drive systems (e.g. disk drives), or media incorporated in data processing platforms, such as random access memory (RAM), read-only memory (ROM) or other semiconductor or solid state memory. More broadly, the media could comprise any electronic, magnetic, optical, electromagnetic, infrared, semiconductor system or apparatus or device, transmission or propagation medium or signal, or other entity that can contain, store, communicate, propagate or transport the programming means for use by or in connection with a data processing system, computer or other instruction execution system, apparatus or device. It will also be appreciated that the invention may be embodied in a combination of hardware logic and software elements, and that the software elements may include but are not limited to firmware, resident software, microcode, etc.

While various embodiments of the invention have been described, it should be apparent that many variations and alternative embodiments could be implemented in accordance with the invention. It is understood, therefore, that the invention is not to be in any way limited except in accordance with the spirit of the appended claims and their equivalents.