| Abstract |
Two well-known mechanisms for automatically executing sequential code segments in a
concurrent environment are universal constructions and software transactional memory.
They both have the same goal of simplifying the task of parallel programming. A universal
construction is a mechanism which takes as input the sequential code and executes it
in a concurrent environment. Software transactional memory (STM) employs transactions
to avoid conflicting accesses to common data (known as data items or transactional variables).
A transaction may either commit, in which case it appears as if it has been executed
at a single point in time, or abort, in which case it appears as if it is never executed. Notice
that if a transaction commits, then its updates to data items become visible, otherwise, if it
aborts, all its changes are discarded.
In this thesis, we study how to achieve increased concurrency while designing such
mechanisms, without sacrificing correctness and progress. One well-studied technique for
enhancing concurrency is ensuring a property called disjoint-access parallelism. Roughly
speaking, disjoint-access parallelism guarantees that processes operating on different parts
of an implemented object do not interfere with each other. Thus, disjoint-access parallel
implementations allow for increased parallelism.
Wait-freedom is a well-known progress property which ensures that each process completes
its execution, even when other processes run at arbitrary speeds or crash. Waitfreedom
is highly desirable because implementations ensuring this property are highly faulttolerant
and usually ensure bounds on the number of steps executed before an implemented
operation responds.
In this thesis, we prove that it is not possible for a universal construction to achieve
both disjoint-access parallelism and wait-freedom; this impossibility result holds for STM
as well. Specifically, we identify a natural property of universal constructions and prove
that there is no universal construction (with this property) that ensures both disjoint-access
parallelism and wait-freedom. Our impossibility proof is obtained by considering a dynamic
data structure that can grow arbitrarily large during an execution. This impossibility result
can be beaten if we focus on data structures that have a bound on the number of pieces
of data accessed by each operation they support. For this setting, we present a universal
construction that ensures both wait-freedom and disjoint-access parallelism.
We further introduce and study weaker versions of disjoint-access parallelism, which
still however allow for increased parallelism. Motivated be the way current STM algorithm
work, we introduce timestamp-ignoring disjoint-access parallelism, which allows operations
operating on different parts of an implemented data structure to proceed in parallel,
except for accesses to a timestamp object. A timestamp object allows a process to know the
“time” at which it accesses the object, relative to accesses by other processes (on the same
timestamp object); specifically, a process is able to determine whether it accessed the object
before or after some other process accessed it. We present a universal construction that ensures
wait-freedom and timestamp-ignoring disjoint-access parallelism, for certain classes
of data structures.
We next concentrate on important issues in achieving enhanced parallelism in STM
computing. Most STM algorithms employ an optimistic approach, where transactions are
executed speculatively, as if they will never read inconsistent data. When a conflict occurs,
STM algorithms usually abort one of the transactions to ensure correctness; two concurrent
transactions conflict if they both access the same data item and at least one of them
attempts to modify it. The work performed by a transaction that aborts is discarded and it
is later re-executed as a new transaction; this incurs a performance penalty. Moreover, for
read-intensive workloads, it is really important to ensure that transactions that never update
a data item (which are called read-only transactions) never abort and are wait-free; i.e. they
always commit within a finite number of steps. For these reasons, the literature also contains
pessimistic STM algorithms, which never abort transactions and support wait-freedom for
read-only transactions. However, most of them achieve this by “pessimistically” requiring
transactions that update data items (called update transactions) to be executed sequentially.
This significantly restricts parallelism in many cases and therefore it also leads to performance
degradation.
As a first step towards achieving enhanced parallelism, we introduce WFR-TM, an STM
algorithm which attempts to combine some of the advantages of pessimistic and optimistic
STM. In WFR-TM, as in pessimistic STMs, read-only transactions never abort and are wait-free. WFR-TM additionally ensures that read-only transactions never execute expensive
synchronization instructions. In contrast to pessimistic STMs, these properties are
achieved without sacrificing all parallelism between update transactions. More specifically,
update transactions use a pessimistic approach to synchronize with concurrently executed
read-only transactions: they wait for read-only transactions to complete. However, they use
an optimistic approach to synchronize with each other: they are executed concurrently in
a speculative way, and they commit if they have not encountered any conflict with other
update transactions during their execution. Thus, WFR-TM achieves more parallelism than
pessimistic STMs.
Finally, we introduce SemanticTM, an STM algorithm in which parallelism is achieved
at the level of transactional instructions; i.e. not only the transactions themselves but also
the instructions of each transaction may be executed concurrently. With compiler support,
SemanticTM guarantees that simple transactions are wait-free, by ensuring that no transactions
conflict. We remark that STM algorithms that never abort transactions are highly
desirable since they additionally support transactions that perform irrevocable operations,
e.g. I/O operations.
keywords: Asynchronous System, Shared-Memory, Concurrent Programming, Universal
Construction, Software Transactional Memory (STM), Optimistic STM, Pessimistic STM,
Disjoint-Access Parallelism, Wait-Freedom, Impossibility, Timestamps, Read-only Transactions,
Abort-Free Transactions, Fine-Grained Parallelism
|
Collections
