|
In computer operating systems, read-copy-update (RCU) is a synchronization mechanism implementing a kind of mutual exclusion〔RCU does not implement mutual exclusion in the conventional sense: RCU readers can and do run concurrently with RCU updates. RCU's variant of mutual exclusion is in space, with RCU readers accessing old versions of data being concurrently updated, rather than in time, as is the case for conventional concurrency-control mechanisms.〕 that can sometimes be used as an alternative to a readers-writer lock. It allows extremely low overhead, wait-free reads. However, RCU updates can be expensive, as they must leave the old versions of the data structure in place to accommodate pre-existing readers. These old versions are reclaimed after all pre-existing readers finish their accesses. ==Overview== A key property of RCU is that readers can access a data structure even when it is in the process of being updated: There is absolutely nothing that RCU updaters can do to block readers or even to force them to retry their accesses. This overview starts by showing how data can be safely inserted into and deleted from linked structures despite concurrent readers. The first diagram on the right depicts a four-state insertion procedure, with time advancing from left to right. The first state shows a global pointer named that is initially , colored red to indicate that it might be accessed by a reader at any time, thus requiring updaters to take care. Allocating memory for a new structure transitions to the second state. This structure has indeterminate state (indicated by the question marks) but is inaccessible to readers (indicated by the green color). Because the structure is inaccessible to readers, the updater may carry out any desired operation without fear of disrupting concurrent readers. Initializing this new structure transitions to the third state, which shows the initialized values of the structure's fields. Assigning a reference to this new structure to transitions to the fourth and final state. In this state, the structure is accessible to readers, and is therefore colored red. The primitive is used to carry out this assignment, and ensures that the assignment is atomic in the sense that concurrent readers will either see a pointer or a valid pointer to the new structure, but not some mash-up of the two values. Additional properties of are described later in this article. This procedure demonstrates how new data may be inserted into a linked data structure even though readers are concurrently traversing the data structure before, during, and after the insertion. The second diagram on the right depicts a four-state deletion procedure, again with time advancing from left to right. The first state shows a linked list containing elements , , and . All three elements are colored red to indicate that an RCU reader might reference any of them at any time. Using to remove element from this list transitions to the second state. Note that the link from element B to C is left intact in order to allow readers currently referencing element to traverse the remainder of the list. Readers accessing the link from element will either obtain a reference to element or element , but either way, each reader will see a valid and correctly formatted linked list. Element is now colored yellow to indicate that while pre-existing readers might still have a reference to element , new readers have no way to obtain a reference. A wait-for-readers operation transitions to the third state. Note that this wait-for-readers operation need only wait for pre-existing readers, but not new readers. Element is now colored green to indicate that readers can no longer be referencing it. Therefore, it is now safe for the updater to free element , thus transitioning to the fourth and final state. It is important to reiterate that in the second state different readers can see two different versions of the list, either with or without element . In other words, RCU provides coordination in space (different versions of the list) as well as in time (different states in the deletion procedures). This is in stark contrast with more traditional synchronization primitives such as locking or transactions that coordinate in time, but not in space. This procedure demonstrates how old data may be removed from a linked data structure even though readers are concurrently traversing the data structure before, during, and after the deletion. Given insertion and deletion, a wide variety of data structures can be implemented using RCU. RCU's readers execute within ''read-side critical sections'', which are normally delimited by and . Any statement that is not within an RCU read-side critical section is said to be in a ''quiescent state'', and such statements are not permitted to hold references to RCU-protected data structures, nor is the wait-for-readers operation required to wait for threads in quiescent states. Any time period during which each thread resides at least once in a quiescent state is called a ''grace period''. By definition, any RCU read-side critical section in existence at the beginning of a given grace period must complete before the end of that grace period, which constitutes the fundamental guarantee provided by RCU. In addition, the wait-for-readers operation must wait for at least one grace period to elapse. It turns out that this guarantee can be provided with extremely small read-side overheads, in fact, in the limiting case that is actually realized by server-class Linux-kernel builds, the read-side overhead is exactly zero. RCU's fundamental guarantee may be used by splitting updates into ''removal'' and ''reclamation'' phases. The removal phase removes references to data items within a data structure (possibly by replacing them with references to new versions of these data items), and can run concurrently with RCU read-side critical sections. The reason that it is safe to run the removal phase concurrently with RCU readers is the semantics of modern CPUs guarantee that readers will see either the old or the new version of the data structure rather than a partially updated reference. Once a grace period has elapsed, there can no longer be any readers referencing the old version, so it is then safe for the reclamation phase to free (''reclaim'') the data items that made up that old version. Splitting an update into removal and reclamation phases allows the updater to perform the removal phase immediately, and to defer the reclamation phase until all readers active during the removal phase have completed, in other words, until a grace period has elapsed.〔Only readers that are active during the removal phase need be considered, because any reader starting after the removal phase will be unable to gain a reference to the removed data items, and therefore cannot be disrupted by the reclamation phase.〕 So the typical RCU update sequence goes something like the following: # Ensure that all readers accessing RCU-protected data structures carry out their references from within an RCU read-side critical section. # Remove pointers to a data structure, so that subsequent readers cannot gain a reference to it. # Wait for a grace period to elapse, so that all previous readers (which might still have pointers to the data structure removed in the prior step) will have completed their RCU read-side critical sections. # At this point, there cannot be any readers still holding references to the data structure, so it now may safely be reclaimed (e.g., freed).〔Garbage collectors, where available, may be used to perform this step.〕 In the above procedure (which matches the earlier diagram), the updater is performing both the removal and the reclamation step, but it is often helpful for an entirely different thread to do the reclamation. Reference counting can be used to let the reader perform removal so, even if the same thread performs both the update step (step (2) above) and the reclamation step (step (4) above), it is often helpful to think of them separately. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Read-copy-update」の詳細全文を読む スポンサード リンク
|