A new concurrency control mechanism for multi-threaded environment using transactional memory

Software transactional memory (STM) [20] is a promising technique to facilitate concurrent programming in modern multi-processor environment. A transaction in an STM executes series of reads and writes on shared data and then either commits or aborts. When two threads concurrently access the transactional data and at least one of these accesses is a write, conflict occurs.

The progress property of an STM demands that every transaction should eventually commit. The three different levels of progress guarantee for non-blocking process synchronization are wait freedom, lock freedom and obstruction freedom. The obstruction freedom [11] guarantees progress by ensuring that one thread makes progress if it executes in isolation. In presence of contention a transaction is allowed to abort the conflicting transaction or back off for arbitrary time interval to ensure progress [11, 12]. Thus, one of the major challenges for STM-based solutions is concurrent abort-free execution of transactions maintaining progress condition, and data consistency.

One of the notable STM implementations is DSTM (Software Transactional Memory for Dynamic-sized Data Structures) [12]. It offers an abort-free non-blocking synchronization approach that guarantees progress when a thread executes in isolation. When a transaction faces contention with another, it consults with contention manager to decide which transaction to delay or abort and when to restart an aborting transaction.

There exist a few STMs [2, 4‐6, 17] that have aimed to avoid spurious aborts. The propositions either use time stamp from a global clock [6], or maintain multiple versions [5, 17], or use conflict serializability scheduling as in [2, 4]. All these approaches are able to achieve abort-free execution for read-only transactions to some extent. However, none of them consider reducing abort for write transactions.

In very recent time, an obstruction-free non-blocking synchronization is proposed [8] that claims abort-free execution. However, the work in [8] is tailored for two concurrent transactions only. Moreover, the first transaction may be aborted by the second transaction under certain conditions. In this paper, we have proposed a new non-blocking, concurrency control approach for multi-threaded environment. The designing goal of the proposed algorithm is to allow multiple read and write transactions on the same data object. The proposed STM does not require aborting a transaction except towards handling a typical exception as detailed in procedure tryCommit (Step 50–58) of the algorithm proposed in Sect. 3. Thus, in this method every transaction with in a group is able to commit in a finite number of steps. The key idea of the algorithm is to create a chain of update transactions while accessing same data object concurrently. Every transaction in the chain shares the data value among them and always commits after satisfying certain conditions.

Although DSTM [12] is unable to provide desired progress guarantee, its implementation simplicity motivates us to build our solution using a data structure that is very similar to what is used for DSTM. Unlike DSTM, the proposed algorithm in Sect. 3 of this paper does not require any contention manager as the transactions are capable to resolve contention on their own.

The rest of the paper is organized as follows. Section 2 reviews the state of the art scenario for non-blocking process synchronization and explains some of its important terminologies and conceptions. In Sect. 3, the formal model of the proposed system is described. Section 4 presents the critical analysis of the proposed model. In Sect. 5, a comparative study of the proposed model is presented. The paper ends with concluding remarks in Sect. 6.

The non-blocking synchronization technique in STM implementation ensures that at least some threads must commit while running concurrently. This property is known as progress condition. STM provides two levels of progress [10] i.e., transactional memory level (TM-level) progress and transaction level progress. At TM-level, progress means completion of the individual TM operation, whereas at transaction level, progress implies execution of a thread through a successful commit. At either of these two levels, non-blocking synchronization technique ensures that a thread pre-empted during its execution cannot prevent other transaction to make progress. Depending on the level of progress, three types of non-blocking progress guarantees are found [15]. Among these, the obstruction freedom guarantees that a thread makes progress if it executes in isolation. In obstruction free transactional memory (OFTM) [11], a transaction T of a process P may be forcefully aborted, if it concurrently executes with some process other than P [9]. Thus, in presence of contention, choosing which transaction to abort and when to restart an aborting transaction is a crucial task. In order to cope up with the situation, OFTM takes help form contention manager. The contention management comprises of notification method for various events along with request methods that ask contention manager to make a decision. The notifications include beginning of a transaction, successful/unsuccessful commit, acquire of an object etc. The request method asks contention manager to decide whether to back off the transaction or to abort competing transactions [19].

The first OFTM that is implemented by Herlihy et al. [12], to manage dynamic set of data is known as DSTM (Software Transactional Memory for Dynamic-sized Data Structures). Since the inception of DSTM, several OFTM systems are implemented [7, 14, 16, 21] that work upon the limitations of OFTM and propose a better solution. All of them include contention management policies to avoid conflicts among transactions. However, any contention management policy for obstruction freedom always eventually aborts a competing transaction to avoid deadlock [18]. There are different types of contention management policies those are evolved to work with a specific OFTM and to achieve better throughput. Thus, selecting a specific contention manager for a particular OFTM is a challenging task. In [19], the experimental evaluation shows that improper selection of contention manager deteriorates the throughput.

There are few works [2, 5, 6, 17] on the conflict avoidance between transactions to reduce abort. These implementations either use time stamp from a global clock or maintain multiple versions or employ conflict serializability scheduling. In lazy Snapshot algorithm [6], every shared object gets a timestamp from a discrete logical global clock. The implementation retains multiple versions for each object and if sufficient versions available, then read-only transactions can commit without any back-off or abort. Multi-Version Permissive System (MV-Permissive) [17] also maintains multiple versions to avoid spurious aborts for read-only transactions. The SwissTM [5] combines global clock with hybrid conflict detection technique i.e., eager conflict detection for a write/write transactions and lazy conflict detection for read/write transactions. The approach gets best result when read transactions commit before writes. The garbage collection i.e., cleaning up of the older object versions is a challenging task for these algorithms. Moreover, they have focused on avoiding aborts for read-only transactions; how to reduce the number of aborts for write transaction has not been considered.

