Asynchronous Grace-Period Primitives For User-Space Applications

BACKGROUND

00011. Field

0002The present disclosure relates to computer systems and methods in which data resources are shared among data consumers while preserving data integrity and consistency relative to each consumer. More particularly, the disclosure concerns an implementation of a mutual exclusion mechanism known as “read-copy update” in a user-level computing environment.

00032. Description of the Prior Art

0004By way of background, read-copy update (also known as “RCU”) is a mutual exclusion technique that permits shared data to be accessed for reading without the use of locks, writes to shared memory, memory barriers, atomic instructions, or other computationally expensive synchronization mechanisms, while still permitting the data to be updated (modify, delete, insert, etc.) concurrently. The technique is well suited to both uniprocessor and multiprocessor computing environments wherein the number of read operations (readers) accessing a shared data set is large in comparison to the number of update operations (updaters), and wherein the overhead cost of employing other mutual exclusion techniques (such as locks) for each read operation would be high. By way of 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 read-side lock acquisition would be quite burdensome.

0005The read-copy update technique implements data updates in two phases. In the first (initial update) phase, the actual data update is carried out in a manner that temporarily preserves two views of the data being updated. One view is the old (pre-update) data state that is maintained for the benefit of read operations that may have been referencing the data concurrently with the update. The other view is the new (post-update) data state that is seen by operations that access the data following the update. In the second (deferred update) phase, the old data state is removed following a “grace period” that is long enough to ensure that the first group of read operations will no longer maintain references to the pre-update data. The second-phase update operation typically comprises freeing a stale data element to reclaim its memory. In certain RCU implementations, the second-phase update operation may comprise something else, such as changing an operational state according to the first-phase update.

0006<figref idref="DRAWINGS">FIGS. 1A-1D</figref> illustrate the use of read-copy update to modify a data element B in a group of data elements A, B and C. The data elements A, B, and C are arranged in a singly-linked list that is traversed in acyclic fashion, with each element containing a pointer to a next element in the list (or a NULL pointer for the last element) in addition to storing some item of data. A global pointer (not shown) is assumed to point to data element A, the first member of the list. Persons skilled in the art will appreciate that the data elements A, B and C can be implemented using any of a variety of conventional programming constructs, including but not limited to, data structures defined by C-language “struct” variables. Moreover, the list itself is a type of data structure.

0007It is assumed that the data element list of <figref idref="DRAWINGS">FIGS. 1A-1D</figref> is traversed (without locking) by multiple readers and occasionally updated by updaters that delete, insert or modify data elements in the list. In <figref idref="DRAWINGS">FIG. 1A</figref>, the data element B is being referenced by a reader r<b>1</b>, as shown by the vertical arrow below the data element. In <figref idref="DRAWINGS">FIG. 1B</figref>, an updater u<b>1</b> wishes to update the linked list by modifying data element B. Instead of simply updating this data element without regard to the fact that r<b>1</b> is referencing it (which might crash r<b>1</b>), u<b>1</b> preserves B while generating an updated version thereof (shown in <figref idref="DRAWINGS">FIG. 1C</figref> as data element B′) and inserting it into the linked list. This is done by u<b>1</b> acquiring an appropriate lock (to exclude other updaters), allocating new memory for B′, copying the contents of B to B′, modifying B′ as needed, updating the pointer from A to B so that it points to B′, and releasing the lock. In current versions of the Linux® kernel, pointer updates performed by updaters can be implemented using the rcu_assign_pointer( ) primitive. As an alternative to locking during the update operation, other techniques such as non-blocking synchronization or a designated update thread could be used to serialize data updates. All subsequent (post update) readers that traverse the linked list, such as the reader r<b>2</b>, will see the effect of the update operation by encountering B′ as they dereference B's pointer. On the other hand, the old reader r<b>1</b> will be unaffected because the original version of B and its pointer to C are retained. Although r<b>1</b> will now be reading stale data, there are many cases where this can be tolerated, such as when data elements track the state of components external to the computer system (e.g., network connectivity) and must tolerate old data because of communication delays. In current versions of the Linux® kernel, pointer dereferences performed by readers can be implemented using the rcu_dereference( ) primitive.

0008At some subsequent time following the update, r<b>1</b> will have continued its traversal of the linked list and moved its reference off of B. In addition, there will be a time at which no other reader process is entitled to access B. It is at this point, representing an expiration of the grace period referred to above, that u<b>1</b> can free B, as shown in <figref idref="DRAWINGS">FIG. 1D</figref>.

0009<figref idref="DRAWINGS">FIGS. 2A-2C</figref> illustrate the use of read-copy update to delete a data element B in a singly-linked list of data elements A, B and C. As shown in <figref idref="DRAWINGS">FIG. 2A</figref>, a reader r<b>1</b> is assumed be currently referencing B and an updater u<b>1</b> wishes to delete B. As shown in <figref idref="DRAWINGS">FIG. 2B</figref>, the updater u<b>1</b> updates the pointer from A to B so that A now points to C. In this way, r<b>1</b> is not disturbed but a subsequent reader r<b>2</b> sees the effect of the deletion. As shown in <figref idref="DRAWINGS">FIG. 2C</figref>, r<b>1</b> will subsequently move its reference off of B, allowing B to be freed following the expiration of a grace period.

0010In the context of the read-copy update mechanism, a grace period represents the point at which all running tasks (e.g., processes, threads or other work) having access to a data element guarded by read-copy update have passed through a “quiescent state” in which they can no longer maintain references to the data element, assert locks thereon, or make any assumptions about data element state. By convention, for operating system kernel code paths, a context switch, an idle loop, and user mode execution all represent quiescent states for any given CPU running non-preemptible code (as can other operations that will not be listed here). The reason for this is that a non-preemptible kernel will always complete a particular operation (e.g., servicing a system call while running in process context) prior to a context switch.

0011In <figref idref="DRAWINGS">FIG. 3</figref>, four tasks <b>0</b>, <b>1</b>, <b>2</b>, and <b>3</b> running on four separate CPUs are shown to pass periodically through quiescent states (represented by the double vertical bars). The grace period (shown by the dotted vertical lines) encompasses the time frame in which all four tasks that began before the start of the grace period have passed through one quiescent state. If the four tasks <b>0</b>, <b>1</b>, <b>2</b>, and <b>3</b> were reader tasks traversing the linked lists of <figref idref="DRAWINGS">FIGS. 1A-1D</figref> or <figref idref="DRAWINGS">FIGS. 2A-2C</figref>, none of these tasks having reference to the old data element B prior to the grace period could maintain a reference thereto following the grace period. All post grace period searches conducted by these tasks would bypass B by following the updated pointers created by the updater.

