Department of Information Technology
Department of Information Technology
Uppsala UniversityInformation TechnologySearch for staffHome
Listen

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.

Link to the paper

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:
The dualstack may contain either (1) all reservations, (2) all data, or (3) one datum at the top, followed by an arbitrary number of reservations. Case (3) will happen when a datum is pushed onto a stack consisting of all reservations; the datum is pushed, its adress written into the underlying reservation, and finally both nodes are popped from the stack. All other mixtures of reservations and data would be impossible, since a reservation on a stack with contained data would be directly matched, and vice versa.

Q2:
A history of an object is a sequence of invocation events and response events, where an invocation matches the next response in the sequence that has the same thread id. Such a history is linearizable if the (partial) order of its linearization points appear in the same order as the operations of some legal sequential history.
Stavros

Q1:
The dualstack may contain (a) just pop reservations, (b) just data from push operations or (c) pop reservations with a single pushed data cell on top. States (a) and (b) are trivial to justify. State (c) ensures that no additional elements may be pushed and subsequently popped earlier than the first element that is pushed.

Q2:
The history of an object is a (potentially infinite) sequence of method invocations by threads and responses to threads. Each response matches the most recent invocation from the same thread. A history is sequential if each response immediately follows its matching request and is legal according to the semantics of the object. Two histories are equivalent if their projections to each thread are identical. The history is linearizable if it is equivalent to some legal sequential history.
Martin

Q1:
The dualstack may contain all reservations, all data, or a single data item at the top, followed by all reservations.

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:
A history is a sequence of invocation and response events. A history is linearizable if all events that happen before other events on the same thread also happens in that order in some legal sequential history where every response immediately follows its matching invocation.
Kjell

Q1:
The dual stack can contain:

  • Just data elements
  • Just reservations
  • One data element at the top followed by one or more reservation

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:
A history of an object can be described as a set of of tuples {Event,Time} where Event is a request to the object or a response and Time is the time when the Event happened. A history is linearizable if one can select a point in time (linearization point) between all requests and the corresponding responses so that a sequence of { {Request,Response}, linearization point} tuples (sorted by linearization point) can be created that would make sense if the methods where executed by a single thread.

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:
Updated  2013-06-19 12:27:42 by Kjell Winblad.