In [2], the conflict serializability model of database management system (DBMS) is introduced to reduce the rate of aborts. The system maintains a serializability order number for every transaction. In presence of contention, the transactions execute as per their order number without causing any abort. Construction of unique serializability order number is a crucial task as without this number the transaction cannot be serialized. Although this implementation is able to achieve a better throughput but cannot ensure that every transaction will commit in presence data accessing conflict.

In [4], a wait-free non-blocking synchronization is designed to exploit parallelism between read and write transactions without involving contention manager. The algorithm maintains a list of instructions for each sharable data object. A scheduler places the transactions’ instruction in the appropriate list. The list is chosen in such a way so that contention between transactions can be avoided. The major drawback of this implementation is that every transaction must know list of instructions in advance, which is a quite challenging task.

Attiya and Milani presented a BIMODAL transactional scheduler [1] in the context of read-dominated workload. The algorithm specially tailored for abort-free execution of read-only transactions without causing any delay to the early-write transaction most of the cases. The throughput of the algorithm is significantly deteriorated for late-write transactions, where updates are made at commit time.

The proposed work designs a new non-blocking algorithm to achieve concurrency control for multi-threaded environment. This non-blocking thread synchronization algorithm is an improvisation of OFTM that focuses on lowering transaction aborts for update-executions in presence of contention. The proposed method doesn’t require to include any existing contention management policies [19] as the update transactions are able to resolve conflicts themselves while accessing the sharable data concurrently.

In case of read–write contention, there are several comprehensive works and tested approaches towards lowering the abort for read executions in STM [2, 4, 5, 17]. This paper focuses on write–write contention and maintaining the read executions is beyond the scope of this paper.

The proposed methodology is based on the foundations of OFTM, while it provides a completely new mechanism for write transactions to execute concurrently while sharing common data object.

Suppose, \(T_1, T_2, T_3,\ldots ,T_k\) are consecutive write transactions in the chain. These transactions have formed the chain in the order as these are mentioned. The statements of Lemmas 1, 2 and 3 are stated for these transactions in the chain.

We have considered the efficiency of the proposed algorithm on the basis of transactions’ start time, access time of the sharable object and the execution length. The data sets are considered and grouped to cover all possible classes of scenarios that may occur between transactions in terms of these parameters As for example, a typical scenario may consider that the second transaction occurs at a time when the first transaction has already accessed the shared resource, but could not commit itself as the first transaction is yet to commit. In another scenario, the second transaction may occur and then start accessing the shared resource even before the first transaction could access the resource although first transaction is initiated before the second transaction. For each and every scenario, data sets are taken with random values in the range of that particular group. The throughput of the proposed STM is evaluated and compared with conventional lock-based concurrency control algorithm [3, 13] for each scenario.

The proposed algorithm has a single iterative step and it iterates exactly n times, where n is the number of transactions in the chain. If average time of execution for each transaction is \(\tau \), then the worst case performance is \(\hbox {O}\,(n\tau )\), which is equivalent to serial execution of the transactions one after another. However, the actual turn-around time for a group of n transactions would be much less than \(n\tau \), due to the concurrent execution of transactions.

It is not quite realistic to make a best-case or even an average-case time estimation for the proposed algorithm as execution time would depend on the relative length of successive transactions as well as on the actual time of accessing the shared data object. Thus, in this section, the performance evaluation is done using an abstracted view. All possible scenarios are grouped into three distinct types of cases in Sects. 5.1, 5.2 and 5.3. At first the different scenarios in terms of the access times of the successive transactions are considered for two arbitrary transactions \(T_1\) and \(T_2\), where transaction \(T_1\) is the immediate-predecessor transaction of \(T_2\). Subsequently, to make the analysis true for multiple transactions, the result set of five transactions executing in cascading manner and sharing same sharable object has been considered. In this section, we have included various diagrams regarding the commit process of two transactions in different scenarios for a better understandability. The tables in this section list some representative cases to study the effectiveness of the proposed algorithm. Figure 5 shows different symbols and abbreviated forms used in the diagrams and tables. In figures and tables, the legend for the proposed new STM is termed as PSTM for brevity. Few symbols and abbreviations (e.g. S, A, C etc.) those are self-explanatory are not described. The other abbreviations used in the tables and figures are as follows:

In this paper, a new non-blocking concurrency control mechanism for multi-threaded environment is proposed. The proposed STM aims to avoid aborting transactions excepting typical scenarios that may otherwise lead to a long denial of access to shared object. In this algorithm, when a write transaction faces contention with other

write transactions, it neither aborts the conflicting transaction nor backs off. Instead, the transaction adds itself as an element in the chain of write transactions and reads the data object. Thus, multiple write transactions are allowed to execute concurrently by forming a cascading chain of transactions without causing any immediate abort or back-off to any transactions. Moreover, the proposed method doesn’t include any additional contention manager as the transactions are able to resolve conflicts on their won. The uniqueness of the proposed implementation in this paper is in achieving reduced number of aborts for write transaction on top of obstruction-free non-blocking architecture. No such similar approach is found in the existing literature.