Non-blocking Concurrent Data Structures with Condition Synchronization
Description (Abstract)
We apply the classic theory of linearizability to operations that must wait for some other thread to establish a precondition. We model such an operation as a request and a follow-up, each with its own linearization point. Linearization of the request marks the point at which a thread´s wishes become visible to its peers; linearization of the follow-up marks the point at which the request is fulfilled and the operation takes effect. By placing both linearization points within the purview of object semantics, we can specify not only the effects of operations, but also the order in which pending requests should be fulfilled. We use the term dual data structure to describe a concurrent object implementation that may hold both data and reservations (registered requests). By reasoning separately about a request, its successful follow-up, and the period in-between, we obtain meaningful definitions of nonblocking dual data structures. As concrete examples, we present lock-free dualstacks and dualqueues, and experimentally compare their performance with that of lock-based and nonblocking alternatives. |
Questions
Question 1: There are restrictions on what the dualstack may contain (reservations and/or data). What are these restrictions and why are they necessary?
Question 2: What is a linearizable history (of a concurrent object)?
Magnus
Q1: Q2: |
Stavros
Q1: Q2: |
Martin
Q1: Since reservation and data items pairs up, it should not be possible to have both types in the stack. However, push always pushes a data node even if the top of the stack has a matching reservation. The purpose of this is to prevent other threads from finishing subsequent operations before the matching is completed, which would break the LIFO order. Q2: |
Kjell
Q1:
A thread checks if a data element followed by a request is at the top of the stack before replacing the top. If the top is a data element followed by a request, the thread tries to match the data element with the request before proceeding. Q2: |
Yunyun
Q1: The dualstack always contains 1) all reservations, 2) all data, 3) one datum at the top followed by reseravations. The restrictions ensure that no other threads push new data into the stack and matches the subsequent reservations before the the match of the top datum and the first reservation finishes. Q2: A history of an object is a seqence of method invocations and responses. A sequential history is a sequence of such events where an invocation is followed by the matching response right away. A history is linearizable if 1) it has the same set of the events as a sequential history 2)for all the events in some thread of the sequential history, if one method finishes before the other starts, then it is the same in this history. |
Name
Q1: Q2: |