0012Grace periods may be synchronous or asynchronous. According to the synchronous technique, an updater performs the first phase update operation, blocks (waits) until a grace period has completed, and then implements the second phase update operation, such as by removing stale data. According to the asynchronous technique, an updater performs the first phase update operation, specifies the second phase update operation as a callback, then resumes other processing with the knowledge that the callback will eventually be processed at the end of a grace period. Advantageously, callbacks requested by one or more updaters can be batched (e.g., on callback lists) and processed as a group at the end of an asynchronous grace period. This allows asynchronous grace period overhead to be amortized over plural deferred update operations.

0013In operating system kernel implementations of RCU, callback registration and processing is performed by code sections whose execution is well-defined and highly deterministic. An example of such code is the call_rcu( ) primitive that registers a callback for deferred processing following an asynchronous grace period, and then invokes a callback processing primitive such as process callbacks( ) to execute one or more pending callbacks at the end of a grace period. The situation is less favorable when RCU is run in user space. Current user-level versions of the call_rcu( ) primitive have limitations due to the fact that user-level applications generally do not have the degree of control over execution that is typically found in kernels.

0014For example, the user-space rcu library for the LTTng (Linux Trace Toolkit) Project includes a defer_rcu( ) primitive that updaters use to queue RCU callbacks (see the urcu_defer.c and urcu_defer.h files at git://lttng.org/usrspace-rcu.git). The urcu_defer.c file contains a primitive named “rcu_defer_register_thread( ) that calls a primitive named “start_defer_thread( ) to create a thread for executing callbacks. However, within the defer_rcu( ) primitive itself, a call is made to synchronize_rcu( ) to force a synchronous grace period if there are too many pending callbacks. The advantage of forcing a synchronous grace period is that it avoids out-of-memory conditions that could otherwise result in cases where there were never any naturally occurring synchronize_rcu( ) invocations. Unfortunately, the above-described implementation of defer_rcu( ) will block updaters in some cases, and is therefore not fully deterministic. This may not be desirable for the critical path of a real-time application. In FIG. 11 of M. Desnoyers et al., “User-Level Implementations of Read-Copy Update”, IEEE Transactions On Parallel And Distributed Systems, Vol. X, No. Y, July 2009, pp. 1-14, a user-space call_rcu( ) primitive is proposed that would invoke a primitive named “call_rcu_cleanup( )” to process callbacks in a separate thread following a grace period so that updaters invoking call_rcu( ) will be wait-free. However, this proposal envisions only a single global callback processing thread, which could become overwhelmed in large multiprocessor systems and would suffer gratuitous cache-miss overhead when invoking callbacks registered on other processors. Implementing this approach would be problematic if real-time response is desired.

SUMMARY

0015A method, system and computer program product are provided for implementing user-level read-copy update (RCU) with support for asynchronous grace periods. In an example embodiment, a user-level RCU subsystem is established that executes within threads of a user-level multithreaded application. The multithreaded application may comprise one or more reader threads that read RCU-protected data elements in a shared memory. The multithreaded application may further comprise one or more updater threads that perform updates to the RCU-protected data elements in the shared memory and register callbacks to be executed following a grace period in order to free stale data resulting from the updates. The RCU subsystem implements two or more helper threads (helpers) that can be created or selected as needed to track grace periods and execute callbacks on behalf of the updaters instead of the updaters performing such work themselves.

0016In another embodiment, the two or more helper threads may include a default helper and one or more of a per-thread helper, a per-CPU helper or a per-node helper. In another embodiment, a single one of the two or more helper threads may be assigned to operate as the default thread and as one or more of the per-thread helper, the per-CPU helper or the per-node helper. In another embodiment, the two or more helper threads may each have an associated helper thread data structure whose fields may include a callback list header field, a flags field, a lock field, a condition field, a callback list length field, a helper thread identifier field and a list head field. In another embodiment, the RCU subsystem may comprise a register callback component that enqueues a callback on a callback list of one of the helper thread data structures and wakes up the data structure's associated helper thread. In another embodiment, the RCU subsystem comprises a grace period detection/callback processing component that is implemented by the two or more helper threads on behalf of the updaters. In another embodiment, the grace period detection/callback processing component processes callbacks while they are pending, then either (1) polls for a specified time period to await new callbacks if a real-time updater is being serviced, or (2) sleeps to await awakening if a non-real-time updater is being serviced. In another embodiment, the RCU subsystem comprises a set of helper thread functions for creating, ending, waking, querying and assigning the two or more helper threads.

BRIEF DESCRIPTION OF THE DRAWINGS

0017The foregoing and other features and advantages will be apparent from the following more particular description of example embodiments, as illustrated in the accompanying Drawings, in which:

0018<figref idref="DRAWINGS">FIGS. 1A-1D</figref> are diagrammatic representations of a linked list of data elements undergoing a data element replacement according to a conventional read-copy update mechanism;

0019<figref idref="DRAWINGS">FIGS. 2A-2C</figref> are diagrammatic representations of a linked list of data elements undergoing a data element deletion according to a conventional read-copy update mechanism;

0020<figref idref="DRAWINGS">FIG. 3</figref> is a flow diagram illustrating a grace period in which four processes pass through a quiescent state;

0021<figref idref="DRAWINGS">FIG. 4</figref> is a functional block diagram showing a multiprocessor computing system that may be implemented in accordance with the present disclosure;

0022<figref idref="DRAWINGS">FIG. 5</figref> is a functional block diagram showing a uniprocessor computing system that may be implemented in accordance with the present disclosure;

0023<figref idref="DRAWINGS">FIG. 6A</figref> is a functional block diagram showing an example set of updaters and per-thread helpers that may operate in the computer systems of <figref idref="DRAWINGS">FIGS. 4 and 5</figref>;

0024<figref idref="DRAWINGS">FIG. 6B</figref> is a functional block diagram showing an example set of updaters and per-CPU helpers that may operate in the computer systems of <figref idref="DRAWINGS">FIGS. 4 and 5</figref>;

0025<figref idref="DRAWINGS">FIG. 6C</figref> is a functional block diagram showing an example set of updaters and per-node helpers that may operate in the computer systems of <figref idref="DRAWINGS">FIGS. 4 and 5</figref>;

0026<figref idref="DRAWINGS">FIG. 6D</figref> is a functional block diagram showing an example set of updaters and a default helper that may operate in the computer systems of <figref idref="DRAWINGS">FIGS. 4 and 5</figref>;

0027<figref idref="DRAWINGS">FIG. 7</figref> is a functional block diagram showing an example RCU subsystem that includes two or more RCU subsystem helper thread data structures and a set of RCU subsystem support functions;

0028<figref idref="DRAWINGS">FIG. 8</figref> is a functional block diagram showing an example helper thread data structure;

0029<figref idref="DRAWINGS">FIG. 9</figref> is a block diagram showing examples of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 7</figref>;

0030<figref idref="DRAWINGS">FIG. 10</figref> is a flow diagram illustrating operations that may be performed by a create_helper component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0031<figref idref="DRAWINGS">FIG. 11</figref> is a flow diagram illustrating operations that may be performed by a create_per-CPU_helper component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0032<figref idref="DRAWINGS">FIG. 12</figref> is a flow diagram illustrating operations that may be performed by a free_helper component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0033<figref idref="DRAWINGS">FIG. 13</figref> is a flow diagram illustrating operations that may be performed by a wake_up_helper component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0034<figref idref="DRAWINGS">FIG. 14</figref> is a flow diagram illustrating operations that may be performed by a get_current_helper component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0035<figref idref="DRAWINGS">FIG. 15</figref> is a flow diagram illustrating operations that may be performed by a get_assigned_helper component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0036<figref idref="DRAWINGS">FIG. 16</figref> is a flow diagram illustrating operations that may be performed by a get_per-CPU_helper component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0037<figref idref="DRAWINGS">FIG. 17</figref> is a flow diagram illustrating operations that may be performed by a get_default_helper component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0038<figref idref="DRAWINGS">FIG. 18</figref> is a flow diagram illustrating operations that may be performed by a set_current_helper component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0039<figref idref="DRAWINGS">FIG. 19</figref> is a flow diagram illustrating operations that may be performed by a set_per-CPU_helper component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0040<figref idref="DRAWINGS">FIG. 20</figref> is a flow diagram illustrating operations that may be performed by a register callback component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>;

0041<figref idref="DRAWINGS">FIG. 21</figref> is a flow diagram illustrating operations that may be performed by an RCU grace period detection/callback processing component of the RCU subsystem support functions of <figref idref="DRAWINGS">FIG. 9</figref>; and

0042<figref idref="DRAWINGS">FIG. 22</figref> is a diagrammatic illustration showing example media that may be used to provide a computer program product in accordance with the present disclosure.

DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS

Introduction

0043The present disclosure describes an efficient technique for supporting asynchronous grace periods in user-level RCU implementations. According to example embodiments described in more detail below, the technique optionally provisions two or more helper threads to handle the RCU callbacks of one or more worker threads. In this context, a worker thread can be any thread that registers a callback for processing following an asynchronous grace period, such as by invoking a register callback component (see below). In most cases, worker threads will be updaters. However, the register callback component could also be invoked by readers while performing an update within an RCU read-side critical section, or could even be invoked during the processing of an RCU callback. In the former case, readers that invoke the register callback component would also be worker threads. In the latter case, helper threads that invoke the register callback component during callback processing would also be worker threads. However, such helper threads would most likely process new callbacks that they registered on there own behalf, but could conceivably invoke additional helper threads if desired.

0044The helper threads may have varying scope according to the number of worker threads they support. At one extreme, a single default system-wide helper thread may be provided to support all worker threads. At the other extreme, per-thread helper threads may be exclusively assigned to individual worker threads. Between these extremes, it would be possible to create many other worker thread/helper thread relationships, including but limited to per-processor helper threads that are assigned to worker threads on a given processor, per-node worker threads that are assigned to worker threads on a given node (e.g., for NUMA systems), etc. Helper threads may also be assigned to worker threads other means, including random or round-robin.

0045In an embodiment, each helper thread has a corresponding data structure whose elements may include a (1) helper thread callback list, (2) a helper thread identifier, (3) a helper thread lock, (4) a helper thread condition indicator, (5) a set of helper thread flags, (6) a helper thread callback counter, and (7) a list_head for maintaining the helper thread data structure on a list of helper thread data structures. Details of the helper thread data structures are described in more detail below.

0046In an embodiment, helper threads may be created in advance of any worker threads invoking the register callback component. Alternatively, the register callback component may be implemented so that it will create a new helper thread the first time it is invoked by a worker thread if there are no existing helper threads available. Prior to creating a new helper thread, the register callback component may look for existing helper threads that can be used on the worker thread's behalf. By way of example, the register callback component may look first for a per-thread helper thread that has already been assigned to the worker thread, then a per-CPU helper thread, and finally the system default helper thread. Once a suitable helper thread has been identified (or created if necessary), the register callback component can wake up the thread and cause it to perform the appropriate callback operations. These operations include registering a new callback, waiting for the end of a grace period, and processing the callbacks on its callback list. In an embodiment, a new helper thread may be assigned to a worker thread if the worker thread is migrated away from the part of the system serviced by its current helper thread. This feature (as well as others) may be implemented by way of a set of one or more helper thread support functions (such as those that are described in more detail below).

Example Embodiments

0047Turning now to the figures, wherein like reference numerals represent like elements in all of the several views, <figref idref="DRAWINGS">FIG. 4</figref> illustrates a symmetrical multiprocessor (SMP) computing system <b>2</b> is shown in which multiple processors <b>4</b>₁, <b>4</b>₂. . . <b>4</b>_nare connected by way of a common bus <b>6</b> to a shared memory <b>8</b>. Respectively associated with each processor <b>4</b>₁, <b>4</b>₂. . . <b>4</b>_nis a conventional cache memory <b>10</b>₁, <b>10</b>₂. . . <b>10</b>_nand a cache controller <b>12</b>₁, <b>12</b>₂. . . <b>12</b>_n. A conventional memory controller <b>14</b> is associated with the shared memory <b>8</b>. As shown, the memory controller <b>14</b> may reside separately from processors <b>4</b>₂. . . <b>4</b>_n(e.g., as part of a chipset). Alternatively, the memory controller <b>14</b> could be provided by plural memory controller instances respectively integrated with the processors <b>4</b>₂. . . <b>4</b>_n(as is known in the art). The computing system <b>2</b> is assumed to be under the management of a multitasking operating system adapted for use in an SMP environment.

0048In each of <figref idref="DRAWINGS">FIGS. 4 and 5</figref>, the example computing systems <b>2</b> and <b>2</b>A may represent any type of computing apparatus, including but not limited to, general purpose computers, special purpose computers, portable computing devices, communication and/or media player devices, set-top devices, embedded systems, to name but a few. In <figref idref="DRAWINGS">FIG. 4</figref>, the processors <b>4</b>₁, <b>4</b>₂. . . <b>4</b>_nmay each be implemented as an integrated single-core or multi-core CPU (Central Processing Unit) devices. Alternatively, the processors <b>4</b>₁, <b>4</b>₂. . . <b>4</b>_ncould represent individual cores within a single multi-core CPU device. In <figref idref="DRAWINGS">FIG. 5</figref>, the processor <b>4</b> may be a single-core or multi-core CPU device. Each processor <b>4</b> of <figref idref="DRAWINGS">FIGS. 4 and 5</figref> is operable to execute program instruction logic under the control of a software program stored in the memory <b>8</b> (or elsewhere). The memory <b>8</b> may comprise any type of tangible storage medium capable of storing data in computer readable form, including but not limited to, any of various types of random access memory (RAM), various flavors of programmable read-only memory (PROM) (such as flash memory), and other types of primary storage. In <figref idref="DRAWINGS">FIG. 5</figref>, the processor <b>4</b> and the memory <b>8</b> may be situated within a single computing device or node. In <figref idref="DRAWINGS">FIG. 4</figref>, the processors <b>4</b>₁, <b>4</b>₂. . . <b>4</b>_nmay be situated within a single computing device or node (e.g., as part of a single-node SMP system) or they may be distributed over plural nodes (e.g., as part of a NUMA system, a cluster, a cloud, etc.).

0049It is further assumed in <figref idref="DRAWINGS">FIG. 4</figref> that update operations executed within a user-level threads (or other user-level execution contexts) will periodically perform updates on a set of shared data <b>16</b> stored in the shared memory <b>8</b>. Reference numerals <b>18</b>₁, <b>18</b>₂. . . <b>18</b>_nillustrate individual user-level data update operations (updaters) that may periodically execute on the several processors <b>4</b>₁, <b>4</b>₂. . . <b>4</b>_n. Alternatively, as shown in <figref idref="DRAWINGS">FIG. 5</figref>, the updaters <b>18</b>₁, <b>18</b>₂. . . <b>18</b>_ncould all run on a single processor <b>4</b> that is either part of the multiprocessor computing system <b>2</b>, or is the sole processor of a uniprocessor computing system. As described by way of background above, the updates performed by the data updaters <b>18</b>₁, <b>18</b>₂. . . <b>18</b>_ncan include modifying elements of a linked list, inserting new elements into the list, deleting elements from the list, and many other types of operations. To facilitate such updates, the several processors <b>4</b>₁, <b>4</b>₂. . . <b>4</b>_nof <figref idref="DRAWINGS">FIG. 4</figref>, or the single processor <b>4</b> of <figref idref="DRAWINGS">FIG. 5</figref>, are programmed to implement a user-level read-copy update (RCU) subsystem <b>20</b> as part of their user-level application functions. In <figref idref="DRAWINGS">FIG. 4</figref>, the RCU subsystem <b>20</b> comprises RCU instances <b>20</b>₁, <b>20</b>₂. . . <b>20</b>_nthat periodically execute on the several processors <b>4</b>₁, <b>4</b>₂. . . <b>4</b>_n. Each of the processors <b>4</b>₁, <b>4</b>₂. . . <b>4</b>_nof <figref idref="DRAWINGS">FIG. 5</figref>, or the single processor of <figref idref="DRAWINGS">FIG. 4</figref>, also periodically execute user-level read operations (readers) <b>21</b>₁, <b>21</b>₂. . . <b>21</b>_non the shared data <b>16</b>. 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-copy update.

0050The updaters <b>18</b>₁, <b>18</b>₂. . . <b>18</b>_n, the readers <b>21</b>₁, <b>21</b>₂. . . <b>21</b>_n, and the RCU subsystem instances <b>20</b>₁, <b>20</b>₂. . . <b>20</b>_ncan be implemented as user-level threads within a multithreaded user-level program. As persons skilled in the art will appreciate, multithreaded programming is a form of parallel programming wherein several threads of control (also known as lightweight processes) may execute separately within a single application program. All threads share the same memory space, and can therefore work concurrently with shared data. The POSIX threads (pthreads) library is one example of a multithreaded implementation wherein each user-level thread is implemented by a kernel thread with scheduling support being provided by the underlying operating system (e.g., Linux®). In an alternate embodiment, the user-level threads could be provided entirely at the user level via implementations such as “Green threads.” In the example embodiments described hereinafter, a POSIX pthreads implementation is assumed for purposes of illustration only, and not by way of limitation.

0051The RCU subsystem <b>20</b> supports asynchronous grace periods. This type of grace period processing entails the management of callback lists that accumulate callbacks registered by the updaters <b>18</b>₁, <b>18</b>₂. . . <b>18</b>_nuntil they are ripe for batch processing at the end of a given grace period. Updaters may register callbacks using a user-level variant of the call_rcu( ) primitive found in existing RCU implementations. As discussed in the “Introduction” section above, the registered callbacks occasionally need to be processed in order to free the memory associated with stale data elements. In accordance with the present disclosure, callback processing efficiency is improved by offloading callback processing from the updaters <b>18</b>₁, <b>18</b>₂. . . <b>18</b>_n(worker threads) to two or more helper threads that can be created or selected as needed. This offloading is illustrated in <figref idref="DRAWINGS">FIGS. 6A-6D</figref>, each of which depicts two or more helper threads <b>22</b> that may be used by the updaters <b>18</b>₁, <b>18</b>₂. . . <b>18</b>_nin the system <b>2</b> of <figref idref="DRAWINGS">FIG. 4</figref> to perform callback processing.

0052In <figref idref="DRAWINGS">FIG. 6A</figref>, each updater <b>18</b>₁, <b>18</b>₂. . . <b>18</b>_nhas a corresponding per-thread helper thread <b>22</b>A₁, <b>22</b>A₂. . . <b>22</b>A_n. In <figref idref="DRAWINGS">FIG. 6B</figref>, updaters <b>18</b>₁and <b>18</b>₂on processor <b>4</b>₁share a per-cpu helper thread <b>22</b>B₁, and updaters <b>18</b>_n-1and <b>18</b><i>n </i>on processor <b>4</b>_mshare a per-cpu helper thread <b>22</b>B_x. In <figref idref="DRAWINGS">FIG. 6C</figref>, updaters <b>18</b>₁and <b>18</b>₂on processor <b>4</b>₁and updaters <b>18</b>_n-1and <b>18</b><i>n </i>on processor <b>4</b>_min a node <b>24</b> of the system <b>2</b> share a per-node cpu helper thread <b>22</b>C₁. Although not shown, other nodes in the system <b>2</b> could likewise have per-node helper threads <b>22</b>C₂. . . <b>22</b>C_y. In <figref idref="DRAWINGS">FIG. 6D</figref>, updaters <b>18</b>₁and <b>18</b>₂on processor <b>4</b>₁and updaters <b>18</b>_n-1and <b>18</b><i>n </i>on processor <b>4</b>_min the system <b>2</b> share a system-wide default helper thread <b>22</b>D.

0053It should be pointed out that the above-listed types of helper threads <b>22</b>A, <b>22</b>B, <b>22</b>C and <b>22</b>D are not necessarily provided by separate mutually exclusive helper threads <b>22</b>. In fact, any given helper thread <b>22</b> may be assigned to serve as a per-thread helper <b>22</b>A, a per-CPU helper <b>22</b>B, a per-node helper <b>22</b>C, and as the default helper <b>22</b>D. In some cases, a given helper thread <b>22</b> might have overlapping assignments, for example, as a both per-thread helper <b>22</b>A and as a per-CPU helper <b>22</b>B, and so on. Indeed, it would be possible for a single helper thread <b>22</b> to be assigned to play the role of all helper thread types listed above.

0054Turning now to <figref idref="DRAWINGS">FIG. 7</figref>, example components of the RCU subsystem <b>20</b> are shown. These components include several RCU subsystem data structures <b>24</b> and a set of RCU subsystem support functions <b>26</b>. The RCU subsystem data structures <b>24</b> include two or more helper thread data structures <b>28</b>. The RCU subsystem support functions <b>26</b> include an RCU reader API (Application Programming Interface) <b>30</b>, an RCU updater API <b>32</b>, a grace period detection/callback processing component <b>34</b>, and a helper thread API <b>36</b>.

0055The two or more helper thread data structures <b>28</b> respectively correspond to the two or more helper threads <b>22</b> shown in <figref idref="DRAWINGS">FIGS. 6A-6D</figref>. For example, one or more per-thread data structures <b>28</b>A₁, <b>28</b>A₂. . . <b>28</b>A_nmay be respectively associated with the per-thread helper threads <b>22</b>A₁, <b>22</b>A₂. . . <b>22</b>A_nof <figref idref="DRAWINGS">FIG. 6A</figref>. One or more per-CPU data structures <b>28</b>B₁, <b>28</b>B₂. . . <b>28</b>B_xmay be respectively associated with the per-CPU helper threads <b>22</b>B₁, <b>22</b>B₂. . . <b>22</b>B_xof <figref idref="DRAWINGS">FIG. 6B</figref>. One or more per-node data structures <b>28</b>C₁, <b>28</b>C₂. . . <b>28</b>C_ymay be respectively associated with the per-node helper threads <b>22</b>C₁, <b>22</b>C₂. . . <b>22</b>C_yof <figref idref="DRAWINGS">FIG. 6C</figref>. Finally, a default data structure <b>28</b>D may be associated with the default helper thread <b>22</b>D. Each of the foregoing helper thread data structures <b>28</b> may be linked together in a linked list, such as by incorporating a list head structure in each such data structure.

0056Because the helper threads <b>22</b> may serve in various roles, their associated helper thread data structures <b>28</b> may likewise play different roles. Indeed, the helper thread data structures <b>28</b> may be used to assign the helper threads <b>22</b> to their various roles. For example, to assign a helper thread <b>22</b> to the role of a per-thread helper <b>22</b>A, a pointer to the associated helper thread data structure <b>28</b> may be stored as a per-thread variable for a worker thread that will use the helper thread (e.g., an updater <b>18</b>). This will cause the helper thread data structure <b>28</b> to assume the role of a per-thread data structure <b>28</b>A. To assign a helper thread <b>22</b> to the role of a per-CPU helper <b>22</b>B, a pointer to the associated helper thread data structure <b>28</b> may be stored in an array of pointers to per-CPU data structures <b>28</b>B, with each array position corresponding to a particular processor <b>4</b>. This will cause the helper thread data structure <b>28</b> to assume the role of a per-CPU data structure <b>28</b>B. To assign a helper thread <b>22</b> to the role of a per-node helper <b>22</b>C, pointers to the associated helper thread data structure <b>28</b> may be stored in the per-CPU pointer array in association with each processor <b>4</b> located in a given node <b>24</b>. This will cause the helper thread data structure <b>28</b> to assume the role of a per-node data structure <b>28</b>C. To assign a helper thread <b>22</b> to the role of the default helper <b>22</b>D, a pointer to the associated helper thread data structure <b>28</b> may be stored as a global variable that is accessible by all threads. This will cause the helper thread data structure <b>28</b> to assume the role of the default data structure <b>28</b>D.

0057Turning now to <figref idref="DRAWINGS">FIG. 8</figref>, an example template for each of the helper thread data structures <b>28</b> is shown that may include seven fields. A first field <b>28</b>-<b>1</b> is a callback list header for a list of callbacks that an associated helper thread will manage and process at the end of a grace period. A second field <b>28</b>-<b>2</b> is used to various thread flags indicating the status of the associated thread. In an example embodiment the following status flags may be represented by setting/clearing bits in this field: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0058">(1) URCU_CALL_RCU_RT</li><li id="ul0002-0002" num="0059">(2) URCU_CALL_RCU_RUNNING</li><li id="ul0002-0003" num="0060">(3) URCU_CALL_RCU_STOP</li><li id="ul0002-0004" num="0061">(4) URCU_CALL_RCU_STOPPED <br /> The URCU_CALL_RCU_RT flag indicates whether the helper thread requires real-time response. In an example embodiment, this flag may be set by the least significant (lowermost) bit of the flags field <b>28</b>-<b>2</b>. The URCU_CALL_RCU_RUNNING flag indicates whether the associated helper thread <b>22</b> is running In an example embodiment, this flag may be set by the second lowermost bit of the flags field <b>28</b>-<b>2</b>. The URCU_CALL_RCU_STOP flag tells the associated helper thread <b>22</b> to stop. In an example embodiment, this flag may be set by the third lowermost bit of the flags field <b>28</b>-<b>2</b>. The URCU_CALL_RCU_STOPPED flag is set by the helper thread <b>22</b> when it does stop. In an example embodiment, this flag may be set by the fourth lowermost bit of the flags field <b>28</b>-<b>2</b>. </li></ul></li></ul>

0062The third field <b>28</b>-<b>3</b> of the helper thread data structure <b>28</b> is a lock for serializing access by the associated helper thread <b>22</b> to variables that are shared with other helper threads. In an example embodiment, the lock <b>28</b>-<b>3</b> may be implemented as a pthread mutex (mutual exclusion) lock. The fourth field <b>28</b>-<b>4</b> holds conventional pthread condition variables that are protected by the lock <b>28</b>-<b>3</b> and set by conventional pthread condition functions to support synchronization of the associated helper thread <b>22</b> with respect to other helper threads. Such condition functions allows the helper thread <b>22</b> to suspend execution and relinquish its processor until some predicate on shared data is satisfied. The basic operations on conditions are to (1) signal the condition (when the predicate becomes true), and wait for the condition, suspending the thread execution until another thread signals the condition. Examples condition functions include pthread_cond_init, pthread_cond_signal, and pthread_cond_wait. The pthread_cond_init function initializes the condition variable <b>28</b>-<b>4</b>. The pthread_cond_signal function restarts the helper thread <b>22</b> when the condition indicated by the condition variable has occurred. The pthread_cond_wait function waits for the condition variable <b>28</b>-<b>4</b> to be signaled.

0063The fifth field <b>28</b>-<b>5</b> of the helper thread data structure <b>28</b> is callback count variable that indicates the length of the callback list linked to the callback list header <b>28</b>-<b>1</b>. The sixth field <b>28</b>-<b>6</b> is a helper thread identifier that contains the pthread id number of the associated helper thread <b>22</b>. The seventh field <b>28</b>-<b>7</b> is a list head structure for queuing the helper thread data structure <b>28</b> on a list of helper thread data structures.

0064Turning now to <figref idref="DRAWINGS">FIG. 9</figref>, individual components of the RCU subsystem support functions <b>26</b> are shown. These components may be implemented in any suitable fashion, including within the readers and updaters themselves, or as library functions in a user-level library such as the POSIX threads library. The RCU reader API <b>30</b> comprises a reader registration component <b>30</b>-<b>1</b> and a reader unregistration component <b>32</b>-<b>1</b>. These components are respectively invoked by readers <b>21</b> as they enter and leave their RCU read-side critical sections in order to allow the RCU subsystem <b>20</b> to track reader quiescent states, with all processing performed outside of a set of bounded calls to the reader registration and reader unregistration components <b>30</b>-<b>1</b>/<b>30</b>-<b>2</b> being treated as a quiescent state. The operational details of the reader registration component <b>30</b>-<b>1</b> and the reader unregistration component <b>30</b>-<b>2</b> are not germane to the present disclosure and will therefore not be described. Suffice it to say that there are existing user-level RCU implementations whose reader registration and reader unregistration components may be used to implement the user-level RCU implementation described herein. See, for example, the user-level versions of rcu_read_lock( ) and rcu_read_unlock( ) described in commonly owned U.S. Published Patent Application No. 2010/0023946A1.

0065The RCU updater API <b>32</b> comprises a register callback component <b>32</b>-<b>1</b> for use in connection with asynchronous grace period processing, and may also include a synchronous grace period component <b>32</b>-<b>2</b>. The latter component may be implemented in conventional fashion and its details will therefore not be described. Any suitable user-level version of an RCU primitive such as synchronize_rcu( ) may be used. See, for example, the user-level version of synchronize_rcu( ) described in commonly owned U.S. Published Patent Application No. 2010/0023946A1. During update operations, an updater <b>18</b> may perform a first-phase update to a shared data element <b>16</b> and then invoke the synchronous grace period component to <b>32</b>-<b>2</b> to force a grace period. The updater <b>18</b> would block until the synchronous grace period has ended, then perform a second-phase update to free stale data from memory (or take other actions).

0066The register callback component <b>32</b>-<b>1</b> is used by updaters <b>18</b> to register a callback following a first-phase update to a shared data element <b>16</b>. A user-level version of the call_rcu( ) primitive may be used for this purpose. The details of this primitive will be described in more detail below in connection with <figref idref="DRAWINGS">FIG. 20</figref>. Its principal operations are to identify a helper thread <b>22</b> to act on behalf of the updater <b>18</b> (or create one if necessary), enqueue a callback on the callback list of the associated helper thread data structure <b>28</b>, and wake up the helper thread to perform asynchronous grace period detection and callback processing (i.e., by implementing the RCU grace period detection/callback processing component <b>34</b>).

0067The RCU grace period detection/callback processing component <b>34</b> performs the asynchronous grace period processing referred to in the previous paragraph. These operations are performed by the helper thread <b>22</b> that was invoked by the register callback component <b>32</b>-<b>1</b>. As described in more detail below, these operations comprise waiting for the end of an asynchronous grace period, at which point the callback list <b>28</b>-<b>1</b> of the associated helper thread data structure <b>28</b> is traversed in order to execute each callback that is ripe for processing.

0068The helper thread API <b>36</b> comprises various helper functions that provide an infrastructure for invoking and using the helper threads <b>22</b>. These helper functions may include a create_helper component <b>36</b>-<b>1</b>, a create_per-CPU_helper component <b>36</b>-<b>2</b>, a free_helper component <b>36</b>-<b>3</b>, a wake_up_helper component <b>36</b>-<b>4</b>, a get_current_helper component <b>36</b>-<b>5</b>, a get_assigned_helper component <b>36</b>-<b>6</b>, a get_per-CPU_helper component <b>36</b>-<b>7</b>, a get_default_helper component <b>36</b>-<b>8</b>, a set_current_helper component <b>36</b>-<b>9</b> and a set_per-CPU_helper component <b>36</b>-<b>10</b>.

0069Example operations of the create_helper component <b>36</b>-<b>1</b> are shown in <figref idref="DRAWINGS">FIG. 10</figref>. Block <b>40</b> creates a new helper thread data structure <b>28</b>. Block <b>42</b> initializes the helper thread data structure <b>28</b>. This initialization may include initializing the callback list <b>28</b>-<b>1</b>, setting the flag field <b>28</b>-<b>2</b> to indicate the URCU_CALL_RCU_RUNNING state, initializing the attributes of the lock <b>28</b>-<b>3</b>, and initializing the condition variable <b>28</b>-<b>4</b>. Block <b>44</b> adds the helper thread data structure to a linked list of such data structures. Block <b>46</b> launches the new helper thread <b>22</b>, such as by calling the POSIX pthread_create( ) function. The arguments to the pthread_create( ) function will specify the helper thread routine to be performed and the arguments to that routine. In accordance with the present disclosure, the helper thread routine is the grace period detection and callback processing component <b>36</b> and the argument to that routine is the new helper thread data structure <b>28</b>. The operations of the grace period detection and callback processing component <b>36</b> are described in more detail below.

0070The create_per_cpu_helpers component <b>36</b>-<b>1</b> is used to create a separate per-CPU helper thread <b>22</b>B for each processor <b>4</b> that may be present. Example operations are shown in <figref idref="DRAWINGS">FIG. 11</figref>, in which block <b>50</b>, allocates an array of pointers to the per-CPU helper threads <b>22</b>B and then block <b>52</b> populates the array by creating one such helper thread for each processor <b>4</b> that does not already have a per-CPU helper thread.

0071The free_helper component <b>36</b>-<b>2</b> ends a helper thread <b>22</b> and frees its associated helper thread data structure <b>28</b>. The caller should ensure that the helper thread <b>22</b> is no longer in use before invoking this component. Example operations are shown in <figref idref="DRAWINGS">FIG. 12</figref>, beginning with block <b>60</b>, which returns if an attempt is made to free the default helper thread <b>22</b>D (or if the specified helper thread does not exist). In block <b>62</b>, a check is made to see if the helper thread <b>22</b> has any pending callbacks that need to be processed. If there are such callbacks, they are transferred to the default helper thread in block <b>64</b>. Following block <b>64</b>, or if there were no remaining callbacks in block <b>62</b>, the associated helper thread data structure <b>28</b> is freed from memory.

0072The wake_up_helper component <b>36</b>-<b>4</b> wakes up a helper thread <b>22</b> in order to perform callback processing, but only if the helper thread <b>22</b> is servicing a non-real-time worker thread. If the helper thread <b>22</b> is servicing a real-time worker thread (as indicated by the flags field <b>28</b>-<b>2</b> of the associated helper thread data structure <b>28</b> being set to URCU_CALL_RCU_RT), a wake-up signal is not used. Instead, the helper thread <b>22</b> polls to await new callbacks, as described in more detail below in connection with <figref idref="DRAWINGS">FIG. 21</figref>. The wake_up_helper component <b>36</b>-<b>4</b> is invoked by the register callback component <b>32</b>-<b>1</b>. Its wake-up operation is shown by block <b>70</b> in <figref idref="DRAWINGS">FIG. 13</figref>, which calls pthread_condition_signal to wake the helper thread, provided that the helper thread is not already running

0073The get_current_helper component <b>36</b>-<b>5</b> is invoked by updaters <b>18</b>. It returns a pointer to a helper thread data structure <b>28</b> for the updater's current helper thread <b>22</b>. Any per-thread helper <b>22</b>A assigned specifically to the updater <b>18</b> has first priority, followed by any per-CPU helper <b>22</b>B for the processor <b>4</b> which the updater is running, followed by the default helper <b>22</b>D, if their are no other helpers. Provision could also be made to check for a per-node helper <b>28</b>C if so desired. Example operations are shown in <figref idref="DRAWINGS">FIG. 14</figref>. Block <b>80</b> returns a pointer to the current per-thread data structure <b>28</b>A being used by the updater <b>18</b>, if there is one. If the updater <b>18</b> is not currently using a per-thread helper <b>22</b>A, block <b>82</b> returns a pointer to the current per-CPU data structure <b>28</b>B being used by the updater <b>18</b>, if there is one. If the updater <b>18</b> is not currently using a per-CPU helper <b>22</b>B, block <b>84</b> returns a pointer to the default data structure <b>28</b>D. If for some reason there is no default helper <b>22</b>D, block <b>84</b> will create it. As indicated above, the get_current_helper component <b>36</b>-<b>5</b> could be modified to check for and return a pointer the current per-node helper <b>22</b>C being used by the updater <b>18</b>, if there is one.

0074The get_assigned_helper component <b>36</b>-<b>6</b> returns a pointer to a per-thread data structure <b>28</b>A whose associated per-thread helper <b>22</b>A is hard-assigned to an updater <b>18</b>. A NULL pointer may be returned if the updater <b>18</b> is instead using a per-CPU helper <b>22</b>B or the default helper <b>22</b>D. This operation is shown by block <b>90</b> in <figref idref="DRAWINGS">FIG. 15</figref>.

0075The get_per-CPU_helper component <b>36</b>-<b>7</b> returns a pointer to a per-CPU data structure <b>28</b>B for a specified processor <b>4</b>. A NULL pointer may be returned if there is no per-CPU helper <b>22</b>B for the indicated processor. This operation is shown by block <b>100</b> in <figref idref="DRAWINGS">FIG. 16</figref>.

0076The get_default_helper component <b>36</b>-<b>8</b> returns a pointer to the default data structure <b>28</b>D, or creates such a data structure if necessary. This operation is shown by block <b>110</b> in <figref idref="DRAWINGS">FIG. 17</figref>.

0077The set_current_helper component <b>36</b>-<b>9</b> is called by an updater <b>18</b>. It sets the updater's helper thread using a local thread pointer variable that references a specified helper thread data structure <b>28</b>. The helper thread data structure <b>28</b> will thereafter serve as a hard-assigned per-thread data structure <b>28</b>A. This operation is shown by block <b>120</b> in <figref idref="DRAWINGS">FIG. 18</figref>.

0078The set_per-CPU_helper component <b>36</b>-<b>10</b> is used to set a processor's per-CPU helper thread <b>22</b>B. This may be done by setting a pointer to a specified helper thread data structure <b>28</b> in the previously-mentioned pointer array that stores pointers to per-CPU data structures <b>28</b>B. The specified data structure <b>28</b> will be assigned to role of a per-CPU thread data structure <b>28</b>B. This operation is shown by block <b>130</b> in <figref idref="DRAWINGS">FIG. 19</figref>. Note that the set_per-CPU helper_component <b>36</b>-<b>10</b> may be used to establish a per-node helper thread <b>22</b>C. For example, a helper thread <b>22</b> may be created using the create_helper component <b>36</b>-<b>1</b> for the node <b>24</b>. Then the set_per-CPU_helper component <b>36</b>-<b>10</b> may be invoked to assign the newly created helper thread <b>22</b> to each of the node's processors <b>4</b>.

0079Having now described the various components that may be used to implement the helper thread API, the operations of the register callback component <b>32</b>-<b>1</b> and the RCU grace_period_detection_and_callback_processing component <b>34</b> may be described in more detail.

0080The register callback component <b>32</b>-<b>1</b> is invoked by updaters <b>18</b> to schedule a callback function to be executed following the end of a grace period. These operations are performed by a helper thread <b>22</b> acting on behalf of worker threads that implement the updaters <b>18</b>. In most cases, the register callback component <b>32</b>-<b>1</b> will be the only function that an updater <b>18</b> needs to call in order to invoke a helper thread <b>22</b>. The various above-described components <b>36</b>-<b>1</b> . . . <b>36</b>-<b>10</b> of the helper thread API <b>36</b> are only needed by the updaters <b>18</b> to tune their use of RCU for maximum performance. Example operations of the register callback component <b>32</b>-<b>1</b> are shown in <figref idref="DRAWINGS">FIG. 20</figref>. Updaters <b>18</b> call this function with callback and its execution function serving as the function parameters. In block <b>140</b>, the register callback component <b>32</b>-<b>1</b> prepares the callback for enqueuing on a callback list. Block <b>142</b> parameters calls the get_current_helper component <b>36</b>-<b>5</b> described above in connection with <figref idref="DRAWINGS">FIG. 14</figref>. As previously described, this component will return the updater's current helper thread <b>22</b> (which may be a per-thread helper <b>22</b>A, a per-CPU helper <b>22</b>B, a per-node helper <b>22</b>C, or the default helper <b>22</b>D). Block <b>144</b> enqueues the callback on the callback list that is linked to the callback list header <b>28</b>-<b>1</b> of the helper thread's associated helper thread data structure <b>28</b>. This enqueuing may be performed using a conventional non-blocking enqueuing technique, as disclosed for example in M. Micheal et al., “Nonblocking algorithms and preemption-safe locking on multiprogrammed shared memory multiprocessors,” J. Parallel Distrib. Comput., vol. 51, no. 1, pp. 1-26, 1998. According to this technique, an atomic exchange operation is used to atomically update the callback list's tail pointer to reference the next pointer of the new callback, returning a pointer to the next pointer of the previous callback (or a pointer to the list header if there is no previous element). Then a pointer to the new element is non-atomically updated into the next pointer returned by the atomic exchange operation. This allows unconditional enqueuing in a fixed number of instructions. In block <b>146</b>, the callback counter <b>28</b>-<b>5</b> in the helper thread data structure <b>28</b> is incremented to reflect the addition of the new callback. Block <b>148</b> calls the wake_up_helper component <b>36</b>-<b>4</b> described above in connection with <figref idref="DRAWINGS">FIG. 13</figref>. This wakes up the helper thread <b>22</b> so that it can implement the RCU grace period detection/callback processing component <b>34</b>.

0081Example operations of the RCU grace period detection/callback processing component <b>34</b> are shown in <figref idref="DRAWINGS">FIG. 21</figref>. As discussed above, it is invoked by the register callback component <b>32</b>-<b>1</b>, with a pointer to a helper thread data structure <b>28</b> being passed as a parameter. In block <b>150</b>, a check is made for pending callbacks. If there are none (which is possible if the helper thread <b>22</b> was recently invoked by another worker thread to process callbacks, processing returns. If there are pending callbacks, block <b>152</b> separates them from the callback list linked to the callback list header <b>28</b>-<b>1</b> of the helper thread's associated helper thread data structure <b>28</b>. This allows new callbacks to accumulate for subsequent execution following a later grace period. Block <b>154</b> then forces a synchronous grace period and block <b>156</b> processes the callbacks when the grace period ends. At this point, it is desirable to have the helper thread <b>22</b> wait until there are more callbacks to processes. How this is handled depends on whether or not the helper thread <b>22</b> is servicing a real-time worker thread. Block <b>158</b> performs this check by inspecting the flags field <b>28</b>-<b>2</b> of the associated helper thread data structure <b>28</b> to see if the URCU_CALL_RCU_RT flag is set. If this is the case, it means that the worker thread will not explicitly signal the helper thread <b>22</b> to wakeup. The helper thread <b>22</b> may therefore poll for a selected time period in block <b>160</b> before returning to block <b>150</b> to check for more callbacks. On the other hand, if block <b>158</b> determines that the helper thread <b>22</b> is servicing a non-real-time thread, and provided there is no further work to do (i.e., there are no pending callbacks), the helper thread will be put to sleep in block <b>162</b> and the condition field <b>28</b>-<b>4</b> of the associated helper thread data structure <b>28</b> will be set to indicate this condition. Assuming the helper thread <b>22</b> is put to sleep, processing will return to block <b>150</b> after the thread is reawakened.

0082Accordingly, a technique for has been disclosed for effectively implementing asynchronous grace periods in a user-level RCU implementation. 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 logic is provided by one or more machine-useable storage media for use in controlling a data processing system to perform the required functions. Example embodiments of a data processing system and machine implemented method were previously described in connection with <figref idref="DRAWINGS">FIGS. 4-21</figref>. With respect to a computer program product, digitally encoded program instructions may be stored on one or more computer-readable data storage media for use in controlling a computer or other digital machine or device to perform the required functions. The program instructions may be embodied as machine language code that is ready for loading and execution by the machine apparatus, or the program instructions may comprise a higher level language that can be assembled, compiled or interpreted into machine language. Example languages include, but are not limited to C, C++, assembly, to name but a few. When implemented on a machine comprising a processor, the program instructions combine with the processor to provide a particular machine that operates analogously to specific logic circuits, which themselves could be used to implement the disclosed subject matter.

0083Example data storage media for storing such program instructions are shown by reference numerals <b>8</b> (memory) and <b>10</b> (cache) of the multiprocessor system <b>2</b> of <figref idref="DRAWINGS">FIG. 4</figref> and the uniprocessor system <b>2</b>A of <figref idref="DRAWINGS">FIG. 5</figref>. The systems <b>2</b> and <b>2</b>A may further include one or more secondary (or tertiary) storage devices (not shown) that could store the program instructions between system reboots. A further example of media that may be used to store the program instructions is shown by reference numeral <b>200</b> in <figref idref="DRAWINGS">FIG. 22</figref>. The media <b>200</b> are illustrated 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 program instructions either alone or in conjunction with an operating system or other software product that incorporates the required functionality. The data storage media could also be provided by portable magnetic storage media (such as floppy disks, flash memory sticks, etc.), or magnetic storage media combined with drive systems (e.g. disk drives). As is the case with the main memory <b>8</b> and the cache memories <b>10</b> of <figref idref="DRAWINGS">FIGS. 4 and 5</figref>, the storage media may be incorporated in data processing platforms that have integrated random access memory (RAM), read-only memory (ROM) or other semiconductor or solid state memory. More broadly, the storage media could comprise any electronic, magnetic, optical, infrared, semiconductor system or apparatus or device, or any other tangible entity representing a machine, manufacture or composition of matter that can contain, store, communicate, or transport the program instructions for use by or in connection with an instruction execution system, apparatus or device, such as a computer. For all of the above forms of storage media, when the program instructions are loaded into and executed by an instruction execution system, apparatus or device, the resultant programmed system, apparatus or device becomes a particular machine for practicing embodiments of the method(s) and system(s) described herein.

0084Although various example embodiments have been shown and described, it should be apparent that many variations and alternative embodiments could be implemented in accordance with the disclosure. 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.