The non-blocking synchronization for these structures follows a common base structure. There is a version number per list. The DCAS primitive is used to atomically perform a write to a descriptor in a list and increment the version number, checking that the previous value of both has not been changed by a conflicting access to the list. Figure 2 illustrated this structure for deleting a descriptor from a list, where the single write to the descriptor was to change the link field of the predecessor descriptor. Inserting a new descriptor D entails initializing D, locating the descriptor in the linked list after which to insert D, writing the D's link field to point to the next descriptor, and then performing the DCAS to write the link field of this prior descriptor to D and to increment the version, checking both locations for contention as part of the update.
Dequeuing a descriptor from a TSM free list is a degenerate case of deletion because the dequeue always takes place from the head. It is possible to optimize this case and use a single CAS to dequeue without a version number. However, with efficient DCAS support, it is attractive to use DCAS with a version number to allow the version number to count the number of allocations that take place. (As another special case, an operation requiring at most two locations for the reads and writes can be updated directly using DCAS. We have used this approach with array-based stacks and FIFO queues.)
Some operations that involve multiple writes to the same descriptor
can be performed by creating a duplicate of this descriptor,
performing the modifications
and then atomically replacing the old descriptor by the new descriptor
if the list has not changed since the duplicate descriptor was created.
This approach is a variant of Herlihy's general
methodology [13]
which can convert a sequential implementation of any data structure into
a wait-free, concurrent one.
However, we use DCAS to ensure atomicity with respect to the entire
data structure (the scope of the version number)
even though we are only copying a single descriptor
.
As a variant of this approach,
the code can duplicate just a portion of the descriptor,
update it and use DCAS to insert it in place of the original
while updating a version number. If a thread fails
before completing the insertion, we rely on a TSM-based audit to
reclaim the
partially initialized descriptor after it is unclaimed for
time.
As a further optimization, some data structures allow a descriptor to be removed, modified and then reinserted as long as the deletion and the reinsertion are each done atomically. This optimization saves the cost of allocating and freeing a new descriptor compared to the previous approach. This approach requires that other operations can tolerate the inconsistency of this descriptor not being in the list for some period of time. For example, the Cache Kernel signal delivery relies on a list of threads to which a signal should be delivered. A thread fails to get the signal if it is not in the list at the time a signal is generated. However, we defined signal delivery to be best-effort because there are (other) reasons for signal drop so having signal delivery fail to a thread during an update is not a violation of the signal delivery semantics. Programming the higher-level software with best-effort signal delivery has required incorporating timeout and retry mechanisms but these are required for distributed operation in any case and do not add significant overhead [25]. These techniques, related to the transport-layer in network protocols, also make the system more resilient to faults.
Note that just having a search mechanism retry a search when it fails in conjunction with this approach can lead to deadlock. For example, if a signal handler that attempts to access descriptor D, retrying until successful, is called on the stack of a thread that has removed D to perform an update, the signal handler effectively deadlocks with the thread.